```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
028import java.util.ArrayDeque;
029import java.util.Collection;
030import java.util.Collections;
031import java.util.HashSet;
033import java.util.Map;
034import java.util.Optional;
035import java.util.Queue;
036import java.util.Set;
037import javax.annotation.Nullable;
038
039/**
041 *
042 * @author James Sexton
044 * @since 20.0
045 */
046@Beta
047public final class Graphs {
048
049  private Graphs() {}
050
051  // Graph query methods
052
053  /**
054   * Returns true if {@code graph} has at least one cycle. A cycle is defined as a non-empty subset
055   * of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting
056   * and ending with the same node.
057   *
058   * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
059   */
060  public static <N> boolean hasCycle(Graph<N> graph) {
061    int numEdges = graph.edges().size();
062    if (numEdges == 0) {
063      return false; // An edge-free graph is acyclic by definition.
064    }
065    if (!graph.isDirected() && numEdges >= graph.nodes().size()) {
066      return true; // Optimization for the undirected case: at least one cycle must exist.
067    }
068
069    Map<Object, NodeVisitState> visitedNodes =
070        Maps.newHashMapWithExpectedSize(graph.nodes().size());
071    for (N node : graph.nodes()) {
072      if (subgraphHasCycle(graph, visitedNodes, node, null)) {
073        return true;
074      }
075    }
076    return false;
077  }
078
079  /**
080   * Returns true if {@code network} has at least one cycle. A cycle is defined as a non-empty
081   * subset of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges)
082   * starting and ending with the same node.
083   *
084   * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
085   */
086  public static boolean hasCycle(Network<?, ?> network) {
087    // In a directed graph, parallel edges cannot introduce a cycle in an acyclic graph.
088    // However, in an undirected graph, any parallel edge induces a cycle in the graph.
089    if (!network.isDirected()
090        && network.allowsParallelEdges()
091        && network.edges().size() > network.asGraph().edges().size()) {
092      return true;
093    }
094    return hasCycle(network.asGraph());
095  }
096
097  /**
098   * Performs a traversal of the nodes reachable from {@code node}. If we ever reach a node we've
099   * already visited (following only outgoing edges and without reusing edges), we know there's a
100   * cycle in the graph.
101   */
102  private static <N> boolean subgraphHasCycle(
103      Graph<N> graph, Map<Object, NodeVisitState> visitedNodes, N node, @Nullable N 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 (N 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  public static <N> Set<N> reachableNodes(Graph<N> graph, N node) {
194    checkArgument(graph.nodes().contains(node), NODE_NOT_IN_GRAPH, node);
195    Set<N> visitedNodes = new LinkedHashSet<N>();
196    Queue<N> queuedNodes = new ArrayDeque<N>();
199    // Perform a breadth-first traversal rooted at the input node.
200    while (!queuedNodes.isEmpty()) {
201      N currentNode = queuedNodes.remove();
202      for (N successor : graph.successors(currentNode)) {
205        }
206      }
207    }
208    return Collections.unmodifiableSet(visitedNodes);
209  }
210
211  /**
212   * @deprecated Use {@link Graph#equals(Object)} instead. This method will be removed in late 2017.
213   */
214  // TODO(user): Delete this method.
215  @Deprecated
216  public static boolean equivalent(@Nullable Graph<?> graphA, @Nullable Graph<?> graphB) {
217    return Objects.equal(graphA, graphB);
218  }
219
220  /**
221   * @deprecated Use {@link ValueGraph#equals(Object)} instead. This method will be removed in late
222   * 2017.
223   */
224  // TODO(user): Delete this method.
225  @Deprecated
226  public static boolean equivalent(
227      @Nullable ValueGraph<?, ?> graphA, @Nullable ValueGraph<?, ?> graphB) {
228    return Objects.equal(graphA, graphB);
229  }
230
231  /**
232   * @deprecated Use {@link Network#equals(Object)} instead. This method will be removed in late
233   * 2017.
234   */
235  // TODO(user): Delete this method.
236  @Deprecated
237  public static boolean equivalent(
238      @Nullable Network<?, ?> networkA, @Nullable Network<?, ?> networkB) {
239    return Objects.equal(networkA, networkB);
240  }
241
242  // Graph mutation methods
243
244  // Graph view methods
245
246  /**
247   * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
248   * properties remain intact, and further updates to {@code graph} will be reflected in the view.
249   */
250  public static <N> Graph<N> transpose(Graph<N> graph) {
251    if (!graph.isDirected()) {
252      return graph; // the transpose of an undirected graph is an identical graph
253    }
254
255    if (graph instanceof TransposedGraph) {
256      return ((TransposedGraph<N>) graph).graph;
257    }
258
259    return new TransposedGraph<N>(graph);
260  }
261
262  // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of
263  // AbstractGraph) derives its behavior from calling successors().
264  private static class TransposedGraph<N> extends ForwardingGraph<N> {
265    private final Graph<N> graph;
266
267    TransposedGraph(Graph<N> graph) {
268      this.graph = graph;
269    }
270
271    @Override
272    protected Graph<N> delegate() {
273      return graph;
274    }
275
276    @Override
277    public Set<N> predecessors(N node) {
278      return delegate().successors(node); // transpose
279    }
280
281    @Override
282    public Set<N> successors(N node) {
283      return delegate().predecessors(node); // transpose
284    }
285
286    @Override
287    public int inDegree(N node) {
288      return delegate().outDegree(node);  // transpose
289    }
290
291    @Override
292    public int outDegree(N node) {
293      return delegate().inDegree(node);  // transpose
294    }
295
296    @Override
297    public boolean hasEdgeConnecting(N nodeU, N nodeV) {
298      return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
299    }
300  }
301
302  /**
303   * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
304   * properties remain intact, and further updates to {@code graph} will be reflected in the view.
305   */
306  public static <N, V> ValueGraph<N, V> transpose(ValueGraph<N, V> graph) {
307    if (!graph.isDirected()) {
308      return graph; // the transpose of an undirected graph is an identical graph
309    }
310
311    if (graph instanceof TransposedValueGraph) {
312      return ((TransposedValueGraph<N, V>) graph).graph;
313    }
314
315    return new TransposedValueGraph<N, V>(graph);
316  }
317
318  // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of
319  // AbstractValueGraph) derives its behavior from calling successors().
320  private static class TransposedValueGraph<N, V> extends ForwardingValueGraph<N, V> {
321    private final ValueGraph<N, V> graph;
322
323    TransposedValueGraph(ValueGraph<N, V> graph) {
324      this.graph = graph;
325    }
326
327    @Override
328    protected ValueGraph<N, V> delegate() {
329      return graph;
330    }
331
332    @Override
333    public Set<N> predecessors(N node) {
334      return delegate().successors(node); // transpose
335    }
336
337    @Override
338    public Set<N> successors(N node) {
339      return delegate().predecessors(node); // transpose
340    }
341
342    @Override
343    public int inDegree(N node) {
344      return delegate().outDegree(node);  // transpose
345    }
346
347    @Override
348    public int outDegree(N node) {
349      return delegate().inDegree(node);  // transpose
350    }
351
352    @Override
353    public boolean hasEdgeConnecting(N nodeU, N nodeV) {
354      return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
355    }
356
357    @Override
358    public Optional<V> edgeValue(N nodeU, N nodeV) {
359      return delegate().edgeValue(nodeV, nodeU); // transpose
360    }
361
362    @Override
363    @Nullable
364    public V edgeValueOrDefault(N nodeU, N nodeV, @Nullable V defaultValue) {
365      return delegate().edgeValueOrDefault(nodeV, nodeU, defaultValue); // transpose
366    }
367  }
368
369  /**
370   * Returns a view of {@code network} with the direction (if any) of every edge reversed. All other
371   * properties remain intact, and further updates to {@code network} will be reflected in the view.
372   */
373  @GwtIncompatible
374  public static <N, E> Network<N, E> transpose(Network<N, E> network) {
375    if (!network.isDirected()) {
376      return network; // the transpose of an undirected network is an identical network
377    }
378
379    if (network instanceof TransposedNetwork) {
380      return ((TransposedNetwork<N, E>) network).network;
381    }
382
383    return new TransposedNetwork<N, E>(network);
384  }
385
386  @GwtIncompatible
387  private static class TransposedNetwork<N, E> extends ForwardingNetwork<N, E> {
388    private final Network<N, E> network;
389
390    TransposedNetwork(Network<N, E> network) {
391      this.network = network;
392    }
393
394    @Override
395    protected Network<N, E> delegate() {
396      return network;
397    }
398
399    @Override
400    public Set<N> predecessors(N node) {
401      return delegate().successors(node); // transpose
402    }
403
404    @Override
405    public Set<N> successors(N node) {
406      return delegate().predecessors(node); // transpose
407    }
408
409    @Override
410    public int inDegree(N node) {
411      return delegate().outDegree(node);  // transpose
412    }
413
414    @Override
415    public int outDegree(N node) {
416      return delegate().inDegree(node);  // transpose
417    }
418
419    @Override
420    public Set<E> inEdges(N node) {
421      return delegate().outEdges(node); // transpose
422    }
423
424    @Override
425    public Set<E> outEdges(N node) {
426      return delegate().inEdges(node); // transpose
427    }
428
429    @Override
430    public EndpointPair<N> incidentNodes(E edge) {
431      EndpointPair<N> endpointPair = delegate().incidentNodes(edge);
432      return EndpointPair.of(network, endpointPair.nodeV(), endpointPair.nodeU()); // transpose
433    }
434
435    @Override
436    public Set<E> edgesConnecting(N nodeU, N nodeV) {
437      return delegate().edgesConnecting(nodeV, nodeU); // transpose
438    }
439
440    @Override
441    public Optional<E> edgeConnecting(N nodeU, N nodeV) {
442      return delegate().edgeConnecting(nodeV, nodeU); // transpose
443    }
444
445    @Override
446    public E edgeConnectingOrNull(N nodeU, N nodeV) {
447      return delegate().edgeConnectingOrNull(nodeV, nodeU); // transpose
448    }
449
450    @Override
451    public boolean hasEdgeConnecting(N nodeU, N nodeV) {
452      return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
453    }
454  }
455
456  // Graph copy methods
457
458  /**
459   * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph
460   * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges}
461   * from {@code graph} for which both nodes are contained by {@code nodes}.
462   *
463   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
464   */
465  public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes) {
466    MutableGraph<N> subgraph = (nodes instanceof Collection)
467        ? GraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build()
468        : GraphBuilder.from(graph).build();
469    for (N node : nodes) {
471    }
472    for (N node : subgraph.nodes()) {
473      for (N successorNode : graph.successors(node)) {
474        if (subgraph.nodes().contains(successorNode)) {
475          subgraph.putEdge(node, successorNode);
476        }
477      }
478    }
479    return subgraph;
480  }
481
482  /**
483   * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph
484   * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges}
485   * (and associated edge values) from {@code graph} for which both nodes are contained by {@code
486   * nodes}.
487   *
488   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
489   */
490  public static <N, V> MutableValueGraph<N, V> inducedSubgraph(
491      ValueGraph<N, V> graph, Iterable<? extends N> nodes) {
492    MutableValueGraph<N, V> subgraph = (nodes instanceof Collection)
493        ? ValueGraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build()
494        : ValueGraphBuilder.from(graph).build();
495    for (N node : nodes) {
497    }
498    for (N node : subgraph.nodes()) {
499      for (N successorNode : graph.successors(node)) {
500        if (subgraph.nodes().contains(successorNode)) {
501          subgraph.putEdgeValue(
502              node, successorNode, graph.edgeValueOrDefault(node, successorNode, null));
503        }
504      }
505    }
506    return subgraph;
507  }
508
509  /**
510   * Returns the subgraph of {@code network} induced by {@code nodes}. This subgraph is a new graph
511   * that contains all of the nodes in {@code nodes}, and all of the {@link Network#edges() edges}
512   * from {@code network} for which the {@link Network#incidentNodes(Object) incident nodes} are
513   * both contained by {@code nodes}.
514   *
515   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
516   */
517  @GwtIncompatible
518  public static <N, E> MutableNetwork<N, E> inducedSubgraph(
519      Network<N, E> network, Iterable<? extends N> nodes) {
520    MutableNetwork<N, E> subgraph = (nodes instanceof Collection)
521        ? NetworkBuilder.from(network).expectedNodeCount(((Collection) nodes).size()).build()
522        : NetworkBuilder.from(network).build();
523    for (N node : nodes) {
525    }
526    for (N node : subgraph.nodes()) {
527      for (E edge : network.outEdges(node)) {
529        if (subgraph.nodes().contains(successorNode)) {
531        }
532      }
533    }
534    return subgraph;
535  }
536
537  /** Creates a mutable copy of {@code graph} with the same nodes and edges. */
538  public static <N> MutableGraph<N> copyOf(Graph<N> graph) {
539    MutableGraph<N> copy = GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
540    for (N node : graph.nodes()) {
542    }
543    for (EndpointPair<N> edge : graph.edges()) {
544      copy.putEdge(edge.nodeU(), edge.nodeV());
545    }
546    return copy;
547  }
548
549  /** Creates a mutable copy of {@code graph} with the same nodes, edges, and edge values. */
550  public static <N, V> MutableValueGraph<N, V> copyOf(ValueGraph<N, V> graph) {
551    MutableValueGraph<N, V> copy =
552        ValueGraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
553    for (N node : graph.nodes()) {
555    }
556    for (EndpointPair<N> edge : graph.edges()) {
557      copy.putEdgeValue(
558          edge.nodeU(), edge.nodeV(), graph.edgeValueOrDefault(edge.nodeU(), edge.nodeV(), null));
559    }
560    return copy;
561  }
562
563  /** Creates a mutable copy of {@code network} with the same nodes and edges. */
564  @GwtIncompatible
565  public static <N, E> MutableNetwork<N, E> copyOf(Network<N, E> network) {
566    MutableNetwork<N, E> copy =
567        NetworkBuilder.from(network)
568            .expectedNodeCount(network.nodes().size())
569            .expectedEdgeCount(network.edges().size())
570            .build();
571    for (N node : network.nodes()) {
573    }
574    for (E edge : network.edges()) {
575      EndpointPair<N> endpointPair = network.incidentNodes(edge);
577    }
578    return copy;
579  }
580
581  @CanIgnoreReturnValue
582  static int checkNonNegative(int value) {
583    checkArgument(value >= 0, "Not true that %s is non-negative.", value);
584    return value;
585  }
586
587  @CanIgnoreReturnValue
588  static int checkPositive(int value) {
589    checkArgument(value > 0, "Not true that %s is positive.", value);
590    return value;
591  }
592
593  @CanIgnoreReturnValue
594  static long checkNonNegative(long value) {
595    checkArgument(value >= 0, "Not true that %s is non-negative.", value);
596    return value;
597  }
598
599  @CanIgnoreReturnValue
600  static long checkPositive(long value) {
601    checkArgument(value > 0, "Not true that %s is positive.", value);
602    return value;
603  }
604
605  /**
606   * An enum representing the state of a node during DFS. {@code PENDING} means that the node is on
607   * the stack of the DFS, while {@code COMPLETE} means that the node and all its successors have
608   * been already explored. Any node that has not been explored will not have a state at all.
609   */
610  private enum NodeVisitState {
611    PENDING,
612    COMPLETE
613  }
614}

```