Module routing 

Shortest-path routing over a Graph.

Structs

LagrangianRoute

Outcome of the Lagrangian constrained-shortest-path solver: a feasible path, its true cost/resource, the best dual lower bound on the optimal cost (cost == lower_bound proves optimality), the multiplier that produced it and the number of Dijkstra runs spent.

ParetoRoute

A Pareto-optimal route found by pareto_paths. edges holds the input-order indices of the edges actually traversed, so callers can recover attributes/geometry exactly even across parallel edges.

Route

A route as node path plus the input-order indices of the edges traversed (so callers can recover attributes/geometry, parallel edges included).

Functions

csp_lagrangian

Constrained shortest path by Lagrangian relaxation (the LARAC algorithm): minimize cost subject to resource <= budget, dualizing the constraint so each iteration is a plain Dijkstra on cost + lambda * resource. A binary search on the two support paths (cheapest-infeasible and feasible-so-far) drives lambda to the maximizer of the dual, which takes few iterations and scales to graphs where exact label-setting is slow.

csr_edge_order

Input-edge index occupying each CSR slot of the graph that Graph::from_edges builds from from (it replays the same construction order).

dijkstra

Dijkstra single-source shortest distances. Returns a vector of length n_nodes; unreachable nodes are f64::INFINITY.

distance_matrix

Row-major shortest-distance matrix from each source to each target.

k_shortest_paths

Yen’s algorithm for the k loopless shortest paths from source to target. Returns up to k routes in increasing cost order; Yen operates on the simple-graph abstraction where parallel edges collapse to the minimum weight, so each route’s edges are those minimum-weight edges.

pareto_paths

Bicriteria shortest paths from source to target by label-setting (Martins’ algorithm): every edge carries a (cost, resource) pair and the result is the Pareto front of nondominated (cost, resource) path values, in increasing cost / decreasing resource order. With a finite budget the front is restricted to paths with resource <= budget, so its first entry solves the constrained shortest path problem exactly. max_routes caps the number of routes returned (usize::MAX for the whole front).

shortest_path_route

Dijkstra with predecessor tracking, returning the shortest path from source to target as (node path, traversed CSR slots, cost), or None when the target is unreachable.

tsp_tour

Heuristic travelling-salesman tour over a row-major n x n cost matrix. Builds a nearest-neighbour tour and, when improve, polishes it with an iterated local search: or-opt/swap/2-opt descent restarted from double-bridge perturbations, keeping the best tour found. The tour starts at start; when closed it returns there (and end is ignored), otherwise a fixed end pins the final stop and None leaves it free. Returns the visiting order as indices into the matrix.