@ParametersAreNonnullByDefault public class GraphAlgorithms extends Object
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 and Description |
---|
GraphAlgorithms() |
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.
|
public static final float INVALID_DISTANCE
public static <N,E> List<N> toNodeList(List<E> edgeList, Graph<N,E> graph, N init)
edgeList
- the list of edgesgraph
- the graphinit
- the initial nodepublic static <N,E> APSPResult<N,E> findAPSP(Graph<N,E> graph, EdgeWeights<E> edgeWeights)
graph
- the graphedgeWeights
- the edge weightsFloydWarshallAPSP
public static <N,E> SSSPResult<N,E> findSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights)
graph
- the graphinit
- the source nodeedgeWeights
- the edge weightsDijkstraSSSP
public static <N,E> List<List<N>> collectSCCs(Graph<N,E> graph)
Tarjan's algorithm is used for realizing the SCC search.
graph
- the graphTarjanSCCVisitor
,
SCCs
public static <N,E> void findSCCs(Graph<N,E> graph, SCCListener<N> sccListener)
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.
graph
- the graphsccListener
- the SCC listenerTarjanSCCVisitor
,
SCCs
Copyright © 2015. All rights reserved.