API reference
Index
ConstrainedShortestPaths.CSPInstance
ConstrainedShortestPaths.CSPInstance
ConstrainedShortestPaths.ForwardCSPInstance
ConstrainedShortestPaths.basic_shortest_path
ConstrainedShortestPaths.compute_bounds
ConstrainedShortestPaths.generalized_a_star
ConstrainedShortestPaths.generalized_a_star
ConstrainedShortestPaths.generalized_a_star_with_threshold
ConstrainedShortestPaths.generalized_constrained_shortest_path
ConstrainedShortestPaths.generalized_constrained_shortest_path_with_threshold
ConstrainedShortestPaths.resource_shortest_path
ConstrainedShortestPaths.stochastic_routing_shortest_path
ConstrainedShortestPaths.stochastic_routing_shortest_path_with_threshold
Docstrings
ConstrainedShortestPaths.CSPInstance
— Typestruct 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 pathorigin_vertex::Any
: origin vertex of pathdestination_vertex::Any
: destination vertex of pathorigin_forward_resource::Any
: forward resource at the origin vertexdestination_backward_resource::Any
: backward resource at the destination vertexcost_function::Any
: cost functionforward_functions::AbstractMatrix
: forward functions along edgesbackward_functions::AbstractMatrix
: backward functions along edgesis_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 ittopological_ordering::Vector
: precomputed topological ordering of useful vertices, from destination to source
ConstrainedShortestPaths.CSPInstance
— MethodCSPInstance(
;
graph,
origin_vertex,
destination_vertex,
origin_forward_resource,
destination_backward_resource,
cost_function,
forward_functions,
backward_functions
)
Constructor for CSPInstance
.
ConstrainedShortestPaths.ForwardCSPInstance
— Typestruct ForwardCSPInstance{T, G<:Graphs.AbstractGraph{T}, FR, C, FF<:(AbstractMatrix)} <: ConstrainedShortestPaths.AbstractCSPInstance
Fields
graph::Graphs.AbstractGraph
: acyclic digraph in which to compute the shortest pathorigin_vertex::Any
: origin vertex of pathdestination_vertex::Any
: destination vertex of pathorigin_forward_resource::Any
: forward resource at the origin vertexcost_function::Any
: cost functionforward_functions::AbstractMatrix
: forward functions along edgesis_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 ittopological_ordering::Vector
: precomputed topological ordering of useful vertices, from destination to source
ConstrainedShortestPaths.basic_shortest_path
— Methodbasic_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 verticesi
andj
along edge(i, j)
ofgraph
.
Returns
p_star::Vector{Int}
: optimal path found.c_star::Float64
: length of pathp_star
.
ConstrainedShortestPaths.compute_bounds
— Methodcompute_bounds(
instance::CSPInstance;
kwargs...
) -> Dict{Int64}
Compute backward bounds of instance (see Computing bounds).
ConstrainedShortestPaths.generalized_a_star
— Methodgeneralized_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
).
ConstrainedShortestPaths.generalized_a_star
— Methodgeneralized_a_star(
instance::ConstrainedShortestPaths.ForwardCSPInstance;
kwargs...
) -> NamedTuple{(:p_star, :c_star), <:Tuple{Vector, Any}}
Label dominance dynamic programming without bounding.
ConstrainedShortestPaths.generalized_a_star_with_threshold
— Methodgeneralized_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.
ConstrainedShortestPaths.generalized_constrained_shortest_path
— Methodgeneralized_constrained_shortest_path(
instance::CSPInstance;
kwargs...
) -> NamedTuple{(:p_star, :c_star), <:Tuple{Vector, Any}}
Compute the shortest path of instance
.
ConstrainedShortestPaths.generalized_constrained_shortest_path_with_threshold
— Methodgeneralized_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
ConstrainedShortestPaths.resource_shortest_path
— Methodresource_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 verticesi
andj
along edge(i, j)
ofg
.costmx::Array{Float64, 3}
:cost_mx[i, j, k]
corresponds to the resource cost of edge(i, j)
for thek
th resource constraint.
Returns
p_star::Vector{Int}
: optimal path found.c_star::Float64
: length of pathp_star
.
ConstrainedShortestPaths.stochastic_routing_shortest_path
— Methodstochastic_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 betweeni
andj
.delays
:delays[i, ω]
corresponds to delay ofi
for scenarioω
.
Returns
p_star::Vector{Int}
: optimal path found.c_star::Float64
: length of pathp_star
.
ConstrainedShortestPaths.stochastic_routing_shortest_path_with_threshold
— Functionstochastic_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
.