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 java.lang.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
andBhandariKDisjointShortestPaths
.
-
-
Field Summary
Fields Modifier and Type Field Description protected Graph<V,E>
originalGraph
protected java.util.List<java.util.List<E>>
pathList
private java.util.Set<E>
validEdges
protected Graph<V,E>
workingGraph
Graph on which shortest paths are searched.
-
Constructor Summary
Constructors Constructor Description BaseKDisjointShortestPathsAlgorithm(Graph<V,E> graph)
Creates a new instance of the algorithm
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description private java.util.List<GraphPath<V,E>>
buildPaths(V startVertex, V endVertex)
After removing overlapping edges, each path is not necessarily connecting start to end vertex.protected abstract GraphPath<V,E>
calculateShortestPath(V startVertex, V endVertex)
Calculates the shortest paths for the current iteration.private GraphPath<V,E>
createGraphPath(java.util.List<E> edgeList, V startVertex, V endVertex)
private void
findValidEdges()
Iterate over all paths and remove all edges used an even number of times.private V
getEdgeSource(E e)
private V
getEdgeTarget(E e)
java.util.List<GraphPath<V,E>>
getPaths(V startVertex, V endVertex, int k)
Returns the $k$ shortest simple paths in increasing order of weight.private java.util.List<GraphPath<V,E>>
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(java.util.List<E> previousPath)
Prepares the working graph for next iteration.
-
-
-
Constructor Detail
-
BaseKDisjointShortestPathsAlgorithm
public BaseKDisjointShortestPathsAlgorithm(Graph<V,E> graph)
Creates a new instance of the algorithm- Parameters:
graph
- graph on which shortest paths are searched.- Throws:
java.lang.IllegalArgumentException
- if the graph is null.java.lang.IllegalArgumentException
- if the graph is undirected.java.lang.IllegalArgumentException
- if the graph is not simple.
-
-
Method Detail
-
getPaths
public java.util.List<GraphPath<V,E>> getPaths(V startVertex, V endVertex, int k)
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:
java.lang.IllegalArgumentException
- if the graph does not contain the startVertex or the endVertexjava.lang.IllegalArgumentException
- if the startVertex and the endVertex are the same verticesjava.lang.IllegalArgumentException
- if the startVertex or the endVertex is null
-
resolvePaths
private java.util.List<GraphPath<V,E>> 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. 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
private java.util.List<GraphPath<V,E>> buildPaths(V startVertex, V endVertex)
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
private GraphPath<V,E> createGraphPath(java.util.List<E> edgeList, V startVertex, V endVertex)
-
calculateShortestPath
protected abstract GraphPath<V,E> calculateShortestPath(V startVertex, V endVertex)
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
protected abstract void transformGraph(java.util.List<E> previousPath)
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.
-
-