Package com.google.common.graph

Class Graphs

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