001/* 002 * Copyright (C) 2014 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 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 017package com.google.common.graph; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.graph.GraphConstants.NODE_NOT_IN_GRAPH; 021import static java.util.Objects.requireNonNull; 022 023import com.google.common.annotations.Beta; 024import com.google.common.base.Function; 025import com.google.common.base.Objects; 026import com.google.common.collect.ImmutableSet; 027import com.google.common.collect.Iterables; 028import com.google.common.collect.Iterators; 029import com.google.common.collect.Maps; 030import com.google.errorprone.annotations.CanIgnoreReturnValue; 031import java.util.Collection; 032import java.util.HashSet; 033import java.util.Iterator; 034import java.util.Map; 035import java.util.Optional; 036import java.util.Set; 037import javax.annotation.CheckForNull; 038 039/** 040 * Static utility methods for {@link Graph}, {@link ValueGraph}, and {@link Network} instances. 041 * 042 * @author James Sexton 043 * @author Joshua O'Madadhain 044 * @since 20.0 045 */ 046@Beta 047@ElementTypesAreNonnullByDefault 048public final class Graphs { 049 050 private Graphs() {} 051 052 // Graph query methods 053 054 /** 055 * Returns true if {@code graph} has at least one cycle. A cycle is defined as a non-empty subset 056 * of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting 057 * and ending with the same node. 058 * 059 * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1). 060 */ 061 public static <N> boolean hasCycle(Graph<N> graph) { 062 int numEdges = graph.edges().size(); 063 if (numEdges == 0) { 064 return false; // An edge-free graph is acyclic by definition. 065 } 066 if (!graph.isDirected() && numEdges >= graph.nodes().size()) { 067 return true; // Optimization for the undirected case: at least one cycle must exist. 068 } 069 070 Map<Object, NodeVisitState> visitedNodes = 071 Maps.newHashMapWithExpectedSize(graph.nodes().size()); 072 for (N node : graph.nodes()) { 073 if (subgraphHasCycle(graph, visitedNodes, node, null)) { 074 return true; 075 } 076 } 077 return false; 078 } 079 080 /** 081 * Returns true if {@code network} has at least one cycle. A cycle is defined as a non-empty 082 * subset of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) 083 * starting and ending with the same node. 084 * 085 * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1). 086 */ 087 public static boolean hasCycle(Network<?, ?> network) { 088 // In a directed graph, parallel edges cannot introduce a cycle in an acyclic graph. 089 // However, in an undirected graph, any parallel edge induces a cycle in the graph. 090 if (!network.isDirected() 091 && network.allowsParallelEdges() 092 && network.edges().size() > network.asGraph().edges().size()) { 093 return true; 094 } 095 return hasCycle(network.asGraph()); 096 } 097 098 /** 099 * 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}