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