java.lang.Object
org.jgrapht.alg.shortestpath.AllDirectedPaths<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
A Dijkstra-like algorithm to find all paths between two sets of nodes in a directed graph, with
options to search only simple paths and to limit the path length.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final PathValidator
<V, E> Provides validation for the paths which will be computed. -
Constructor Summary
ConstructorsConstructorDescriptionAllDirectedPaths
(Graph<V, E> graph) Create a new instance.AllDirectedPaths
(Graph<V, E> graph, PathValidator<V, E> pathValidator) Create a new instance with givenpathValidator
. -
Method Summary
Modifier and TypeMethodDescriptionedgeMinDistancesBackwards
(Set<V> targetVertices, Integer maxPathLength) Compute the minimum number of edges in a path to the targets through each edge, so long as it is not greater than a bound.generatePaths
(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, Integer maxPathLength, Map<E, Integer> edgeMinDistancesFromTargets) Generate all paths from the sources to the targets, using pre-computed minimum distances.getAllPaths
(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, Integer maxPathLength) Calculate (and return) all paths from the source vertices to the target vertices.getAllPaths
(V sourceVertex, V targetVertex, boolean simplePathsOnly, Integer maxPathLength) Calculate (and return) all paths from the source vertex to the target vertex.Transform an ordered list of edges into a GraphPath.
-
Field Details
-
graph
-
pathValidator
Provides validation for the paths which will be computed. If the validator isnull
, this means that all paths are valid.
-
-
Constructor Details
-
AllDirectedPaths
Create a new instance.- Parameters:
graph
- the input graph- Throws:
IllegalArgumentException
- if the graph is not directed
-
AllDirectedPaths
Create a new instance with givenpathValidator
. If non-null
, thepathValidator
will be used while searching for paths, validating the addition of any edge to a partial path. Zero-length paths will therefore not be subject topathValidator
; length-1 paths will.- Parameters:
graph
- the input graphpathValidator
- validator for computed paths; may be null- Throws:
IllegalArgumentException
- if the graph is not directed
-
-
Method Details
-
getAllPaths
public List<GraphPath<V,E>> getAllPaths(V sourceVertex, V targetVertex, boolean simplePathsOnly, Integer maxPathLength) Calculate (and return) all paths from the source vertex to the target vertex.- Parameters:
sourceVertex
- the source vertextargetVertex
- the target vertexsimplePathsOnly
- if true, only search simple (non-self-intersecting) pathsmaxPathLength
- maximum number of edges to allow in a path (if null, all paths are considered, which may be very slow due to potentially huge output)- Returns:
- all paths from the source vertex to the target vertex
-
getAllPaths
public List<GraphPath<V,E>> getAllPaths(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, Integer maxPathLength) Calculate (and return) all paths from the source vertices to the target vertices.- Parameters:
sourceVertices
- the source verticestargetVertices
- the target verticessimplePathsOnly
- if true, only search simple (non-self-intersecting) pathsmaxPathLength
- maximum number of edges to allow in a path (if null, all paths are considered, which may be very slow due to potentially huge output)- Returns:
- list of all paths from the sources to the targets containing no more than maxPathLength edges
-
edgeMinDistancesBackwards
Compute the minimum number of edges in a path to the targets through each edge, so long as it is not greater than a bound.- Parameters:
targetVertices
- the target verticesmaxPathLength
- maximum number of edges to allow in a path (if null, all edges will be considered, which may be expensive)- Returns:
- the minimum number of edges in a path from each edge to the targets, encoded in a Map
-
generatePaths
private List<GraphPath<V,E>> generatePaths(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, Integer maxPathLength, Map<E, Integer> edgeMinDistancesFromTargets) Generate all paths from the sources to the targets, using pre-computed minimum distances.- Parameters:
sourceVertices
- the source verticestargetVertices
- the target verticessimplePathsOnly
- if true, only search simple (non-self-intersecting) paths (if null, all edges will be considered, which may be expensive)maxPathLength
- maximum number of edges to allow in a pathedgeMinDistancesFromTargets
- the minimum number of edges in a path to a target through each edge, as computed byedgeMinDistancesBackwards
.- Returns:
- a List of all GraphPaths from the sources to the targets satisfying the given constraints
-
makePath
Transform an ordered list of edges into a GraphPath. The weight of the generated GraphPath is set to the sum of the weights of the edges.- Parameters:
edges
- the edges- Returns:
- the corresponding GraphPath
-