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