/* Brandes' Algorithm, as implemented by Raymond Zhong <raymondz@princeton.edu>
 * Finds betweenness centrality in unweighted graph in O(nm)
 * http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf
 *
 * Clustering code roughly based on InfoVis Cyberinfrastructure
 * http://iv.slis.indiana.edu/sw/bc.html
 *
 * Namespace is 'betweenness_'
 */

// given indexed associative array of nodes, matrix of links by index
// return similarly indexed associative array of betweenness centrality
function betweenness_centrality(nodes, links, callback) {
    var i, count = 0;
    var centrality = {};

    for (i in nodes)
	centrality[i] = 0;

    for (i in nodes) {
	count++;
	if (callback !== undefined) callback(count);

//	if (links[i].length == 0)
//	    continue;

	var s = []; // stack of nodes searched
	var q = []; // queue of nodes to search (BFS)
	var paths = {}; // shortest paths: list of indices
	var dist = {}; // -1 if never visited, 1 if visited for last time
	var sigma = {};
	for (j in nodes) {
	    sigma[j] = 0;
	    dist[j] = -1;
	    paths[j] = [];
	}
	sigma[i] = 1;
	dist[i] = 0;

	q.push(i);
	while (q.length > 0)
	{
	    var n = q.pop();
	    s.unshift(n);

	    //for (i in dist) if (isNaN(dist[i])) debugger;
	    //var u = 0; for (i in sigma) u += sigma[i]; if (u==0) debugger;

	    for (neighbor in links[n]) {
		var neighbor_id = links[n][neighbor];

		if (dist[neighbor_id] < 0) {
		    q.unshift(neighbor_id);
		    dist[neighbor_id] = dist[n] + 1; // mark as visited
		}

		if (dist[neighbor_id] == dist[n] + 1) {
		    sigma[neighbor_id] = sigma[n] + sigma[neighbor_id];
		    paths[neighbor_id].push(n); // there exists a path to neighbor_id via n
		}
	    }
	}

	var delta = {};
	for (j in nodes)
	    delta[j] = 0;

	while (s.length > 0)
	{
	    var w = s.pop();
	    for (p in paths[w])
		var adj_id = paths[w][p];
		delta[adj_id] += (sigma[adj_id]/sigma[w]) * (1+delta[w]);
	    if (w != i)
		centrality[w] += delta[w];
	}
    }

    return centrality;
}

// given a threshold for betweenness centrality, 0.0 < threshold < 1.0
// clusters a graph by iteratively removing edges
// returns reduced set of edges
function betweenness_cluster_graph(graph_nodes, graph_links, threshold, normalize) {
    var links = graph_links.slice(0);
    do {
	var graph_centrality = centrality(graph_nodes, links);

	var max_centrality = 0;
	var max_i;
	for (i in graph_centrality) {
	    if (graph_centrality[i] > max_centrality) {
		max_i = i;
		max_centrality = graph_centrality[i];
	    }
	}

	if (normalize) {
	    var n = graph_centrality.length;
	    max_centrality = max_centrality / ((n - 1) * (n - 2) / 2);
	}

	delete links[max_i];

    } while (max_centrality > threshold)

    return links;
}

// partitions a graph, assuming symmetric connectivity and undirectedness
// given indexed associative array of nodes, matrix of links by index
// returns a list of lists (partitions)
function betweenness_partition(nodes, links) {
    var c = []; // clusters
    var v = {}; // if visited
    for (i in nodes)
	v[i] = 0;

    function betweenness_bfs(node, cluster) {
	if (v[node] == 1) return;

	v[node] = 1;
	cluster.push(node);
	for (j in links[node])
	    betweenness_bfs(links[node][j], cluster);
    }

    for (i in nodes) {
	var cluster = [];
	betweenness_bfs(i, cluster);

	if (cluster.length > 0)
	    c.push(cluster);
    }

    return c;
}

function betweenness_fail() {
    alert('An error occurred.');
    debugger;
}