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.ImmutableSet; 025import com.google.common.collect.Iterables; 026import com.google.common.collect.Maps; 027import com.google.errorprone.annotations.CanIgnoreReturnValue; 028import java.util.Collection; 029import java.util.HashSet; 030import java.util.Map; 031import java.util.Optional; 032import java.util.Set; 033import org.checkerframework.checker.nullness.qual.Nullable; 034 035/** 036 * Static utility methods for {@link Graph}, {@link ValueGraph}, and {@link Network} instances. 037 * 038 * @author James Sexton 039 * @author Joshua O'Madadhain 040 * @since 20.0 041 */ 042@Beta 043public final class Graphs { 044 045 private Graphs() {} 046 047 // Graph query methods 048 049 /** 050 * Returns true if {@code graph} has at least one cycle. A cycle is defined as a non-empty subset 051 * of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting 052 * and ending with the same node. 053 * 054 * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1). 055 */ 056 public static <N> boolean hasCycle(Graph<N> graph) { 057 int numEdges = graph.edges().size(); 058 if (numEdges == 0) { 059 return false; // An edge-free graph is acyclic by definition. 060 } 061 if (!graph.isDirected() && numEdges >= graph.nodes().size()) { 062 return true; // Optimization for the undirected case: at least one cycle must exist. 063 } 064 065 Map<Object, NodeVisitState> visitedNodes = 066 Maps.newHashMapWithExpectedSize(graph.nodes().size()); 067 for (N node : graph.nodes()) { 068 if (subgraphHasCycle(graph, visitedNodes, node, null)) { 069 return true; 070 } 071 } 072 return false; 073 } 074 075 /** 076 * Returns true if {@code network} has at least one cycle. A cycle is defined as a non-empty 077 * subset of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) 078 * starting and ending with the same node. 079 * 080 * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1). 081 */ 082 public static boolean hasCycle(Network<?, ?> network) { 083 // In a directed graph, parallel edges cannot introduce a cycle in an acyclic graph. 084 // However, in an undirected graph, any parallel edge induces a cycle in the graph. 085 if (!network.isDirected() 086 && network.allowsParallelEdges() 087 && network.edges().size() > network.asGraph().edges().size()) { 088 return true; 089 } 090 return hasCycle(network.asGraph()); 091 } 092 093 /** 094 * Performs a traversal of the nodes reachable from {@code node}. If we ever reach a node we've 095 * already visited (following only outgoing edges and without reusing edges), we know there's a 096 * cycle in the graph. 097 */ 098 private static <N> boolean subgraphHasCycle( 099 Graph<N> graph, Map<Object, NodeVisitState> visitedNodes, N node, @Nullable N previousNode) { 100 NodeVisitState state = visitedNodes.get(node); 101 if (state == NodeVisitState.COMPLETE) { 102 return false; 103 } 104 if (state == NodeVisitState.PENDING) { 105 return true; 106 } 107 108 visitedNodes.put(node, NodeVisitState.PENDING); 109 for (N nextNode : graph.successors(node)) { 110 if (canTraverseWithoutReusingEdge(graph, nextNode, previousNode) 111 && subgraphHasCycle(graph, visitedNodes, nextNode, node)) { 112 return true; 113 } 114 } 115 visitedNodes.put(node, NodeVisitState.COMPLETE); 116 return false; 117 } 118 119 /** 120 * Determines whether an edge has already been used during traversal. In the directed case a cycle 121 * is always detected before reusing an edge, so no special logic is required. In the undirected 122 * case, we must take care not to "backtrack" over an edge (i.e. going from A to B and then going 123 * from B to A). 124 */ 125 private static boolean canTraverseWithoutReusingEdge( 126 Graph<?> graph, Object nextNode, @Nullable Object previousNode) { 127 if (graph.isDirected() || !Objects.equal(previousNode, nextNode)) { 128 return true; 129 } 130 // This falls into the undirected A->B->A case. The Graph interface does not support parallel 131 // edges, so this traversal would require reusing the undirected AB edge. 132 return false; 133 } 134 135 /** 136 * Returns the transitive closure of {@code graph}. The transitive closure of a graph is another 137 * graph with an edge connecting node A to node B if node B is {@link #reachableNodes(Graph, 138 * Object) reachable} from node A. 139 * 140 * <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view 141 * of the transitive closure of {@code graph}. In other words, the returned {@link Graph} will not 142 * be updated after modifications to {@code graph}. 143 */ 144 // TODO(b/31438252): Consider potential optimizations for this algorithm. 145 public static <N> Graph<N> transitiveClosure(Graph<N> graph) { 146 MutableGraph<N> transitiveClosure = GraphBuilder.from(graph).allowsSelfLoops(true).build(); 147 // Every node is, at a minimum, reachable from itself. Since the resulting transitive closure 148 // will have no isolated nodes, we can skip adding nodes explicitly and let putEdge() do it. 149 150 if (graph.isDirected()) { 151 // Note: works for both directed and undirected graphs, but we only use in the directed case. 152 for (N node : graph.nodes()) { 153 for (N reachableNode : reachableNodes(graph, node)) { 154 transitiveClosure.putEdge(node, reachableNode); 155 } 156 } 157 } else { 158 // An optimization for the undirected case: for every node B reachable from node A, 159 // node A and node B have the same reachability set. 160 Set<N> visitedNodes = new HashSet<N>(); 161 for (N node : graph.nodes()) { 162 if (!visitedNodes.contains(node)) { 163 Set<N> reachableNodes = reachableNodes(graph, node); 164 visitedNodes.addAll(reachableNodes); 165 int pairwiseMatch = 1; // start at 1 to include self-loops 166 for (N nodeU : reachableNodes) { 167 for (N nodeV : Iterables.limit(reachableNodes, pairwiseMatch++)) { 168 transitiveClosure.putEdge(nodeU, nodeV); 169 } 170 } 171 } 172 } 173 } 174 175 return transitiveClosure; 176 } 177 178 /** 179 * Returns the set of nodes that are reachable from {@code node}. Node B is defined as reachable 180 * from node A if there exists a path (a sequence of adjacent outgoing edges) starting at node A 181 * and ending at node B. Note that a node is always reachable from itself via a zero-length path. 182 * 183 * <p>This is a "snapshot" based on the current topology of {@code graph}, rather than a live view 184 * of the set of nodes reachable from {@code node}. In other words, the returned {@link Set} will 185 * not be updated after modifications to {@code graph}. 186 * 187 * @throws IllegalArgumentException if {@code node} is not present in {@code graph} 188 */ 189 public static <N> Set<N> reachableNodes(Graph<N> graph, N node) { 190 checkArgument(graph.nodes().contains(node), NODE_NOT_IN_GRAPH, node); 191 return ImmutableSet.copyOf(Traverser.forGraph(graph).breadthFirst(node)); 192 } 193 194 // Graph mutation methods 195 196 // Graph view methods 197 198 /** 199 * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other 200 * properties remain intact, and further updates to {@code graph} will be reflected in the view. 201 */ 202 public static <N> Graph<N> transpose(Graph<N> graph) { 203 if (!graph.isDirected()) { 204 return graph; // the transpose of an undirected graph is an identical graph 205 } 206 207 if (graph instanceof TransposedGraph) { 208 return ((TransposedGraph<N>) graph).graph; 209 } 210 211 return new TransposedGraph<N>(graph); 212 } 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, V> ValueGraph<N, V> transpose(ValueGraph<N, V> graph) { 219 if (!graph.isDirected()) { 220 return graph; // the transpose of an undirected graph is an identical graph 221 } 222 223 if (graph instanceof TransposedValueGraph) { 224 return ((TransposedValueGraph<N, V>) graph).graph; 225 } 226 227 return new TransposedValueGraph<>(graph); 228 } 229 230 /** 231 * Returns a view of {@code network} with the direction (if any) of every edge reversed. All other 232 * properties remain intact, and further updates to {@code network} will be reflected in the view. 233 */ 234 public static <N, E> Network<N, E> transpose(Network<N, E> network) { 235 if (!network.isDirected()) { 236 return network; // the transpose of an undirected network is an identical network 237 } 238 239 if (network instanceof TransposedNetwork) { 240 return ((TransposedNetwork<N, E>) network).network; 241 } 242 243 return new TransposedNetwork<>(network); 244 } 245 246 static <N> EndpointPair<N> transpose(EndpointPair<N> endpoints) { 247 if (endpoints.isOrdered()) { 248 return EndpointPair.ordered(endpoints.target(), endpoints.source()); 249 } 250 return endpoints; 251 } 252 253 // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of 254 // AbstractGraph) derives its behavior from calling successors(). 255 private static class TransposedGraph<N> extends ForwardingGraph<N> { 256 private final Graph<N> graph; 257 258 TransposedGraph(Graph<N> graph) { 259 this.graph = graph; 260 } 261 262 @Override 263 protected Graph<N> delegate() { 264 return graph; 265 } 266 267 @Override 268 public Set<N> predecessors(N node) { 269 return delegate().successors(node); // transpose 270 } 271 272 @Override 273 public Set<N> successors(N node) { 274 return delegate().predecessors(node); // transpose 275 } 276 277 @Override 278 public int inDegree(N node) { 279 return delegate().outDegree(node); // transpose 280 } 281 282 @Override 283 public int outDegree(N node) { 284 return delegate().inDegree(node); // transpose 285 } 286 287 @Override 288 public boolean hasEdgeConnecting(N nodeU, N nodeV) { 289 return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose 290 } 291 292 @Override 293 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { 294 return delegate().hasEdgeConnecting(transpose(endpoints)); 295 } 296 } 297 298 // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of 299 // AbstractValueGraph) derives its behavior from calling successors(). 300 private static class TransposedValueGraph<N, V> extends ForwardingValueGraph<N, V> { 301 private final ValueGraph<N, V> graph; 302 303 TransposedValueGraph(ValueGraph<N, V> graph) { 304 this.graph = graph; 305 } 306 307 @Override 308 protected ValueGraph<N, V> delegate() { 309 return graph; 310 } 311 312 @Override 313 public Set<N> predecessors(N node) { 314 return delegate().successors(node); // transpose 315 } 316 317 @Override 318 public Set<N> successors(N node) { 319 return delegate().predecessors(node); // transpose 320 } 321 322 @Override 323 public int inDegree(N node) { 324 return delegate().outDegree(node); // transpose 325 } 326 327 @Override 328 public int outDegree(N node) { 329 return delegate().inDegree(node); // transpose 330 } 331 332 @Override 333 public boolean hasEdgeConnecting(N nodeU, N nodeV) { 334 return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose 335 } 336 337 @Override 338 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { 339 return delegate().hasEdgeConnecting(transpose(endpoints)); 340 } 341 342 @Override 343 public Optional<V> edgeValue(N nodeU, N nodeV) { 344 return delegate().edgeValue(nodeV, nodeU); // transpose 345 } 346 347 @Override 348 public Optional<V> edgeValue(EndpointPair<N> endpoints) { 349 return delegate().edgeValue(transpose(endpoints)); 350 } 351 352 @Override 353 public @Nullable V edgeValueOrDefault(N nodeU, N nodeV, @Nullable V defaultValue) { 354 return delegate().edgeValueOrDefault(nodeV, nodeU, defaultValue); // transpose 355 } 356 357 @Override 358 public @Nullable V edgeValueOrDefault(EndpointPair<N> endpoints, @Nullable V defaultValue) { 359 return delegate().edgeValueOrDefault(transpose(endpoints), defaultValue); 360 } 361 } 362 363 private static class TransposedNetwork<N, E> extends ForwardingNetwork<N, E> { 364 private final Network<N, E> network; 365 366 TransposedNetwork(Network<N, E> network) { 367 this.network = network; 368 } 369 370 @Override 371 protected Network<N, E> delegate() { 372 return network; 373 } 374 375 @Override 376 public Set<N> predecessors(N node) { 377 return delegate().successors(node); // transpose 378 } 379 380 @Override 381 public Set<N> successors(N node) { 382 return delegate().predecessors(node); // transpose 383 } 384 385 @Override 386 public int inDegree(N node) { 387 return delegate().outDegree(node); // transpose 388 } 389 390 @Override 391 public int outDegree(N node) { 392 return delegate().inDegree(node); // transpose 393 } 394 395 @Override 396 public Set<E> inEdges(N node) { 397 return delegate().outEdges(node); // transpose 398 } 399 400 @Override 401 public Set<E> outEdges(N node) { 402 return delegate().inEdges(node); // transpose 403 } 404 405 @Override 406 public EndpointPair<N> incidentNodes(E edge) { 407 EndpointPair<N> endpointPair = delegate().incidentNodes(edge); 408 return EndpointPair.of(network, endpointPair.nodeV(), endpointPair.nodeU()); // transpose 409 } 410 411 @Override 412 public Set<E> edgesConnecting(N nodeU, N nodeV) { 413 return delegate().edgesConnecting(nodeV, nodeU); // transpose 414 } 415 416 @Override 417 public Set<E> edgesConnecting(EndpointPair<N> endpoints) { 418 return delegate().edgesConnecting(transpose(endpoints)); 419 } 420 421 @Override 422 public Optional<E> edgeConnecting(N nodeU, N nodeV) { 423 return delegate().edgeConnecting(nodeV, nodeU); // transpose 424 } 425 426 @Override 427 public Optional<E> edgeConnecting(EndpointPair<N> endpoints) { 428 return delegate().edgeConnecting(transpose(endpoints)); 429 } 430 431 @Override 432 public E edgeConnectingOrNull(N nodeU, N nodeV) { 433 return delegate().edgeConnectingOrNull(nodeV, nodeU); // transpose 434 } 435 436 @Override 437 public E edgeConnectingOrNull(EndpointPair<N> endpoints) { 438 return delegate().edgeConnectingOrNull(transpose(endpoints)); 439 } 440 441 @Override 442 public boolean hasEdgeConnecting(N nodeU, N nodeV) { 443 return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose 444 } 445 446 @Override 447 public boolean hasEdgeConnecting(EndpointPair<N> endpoints) { 448 return delegate().hasEdgeConnecting(transpose(endpoints)); 449 } 450 } 451 452 // Graph copy methods 453 454 /** 455 * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph 456 * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges} 457 * from {@code graph} for which both nodes are contained by {@code nodes}. 458 * 459 * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph 460 */ 461 public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes) { 462 MutableGraph<N> subgraph = 463 (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 = 490 (nodes instanceof Collection) 491 ? ValueGraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build() 492 : ValueGraphBuilder.from(graph).build(); 493 for (N node : nodes) { 494 subgraph.addNode(node); 495 } 496 for (N node : subgraph.nodes()) { 497 for (N successorNode : graph.successors(node)) { 498 if (subgraph.nodes().contains(successorNode)) { 499 subgraph.putEdgeValue( 500 node, successorNode, graph.edgeValueOrDefault(node, successorNode, null)); 501 } 502 } 503 } 504 return subgraph; 505 } 506 507 /** 508 * Returns the subgraph of {@code network} induced by {@code nodes}. This subgraph is a new graph 509 * that contains all of the nodes in {@code nodes}, and all of the {@link Network#edges() edges} 510 * from {@code network} for which the {@link Network#incidentNodes(Object) incident nodes} are 511 * both contained by {@code nodes}. 512 * 513 * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph 514 */ 515 public static <N, E> MutableNetwork<N, E> inducedSubgraph( 516 Network<N, E> network, Iterable<? extends N> nodes) { 517 MutableNetwork<N, E> subgraph = 518 (nodes instanceof Collection) 519 ? NetworkBuilder.from(network).expectedNodeCount(((Collection) nodes).size()).build() 520 : NetworkBuilder.from(network).build(); 521 for (N node : nodes) { 522 subgraph.addNode(node); 523 } 524 for (N node : subgraph.nodes()) { 525 for (E edge : network.outEdges(node)) { 526 N successorNode = network.incidentNodes(edge).adjacentNode(node); 527 if (subgraph.nodes().contains(successorNode)) { 528 subgraph.addEdge(node, successorNode, edge); 529 } 530 } 531 } 532 return subgraph; 533 } 534 535 /** Creates a mutable copy of {@code graph} with the same nodes and edges. */ 536 public static <N> MutableGraph<N> copyOf(Graph<N> graph) { 537 MutableGraph<N> copy = GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build(); 538 for (N node : graph.nodes()) { 539 copy.addNode(node); 540 } 541 for (EndpointPair<N> edge : graph.edges()) { 542 copy.putEdge(edge.nodeU(), edge.nodeV()); 543 } 544 return copy; 545 } 546 547 /** Creates a mutable copy of {@code graph} with the same nodes, edges, and edge values. */ 548 public static <N, V> MutableValueGraph<N, V> copyOf(ValueGraph<N, V> graph) { 549 MutableValueGraph<N, V> copy = 550 ValueGraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build(); 551 for (N node : graph.nodes()) { 552 copy.addNode(node); 553 } 554 for (EndpointPair<N> edge : graph.edges()) { 555 copy.putEdgeValue( 556 edge.nodeU(), edge.nodeV(), graph.edgeValueOrDefault(edge.nodeU(), edge.nodeV(), null)); 557 } 558 return copy; 559 } 560 561 /** Creates a mutable copy of {@code network} with the same nodes and edges. */ 562 public static <N, E> MutableNetwork<N, E> copyOf(Network<N, E> network) { 563 MutableNetwork<N, E> copy = 564 NetworkBuilder.from(network) 565 .expectedNodeCount(network.nodes().size()) 566 .expectedEdgeCount(network.edges().size()) 567 .build(); 568 for (N node : network.nodes()) { 569 copy.addNode(node); 570 } 571 for (E edge : network.edges()) { 572 EndpointPair<N> endpointPair = network.incidentNodes(edge); 573 copy.addEdge(endpointPair.nodeU(), endpointPair.nodeV(), edge); 574 } 575 return copy; 576 } 577 578 @CanIgnoreReturnValue 579 static int checkNonNegative(int value) { 580 checkArgument(value >= 0, "Not true that %s is non-negative.", value); 581 return value; 582 } 583 584 @CanIgnoreReturnValue 585 static long checkNonNegative(long value) { 586 checkArgument(value >= 0, "Not true that %s is non-negative.", value); 587 return value; 588 } 589 590 @CanIgnoreReturnValue 591 static int checkPositive(int value) { 592 checkArgument(value > 0, "Not true that %s is positive.", value); 593 return value; 594 } 595 596 @CanIgnoreReturnValue 597 static long checkPositive(long value) { 598 checkArgument(value > 0, "Not true that %s is positive.", value); 599 return value; 600 } 601 602 /** 603 * An enum representing the state of a node during DFS. {@code PENDING} means that the node is on 604 * the stack of the DFS, while {@code COMPLETE} means that the node and all its successors have 605 * been already explored. Any node that has not been explored will not have a state at all. 606 */ 607 private enum NodeVisitState { 608 PENDING, 609 COMPLETE 610 } 611}