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, java.lang.Iterable<? extends N> nodes)
Returns the subgraph ofgraph
induced bynodes
.static <N,E>
MutableNetwork<N,E>inducedSubgraph(Network<N,E> network, java.lang.Iterable<? extends N> nodes)
Returns the subgraph ofnetwork
induced bynodes
.static <N,V>
MutableValueGraph<N,V>inducedSubgraph(ValueGraph<N,V> graph, java.lang.Iterable<? extends N> nodes)
Returns the subgraph ofgraph
induced bynodes
.static <N> java.util.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 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 ifnetwork
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 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> java.util.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 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 fromnode
. In other words, the returnedSet
will not be updated after modifications tograph
.- Throws:
java.lang.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, java.lang.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:
java.lang.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, java.lang.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:
java.lang.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, java.lang.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:
java.lang.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.
-
-