Package net.automatalib.util.graph
Class Graphs
- java.lang.Object
-
- net.automatalib.util.graph.Graphs
-
public final class Graphs extends Object
-
-
Field Summary
Fields Modifier and Type Field 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).
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method 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>
voidfindSCCs(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>
Mapping<N,@Nullable Collection<E>>incomingEdges(Graph<N,E> graph)
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.
-
-
-
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).- See Also:
- Constant Field Values
-
-
Method Detail
-
incomingEdges
public static <N,E> Mapping<N,@Nullable Collection<E>> incomingEdges(Graph<N,E> graph)
-
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 edgesgraph
- the graphinit
- 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 graphedgeWeights
- the edge weights- Returns:
- the all pairs shortest paths result
- See Also:
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 graphinit
- the source nodeedgeWeights
- the edge weights- Returns:
- the single-source shortest paths result
- See Also:
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
- See Also:
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, theSCCListener.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 graphsccListener
- the SCC listener- See Also:
TarjanSCCVisitor
,SCCs
-
-