ProfileRouter Namespace Reference

Classes
struct	Edge
	A single directed weighted edge in the routing graph. More...
struct	Graph
	The input to ProfileRouter — nodes are 0..nodeCount-1, edges are directed by default and reinterpreted as undirected via Options. More...
struct	Options
	Tunables for a single routing query. More...
struct	Path
	A single candidate path: ordered node sequence (length N+1) of engine node indices, the user-supplied link IDs joining them (length N — pulled from Edge::linkId at emit time), and the summed weight along the sequence. More...
struct	Result
	What the router returns. Empty paths plus non-empty error means an outright failure (e.g. invalid endpoints); empty paths plus empty error means no path was found (disconnected components). More...

Functions
Result	enumerateSimplePaths (const Graph &g, int startNode, int endNode, const Options &opts={})
	Enumerates every simple (no-repeated-node) path between startNode and endNode using DFS with backtracking.
Result	kShortestPaths (const Graph &g, int startNode, int endNode, const Options &opts={})
	Yen's k-shortest simple paths from startNode to endNode.
Result	kShortestPathsThrough (const Graph &g, const QVector< int > &waypoints, const Options &opts={})
	Routes through a sequence of waypoints (start → w1 → … → end).

Function Documentation

enumerateSimplePaths()

Result ProfileRouter::enumerateSimplePaths	(	const Graph &	g,
		int	startNode,
		int	endNode,
		const Options &	opts = {}
	)

Enumerates every simple (no-repeated-node) path between startNode and endNode using DFS with backtracking.

Returned paths are sorted by total edge weight ascending, so the shortest path is at index 0 and consumers that only care about the "best" candidate can keep ignoring the rest. Edge weights must be non-negative — they are used only for ordering, not for pruning, so even paths with very heavy weights are returned as long as the path-count and wall-clock caps allow.

Honours opts.maxPaths (hard cap on collected paths) and opts.softCapMs (wall-clock soft cap). When either fires the collected paths are sorted and returned with Result::truncated = true.

When startNode == endNode an error result is returned. Worst-case running time is exponential in the number of nodes; do NOT raise maxPaths beyond a few hundred thousand on a heavily-meshed network without raising softCapMs in proportion.

kShortestPaths()

Result ProfileRouter::kShortestPaths	(	const Graph &	g,
		int	startNode,
		int	endNode,
		const Options &	opts = {}
	)

Yen's k-shortest simple paths from startNode to endNode.

A "simple" path has no repeated nodes. Edge weights must be non-negative. See class documentation for caller conventions.

When startNode == endNode an error result is returned — a zero-length path is not useful in the profile-plot context.

Here is the caller graph for this function:

kShortestPathsThrough()

Result ProfileRouter::kShortestPathsThrough	(	const Graph &	g,
		const QVector< int > &	waypoints,
		const Options &	opts = {}
	)

Routes through a sequence of waypoints (start → w1 → … → end).

v1 returns at most one path — the concatenation of the per-segment shortest paths. If any segment is unreachable the result is empty. Multi-path enumeration through waypoints is deliberately deferred (combinatorial blow-up; planned-but- deferred to a follow-up).

Here is the call graph for this function: