```001/*
002 * Copyright (C) 2014 The Guava Authors
003 *
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
009 *
010 * Unless required by applicable law or agreed to in writing, software
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
018
021
027import java.util.ArrayDeque;
028import java.util.Collections;
029import java.util.HashSet;
031import java.util.Map;
032import java.util.Queue;
033import java.util.Set;
034import javax.annotation.Nullable;
035
036/**
037 * Static utility methods for {@link Graph} and {@link Network} instances.
038 *
039 * @author James Sexton
041 * @since 20.0
042 */
043@Beta
044public final class Graphs {
045
046  private Graphs() {}
047
048  // Graph query methods
049
050  /**
051   * Returns true if {@code graph} has at least one cycle. A cycle is defined as a non-empty subset
052   * of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting
053   * and ending with the same node.
054   *
055   * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
056   */
057  public static boolean hasCycle(Graph<?> graph) {
058    int numEdges = graph.edges().size();
059    if (numEdges == 0) {
060      return false; // An edge-free graph is acyclic by definition.
061    }
062    if (!graph.isDirected() && numEdges >= graph.nodes().size()) {
063      return true; // Optimization for the undirected case: at least one cycle must exist.
064    }
065
066    Map<Object, NodeVisitState> visitedNodes =
067        Maps.newHashMapWithExpectedSize(graph.nodes().size());
068    for (Object node : graph.nodes()) {
069      if (subgraphHasCycle(graph, visitedNodes, node, null)) {
070        return true;
071      }
072    }
073    return false;
074  }
075
076  /**
077   * Returns true if {@code network} has at least one cycle. A cycle is defined as a non-empty
078   * subset of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges)
079   * starting and ending with the same node.
080   *
081   * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
082   */
083  public static boolean hasCycle(Network<?, ?> network) {
084    // In a directed graph, parallel edges cannot introduce a cycle in an acyclic graph.
085    // However, in an undirected graph, any parallel edge induces a cycle in the graph.
086    if (!network.isDirected()
087        && network.allowsParallelEdges()
088        && network.edges().size() > network.asGraph().edges().size()) {
089      return true;
090    }
091    return hasCycle(network.asGraph());
092  }
093
094  /**
095   * Performs a traversal of the nodes reachable from {@code node}. If we ever reach a node we've
096   * already visited (following only outgoing edges and without reusing edges), we know there's a
097   * cycle in the graph.
098   */
099  private static boolean subgraphHasCycle(
100      Graph<?> graph,
101      Map<Object, NodeVisitState> visitedNodes,
102      Object node,
103      @Nullable Object previousNode) {
104    NodeVisitState state = visitedNodes.get(node);
105    if (state == NodeVisitState.COMPLETE) {
106      return false;
107    }
108    if (state == NodeVisitState.PENDING) {
109      return true;
110    }
111
112    visitedNodes.put(node, NodeVisitState.PENDING);
113    for (Object nextNode : graph.successors(node)) {
114      if (canTraverseWithoutReusingEdge(graph, nextNode, previousNode)
115          && subgraphHasCycle(graph, visitedNodes, nextNode, node)) {
116        return true;
117      }
118    }
119    visitedNodes.put(node, NodeVisitState.COMPLETE);
120    return false;
121  }
122
123  /**
124   * Determines whether an edge has already been used during traversal. In the directed case a cycle
125   * is always detected before reusing an edge, so no special logic is required. In the undirected
126   * case, we must take care not to "backtrack" over an edge (i.e. going from A to B and then going
127   * from B to A).
128   */
129  private static boolean canTraverseWithoutReusingEdge(
130      Graph<?> graph, Object nextNode, @Nullable Object previousNode) {
131    if (graph.isDirected() || !Objects.equal(previousNode, nextNode)) {
132      return true;
133    }
134    // This falls into the undirected A->B->A case. The Graph interface does not support parallel
135    // edges, so this traversal would require reusing the undirected AB edge.
136    return false;
137  }
138
139  /**
140   * Returns the transitive closure of {@code graph}. The transitive closure of a graph is another
141   * graph with an edge connecting node A to node B if node B is {@link #reachableNodes(Graph,
142   * Object) reachable} from node A.
143   *
144   * <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view
145   * of the transitive closure of {@code graph}. In other words, the returned {@link Graph} will not
146   * be updated after modifications to {@code graph}.
147   */
148  // TODO(b/31438252): Consider potential optimizations for this algorithm.
149  public static <N> Graph<N> transitiveClosure(Graph<N> graph) {
150    MutableGraph<N> transitiveClosure = GraphBuilder.from(graph).allowsSelfLoops(true).build();
151    // Every node is, at a minimum, reachable from itself. Since the resulting transitive closure
152    // will have no isolated nodes, we can skip adding nodes explicitly and let putEdge() do it.
153
154    if (graph.isDirected()) {
155      // Note: works for both directed and undirected graphs, but we only use in the directed case.
156      for (N node : graph.nodes()) {
157        for (N reachableNode : reachableNodes(graph, node)) {
158          transitiveClosure.putEdge(node, reachableNode);
159        }
160      }
161    } else {
162      // An optimization for the undirected case: for every node B reachable from node A,
163      // node A and node B have the same reachability set.
164      Set<N> visitedNodes = new HashSet<N>();
165      for (N node : graph.nodes()) {
166        if (!visitedNodes.contains(node)) {
167          Set<N> reachableNodes = reachableNodes(graph, node);
169          int pairwiseMatch = 1; // start at 1 to include self-loops
170          for (N nodeU : reachableNodes) {
171            for (N nodeV : Iterables.limit(reachableNodes, pairwiseMatch++)) {
172              transitiveClosure.putEdge(nodeU, nodeV);
173            }
174          }
175        }
176      }
177    }
178
179    return transitiveClosure;
180  }
181
182  /**
183   * Returns the set of nodes that are reachable from {@code node}. Node B is defined as reachable
184   * from node A if there exists a path (a sequence of adjacent outgoing edges) starting at node A
185   * and ending at node B. Note that a node is always reachable from itself via a zero-length path.
186   *
187   * <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view
188   * of the set of nodes reachable from {@code node}. In other words, the returned {@link Set} will
189   * not be updated after modifications to {@code graph}.
190   *
191   * @throws IllegalArgumentException if {@code node} is not present in {@code graph}
192   */
193  @SuppressWarnings("unchecked") // Safe because we only cast if node is an element of the graph.
194  public static <N> Set<N> reachableNodes(Graph<N> graph, Object node) {
195    checkArgument(graph.nodes().contains(node), NODE_NOT_IN_GRAPH, node);
196    Set<N> visitedNodes = new LinkedHashSet<N>();
197    Queue<N> queuedNodes = new ArrayDeque<N>();
200    // Perform a breadth-first traversal rooted at the input node.
201    while (!queuedNodes.isEmpty()) {
202      N currentNode = queuedNodes.remove();
203      for (N successor : graph.successors(currentNode)) {
206        }
207      }
208    }
209    return Collections.unmodifiableSet(visitedNodes);
210  }
211
212  /**
213   * Returns {@code true} if {@code graphA} and {@code graphB} have the same elements and the same
214   * relationships between elements, as exposed via the {@link Graph} interface.
215   *
216   * <p>Thus, two graphs A and B are equivalent if both are null or <b>all</b> of the following are
217   * true:
218   *
219   * <ul>
220   * <li>A and B have equal {@link Graph#isDirected() directedness}.
221   * <li>A and B have equal {@link Graph#nodes() node sets}.
222   * <li>A and B have equal {@link Graph#edges() edge sets}.
223   * </ul>
224   *
225   * <p>Graph properties besides {@link Graph#isDirected() directedness} do <b>not</b> affect
226   * equivalence. For example, two graphs may be considered equivalent even if one allows self-loops
227   * and the other doesn't. Additionally, the order in which nodes or edges are added to the graph,
228   * and the order in which they are iterated over, are irrelevant.
229   */
230  public static boolean equivalent(@Nullable Graph<?> graphA, @Nullable Graph<?> graphB) {
231    if (graphA == graphB) {
232      return true;
233    }
234    if (graphA == null || graphB == null) {
235      return false;
236    }
237
238    return graphA.isDirected() == graphB.isDirected()
239        && graphA.nodes().equals(graphB.nodes())
240        && graphA.edges().equals(graphB.edges());
241  }
242
243  /**
244   * Returns {@code true} if {@code graphA} and {@code graphB} have the same elements (including
245   * edge values) and the same relationships between elements, as exposed via the {@link ValueGraph}
246   * interface.
247   *
248   * <p>Thus, two value graphs A and B are equivalent if both are null or <b>all</b> of the
249   * following are true:
250   *
251   * <ul>
252   * <li>A and B have equal {@link Graph#isDirected() directedness}.
253   * <li>A and B have equal {@link Graph#nodes() node sets}.
254   * <li>A and B have equal {@link Graph#edges() edge sets}.
255   * <li>Each edge in A has a {@link ValueGraph#edgeValue(Object, Object) value} equal to the {@link
256   *     ValueGraph#edgeValue(Object, Object) value} of the corresponding edge in B.
257   * </ul>
258   *
259   * <p>Graph properties besides {@link Graph#isDirected() directedness} do <b>not</b> affect
260   * equivalence. For example, two graphs may be considered equivalent even if one allows self-loops
261   * and the other doesn't. Additionally, the order in which nodes or edges are added to the graph,
262   * and the order in which they are iterated over, are irrelevant.
263   */
264  public static boolean equivalent(
265      @Nullable ValueGraph<?, ?> graphA, @Nullable ValueGraph<?, ?> graphB) {
266    if (graphA == graphB) {
267      return true;
268    }
269    if (graphA == null || graphB == null) {
270      return false;
271    }
272
273    if (graphA.isDirected() != graphB.isDirected()
274        || !graphA.nodes().equals(graphB.nodes())
275        || !graphA.edges().equals(graphB.edges())) {
276      return false;
277    }
278
279    for (EndpointPair<?> edge : graphA.edges()) {
280      if (!graphA
281          .edgeValue(edge.nodeU(), edge.nodeV())
282          .equals(graphB.edgeValue(edge.nodeU(), edge.nodeV()))) {
283        return false;
284      }
285    }
286
287    return true;
288  }
289
290  /**
291   * Returns {@code true} if {@code networkA} and {@code networkB} have the same elements and the
292   * same relationships between elements, as exposed via the {@link Network} interface.
293   *
294   * <p>Thus, two networks A and B are equivalent if both are null or <b>all</b> of the following
295   * are true:
296   *
297   * <ul>
298   * <li>A and B have equal {@link Network#isDirected() directedness}.
299   * <li>A and B have equal {@link Network#nodes() node sets}.
300   * <li>A and B have equal {@link Network#edges() edge sets}.
301   * <li>Each edge in A connects the same nodes in the same direction (if any) as the corresponding
302   *     edge in B.
303   * </ul>
304   *
305   * <p>Network properties besides {@link Network#isDirected() directedness} do <b>not</b> affect
306   * equivalence. For example, two networks may be considered equal even if one allows parallel
307   * edges and the other doesn't. Additionally, the order in which nodes or edges are added to the
308   * network, and the order in which they are iterated over, are irrelevant.
309   */
310  public static boolean equivalent(
311      @Nullable Network<?, ?> networkA, @Nullable Network<?, ?> networkB) {
312    if (networkA == networkB) {
313      return true;
314    }
315    if (networkA == null || networkB == null) {
316      return false;
317    }
318
319    if (networkA.isDirected() != networkB.isDirected()
320        || !networkA.nodes().equals(networkB.nodes())
321        || !networkA.edges().equals(networkB.edges())) {
322      return false;
323    }
324
325    for (Object edge : networkA.edges()) {
326      if (!networkA.incidentNodes(edge).equals(networkB.incidentNodes(edge))) {
327        return false;
328      }
329    }
330
331    return true;
332  }
333
334  // Graph mutation methods
335
336  // Graph view methods
337
338  /**
339   * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
340   * properties remain intact, and further updates to {@code graph} will be reflected in the view.
341   */
342  public static <N> Graph<N> transpose(Graph<N> graph) {
343    if (!graph.isDirected()) {
344      return graph; // the transpose of an undirected graph is an identical graph
345    }
346
347    if (graph instanceof TransposedGraph) {
348      return ((TransposedGraph<N>) graph).graph;
349    }
350
351    return new TransposedGraph<N>(graph);
352  }
353
354  private static class TransposedGraph<N> extends AbstractGraph<N> {
355    private final Graph<N> graph;
356
357    TransposedGraph(Graph<N> graph) {
358      this.graph = graph;
359    }
360
361    @Override
362    public Set<N> nodes() {
363      return graph.nodes();
364    }
365
366    /**
367     * Defer to {@link AbstractGraph#edges()} (based on {@link #successors(Object)}) for full
368     * edges() implementation.
369     */
370    @Override
371    protected long edgeCount() {
372      return graph.edges().size();
373    }
374
375    @Override
376    public boolean isDirected() {
377      return graph.isDirected();
378    }
379
380    @Override
381    public boolean allowsSelfLoops() {
382      return graph.allowsSelfLoops();
383    }
384
385    @Override
386    public ElementOrder<N> nodeOrder() {
387      return graph.nodeOrder();
388    }
389
390    @Override
391    public Set<N> adjacentNodes(Object node) {
393    }
394
395    @Override
396    public Set<N> predecessors(Object node) {
397      return graph.successors(node); // transpose
398    }
399
400    @Override
401    public Set<N> successors(Object node) {
402      return graph.predecessors(node); // transpose
403    }
404  }
405
406  /**
407   * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
408   * properties remain intact, and further updates to {@code graph} will be reflected in the view.
409   */
410  public static <N, V> ValueGraph<N, V> transpose(ValueGraph<N, V> graph) {
411    if (!graph.isDirected()) {
412      return graph; // the transpose of an undirected graph is an identical graph
413    }
414
415    if (graph instanceof TransposedValueGraph) {
416      return ((TransposedValueGraph<N, V>) graph).graph;
417    }
418
419    return new TransposedValueGraph<N, V>(graph);
420  }
421
422  private static class TransposedValueGraph<N, V> extends AbstractValueGraph<N, V> {
423    private final ValueGraph<N, V> graph;
424
425    TransposedValueGraph(ValueGraph<N, V> graph) {
426      this.graph = graph;
427    }
428
429    @Override
430    public Set<N> nodes() {
431      return graph.nodes();
432    }
433
434    /**
435     * Defer to {@link AbstractGraph#edges()} (based on {@link #successors(Object)}) for full
436     * edges() implementation.
437     */
438    @Override
439    protected long edgeCount() {
440      return graph.edges().size();
441    }
442
443    @Override
444    public boolean isDirected() {
445      return graph.isDirected();
446    }
447
448    @Override
449    public boolean allowsSelfLoops() {
450      return graph.allowsSelfLoops();
451    }
452
453    @Override
454    public ElementOrder<N> nodeOrder() {
455      return graph.nodeOrder();
456    }
457
458    @Override
459    public Set<N> adjacentNodes(Object node) {
461    }
462
463    @Override
464    public Set<N> predecessors(Object node) {
465      return graph.successors(node); // transpose
466    }
467
468    @Override
469    public Set<N> successors(Object node) {
470      return graph.predecessors(node); // transpose
471    }
472
473    @Override
474    public V edgeValue(Object nodeU, Object nodeV) {
475      return graph.edgeValue(nodeV, nodeU); // transpose
476    }
477
478    @Override
479    public V edgeValueOrDefault(Object nodeU, Object nodeV, @Nullable V defaultValue) {
480      return graph.edgeValueOrDefault(nodeV, nodeU, defaultValue); // transpose
481    }
482  }
483
484  /**
485   * Returns a view of {@code network} with the direction (if any) of every edge reversed. All other
486   * properties remain intact, and further updates to {@code network} will be reflected in the view.
487   */
488  public static <N, E> Network<N, E> transpose(Network<N, E> network) {
489    if (!network.isDirected()) {
490      return network; // the transpose of an undirected network is an identical network
491    }
492
493    if (network instanceof TransposedNetwork) {
494      return ((TransposedNetwork<N, E>) network).network;
495    }
496
497    return new TransposedNetwork<N, E>(network);
498  }
499
500  private static class TransposedNetwork<N, E> extends AbstractNetwork<N, E> {
501    private final Network<N, E> network;
502
503    TransposedNetwork(Network<N, E> network) {
504      this.network = network;
505    }
506
507    @Override
508    public Set<N> nodes() {
509      return network.nodes();
510    }
511
512    @Override
513    public Set<E> edges() {
514      return network.edges();
515    }
516
517    @Override
518    public boolean isDirected() {
519      return network.isDirected();
520    }
521
522    @Override
523    public boolean allowsParallelEdges() {
524      return network.allowsParallelEdges();
525    }
526
527    @Override
528    public boolean allowsSelfLoops() {
529      return network.allowsSelfLoops();
530    }
531
532    @Override
533    public ElementOrder<N> nodeOrder() {
534      return network.nodeOrder();
535    }
536
537    @Override
538    public ElementOrder<E> edgeOrder() {
539      return network.edgeOrder();
540    }
541
542    @Override
543    public Set<N> adjacentNodes(Object node) {
545    }
546
547    @Override
548    public Set<N> predecessors(Object node) {
549      return network.successors(node); // transpose
550    }
551
552    @Override
553    public Set<N> successors(Object node) {
554      return network.predecessors(node); // transpose
555    }
556
557    @Override
558    public Set<E> incidentEdges(Object node) {
559      return network.incidentEdges(node);
560    }
561
562    @Override
563    public Set<E> inEdges(Object node) {
564      return network.outEdges(node); // transpose
565    }
566
567    @Override
568    public Set<E> outEdges(Object node) {
569      return network.inEdges(node); // transpose
570    }
571
572    @Override
573    public EndpointPair<N> incidentNodes(Object edge) {
574      EndpointPair<N> endpointPair = network.incidentNodes(edge);
575      return EndpointPair.of(network, endpointPair.nodeV(), endpointPair.nodeU()); // transpose
576    }
577
578    @Override
579    public Set<E> adjacentEdges(Object edge) {
581    }
582
583    @Override
584    public Set<E> edgesConnecting(Object nodeU, Object nodeV) {
585      return network.edgesConnecting(nodeV, nodeU); // transpose
586    }
587  }
588
589  // Graph copy methods
590
591  /**
592   * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph
593   * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges}
594   * from {@code graph} for which both nodes are contained by {@code nodes}.
595   *
596   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
597   */
598  public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes) {
599    MutableGraph<N> subgraph = GraphBuilder.from(graph).build();
600    for (N node : nodes) {
602    }
603    for (N node : subgraph.nodes()) {
604      for (N successorNode : graph.successors(node)) {
605        if (subgraph.nodes().contains(successorNode)) {
606          subgraph.putEdge(node, successorNode);
607        }
608      }
609    }
610    return subgraph;
611  }
612
613  /**
614   * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph
615   * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges}
616   * (and associated edge values) from {@code graph} for which both nodes are contained by {@code
617   * nodes}.
618   *
619   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
620   */
621  public static <N, V> MutableValueGraph<N, V> inducedSubgraph(
622      ValueGraph<N, V> graph, Iterable<? extends N> nodes) {
623    MutableValueGraph<N, V> subgraph = ValueGraphBuilder.from(graph).build();
624    for (N node : nodes) {
626    }
627    for (N node : subgraph.nodes()) {
628      for (N successorNode : graph.successors(node)) {
629        if (subgraph.nodes().contains(successorNode)) {
630          subgraph.putEdgeValue(node, successorNode, graph.edgeValue(node, successorNode));
631        }
632      }
633    }
634    return subgraph;
635  }
636
637  /**
638   * Returns the subgraph of {@code network} induced by {@code nodes}. This subgraph is a new graph
639   * that contains all of the nodes in {@code nodes}, and all of the {@link Network#edges() edges}
640   * from {@code network} for which the {@link Network#incidentNodes(Object) incident nodes} are
641   * both contained by {@code nodes}.
642   *
643   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
644   */
645  public static <N, E> MutableNetwork<N, E> inducedSubgraph(
646      Network<N, E> network, Iterable<? extends N> nodes) {
647    MutableNetwork<N, E> subgraph = NetworkBuilder.from(network).build();
648    for (N node : nodes) {
650    }
651    for (N node : subgraph.nodes()) {
652      for (E edge : network.outEdges(node)) {
654        if (subgraph.nodes().contains(successorNode)) {
656        }
657      }
658    }
659    return subgraph;
660  }
661
662  /** Creates a mutable copy of {@code graph} with the same nodes and edges. */
663  public static <N> MutableGraph<N> copyOf(Graph<N> graph) {
664    MutableGraph<N> copy = GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
665    for (N node : graph.nodes()) {
667    }
668    for (EndpointPair<N> edge : graph.edges()) {
669      copy.putEdge(edge.nodeU(), edge.nodeV());
670    }
671    return copy;
672  }
673
674  /** Creates a mutable copy of {@code graph} with the same nodes, edges, and edge values. */
675  public static <N, V> MutableValueGraph<N, V> copyOf(ValueGraph<N, V> graph) {
676    MutableValueGraph<N, V> copy =
677        ValueGraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
678    for (N node : graph.nodes()) {
680    }
681    for (EndpointPair<N> edge : graph.edges()) {
682      copy.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge.nodeU(), edge.nodeV()));
683    }
684    return copy;
685  }
686
687  /** Creates a mutable copy of {@code network} with the same nodes and edges. */
688  public static <N, E> MutableNetwork<N, E> copyOf(Network<N, E> network) {
689    MutableNetwork<N, E> copy =
690        NetworkBuilder.from(network)
691            .expectedNodeCount(network.nodes().size())
692            .expectedEdgeCount(network.edges().size())
693            .build();
694    for (N node : network.nodes()) {
696    }
697    for (E edge : network.edges()) {
698      EndpointPair<N> endpointPair = network.incidentNodes(edge);
700    }
701    return copy;
702  }
703
704  @CanIgnoreReturnValue
705  static int checkNonNegative(int value) {
706    checkArgument(value >= 0, "Not true that %s is non-negative.", value);
707    return value;
708  }
709
710  @CanIgnoreReturnValue
711  static int checkPositive(int value) {
712    checkArgument(value > 0, "Not true that %s is positive.", value);
713    return value;
714  }
715
716  @CanIgnoreReturnValue
717  static long checkNonNegative(long value) {
718    checkArgument(value >= 0, "Not true that %s is non-negative.", value);
719    return value;
720  }
721
722  @CanIgnoreReturnValue
723  static long checkPositive(long value) {
724    checkArgument(value > 0, "Not true that %s is positive.", value);
725    return value;
726  }
727
728  /**
729   * An enum representing the state of a node during DFS. {@code PENDING} means that the node is on
730   * the stack of the DFS, while {@code COMPLETE} means that the node and all its successors have
731   * been already explored. Any node that has not been explored will not have a state at all.
732   */
733  private enum NodeVisitState {
734    PENDING,
735    COMPLETE
736  }
737}

```