Shortest Path Solver

FlowGenerator.ShortestPathSolver.LabelType
struct 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.
source
FlowGenerator.ShortestPathSolver.ShortestPathGeneratorType
mutable 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.
source
FlowGenerator.ShortestPathSolver.ShortestPathSolutionType
mutable 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.
source
FlowGenerator.ShortestPathSolver.generate_shortest_pathMethod
generate_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.
source
FlowGenerator.ShortestPathSolver.generate_shortest_pathMethod
generate_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.
source
FlowGenerator.ShortestPathSolver.get_min_unit_flow_costMethod
get_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.
source
FlowGenerator.ShortestPathSolver.get_min_unit_flow_pathMethod
get_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 the arc.
source