Package org.drip.graph.bellmanford

Class BannisterEppsteinPathGenerator

java.lang.Object

org.drip.graph.shortestpath.OptimalPathGenerator

org.drip.graph.bellmanford.EdgeRelaxationPathGenerator

org.drip.graph.bellmanford.EdgePartitionGenerator

org.drip.graph.bellmanford.BannisterEppsteinPathGenerator

public class BannisterEppsteinPathGenerator
extends EdgePartitionGenerator

BannisterEppsteinPathGenerator generates the Shortest Path for a Directed Graph using the Bellman-Ford Algorithm with the Bannister and Eppstein (2012) Edge Partitioning Scheme applied to improve the Worst-Case Behavior. The References are:

• Bang-Jensen, J., and G. Gutin (2008): Digraphs: Theory, Algorithms, and Applications 2^nd Edition Springer
• Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3^rd Edition MIT Press
• Kleinberg, J., and E. Tardos (2022): Algorithm Design 2^nd Edition Pearson
• Sedgewick, R. and K. Wayne (2011): Algorithms 4^th Edition Addison Wesley
• Wikipedia (2020): Bellman-Ford Algorithm https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_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
BannisterEppsteinPathGenerator(Directed<?> graph, boolean shortestPath, FHeuristic fHeuristic)	BannisterEppsteinPathGenerator Constructor

Method Summary

Modifier and Type	Method	Description
EdgePartition<?>	edgePartition()	Retrieve the Edge Partition

Methods inherited from class org.drip.graph.bellmanford.EdgeRelaxationPathGenerator

augmentVertexes

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

BannisterEppsteinPathGenerator

public BannisterEppsteinPathGenerator(Directed<?> graph,
boolean shortestPath,
FHeuristic fHeuristic)
                               throws java.lang.Exception

BannisterEppsteinPathGenerator 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

edgePartition

public EdgePartition<?> edgePartition()

Description copied from class: EdgePartitionGenerator

Retrieve the Edge Partition

Specified by:

edgePartition in class EdgePartitionGenerator

Returns:

The Edge Partition