package org.dzhuang.dynamic.OtherAlgorithms;

import java.util.*;
import java.io.*;
import java.text.*;

import libsvm.*;
import org.dzhuang.dynamic.comm.NMI;
import org.dzhuang.dynamic.graph.*;
import org.dzhuang.dynamic.util.*;
import toolbox.*;
import toolbox.lr.*;
import toolbox.svm.*;

public class LearnIncSvm {
	
	svm_model model;  //the node SVM classification model
	
	ArrayList<Double> neighWeight;  //the weight from node u to its neighbor communities
	ArrayList<Integer> neighPos;  //the index of node u's neighbor communities
	double neighConnMax;  //the maximum connections from u to its neighbor communities
	int neighLast;
	
	public Graph g;  //the graph
	public ComGraph cg;  // The community graph (each node represents a community)
    public int size;  //the number of communities, during iterations, there may be empty communities
    ArrayList<Integer> n2c;  // the belonging ship from nodes to communities
    ArrayList<Double> n2cIn;  //the connections from each node to its current community
    ArrayList<Double> in, tot;  //the inner and total degree of the communities
    
    public static double MAX_MERGE_SIZE = 8;
	
	//The empty constructor
	public LearnIncSvm(){}
	
	/**
	 * Initialize the heuristic incremental algorithm
	 * @param graphPath
	 * @param comPath
	 * @param param - the parameters generated by the Logistic Regression Model
	 * @param comParam - the comParam is used to classify community nodes, while param is used to classify nodes
	 * @throws Exception
	 */
	public void init2(String graphPath, String comPath) throws Exception{
		readGraph(graphPath);
		readCommunity(comPath);
		initComGraph();
	}
	
	public void init(String graphPath, String comPath, svm_model model) throws Exception{
		this.model = model;
		readGraph(graphPath);
		readCommunity(comPath);
		initComGraph();
	}
	
	public void init(String graphPath, String comPath) throws Exception{
		System.out.println("Initializing...");
		readGraph(graphPath);
		System.out.println("Graph read! Nodes: " + g.nbNodes + "   Edges: " + g.totalWeight/2);
		readCommunity(comPath);
	}
	
	public HashMap increase(String incPath, int maxPoints, String commOutPath) throws Exception{
		HashMap resultMap = new HashMap();
		HashMap<String, Integer> nodeDict = g.nodeDict;
		ArrayList<Float> modList = new ArrayList();
		ArrayList<Float> timeList = new ArrayList();
		ArrayList<Integer> comList = new ArrayList();
		for(int point = 0; point < maxPoints; point++){
			long t1 = System.currentTimeMillis();
			File incFile = new File(FileUtil.extendFileName(incPath, "_" + (point+1)));
			if(!incFile.exists())
				break;
			ArrayList<Data> dataList = FileUtil.readData(incFile.getAbsolutePath());
			int start = 0;
			while(start < dataList.size()){
				TreeMap<Link, Double> deltaG = new TreeMap();
				start = readNextBatch(deltaG, dataList, start, FileUtil.BY_MONTH);  //read the next batch of incremental data into linkSet
				if(deltaG.size() == 0) // if there is no change
					continue;
				updateCommunityStructure(deltaG);
			}
			long t2= System.currentTimeMillis();
			double mod = modularity();
			float time = (float)(t2-t1)/1000;
			int communities = nonEmptyCommunities();
			this.writeCommunity(FileUtil.extendFileName(commOutPath, "_" + (point+1)));
			modList.add((float)mod);
			timeList.add(time);
			comList.add(communities);
			System.out.println("Q" + (point+1) + ": " + (float)mod + "   Time: " + time + "   Communities: " + communities);
			//outputCommunityStatistics();
		}
		resultMap.put("modList", modList);
		resultMap.put("timeList", timeList);
		resultMap.put("comList", comList);
		return resultMap;
	}
	
	public HashMap increaseNoComOutput(String incPath, int maxPoints, String dataSet) throws Exception{
		long t0_1 = System.currentTimeMillis();
		HashMap resultMap = new HashMap();
		HashMap<String, Integer> nodeDict = g.nodeDict;
		ArrayList<Double> modList = new ArrayList();
		ArrayList<Long> timeList = new ArrayList();
		ArrayList<Integer> comList = new ArrayList();
		long t0_2 = System.currentTimeMillis();
		for(int point = 0; point < maxPoints; point++){
			long t1 = System.currentTimeMillis();
			File incFile = new File(FileUtil.extendFileName(incPath, "_" + (point+1)));
			if(!incFile.exists())
				break;
			ArrayList<Data> dataList = FileUtil.readData(incFile.getAbsolutePath());
			//TODO
			this.model = svm.svm_load_model("data2/"+dataSet+"/"+dataSet+"_model_SVM_"+point+".txt");
			int start = 0;
			while(start < dataList.size()){
				TreeMap<Link, Double> deltaG = new TreeMap();
				start = readNextBatch(deltaG, dataList, start, FileUtil.BY_MONTH);  //read the next batch of incremental data into linkSet
				if(deltaG.size() == 0) // if there is no change
					continue;
				updateCommunityStructure(deltaG);
			}
			double mod = modularity();
			modList.add(mod);
			int communities = nonEmptyCommunities();
			comList.add(communities);
			String tmpComPath = "comm.tmp";
			this.writeCommunity(tmpComPath);
			this.writeCommunity("data2/"+dataSet+"/"+dataSet+"_LearnIncSVM_community_"+(point+1)+".txt");
			FileUtil.deleteFile(tmpComPath);
			long t2= System.currentTimeMillis();
			long time = t2-t1+t0_2-t0_1;
			timeList.add(time);
			System.out.println("Q" + (point+1) + ": " + mod + "   Time: " + time + "   Communities: " + communities);
			//outputCommunityStatistics();
		}
		resultMap.put("modList", modList);
		resultMap.put("timeList", timeList);
		resultMap.put("comList", comList);
		return resultMap;
	}
	
	public HashMap increasePeriod(String incPath, int periodMonth, String baseComPath) throws Exception{
		HashMap resultMap = new HashMap();
		HashMap<String, Integer> nodeDict = g.nodeDict;
		ArrayList<Float> modList = new ArrayList();
		ArrayList<Float> timeList = new ArrayList();
		ArrayList<Integer> comList = new ArrayList();
		ArrayList<Float> nmiList = new ArrayList();
		
		ArrayList<Data> dataList = new ArrayList();
		for(int point = 0; point < 10000; point++){
			File incFile = new File(FileUtil.extendFileName(incPath, "_" + (point+1)));
			if(!incFile.exists()){
				if(dataList.size() > 0){
					TreeMap<Link, Double> deltaG = new TreeMap();
					readBatch(deltaG, dataList, 0, periodMonth);
					dataList = new ArrayList();
					long t1 = System.currentTimeMillis();
					updateCommunityStructure(deltaG);
					long t2 = System.currentTimeMillis();
					double mod = modularity();
					float time = (float)(t2-t1)/1000;
					int communities = nonEmptyCommunities();
					String realComPath = FileUtil.extendFileName(baseComPath, "_" + (point));
					String tmpComPath = "comm.tmp";
					this.writeCommunity(tmpComPath);
					float nmi = (float)NMI.getNMI(realComPath, tmpComPath);
					modList.add((float)mod);
					timeList.add(time);
					comList.add(communities);
					nmiList.add(nmi);
					FileUtil.deleteFile(tmpComPath);
					System.out.println("Q" + (point+1) + ": " + (float)mod + "   Time: " + time + "   Communities: " + communities + "   NMI: " + nmi);
				}
				break;
			}
			dataList.addAll(FileUtil.readData(incFile.getAbsolutePath()));
			if((point+1) % periodMonth == 0){
				TreeMap<Link, Double> deltaG = new TreeMap();
				readBatch(deltaG, dataList, 0, periodMonth);
				dataList = new ArrayList();
				long t1 = System.currentTimeMillis();
				updateCommunityStructure(deltaG);
				long t2 = System.currentTimeMillis();
				double mod = modularity();
				float time = (float)(t2-t1)/1000;
				int communities = nonEmptyCommunities();
				String realComPath = FileUtil.extendFileName(baseComPath, "_" + (point+1));
				String tmpComPath = "comm.tmp";
				this.writeCommunity(tmpComPath);
				float nmi = (float)NMI.getNMI(realComPath, tmpComPath);
				modList.add((float)mod);
				timeList.add(time);
				comList.add(communities);
				nmiList.add(nmi);
				FileUtil.deleteFile(tmpComPath);
				System.out.println("Q" + (point+1) + ": " + (float)mod + "   Time: " + time + "   Communities: " + communities + "   NMI: " + nmi);
				//outputCommunityStatistics();
			}
		}
		resultMap.put("modList", modList);
		resultMap.put("timeList", timeList);
		resultMap.put("comList", comList);
		resultMap.put("nmiList", nmiList);
		return resultMap;
	}
	
	public HashMap increaseInitial(String incPath, int initPoint, String baseComPath) throws Exception{
		HashMap resultMap = new HashMap();
		HashMap<String, Integer> nodeDict = g.nodeDict;
		ArrayList<Float> modList = new ArrayList();
		ArrayList<Float> timeList = new ArrayList();
		ArrayList<Integer> comList = new ArrayList();
		ArrayList<Float> nmiList = new ArrayList();
		for(int point = initPoint; point < 10000; point++){
			long t1 = System.currentTimeMillis();
			File incFile = new File(FileUtil.extendFileName(incPath, "_" + (point+1)));
			if(!incFile.exists())
				break;
			ArrayList<Data> dataList = FileUtil.readData(incFile.getAbsolutePath());
			int start = 0;
			while(start < dataList.size()){
				TreeMap<Link, Double> deltaG = new TreeMap();
				start = readNextBatch(deltaG, dataList, start, FileUtil.BY_MONTH);  //read the next batch of incremental data into linkSet
				if(deltaG.size() == 0) // if there is no change
					continue;
				updateCommunityStructure(deltaG);
			}
			long t2= System.currentTimeMillis();
			double mod = modularity();
			float time = (float)(t2-t1)/1000;
			int communities = nonEmptyCommunities();
			String realComPath = FileUtil.extendFileName(baseComPath, "_" + (point+1));
			String tmpComPath = "comm.tmp";
			this.writeCommunity(tmpComPath);
			float nmi = (float)NMI.getNMI(realComPath, tmpComPath);
			modList.add((float)mod);
			timeList.add(time);
			comList.add(communities);
			nmiList.add(nmi);
			FileUtil.deleteFile(tmpComPath);
			System.out.println("Q" + (point+1) + ": " + (float)mod + "   Time: " + time + "   Communities: " + communities + "   NMI: " + nmi);
			//outputCommunityStatistics();
		}
		resultMap.put("modList", modList);
		resultMap.put("timeList", timeList);
		resultMap.put("comList", comList);
		resultMap.put("nmiList", nmiList);
		return resultMap;
	}
	
	public static Param readParam(String paramPath, int paramNum) throws Exception{
		Param param = new Param(paramNum, 0);
		BufferedReader br = new BufferedReader(new FileReader(paramPath));
		String str = br.readLine();
		str = str.substring(str.indexOf('=')+1);
		StringTokenizer token = new StringTokenizer(str, "[, ];");
		for(int i = 0; i < paramNum;i++){
			param.data[i] = new Double(token.nextToken());
		}
		br.close();
		return param;
	}
	
	public static double readPrecision(String paramPath) throws Exception{
		BufferedReader br = new BufferedReader(new FileReader(paramPath));
		String str = br.readLine();
		str = str.substring(str.indexOf('=')+1, str.lastIndexOf(';'));
		double precision = new Double(str);
		br.close();
		return precision;
	}
	
	public static double readRecall(String paramPath) throws Exception{
		BufferedReader br = new BufferedReader(new FileReader(paramPath));
		String str = br.readLine();
		str = br.readLine();
		str = str.substring(str.indexOf('=')+1, str.lastIndexOf(';'));
		double recall = new Double(str);
		br.close();
		return recall;
	}
	
	public void readGraph(String graphPath) throws Exception{
		this.g = new Graph(graphPath);
		neighWeight = new ArrayList();
        neighPos = new ArrayList();
        n2c = new ArrayList();
        n2cIn = new ArrayList();
        in = new ArrayList();
        tot = new ArrayList();
               
        size = g.nbNodes;
        
        neighWeight.ensureCapacity(size);
        neighPos.ensureCapacity(size);
        for(int i = 0; i < size; i++){
            neighWeight.add(new Double(-1.0));        
            neighPos.add(new Integer(-1));
        }
        neighLast = 0;
        
        n2c.ensureCapacity(size);
        n2cIn.ensureCapacity(size);
        in.ensureCapacity(size);
        tot.ensureCapacity(size);
        
        //initialize
        for(int i = 0; i < size; i++){
            n2c.add(i);
            n2cIn.add(0.0);
            tot.add(g.weightedDegree(i));
            in.add(g.nbSelfLoops(i));
        }
	}
	
	public void readCommunity(String commPath) throws Exception{
		BufferedReader br = new BufferedReader(new FileReader(commPath));
		String str = br.readLine();
		int commId = 0;
		while(str != null){
			StringTokenizer token = new StringTokenizer(str, "\t");
			while(token.hasMoreTokens()){
				int nodeId = g.nodeDict.get(token.nextToken());
				n2c.set(nodeId, commId);
			}
			commId++;
			str = br.readLine();
		}
		br.close();
		
		// update the tot and in of the community structure
		for(int i = 0; i < size; i++){
			tot.set(i, 0.0);
			in.set(i, 0.0);
		}
		for(int i = 0; i < g.nbNodes; i++){
			int srcCom = n2c.get(i);
			ArrayList<Pair<Integer, Double>> neighList = g.topology.get(i);
			for(int j = 0; j < neighList.size(); j++){
				Pair<Integer, Double> p = neighList.get(j);
				int dest = p.first;
				int destCom = n2c.get(dest);
				double w = p.second;
				if(srcCom == destCom){  //if i and dest are in the same community
					n2cIn.set(i, n2cIn.get(i) + w);
					in.set(srcCom, in.get(srcCom) + w);  //update in value of this community
				}
				tot.set(srcCom, tot.get(srcCom) + w);  //update the tot value of community C(i)
			}
		}
	}
	
	public void initComGraph(){
		cg = new ComGraph();
		for(int i = 0; i < g.topology.size(); i++){
			int srcCom = n2c.get(i);
			if(!cg.topology.containsKey(srcCom))
				cg.topology.put(srcCom, new ComNode());
			ComNode srcNode = cg.topology.get(srcCom);
			srcNode.size++;
			ArrayList<Pair<Integer, Double>> neighborList = g.topology.get(i);
			for(int j = 0; j < neighborList.size(); j++){
				Pair<Integer, Double> p = neighborList.get(j);
				int destCom = n2c.get(p.first);
				double w = p.second;
				if(srcCom == destCom){  //if i and j are in the same community
					srcNode.inK += w;
				}
				srcNode.totK += w;

				if(!srcNode.neighbors.containsKey(destCom)){
					srcNode.neighbors.put(destCom, w);
				}
				else{
					srcNode.neighbors.put(destCom, srcNode.neighbors.get(destCom) + w);
				}
				
				cg.totalWeight += w;
			}
		}
		cg.nbNodes = cg.topology.size();
	}
	
	public ArrayList<Data> readAllData(String incPath, int from) throws Exception{
		ArrayList<Data> dataList = new ArrayList();
		while(true){
			String incFilePath = FileUtil.extendFileName(incPath, "_" + from);
			File incFile = new File(incFilePath);
			if(!incFile.exists())
				break;
			dataList.addAll(FileUtil.readData(incFilePath));
		}
		return dataList;
	}
	
	//read the next batch of data, put them into a change graph represented by deltaG
	public int readNextBatch(TreeMap<Link, Double> deltaG, ArrayList<Data> dataList, int start, int periodType) throws Exception{
		int end = start;
		long startTime = dataList.get(start).timestamp;
		long endTime = startTime + 1;  //update by Second
		if(periodType == FileUtil.BY_MINUTE)
			endTime = startTime + 60;
		else if(periodType == FileUtil.BY_HOUR)
			endTime = startTime + 3600;
		else if(periodType == FileUtil.BY_DAY)
			endTime = startTime + 24 * 3600;
		else if(periodType == FileUtil.BY_WEEK)
			endTime = startTime + 7 * 24 * 3600;
		else if(periodType == FileUtil.BY_MONTH)
			endTime = DateUtil.nextMonth(startTime);
		else if(periodType == FileUtil.BY_TWO_MONTH)
			endTime = DateUtil.nextKMonth(startTime, 2);
		else if(periodType == FileUtil.BY_YEAR)
			endTime = startTime + 365 * 24 * 3600;
		//parse the data
		for(end = start; end < dataList.size(); end++){
			Data data = dataList.get(end);
			if(data.timestamp >= endTime)
				break;
			if(!g.nodeDict.containsKey(data.from))
				g.nodeDict.put(data.from, g.nodeDict.size());
			if(!g.nodeDict.containsKey(data.to))
				g.nodeDict.put(data.to, g.nodeDict.size());
			int src = g.nodeDict.get(data.from);
			int dest = g.nodeDict.get(data.to);
			Link link = new Link(src, dest);
			if(src < g.nbNodes && dest < g.nbNodes && g.linkMap.containsKey(link)){
				continue;
			}
			deltaG.put(link, 1.0);
		}
		return end;
	}
	
	/**
	 * Read the incremental data of several months
	 * @param deltaG
	 * @param dataList
	 * @param start
	 * @param periodMonth
	 * @return
	 * @throws Exception
	 */
	public int readBatch(TreeMap<Link, Double> deltaG, ArrayList<Data> dataList, int start, int periodMonth) throws Exception{
		int end = start;
		long startTime = dataList.get(start).timestamp;
		long endTime = DateUtil.nextKMonth(startTime, periodMonth);
		//parse the data
		for(end = start; end < dataList.size(); end++){
			Data data = dataList.get(end);
			if(data.timestamp >= endTime)
				break;
			if(!g.nodeDict.containsKey(data.from))
				g.nodeDict.put(data.from, g.nodeDict.size());
			if(!g.nodeDict.containsKey(data.to))
				g.nodeDict.put(data.to, g.nodeDict.size());
			int src = g.nodeDict.get(data.from);
			int dest = g.nodeDict.get(data.to);
			Link link = new Link(src, dest);
			if(src < g.nbNodes && dest < g.nbNodes && g.linkMap.containsKey(link)){
				continue;
			}
			deltaG.put(link, 1.0);
		}
		if(end == dataList.size() && dataList.get(end-1).timestamp < endTime)  //if the final batch of data is incomplete
			end = -1;
		return end;
	}
	
	/**
	 * update the community structure according to the change of the graph
	 * @param deltaG - the change of graph
	 * @throws Exception
	 */
	public void updateCommunityStructure(TreeMap<Link, Double> deltaG) throws Exception{
		//Firstly extend the capacity of the Graph and Community
		int oldNbNodes = g.nbNodes;  // oldNbNodes is used to identify the newly added nodes
		while(size < g.nodeDict.size()){
			cg.nbNodes++;
			ComNode comNode = new ComNode();
			comNode.size = 1;
			cg.topology.put(size, comNode);
			neighWeight.add(-1.0);
			neighPos.add(-1);
			n2c.add(n2c.size());
			n2cIn.add(0.0);
			in.add(0.0);
			tot.add(0.0);
			g.topology.add(new ArrayList<Pair<Integer, Double>>());
			g.nbNodes++;
			size++;
		}
		//read the change part of the graph from deltaG
		// we put links into an array because we will use them again
		Link links[] = (Link []) deltaG.keySet().toArray(new Link[deltaG.size()]);
		for(int i = 0; i < links.length; i++){
			Link link = links[i];
			double w = deltaG.get(link);
			//update the graph topology
			g.linkMap.put(new Link(link.src, link.dest), w);
            g.topology.get(link.src).add(new Pair(link.dest, w));
            g.nbLinks++;
            g.totalWeight += w;
            if(link.src != link.dest){
                g.topology.get(link.dest).add(new Pair(link.src, w));
                g.nbLinks++;
                g.totalWeight += w;
            }
		}
		// initialize the community structure by putting every new node into a singleton community
		TreeSet<Integer> nodeToUpdate = new TreeSet();
		for(int i = 0; i < links.length; i++){
			Link link = links[i];
			double w = deltaG.get(link);
			int srcCom = n2c.get(link.src);
			int destCom = n2c.get(link.dest);
			ComNode srcNode = cg.topology.get(srcCom);
			ComNode destNode = cg.topology.get(destCom);
			if(srcCom == destCom){
				in.set(srcCom, in.get(srcCom) + 2*w);
				srcNode.inK += 2*w;
				n2cIn.set(link.src, n2cIn.get(link.src) + w);
				n2cIn.set(link.dest, n2cIn.get(link.dest) + w);
			}
			tot.set(srcCom, tot.get(srcCom) + w);
			tot.set(destCom, tot.get(destCom) + 1*w);
			srcNode.totK += w;
			destNode.totK += w;
			if(srcNode.neighbors.containsKey(destCom)){
				srcNode.neighbors.put(destCom, srcNode.neighbors.get(destCom) + 1);
				destNode.neighbors.put(srcCom, destNode.neighbors.get(srcCom) + 1);
			}
			else{
				srcNode.neighbors.put(destCom, 1.0);
				destNode.neighbors.put(srcCom, 1.0);
			}
			cg.totalWeight += 2*w;
			nodeToUpdate.add(link.src);
			nodeToUpdate.add(link.dest);
		}
		
		//put the nodes in deltaG in to Priority Queue
		ArrayList<Integer> nodeList = new ArrayList();
		Iterator<Integer> it = nodeToUpdate.iterator();
		while(it.hasNext()){
			int node = it.next();
			SvmSample sample = getNodeSample(node);
			if(sample.type == SampleType.POSITIVE)
				nodeList.add(node);
		}
		//System.out.println("Move node: " + nodeList.size() + "/" + nodeToUpdate.size());
		while(nodeList.size() > 0){
			//System.out.println("Node to move: " + nodeList.size());
			HashSet<Integer> nextSet = refine(nodeList);  //the core step
			nodeList.clear();
			nodeList.addAll(nextSet);
		}
		
		//after the nodes are moved, we next move the communities

		HashMap<Integer, ArrayList<Integer>> c2n = getCommunityToNode();
		ArrayList<Integer> comList = new ArrayList();
		it = c2n.keySet().iterator();
		comList.addAll(c2n.keySet());
		//System.out.println("Move com: " + comList.size() + "/" + c2n.size());
		while(comList.size() > 0){
			//System.out.println("Com to move: " + comList.size());
			HashSet<Integer> nextSet = refineCom(c2n, comList);
			comList.clear();
			comList.addAll(nextSet);
		}
	}	
	
	public HashSet<Integer> refine(ArrayList<Integer> nodeList){
		ArrayList<Integer> orderList = Utility.randomOrderList(nodeList.size());
        HashSet<Integer> updateSet = new HashSet();
        int nbMoves = 0;
        //move node from its current community to the one which gives the maximum gain in modularity
        for(int nodeTmp = 0; nodeTmp < nodeList.size(); nodeTmp++){
            int node = nodeList.get(nodeTmp);
            int nodeComm = n2c.get(node);
            double wDegree = g.weightedDegree(node);

            neighComm(node);
            remove(node, nodeComm, neighWeight.get(nodeComm));
            
            int bestComm = nodeComm;
            double bestNbLinks = 0;
            double bestIncrease = 0;
            for(int i = 0; i < neighLast; i++){
                double increase = modularityGain(node, neighPos.get(i), neighWeight.get(neighPos.get(i)), wDegree);
                if(increase > bestIncrease){
                    bestComm = neighPos.get(i);
                    bestNbLinks = neighWeight.get(bestComm);
                    bestIncrease = increase;
                }
            }
            //before insert node into bestComm, we should update the cg
            if(bestComm != nodeComm){
            	for(int i = 0; i < neighLast; i++){
            		int neighCom = neighPos.get(i);
            		//System.out.println(neighWeight.get(neighCom));
            		if(neighCom != nodeComm){  //first move node out of nodeComm
            			cg.increaseWeight(nodeComm, neighCom, -1 * neighWeight.get(neighCom));
            		}
            	}
            	ComNode comNode = cg.topology.get(nodeComm);
            	comNode.inK -= 2 * neighWeight.get(nodeComm);
            	if(comNode.neighbors.containsKey(nodeComm))
            		comNode.neighbors.put(nodeComm, comNode.neighbors.get(nodeComm) - 2 * neighWeight.get(nodeComm));
            	comNode.totK -= wDegree;
            	comNode.size--;
            	for(int i = 0; i < neighLast; i++){
            		int neighCom = neighPos.get(i);
            		if(neighCom != bestComm){ // secondly move node into bestComm
            			cg.increaseWeight(bestComm, neighCom, neighWeight.get(neighCom));
            		}
            	}
            	ComNode bestNode = cg.topology.get(bestComm);
            	bestNode.inK += 2 * neighWeight.get(bestComm);
            	if(bestNode.neighbors.containsKey(bestComm))
            		bestNode.neighbors.put(bestComm, bestNode.neighbors.get(bestComm) + 2 * neighWeight.get(bestComm));
            	else
            		bestNode.neighbors.put(bestComm, 2 * neighWeight.get(bestComm));
            	bestNode.totK += wDegree;
            	bestNode.size++;
            	//If the community is empty, remove it.
            	if(comNode.totK == 0){
            		cg.removeEmptyComm(nodeComm);
            		//System.out.println("Community removed!");
            	}
            }
            insert(node, bestComm, bestNbLinks);
            n2cIn.set(node, bestNbLinks);
            if(bestComm != nodeComm){
            	nbMoves++;
            	ArrayList<Pair<Integer, Double>> neighbors = g.topology.get(node);
                for(int i = 0; i < neighbors.size(); i++){
                	Pair<Integer, Double> p = neighbors.get(i);
                	int neigh = p.first;
            		double w = p.second;
            		int neighCom = n2c.get(neigh);
            		if(neighCom == nodeComm)
            			n2cIn.set(neigh, n2cIn.get(neigh) - w);
            		else if(neighCom == bestComm)
            			n2cIn.set(neigh, n2cIn.get(neigh) + w);
            		SvmSample sample = getNodeSample(neigh);
            		if(sample.type == SampleType.POSITIVE)
            			updateSet.add(neigh);
                }
            }
        } 
        //System.out.println("nbMoves: " + nbMoves);
        return updateSet;
    }
	
	public HashSet<Integer> refineCom(HashMap<Integer, ArrayList<Integer>> c2n, ArrayList<Integer> comList){
		HashSet<Integer> updateSet = new HashSet();
		for(int comTmp = 0; comTmp < comList.size(); comTmp++){
			int com = comList.get(comTmp);
			ComNode node = cg.topology.get(com);
			if(node.size > MAX_MERGE_SIZE){
				continue;
			}
			double bestIncrease = 0;
			int bestCom = com;
			double bestConn = 0;
			Iterator<Map.Entry<Integer, Double>> it = node.neighbors.entrySet().iterator();
			while(it.hasNext()){
				Map.Entry<Integer, Double> entry = it.next();
				int neighCom = entry.getKey();
				if(neighCom == com)
					continue;
				double neighConn = entry.getValue();
				ComNode neighNode = cg.topology.get(neighCom);
//				if(neighNode.size > g.nbNodes/10)
//					continue;
				double increase = neighConn - node.totK * neighNode.totK / cg.totalWeight;
				if(increase > bestIncrease){
					bestIncrease = increase;
					bestCom = neighCom;
					bestConn = neighConn;
				}
			}
			if(bestCom != com){
				cg.mergeComm(com, bestCom, bestConn);
				mergeCommunity(c2n, com, bestCom, bestConn);
				if(cg.topology.get(bestCom).size <= MAX_MERGE_SIZE)
					updateSet.add(bestCom);  //put this updated community into update Set
				updateSet.remove(com);
				//System.out.println("Inc: " + Parameter.df.format(bestIncrease) + "Com merge: " + com + " -> " + bestCom);
			}
		}
		return updateSet;
	}
	
	public double modularity(){
        double q = 0;
        double m2 = (double)g.totalWeight;
        for(int i = 0; i < size; i++){
            if(tot.get(i) > 0){
                q += in.get(i)/m2 - Math.pow(tot.get(i).doubleValue()/m2, 2);
            }
        }
        return q;
    }
	
	public int nonEmptyCommunities(){
		TreeSet<Integer> comSet = new TreeSet();
		for(int i = 0; i < n2c.size(); i++){
			int com = n2c.get(i);
			comSet.add(com);
		}
		return comSet.size();
	}
    
    public double modularityGain(int node, int comm, double dnodecomm, double wDegree){
        double totc = tot.get(comm).doubleValue();  
        double degc = wDegree; 
        double m2 = g.totalWeight; 
        double dnc = dnodecomm;  
        return (dnc - totc*degc/m2);
    }
    
    public void remove(int node, int comm, double dnodecomm){
    	tot.set(comm, tot.get(comm) - g.weightedDegree(node));
        in.set(comm, in.get(comm) - 2*dnodecomm - g.nbSelfLoops(node));
        n2c.set(node, -1);
    }
    
    public void insert(int node, int comm, double dnodecomm){
        tot.set(comm, tot.get(comm) + g.weightedDegree(node));
        in.set(comm, in.get(comm) + 2*dnodecomm + g.nbSelfLoops(node));
        n2c.set(node, comm);
    }
    
    //move node form its current community to destCom
    public void move(int node, int destCom){
    	neighComm(node);
    	int srcCom = n2c.get(node);
    	double wDegree = g.weightedDegree(node);
    	remove(node, n2c.get(node), neighWeight.get(srcCom));
    	if(srcCom != destCom){
    		for(int i = 0; i < neighLast; i++){
        		int neighCom = neighPos.get(i);
        		if(neighCom != srcCom){  //first move node out of nodeComm
        			cg.increaseWeight(srcCom, neighCom, -1 * neighWeight.get(neighCom));
        		}
        	}
        	ComNode comNode = cg.topology.get(srcCom);
        	comNode.inK -= 2 * neighWeight.get(srcCom);
        	if(comNode.neighbors.containsKey(srcCom))
        		comNode.neighbors.put(srcCom, comNode.neighbors.get(srcCom) - 2 * neighWeight.get(srcCom));
        	comNode.totK -= wDegree;
        	comNode.size--;
        	for(int i = 0; i < neighLast; i++){
        		int neighCom = neighPos.get(i);
        		if(neighCom != destCom){ // secondly move node into bestComm
        			cg.increaseWeight(destCom, neighCom, neighWeight.get(neighCom));
        		}
        	}
        	ComNode bestNode = cg.topology.get(destCom);
        	bestNode.inK += 2 * neighWeight.get(destCom);
        	if(bestNode.neighbors.containsKey(destCom))
        		bestNode.neighbors.put(destCom, bestNode.neighbors.get(destCom) + 2 * neighWeight.get(destCom));
        	else
        		bestNode.neighbors.put(destCom, 2 * neighWeight.get(destCom));
        	bestNode.totK += wDegree;
        	bestNode.size++;
        	//If the community is empty, remove it.
        	if(comNode.totK == 0){
        		cg.removeEmptyComm(srcCom);
        		//System.out.println("Community removed!");
        	}
    	}
    	insert(node, destCom, neighWeight.get(destCom));
    	n2cIn.set(node, neighWeight.get(destCom));
    	//update n2cIn
    	ArrayList<Pair<Integer, Double>> neighbors = g.topology.get(node);
    	for(int i = 0; i < neighbors.size(); i++){
    		Pair<Integer, Double> p = neighbors.get(i);
    		int neigh = p.first;
    		double w = p.second;
    		int neighCom = n2c.get(neigh);
    		if(neighCom == srcCom)
    			n2cIn.set(neigh, n2cIn.get(neigh) - w);
    		else if(neighCom == destCom)
    			n2cIn.set(neigh, n2cIn.get(neigh) + w);
    	}
    }
    
    //create a new singleton community for the node
    public int insertSingleton(int node){
    	double k = g.weightedDegree(node);
    	int commId = 0;  //find a usable community id
    	while(tot.get(commId) > 0)
    		commId++;
    	tot.set(commId, k);
    	in.set(commId, 0.0);
    	n2c.set(node, commId);
    	return commId;
    }
    
    // generate the neighborhood communities of node
    // this operation will change list neighWeight, neighPos
    public void neighComm(int node){
        for(int i = 0; i < neighLast; i++)
            neighWeight.set(neighPos.get(i), -1.0);
        neighLast = 0;
        neighConnMax = 0;
        
        ArrayList<Pair<Integer, Double>> neighList = g.topology.get(node);
        
        int deg = g.nbNeighbors(node);
        //System.out.println("node: " + node + "   n2c: " + n2c.get(node));
        neighPos.set(0, n2c.get(node));
        neighWeight.set(neighPos.get(0), 0.0);
        neighLast = 1;
        
        for(int i = 0; i < deg; i++){
            int neigh = neighList.get(i).first;
            int neighComm = n2c.get(neigh);
            double neighW = neighList.get(i).second;
            
            if(neigh != node){
                if(neighWeight.get(neighComm).intValue() == -1){
                    neighWeight.set(neighComm, 0.0);
                    neighPos.set(neighLast++, neighComm);
                }
                neighWeight.set(neighComm, neighWeight.get(neighComm) + neighW);
                if(neighComm != neighPos.get(0) && neighWeight.get(neighComm) > neighConnMax)
                	neighConnMax = neighWeight.get(neighComm);
            }
        }
    }
    
    public HashMap<Integer, ArrayList<Integer>> getCommunityToNode(){
    	HashMap<Integer, ArrayList<Integer>> c2n = new HashMap();
    	for(int i = 0; i < g.nbNodes; i++){
    		int com = n2c.get(i);
    		if(!c2n.containsKey(com))
    			c2n.put(com, new ArrayList());
    		c2n.get(com).add(i);
    	}
    	return c2n;
    }
    
    //merge the community from srcCom to destCom
    public void mergeCommunity(HashMap<Integer, ArrayList<Integer>> c2n, int srcCom, int destCom, double conn){
    	ArrayList<Integer> sList = c2n.get(srcCom);
    	ArrayList<Integer> dList = c2n.get(destCom);
    	
    	//firstly update n2cs
    	for(int i = 0; i < sList.size(); i++){
    		int node = sList.get(i);
    		int com = n2c.get(node);
    		ArrayList<Pair<Integer, Double>> neighbors = g.topology.get(node);
    		for(int j = 0; j < neighbors.size(); j++){
    			Pair<Integer, Double> p = neighbors.get(j);
    			int neigh = p.first;
    			double w = p.second;
    			int neighCom = n2c.get(neigh);
    			if(neighCom == destCom){
    				n2cIn.set(node, n2cIn.get(node) + w);
    				n2cIn.set(neigh, n2cIn.get(neigh) + w);
    			}
    		}
    	}
    	
    	for(int i = 0; i < sList.size(); i++){
    		n2c.set(sList.get(i), destCom);
    		dList.add(sList.get(i));
    	}
    	in.set(destCom, in.get(destCom) + in.get(srcCom) + 2*conn);
    	tot.set(destCom, tot.get(destCom) + tot.get(srcCom));
    	
    	in.set(srcCom, 0.0);
    	tot.set(srcCom, 0.0);
    	
    	sList.clear();
    }
    
    //get the sample of a node according to the Logistic Regression Model
    public SvmSample getNodeSample(int node){
    	double k = g.weightedDegree(node);
    	double kIn = n2cIn.get(node);
    	Sample sample = new Sample(new double[]{1, k, kIn}, SampleType.NEGATIVE);
    	sample.toLogValue(1);
    	SvmSample s = ClassifierUtil.parseSvmSample(sample);
    	double v = svm.svm_predict(model, s.x);
    	if(v > 0)
    		s.type = SampleType.POSITIVE;
    	return s;
    }
    
    public void outputCommunityStatistics(){
    	int comNum = 0, maxSize=0, minSize=1000000;
    	float avgSize = 0;
    	HashMap<Integer, Integer> sizeMap = new HashMap();
    	ArrayList<Integer> sizeList = new ArrayList();
    	ArrayList<Float> modList = new ArrayList();
    	ArrayList<Float> inList = new ArrayList();
    	ArrayList<Float> totList = new ArrayList();
    	for(int i = 0; i <  n2c.size(); i++){
    		int com = n2c.get(i);
    		if(!sizeMap.containsKey(com))
    			sizeMap.put(com, 0);
    		sizeMap.put(com, sizeMap.get(com) + 1);
    	}
    	Iterator<Integer> it = sizeMap.keySet().iterator();
    	double m2 = g.totalWeight;
    	while(it.hasNext()){
    		int com = it.next();
    		int size = sizeMap.get(com);
    		double mod = in.get(com)/m2 - Math.pow(tot.get(com).doubleValue()/m2, 2);
    		if(size > maxSize)
    			maxSize = size;
    		if(size < minSize)
    			minSize = size;
    		sizeList.add(size);
    		modList.add((float)(mod * m2));
    		inList.add((float)in.get(com).doubleValue());
    		totList.add((float)tot.get(com).doubleValue());
    	}
    	//sort the results by community size
    	int tmp1;
    	float tmp2;
    	for(int i = 0; i < sizeList.size()-1; i++){
    		for(int j = i+1; j < sizeList.size(); j++){
    			if(sizeList.get(i) > sizeList.get(j) || (sizeList.get(i) == sizeList.get(j) && totList.get(i) > totList.get(j))){
    				Utility.listSwap(sizeList, i, j);
    				Utility.listSwap(modList, i, j);
    				Utility.listSwap(inList, i, j);
    				Utility.listSwap(totList, i, j);
    			}
    		}
    	}
    	int com8 = 0, com5 = 0;  //the number of communities which cotains 80% and 50% of the nodes
    	int totalSize = 0;
    	for(int i = sizeList.size()-1; i>=0; i--){
    		totalSize += sizeList.get(i);
    		if((double)totalSize / g.nbNodes < 0.8)
    			com8++;
    		if((double) totalSize / g.nbNodes < 0.5)
    			com5++;
    	}
    	comNum = sizeMap.size();
    	avgSize = g.nbNodes / comNum;
    	System.out.println("Modularity: " + (float)modularity() + "   M2: " + g.totalWeight);
    	System.out.println("#Communities: " + comNum + "   Average Size: " + avgSize + "   Max Size: " + maxSize + "   Min Size: " + minSize);
    	System.out.println("#Communities for 50% nodes: " + com5 + "   #Communities for 80% nodes: " + com8);
//    	System.out.println("size=" + sizeList + ";");
//    	System.out.println("Qc=" + modList + ";");
//    	System.out.println("in=" + inList + ";");
//    	System.out.println("tot=" + totList + ";");
    }
    
    public void writeCommunity(String outPath) throws Exception{
    	HashMap<Integer, String> revDict = Utility.reverseDict(g.nodeDict);
    	HashMap<Integer, ArrayList<Integer>> comToNode = new HashMap();
    	for(int i = 0; i < n2c.size(); i++){
    		int com = n2c.get(i);
    		if(!comToNode.containsKey(com))
    			comToNode.put(com, new ArrayList());
    		comToNode.get(com).add(i);
    	}
    	//write community
    	BufferedWriter bw = new BufferedWriter(new FileWriter(outPath));
    	Iterator<Integer> it = comToNode.keySet().iterator();
    	while(it.hasNext()){
    		int com = it.next();
    		ArrayList<Integer> nodeList = comToNode.get(com);
    		bw.write(revDict.get(nodeList.get(0)));
    		for(int i = 1; i < nodeList.size(); i++){
    			bw.write("\t" + revDict.get(nodeList.get(i)));
    		}
    		bw.write("\r\n");
    	}
    	bw.close();
    }
    
    public void writeGraph(String outPath) throws Exception{
    	HashMap<Integer, String> revDict = Utility.reverseDict(g.nodeDict);
    	TreeSet<LabelEdge> edgeSet = new TreeSet();
    	Iterator<Link> it = g.linkMap.keySet().iterator();
    	while(it.hasNext()){
    		Link link = it.next();
    		String from = revDict.get(link.src);
    		String to = revDict.get(link.dest);
    		LabelEdge edge = new LabelEdge(from, to);
    		edgeSet.add(edge);
    	}
    	//write graph
    	BufferedWriter bw = new BufferedWriter(new FileWriter(outPath));
    	Iterator<LabelEdge> it1 = edgeSet.iterator();
    	while(it1.hasNext()){
    		LabelEdge edge = it1.next();
    		bw.write(edge.src + "\t" + edge.dest + "\t1\r\n");
    	}
    	bw.close();
    }
	
	/**
	 * 
	 * @author shangjiaxing
	 *
	 */
	public class Graph{
		HashMap<String, Integer> nodeDict;  //mapping the node label (String) to node id (Integer)
		public int nbNodes; //number of nodes
	    public int nbLinks; //number of edges;
	    public double totalWeight;  //sum of the weight of the links*2 (each link is calculated twice)
	    
	    ArrayList<ArrayList<Pair<Integer, Double>>> topology;  //The matrix of the graph, the neighbors of i is denoted as topology.get(i)
	    TreeMap<Link, Double> linkMap;
	    
	    public Graph(){
	        nbNodes = 0;
	        nbLinks = 0;
	        totalWeight = 0;
	        topology = new ArrayList();
	    }
	    
	    public Graph(String graphPath) throws Exception{
	    	nodeDict = FileUtil.getDict(graphPath);
	    	nbNodes = nodeDict.size();
	        topology = new ArrayList();
	        BufferedReader br = new BufferedReader(new FileReader(graphPath));
	        topology.ensureCapacity(nbNodes);
	        this.linkMap = new TreeMap();
	        for(int i = 0; i < nbNodes; i++)
	            topology.add(new ArrayList());
	        nbLinks = 0;
	        totalWeight = 0;
	        
	        String str = br.readLine().trim();
	        while(str != null && !str.equals("")){
	        	StringTokenizer token = new StringTokenizer(str, "\t");
	        	int src = nodeDict.get(token.nextToken());
	        	int dest = nodeDict.get(token.nextToken());
	            double weight = new Double(token.nextToken());
	            linkMap.put(new Link(src, dest), weight);
	            topology.get(src).add(new Pair(dest, weight));
	            nbLinks++;
	            totalWeight += weight;  //to support weighted network
	            if(src != dest){
	                topology.get(dest).add(new Pair(src, weight));
	                nbLinks++;
	                totalWeight += weight;
	            }
	            str = br.readLine();
	        }
	        br.close();
	    }
	    
//	    public double weightedDegree(int node){
//	        double wDegree = 0;
//	        ArrayList<Pair<Integer, Double>> neighList = topology.get(node);
//	        for(int i = 0; i < neighList.size(); i++){
//	        	wDegree += neighList.get(i).second;
//	        }
//	        return wDegree;
//	    }
	    
	    public double weightedDegree(int node){
	    	return (double)g.topology.get(node).size();
	    }
	   
	    public int nbNeighbors(int node){
	        return topology.get(node).size();
	    }
	    
	    public double nbSelfLoops(int node){
	        ArrayList<Pair<Integer, Double>> neighList = topology.get(node);
	        for(int i = 0; i < neighList.size(); i++){
	        	Pair<Integer, Double> p = neighList.get(i);
	        	if(node == p.first.intValue())
	        		return p.second;
	        }
	        return 0;
	    }
	    
	    public int getNbNodes(){
	    	return nbNodes;
	    }
	    
	    public int getNbLinks(){
	    	return nbLinks;
	    }
	    
	    public ArrayList<ArrayList<Pair<Integer, Double>>> getTopology(){
	    	return topology;
	    }
	    
	    public double getTotalWeight(){
	    	return totalWeight;
	    }
	}
	
	/**
	 * The community graph, where nodes represent communities and edges represent 
	 * the connections among communities
	 * @author shangjiaxing
	 *
	 */
	public class ComGraph{
		public int nbNodes;
		public double totalWeight;
		public HashMap<Integer, ComNode> topology;
		
		public ComGraph(){
			topology = new HashMap();
		}
		
		public double modularity(){
			double q = 0;
			double m2 = totalWeight;
			Iterator<Map.Entry<Integer, ComNode>> it = topology.entrySet().iterator();
			while(it.hasNext()){
				Map.Entry<Integer, ComNode> entry = it.next();
				ComNode node = entry.getValue();
				if(node.totK > 0)
					q += node.inK / m2 - Math.pow(node.totK/m2, 2);
			}
			return q;
		}
		
		public double modularity2(){
			double q = 0;
			double m2 = totalWeight;
			double total = 0;
			Iterator<Map.Entry<Integer, ComNode>> it = topology.entrySet().iterator();
			while(it.hasNext()){
				Map.Entry<Integer, ComNode> entry = it.next();
				int com = entry.getKey();
				double in = 0, tot = 0;
				ComNode node = entry.getValue();
				Iterator<Map.Entry<Integer, Double>> subIt = node.neighbors.entrySet().iterator();
				while(subIt.hasNext()){
					Map.Entry<Integer, Double> subEntry = subIt.next();
					int destCom = subEntry.getKey();
					double w = subEntry.getValue();
					if(com == destCom)
						in += w;
					tot += w;
					total += w;
				}
				if(node.totK > 0)
					q += in / m2 - Math.pow(tot/m2, 2);
			}
			//System.out.println("m2: " + m2 + "   Total: " + total);
			return q;
		}
		
		public void removeEmptyComm(int comId){
			ComNode node = topology.get(comId);
			Iterator<Map.Entry<Integer, Double>> it = node.neighbors.entrySet().iterator();
			while(it.hasNext()){
				Map.Entry<Integer, Double> entry = it.next();
				int destCom = entry.getKey();
				if(destCom != comId){
					topology.get(destCom).neighbors.remove(comId);
				}
			}
			topology.remove(comId);
			nbNodes--;
		}
		
		//merge the src community to the dest community
		public void mergeComm(int srcCom, int destCom, double conn){
			ComNode srcNode = topology.get(srcCom);
			ComNode destNode = topology.get(destCom);
			Iterator<Map.Entry<Integer, Double>> it = srcNode.neighbors.entrySet().iterator();
			while(it.hasNext()){
				Map.Entry<Integer, Double> entry = it.next();
				int neighCom = entry.getKey();
				double neighW = entry.getValue();
				if(neighCom != destCom && neighCom != srcCom){
					increaseWeight(neighCom, destCom, neighW);
				}
			}
			if(destNode.neighbors.containsKey(destCom))
				destNode.neighbors.put(destCom, destNode.neighbors.get(destCom) + srcNode.inK + 2 * conn);
			else destNode.neighbors.put(destCom, srcNode.inK + 2*conn);
			destNode.inK += srcNode.inK + 2 * conn;
			destNode.totK += srcNode.totK;
			destNode.size += srcNode.size;
			removeEmptyComm(srcCom);
		}
		
		public void increaseWeight(int srcCom, int destCom, double deltaW){
			ComNode srcNode = topology.get(srcCom);
			ComNode destNode = topology.get(destCom);
			if(!srcNode.neighbors.containsKey(destCom)){
				srcNode.neighbors.put(destCom, 0.0);
				destNode.neighbors.put(srcCom, 0.0);
			}
			srcNode.neighbors.put(destCom, srcNode.neighbors.get(destCom) + deltaW);
			destNode.neighbors.put(srcCom, destNode.neighbors.get(srcCom) + deltaW);
		}
		
		public double getM2(){
			double m2 = 0;
			Iterator<Map.Entry<Integer, ComNode>> it = topology.entrySet().iterator();
			while(it.hasNext()){
				Map.Entry<Integer, ComNode> entry = it.next();
				ComNode node = entry.getValue();
				Iterator<Map.Entry<Integer, Double>> subIt = node.neighbors.entrySet().iterator();
				while(subIt.hasNext()){
					Map.Entry<Integer, Double> subEntry = subIt.next();
					double w = subEntry.getValue();
					m2 += w;
				}
			}
			return m2;
		}
		
	}
	
	/**
	 * The community node
	 * @author shangjiaxing
	 *
	 */
	class ComNode{
		double totK;  //the total degree of the community
		double inK;  //the inner degree, i.e., self-loops of the community
		double size;  //the number of nodes in the community
		HashMap<Integer, Double> neighbors;  //the neighbor communities, where the key is the community ID and the value is the connections among the two communities
		
		public ComNode(){
			totK = 0;
			inK = 0;
			size = 0;
			neighbors = new HashMap();
		}
	}
	
	/**
	 * 
	 * @param <T1>
	 * @param <T2>
	 */
	class Pair<T1, T2>{
	    public T1 first;
	    public T2 second;

	    public Pair(T1 first, T2 second){
	        this.first = first;
	        this.second = second;
	    }
	}
	
	class Link implements Comparable{
		int src;
		int dest;
		
		public Link(int src, int dest){
			if(src < dest){
				this.src = src;
				this.dest = dest;
			}
			else{
				this.src = dest;
				this.dest = src;
			}
		}
		
		public int compareTo(Object o){
			Link e = (Link)o;
			if(src < e.src){
				return -1;
			}
			else if(src > e.src){
				return 1;
			}
			else{
				if(dest < e.dest)
					return -1;
				else if(dest > e.dest)
					return 1;
				else
					return 0;
			}
		}
	}
	
}
