Class Graphs

java.lang.Object
com.google.common.graph.Graphs
@Beta public final class Graphs extends Object
Static utility methods for Graph, ValueGraph, and Network instances.
Since:
20.0
Author:
James Sexton, Joshua O'Madadhain

  • Method Details

    • hasCycle

      public static <N> boolean hasCycle(Graph<N> graph)
      Returns true if graph has at least one cycle. A cycle is defined as a non-empty subset of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting and ending with the same node.

      This method will detect any non-empty cycle, including self-loops (a cycle of length 1).

    • hasCycle

      public static boolean hasCycle(Network<?,?> network)
      Returns true if network has at least one cycle. A cycle is defined as a non-empty subset of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting and ending with the same node.

      This method will detect any non-empty cycle, including self-loops (a cycle of length 1).

    • transitiveClosure

      public static <N> ImmutableGraph<N> transitiveClosure(Graph<N> graph)
      Returns the transitive closure of graph. The transitive closure of a graph is another graph with an edge connecting node A to node B if node B is reachable from node A.

      This is a "snapshot" based on the current topology of graph, rather than a live view of the transitive closure of graph. In other words, the returned Graph will not be updated after modifications to graph.

      Since:
      33.1.0 (present with return type Graph since 20.0)

    • reachableNodes

      public static <N> ImmutableSet<N> reachableNodes(Graph<N> graph, N node)
      Returns the set of nodes that are reachable from node. Specifically, it returns all nodes v such that there exists a path (a sequence of adjacent outgoing edges) starting at node and ending at v. This implementation includes node as the first element in the result.

      If needed, the Traverser class provides more flexible and lighter-weight ways to list the nodes reachable from a given node or nodes. See the "Graph traversal" section of the Guava User's Guide for more information.

      The Set returned is a "snapshot" based on the current topology of graph, rather than a live view. In other words, modifications to graph made after this method returns will not be reflected in the set.

      Throws:
      IllegalArgumentException - if node is not present in graph
      Since:
      33.1.0 (present with return type Set since 20.0)

    • transpose

      public static <N> Graph<N> transpose(Graph<N> graph)
      Returns a view of graph with the direction (if any) of every edge reversed. All other properties remain intact, and further updates to graph will be reflected in the view.

    • transpose

      public static <N,V> ValueGraph<N,V> transpose(ValueGraph<N,V> graph)
      Returns a view of graph with the direction (if any) of every edge reversed. All other properties remain intact, and further updates to graph will be reflected in the view.

    • transpose

      public static <N,E> Network<N,E> transpose(Network<N,E> network)
      Returns a view of network with the direction (if any) of every edge reversed. All other properties remain intact, and further updates to network will be reflected in the view.

    • inducedSubgraph

      public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes)
      Returns the subgraph of graph induced by nodes. This subgraph is a new graph that contains all of the nodes in nodes, and all of the edges from graph for which both nodes are contained by nodes.
      Throws:
      IllegalArgumentException - if any element in nodes is not a node in the graph

    • inducedSubgraph

      public static <N,V> MutableValueGraph<N,V> inducedSubgraph(ValueGraph<N,V> graph, Iterable<? extends N> nodes)
      Returns the subgraph of graph induced by nodes. This subgraph is a new graph that contains all of the nodes in nodes, and all of the edges (and associated edge values) from graph for which both nodes are contained by nodes.
      Throws:
      IllegalArgumentException - if any element in nodes is not a node in the graph

    • inducedSubgraph

      public static <N,E> MutableNetwork<N,E> inducedSubgraph(Network<N,E> network, Iterable<? extends N> nodes)
      Returns the subgraph of network induced by nodes. This subgraph is a new graph that contains all of the nodes in nodes, and all of the edges from network for which the incident nodes are both contained by nodes.
      Throws:
      IllegalArgumentException - if any element in nodes is not a node in the graph

    • copyOf

      public static <N> MutableGraph<N> copyOf(Graph<N> graph)
      Creates a mutable copy of graph with the same nodes and edges.

    • copyOf

      public static <N,V> MutableValueGraph<N,V> copyOf(ValueGraph<N,V> graph)
      Creates a mutable copy of graph with the same nodes, edges, and edge values.

    • copyOf

      public static <N,E> MutableNetwork<N,E> copyOf(Network<N,E> network)
      Creates a mutable copy of network with the same nodes and edges.