distance_engine.h

Go to the documentation of this file.

 
#ifndef SOCNETV_DISTANCE_ENGINE_H
#define SOCNETV_DISTANCE_ENGINE_H
 
#include "engine/graph_distance_progress_sink.h"
#include "engine/per_source_scratch.h"
 
#include <QVector>
 
class Graph;
 
class DistanceEngine
{
public:
    explicit DistanceEngine(Graph &g);
    void compute(const bool computeCentralities,
                 const bool considerWeights,
                 const bool inverseWeights,
                 const bool dropIsolates,
                 const bool allowNegativeWeights = false);
 
    // Public probe for the potentials pass - see distance_engine.cpp for the doc comment.
    bool bellmanFordPotentials(const bool inverseWeights, QVector<qreal> &outPotentials);
 
private:
    Graph &graph;

    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);
 
    // Bellman-Ford reweighting pass - see distance_engine.cpp for the doc comment.
    bool bellmanFordPotentials(const bool inverseWeights, struct DistanceScratch &ds);

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

    void finalize(const bool computeCentralities,
                  const bool dropIsolates,
                  struct DistanceScratch &ds,
                  struct CentralityScratchFinalize &csfin,
                  IDistanceProgressSink &sink);
 
    // Breadth-First Search SSSP for unweighted graphs.
    // Writes distances, sigma, and Ps (predecessor lists) to pss. Graph-wide aggregates
    // (distance sum, geodesics count, diameter) and centrality accumulators that depend on the
    // final settled shortest-path DAG (BC, SC) are computed post-hoc from pss.Ps/pss.sigma in
    // runAllSources()'s Brandes back-propagation loop, not accumulated here.
    void bfsSSSP(const int &s, const int &si,
                 const bool &computeCentralities,
                 const bool &dropIsolates,
                 PerSourceScratch &pss);
 
    // Dijkstra SSSP for weighted graphs (directed or not).
    // Same contract as bfsSSSP: unsafe graph-wide writes and DAG-dependent centralities go
    // through pss scratch fields, not touched directly here.
    // potentials: empty for a plain Dijkstra run (the default); when non-empty, indexed by
    // vertex position like pss.dist, each edge weight is reweighted inline as
    // weight + potentials[ui] - potentials[wi] before relaxation (Johnson's algorithm - see
    // bellmanFordPotentials()). Caller is responsible for un-reweighting pss.dist afterward.
    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>());
};
 
#endif // SOCNETV_DISTANCE_ENGINE_H