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