Package com.google.common.graph
Class Graphs
 java.lang.Object

 com.google.common.graph.Graphs


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 ofgraph
with the same nodes and edges.static <N,E>
MutableNetwork<N,E>copyOf(Network<N,E> network)
Creates a mutable copy ofnetwork
with the same nodes and edges.static <N,V>
MutableValueGraph<N,V>copyOf(ValueGraph<N,V> graph)
Creates a mutable copy ofgraph
with the same nodes, edges, and edge values.static <N> boolean
hasCycle(Graph<N> graph)
Returns true ifgraph
has at least one cycle.static boolean
hasCycle(Network<?,?> network)
Returns true ifnetwork
has at least one cycle.static <N> MutableGraph<N>
inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes)
Returns the subgraph ofgraph
induced bynodes
.static <N,E>
MutableNetwork<N,E>inducedSubgraph(Network<N,E> network, Iterable<? extends N> nodes)
Returns the subgraph ofnetwork
induced bynodes
.static <N,V>
MutableValueGraph<N,V>inducedSubgraph(ValueGraph<N,V> graph, Iterable<? extends N> nodes)
Returns the subgraph ofgraph
induced bynodes
.static <N> Set<N>
reachableNodes(Graph<N> graph, N node)
Returns the set of nodes that are reachable fromnode
.static <N> Graph<N>
transitiveClosure(Graph<N> graph)
Returns the transitive closure ofgraph
.static <N> Graph<N>
transpose(Graph<N> graph)
Returns a view ofgraph
with the direction (if any) of every edge reversed.static <N,E>
Network<N,E>transpose(Network<N,E> network)
Returns a view ofnetwork
with the direction (if any) of every edge reversed.static <N,V>
ValueGraph<N,V>transpose(ValueGraph<N,V> graph)
Returns a view ofgraph
with the direction (if any) of every edge reversed.



Method Detail

hasCycle
public static <N> boolean hasCycle(Graph<N> graph)
Returns true ifgraph
has at least one cycle. A cycle is defined as a nonempty 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 nonempty cycle, including selfloops (a cycle of length 1).

hasCycle
public static boolean hasCycle(Network<?,?> network)
Returns true ifnetwork
has at least one cycle. A cycle is defined as a nonempty 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 nonempty cycle, including selfloops (a cycle of length 1).

transitiveClosure
public static <N> Graph<N> transitiveClosure(Graph<N> graph)
Returns the transitive closure ofgraph
. The transitive closure of a graph is another graph with an edge connecting node A to node B if node B isreachable
from node A.This is a "snapshot" based on the current topology of
graph
, rather than a live view of the transitive closure ofgraph
. In other words, the returnedGraph
will not be updated after modifications tograph
.

reachableNodes
public static <N> Set<N> reachableNodes(Graph<N> graph, N node)
Returns the set of nodes that are reachable fromnode
. 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 zerolength path.This is a "snapshot" based on the current topology of
graph
, rather than a live view of the set of nodes reachable fromnode
. In other words, the returnedSet
will not be updated after modifications tograph
. Throws:
IllegalArgumentException
 ifnode
is not present ingraph

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

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

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

inducedSubgraph
public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes)
Returns the subgraph ofgraph
induced bynodes
. This subgraph is a new graph that contains all of the nodes innodes
, and all of theedges
fromgraph
for which both nodes are contained bynodes
. Throws:
IllegalArgumentException
 if any element innodes
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 ofgraph
induced bynodes
. This subgraph is a new graph that contains all of the nodes innodes
, and all of theedges
(and associated edge values) fromgraph
for which both nodes are contained bynodes
. Throws:
IllegalArgumentException
 if any element innodes
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 ofnetwork
induced bynodes
. This subgraph is a new graph that contains all of the nodes innodes
, and all of theedges
fromnetwork
for which theincident nodes
are both contained bynodes
. Throws:
IllegalArgumentException
 if any element innodes
is not a node in the graph

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

copyOf
public static <N,V> MutableValueGraph<N,V> copyOf(ValueGraph<N,V> graph)
Creates a mutable copy ofgraph
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 ofnetwork
with the same nodes and edges.

