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

basic_shortest_path(
    graph::Graphs.AbstractGraph{T},
    s,
    t;
    ...
) -> NamedTuple{(:p_star, :c_star), <:Tuple{Vector, Any}}
basic_shortest_path(
    graph::Graphs.AbstractGraph{T},
    s,
    t,
    distmx::AbstractMatrix;
    bounding
) -> NamedTuple{(:p_star, :c_star), <:Tuple{Vector, Any}}

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), <:Tuple{Vector, 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), <:Tuple{Vector, Any}}

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_constrained_shortest_path(
    instance::CSPInstance;
    kwargs...
) -> NamedTuple{(:p_star, :c_star), <:Tuple{Vector, Any}}

Compute the shortest path of instance.

generalized_constrained_shortest_path_with_threshold(
    instance::CSPInstance{T, G<:Graphs.AbstractGraph},
    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
) -> NamedTuple{(:p_star, :c_star), <:Tuple{Vector, Any}}

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,
    delays::AbstractMatrix;
    ...
) -> NamedTuple{(:p_star, :c_star), <:Tuple{Vector, Any}}
stochastic_routing_shortest_path(
    graph::Graphs.AbstractGraph{T},
    slacks::AbstractMatrix,
    delays::AbstractMatrix,
    λ_values::AbstractVector;
    origin_vertex,
    destination_vertex,
    bounding
) -> NamedTuple{(:p_star, :c_star), <:Tuple{Vector, Any}}

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,
    slacks::AbstractMatrix,
    delays::AbstractMatrix;
    ...
)
stochastic_routing_shortest_path_with_threshold(
    graph::Graphs.AbstractGraph,
    slacks::AbstractMatrix,
    delays::AbstractMatrix,
    λ_values::AbstractVector;
    threshold
)

Compute stochastic routing shortest path between first and last vertices of graph graph.