per_source_scratch.h

Go to the documentation of this file.

 
#ifndef SOCNETV_PER_SOURCE_SCRATCH_H
#define SOCNETV_PER_SOURCE_SCRATCH_H
 
#include <stack>
#include <QHash>
#include <QList>
#include <QVector>
#include <QtGlobal>
#include <cstdlib>  // RAND_MAX
 
struct PerSourceScratch
{
    // Brandes traversal stack — vertices ordered by non-increasing distance from s
    std::stack<int> Stack;
 
    // Predecessor lists: Ps[vi] = list of vertices that precede vertex vi
    // on shortest paths from the current source s.  Indexed by vertex position.
    QVector<QList<int>> Ps;
 
    // Dependency accumulators for Brandes BC back-propagation.
    // Indexed by vertex position.
    QVector<qreal> delta;
 
    // BFS / Dijkstra distances from current source s.
    // dist[vi] == RAND_MAX means vertex vi has not been reached.
    // Indexed by vertex position.
    QVector<qreal> dist;
 
    // Shortest-path counts (sigma) from current source s.
    // Indexed by vertex position.
    QVector<int> sigma;
 
    // Number of vertices at each distance order from s (used for Power Centrality).
    // Key = distance, Value = count.
    QHash<qreal, int> nthOrder;
 
    // Size of the connected component reachable from s (used for SPC normalisation).
    int componentSize = 0;
 
    // No per-source graph-aggregate accumulators live here: diameter, distance sum, and
    // geodesics (reachable-pair) count must all be computed from each vertex's FINAL
    // distance, not a running/duplicated accumulation sampled during or right after
    // relaxation (a vertex can be relaxed to a smaller distance after an earlier, larger
    // one) - computed directly from dist[] / the final APSP matrix in runAllSources() and
    // finalize() instead, after a source's SSSP run has fully settled.
 
    // Allocate all containers once for totalVertices positions.
    // Call this once before the source loop.
    void allocate(int totalVertices)
    {
        Ps.resize(totalVertices);
        delta.resize(totalVertices);
        dist.resize(totalVertices);
        sigma.resize(totalVertices);
    }
 
    // Reset per-source state before each new source vertex.
    // computeCentralities controls whether the Brandes-only structures are reset.
    void resetPerSource(bool computeCentralities)
    {
        dist.fill((qreal)RAND_MAX);
        sigma.fill(0);
        if (computeCentralities)
        {
            while (!Stack.empty())
                Stack.pop();
            for (auto &ps : Ps)
                ps.clear();
            nthOrder.clear();
        }
        // delta is zeroed in the per-source back-propagation setup loop,
        // not here, to preserve the existing guard on computeCentralities.
    }
 
    // Increment the nth-order neighbourhood count for distance d.
    void nthOrderIncrement(qreal d)
    {
        nthOrder.insert(d, nthOrder.value(d, 0) + 1);
    }
};
 
#endif // SOCNETV_PER_SOURCE_SCRATCH_H