Package org.jgrapht.alg.shortestpath

Class SuurballeKDisjointShortestPaths<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    KShortestPathAlgorithm<V,​E>
    public class SuurballeKDisjointShortestPaths<V,​E>
extends java.lang.Object
    An implementation of Suurballe algorithm for finding K edge-disjoint shortest paths. The algorithm determines the k disjoint shortest simple paths in increasing order of weight. Only directed simple graphs are allowed.

    The algorithm is running k sequential Dijkstra iterations to find the shortest path at each step. Hence, yielding a complexity of k*O(Dijkstra).

    For further reference see Wikipedia page

    • Suurballe, J. W.; Tarjan, R. E. (1984), A quick method for finding shortest pairs of disjoint paths.
    Author:
    Assaf Mizrachi

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected Graph<V,​E> originalGraph  
      protected java.util.List<java.util.List<E>> pathList  
      protected Graph<V,​E> workingGraph
      Graph on which shortest paths are searched.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected GraphPath<V,​E> calculateShortestPath​(V startVertex, V endVertex)
      Calculates the shortest paths for the current iteration.
      java.util.List<GraphPath<V,​E>> getPaths​(V startVertex, V endVertex, int k)
      Returns the $k$ shortest simple paths in increasing order of weight.
      protected 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

    • Constructor Detail

      • SuurballeKDisjointShortestPaths

        public SuurballeKDisjointShortestPaths​(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

      • transformGraph

        protected 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.

      • calculateShortestPath

        protected 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.

      • 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