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