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