API reference
Index
ConstrainedShortestPaths.CSPInstance
ConstrainedShortestPaths.PiecewiseLinear
ConstrainedShortestPaths.PiecewiseLinear
Base.:+
ConstrainedShortestPaths.basic_shortest_path
ConstrainedShortestPaths.closest_break_point
ConstrainedShortestPaths.compose
ConstrainedShortestPaths.compute_bounds
ConstrainedShortestPaths.generalized_a_star
ConstrainedShortestPaths.generalized_a_star_with_threshold
ConstrainedShortestPaths.generalized_constrained_shortest_path
ConstrainedShortestPaths.generalized_constrained_shortest_path_with_threshold
ConstrainedShortestPaths.get_points
ConstrainedShortestPaths.get_x
ConstrainedShortestPaths.intersection
ConstrainedShortestPaths.meet
ConstrainedShortestPaths.resource_shortest_path
ConstrainedShortestPaths.stochastic_routing_shortest_path
Docstrings
ConstrainedShortestPaths.CSPInstance
— TypeCSPInstance{G,FR,BR,C,FF,BF}
Attributes
graph
origin_forward_resource
destination_backward_resource
cost_function
forward_functions
backward_functions
ConstrainedShortestPaths.PiecewiseLinear
— TypePiecewiseLinear
Type used to represent increasing piecewise linear functions, with starting slope 0.
Attributes
final_slope::Float64
: (positive) slope of the last linear piece.break_x::Vector{Float64}
: (ordered) list of all break points x-coordinates.break_y::Vector{Float64}
: (non decreasing) list of all break points y-coordinates corresponding tobreak_x
elementwise.
ConstrainedShortestPaths.PiecewiseLinear
— Method(f)(x)
Returns f(x).
Base.:+
— Method+(f1, f2)
Return a PiecewiseLinear corresponding to f1 + f2.
ConstrainedShortestPaths.basic_shortest_path
— Methodbasic_shortest_path(graph, distmx=weights(graph), s, t)
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.closest_break_point
— Methodclosest_break_point(break_x, x)
Find the index of the closest break point from x. (at its right i fright=true else at its left)
ConstrainedShortestPaths.compose
— Methodcompose(f1, f2)
Return a PiecewiseLinear corresponding to f1 ∘ f2 ! only support functions with only one break point and final slope 1
ConstrainedShortestPaths.compute_bounds
— Methodcompute_bounds(instance)
Compute backward bounds of instance (see Computing bounds).
ConstrainedShortestPaths.generalized_a_star
— Methodgeneralized_a_star(instance, s, t, bounds)
Perform generalized A star algorithm on instnace using bounds (see Generalized A^\star
).
ConstrainedShortestPaths.generalized_a_star_with_threshold
— Methodgeneralized_a_star_with_threshold(instance, bounds, threshold)
Compute all paths below threshold.
ConstrainedShortestPaths.generalized_constrained_shortest_path
— Methodgeneralized_constrained_shortest_path(instance, s, t)
Compute the shortest path of instance
.
ConstrainedShortestPaths.generalized_constrained_shortest_path_with_threshold
— Methodgeneralized_constrained_shortest_path(instance)
Compute shortest path between first and last nodes of instance
ConstrainedShortestPaths.get_points
— Methodget_points(f1, f2, i1, i2)
Return break point i1 of f1 and break point i2 of f2. If i1 or i2 are out of range, return a border (x, f(x)).
ConstrainedShortestPaths.get_x
— Methodget_x(f, i; x_max=1000)
Return x coordinate of breakpoint i. If i is out of range, return xmax
ConstrainedShortestPaths.intersection
— Methodintersection(f1, f2, i1, i2)
Return -1 if there is no intersection else the x coordinate of the intersection.
ConstrainedShortestPaths.meet
— Methodmeet(f1, f2)
Compute the minimum of two PiecewiseLinear functions Return a PiecewiseLinear f, such that ∀x, f(x) = min(f1(x), f2(x)).
ConstrainedShortestPaths.resource_shortest_path
— Methodresource_shortest_path(g, s, t, distmx, costmx)
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, slacks, delays)
Compute stochastic routing shortest path between first and last 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
.