<commit_before>/**
 * 
 */
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;
	}

	/**<commit_msg>fix an error.<commit_after>/**
 * 
 */
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<>();
		HashSet<String> activedVertexSet = new HashSet<>();
		// initialize reverse reachable dequeue
		Deque<String> sDeque = new ArrayDeque<String>();
		sDeque.addLast(v);
		activedVertexSet.add(v);
		rrMap.put(v, 1.0);
		while (sDeque.size() > 0) {
			String vertex = sDeque.removeFirst();
			Set<DefaultWeightedEdge> incomingEdges = g.incomingEdgesOf(vertex);
			int inDegree = g.inDegreeOf(vertex);
			for (DefaultWeightedEdge incomingEdge : incomingEdges) {
				String sourceVertex = g.getEdgeSource(incomingEdge);
				if (!activedVertexSet.contains(sourceVertex)) {
					double flip = randomFlip.nextFloat();
					if (flip < 1.0 / inDegree) {
						activedVertexSet.add(sourceVertex);
						sDeque.addLast(sourceVertex);
						double distance = rrMap.get(vertex) + g.getEdgeWeight(incomingEdge);
						if (!rrMap.containsKey(sourceVertex) || rrMap.containsKey(sourceVertex) && distance < rrMap.get(sourceVertex)) {
							rrMap.put(sourceVertex, distance);
						}
					}
				}
			}
		}
		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 randomFlip = 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, randomFlip));
			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;
	}

	/**
{'fraction_non_alphanumeric': 0.1392066557718021, 'fraction_numerical': 0.004456990046055564, 'mean_word_length': 3.5640677966101695, 'pattern_counts': {'":': 0, '<': 59, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4931828', 'n_tokens_mistral': 2747, 'n_tokens_neox': 2285, 'n_words': 495}