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