Code Documentation 3.3
Social Network Visualizer
Loading...
Searching...
No Matches
DistanceEngine Class Reference

#include <engine/distance_engine.h>

Collaboration diagram for DistanceEngine:
Collaboration graph
[legend]

Public Member Functions

 DistanceEngine (Graph &g)
void compute (const bool computeCentralities, const bool considerWeights, const bool inverseWeights, const bool dropIsolates)

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 )

◆ 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: