Package org.drip.graph.bellmanford

Class YenEdgePartitionPathGenerator

java.lang.Object

org.drip.graph.shortestpath.OptimalPathGenerator

org.drip.graph.bellmanford.EdgeRelaxationPathGenerator

org.drip.graph.bellmanford.EdgePartitionGenerator

org.drip.graph.bellmanford.YenEdgePartitionPathGenerator

public class YenEdgePartitionPathGenerator
extends EdgePartitionGenerator

YenEdgePartitionPathGenerator generates the Shortest Path for a Directed Graph using the Bellman-Ford Algorithm with the Yen (1970) 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
YenEdgePartitionPathGenerator(Directed<?> graph, boolean shortestPath, FHeuristic fHeuristic)	YenEdgePartitionPathGenerator 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

YenEdgePartitionPathGenerator

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

YenEdgePartitionPathGenerator 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