Package org.drip.graph.shortestpath

Class OptimalPathGenerator

java.lang.Object
org.drip.graph.shortestpath.OptimalPathGenerator
Direct Known Subclasses:
DijkstraPathGenerator, EdgeRelaxationPathGenerator, JohnsonPathGenerator
public abstract class OptimalPathGenerator
extends java.lang.Object
OptimalPathGenerator contains the Stubs for generating the Optimal (Shortest/Longest) Path on a Directed Graph. The References are:

  • Bang-Jensen, J., and G. Gutin (2008): Digraphs: Theory, Algorithms, and Applications 2nd Edition Springer
  • Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3rd Edition MIT Press
  • Kleinberg, J., and E. Tardos (2022): Algorithm Design 2nd Edition Pearson
  • Sedgewick, R. and K. Wayne (2011): Algorithms 4th Edition Addison Wesley
  • Wikipedia (2020): Bellman-Ford Algorithm https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm




Author:
Lakshmi Krishnamurthy

  • Method Summary

    Modifier and Type Method Description
    abstract VertexAugmentor augmentVertexes​(java.lang.String sourceVertexName)
    Generate the Augmented Vertex Suite starting from the Source Vertex
    FHeuristic fHeuristic()
    Retrieve the F Heuristic
    DirectedGraph graph()
    Retrieve the Graph underlying the Path Generator
    boolean shortestPath()
    Indicate if the Shortest Path is Sought
    Path singlePair​(java.lang.String sourceVertexName, java.lang.String destinationVertexName)
    Generate the Shortest Path from the Source to the Destination
    java.util.List<Path> singleSource​(java.lang.String sourceVertexName)
    Generate the List of the Shortest Path from the Source to all Destinations

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • graph

      public DirectedGraph graph()
      Retrieve the Graph underlying the Path Generator
      Returns:
      Graph underlying the Path Generator

    • shortestPath

      public boolean shortestPath()
      Indicate if the Shortest Path is Sought
      Returns:
      TRUE - Shortest Path Sought

    • fHeuristic

      public FHeuristic fHeuristic()
      Retrieve the F Heuristic
      Returns:
      The F Heuristic

    • augmentVertexes

      public abstract VertexAugmentor augmentVertexes​(java.lang.String sourceVertexName)
      Generate the Augmented Vertex Suite starting from the Source Vertex
      Parameters:
      sourceVertexName - The Source Vertex Name
      Returns:
      The Augmented Vertex Suite

    • singlePair

      public Path singlePair​(java.lang.String sourceVertexName, java.lang.String destinationVertexName)
      Generate the Shortest Path from the Source to the Destination
      Parameters:
      sourceVertexName - Source Vertex Name
      destinationVertexName - Destination Vertex Name
      Returns:
      Shortest Path from the Source to the Destination

    • singleSource

      public java.util.List<Path> singleSource​(java.lang.String sourceVertexName)
      Generate the List of the Shortest Path from the Source to all Destinations
      Parameters:
      sourceVertexName - Source Vertex Name
      Returns:
      List of the Shortest Path from the Source to all Destinations