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. |
(package private) static <N> EndpointPair<N> |
transpose(EndpointPair<N> endpoints) |
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, @CheckForNull 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, @CheckForNull 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 graphpublic 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.static <N> EndpointPair<N> transpose(EndpointPair<N> endpoints)
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)