Shortest Path Solver
FlowGenerator.ShortestPathSolver.Label
— Typestruct Label
Represents a label in the shortest path computation.
Fields
value::Float64
: The cost to reach the node this label is associated with.entering_arc::Arc
: The arc through which this node was reached.min_hops::Int
: The minimum number of arcs required to generate this label.
FlowGenerator.ShortestPathSolver.ShortestPathGenerator
— Typemutable struct ShortestPathGenerator
A structure to accelerate the shortest path computation in networks by reusing a precomputed topologically sorted list of arcs and updating the solution object across calls.
Storing the pre-sorted list of arcs is particularly beneficial when shortest path computations are frequently repeated with varying costs, as in the pricing solution of column generation for large-scale problems.
Fields
top_sorted_arc_list::Vector{Arc}
: List of arcs already sorted by topological order.source::Vertex
: Source vertex for the shortest path computation.sink::Vertex
: Sink (destination) vertex for the shortest path computation.solution::ShortestPathSolution
: Reusable object that holds the current shortest path solution. Reusing the solution object avoids inneficiencies due to memory allocation in huge problems.
FlowGenerator.ShortestPathSolver.ShortestPathSolution
— Typemutable struct ShortestPathSolution
Stores the state necessary for representing a set of solutions of a shortest path computation.
Fields
forward_vertex_to_label::IndexedMap{Vertex,Label}
: Mapping from vertices to labels for forward search from source to each vertex.backward_vertex_to_label::IndexedMap{Vertex,Label}
: Mapping from vertices to labels for backward search from sink to each vertex.arc_to_cost::IndexedMap{Arc,Float64}
: Mapping from arcs to their associated costs.is_hyper_graph::Bool
: Flag indicating if the solution is for a hypergraph. In case this is true, no backward computation has been done.
Constructor
ShortestPathSolution(network::Network)
: Initializes the solution with default labels and inf costs for a given network.
FlowGenerator.ShortestPathSolver.build_shortest_path_generator
— Methodbuild_shortest_path_generator(network::Network, source::Vertex, sink::Vertex) -> ShortestPathGenerator
Constructs a ShortestPathGenerator
instance by creating a topologically sorted list of arcs from the network and initializing an empty shortest path solution.
FlowGenerator.ShortestPathSolver.generate_shortest_path
— Methodgenerate_shortest_path(network::Network, arc_to_cost::AbstractDict; solver::ShortestPathGenerator) -> ShortestPathSolution
Generates the shortest path solution for a given network using a specific ShortestPathGenerator.
Returns
ShortestPathSolution
: The shortest path solution found by the solver.
FlowGenerator.ShortestPathSolver.generate_shortest_path
— Methodgenerate_shortest_path(network::Network, source::Vertex, sink::Vertex, arc_to_cost::AbstractDict) -> ShortestPathSolution
Generates the shortest path solution for a given network from a source to a sink, using specific arc costs. Builds a ShortestPathGenerator internally.
Returns
ShortestPathSolution
: The shortest path solution found by the solver.
FlowGenerator.ShortestPathSolver.get_min_unit_flow_cost
— Methodget_min_unit_flow_cost(solution::ShortestPathSolution, arc::Arc) -> Float64
Calculate the minimum flow cost in a path where the flow on arc
is one unit. This function is not compatible with hyper-graphs.
Returns
Float64
: The minimum unit flow cost for the specified arc.
FlowGenerator.ShortestPathSolver.get_min_unit_flow_path
— Methodget_min_unit_flow_path(solution::ShortestPathSolution, arc::Arc) -> Path
Obtain the path with the minimum unit flow cost for a given arc
. This function does not support hyper-graphs and will throw an error if used in such context.
Returns
Path
: The path corresponding to the minimum unit flow cost of thearc
.
FlowGenerator.ShortestPathSolver.get_optimal_path
— Methodget_optimal_path(solution::ShortestPathSolution, sink::Vertex) -> Path
Retrieve the optimal path from the source to the specified sink vertex using the shortest path solution data.
FlowGenerator.ShortestPathSolver.get_optimal_value_from_source
— Methodget_optimal_value_from_source(solution::ShortestPathSolution, vertex::Vertex) -> Float64
Return the optimal value (cost) of reaching a specified vertex from the source vertex using the shortest path solution data.