net.automatalib.algorithms.graph

Class GraphAlgorithms

• public class GraphAlgorithms
extends Object
Convenience entry points and helper methods for various graph algorithms.
Author:
Malte Isberner
• Field Summary

Fields
Modifier and Type Field and 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).
• Constructor Summary

Constructors
Constructor and Description
GraphAlgorithms()
• 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).
Constant Field Values
• Method Detail

• 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
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
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
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
listener - the SCC listener