Class 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 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:
    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.
    • 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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • workingGraph

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

        protected java.util.List<java.util.List<E>> pathList
      • originalGraph

        protected Graph<V,​E> originalGraph
      • validEdges

        private java.util.Set<E> validEdges
    • 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 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:
        java.lang.IllegalArgumentException - if the graph does not contain the startVertex or the endVertex
        java.lang.IllegalArgumentException - if the startVertex and the endVertex are the same vertices
        java.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 vertex
        endVertex - 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 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​(java.util.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​(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 preceding calculateShortestPath(V, V) call.
        Parameters:
        previousPath - the path found at the previous iteration.