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. Node B is defined as reachable from node A if there exists a path (a sequence of adjacent outgoing edges) starting at node A and ending at node B. Note that a node is always reachable from itself via a zero-length path.

      This is a "snapshot" based on the current topology of graph, rather than a live view of the set of nodes reachable from node. In other words, the returned Set will not be updated after modifications to graph.

      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.