Package com.google.common.graph
Class Graphs
java.lang.Object
com.google.common.graph.GraphsBridgeMethods
com.google.common.graph.Graphs
- Since:
- 20.0
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static final class
private static enum
An enum representing the state of a node during DFS.private static class
private static class
private static class
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static boolean
canTraverseWithoutReusingEdge
(Graph<?> graph, Object nextNode, 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> Creates a mutable copy ofgraph
with the same nodes and edges.static <N,
E> MutableNetwork <N, E> 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
Returns true ifgraph
has at least one cycle.static boolean
Returns true ifnetwork
has at least one cycle.static <N> MutableGraph
<N> inducedSubgraph
(Graph<N> graph, Iterable<? extends N> nodes) Returns the subgraph ofgraph
induced bynodes
.static <N,
E> MutableNetwork <N, E> inducedSubgraph
(Network<N, E> network, Iterable<? extends N> nodes) Returns the subgraph ofnetwork
induced bynodes
.static <N,
V> MutableValueGraph <N, V> inducedSubgraph
(ValueGraph<N, V> graph, Iterable<? extends N> nodes) Returns the subgraph ofgraph
induced bynodes
.static <N> ImmutableSet
<N> reachableNodes
(Graph<N> graph, N node) Returns the set of nodes that are reachable fromnode
.private static <N> boolean
subgraphHasCycle
(Graph<N> graph, Map<Object, Graphs.NodeVisitState> visitedNodes, N startNode) Performs a traversal of the nodes reachable fromstartNode
.static <N> ImmutableGraph
<N> transitiveClosure
(Graph<N> graph) Returns the transitive closure ofgraph
.(package private) static <N> EndpointPair
<N> transpose
(EndpointPair<N> endpoints) static <N> Graph
<N> Returns a view ofgraph
with the direction (if any) of every edge reversed.static <N,
E> Network <N, E> 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.
-
Constructor Details
-
Graphs
private Graphs()
-
-
Method Details
-
hasCycle
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
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, Map<Object, Graphs.NodeVisitState> visitedNodes, N startNode) Performs a traversal of the nodes reachable fromstartNode
. 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, Object nextNode, @CheckForNull 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
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
.- Since:
- 33.1.0 (present with return type
Graph
since 20.0)
-
reachableNodes
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:
IllegalArgumentException
- ifnode
is not present ingraph
- Since:
- 33.1.0 (present with return type
Set
since 20.0)
-
transpose
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
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
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. -
transpose
-
inducedSubgraph
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:
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, 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:
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, 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:
IllegalArgumentException
- if any element innodes
is not a node in the graph
-
copyOf
Creates a mutable copy ofgraph
with the same nodes and edges. -
copyOf
Creates a mutable copy ofgraph
with the same nodes, edges, and edge values. -
copyOf
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)
-