DistanceEngine Class Reference

#include <engine/distance_engine.h>

Collaboration diagram for DistanceEngine:

Public Member Functions
	DistanceEngine (Graph &g)
void	compute (const bool computeCentralities, const bool considerWeights, const bool inverseWeights, const bool dropIsolates)
	Runs the full geodesic distance (and optionally centrality) computation pipeline.

Private Member Functions
void	initRun (const bool computeCentralities, const bool considerWeights, const bool inverseWeights, const bool dropIsolates, struct DistanceScratch &ds, struct CentralityScratchSSSP &csssp, struct CentralityScratchFinalize &csfin, IDistanceProgressSink &sink)
void	runAllSources (const bool computeCentralities, const bool considerWeights, const bool inverseWeights, const bool dropIsolates, struct DistanceScratch &ds, struct CentralityScratchSSSP &csssp, IDistanceProgressSink &sink)
void	finalize (const bool computeCentralities, const bool dropIsolates, struct DistanceScratch &ds, struct CentralityScratchFinalize &csfin, IDistanceProgressSink &sink)
void	bfsSSSP (const int &s, const int &si, const bool &computeCentralities, const bool &dropIsolates)
void	dijkstraSSSP (const int &s, const int &si, const bool &computeCentralities, const bool &inverseWeights, const bool &dropIsolates)

Private Attributes
Graph &	graph

Constructor & Destructor Documentation

DistanceEngine()

DistanceEngine::DistanceEngine ( Graph &  g )

explicit

Member Function Documentation

bfsSSSP()

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

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: d(s, t) is set to the distance of each t from s For every vertex t: s(s, t) 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 sizeOfNthOrderNeighborhood [ N ] by one, to store the number of nodes at distance n from source s b) For every vertex u: it increases SC(u) by one, when it finds a new shor. path from s to t through u. appends each neighbor y of u to the list , thus Ps stores all predecessors of y on all all shortest paths from s c) Each vertex u popped from Q is pushed to a stack Stack

compute()

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

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.

dijkstraSSSP()

void DistanceEngine::dijkstraSSSP ( const int &  s, const int &  si, const bool &  computeCentralities, const bool &  inverseWeights, const bool &  dropIsolates  )

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: d(s, t) is set to the distance of each t from s For every vertex t: s(s, t) 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 sizeOfNthOrderNeighborhood [ N ] by one, to store the number of nodes at distance n from source s b) For every vertex u: it increases SC(u) by one, when it finds a new shor. path from s to t through u. appends each neighbor y of u to the list Ps, thus Ps stores all predecessors of y on all all shortest paths from s c) Each vertex u popped from prQ is pushed to a stack Stack

finalize()

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

private

initRun()

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

private

runAllSources()

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

private

Member Data Documentation

graph

Graph& DistanceEngine::graph

private

---

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

• distance_engine.h
• distance_engine.cpp