Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

Class BhandariKDisjointShortestPaths<V,​E>

java.lang.Object
org.jgrapht.alg.shortestpath.BhandariKDisjointShortestPaths<V,​E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
KShortestPathAlgorithm<V,​E>
public class BhandariKDisjointShortestPaths<V,​E>
extends java.lang.Object
An implementation of Bhandari algorithm for finding $K$ edge-disjoint shortest paths. The algorithm determines the $k$ edge-disjoint shortest simple paths in increasing order of weight. Weights can be negative (but no negative cycle is allowed). Only directed simple graphs are allowed.

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

  • Bhandari, Ramesh 1999. Survivable networks: algorithms for diverse routing. 477. Springer. p. 46. ISBN 0-7923-8381-8.
  • Iqbal, F. and Kuipers, F. A. 2015. Disjoint Paths in Networks . Wiley Encyclopedia of Electrical and Electronics Engineering. 1–11.
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.

  • Constructor Summary

    Constructors 
    Constructor Description
    BhandariKDisjointShortestPaths​(Graph<V,​E> graph)
    Creates a new instance of the algorithm.

  • Method Summary

    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 Details

  • Constructor Details

    • BhandariKDisjointShortestPaths

      public BhandariKDisjointShortestPaths​(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 Details

    • 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