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 classprivate static enumAn enum representing the state of a node during DFS.private static classprivate static classprivate static class -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static booleancanTraverseWithoutReusingEdge(Graph<?> graph, Object nextNode, Object previousNode) Determines whether an edge has already been used during traversal.(package private) static intcheckNonNegative(int value) (package private) static longcheckNonNegative(long value) (package private) static intcheckPositive(int value) (package private) static longcheckPositive(long value) static <N> MutableGraph<N> Creates a mutable copy ofgraphwith the same nodes and edges.static <N,E> MutableNetwork <N, E> Creates a mutable copy ofnetworkwith the same nodes and edges.static <N,V> MutableValueGraph <N, V> copyOf(ValueGraph<N, V> graph) Creates a mutable copy ofgraphwith the same nodes, edges, and edge values.static <N> booleanReturns true ifgraphhas at least one cycle.static booleanReturns true ifnetworkhas at least one cycle.static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph, Iterable<? extends N> nodes) Returns the subgraph ofgraphinduced bynodes.static <N,E> MutableNetwork <N, E> inducedSubgraph(Network<N, E> network, Iterable<? extends N> nodes) Returns the subgraph ofnetworkinduced bynodes.static <N,V> MutableValueGraph <N, V> inducedSubgraph(ValueGraph<N, V> graph, Iterable<? extends N> nodes) Returns the subgraph ofgraphinduced bynodes.static <N> ImmutableSet<N> reachableNodes(Graph<N> graph, N node) Returns the set of nodes that are reachable fromnode.private static <N> booleansubgraphHasCycle(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 ofgraphwith the direction (if any) of every edge reversed.static <N,E> Network <N, E> Returns a view ofnetworkwith the direction (if any) of every edge reversed.static <N,V> ValueGraph <N, V> transpose(ValueGraph<N, V> graph) Returns a view ofgraphwith the direction (if any) of every edge reversed.
-
Constructor Details
-
Graphs
private Graphs()
-
-
Method Details
-
hasCycle
Returns true ifgraphhas 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 ifnetworkhas 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 isreachablefrom 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 returnedGraphwill not be updated after modifications tograph.- Since:
- 33.1.0 (present with return type
Graphsince 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 returnedSetwill not be updated after modifications tograph.- Throws:
IllegalArgumentException- ifnodeis not present ingraph- Since:
- 33.1.0 (present with return type
Setsince 20.0)
-
transpose
Returns a view ofgraphwith the direction (if any) of every edge reversed. All other properties remain intact, and further updates tographwill be reflected in the view. -
transpose
Returns a view ofgraphwith the direction (if any) of every edge reversed. All other properties remain intact, and further updates tographwill be reflected in the view. -
transpose
Returns a view ofnetworkwith the direction (if any) of every edge reversed. All other properties remain intact, and further updates tonetworkwill be reflected in the view. -
transpose
-
inducedSubgraph
Returns the subgraph ofgraphinduced bynodes. This subgraph is a new graph that contains all of the nodes innodes, and all of theedgesfromgraphfor which both nodes are contained bynodes.- Throws:
IllegalArgumentException- if any element innodesis 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 ofgraphinduced bynodes. This subgraph is a new graph that contains all of the nodes innodes, and all of theedges(and associated edge values) fromgraphfor which both nodes are contained bynodes.- Throws:
IllegalArgumentException- if any element innodesis 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 ofnetworkinduced bynodes. This subgraph is a new graph that contains all of the nodes innodes, and all of theedgesfromnetworkfor which theincident nodesare both contained bynodes.- Throws:
IllegalArgumentException- if any element innodesis not a node in the graph
-
copyOf
Creates a mutable copy ofgraphwith the same nodes and edges. -
copyOf
Creates a mutable copy ofgraphwith the same nodes, edges, and edge values. -
copyOf
Creates a mutable copy ofnetworkwith 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)
-