Package org.drip.graph.shortestpath

Class VertexAugmentor

java.lang.Object
org.drip.graph.shortestpath.VertexAugmentor
public class VertexAugmentor
extends java.lang.Object
VertexAugmentor augments and maintains the set of Path Vertexes. The References are:

  • Dijkstra, E. W. (1959): A Note on Two Problems in Connection with Graphs Numerische Mathematik 1 269-271
  • Felner, A. (2011): Position Paper: Dijkstra’s Algorithm versus Uniform Cost Search or a Case against Dijkstra’s Algorithm Proceedings of the 4th International Symposium on Combinatorial Search 47-51
  • Mehlhorn, K. W., and P. Sanders (2008): Algorithms and Data Structures: The Basic Toolbox Springer
  • Russell, S., and P. Norvig (2009): Artificial Intelligence: A Modern Approach 3rd Edition Prentice Hall
  • Wikipedia (2019): Dijkstra's Algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    VertexAugmentor​(java.lang.String sourceVertexName, boolean shortestPath, FHeuristic fHeuristic, java.util.Map<java.lang.String,​Vertex> vertexMap)
    VertexAugmentor Constructor

  • Method Summary

    Modifier and Type Method Description
    java.util.Map<java.lang.String,​AugmentedVertex> augmentedVertexMap()
    Retrieve the Map of Augmented Vertexes
    FHeuristic fHeuristic()
    Retrieve the F Heuristic
    Path generatePath​(java.lang.String destinationVertexName)
    Generate the Path to the Destination Vertex
    boolean initializeVertexNameSet​(java.util.Set<java.lang.String> vertexNameSet)
    Initialize the Set of Vertexes
    boolean setVertexProcessed​(java.lang.String augmentedVertexName)
    Set the Augmented Vertex as having been Processed
    boolean shortestPath()
    Indicate if the Shortest Path is Sought
    java.lang.String sourceVertexName()
    Retrieve the Source Vertex Name
    boolean updateAugmentedVertex​(Edge precedingEdge)
    Update the Augmented Vertex through the Preceding Vertex represented in the Preceding Edge
    java.util.Map<java.lang.String,​Vertex> vertexMap()
    Retrieve the Underlying Graph Vertex Map
    boolean vertexProcessed​(java.lang.String augmentedVertexName)
    Indicate if the Augmented Vertex has been Processed

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • VertexAugmentor

      public VertexAugmentor​(java.lang.String sourceVertexName, boolean shortestPath, FHeuristic fHeuristic, java.util.Map<java.lang.String,​Vertex> vertexMap) throws java.lang.Exception
      VertexAugmentor Constructor
      Parameters:
      sourceVertexName - The Source vertex Name
      shortestPath - TRUE - Shortest Path Sought
      fHeuristic - F Heuristic
      vertexMap - Underlying Graph Vertex Map
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • sourceVertexName

      public java.lang.String sourceVertexName()
      Retrieve the Source Vertex Name
      Returns:
      The Source Vertex Name

    • shortestPath

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

    • augmentedVertexMap

      public java.util.Map<java.lang.String,​AugmentedVertex> augmentedVertexMap()
      Retrieve the Map of Augmented Vertexes
      Returns:
      Map of Augmented Vertexes

    • fHeuristic

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

    • vertexMap

      public java.util.Map<java.lang.String,​Vertex> vertexMap()
      Retrieve the Underlying Graph Vertex Map
      Returns:
      The Underlying Graph Vertex Map

    • initializeVertexNameSet

      public boolean initializeVertexNameSet​(java.util.Set<java.lang.String> vertexNameSet)
      Initialize the Set of Vertexes
      Parameters:
      vertexNameSet - The Vertex Name Set
      Returns:
      TRUE - The Set of Vertexes successfully initialized

    • updateAugmentedVertex

      public boolean updateAugmentedVertex​(Edge precedingEdge)
      Update the Augmented Vertex through the Preceding Vertex represented in the Preceding Edge
      Parameters:
      precedingEdge - The Preceding Edge
      Returns:
      TRUE - Update of the Augmented Vertex is Successful

    • setVertexProcessed

      public boolean setVertexProcessed​(java.lang.String augmentedVertexName)
      Set the Augmented Vertex as having been Processed
      Parameters:
      augmentedVertexName - The Augmented Vertex Name
      Returns:
      TRUE - The Augmented Vertex is set as having been Processed

    • vertexProcessed

      public boolean vertexProcessed​(java.lang.String augmentedVertexName)
      Indicate if the Augmented Vertex has been Processed
      Parameters:
      augmentedVertexName - The Augmented Vertex Name
      Returns:
      TRUE - The Augmented Vertex has been Processed

    • generatePath

      public Path generatePath​(java.lang.String destinationVertexName)
      Generate the Path to the Destination Vertex
      Parameters:
      destinationVertexName - The Destination Vertex
      Returns:
      Path to the Destination Vertex