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}