Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath
Class BaseKDisjointShortestPathsAlgorithm<V,E>
java.lang.Object
org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
KShortestPathAlgorithm<V,
E>
- Direct Known Subclasses:
BhandariKDisjointShortestPaths
,SuurballeKDisjointShortestPaths
abstract class BaseKDisjointShortestPathsAlgorithm<V,E>
extends Object
implements KShortestPathAlgorithm<V,E>
A base implementation of a $k$ disjoint shortest paths algorithm based on the strategy used in
Suurballe and Bhandari algorithms. The algorithm procedure goes as follow:
- Using some known shortest path algorithm (e.g. Dijkstra) to find the shortest path $P_1$ from source to target.
- For i = 2,...,$k$
- Perform some graph transformations based on the previously found path
- Find the shortest path $P_i$ from source to target
- Remove all overlapping edges to get $k$ disjoint paths.
transformGraph(java.util.List<E>)
- to be used in step 3.calculateShortestPath(V, V)
- to be used in step 4.
SuurballeKDisjointShortestPaths
and
BhandariKDisjointShortestPaths
.-
Field Summary
FieldsModifier and TypeFieldDescriptionGraph on which shortest paths are searched. -
Constructor Summary
ConstructorsConstructorDescriptionBaseKDisjointShortestPathsAlgorithm
(Graph<V, E> graph) Creates a new instance of the algorithm -
Method Summary
Modifier and TypeMethodDescriptionbuildPaths
(V startVertex, V endVertex) After removing overlapping edges, each path is not necessarily connecting start to end vertex.calculateShortestPath
(V startVertex, V endVertex) Calculates the shortest paths for the current iteration.createGraphPath
(List<E> edgeList, V startVertex, V endVertex) private void
Iterate over all paths and remove all edges used an even number of times.private V
getEdgeSource
(E e) private V
getEdgeTarget
(E e) Returns the $k$ shortest simple paths in increasing order of weight.resolvePaths
(V startVertex, V endVertex) At the end of the search we have list of intermediate paths - not necessarily disjoint and may contain reversed edges.protected abstract void
transformGraph
(List<E> previousPath) Prepares the working graph for next iteration.
-
Field Details
-
workingGraph
Graph on which shortest paths are searched. -
pathList
-
originalGraph
-
validEdges
-
-
Constructor Details
-
BaseKDisjointShortestPathsAlgorithm
Creates a new instance of the algorithm- Parameters:
graph
- graph on which shortest paths are searched.- Throws:
IllegalArgumentException
- if the graph is null.IllegalArgumentException
- if the graph is undirected.IllegalArgumentException
- if the graph is not simple.
-
-
Method Details
-
getPaths
Returns the $k$ shortest simple paths in increasing order of weight.- Specified by:
getPaths
in interfaceKShortestPathAlgorithm<V,
E> - Parameters:
startVertex
- source vertex of the calculated paths.endVertex
- target vertex of the calculated paths.k
- the number of shortest paths to return- Returns:
- list of disjoint paths between the start vertex and the end vertex
- Throws:
IllegalArgumentException
- if the graph does not contain the startVertex or the endVertexIllegalArgumentException
- if the startVertex and the endVertex are the same verticesIllegalArgumentException
- if the startVertex or the endVertex is null
-
resolvePaths
At the end of the search we have list of intermediate paths - not necessarily disjoint and may contain reversed edges. Here we go over all, removing overlapping edges and merging them to valid paths (from start to end). Finally, we sort them according to their weight.- Parameters:
startVertex
- the start vertexendVertex
- the end vertex- Returns:
- sorted list of disjoint paths from start vertex to end vertex.
-
buildPaths
After removing overlapping edges, each path is not necessarily connecting start to end vertex. Here we connect the path fragments to valid paths (from start to end).- Parameters:
startVertex
- the start vertexendVertex
- the end vertex- Returns:
- list of disjoint paths from start to end.
-
findValidEdges
private void findValidEdges()Iterate over all paths and remove all edges used an even number of times. The remaining edges forms the valid edge set, which is used in the buildPaths method to construct the k-shortest paths -
createGraphPath
-
getEdgeSource
-
getEdgeTarget
-
calculateShortestPath
Calculates the shortest paths for the current iteration. Path is not final; rather, it is intended to be used in a "post-production" phase (see resolvePaths method).- Parameters:
startVertex
- the start vertexendVertex
- the end vertex- Returns:
- the shortest path between start and end vertices.
-
transformGraph
Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a precedingcalculateShortestPath(V, V)
call.- Parameters:
previousPath
- the path found at the previous iteration.
-