Class BaseKDisjointShortestPathsAlgorithm<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.BaseKDisjointShortestPathsAlgorithm<V,E>
Type Parameters:
V - the graph vertex type
E - 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:
  1. Using some known shortest path algorithm (e.g. Dijkstra) to find the shortest path $P_1$ from source to target.
  2. For i = 2,...,$k$
  3.  Perform some graph transformations based on the previously found path
  4.  Find the shortest path $P_i$ from source to target
  5. Remove all overlapping edges to get $k$ disjoint paths.
The class implements the above procedure and resolves final paths (step 5) from the intermediate path results found in step 4. An extending class has to implement two methods: Currently known extensions are SuurballeKDisjointShortestPaths and BhandariKDisjointShortestPaths.
  • Field Details

    • workingGraph

      protected Graph<V,E> workingGraph
      Graph on which shortest paths are searched.
    • pathList

      protected List<List<E>> pathList
    • originalGraph

      protected Graph<V,E> originalGraph
    • validEdges

      private Set<E> validEdges
  • Constructor Details

  • Method Details

    • getPaths

      public 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 interface KShortestPathAlgorithm<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 endVertex
      IllegalArgumentException - if the startVertex and the endVertex are the same vertices
      IllegalArgumentException - if the startVertex or the endVertex is null
    • resolvePaths

      private 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 vertex
      endVertex - the end vertex
      Returns:
      sorted list of disjoint paths from start vertex to end vertex.
    • buildPaths

      private 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 vertex
      endVertex - 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(List<E> edgeList, V startVertex, V endVertex)
    • getEdgeSource

      private V getEdgeSource(E e)
    • getEdgeTarget

      private V getEdgeTarget(E e)
    • 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 vertex
      endVertex - the end vertex
      Returns:
      the shortest path between start and end vertices.
    • transformGraph

      protected abstract void transformGraph(List<E> previousPath)
      Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a preceding calculateShortestPath(V, V) call.
      Parameters:
      previousPath - the path found at the previous iteration.