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