public final class Graphs 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).
|
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 <E,EP> Mapping<E,EP> |
edgeProperties(UniversalIndefiniteGraph<?,E,?,EP> graph)
Deprecated.
|
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> Path<N,E> |
findShortestPath(IndefiniteGraph<N,E> graph,
int limit,
N start,
Collection<? extends N> targets) |
static <N,E> Path<N,E> |
findShortestPath(IndefiniteGraph<N,E> graph,
int limit,
N start,
Predicate<? super N> targetPred) |
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,Collection<E>> |
incomingEdges(Graph<N,E> graph) |
static <N,NP> Mapping<N,NP> |
nodeProperties(UniversalIndefiniteGraph<N,?,NP,?> graph)
Deprecated.
|
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> Mapping<N,Collection<E>> incomingEdges(Graph<N,E> graph)
public static <N,E> Path<N,E> findShortestPath(IndefiniteGraph<N,E> graph, int limit, N start, Collection<? extends N> targets)
public static <N,E> Path<N,E> findShortestPath(IndefiniteGraph<N,E> graph, int limit, N start, Predicate<? super N> targetPred)
@Deprecated public static <N,NP> Mapping<N,NP> nodeProperties(UniversalIndefiniteGraph<N,?,NP,?> graph)
@Deprecated public static <E,EP> Mapping<E,EP> edgeProperties(UniversalIndefiniteGraph<?,E,?,EP> graph)
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 © 2018. All rights reserved.