/*-
 * Copyright (c) 2014, Alexandre P. Francisco <aplf@ist.utl.pt>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

import java.io.IOException;
import java.util.Iterator;
import java.util.TreeMap;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

import it.unimi.dsi.fastutil.ints.IntArrayFIFOQueue;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
import it.unimi.dsi.fastutil.ints.IntIterator;
import it.unimi.dsi.fastutil.ints.Int2DoubleOpenHashMap;
import it.unimi.dsi.fastutil.io.BinIO;
import it.unimi.dsi.webgraph.ImmutableGraph;
import it.unimi.dsi.webgraph.LazyIntIterator;
import it.unimi.dsi.webgraph.NodeIterator;

public class VertexBetweenness {
		
	private static double[] betweenness;
	private static Int2DoubleOpenHashMap[] edgeBetweenness;
	private static ImmutableGraph g = null;
	private static int [] cluster = null;
	private static int poolSize = 4;
	private static IntArrayList sources;

	private static synchronized void betweennessUpdate(int w, double x) {
		betweenness[w] += x;
	}

	private static void edgeBetweennessUpdate(int x, int w, double incr) {
		synchronized(edgeBetweenness[x]) {
			edgeBetweenness[x].addTo(w, incr);
		}
	}

	private static synchronized int getNextSource() {
		if (! sources.isEmpty())
			return sources.pop();
		return -1;
	}

	public static void main(String[] args) {
		
		String usage = "java VertexBetweenness <graph_base_name_string> <fraction_double> <thread_pool_int> <clusters>";
		if (args.length != 4 || "-h".equals(args[0])) {
	    		System.err.println("Usage: " + usage);
		    	System.exit(1);
		}

		System.err.println("Graph: " + args[0]);
		System.err.println("Loading graph " + args[0] + " in memory...");
		try {
			g = ImmutableGraph.load(args[0]);
			cluster = BinIO.loadInts(args[3]);
		} catch (IOException e) {
			System.err.println("Error: Failed to load graph '"+ args[0] +"'.");
			e.printStackTrace();
			System.exit(1);
		}

		double fraction = Double.parseDouble(args[1]);
		poolSize = Integer.parseInt(args[2]);

		System.err.println("Sampling nodes (" + (fraction*100) + "%)...");
		sources = new IntArrayList(g.numNodes());
		NodeIterator nIter = g.nodeIterator();
		while (nIter.hasNext()) {
			int u = nIter.nextInt();
			if (Math.random() < fraction)
				sources.push(u);
		}
		sources.trim();

		System.err.println(sources.size() + " nodes sampled in " + g.numNodes() + ".");
		System.err.println("Computing vertex betweenness...");

		betweenness = new double[g.numNodes()];
		edgeBetweenness = new Int2DoubleOpenHashMap[g.numNodes()];
		for (int k = 0; k < g.numNodes(); k++)
			edgeBetweenness[k] = new Int2DoubleOpenHashMap();

		ExecutorService es = Executors.newFixedThreadPool(poolSize);	

		while (poolSize != 0)
			es.submit(new BFSTask(poolSize--, g.copy()));

		es.shutdown();
		try {
			es.awaitTermination(Integer.MAX_VALUE, TimeUnit.SECONDS);
		} catch (InterruptedException e) {
			es.shutdownNow();
		}

		for (int k = 0; k < g.numNodes(); k++) {
			System.out.println(betweenness[k]);

			if (edgeBetweenness[k] == null) continue;
			IntIterator ii = edgeBetweenness[k].keySet().iterator();
			while (ii.hasNext()) {
				int x = ii.nextInt();
				System.out.println(" " + x + " " + edgeBetweenness[k].get(x));
			}
		}
		
		System.err.println("Done.");
	}

	private static class BFSTask implements Runnable {

		private ImmutableGraph g = null;
		private int id;

		BFSTask(int id, ImmutableGraph g) {
			this.g = g;
			this.id = id;
		}

		@Override
		public void run() {

			System.err.println("[" + id + "] starting thread...");

			int u = -1;
			int[] sigma = new int[g.numNodes()];
			double[] delta = new double[g.numNodes()];
			int[] d = new int[g.numNodes()];
			IntOpenHashSet[] pi = new IntOpenHashSet[g.numNodes()];	
			for (int k = 0; k < g.numNodes(); k++)
				pi[k] = new IntOpenHashSet();

			System.err.println("[" + id + "] running...");

			while ((u = getNextSource()) != -1) {
				System.err.println("[" + id + "] processing vertex " + u + "...");

				for (int k = 0; k < g.numNodes(); k++) {
					sigma[k] = 0;
					delta[k] = 0;
					d[k] = -1;
					pi[k].clear();
				}

				IntArrayFIFOQueue Q = new IntArrayFIFOQueue();
				IntArrayList S = new IntArrayList();

				Q.enqueue(u);
				sigma[u] = 1;
				d[u] = 0;

				while (! Q.isEmpty()) {
					int v = Q.dequeue();
					S.push(v);

					int w = -1;
					LazyIntIterator eIter = g.successors(v);
					while ((w = eIter.nextInt()) != -1) {
	
						if (d[w] < 0) {
							Q.enqueue(w);
							d[w] = d[v] + 1;
						}

						if (d[w] == d[v] + 1) {
							sigma[w] += sigma[v];
							pi[w].add(v);
						}
					}
				}
	
				while (! S.isEmpty()) {
					int w = S.pop();
	
					IntIterator iiter = pi[w].iterator();
					while (iiter.hasNext()) {
						int x = iiter.nextInt();
						double incr = (sigma[x]*1.0/sigma[w])*(1+delta[w]);
						delta[x] += incr;
						// Update edge (x,w) betweenness
						if (cluster[x] != cluster[w])
							edgeBetweennessUpdate(x, w, incr);
					}
					if (w != u)
						betweennessUpdate(w, delta[w]);
				}
					
				System.err.println("[" + id + "] vertex " + u + " done.");
			}
			
			System.err.println("[" + id + "] done.");
		}
	}
}