khotkin

#include "defs.h"
#include <stack>
#include <queue>
#include <list>
#include <cstdio>
#include <iostream>

using namespace std;

typedef stack<vertex_id_t> b_stack;
typedef queue<vertex_id_t> b_queue;
typedef list<vertex_id_t> b_list;

/* algorithm */
void run(graph_t *G, double *result)
{
  //FIXME: Your solution

    /* result array */
    vertex_id_t num = G->n;
    for (vertex_id_t v = 0; v < num; ++v) {
        result[v] = 0;
    }

    /* participant vertices and graph indeces */
    vertex_id_t V_vert;
    vertex_id_t W_vert;
    edge_id_t Vert_deg;
    edge_id_t Vert_cur;

    /* count, dist, aux arrays */
    int* count = new int[num];
    int* dist = new int[num];
    double* aux = new double[num];

    /* queue, stack and list */
    b_stack b_S;
    b_queue b_Q;
    b_list* b__P = new b_list[num];

    /* main cycle */
    for (vertex_id_t s = 0; s < num; ++s) {
        /* set starting values */
        for (vertex_id_t v = 0; v < num; ++v) {
            count[v] = 0;
            dist[v] = -1;
            aux[v] = 0.0;
        }
        count[s] = 1;
        dist[s] = 0;
        b_Q.push(s);

        /* count shortest paths */
        while (!b_Q.empty()) {
            V_vert = b_Q.front();
            b_Q.pop();
            b_S.push(V_vert);

            Vert_cur = G->rowsIndices[V_vert];
            Vert_deg = G->rowsIndices[V_vert + 1] - Vert_cur;
            for(edge_id_t E = 0; E < Vert_deg; ++E) {
                /* next neighbour */
                W_vert = G->endV[Vert_cur + E];

                /* vertex encountered for the 1st time */
                if (dist[W_vert] < 0) {
                    b_Q.push(W_vert);
                    dist[W_vert] = dist[V_vert] + 1;
                }

                /* vertex provides the shortest path */
                if (dist[W_vert] == dist[V_vert] + 1) {
                    count[W_vert] += count[V_vert];
                    b__P[W_vert].push_back(V_vert);
                }
            }
        }

        /* accumulate */
        while (!b_S.empty()) {
            W_vert = b_S.top();
            b_S.pop();

            /* change aux according to list */
            while(!b__P[W_vert].empty()) {
                V_vert = b__P[W_vert].front();
                aux[V_vert] += (1.0 + aux[W_vert]) * (double(count[V_vert]) / double(count[W_vert]));
                b__P[W_vert].pop_front();
            }

            /* change betweeness centrality */
            if (W_vert != s) {
                result[W_vert] += aux[W_vert];
            }
        }

        if (!b_Q.empty()) std::cout << "QUEUE!\n";
        if (!b_S.empty()) std::cout << "STACK!\n";
        for (vertex_id_t v = 0; v < num; ++v) {
            if(!b__P[v].empty()) std::cout << "LIST " << v << " !\n";
        }
    }

    /* free memory */
    delete aux;
    delete dist;
    delete count;
}