Package org.drip.graph.bellmanford

Class VertexRelaxationControl

java.lang.Object
org.drip.graph.bellmanford.VertexRelaxationControl
public class VertexRelaxationControl
extends java.lang.Object
VertexRelaxationControl controls the Vertexes to be relaxed in the Shortest Path Generation for a Directed Graph under the Bellman-Ford Algorithm. This happens by eliminating unnecessary Vertex Relaxations. 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

  • Constructor Summary

    Constructors
    Constructor Description
    VertexRelaxationControl​(java.util.Map<java.lang.String,​AugmentedVertex> augmentedVertexMap)
    VertexRelaxationControl Constructor

  • Method Summary

    Modifier and Type Method Description
    boolean relaxAndUpdateVertexes​(java.util.Map<java.lang.String,​AugmentedVertex> updatedAugmentedVertexMap)
    Relax and Update the Vertexes
    java.util.Map<java.lang.String,​java.lang.Double> vertexDistanceMap()
    Retrieve the Vertex Distance Map
    boolean vertexNeedsRelaxation​(java.lang.String vertexName)
    Indicate if the Vertex Needs a Relaxation
    java.util.Map<java.lang.String,​java.lang.Boolean> vertexRelaxationMap()
    Retrieve the Vertex Relaxation Map

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • VertexRelaxationControl

      public VertexRelaxationControl​(java.util.Map<java.lang.String,​AugmentedVertex> augmentedVertexMap) throws java.lang.Exception
      VertexRelaxationControl Constructor
      Parameters:
      augmentedVertexMap - The Augmented Vertex Map
      Throws:
      java.lang.Exception - Thrown if the Input is Invalid

  • Method Details

    • vertexRelaxationMap

      public java.util.Map<java.lang.String,​java.lang.Boolean> vertexRelaxationMap()
      Retrieve the Vertex Relaxation Map
      Returns:
      The Vertex Relaxation Map

    • vertexDistanceMap

      public java.util.Map<java.lang.String,​java.lang.Double> vertexDistanceMap()
      Retrieve the Vertex Distance Map
      Returns:
      The Vertex Distance Map

    • relaxAndUpdateVertexes

      public boolean relaxAndUpdateVertexes​(java.util.Map<java.lang.String,​AugmentedVertex> updatedAugmentedVertexMap)
      Relax and Update the Vertexes
      Parameters:
      updatedAugmentedVertexMap - The Updated Augmented Vertex Map
      Returns:
      TRUE - The Vertexes are Relaxed and Updated

    • vertexNeedsRelaxation

      public boolean vertexNeedsRelaxation​(java.lang.String vertexName)
      Indicate if the Vertex Needs a Relaxation
      Parameters:
      vertexName - The Vertex Name
      Returns:
      TRUE - The Vertex Needs a Relaxation