Betweenness Centrality

#include <iostream>
#include <queue>
#include <stack>
#include <vector>

auto brandes(const std::vector<int>& rowPtr, const std::vector<int>& colIdx)
{
  const auto         numVertices = rowPtr.size() - 1;
  std::vector<float> betweenness(numVertices, 0.0f);
  //For each vertex s, perform a BFS to establish levels and predecessors
  //! The time complexity is O(V^3)
  for(int i = 0; i < numVertices; i++)
  {
    std::vector<int> distance(numVertices, -1);    // Initialize distance from s
    std::vector<int> pathCount(numVertices, 0);    // Initialize path count
    std::vector<int> DepScore(numVertices, 0);     // Dependency score for each vertex
    std::queue<int>  pathQueue;                    // for BFS
    std::stack<int>  pathStack;

    std::vector<std::vector<int>> predecessor(numVertices);

    distance[i]  = 0;
    pathCount[i] = 1;
    pathQueue.push(i);
    // BFS traversal
    // for a single source vertex, the time complexity is O(V+E),
    //! so the overall time complexity is O(V+E) for each vertex i
    while(!pathQueue.empty())
    {
      const auto source = pathQueue.front();
      pathQueue.pop();
      pathStack.push(source);
      for(auto i = rowPtr[source]; i < rowPtr[source + 1]; i++)
      {
        const auto target = colIdx[i];
        if(distance[target] < 0)
        {
          pathQueue.push(target);
          distance[target] = distance[source] + 1;
        }
        // shortest path to target via source?
        if(distance[target] == distance[source] + 1)
        {
          pathCount[target] += pathCount[source];
          predecessor[target].push_back(source);
        }
      }
    }
    // traverse the graph in reverse BFS order
    // backtrack to propagate the dependency scores (delta) back through the graph,
    // to calculate the BC value for each node.
    //! The time complexity is O(V*V) for each vertex i
    //! There are V vertices in the stack, each of which has at most V-1 predecessors
    while(!pathStack.empty())
    {
      const auto curr = pathStack.top();
      pathStack.pop();

      for(auto prev : predecessor[curr])
      {
        DepScore[prev] +=
            (static_cast<float>(pathCount[prev]) / pathCount[curr]) * (1 + DepScore[curr]);
      }
      if(curr != i)
      {
        betweenness[curr] += DepScore[curr];
      }
    }
  }
  return betweenness;
}

int main()
{
  std::vector<int> rowPtr = { 0, 2, 4, 6, 8, 10, 12 };
  std::vector<int> colIdx = { 1, 2, 0, 3, 0, 1, 4, 1, 2, 5, 3, 5 };
  // Compute betweenness centrality using Brandes's algorithm
  // unweighted graph for simplicity
  auto betweenness = brandes(rowPtr, colIdx);
  // Print betweenness centrality
  std::cout << "Betweenness centrality:" << std::endl;
  for(int i = 0; i < betweenness.size(); i++)
  {
    std::cout << "Vertex " << i << ": " << betweenness[i] << std::endl;
  }
}