#include <stdio.h>
#include <stdlib.h>
#include <alloca.h>

#include "getbingraph.c"
#include "intset.h"

int countEdges (struct graphInfo *g) {
  int n = g->nNodes, k = 0, i;
  for (i = 0; i < n; ++i) k += SetSize (BitMatrixRow (g->graph, n, i), n);
  return k;
}

struct nodeList {
  int node, edge, next;
};

void betweenness (struct graphInfo *g, double **onNodes, double **onEdges) {
  // assumes list representation
  int n = g->nNodes, m = g->offsets[n];
  double *totalBtw = (double *) calloc (n, sizeof (double)),
    *totalBtwE = (double *) calloc (m, sizeof (double)),
    *curBtw = (double *) alloca (n * sizeof (double));
  int *minPathLen = (int *) alloca (n * sizeof (int)),
    *nPaths = (int *) alloca (n * sizeof (int)),
    *preds = (int *) alloca (n * sizeof (int)),
    *queue = (int *) alloca (n * sizeof (int));
  struct nodeList *linx =
    (struct nodeList *) malloc (m * sizeof (struct nodeList));
  int i;

#define Enq(i,l) \
  (minPathLen[i] = l, preds[i] = -1, curBtw[i] = 1.0, queue[back++] = i)

  for (i = 0; i < n; ++i) {
    int front, back = 0, rev = 0;
    memset ((void *) nPaths, 0, n * sizeof (int));
    Enq (i, 0);
    nPaths[i] = 1;
    for (front = 0; front != back; ++front) {
      int j = queue[front], l = minPathLen[j] + 1, p = nPaths[j];
      int cur = g->offsets[j], top = g->offsets[j+1], k;
      for (; cur < top && (k = g->base[cur], 1); ++cur)
	if ((nPaths[k] == 0 && (Enq (k, l), 1)) || minPathLen[k] == l) {
	  nPaths[k] += p;
	  linx[rev].node = j;
	  linx[rev].edge = cur;
	  linx[rev].next = preds[k];
	  preds[k] = rev++;
	}
    }
    do {
      int k = queue[--front], r;
      double x = curBtw[k] / nPaths[k];
      for (r = preds[k]; r >= 0; r = linx[r].next) {
	int cur = linx[r].edge, j = linx[r].node;
	double part = x * nPaths[j];
	totalBtwE[cur] += part;
	curBtw[j] += part;
      }
    } while (front);
    for (front = 0; front != back; ++front) {
      int j = queue[front];
      totalBtw[j] += curBtw[j];
    }
  }
  free (linx);
  *onNodes = totalBtw;
  *onEdges = totalBtwE;
}

struct graphInfo *mtx2list (struct graphInfo *g) {
  int m = countEdges (g), n = g->nNodes;
  struct graphInfo *g1 = (struct graphInfo *) malloc (sizeof (struct graphInfo));
  g1->nNodes = n;
  g1->listrep = 1;
  g1->names = g->names;
  g1->nodeDict = g->nodeDict;
  int *offsets = (int *) malloc ((n+1) * sizeof (int)),
    *base = (int *) malloc (m * sizeof (int));
  g1->offsets = offsets;
  g1->base = base;
  int i, j, k;
  offsets[0] = 0;
  for (i = k = 0; i < n; ++i) {
    IntSet out = BitMatrixRow (g->graph, n, i);
    for (j = -1; (j = SetFindNext (out, n, j+1)) != n; ) base[k++] = j;
    offsets[i+1] = k;
  }
  return g1;
}

void usage () {
  fprintf (stderr, "\
args: [-e] <bin-graph>\n\
  -e  compute betweenness for edges\n");
  exit (1);
}

main (int argc, char **argv) {
  if (argc < 2) usage ();
  struct graphInfo gi, *g;
  int nextArg = 1, mode = 0, i;
  if (argv[1][0] == '-') {
    if (argv[1][1] == 'e') mode = 1;
    else usage ();
    nextArg = 2;
  }
  getGraph (argv[nextArg], &gi);
  g = mtx2list (&gi);
  double *bn, *be;
  betweenness (g, &bn, &be);
  if (mode) {
    int k, l;
    for (i = k = 0; i < g->nNodes; ++i)
      for (l = g->offsets[i+1]; k < l; ++k)
	printf ("%s/%s\t%f\n", g->names[i], g->names[g->base[k]], be[k]);
  }
  else
    for (i = 0; i < g->nNodes; ++i)
      printf ("%s\t%f\n", g->names[i], bn[i]);
}