Package com.google.common.graph

Class Graphs

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

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static <N> MutableGraph<N> copyOf​(Graph<N> graph)
      Creates a mutable copy of graph with the same nodes and edges.
      static <N,​E>
      MutableNetwork<N,​E>      		 copyOf​(Network<N,​E> network)
      Creates a mutable copy of network with the same nodes and edges.
      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.
      static <N> boolean hasCycle​(Graph<N> graph)
      Returns true if graph has at least one cycle.
      static boolean hasCycle​(Network<?,​?> network)
      Returns true if network has at least one cycle.
      static <N> MutableGraph<N> inducedSubgraph​(Graph<N> graph, java.lang.Iterable<? extends N> nodes)
      Returns the subgraph of graph induced by nodes.
      static <N,​E>
      MutableNetwork<N,​E>      		 inducedSubgraph​(Network<N,​E> network, java.lang.Iterable<? extends N> nodes)
      Returns the subgraph of network induced by nodes.
      static <N,​V>
      MutableValueGraph<N,​V>      		 inducedSubgraph​(ValueGraph<N,​V> graph, java.lang.Iterable<? extends N> nodes)
      Returns the subgraph of graph induced by nodes.
      static <N> java.util.Set<N> reachableNodes​(Graph<N> graph, N node)
      Returns the set of nodes that are reachable from node.
      static <N> Graph<N> transitiveClosure​(Graph<N> graph)
      Returns the transitive closure of graph.
      static <N> Graph<N> transpose​(Graph<N> graph)
      Returns a view of graph with the direction (if any) of every edge reversed.
      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.
      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.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Method Detail

      • 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> Graph<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.

      • reachableNodes

        public static <N> java.util.Set<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:
        java.lang.IllegalArgumentException - if node is not present in graph

      • 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,
                                                  java.lang.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:
        java.lang.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,
                                                                       java.lang.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:
        java.lang.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,
                                                                    java.lang.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:
        java.lang.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.