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.Function;
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.Optional;
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    return ImmutableSet.copyOf(Traverser.forGraph(graph).breadthFirst(node));
195  }
196
197  // Graph mutation methods
198
199  // Graph view methods
200
201  /**
202   * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
203   * properties remain intact, and further updates to {@code graph} will be reflected in the view.
204   */
205  public static <N> Graph<N> transpose(Graph<N> graph) {
206    if (!graph.isDirected()) {
207      return graph; // the transpose of an undirected graph is an identical graph
208    }
209
210    if (graph instanceof TransposedGraph) {
211      return ((TransposedGraph<N>) graph).graph;
212    }
213
214    return new TransposedGraph<N>(graph);
215  }
216
217  /**
218   * Returns a view of {@code graph} with the direction (if any) of every edge reversed. All other
219   * properties remain intact, and further updates to {@code graph} will be reflected in the view.
220   */
221  public static <N, V> ValueGraph<N, V> transpose(ValueGraph<N, V> graph) {
222    if (!graph.isDirected()) {
223      return graph; // the transpose of an undirected graph is an identical graph
224    }
225
226    if (graph instanceof TransposedValueGraph) {
227      return ((TransposedValueGraph<N, V>) graph).graph;
228    }
229
230    return new TransposedValueGraph<>(graph);
231  }
232
233  /**
234   * Returns a view of {@code network} with the direction (if any) of every edge reversed. All other
235   * properties remain intact, and further updates to {@code network} will be reflected in the view.
236   */
237  public static <N, E> Network<N, E> transpose(Network<N, E> network) {
238    if (!network.isDirected()) {
239      return network; // the transpose of an undirected network is an identical network
240    }
241
242    if (network instanceof TransposedNetwork) {
243      return ((TransposedNetwork<N, E>) network).network;
244    }
245
246    return new TransposedNetwork<>(network);
247  }
248
249  static <N> EndpointPair<N> transpose(EndpointPair<N> endpoints) {
250    if (endpoints.isOrdered()) {
251      return EndpointPair.ordered(endpoints.target(), endpoints.source());
252    }
253    return endpoints;
254  }
255
256  // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of
257  // AbstractGraph) derives its behavior from calling successors().
258  private static class TransposedGraph<N> extends ForwardingGraph<N> {
259    private final Graph<N> graph;
260
261    TransposedGraph(Graph<N> graph) {
262      this.graph = graph;
263    }
264
265    @Override
266    protected Graph<N> delegate() {
267      return graph;
268    }
269
270    @Override
271    public Set<N> predecessors(N node) {
272      return delegate().successors(node); // transpose
273    }
274
275    @Override
276    public Set<N> successors(N node) {
277      return delegate().predecessors(node); // transpose
278    }
279
280    @Override
281    public Set<EndpointPair<N>> incidentEdges(N node) {
282      return new IncidentEdgeSet<N>(this, node) {
283        @Override
284        public Iterator<EndpointPair<N>> iterator() {
285          return Iterators.transform(
286              delegate().incidentEdges(node).iterator(),
287              new Function<EndpointPair<N>, EndpointPair<N>>() {
288                @Override
289                public EndpointPair<N> apply(EndpointPair<N> edge) {
290                  return EndpointPair.of(delegate(), edge.nodeV(), edge.nodeU());
291                }
292              });
293        }
294      };
295    }
296
297    @Override
298    public int inDegree(N node) {
299      return delegate().outDegree(node); // transpose
300    }
301
302    @Override
303    public int outDegree(N node) {
304      return delegate().inDegree(node); // transpose
305    }
306
307    @Override
308    public boolean hasEdgeConnecting(N nodeU, N nodeV) {
309      return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
310    }
311
312    @Override
313    public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
314      return delegate().hasEdgeConnecting(transpose(endpoints));
315    }
316  }
317
318  // NOTE: this should work as long as the delegate graph's implementation of edges() (like that of
319  // AbstractValueGraph) derives its behavior from calling successors().
320  private static class TransposedValueGraph<N, V> extends ForwardingValueGraph<N, V> {
321    private final ValueGraph<N, V> graph;
322
323    TransposedValueGraph(ValueGraph<N, V> graph) {
324      this.graph = graph;
325    }
326
327    @Override
328    protected ValueGraph<N, V> delegate() {
329      return graph;
330    }
331
332    @Override
333    public Set<N> predecessors(N node) {
334      return delegate().successors(node); // transpose
335    }
336
337    @Override
338    public Set<N> successors(N node) {
339      return delegate().predecessors(node); // transpose
340    }
341
342    @Override
343    public int inDegree(N node) {
344      return delegate().outDegree(node); // transpose
345    }
346
347    @Override
348    public int outDegree(N node) {
349      return delegate().inDegree(node); // transpose
350    }
351
352    @Override
353    public boolean hasEdgeConnecting(N nodeU, N nodeV) {
354      return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
355    }
356
357    @Override
358    public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
359      return delegate().hasEdgeConnecting(transpose(endpoints));
360    }
361
362    @Override
363    public Optional<V> edgeValue(N nodeU, N nodeV) {
364      return delegate().edgeValue(nodeV, nodeU); // transpose
365    }
366
367    @Override
368    public Optional<V> edgeValue(EndpointPair<N> endpoints) {
369      return delegate().edgeValue(transpose(endpoints));
370    }
371
372    @Override
373    public @Nullable V edgeValueOrDefault(N nodeU, N nodeV, @Nullable V defaultValue) {
374      return delegate().edgeValueOrDefault(nodeV, nodeU, defaultValue); // transpose
375    }
376
377    @Override
378    public @Nullable V edgeValueOrDefault(EndpointPair<N> endpoints, @Nullable V defaultValue) {
379      return delegate().edgeValueOrDefault(transpose(endpoints), defaultValue);
380    }
381  }
382
383  private static class TransposedNetwork<N, E> extends ForwardingNetwork<N, E> {
384    private final Network<N, E> network;
385
386    TransposedNetwork(Network<N, E> network) {
387      this.network = network;
388    }
389
390    @Override
391    protected Network<N, E> delegate() {
392      return network;
393    }
394
395    @Override
396    public Set<N> predecessors(N node) {
397      return delegate().successors(node); // transpose
398    }
399
400    @Override
401    public Set<N> successors(N node) {
402      return delegate().predecessors(node); // transpose
403    }
404
405    @Override
406    public int inDegree(N node) {
407      return delegate().outDegree(node); // transpose
408    }
409
410    @Override
411    public int outDegree(N node) {
412      return delegate().inDegree(node); // transpose
413    }
414
415    @Override
416    public Set<E> inEdges(N node) {
417      return delegate().outEdges(node); // transpose
418    }
419
420    @Override
421    public Set<E> outEdges(N node) {
422      return delegate().inEdges(node); // transpose
423    }
424
425    @Override
426    public EndpointPair<N> incidentNodes(E edge) {
427      EndpointPair<N> endpointPair = delegate().incidentNodes(edge);
428      return EndpointPair.of(network, endpointPair.nodeV(), endpointPair.nodeU()); // transpose
429    }
430
431    @Override
432    public Set<E> edgesConnecting(N nodeU, N nodeV) {
433      return delegate().edgesConnecting(nodeV, nodeU); // transpose
434    }
435
436    @Override
437    public Set<E> edgesConnecting(EndpointPair<N> endpoints) {
438      return delegate().edgesConnecting(transpose(endpoints));
439    }
440
441    @Override
442    public Optional<E> edgeConnecting(N nodeU, N nodeV) {
443      return delegate().edgeConnecting(nodeV, nodeU); // transpose
444    }
445
446    @Override
447    public Optional<E> edgeConnecting(EndpointPair<N> endpoints) {
448      return delegate().edgeConnecting(transpose(endpoints));
449    }
450
451    @Override
452    public E edgeConnectingOrNull(N nodeU, N nodeV) {
453      return delegate().edgeConnectingOrNull(nodeV, nodeU); // transpose
454    }
455
456    @Override
457    public E edgeConnectingOrNull(EndpointPair<N> endpoints) {
458      return delegate().edgeConnectingOrNull(transpose(endpoints));
459    }
460
461    @Override
462    public boolean hasEdgeConnecting(N nodeU, N nodeV) {
463      return delegate().hasEdgeConnecting(nodeV, nodeU); // transpose
464    }
465
466    @Override
467    public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
468      return delegate().hasEdgeConnecting(transpose(endpoints));
469    }
470  }
471
472  // Graph copy methods
473
474  /**
475   * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph
476   * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges}
477   * from {@code graph} for which both nodes are contained by {@code nodes}.
478   *
479   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
480   */
481  public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes) {
482    MutableGraph<N> subgraph =
483        (nodes instanceof Collection)
484            ? GraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build()
485            : GraphBuilder.from(graph).build();
486    for (N node : nodes) {
487      subgraph.addNode(node);
488    }
489    for (N node : subgraph.nodes()) {
490      for (N successorNode : graph.successors(node)) {
491        if (subgraph.nodes().contains(successorNode)) {
492          subgraph.putEdge(node, successorNode);
493        }
494      }
495    }
496    return subgraph;
497  }
498
499  /**
500   * Returns the subgraph of {@code graph} induced by {@code nodes}. This subgraph is a new graph
501   * that contains all of the nodes in {@code nodes}, and all of the {@link Graph#edges() edges}
502   * (and associated edge values) from {@code graph} for which both nodes are contained by {@code
503   * nodes}.
504   *
505   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
506   */
507  public static <N, V> MutableValueGraph<N, V> inducedSubgraph(
508      ValueGraph<N, V> graph, Iterable<? extends N> nodes) {
509    MutableValueGraph<N, V> subgraph =
510        (nodes instanceof Collection)
511            ? ValueGraphBuilder.from(graph).expectedNodeCount(((Collection) nodes).size()).build()
512            : ValueGraphBuilder.from(graph).build();
513    for (N node : nodes) {
514      subgraph.addNode(node);
515    }
516    for (N node : subgraph.nodes()) {
517      for (N successorNode : graph.successors(node)) {
518        if (subgraph.nodes().contains(successorNode)) {
519          subgraph.putEdgeValue(
520              node, successorNode, graph.edgeValueOrDefault(node, successorNode, null));
521        }
522      }
523    }
524    return subgraph;
525  }
526
527  /**
528   * Returns the subgraph of {@code network} induced by {@code nodes}. This subgraph is a new graph
529   * that contains all of the nodes in {@code nodes}, and all of the {@link Network#edges() edges}
530   * from {@code network} for which the {@link Network#incidentNodes(Object) incident nodes} are
531   * both contained by {@code nodes}.
532   *
533   * @throws IllegalArgumentException if any element in {@code nodes} is not a node in the graph
534   */
535  public static <N, E> MutableNetwork<N, E> inducedSubgraph(
536      Network<N, E> network, Iterable<? extends N> nodes) {
537    MutableNetwork<N, E> subgraph =
538        (nodes instanceof Collection)
539            ? NetworkBuilder.from(network).expectedNodeCount(((Collection) nodes).size()).build()
540            : NetworkBuilder.from(network).build();
541    for (N node : nodes) {
542      subgraph.addNode(node);
543    }
544    for (N node : subgraph.nodes()) {
545      for (E edge : network.outEdges(node)) {
546        N successorNode = network.incidentNodes(edge).adjacentNode(node);
547        if (subgraph.nodes().contains(successorNode)) {
548          subgraph.addEdge(node, successorNode, edge);
549        }
550      }
551    }
552    return subgraph;
553  }
554
555  /** Creates a mutable copy of {@code graph} with the same nodes and edges. */
556  public static <N> MutableGraph<N> copyOf(Graph<N> graph) {
557    MutableGraph<N> copy = GraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
558    for (N node : graph.nodes()) {
559      copy.addNode(node);
560    }
561    for (EndpointPair<N> edge : graph.edges()) {
562      copy.putEdge(edge.nodeU(), edge.nodeV());
563    }
564    return copy;
565  }
566
567  /** Creates a mutable copy of {@code graph} with the same nodes, edges, and edge values. */
568  public static <N, V> MutableValueGraph<N, V> copyOf(ValueGraph<N, V> graph) {
569    MutableValueGraph<N, V> copy =
570        ValueGraphBuilder.from(graph).expectedNodeCount(graph.nodes().size()).build();
571    for (N node : graph.nodes()) {
572      copy.addNode(node);
573    }
574    for (EndpointPair<N> edge : graph.edges()) {
575      copy.putEdgeValue(
576          edge.nodeU(), edge.nodeV(), graph.edgeValueOrDefault(edge.nodeU(), edge.nodeV(), null));
577    }
578    return copy;
579  }
580
581  /** Creates a mutable copy of {@code network} with the same nodes and edges. */
582  public static <N, E> MutableNetwork<N, E> copyOf(Network<N, E> network) {
583    MutableNetwork<N, E> copy =
584        NetworkBuilder.from(network)
585            .expectedNodeCount(network.nodes().size())
586            .expectedEdgeCount(network.edges().size())
587            .build();
588    for (N node : network.nodes()) {
589      copy.addNode(node);
590    }
591    for (E edge : network.edges()) {
592      EndpointPair<N> endpointPair = network.incidentNodes(edge);
593      copy.addEdge(endpointPair.nodeU(), endpointPair.nodeV(), edge);
594    }
595    return copy;
596  }
597
598  @CanIgnoreReturnValue
599  static int checkNonNegative(int value) {
600    checkArgument(value >= 0, "Not true that %s is non-negative.", value);
601    return value;
602  }
603
604  @CanIgnoreReturnValue
605  static long checkNonNegative(long value) {
606    checkArgument(value >= 0, "Not true that %s is non-negative.", value);
607    return value;
608  }
609
610  @CanIgnoreReturnValue
611  static int checkPositive(int value) {
612    checkArgument(value > 0, "Not true that %s is positive.", value);
613    return value;
614  }
615
616  @CanIgnoreReturnValue
617  static long checkPositive(long value) {
618    checkArgument(value > 0, "Not true that %s is positive.", value);
619    return value;
620  }
621
622  /**
623   * An enum representing the state of a node during DFS. {@code PENDING} means that the node is on
624   * the stack of the DFS, while {@code COMPLETE} means that the node and all its successors have
625   * been already explored. Any node that has not been explored will not have a state at all.
626   */
627  private enum NodeVisitState {
628    PENDING,
629    COMPLETE
630  }
631}