View Javadoc
1   /*
2    * Copyright (C) 2014 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.graph;
18  
19  import static com.google.common.base.Preconditions.checkArgument;
20  import static com.google.common.graph.GraphConstants.NODE_NOT_IN_GRAPH;
21  
22  import com.google.common.annotations.Beta;
23  import com.google.common.base.Objects;
24  import com.google.common.collect.Iterables;
25  import com.google.common.collect.Maps;
26  import com.google.errorprone.annotations.CanIgnoreReturnValue;
27  import java.util.ArrayDeque;
28  import java.util.Collection;
29  import java.util.Collections;
30  import java.util.HashSet;
31  import java.util.LinkedHashSet;
32  import java.util.Map;
33  import java.util.Optional;
34  import java.util.Queue;
35  import java.util.Set;
36  import javax.annotation.Nullable;
37  
38  /**
39   * Static utility methods for {@link Graph}, {@link ValueGraph}, and {@link Network} instances.
40   *
41   * @author James Sexton
42   * @author Joshua O'Madadhain
43   * @since 20.0
44   */
45  @Beta
46  public final class Graphs {
47  
48    private Graphs() {}
49  
50    // Graph query methods
51  
52    /**
53     * Returns true if {@code graph} has at least one cycle. A cycle is defined as a non-empty subset
54     * of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting
55     * and ending with the same node.
56     *
57     * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
58     */
59    public static <N> boolean hasCycle(Graph<N> graph) {
60      int numEdges = graph.edges().size();
61      if (numEdges == 0) {
62        return false; // An edge-free graph is acyclic by definition.
63      }
64      if (!graph.isDirected() && numEdges >= graph.nodes().size()) {
65        return true; // Optimization for the undirected case: at least one cycle must exist.
66      }
67  
68      Map<Object, NodeVisitState> visitedNodes =
69          Maps.newHashMapWithExpectedSize(graph.nodes().size());
70      for (N node : graph.nodes()) {
71        if (subgraphHasCycle(graph, visitedNodes, node, null)) {
72          return true;
73        }
74      }
75      return false;
76    }
77  
78    /**
79     * Returns true if {@code network} has at least one cycle. A cycle is defined as a non-empty
80     * subset of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges)
81     * starting and ending with the same node.
82     *
83     * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
84     */
85    public static boolean hasCycle(Network<?, ?> network) {
86      // In a directed graph, parallel edges cannot introduce a cycle in an acyclic graph.
87      // However, in an undirected graph, any parallel edge induces a cycle in the graph.
88      if (!network.isDirected()
89          && network.allowsParallelEdges()
90          && network.edges().size() > network.asGraph().edges().size()) {
91        return true;
92      }
93      return hasCycle(network.asGraph());
94    }
95  
96    /**
97     * Performs a traversal of the nodes reachable from {@code node}. If we ever reach a node we've
98     * already visited (following only outgoing edges and without reusing edges), we know there's a
99     * cycle in the graph.
100    */
101   private static <N> boolean subgraphHasCycle(
102       Graph<N> graph, Map<Object, NodeVisitState> visitedNodes, N node, @Nullable N previousNode) {
103     NodeVisitState state = visitedNodes.get(node);
104     if (state == NodeVisitState.COMPLETE) {
105       return false;
106     }
107     if (state == NodeVisitState.PENDING) {
108       return true;
109     }
110 
111     visitedNodes.put(node, NodeVisitState.PENDING);
112     for (N nextNode : graph.successors(node)) {
113       if (canTraverseWithoutReusingEdge(graph, nextNode, previousNode)
114           && subgraphHasCycle(graph, visitedNodes, nextNode, node)) {
115         return true;
116       }
117     }
118     visitedNodes.put(node, NodeVisitState.COMPLETE);
119     return false;
120   }
121 
122   /**
123    * Determines whether an edge has already been used during traversal. In the directed case a cycle
124    * is always detected before reusing an edge, so no special logic is required. In the undirected
125    * case, we must take care not to "backtrack" over an edge (i.e. going from A to B and then going
126    * from B to A).
127    */
128   private static boolean canTraverseWithoutReusingEdge(
129       Graph<?> graph, Object nextNode, @Nullable Object previousNode) {
130     if (graph.isDirected() || !Objects.equal(previousNode, nextNode)) {
131       return true;
132     }
133     // This falls into the undirected A->B->A case. The Graph interface does not support parallel
134     // edges, so this traversal would require reusing the undirected AB edge.
135     return false;
136   }
137 
138   /**
139    * Returns the transitive closure of {@code graph}. The transitive closure of a graph is another
140    * graph with an edge connecting node A to node B if node B is {@link #reachableNodes(Graph,
141    * Object) reachable} from node A.
142    *
143    * <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view
144    * of the transitive closure of {@code graph}. In other words, the returned {@link Graph} will not
145    * be updated after modifications to {@code graph}.
146    */
147   // TODO(b/31438252): Consider potential optimizations for this algorithm.
148   public static <N> Graph<N> transitiveClosure(Graph<N> graph) {
149     MutableGraph<N> transitiveClosure = GraphBuilder.from(graph).allowsSelfLoops(true).build();
150     // Every node is, at a minimum, reachable from itself. Since the resulting transitive closure
151     // will have no isolated nodes, we can skip adding nodes explicitly and let putEdge() do it.
152 
153     if (graph.isDirected()) {
154       // Note: works for both directed and undirected graphs, but we only use in the directed case.
155       for (N node : graph.nodes()) {
156         for (N reachableNode : reachableNodes(graph, node)) {
157           transitiveClosure.putEdge(node, reachableNode);
158         }
159       }
160     } else {
161       // An optimization for the undirected case: for every node B reachable from node A,
162       // node A and node B have the same reachability set.
163       Set<N> visitedNodes = new HashSet<N>();
164       for (N node : graph.nodes()) {
165         if (!visitedNodes.contains(node)) {
166           Set<N> reachableNodes = reachableNodes(graph, node);
167           visitedNodes.addAll(reachableNodes);
168           int pairwiseMatch = 1; // start at 1 to include self-loops
169           for (N nodeU : reachableNodes) {
170             for (N nodeV : Iterables.limit(reachableNodes, pairwiseMatch++)) {
171               transitiveClosure.putEdge(nodeU, nodeV);
172             }
173           }
174         }
175       }
176     }
177 
178     return transitiveClosure;
179   }
180 
181   /**
182    * Returns the set of nodes that are reachable from {@code node}. Node B is defined as reachable
183    * from node A if there exists a path (a sequence of adjacent outgoing edges) starting at node A
184    * and ending at node B. Note that a node is always reachable from itself via a zero-length path.
185    *
186    * <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view
187    * of the set of nodes reachable from {@code node}. In other words, the returned {@link Set} will
188    * not be updated after modifications to {@code graph}.
189    *
190    * @throws IllegalArgumentException if {@code node} is not present in {@code graph}
191    */
192   public static <N> Set<N> reachableNodes(Graph<N> graph, N node) {
193     checkArgument(graph.nodes().contains(node), NODE_NOT_IN_GRAPH, node);
194     Set<N> visitedNodes = new LinkedHashSet<N>();
195     Queue<N> queuedNodes = new ArrayDeque<N>();
196     visitedNodes.add(node);
197     queuedNodes.add(node);
198     // Perform a breadth-first traversal rooted at the input node.
199     while (!queuedNodes.isEmpty()) {
200       N currentNode = queuedNodes.remove();
201       for (N successor : graph.successors(currentNode)) {
202         if (visitedNodes.add(successor)) {
203           queuedNodes.add(successor);
204         }
205       }
206     }
207     return Collections.unmodifiableSet(visitedNodes);
208   }
209 
210   /**
211    * @deprecated Use {@link Graph#equals(Object)} instead. This method will be removed in late 2017.
212    */
213   // TODO(user): Delete this method.
214   @Deprecated
215   public static boolean equivalent(@Nullable Graph<?> graphA, @Nullable Graph<?> graphB) {
216     return Objects.equal(graphA, graphB);
217   }
218 
219   /**
220    * @deprecated Use {@link ValueGraph#equals(Object)} instead. This method will be removed in late
221    * 2017.
222    */
223   // TODO(user): Delete this method.
224   @Deprecated
225   public static boolean equivalent(
226       @Nullable ValueGraph<?, ?> graphA, @Nullable ValueGraph<?, ?> graphB) {
227     return Objects.equal(graphA, graphB);
228   }
229 
230   /**
231    * @deprecated Use {@link Network#equals(Object)} instead. This method will be removed in late
232    * 2017.
233    */
234   // TODO(user): Delete this method.
235   @Deprecated
236   public static boolean equivalent(
237       @Nullable Network<?, ?> networkA, @Nullable Network<?, ?> networkB) {
238     return Objects.equal(networkA, networkB);
239   }
240 
241   // Graph mutation methods
242 
243   // Graph view methods
244 
245   /**
246    * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
247    * properties remain intact, and further updates to {@code graph} will be reflected in the view.
248    */
249   public static <N> Graph<N> transpose(Graph<N> graph) {
250     if (!graph.isDirected()) {
251       return graph; // the transpose of an undirected graph is an identical graph
252     }
253 
254     if (graph instanceof TransposedGraph) {
255       return ((TransposedGraph<N>) graph).graph;
256     }
257 
258     return new TransposedGraph<N>(graph);
259   }
260 
261   // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of
262   // AbstractGraph) derives its behavior from calling successors().
263   private static class TransposedGraph<N> extends ForwardingGraph<N> {
264     private final Graph<N> graph;
265 
266     TransposedGraph(Graph<N> graph) {
267       this.graph = graph;
268     }
269 
270     @Override
271     protected Graph<N> delegate() {
272       return graph;
273     }
274 
275     @Override
276     public Set<N> predecessors(N node) {
277       return delegate().successors(node); // transpose
278     }
279 
280     @Override
281     public Set<N> successors(N node) {
282       return delegate().predecessors(node); // transpose
283     }
284 
285     @Override
286     public int inDegree(N node) {
287       return delegate().outDegree(node);  // transpose
288     }
289 
290     @Override
291     public int outDegree(N node) {
292       return delegate().inDegree(node);  // transpose
293     }
294 
295     @Override
296     public boolean hasEdgeConnecting(N nodeU, N nodeV) {
297       return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
298     }
299   }
300 
301   /**
302    * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
303    * properties remain intact, and further updates to {@code graph} will be reflected in the view.
304    */
305   public static <N, V> ValueGraph<N, V> transpose(ValueGraph<N, V> graph) {
306     if (!graph.isDirected()) {
307       return graph; // the transpose of an undirected graph is an identical graph
308     }
309 
310     if (graph instanceof TransposedValueGraph) {
311       return ((TransposedValueGraph<N, V>) graph).graph;
312     }
313 
314     return new TransposedValueGraph<>(graph);
315   }
316 
317   // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of
318   // AbstractValueGraph) derives its behavior from calling successors().
319   private static class TransposedValueGraph<N, V> extends ForwardingValueGraph<N, V> {
320     private final ValueGraph<N, V> graph;
321 
322     TransposedValueGraph(ValueGraph<N, V> graph) {
323       this.graph = graph;
324     }
325 
326     @Override
327     protected ValueGraph<N, V> delegate() {
328       return graph;
329     }
330 
331     @Override
332     public Set<N> predecessors(N node) {
333       return delegate().successors(node); // transpose
334     }
335 
336     @Override
337     public Set<N> successors(N node) {
338       return delegate().predecessors(node); // transpose
339     }
340 
341     @Override
342     public int inDegree(N node) {
343       return delegate().outDegree(node);  // transpose
344     }
345 
346     @Override
347     public int outDegree(N node) {
348       return delegate().inDegree(node);  // transpose
349     }
350 
351     @Override
352     public boolean hasEdgeConnecting(N nodeU, N nodeV) {
353       return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
354     }
355 
356     @Override
357     public Optional<V> edgeValue(N nodeU, N nodeV) {
358       return delegate().edgeValue(nodeV, nodeU); // transpose
359     }
360 
361     @Override
362     @Nullable
363     public V edgeValueOrDefault(N nodeU, N nodeV, @Nullable V defaultValue) {
364       return delegate().edgeValueOrDefault(nodeV, nodeU, defaultValue); // transpose
365     }
366   }
367 
368   /**
369    * Returns a view of {@code network} with the direction (if any) of every edge reversed. All other
370    * properties remain intact, and further updates to {@code network} will be reflected in the view.
371    */
372   public static <N, E> Network<N, E> transpose(Network<N, E> network) {
373     if (!network.isDirected()) {
374       return network; // the transpose of an undirected network is an identical network
375     }
376 
377     if (network instanceof TransposedNetwork) {
378       return ((TransposedNetwork<N, E>) network).network;
379     }
380 
381     return new TransposedNetwork<>(network);
382   }
383 
384   private static class TransposedNetwork<N, E> extends ForwardingNetwork<N, E> {
385     private final Network<N, E> network;
386 
387     TransposedNetwork(Network<N, E> network) {
388       this.network = network;
389     }
390 
391     @Override
392     protected Network<N, E> delegate() {
393       return network;
394     }
395 
396     @Override
397     public Set<N> predecessors(N node) {
398       return delegate().successors(node); // transpose
399     }
400 
401     @Override
402     public Set<N> successors(N node) {
403       return delegate().predecessors(node); // transpose
404     }
405 
406     @Override
407     public int inDegree(N node) {
408       return delegate().outDegree(node);  // transpose
409     }
410 
411     @Override
412     public int outDegree(N node) {
413       return delegate().inDegree(node);  // transpose
414     }
415 
416     @Override
417     public Set<E> inEdges(N node) {
418       return delegate().outEdges(node); // transpose
419     }
420 
421     @Override
422     public Set<E> outEdges(N node) {
423       return delegate().inEdges(node); // transpose
424     }
425 
426     @Override
427     public EndpointPair<N> incidentNodes(E edge) {
428       EndpointPair<N> endpointPair = delegate().incidentNodes(edge);
429       return EndpointPair.of(network, endpointPair.nodeV(), endpointPair.nodeU()); // transpose
430     }
431 
432     @Override
433     public Set<E> edgesConnecting(N nodeU, N nodeV) {
434       return delegate().edgesConnecting(nodeV, nodeU); // transpose
435     }
436 
437     @Override
438     public Optional<E> edgeConnecting(N nodeU, N nodeV) {
439       return delegate().edgeConnecting(nodeV, nodeU); // transpose
440     }
441 
442     @Override
443     public E edgeConnectingOrNull(N nodeU, N nodeV) {
444       return delegate().edgeConnectingOrNull(nodeV, nodeU); // transpose
445     }
446 
447     @Override
448     public boolean hasEdgeConnecting(N nodeU, N nodeV) {
449       return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
450     }
451   }
452 
453   // Graph copy methods
454 
455   /**
456    * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph
457    * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges}
458    * from {@code graph} for which both nodes are contained by {@code nodes}.
459    *
460    * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
461    */
462   public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes) {
463     MutableGraph<N> subgraph = (nodes instanceof Collection)
464         ? GraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build()
465         : GraphBuilder.from(graph).build();
466     for (N node : nodes) {
467       subgraph.addNode(node);
468     }
469     for (N node : subgraph.nodes()) {
470       for (N successorNode : graph.successors(node)) {
471         if (subgraph.nodes().contains(successorNode)) {
472           subgraph.putEdge(node, successorNode);
473         }
474       }
475     }
476     return subgraph;
477   }
478 
479   /**
480    * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph
481    * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges}
482    * (and associated edge values) from {@code graph} for which both nodes are contained by {@code
483    * nodes}.
484    *
485    * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
486    */
487   public static <N, V> MutableValueGraph<N, V> inducedSubgraph(
488       ValueGraph<N, V> graph, Iterable<? extends N> nodes) {
489     MutableValueGraph<N, V> subgraph = (nodes instanceof Collection)
490         ? ValueGraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build()
491         : ValueGraphBuilder.from(graph).build();
492     for (N node : nodes) {
493       subgraph.addNode(node);
494     }
495     for (N node : subgraph.nodes()) {
496       for (N successorNode : graph.successors(node)) {
497         if (subgraph.nodes().contains(successorNode)) {
498           subgraph.putEdgeValue(
499               node, successorNode, graph.edgeValueOrDefault(node, successorNode, null));
500         }
501       }
502     }
503     return subgraph;
504   }
505 
506   /**
507    * Returns the subgraph of {@code network} induced by {@code nodes}. This subgraph is a new graph
508    * that contains all of the nodes in {@code nodes}, and all of the {@link Network#edges() edges}
509    * from {@code network} for which the {@link Network#incidentNodes(Object) incident nodes} are
510    * both contained by {@code nodes}.
511    *
512    * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
513    */
514   public static <N, E> MutableNetwork<N, E> inducedSubgraph(
515       Network<N, E> network, Iterable<? extends N> nodes) {
516     MutableNetwork<N, E> subgraph = (nodes instanceof Collection)
517         ? NetworkBuilder.from(network).expectedNodeCount(((Collection) nodes).size()).build()
518         : NetworkBuilder.from(network).build();
519     for (N node : nodes) {
520       subgraph.addNode(node);
521     }
522     for (N node : subgraph.nodes()) {
523       for (E edge : network.outEdges(node)) {
524         N successorNode = network.incidentNodes(edge).adjacentNode(node);
525         if (subgraph.nodes().contains(successorNode)) {
526           subgraph.addEdge(node, successorNode, edge);
527         }
528       }
529     }
530     return subgraph;
531   }
532 
533   /** Creates a mutable copy of {@code graph} with the same nodes and edges. */
534   public static <N> MutableGraph<N> copyOf(Graph<N> graph) {
535     MutableGraph<N> copy = GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
536     for (N node : graph.nodes()) {
537       copy.addNode(node);
538     }
539     for (EndpointPair<N> edge : graph.edges()) {
540       copy.putEdge(edge.nodeU(), edge.nodeV());
541     }
542     return copy;
543   }
544 
545   /** Creates a mutable copy of {@code graph} with the same nodes, edges, and edge values. */
546   public static <N, V> MutableValueGraph<N, V> copyOf(ValueGraph<N, V> graph) {
547     MutableValueGraph<N, V> copy =
548         ValueGraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
549     for (N node : graph.nodes()) {
550       copy.addNode(node);
551     }
552     for (EndpointPair<N> edge : graph.edges()) {
553       copy.putEdgeValue(
554           edge.nodeU(), edge.nodeV(), graph.edgeValueOrDefault(edge.nodeU(), edge.nodeV(), null));
555     }
556     return copy;
557   }
558 
559   /** Creates a mutable copy of {@code network} with the same nodes and edges. */
560   public static <N, E> MutableNetwork<N, E> copyOf(Network<N, E> network) {
561     MutableNetwork<N, E> copy =
562         NetworkBuilder.from(network)
563             .expectedNodeCount(network.nodes().size())
564             .expectedEdgeCount(network.edges().size())
565             .build();
566     for (N node : network.nodes()) {
567       copy.addNode(node);
568     }
569     for (E edge : network.edges()) {
570       EndpointPair<N> endpointPair = network.incidentNodes(edge);
571       copy.addEdge(endpointPair.nodeU(), endpointPair.nodeV(), edge);
572     }
573     return copy;
574   }
575 
576   @CanIgnoreReturnValue
577   static int checkNonNegative(int value) {
578     checkArgument(value >= 0, "Not true that %s is non-negative.", value);
579     return value;
580   }
581 
582   @CanIgnoreReturnValue
583   static int checkPositive(int value) {
584     checkArgument(value > 0, "Not true that %s is positive.", value);
585     return value;
586   }
587 
588   @CanIgnoreReturnValue
589   static long checkNonNegative(long value) {
590     checkArgument(value >= 0, "Not true that %s is non-negative.", value);
591     return value;
592   }
593 
594   @CanIgnoreReturnValue
595   static long checkPositive(long value) {
596     checkArgument(value > 0, "Not true that %s is positive.", value);
597     return value;
598   }
599 
600   /**
601    * An enum representing the state of a node during DFS. {@code PENDING} means that the node is on
602    * the stack of the DFS, while {@code COMPLETE} means that the node and all its successors have
603    * been already explored. Any node that has not been explored will not have a state at all.
604    */
605   private enum NodeVisitState {
606     PENDING,
607     COMPLETE
608   }
609 }