Package net.automatalib.util.graph

Class Graphs

java.lang.Object

net.automatalib.util.graph.Graphs

public final class Graphs
extends Object

Field Summary

Fields

Modifier and Type	Field	Description
static float	INVALID_DISTANCE	Float value to signal that no valid distance is returned (e.g., when attempting to retrieve the length of a path that does not exist).

Method Summary

Modifier and Type	Method	Description
static <N,E> List<List<N>>	collectSCCs(Graph<N,E> graph)	Collects all strongly-connected components in a graph.
static <N,E> APSPResult<N,E>	findAPSP(Graph<N,E> graph, EdgeWeights<E> edgeWeights)	Computes the shortest paths between all pairs of nodes in a graph, using the Floyd-Warshall dynamic programming algorithm.
static <N,E> void	findSCCs(Graph<N,E> graph, SCCListener<N> sccListener)	Find all strongly-connected components in a graph.
static <N,E> SSSPResult<N,E>	findSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights)	Computes the shortest paths between a single source node and all other nodes in a graph, using Dijkstra's algorithm.
static <N,E> Mapping<N,@Nullable Collection<E>>	incomingEdges(Graph<N,E> graph)
static <N,E> List<N>	toNodeList(List<E> edgeList, Graph<N,E> graph, N init)	Converts a list of edges into a corresponding list of nodes.

Methods inherited from class java.lang.Object

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

Field Detail

INVALID_DISTANCE

public static final float INVALID_DISTANCE

Float value to signal that no valid distance is returned (e.g., when attempting to retrieve the length of a path that does not exist).

See Also:

Constant Field Values

Method Detail

incomingEdges

public static <N,E> Mapping<N,@Nullable Collection<E>> incomingEdges(Graph<N,E> graph)

toNodeList

public static <N,E> List<N> toNodeList(List<E> edgeList,
                                             Graph<N,E> graph,
                                             N init)

Converts a list of edges into a corresponding list of nodes. Note that the list of nodes is always one larger than the respective list of edges.

Parameters:

edgeList - the list of edges

graph - the graph

init - the initial node

Returns:

the node list corresponding to the given edge list.

findAPSP

public static <N,E> APSPResult<N,E> findAPSP(Graph<N,E> graph,
                                                         EdgeWeights<E> edgeWeights)

Computes the shortest paths between all pairs of nodes in a graph, using the Floyd-Warshall dynamic programming algorithm. Note that the result is only correct if the graph contains no cycles with negative edge weight sums.

Parameters:

graph - the graph

edgeWeights - the edge weights

Returns:

the all pairs shortest paths result

See Also:

FloydWarshallAPSP

findSSSP

public static <N,E> SSSPResult<N,E> findSSSP(Graph<N,E> graph,
                                                         N init,
                                                         EdgeWeights<E> edgeWeights)

Computes the shortest paths between a single source node and all other nodes in a graph, using Dijkstra's algorithm. Note that the result is only correct if the graph contains no edges with negative weights.

Parameters:

graph - the graph

init - the source node

edgeWeights - the edge weights

Returns:

the single-source shortest paths result

See Also:

DijkstraSSSP

collectSCCs

public static <N,E> List<List<N>> collectSCCs(Graph<N,E> graph)

Collects all strongly-connected components in a graph. The SCCs are returned as a list of lists.

Tarjan's algorithm is used for realizing the SCC search.

Parameters:

graph - the graph

Returns:

a list of all SCCs, each represented as a list of its nodes

See Also:

TarjanSCCVisitor, SCCs

findSCCs

public static <N,E> void findSCCs(Graph<N,E> graph,
                                        SCCListener<N> sccListener)

Find all strongly-connected components in a graph. When a new SCC is found, the SCCListener.foundSCC(java.util.Collection) method is invoked. The listener object may hence not be null.

Tarjan's algorithm is used for realizing the SCC search.

Parameters:

graph - the graph

sccListener - the SCC listener

See Also:

TarjanSCCVisitor, SCCs