Package com.google.common.graph
Class Graphs
- java.lang.Object
-
- com.google.common.graph.Graphs
-
@Beta public final class Graphs extends java.lang.Object
- Since:
- 20.0
-
-
Nested Class Summary
Nested Classes Modifier and Type Class 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>
-
Constructor Summary
Constructors Modifier Constructor Description private
Graphs()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method 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 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
.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 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).
-
subgraphHasCycle
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 fromnode
. 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.
-
canTraverseWithoutReusingEdge
private static boolean canTraverseWithoutReusingEdge(Graph<?> graph, java.lang.Object nextNode, java.lang.Object previousNode)
Determines whether an edge has already been used during traversal. In the directed case a cycle is always detected before reusing an edge, so no special logic is required. In the undirected case, we must take care not to "backtrack" over an edge (i.e. going from A to B and then going from B to A).
-
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.
-
checkNonNegative
static int checkNonNegative(int value)
-
checkNonNegative
static long checkNonNegative(long value)
-
checkPositive
static int checkPositive(int value)
-
checkPositive
static long checkPositive(long value)
-
-