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 stronglyconnected 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
FloydWarshall dynamic programming algorithm.

static <N,E> void 
findSCCs(Graph<N,E> graph,
SCCListener<N> sccListener)
Find all stronglyconnected 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 GraphAlgorithms()
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 graphlistener
 the SCC listenerTarjanSCCVisitor
,
SCCs
Copyright © 2015. All Rights Reserved.