/**
 * 
 */
package cn.shawn.iem;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;

/**
 * @author zhuxiang
 *
 */
public class ReverseEfficiencySampling {
	private HashMap<String, Double> generateReverseReachableMap(DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> g, String v, Random randomFlip){
		HashMap<String, Double> rrMap = new HashMap<>();
		HashMap<String, Boolean> searchedNodeMap = new HashMap<>();
		// initialize reverse reachable dequeue
		Deque<String> sDeque = new ArrayDeque<String>();
		sDeque.addLast(v);
		rrMap.put(v, 1.0);
		while (sDeque.size() > 0) {
			String vertex = sDeque.removeFirst();
			searchedNodeMap.put(vertex, true);
			Set<DefaultWeightedEdge> incomingEdges = g.incomingEdgesOf(vertex);
			int inDegree = g.inDegreeOf(vertex);
			for (DefaultWeightedEdge incomingEdge : incomingEdges) {
				String sourceVertex = g.getEdgeSource(incomingEdge);
				if (!searchedNodeMap.containsKey(sourceVertex)) {
					double flip = randomFlip.nextFloat();
					if (flip < 1.0 / inDegree) {
						double distance = rrMap.get(vertex) + g.getEdgeWeight(incomingEdge);
						if (!rrMap.containsKey(sourceVertex) || rrMap.containsKey(sourceVertex) && distance < rrMap.get(sourceVertex)) {
							rrMap.put(sourceVertex, distance);
							sDeque.addLast(sourceVertex);
						}
					}
				}
			}
		}
		return rrMap;
	}
	
	public ArrayList<String> calculateSourceSet(DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> g, int k, int r) {
		// initialize seed set s
		ArrayList<String> s = new ArrayList<>();
		// initialize distance map
		HashMap<Integer, Double> distanceMap = new HashMap<>();

		int n = g.vertexSet().size();
		String[] vertexArr = new String[n];
		g.vertexSet().toArray(vertexArr);
		
		long currentTime = System.currentTimeMillis();
		Random randomGenerator = new Random(currentTime);
		
		currentTime = System.currentTimeMillis();
		Random randomFilp = new Random(currentTime);
		// initialize reverse map array for the reverse maps.
//		HashMap<String, Double>[] rrMapArr = new HashMap[r];
		ArrayList<HashMap<String, Double>> rrMapArr = new ArrayList<>();
		for (int i = 0; i < r; i++) {
			String v = vertexArr[randomGenerator.nextInt(n)];
			rrMapArr.add(this.generateReverseReachableMap(g, v, randomFilp));
			distanceMap.put(i, Double.POSITIVE_INFINITY);
		}
		
		for (int i = 0; i < k; i++) {
			HashMap<String, Double> eff = new HashMap<>();
			for (int j = 0; j < r; j++) {
				HashMap<String, Double> rrMap = rrMapArr.get(j);
				for (String u : rrMap.keySet()) {				
					if (!s.contains(u)) {
						if (rrMap.get(u) < distanceMap.get(j)) {
							double marginalGain = 1.0 / rrMap.get(u) - 1.0 / distanceMap.get(j);
							if (eff.containsKey(u)) {
								eff.put(u, eff.get(u) + marginalGain);
							} else {
								eff.put(u, marginalGain);
							}
						} 
					}
				}
			}
			
			double maxEff = 0.0;
			String maxNode = new String("-1");
			for (String node : eff.keySet()) {
				if (eff.get(node) > maxEff) {
					maxEff = eff.get(node);
					maxNode = node;
				}
			}
			s.add(maxNode);		
		}
		
		return s;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		ArrayList<Integer> arr = new ArrayList<>();
//		for (int i = 0; i < 100; i++) {
//			arr.add(i);
//		}
//		System.out.println(arr.get(0));
		String fileName = args[0];
		DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> dirWgtGph = Utility.loadGraph(fileName);
		ReverseEfficiencySampling res = new ReverseEfficiencySampling();
		int k = 50;
		int n = dirWgtGph.vertexSet().size();
		Double samplingCnt = n*Math.log(Double.parseDouble(Integer.toString(n)));
		int r = samplingCnt.intValue();
		long startTime = System.currentTimeMillis();
		ArrayList<String> s = res.calculateSourceSet(dirWgtGph, k, r);
		long endTime = System.currentTimeMillis();
		long runTimeSec = (endTime - startTime)/1000;
		System.out.println("k = " + k + ", r = " + r + ", runtime = " + runTimeSec + " secs.");
		System.out.println(s);
	}

}

@@ -596,44 +596,36 @@
 Hash
-Map
+Set
 %3CString
-, Boolean%3E searchedNodeMap
+%3E activedVertexSet
  = n
@@ -623,35 +623,35 @@
 exSet = new Hash
-Map
+Set
 %3C%3E();%0A%09%09// initi
@@ -754,16 +754,43 @@
 ast(v);%0A
+%09%09activedVertexSet.add(v);%0A
 %09%09rrMap.
@@ -877,46 +877,8 @@
 ();%0A
-%09%09%09searchedNodeMap.put(vertex, true);%0A
 %09%09%09S
@@ -1114,23 +1114,24 @@
 f (!
-searchedNodeMap
+activedVertexSet
 .con
@@ -1127,35 +1127,32 @@
 rtexSet.contains
-Key
 (sourceVertex)) 
@@ -1226,24 +1226,102 @@
 inDegree) %7B%0A
+%09%09%09%09%09%09activedVertexSet.add(sourceVertex);%0A%09%09%09%09%09%09sDeque.addLast(sourceVertex);%0A
 %09%09%09%09%09%09double
@@ -1548,45 +1548,8 @@
 e);%0A
-%09%09%09%09%09%09%09sDeque.addLast(sourceVertex);%0A
 %09%09%09%09
@@ -2148,18 +2148,18 @@
  randomF
-i
 l
+i
 p = new 
@@ -2506,18 +2506,18 @@
  randomF
-i
 l
+i
 p));%0A%09%09%09
@@ -3294,16 +3294,16 @@
 %09%7D%0A%09%09%09%7D%0A
+
 %09%09%09s.add
@@ -3313,17 +3313,16 @@
 xNode);%09
-%09
 %0A%09%09%7D%0A%09%09%0A

fix an error.