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