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()`
• ### Method Summary

All Methods
Modifier and Type Method and 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> 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).
Constant Field Values
• ### Constructor Detail

• #### GraphAlgorithms

`public GraphAlgorithms()`
• ### 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
`TarjanSCCVisitor`, `SCCs`