Package org.drip.graph.bellmanford

Class EdgePartitionGenerator

java.lang.Object

org.drip.graph.shortestpath.OptimalPathGenerator

org.drip.graph.bellmanford.EdgeRelaxationPathGenerator

org.drip.graph.bellmanford.EdgePartitionGenerator

Direct Known Subclasses:

BannisterEppsteinPathGenerator, YenEdgePartitionPathGenerator

public abstract class EdgePartitionGenerator
extends EdgeRelaxationPathGenerator

EdgePartitionGenerator generates the Shortest Path for a Directed Graph using the Bellman-Ford Algorithm with the 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

Method Summary

Modifier and Type	Method	Description
abstract 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

Method Details

edgePartition

public abstract EdgePartition edgePartition()

Retrieve the Edge Partition

Returns:

The Edge Partition