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