#include <engine/distance_engine.h>

Collaboration diagram for DistanceEngine:

[legend]

Public Member Functions
	DistanceEngine (Graph &g)
void	compute (const bool computeCentralities, const bool considerWeights, const bool inverseWeights, const bool dropIsolates, const bool allowNegativeWeights=false)
	Runs the full geodesic distance (and optionally centrality) computation pipeline.
bool	bellmanFordPotentials (const bool inverseWeights, QVector< qreal > &outPotentials)
	Public entry point for the potentials pass below, for callers with no DistanceScratch of their own (currently just the "signed" CLI kernel). Owns a throwaway DistanceScratch and copies its result out. Not part of compute()'s pipeline and not yet threaded into dijkstraSSSP()/runAllSources() - see the overload below for the algorithm and status.

Private Member Functions
void	initRun (const bool computeCentralities, const bool considerWeights, const bool inverseWeights, const bool dropIsolates, const bool allowNegativeWeights, struct DistanceScratch &ds, struct CentralityScratchSSSP &csssp, struct CentralityScratchFinalize &csfin, IDistanceProgressSink &sink)
	Phase 0 of compute(): resets every scratch/aggregate field this run will populate, scans for a negative edge weight up front (refusing the whole computation via sink.reportNegativeWeights() unless allowNegativeWeights is set), and handles the zero-edges (E==0) case entirely on its own since runAllSources() has nothing to do then.
bool	bellmanFordPotentials (const bool inverseWeights, struct DistanceScratch &ds)
	Bellman-Ford reweighting pass computing a potential h(v) for every vertex, so that edges can later be reweighted as w'(u,v) = w(u,v) + h(u) - h(v) and handed to dijkstraSSSP() unmodified on a graph guaranteed to have no negative edges. Every real vertex starts at potential 0 - this is exactly the result an implicit virtual source with a zero-weight edge to every real vertex would produce on round 0, so that virtual source never needs to be materialized. Also detects negative cycles as a by-product of the same pass (the standard "does relaxation round V still improve anything" check) - a negative cycle makes shortest paths undefined, so ds.potentials is left incomplete/unusable and this returns false. Not yet called from compute() or wired into dijkstraSSSP()/runAllSources() - calling it unconditionally would cost every ordinary (non-negative-weight) computation a wasted full edge relaxation pass; it should be gated behind an explicit opt-in once its result is actually consumed by the SSSP loop.
void	runAllSources (const bool computeCentralities, const bool considerWeights, const bool inverseWeights, const bool dropIsolates, struct DistanceScratch &ds, IDistanceProgressSink &sink)
	Runs SSSP (BFS or Dijkstra, per considerWeights) from every enabled vertex, in parallel across CPU cores via QtConcurrent::blockingMap. Each worker thread owns its own ThreadLocalState; graph-wide writes that aren't safe to make concurrently (BC, SC, distance sum, geodesics count, diameter) are accumulated into per-thread state during the map and reduced into graph-global state in a single-threaded step immediately after.
void	finalize (const bool computeCentralities, const bool dropIsolates, struct DistanceScratch &ds, struct CentralityScratchFinalize &csfin, IDistanceProgressSink &sink)
	Single-threaded aggregation pass run after runAllSources() completes: scans for vertex pairs left unreachable (populating notConnectedPairs and the infinite-eccentricity/ zero-centrality bookkeeping that implies), determines overall graph connectedness, and finishes the graph-wide centrality aggregates (sums, min/max, normalized forms) that runAllSources() only partially accumulated per-source.
void	bfsSSSP (const int &s, const int &si, const bool &computeCentralities, const bool &dropIsolates, PerSourceScratch &pss)
void	dijkstraSSSP (const int &s, const int &si, const bool &computeCentralities, const bool &inverseWeights, const bool &dropIsolates, PerSourceScratch &pss, const QVector< qreal > &potentials=QVector< qreal >())

Private Attributes
Graph &	graph

Constructor & Destructor Documentation

◆ DistanceEngine()

DistanceEngine::DistanceEngine ( Graph & g )

explicit

Member Function Documentation

◆ bellmanFordPotentials() [1/2]

bool DistanceEngine::bellmanFordPotentials	(	const bool	inverseWeights,
		QVector< qreal > &	outPotentials )

Public entry point for the potentials pass below, for callers with no DistanceScratch of their own (currently just the "signed" CLI kernel). Owns a throwaway DistanceScratch and copies its result out. Not part of compute()'s pipeline and not yet threaded into dijkstraSSSP()/runAllSources() - see the overload below for the algorithm and status.

Parameters

inverseWeights	invert each edge weight before relaxing, same convention as elsewhere
outPotentials	filled with h(v) per vertex (indexed by vertex position) on success; not meaningful if this returns false

Returns: false if a reachable negative cycle was found, true otherwise

◆ bellmanFordPotentials() [2/2]

bool DistanceEngine::bellmanFordPotentials	(	const bool	inverseWeights,
		struct DistanceScratch &	ds )

private

Bellman-Ford reweighting pass computing a potential h(v) for every vertex, so that edges can later be reweighted as w'(u,v) = w(u,v) + h(u) - h(v) and handed to dijkstraSSSP() unmodified on a graph guaranteed to have no negative edges. Every real vertex starts at potential 0 - this is exactly the result an implicit virtual source with a zero-weight edge to every real vertex would produce on round 0, so that virtual source never needs to be materialized. Also detects negative cycles as a by-product of the same pass (the standard "does relaxation round V still improve anything" check) - a negative cycle makes shortest paths undefined, so ds.potentials is left incomplete/unusable and this returns false. Not yet called from compute() or wired into dijkstraSSSP()/runAllSources() - calling it unconditionally would cost every ordinary (non-negative-weight) computation a wasted full edge relaxation pass; it should be gated behind an explicit opt-in once its result is actually consumed by the SSSP loop.

Parameters

inverseWeights	invert each edge weight before relaxing, same convention as elsewhere
ds	run-scratch state; ds.potentials/ds.negativeCycleDetected are written here

Returns: false if a reachable negative cycle was found, true otherwise

◆ bfsSSSP()

void DistanceEngine::bfsSSSP	(	const int &	s,
		const int &	si,
		const bool &	computeCentralities,
		const bool &	dropIsolates,
		PerSourceScratch &	pss )

private

Breadth-First Search (BFS) method for unweighted graphs (directed or not)

INPUT: a 'source' vertex with vpos s and a boolean computeCentralities. (Implicitly, BFS uses the m_graph structure)

OUTPUT: For every vertex t: pss.dist[ti] is set to the distance of each t from s For every vertex t: pss.sigma[ti] is set to the number of shortest paths between s and t

Also, if computeCentralities is true then BFS does extra operations: a) For source vertex s: it calculates CC(s) as the sum of its distances from every other vertex. it calculates eccentricity(s) as the maximum distance from all other vertices. it increases pss.nthOrder[ N ] by one, to store the number of nodes at distance n from source s b) For every vertex u on a shortest path from s to w: appends u to pss.Ps[w], thus Ps stores all predecessors of w on all shortest paths from s. BC and SC are both derived from Ps/sigma afterward, in runAllSources()'s Brandes back-propagation loop - not accumulated here. c) Each vertex u popped from Q is pushed to pss.Stack

◆ compute()

void DistanceEngine::compute	(	const bool	computeCentralities,
		const bool	considerWeights,
		const bool	inverseWeights,
		const bool	dropIsolates,
		const bool	allowNegativeWeights = false )

Runs the full geodesic distance (and optionally centrality) computation pipeline.

Orchestrates three phases:

Phase 0 (Init): initialises scratch structures, resets aggregates, handles the degenerate E==0 case.
Phase 1+2 (SSSP loop): runs BFS or Dijkstra from every source vertex, accumulating per-source distance and centrality data.
Phase 3 (Finalize): connectivity scan, group-level aggregation, normalisation of centrality scores.

If the user cancels via the progress dialog, the function returns early after Phase 1+2 without finalising, and calculatedDistances is left false so the next call recomputes from scratch.

Parameters

computeCentralities	If true, also computes BC, CC, SC, EC, PC.
considerWeights	If true, uses edge weights (Dijkstra); otherwise BFS.
inverseWeights	If true, uses 1/weight as the distance metric.
dropIsolates	If true, excludes isolated vertices from all calculations.
allowNegativeWeights	If true, negative edge weights are not refused - instead, potentials are computed via bellmanFordPotentials() (Johnson's algorithm) and every source's Dijkstra run is reweighted to be non-negative. Refuses instead if the network has a reachable negative cycle (see Graph::negativeCycleDetected()), since shortest paths are then undefined regardless of algorithm. Has no effect unless considerWeights is also true.

◆ dijkstraSSSP()

void DistanceEngine::dijkstraSSSP	(	const int &	s,
		const int &	si,
		const bool &	computeCentralities,
		const bool &	inverseWeights,
		const bool &	dropIsolates,
		PerSourceScratch &	pss,
		const QVector< qreal > &	potentials = QVector<qreal>() )

private

Dijkstra's algorithm for solving the SSSP problem in weighted graphs (directed or not). It uses a min-priority queue prQ to provide constant time lookup of the minimum distance. The priority queue is implemented with std::priority_queue

INPUT: a 'source' vertex with vpos s and a boolean computeCentralities. (Implicitly, the algorithm uses the m_graph structure)

OUTPUT: For every vertex t: pss.dist[ti] is set to the distance of each t from s For every vertex t: pss.sigma[ti] is set to the number of shortest paths between s and t

Also, if computeCentralities is true then it does extra operations: a) For source vertex s: it calculates CC(s) as the sum of its distances from every other vertex. it calculates eccentricity(s) as the maximum distance from all other vertices. it increases pss.nthOrder[ N ] by one, to store the number of nodes at distance n from source s b) For every vertex u: appends each predecessor u of w to pss.Ps[w], thus Ps stores all predecessors of w on all shortest paths from s. BC and SC are both derived from Ps/sigma afterward, in runAllSources()'s Brandes back-propagation loop - not accumulated here. c) Each vertex u popped from prQ is pushed to pss.Stack

◆ finalize()

void DistanceEngine::finalize	(	const bool	computeCentralities,
		const bool	dropIsolates,
		struct DistanceScratch &	ds,
		struct CentralityScratchFinalize &	csfin,
		IDistanceProgressSink &	sink )

private

Single-threaded aggregation pass run after runAllSources() completes: scans for vertex pairs left unreachable (populating notConnectedPairs and the infinite-eccentricity/ zero-centrality bookkeeping that implies), determines overall graph connectedness, and finishes the graph-wide centrality aggregates (sums, min/max, normalized forms) that runAllSources() only partially accumulated per-source.

Phase 3 of compute(): single-threaded aggregation pass run after runAllSources() completes. Scans for vertex pairs left unreachable (populating notConnectedPairs and the infinite-eccentricity/zero-centrality bookkeeping that implies), determines overall graph connectedness, and finishes the graph-wide centrality aggregates (sums, min/max, normalized forms) that runAllSources() only partially accumulated per-source.

Parameters

computeCentralities	Whether centrality aggregates need finishing at all.
dropIsolates	Exclude isolated vertices from the connectivity/aggregate scan.
ds	Scratch state carried over from initRun()/runAllSources().
csfin	Centrality-aggregation scratch (sums, min/max trackers) to finish into graph state.
sink	Progress/cancellation callback.
computeCentralities	Whether centrality aggregates need finishing at all.
dropIsolates	Exclude isolated vertices from the connectivity/aggregate scan.
ds	Scratch state carried over from initRun()/runAllSources().
csf	Centrality-aggregation scratch (sums, min/max trackers) to finish into graph state.
sink	Progress/cancellation callback.

◆ initRun()

void DistanceEngine::initRun	(	const bool	computeCentralities,
		const bool	considerWeights,
		const bool	inverseWeights,
		const bool	dropIsolates,
		const bool	allowNegativeWeights,
		struct DistanceScratch &	ds,
		struct CentralityScratchSSSP &	csssp,
		struct CentralityScratchFinalize &	csfin,
		IDistanceProgressSink &	sink )

private

Phase 0 of compute(): resets every scratch/aggregate field this run will populate, scans for a negative edge weight up front (refusing the whole computation via sink.reportNegativeWeights() unless allowNegativeWeights is set), and handles the zero-edges (E==0) case entirely on its own since runAllSources() has nothing to do then.

Phase 0 of compute(): resets every scratch/aggregate field this run will populate, scans for a negative edge weight up front (refusing the whole computation via sink.reportNegativeWeights() unless allowNegativeWeights is set), and handles the zero-edges (E==0) case entirely on its own, since runAllSources()/finalize() have nothing to do then.

Parameters

computeCentralities	Whether centrality scratch/aggregate fields need resetting too.
considerWeights	Whether the negative-weight scan below runs at all (BFS never sees weights, so there is nothing to detect).
inverseWeights	Only used for the E==0 branch's own bookkeeping.
dropIsolates	Exclude isolated vertices from the vertex count/E==0 population.
allowNegativeWeights	If true, a detected negative edge weight is not refused here - the caller (compute()) has opted into the negative-weight-safe (Johnson's-algorithm) path, which is defined for negative weights.
ds	Output: scratch state for this run (sizes, maxima, per-run accumulators).
csssp	Output: SSSP-phase centrality scratch, zeroed for this run.
csfin	Output: finalize-phase centrality scratch, zeroed for this run.
sink	Progress/cancellation/negative-weight-refusal callback.

◆ runAllSources()

void DistanceEngine::runAllSources	(	const bool	computeCentralities,
		const bool	considerWeights,
		const bool	inverseWeights,
		const bool	dropIsolates,
		struct DistanceScratch &	ds,
		IDistanceProgressSink &	sink )

private

Runs SSSP (BFS or Dijkstra, per considerWeights) from every enabled vertex, in parallel across CPU cores via QtConcurrent::blockingMap. Each worker thread owns its own ThreadLocalState; graph-wide writes that aren't safe to make concurrently (BC, SC, distance sum, geodesics count, diameter) are accumulated into per-thread state during the map and reduced into graph-global state in a single-threaded step immediately after.

Phase 1+2 of compute(): runs SSSP (BFS or Dijkstra, per considerWeights) from every enabled vertex, in parallel across CPU cores via QtConcurrent::blockingMap. Each worker thread owns its own ThreadLocalState; graph-wide writes that aren't safe to make concurrently (BC, SC, distance sum, geodesics count, diameter) are accumulated into per-thread state during the map and reduced into graph-global state in a single-threaded step immediately after.

Parameters

computeCentralities	Also accumulate BC/SC/CC/etc. per source, not just distances.
considerWeights	Dijkstra (true) vs. BFS (false).
inverseWeights	Use 1/weight as the per-edge distance metric.
dropIsolates	Exclude isolated vertices from the source loop.
ds	Scratch state populated by initRun() (potentials, if any, bounds, etc.).
sink	Progress/cancellation callback.
computeCentralities	Also accumulate BC/SC/CC/etc. per source, not just distances.
considerWeights	Dijkstra (true) vs. BFS (false).
inverseWeights	Use 1/weight as the per-edge distance metric.
dropIsolates	Exclude isolated vertices from the source loop.
ds	Scratch state populated by initRun() (potentials, if any, bounds, etc.); also where this phase's own per-run accumulators live.
sink	Progress/cancellation callback.

Member Data Documentation

◆ graph

Graph& DistanceEngine::graph

private

The documentation for this class was generated from the following files:

Public Member Functions

Private Member Functions

Private Attributes

Constructor & Destructor Documentation

◆ DistanceEngine()

Member Function Documentation

◆ bellmanFordPotentials() [1/2]

◆ bellmanFordPotentials() [2/2]

◆ bfsSSSP()

◆ compute()

◆ dijkstraSSSP()

◆ finalize()

◆ initRun()

◆ runAllSources()

Member Data Documentation

◆ graph