Package com.google.common.graph

Class Graphs

java.lang.Object

com.google.common.graph.Graphs

@Beta
public final class Graphs
extends java.lang.Object

Static utility methods for Graph, ValueGraph, and Network instances.

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

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 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Graphs

private Graphs()

Method Detail

hasCycle

public static <N> boolean hasCycle(Graph<N> graph)

Returns true if 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).

hasCycle

public static boolean hasCycle(Network<?,?> network)

Returns true if 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).

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 from 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.

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 of 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.

reachableNodes

public static <N> java.util.Set<N> reachableNodes(Graph<N> graph,
                                                  N node)

Returns the set of nodes that are reachable from 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.

Throws:

java.lang.IllegalArgumentException - if node is not present in graph

transpose

public static <N> Graph<N> transpose(Graph<N> graph)

Returns a view of 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.

transpose

public 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. All other properties remain intact, and further updates to graph will be reflected in the view.

transpose

public 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. All other properties remain intact, and further updates to network will be reflected in the view.

transpose

static <N> EndpointPair<N> transpose(EndpointPair<N> endpoints)

inducedSubgraph

public static <N> MutableGraph<N> inducedSubgraph(Graph<N> graph,
                                                  java.lang.Iterable<? extends N> nodes)

Returns the subgraph of 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.

Throws:

java.lang.IllegalArgumentException - if any element in nodes 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 of 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.

Throws:

java.lang.IllegalArgumentException - if any element in nodes 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 of 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.

Throws:

java.lang.IllegalArgumentException - if any element in nodes is not a node in the graph

copyOf

public static <N> MutableGraph<N> copyOf(Graph<N> graph)

Creates a mutable copy of graph with the same nodes and edges.

copyOf

public 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.

copyOf

public static <N,E> MutableNetwork<N,E> copyOf(Network<N,E> network)

Creates a mutable copy of network 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)