Package org.drip.graph.bellmanford

Class JohnsonPathGenerator

java.lang.Object

org.drip.graph.shortestpath.OptimalPathGenerator

org.drip.graph.bellmanford.JohnsonPathGenerator

public class JohnsonPathGenerator
extends OptimalPathGenerator

JohnsonPathGenerator generates the Shortest Path for a Directed Graph using the Johnson Algorithm. The References are:

• Black, P. E. (2004): Johnson's Algorithm https://xlinux.nist.gov/dads/HTML/johnsonsAlgorithm.html
• Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3^rd Edition MIT Press
• Johnson, D. B. (1977): Efficient Algorithms for Shortest Paths in Sparse Networks Journal of the ACM 24 (1) 1-13
• Suurballe, J. W. (1974): Disjoint Paths in a Network Networks 14 (2) 125-145
• Wikipedia (2019): Johnson's Algorithm https://en.wikipedia.org/wiki/Johnson%27s_algorithm

• Module = Computational Core Module
• Library = Graph Algorithm Library
• Project = Graph Optimization and Tree Construction Algorithms
• Package = Bellman Ford Shortest Path Family

Author:

Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor	Description
JohnsonPathGenerator(DirectedGraph graph, boolean shortestPath, FHeuristic fHeuristic)	JohnsonPathGenerator Constructor

Method Summary

Modifier and Type	Method	Description
VertexAugmentor	augmentVertexes(java.lang.String sourceVertexName)	Generate the Augmented Vertex Suite starting from the Source Vertex

Methods inherited from class org.drip.graph.shortestpath.OptimalPathGenerator

fHeuristic, graph, shortestPath, singlePair, singleSource

Methods inherited from class java.lang.Object

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

Constructor Details

JohnsonPathGenerator

public JohnsonPathGenerator(DirectedGraph graph,
boolean shortestPath,
FHeuristic fHeuristic)
                     throws java.lang.Exception

JohnsonPathGenerator Constructor

Parameters:

graph - Graph underlying the Path Generator

shortestPath - TRUE - Shortest Path Sought

fHeuristic - F Heuristic

Throws:

java.lang.Exception - Thrown if the Inputs are Invalid

Method Details

augmentVertexes

public VertexAugmentor augmentVertexes(java.lang.String sourceVertexName)

Description copied from class: OptimalPathGenerator

Generate the Augmented Vertex Suite starting from the Source Vertex

Specified by:

augmentVertexes in class OptimalPathGenerator

Parameters:

sourceVertexName - The Source Vertex Name

Returns:

The Augmented Vertex Suite