@Beta public final class Graphs extends java.lang.Object
Modifier and Type | Class and Description |
---|---|
private static class |
Graphs.NodeVisitState
An enum representing the state of a node during DFS.
|
private static class |
Graphs.TransposedGraph<N> |
private static class |
Graphs.TransposedNetwork<N,E> |
private static class |
Graphs.TransposedValueGraph<N,V> |
Modifier | Constructor and Description |
---|---|
private |
Graphs() |
Modifier and Type | Method and Description |
---|---|
private static boolean |
canTraverseWithoutReusingEdge(Graph<?> graph,
java.lang.Object nextNode,
java.lang.Object previousNode)
Determines whether an edge has already been used during traversal.
|
(package private) static int |
checkNonNegative(int value) |
(package private) static long |
checkNonNegative(long value) |
(package private) static int |
checkPositive(int value) |
(package private) static long |
checkPositive(long value) |
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 . |
private static <N> boolean |
subgraphHasCycle(Graph<N> graph,
java.util.Map<java.lang.Object,Graphs.NodeVisitState> visitedNodes,
N node,
N previousNode)
Performs a traversal of the nodes 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. |
public static <N> boolean hasCycle(Graph<N> graph)
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).
public static boolean hasCycle(Network<?,?> network)
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).
private static <N> boolean subgraphHasCycle(Graph<N> graph, java.util.Map<java.lang.Object,Graphs.NodeVisitState> visitedNodes, N node, N previousNode)
node
. If we ever reach a node we've
already visited (following only outgoing edges and without reusing edges), we know there's a
cycle in the graph.private static boolean canTraverseWithoutReusingEdge(Graph<?> graph, java.lang.Object nextNode, java.lang.Object previousNode)
public static <N> Graph<N> transitiveClosure(Graph<N> graph)
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
.
public static <N> java.util.Set<N> reachableNodes(Graph<N> graph, N node)
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
.
java.lang.IllegalArgumentException
- if node
is not present in graph
public static <N> Graph<N> transpose(Graph<N> graph)
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.public static <N,V> ValueGraph<N,V> transpose(ValueGraph<N,V> graph)
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.public static <N,E> Network<N,E> transpose(Network<N,E> network)
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.public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, java.lang.Iterable<? extends N> nodes)
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
.java.lang.IllegalArgumentException
- if any element in nodes
is not a node in the graphpublic static <N,V> MutableValueGraph<N,V> inducedSubgraph(ValueGraph<N,V> graph, java.lang.Iterable<? extends N> nodes)
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
.java.lang.IllegalArgumentException
- if any element in nodes
is not a node in the graphpublic static <N,E> MutableNetwork<N,E> inducedSubgraph(Network<N,E> network, java.lang.Iterable<? extends N> nodes)
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
.java.lang.IllegalArgumentException
- if any element in nodes
is not a node in the graphpublic static <N> MutableGraph<N> copyOf(Graph<N> graph)
graph
with the same nodes and edges.public static <N,V> MutableValueGraph<N,V> copyOf(ValueGraph<N,V> graph)
graph
with the same nodes, edges, and edge values.public static <N,E> MutableNetwork<N,E> copyOf(Network<N,E> network)
network
with the same nodes and edges.static int checkNonNegative(int value)
static long checkNonNegative(long value)
static int checkPositive(int value)
static long checkPositive(long value)