|
The Graphs.java Java example source code
/*
* Copyright (C) 2014 The Guava Authors
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.common.graph;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.graph.GraphConstants.ENDPOINTS_GRAPH_DIRECTEDNESS;
import static com.google.common.graph.GraphConstants.NETWORK_WITH_PARALLEL_EDGE;
import com.google.common.annotations.Beta;
import com.google.common.base.Function;
import com.google.common.base.Joiner;
import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
/**
* Static utility methods for {@link Graph} instances.
*
* @author Joshua O'Madadhain
* @since 20.0
*/
@Beta
public final class Graphs {
private static final String GRAPH_FORMAT = "%s, nodes: %s, edges: %s";
private static final String DIRECTED_FORMAT = "<%s -> %s>";
private static final String UNDIRECTED_FORMAT = "[%s, %s]";
private Graphs() {}
/**
* Returns the node at the other end of {@code edge} from {@code node}.
*
* @throws IllegalArgumentException if {@code edge} is not incident to {@code node}
*/
public static <N> N oppositeNode(Network graph, Object edge, Object node) {
checkNotNull(node, "node");
Endpoints<N> endpoints = graph.incidentNodes(edge);
if (node.equals(endpoints.nodeA())) {
return endpoints.nodeB();
} else {
checkArgument(node.equals(endpoints.nodeB()),
"Edge %s is not incident to node %s", edge, node);
return endpoints.nodeA();
}
}
/**
* Returns the subset of nodes in {@code graph} that have no predecessors.
*
* <p>Note that in an undirected graph, this is equivalent to all isolated nodes.
*/
public static <N> Set roots(final Graph graph) {
return Sets.filter(graph.nodes(), new Predicate<N>() {
@Override
public boolean apply(N node) {
return graph.predecessors(node).isEmpty();
}
});
}
/**
* Returns an unmodifiable view of edges that are parallel to {@code edge}, i.e. the set of edges
* that connect the same nodes in the same direction (if any). An edge is not parallel to itself.
*
* @throws IllegalArgumentException if {@code edge} is not present in {@code graph}
*/
public static <N, E> Set parallelEdges(Network graph, Object edge) {
Endpoints<N> endpoints = graph.incidentNodes(edge); // Verifies that edge is in graph
if (!graph.allowsParallelEdges()) {
return ImmutableSet.of();
}
return Sets.difference(graph.edgesConnecting(endpoints.nodeA(), endpoints.nodeB()),
ImmutableSet.of(edge)); // An edge is not parallel to itself.
}
/**
* Adds {@code edge} to {@code graph} with the specified {@code endpoints}.
*/
@CanIgnoreReturnValue
public static <N, E> boolean addEdge(MutableNetwork graph, E edge, Endpoints endpoints) {
checkNotNull(graph, "graph");
checkNotNull(edge, "edge");
checkNotNull(endpoints, "endpoints");
checkArgument(endpoints.isDirected() == graph.isDirected(),
ENDPOINTS_GRAPH_DIRECTEDNESS, endpoints.isDirected(), graph.isDirected());
return graph.addEdge(edge, endpoints.nodeA(), endpoints.nodeB());
}
/**
* Creates a mutable copy of {@code graph}, using the same nodes.
*/
public static <N> MutableGraph copyOf(Graph graph) {
return copyOfInternal(
graph,
GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()),
Predicates.alwaysTrue());
}
@SuppressWarnings("unchecked")
private static <N> MutableGraph copyOfInternal(
Graph<N> graph, GraphBuilder copyBuilder, Predicate nodePredicate) {
checkNotNull(graph, "graph");
checkNotNull(nodePredicate, "nodePredicate");
// TODO(b/28087289): we can remove this restriction when Graph supports parallel edges
checkArgument(!((graph instanceof Network) && ((Network<N, ?>) graph).allowsParallelEdges()),
NETWORK_WITH_PARALLEL_EDGE);
MutableGraph<N> copy = copyBuilder.build();
for (N node : Sets.filter(graph.nodes(), nodePredicate)) {
copy.addNode(node);
for (N successor : Sets.filter(graph.successors(node), nodePredicate)) {
// TODO(b/28087289): Ensure that multiplicity is preserved if parallel edges are supported.
copy.addEdge(node, successor);
}
}
return copy;
}
/**
* Copies all nodes from {@code src} into {@code dest}.
*/
public static <N> void copyNodes(Graph src, MutableGraph dest) {
copyNodesInternal(src, dest, Predicates.alwaysTrue());
}
private static <N, E> void copyNodesInternal(
Graph<N> src, MutableGraph dest, Predicate nodePredicate) {
checkNotNull(src, "src");
checkNotNull(dest, "dest");
checkNotNull(nodePredicate, "nodePredicate");
for (N node : Sets.filter(src.nodes(), nodePredicate)) {
dest.addNode(node);
}
}
/**
* Creates a mutable copy of {@code graph}, using the same node and edge elements.
*/
public static <N, E> MutableNetwork copyOf(Network graph) {
return copyOfInternal(
graph,
NetworkBuilder.from(graph)
.expectedNodeCount(graph.nodes().size())
.expectedEdgeCount(graph.edges().size()),
Predicates.alwaysTrue(),
Predicates.alwaysTrue());
}
private static <N, E> MutableNetwork copyOfInternal(
Network<N, E> graph,
NetworkBuilder<N, E> copyBuilder,
Predicate<? super N> nodePredicate,
Predicate<? super E> edgePredicate) {
checkNotNull(graph, "graph");
checkNotNull(nodePredicate, "nodePredicate");
checkNotNull(edgePredicate, "edgePredicate");
MutableNetwork<N, E> copy = copyBuilder.build();
copyNodesInternal(graph, copy, nodePredicate);
copyEdgesInternal(graph, copy, edgePredicate);
return copy;
}
/**
* Copies all nodes from {@code src} into {@code dest}.
*/
public static <N> void copyNodes(Graph src, MutableNetwork dest) {
copyNodesInternal(src, dest, Predicates.alwaysTrue());
}
private static <N, E> void copyNodesInternal(
Graph<N> src, MutableNetwork dest, Predicate nodePredicate) {
checkNotNull(src, "src");
checkNotNull(dest, "dest");
checkNotNull(nodePredicate, "nodePredicate");
for (N node : Sets.filter(src.nodes(), nodePredicate)) {
dest.addNode(node);
}
}
/**
* Copies edges from {@code src} into {@code dest}.
* <p>
* This method DOES NOT copy over edges if their incident nodes are not already in {@code dest}.
*/
public static <N, E> void copyEdges(Network src, MutableNetwork dest) {
copyEdgesInternal(src, dest, Predicates.alwaysTrue());
}
private static <N, E> void copyEdgesInternal(
Network<N, E> src, MutableNetwork dest, Predicate edgePredicate) {
checkNotNull(src, "src");
checkNotNull(dest, "dest");
checkNotNull(edgePredicate, "edgePredicate");
for (E edge : Sets.filter(src.edges(), edgePredicate)) {
Endpoints<N> endpoints = src.incidentNodes(edge);
if (dest.nodes().containsAll(endpoints)) {
addEdge(dest, edge, endpoints);
}
}
}
/**
* Returns true iff {@code graph1} and {@code graph2} have the same node connections.
*
* <p>Note: {@link Network} instances can only be equal to other {@link Network} instances.
* In particular, {@link Graph}s that are not also {@link Network}s cannot be equal
* to {@link Network}s.
*
* @see Network#equals(Object)
*/
public static boolean equal(@Nullable Graph<?> graph1, @Nullable Graph graph2) {
// If both graphs are Network instances, use equal(Network, Network) instead
if (graph1 instanceof Network && graph2 instanceof Network) {
return equal((Network<?, ?>) graph1, (Network) graph2);
}
// Otherwise, if either graph is a Network (but not both), they can't be equal.
if (graph1 instanceof Network || graph2 instanceof Network) {
return false;
}
if (graph1 == graph2) {
return true;
}
if (graph1 == null || graph2 == null) {
return false;
}
if (!graph1.nodes().equals(graph2.nodes())) {
return false;
}
for (Object node : graph1.nodes()) {
if (!graph1.successors(node).equals(graph2.successors(node))) {
return false;
}
boolean bothUndirected = !graph1.isDirected() && !graph2.isDirected();
if (!bothUndirected && !graph1.predecessors(node).equals(graph2.predecessors(node))) {
return false;
}
}
return true;
}
/**
* Returns true iff {@code graph1} and {@code graph2} have the same node/edge relationships.
*
* @see Network#equals(Object)
*/
public static boolean equal(@Nullable Network<?, ?> graph1, @Nullable Network graph2) {
if (graph1 == graph2) {
return true;
}
if (graph1 == null || graph2 == null) {
return false;
}
if (graph1.edges().size() != graph2.edges().size()) {
return false;
}
if (!graph1.nodes().equals(graph2.nodes())) {
return false;
}
for (Object node : graph1.nodes()) {
if (!graph1.inEdges(node).equals(graph2.inEdges(node))) {
return false;
}
boolean bothUndirected = !graph1.isDirected() && !graph2.isDirected();
if (!bothUndirected && !graph1.outEdges(node).equals(graph2.outEdges(node))) {
return false;
}
}
return true;
}
/**
* Returns the hash code of {@code graph}.
*
* @see Graph#hashCode()
*/
public static int hashCode(Graph<?> graph) {
if (graph instanceof Network) {
return hashCode((Network<?, ?>) graph);
}
return nodeToAdjacentNodes(graph).hashCode();
}
/**
* Returns the hash code of {@code graph}.
*
* @see Network#hashCode()
*/
public static int hashCode(Network<?, ?> graph) {
return nodeToIncidentEdges(graph).hashCode();
}
/**
* Returns a string representation of {@code graph}. Encodes edge direction if {@code graph}
* is directed.
*/
public static String toString(Graph<?> graph) {
if (graph instanceof Network) {
return toString((Network<?, ?>) graph);
}
return String.format(GRAPH_FORMAT,
getPropertiesString(graph),
graph.nodes(),
adjacentNodesString(graph));
}
/**
* Returns a string representation of {@code graph}. Encodes edge direction if {@code graph}
* is directed.
*/
public static String toString(Network<?, ?> graph) {
return String.format(GRAPH_FORMAT,
getPropertiesString(graph),
graph.nodes(),
Maps.asMap(graph.edges(), edgeToIncidentNodesString(graph)));
}
/**
* Returns a String of the adjacent node relationships for {@code graph}.
*/
private static <N> String adjacentNodesString(final Graph graph) {
checkNotNull(graph, "graph");
List<String> adjacencies = new ArrayList();
// This will list each undirected edge twice (once as [n1, n2] and once as [n2, n1]); this is OK
for (N node : graph.nodes()) {
for (N successor : graph.successors(node)) {
adjacencies.add(
String.format(
graph.isDirected() ? DIRECTED_FORMAT : UNDIRECTED_FORMAT,
node, successor));
}
}
return String.format("{%s}", Joiner.on(", ").join(adjacencies));
}
/**
* Returns a map that is a live view of {@code graph}, with nodes as keys
* and the set of incident edges as values.
*/
private static <N, E> Map> nodeToIncidentEdges(final Network graph) {
checkNotNull(graph, "graph");
return Maps.asMap(graph.nodes(), new Function<N, Set() {
@Override
public Set<E> apply(N node) {
return graph.incidentEdges(node);
}
});
}
/**
* Returns a map that is a live view of {@code graph}, with nodes as keys
* and the set of adjacent nodes as values.
*/
private static <N> Map> nodeToAdjacentNodes(final Graph graph) {
checkNotNull(graph, "graph");
return Maps.asMap(graph.nodes(), new Function<N, Set() {
@Override
public Set<N> apply(N node) {
return graph.adjacentNodes(node);
}
});
}
/**
* Returns a function that transforms an edge into a string representation of its incident nodes
* in {@code graph}. The function's {@code apply} method will throw an
* {@link IllegalArgumentException} if {@code graph} does not contain {@code edge}.
*/
private static Function<Object, String> edgeToIncidentNodesString(final Network graph) {
checkNotNull(graph, "graph");
return new Function<Object, String>() {
@Override
public String apply(Object edge) {
return graph.incidentNodes(edge).toString();
}
};
}
/**
* Returns a string representation of the properties of {@code graph}.
*/
// TODO(b/28087289): add allowsParallelEdges() once that's supported
private static String getPropertiesString(Graph<?> graph) {
if (graph instanceof Network) {
return getPropertiesString((Network<?, ?>) graph);
}
return String.format("isDirected: %s, allowsSelfLoops: %s",
graph.isDirected(), graph.allowsSelfLoops());
}
/**
* Returns a string representation of the properties of {@code graph}.
*/
private static String getPropertiesString(Network<?, ?> graph) {
return String.format("isDirected: %s, allowsParallelEdges: %s, allowsSelfLoops: %s",
graph.isDirected(), graph.allowsParallelEdges(), graph.allowsSelfLoops());
}
}
Other Java examples (source code examples)
Here is a short list of links related to this Java Graphs.java source code file:
|