| /* |
| * 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.graph.GraphConstants.NODE_NOT_IN_GRAPH; |
| |
| import com.google.common.annotations.Beta; |
| import com.google.common.base.Function; |
| import com.google.common.base.Objects; |
| import com.google.common.collect.ImmutableSet; |
| import com.google.common.collect.Iterables; |
| import com.google.common.collect.Iterators; |
| import com.google.common.collect.Maps; |
| import com.google.errorprone.annotations.CanIgnoreReturnValue; |
| import java.util.Collection; |
| import java.util.HashSet; |
| import java.util.Iterator; |
| import java.util.Map; |
| import java.util.Optional; |
| import java.util.Set; |
| import org.checkerframework.checker.nullness.qual.Nullable; |
| |
| /** |
| * Static utility methods for {@link Graph}, {@link ValueGraph}, and {@link Network} instances. |
| * |
| * @author James Sexton |
| * @author Joshua O'Madadhain |
| * @since 20.0 |
| */ |
| @Beta |
| public final class Graphs { |
| |
| private Graphs() {} |
| |
| // Graph query methods |
| |
| /** |
| * Returns true if {@code graph} has at least one cycle. A cycle is defined as a non-empty subset |
| * of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting |
| * and ending with the same node. |
| * |
| * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1). |
| */ |
| public static <N> boolean hasCycle(Graph<N> graph) { |
| int numEdges = graph.edges().size(); |
| if (numEdges == 0) { |
| return false; // An edge-free graph is acyclic by definition. |
| } |
| if (!graph.isDirected() && numEdges >= graph.nodes().size()) { |
| return true; // Optimization for the undirected case: at least one cycle must exist. |
| } |
| |
| Map<Object, NodeVisitState> visitedNodes = |
| Maps.newHashMapWithExpectedSize(graph.nodes().size()); |
| for (N node : graph.nodes()) { |
| if (subgraphHasCycle(graph, visitedNodes, node, null)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Returns true if {@code network} has at least one cycle. A cycle is defined as a non-empty |
| * subset of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) |
| * starting and ending with the same node. |
| * |
| * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1). |
| */ |
| public static boolean hasCycle(Network<?, ?> network) { |
| // In a directed graph, parallel edges cannot introduce a cycle in an acyclic graph. |
| // However, in an undirected graph, any parallel edge induces a cycle in the graph. |
| if (!network.isDirected() |
| && network.allowsParallelEdges() |
| && network.edges().size() > network.asGraph().edges().size()) { |
| return true; |
| } |
| return hasCycle(network.asGraph()); |
| } |
| |
| /** |
| * Performs a traversal of the nodes reachable from {@code node}. If we ever reach a node we've |
| * already visited (following only outgoing edges and without reusing edges), we know there's a |
| * cycle in the graph. |
| */ |
| private static <N> boolean subgraphHasCycle( |
| Graph<N> graph, Map<Object, NodeVisitState> visitedNodes, N node, @Nullable N previousNode) { |
| NodeVisitState state = visitedNodes.get(node); |
| if (state == NodeVisitState.COMPLETE) { |
| return false; |
| } |
| if (state == NodeVisitState.PENDING) { |
| return true; |
| } |
| |
| visitedNodes.put(node, NodeVisitState.PENDING); |
| for (N nextNode : graph.successors(node)) { |
| if (canTraverseWithoutReusingEdge(graph, nextNode, previousNode) |
| && subgraphHasCycle(graph, visitedNodes, nextNode, node)) { |
| return true; |
| } |
| } |
| visitedNodes.put(node, NodeVisitState.COMPLETE); |
| return false; |
| } |
| |
| /** |
| * Determines whether an edge has already been used during traversal. In the directed case a cycle |
| * is always detected before reusing an edge, so no special logic is required. In the undirected |
| * case, we must take care not to "backtrack" over an edge (i.e. going from A to B and then going |
| * from B to A). |
| */ |
| private static boolean canTraverseWithoutReusingEdge( |
| Graph<?> graph, Object nextNode, @Nullable Object previousNode) { |
| if (graph.isDirected() || !Objects.equal(previousNode, nextNode)) { |
| return true; |
| } |
| // This falls into the undirected A->B->A case. The Graph interface does not support parallel |
| // edges, so this traversal would require reusing the undirected AB edge. |
| return false; |
| } |
| |
| /** |
| * Returns the transitive closure of {@code graph}. The transitive closure of a graph is another |
| * graph with an edge connecting node A to node B if node B is {@link #reachableNodes(Graph, |
| * Object) reachable} from node A. |
| * |
| * <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view |
| * of the transitive closure of {@code graph}. In other words, the returned {@link Graph} will not |
| * be updated after modifications to {@code graph}. |
| */ |
| // TODO(b/31438252): Consider potential optimizations for this algorithm. |
| public static <N> Graph<N> transitiveClosure(Graph<N> graph) { |
| MutableGraph<N> transitiveClosure = GraphBuilder.from(graph).allowsSelfLoops(true).build(); |
| // Every node is, at a minimum, reachable from itself. Since the resulting transitive closure |
| // will have no isolated nodes, we can skip adding nodes explicitly and let putEdge() do it. |
| |
| if (graph.isDirected()) { |
| // Note: works for both directed and undirected graphs, but we only use in the directed case. |
| for (N node : graph.nodes()) { |
| for (N reachableNode : reachableNodes(graph, node)) { |
| transitiveClosure.putEdge(node, reachableNode); |
| } |
| } |
| } else { |
| // An optimization for the undirected case: for every node B reachable from node A, |
| // node A and node B have the same reachability set. |
| Set<N> visitedNodes = new HashSet<N>(); |
| for (N node : graph.nodes()) { |
| if (!visitedNodes.contains(node)) { |
| Set<N> reachableNodes = reachableNodes(graph, node); |
| visitedNodes.addAll(reachableNodes); |
| int pairwiseMatch = 1; // start at 1 to include self-loops |
| for (N nodeU : reachableNodes) { |
| for (N nodeV : Iterables.limit(reachableNodes, pairwiseMatch++)) { |
| transitiveClosure.putEdge(nodeU, nodeV); |
| } |
| } |
| } |
| } |
| } |
| |
| return transitiveClosure; |
| } |
| |
| /** |
| * Returns the set of nodes that are reachable from {@code node}. Node B is defined as reachable |
| * from node A if there exists a path (a sequence of adjacent outgoing edges) starting at node A |
| * and ending at node B. Note that a node is always reachable from itself via a zero-length path. |
| * |
| * <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view |
| * of the set of nodes reachable from {@code node}. In other words, the returned {@link Set} will |
| * not be updated after modifications to {@code graph}. |
| * |
| * @throws IllegalArgumentException if {@code node} is not present in {@code graph} |
| */ |
| public static <N> Set<N> reachableNodes(Graph<N> graph, N node) { |
| checkArgument(graph.nodes().contains(node), NODE_NOT_IN_GRAPH, node); |
| return ImmutableSet.copyOf(Traverser.forGraph(graph).breadthFirst(node)); |
| } |
| |
| // Graph mutation methods |
| |
| // Graph view methods |
| |
| /** |
| * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other |
| * properties remain intact, and further updates to {@code graph} will be reflected in the view. |
| */ |
| public static <N> Graph<N> transpose(Graph<N> graph) { |
| if (!graph.isDirected()) { |
| return graph; // the transpose of an undirected graph is an identical graph |
| } |
| |
| if (graph instanceof TransposedGraph) { |
| return ((TransposedGraph<N>) graph).graph; |
| } |
| |
| return new TransposedGraph<N>(graph); |
| } |
| |
| /** |
| * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other |
| * properties remain intact, and further updates to {@code graph} will be reflected in the view. |
| */ |
| public static <N, V> ValueGraph<N, V> transpose(ValueGraph<N, V> graph) { |
| if (!graph.isDirected()) { |
| return graph; // the transpose of an undirected graph is an identical graph |
| } |
| |
| if (graph instanceof TransposedValueGraph) { |
| return ((TransposedValueGraph<N, V>) graph).graph; |
| } |
| |
| return new TransposedValueGraph<>(graph); |
| } |
| |
| /** |
| * Returns a view of {@code network} with the direction (if any) of every edge reversed. All other |
| * properties remain intact, and further updates to {@code network} will be reflected in the view. |
| */ |
| public static <N, E> Network<N, E> transpose(Network<N, E> network) { |
| if (!network.isDirected()) { |
| return network; // the transpose of an undirected network is an identical network |
| } |
| |
| if (network instanceof TransposedNetwork) { |
| return ((TransposedNetwork<N, E>) network).network; |
| } |
| |
| return new TransposedNetwork<>(network); |
| } |
| |
| static <N> EndpointPair<N> transpose(EndpointPair<N> endpoints) { |
| if (endpoints.isOrdered()) { |
| return EndpointPair.ordered(endpoints.target(), endpoints.source()); |
| } |
| return endpoints; |
| } |
| |
| // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of |
| // AbstractGraph) derives its behavior from calling successors(). |
| private static class TransposedGraph<N> extends ForwardingGraph<N> { |
| private final Graph<N> graph; |
| |
| TransposedGraph(Graph<N> graph) { |
| this.graph = graph; |
| } |
| |
| @Override |
| protected Graph<N> delegate() { |
| return graph; |
| } |
| |
| @Override |
| public Set<N> predecessors(N node) { |
| return delegate().successors(node); // transpose |
| } |
| |
| @Override |
| public Set<N> successors(N node) { |
| return delegate().predecessors(node); // transpose |
| } |
| |
| @Override |
| public Set<EndpointPair<N>> incidentEdges(N node) { |
| return new IncidentEdgeSet<N>(this, node) { |
| @Override |
| public Iterator<EndpointPair<N>> iterator() { |
| return Iterators.transform( |
| delegate().incidentEdges(node).iterator(), |
| new Function<EndpointPair<N>, EndpointPair<N>>() { |
| @Override |
| public EndpointPair<N> apply(EndpointPair<N> edge) { |
| return EndpointPair.of(delegate(), edge.nodeV(), edge.nodeU()); |
| } |
| }); |
| } |
| }; |
| } |
| |
| @Override |
| public int inDegree(N node) { |
| return delegate().outDegree(node); // transpose |
| } |
| |
| @Override |
| public int outDegree(N node) { |
| return delegate().inDegree(node); // transpose |
| } |
| |
| @Override |
| public boolean hasEdgeConnecting(N nodeU, N nodeV) { |
| return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose |
| } |
| |
| @Override |
| public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { |
| return delegate().hasEdgeConnecting(transpose(endpoints)); |
| } |
| } |
| |
| // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of |
| // AbstractValueGraph) derives its behavior from calling successors(). |
| private static class TransposedValueGraph<N, V> extends ForwardingValueGraph<N, V> { |
| private final ValueGraph<N, V> graph; |
| |
| TransposedValueGraph(ValueGraph<N, V> graph) { |
| this.graph = graph; |
| } |
| |
| @Override |
| protected ValueGraph<N, V> delegate() { |
| return graph; |
| } |
| |
| @Override |
| public Set<N> predecessors(N node) { |
| return delegate().successors(node); // transpose |
| } |
| |
| @Override |
| public Set<N> successors(N node) { |
| return delegate().predecessors(node); // transpose |
| } |
| |
| @Override |
| public int inDegree(N node) { |
| return delegate().outDegree(node); // transpose |
| } |
| |
| @Override |
| public int outDegree(N node) { |
| return delegate().inDegree(node); // transpose |
| } |
| |
| @Override |
| public boolean hasEdgeConnecting(N nodeU, N nodeV) { |
| return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose |
| } |
| |
| @Override |
| public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { |
| return delegate().hasEdgeConnecting(transpose(endpoints)); |
| } |
| |
| @Override |
| public Optional<V> edgeValue(N nodeU, N nodeV) { |
| return delegate().edgeValue(nodeV, nodeU); // transpose |
| } |
| |
| @Override |
| public Optional<V> edgeValue(EndpointPair<N> endpoints) { |
| return delegate().edgeValue(transpose(endpoints)); |
| } |
| |
| @Override |
| public @Nullable V edgeValueOrDefault(N nodeU, N nodeV, @Nullable V defaultValue) { |
| return delegate().edgeValueOrDefault(nodeV, nodeU, defaultValue); // transpose |
| } |
| |
| @Override |
| public @Nullable V edgeValueOrDefault(EndpointPair<N> endpoints, @Nullable V defaultValue) { |
| return delegate().edgeValueOrDefault(transpose(endpoints), defaultValue); |
| } |
| } |
| |
| private static class TransposedNetwork<N, E> extends ForwardingNetwork<N, E> { |
| private final Network<N, E> network; |
| |
| TransposedNetwork(Network<N, E> network) { |
| this.network = network; |
| } |
| |
| @Override |
| protected Network<N, E> delegate() { |
| return network; |
| } |
| |
| @Override |
| public Set<N> predecessors(N node) { |
| return delegate().successors(node); // transpose |
| } |
| |
| @Override |
| public Set<N> successors(N node) { |
| return delegate().predecessors(node); // transpose |
| } |
| |
| @Override |
| public int inDegree(N node) { |
| return delegate().outDegree(node); // transpose |
| } |
| |
| @Override |
| public int outDegree(N node) { |
| return delegate().inDegree(node); // transpose |
| } |
| |
| @Override |
| public Set<E> inEdges(N node) { |
| return delegate().outEdges(node); // transpose |
| } |
| |
| @Override |
| public Set<E> outEdges(N node) { |
| return delegate().inEdges(node); // transpose |
| } |
| |
| @Override |
| public EndpointPair<N> incidentNodes(E edge) { |
| EndpointPair<N> endpointPair = delegate().incidentNodes(edge); |
| return EndpointPair.of(network, endpointPair.nodeV(), endpointPair.nodeU()); // transpose |
| } |
| |
| @Override |
| public Set<E> edgesConnecting(N nodeU, N nodeV) { |
| return delegate().edgesConnecting(nodeV, nodeU); // transpose |
| } |
| |
| @Override |
| public Set<E> edgesConnecting(EndpointPair<N> endpoints) { |
| return delegate().edgesConnecting(transpose(endpoints)); |
| } |
| |
| @Override |
| public Optional<E> edgeConnecting(N nodeU, N nodeV) { |
| return delegate().edgeConnecting(nodeV, nodeU); // transpose |
| } |
| |
| @Override |
| public Optional<E> edgeConnecting(EndpointPair<N> endpoints) { |
| return delegate().edgeConnecting(transpose(endpoints)); |
| } |
| |
| @Override |
| public E edgeConnectingOrNull(N nodeU, N nodeV) { |
| return delegate().edgeConnectingOrNull(nodeV, nodeU); // transpose |
| } |
| |
| @Override |
| public E edgeConnectingOrNull(EndpointPair<N> endpoints) { |
| return delegate().edgeConnectingOrNull(transpose(endpoints)); |
| } |
| |
| @Override |
| public boolean hasEdgeConnecting(N nodeU, N nodeV) { |
| return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose |
| } |
| |
| @Override |
| public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { |
| return delegate().hasEdgeConnecting(transpose(endpoints)); |
| } |
| } |
| |
| // Graph copy methods |
| |
| /** |
| * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph |
| * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges} |
| * from {@code graph} for which both nodes are contained by {@code nodes}. |
| * |
| * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph |
| */ |
| public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes) { |
| MutableGraph<N> subgraph = |
| (nodes instanceof Collection) |
| ? GraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build() |
| : GraphBuilder.from(graph).build(); |
| for (N node : nodes) { |
| subgraph.addNode(node); |
| } |
| for (N node : subgraph.nodes()) { |
| for (N successorNode : graph.successors(node)) { |
| if (subgraph.nodes().contains(successorNode)) { |
| subgraph.putEdge(node, successorNode); |
| } |
| } |
| } |
| return subgraph; |
| } |
| |
| /** |
| * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph |
| * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges} |
| * (and associated edge values) from {@code graph} for which both nodes are contained by {@code |
| * nodes}. |
| * |
| * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph |
| */ |
| public static <N, V> MutableValueGraph<N, V> inducedSubgraph( |
| ValueGraph<N, V> graph, Iterable<? extends N> nodes) { |
| MutableValueGraph<N, V> subgraph = |
| (nodes instanceof Collection) |
| ? ValueGraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build() |
| : ValueGraphBuilder.from(graph).build(); |
| for (N node : nodes) { |
| subgraph.addNode(node); |
| } |
| for (N node : subgraph.nodes()) { |
| for (N successorNode : graph.successors(node)) { |
| if (subgraph.nodes().contains(successorNode)) { |
| subgraph.putEdgeValue( |
| node, successorNode, graph.edgeValueOrDefault(node, successorNode, null)); |
| } |
| } |
| } |
| return subgraph; |
| } |
| |
| /** |
| * Returns the subgraph of {@code network} induced by {@code nodes}. This subgraph is a new graph |
| * that contains all of the nodes in {@code nodes}, and all of the {@link Network#edges() edges} |
| * from {@code network} for which the {@link Network#incidentNodes(Object) incident nodes} are |
| * both contained by {@code nodes}. |
| * |
| * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph |
| */ |
| public static <N, E> MutableNetwork<N, E> inducedSubgraph( |
| Network<N, E> network, Iterable<? extends N> nodes) { |
| MutableNetwork<N, E> subgraph = |
| (nodes instanceof Collection) |
| ? NetworkBuilder.from(network).expectedNodeCount(((Collection) nodes).size()).build() |
| : NetworkBuilder.from(network).build(); |
| for (N node : nodes) { |
| subgraph.addNode(node); |
| } |
| for (N node : subgraph.nodes()) { |
| for (E edge : network.outEdges(node)) { |
| N successorNode = network.incidentNodes(edge).adjacentNode(node); |
| if (subgraph.nodes().contains(successorNode)) { |
| subgraph.addEdge(node, successorNode, edge); |
| } |
| } |
| } |
| return subgraph; |
| } |
| |
| /** Creates a mutable copy of {@code graph} with the same nodes and edges. */ |
| public static <N> MutableGraph<N> copyOf(Graph<N> graph) { |
| MutableGraph<N> copy = GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build(); |
| for (N node : graph.nodes()) { |
| copy.addNode(node); |
| } |
| for (EndpointPair<N> edge : graph.edges()) { |
| copy.putEdge(edge.nodeU(), edge.nodeV()); |
| } |
| return copy; |
| } |
| |
| /** Creates a mutable copy of {@code graph} with the same nodes, edges, and edge values. */ |
| public static <N, V> MutableValueGraph<N, V> copyOf(ValueGraph<N, V> graph) { |
| MutableValueGraph<N, V> copy = |
| ValueGraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build(); |
| for (N node : graph.nodes()) { |
| copy.addNode(node); |
| } |
| for (EndpointPair<N> edge : graph.edges()) { |
| copy.putEdgeValue( |
| edge.nodeU(), edge.nodeV(), graph.edgeValueOrDefault(edge.nodeU(), edge.nodeV(), null)); |
| } |
| return copy; |
| } |
| |
| /** Creates a mutable copy of {@code network} with the same nodes and edges. */ |
| public static <N, E> MutableNetwork<N, E> copyOf(Network<N, E> network) { |
| MutableNetwork<N, E> copy = |
| NetworkBuilder.from(network) |
| .expectedNodeCount(network.nodes().size()) |
| .expectedEdgeCount(network.edges().size()) |
| .build(); |
| for (N node : network.nodes()) { |
| copy.addNode(node); |
| } |
| for (E edge : network.edges()) { |
| EndpointPair<N> endpointPair = network.incidentNodes(edge); |
| copy.addEdge(endpointPair.nodeU(), endpointPair.nodeV(), edge); |
| } |
| return copy; |
| } |
| |
| @CanIgnoreReturnValue |
| static int checkNonNegative(int value) { |
| checkArgument(value >= 0, "Not true that %s is non-negative.", value); |
| return value; |
| } |
| |
| @CanIgnoreReturnValue |
| static long checkNonNegative(long value) { |
| checkArgument(value >= 0, "Not true that %s is non-negative.", value); |
| return value; |
| } |
| |
| @CanIgnoreReturnValue |
| static int checkPositive(int value) { |
| checkArgument(value > 0, "Not true that %s is positive.", value); |
| return value; |
| } |
| |
| @CanIgnoreReturnValue |
| static long checkPositive(long value) { |
| checkArgument(value > 0, "Not true that %s is positive.", value); |
| return value; |
| } |
| |
| /** |
| * An enum representing the state of a node during DFS. {@code PENDING} means that the node is on |
| * the stack of the DFS, while {@code COMPLETE} means that the node and all its successors have |
| * been already explored. Any node that has not been explored will not have a state at all. |
| */ |
| private enum NodeVisitState { |
| PENDING, |
| COMPLETE |
| } |
| } |