API reference

struct CSPInstance{T, G<:Graphs.AbstractGraph{T}, FR, BR, C, FF<:(AbstractMatrix), BF<:(AbstractMatrix)} <: ConstrainedShortestPaths.AbstractCSPInstance

Fields

• graph::Graphs.AbstractGraph: acyclic digraph in which to compute the shortest path

• origin_vertex::Any: origin vertex of path

• destination_vertex::Any: destination vertex of path

• origin_forward_resource::Any: forward resource at the origin vertex

• destination_backward_resource::Any: backward resource at the destination vertex

• cost_function::Any: cost function

• forward_functions::AbstractMatrix: forward functions along edges

• backward_functions::AbstractMatrix: backward functions along edges

• is_useful::BitVector: bit vector indicating if a vertices will be useful in the path computation, i.e. if there is a path from origin to destination that goes through it

• topological_ordering::Vector: precomputed topological ordering of useful vertices, from destination to source

CSPInstance(
;
    graph,
    origin_vertex,
    destination_vertex,
    origin_forward_resource,
    destination_backward_resource,
    cost_function,
    forward_functions,
    backward_functions
)

Constructor for CSPInstance.

struct ForwardCSPInstance{T, G<:Graphs.AbstractGraph{T}, FR, C, FF<:(AbstractMatrix)} <: ConstrainedShortestPaths.AbstractCSPInstance

Fields

• graph::Graphs.AbstractGraph: acyclic digraph in which to compute the shortest path

• origin_vertex::Any: origin vertex of path

• destination_vertex::Any: destination vertex of path

• origin_forward_resource::Any: forward resource at the origin vertex

• cost_function::Any: cost function

• forward_functions::AbstractMatrix: forward functions along edges

• is_useful::BitVector: bit vector indicating if a vertices will be useful in the path computation, i.e. if there is a path from origin to destination that goes through it

• topological_ordering::Vector: precomputed topological ordering of useful vertices, from destination to source

struct StochasticBackwardFunction

Fields

• slacks::Vector{Float64}: arc slack for each scenario

• intrinsic_delays::Vector{Float64}: intrinsic delay for each scenario of arc head

• λ_value::Float64: dual variable of arc head

struct StochasticBackwardResource{is_convex}

Fields

• g::Vector{PiecewiseLinearFunctions.PiecewiseLinearFunction{Float64}}: piecewise linear function for each scenario, take as input propagated delay and outputs total delay of partail path

struct StochasticForwardFunction

Fields

• slacks::Vector{Float64}: arc slack for each scenario

• intrinsic_delays::Vector{Float64}: intrinsic delay for each scenario of arc head

• λ_value::Float64: dual variable of arc tail

struct StochasticForwardResource

Fields

• path_cost::Float64: partial cost of the associated path (not counting task at end of path)

• delays::Vector{Float64}: current task (end of path) delay for each scenario

basic_shortest_path(
    graph::Graphs.AbstractGraph{T},
    s,
    t;
    ...
) -> Union{NamedTuple{(:p_star, :c_star, :info, :bounds), <:Tuple{Vector{Int64}, Any, @NamedTuple{nb_cuts_with_bounds::Int64, nb_cuts_with_dominance::Int64}, Dict{Int64, Float64}}}, NamedTuple{(:p_star, :c_star, :info), <:Tuple{Vector{Int64}, Any, @NamedTuple{nb_cuts_with_dominance::Int64}}}}
basic_shortest_path(
    graph::Graphs.AbstractGraph{T},
    s,
    t,
    distmx::AbstractMatrix;
    bounding
) -> Union{NamedTuple{(:p_star, :c_star, :info, :bounds), <:Tuple{Vector{Int64}, Any, @NamedTuple{nb_cuts_with_bounds::Int64, nb_cuts_with_dominance::Int64}, Dict{Int64, Float64}}}, NamedTuple{(:p_star, :c_star, :info), <:Tuple{Vector{Int64}, Any, @NamedTuple{nb_cuts_with_dominance::Int64}}}}

Compute shortest path between vertices s and t of graph graph.

Arguments

• graph::AbstractGraph: acyclic directed graph.
• distmx::AbstractMatrix: distmx[i, j] corresponds to the distance between vertices i and j along edge (i, j) of graph.

Returns

• p_star::Vector{Int}: optimal path found.
• c_star::Float64: length of path p_star.

compute_bounds(
    instance::CSPInstance;
    kwargs...
) -> Dict{Int64}

Compute backward bounds of instance (see Computing bounds).

generalized_a_star(
    instance::CSPInstance,
    bounds;
    kwargs...
) -> NamedTuple{(:p_star, :c_star, :info, :bounds), <:Tuple{Vector, Any, @NamedTuple{nb_cuts_with_bounds::Int64, nb_cuts_with_dominance::Int64}, Any}}

Perform generalized A star algorithm on instnace using bounds (see Generalized A^\star).

generalized_a_star(
    instance::ConstrainedShortestPaths.ForwardCSPInstance;
    kwargs...
) -> NamedTuple{(:p_star, :c_star, :info), <:Tuple{Vector, Any, @NamedTuple{nb_cuts_with_dominance::Int64}}}

Label dominance dynamic programming without bounding.

generalized_a_star_with_threshold(
    instance::CSPInstance,
    bounds,
    threshold::Float64;
    kwargs...
) -> @NamedTuple{p_star::Vector{Vector{Int64}}, c_star::Vector{Float64}}

Compute all paths below threshold.

generalized_a_star_with_threshold(
    instance::ConstrainedShortestPaths.ForwardCSPInstance,
    threshold::Float64;
    kwargs...
) -> @NamedTuple{p_star::Vector{Vector{Int64}}, c_star::Vector{Float64}}

Compute all paths below threshold.

generalized_constrained_shortest_path(
    instance::CSPInstance;
    kwargs...
) -> NamedTuple{(:p_star, :c_star, :info, :bounds), <:Tuple{Vector, Any, @NamedTuple{nb_cuts_with_bounds::Int64, nb_cuts_with_dominance::Int64}, Dict{Int64}}}

Compute the shortest path of instance.

generalized_constrained_shortest_path_with_threshold(
    instance::CSPInstance,
    threshold::Float64;
    kwargs...
) -> @NamedTuple{p_star::Vector{Vector{Int64}}, c_star::Vector{Float64}}

Compute shortest path between first and last nodes of instance

resource_shortest_path(
    graph::Graphs.AbstractGraph{T},
    s,
    t,
    max_costs::AbstractVector,
    distmx::AbstractMatrix,
    costmx::Array{Float64, 3};
    bounding
) -> Union{@NamedTuple{p_star::Vector{Int64}, c_star::Float64, info::@NamedTuple{nb_cuts_with_dominance::Int64}}, @NamedTuple{p_star::Vector{Int64}, c_star::Float64, info::@NamedTuple{nb_cuts_with_bounds::Int64, nb_cuts_with_dominance::Int64}, bounds::Dict{Int64, ConstrainedShortestPaths.RSPResource}}}

Compute resource contrained shortest path between vertices s and t of graph g.

Arguments

• g::AbstractGraph: acyclic directed graph.
• max_costs::AbstractVector: list of upper bounds for each resource constraint.
• distmx::AbstractMatrix: distmx[i, j] corresponds to the distance between vertices i and j along edge (i, j) of g.
• costmx::Array{Float64, 3}: cost_mx[i, j, k] corresponds to the resource cost of edge (i, j) for the kth resource constraint.

Returns

• p_star::Vector{Int}: optimal path found.
• c_star::Float64: length of path p_star.

stochastic_routing_shortest_path(
    graph::Graphs.AbstractGraph{T},
    slacks::AbstractMatrix,
    intrinsic_delays::AbstractMatrix;
    ...
) -> Union{@NamedTuple{p_star::Vector{Int64}, c_star::Float64, info::@NamedTuple{nb_cuts_with_dominance::Int64}}, NamedTuple{(:p_star, :c_star, :info, :bounds), <:Tuple{Vector{Int64}, Float64, @NamedTuple{nb_cuts_with_bounds::Int64, nb_cuts_with_dominance::Int64}, Dict{Int64, ConstrainedShortestPaths.StochasticBackwardResource{is_convex}} where is_convex}}}
stochastic_routing_shortest_path(
    graph::Graphs.AbstractGraph{T},
    slacks::AbstractMatrix,
    intrinsic_delays::AbstractMatrix,
    λ_values::AbstractVector;
    origin_vertex,
    destination_vertex,
    bounding,
    use_convex_resources
) -> Union{@NamedTuple{p_star::Vector{Int64}, c_star::Float64, info::@NamedTuple{nb_cuts_with_dominance::Int64}}, NamedTuple{(:p_star, :c_star, :info, :bounds), <:Tuple{Vector{Int64}, Float64, @NamedTuple{nb_cuts_with_bounds::Int64, nb_cuts_with_dominance::Int64}, Dict{Int64, ConstrainedShortestPaths.StochasticBackwardResource{is_convex}} where is_convex}}}

Compute stochastic routing shortest path between origin_vertex and destination_vertex vertices of graph graph.

Arguments

• graph::AbstractGraph: acyclic directed graph.
• slacks: slacks[i, j] corresponds to the time slack between i and j.
• delays: delays[i, ω] corresponds to delay of i for scenario ω.

Returns

• p_star::Vector{Int}: optimal path found.
• c_star::Float64: length of path p_star.

stochastic_routing_shortest_path_with_threshold(
    graph::Graphs.AbstractGraph{T},
    slacks::AbstractMatrix,
    delays::AbstractMatrix;
    ...
)
stochastic_routing_shortest_path_with_threshold(
    graph::Graphs.AbstractGraph{T},
    slacks::AbstractMatrix,
    delays::AbstractMatrix,
    λ_values::AbstractVector;
    origin_vertex,
    destination_vertex,
    bounding,
    use_convex_resources,
    threshold
)

Threshold version of stochastic_routing_shortest_path.