Class Graphs
- java.lang.Object
-
- com.google.common.graph.Graphs
-
@Beta public final class Graphs extends java.lang.Object
- Since:
- 20.0
-
-
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 boolean
equivalent(Graph<?> graphA, Graph<?> graphB)
Returnstrue
ifgraphA
andgraphB
have the same elements and the same relationships between elements, as exposed via theGraph
interface.static boolean
equivalent(Network<?,?> networkA, Network<?,?> networkB)
Returnstrue
ifnetworkA
andnetworkB
have the same elements and the same relationships between elements, as exposed via theNetwork
interface.static boolean
equivalent(ValueGraph<?,?> graphA, ValueGraph<?,?> graphB)
Returnstrue
ifgraphA
andgraphB
have the same elements (including edge values) and the same relationships between elements, as exposed via theValueGraph
interface.static boolean
hasCycle(Graph<?> 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, java.lang.Object 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 boolean hasCycle(Graph<?> 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, java.lang.Object 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
-
equivalent
public static boolean equivalent(@Nullable Graph<?> graphA, @Nullable Graph<?> graphB)
Returnstrue
ifgraphA
andgraphB
have the same elements and the same relationships between elements, as exposed via theGraph
interface.Thus, two graphs A and B are equivalent if both are null or all of the following are true:
- A and B have equal
directedness
. - A and B have equal
node sets
. - A and B have equal
edge sets
.
Graph properties besides
directedness
do not affect equivalence. For example, two graphs may be considered equivalent even if one allows self-loops and the other doesn't. Additionally, the order in which nodes or edges are added to the graph, and the order in which they are iterated over, are irrelevant. - A and B have equal
-
equivalent
public static boolean equivalent(@Nullable ValueGraph<?,?> graphA, @Nullable ValueGraph<?,?> graphB)
Returnstrue
ifgraphA
andgraphB
have the same elements (including edge values) and the same relationships between elements, as exposed via theValueGraph
interface.Thus, two value graphs A and B are equivalent if both are null or all of the following are true:
- A and B have equal
directedness
. - A and B have equal
node sets
. - A and B have equal
edge sets
. - Each edge in A has a
value
equal to thevalue
of the corresponding edge in B.
Graph properties besides
directedness
do not affect equivalence. For example, two graphs may be considered equivalent even if one allows self-loops and the other doesn't. Additionally, the order in which nodes or edges are added to the graph, and the order in which they are iterated over, are irrelevant. - A and B have equal
-
equivalent
public static boolean equivalent(@Nullable Network<?,?> networkA, @Nullable Network<?,?> networkB)
Returnstrue
ifnetworkA
andnetworkB
have the same elements and the same relationships between elements, as exposed via theNetwork
interface.Thus, two networks A and B are equivalent if both are null or all of the following are true:
- A and B have equal
directedness
. - A and B have equal
node sets
. - A and B have equal
edge sets
. - Each edge in A connects the same nodes in the same direction (if any) as the corresponding edge in B.
Network properties besides
directedness
do not affect equivalence. For example, two networks may be considered equal even if one allows parallel edges and the other doesn't. Additionally, the order in which nodes or edges are added to the network, and the order in which they are iterated over, are irrelevant. - A and B have equal
-
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.
-
-