package one;


import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Arrays;

/**
 * 实现了算法的过程 整体的过程是随机选取一个节点为初始节点，如果处理完了以后，再在剩下的里面随机选取一个节点为初始节点
 * first将初始节点和与它有最大相似度的节点进行合并
 * 按pc从小到大 
 */
public class Merge {

	@SuppressWarnings("unchecked")
	public Merge(float[][] matrix) {
		visited = new boolean[matrix.length];
		for (int i = 0; i < matrix.length; i++) {
			com.add(i, new ArrayList<Integer>()); // 初始化集合数组
			com.get(i).add(i); // 数组的第一个节点是自己本身
			visited[i] = false; // 记录该节点有没有被处理过
		}
	}

	// 已知一个节点，将它的相似度最大的节点加入
	// 比如节点0,最大相似度的节点为1,则将1所在社区和0所在社区合并
	// node为当前社区
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public void first(int node, List<List> similarity) {
		int sim_max = 0;
		visited[node] = true;
		Random rand = new Random();
		int x = rand.nextInt(similarity.get(node).size()); //随机选取一个与node相似度最大的节点
		sim_max = (Integer) similarity.get(node).get(x); // 相似度最大的节点
//		System.out.printf("%d %d\n", node, sim_max);

		// "包含"最大节点的社区与目标节点合并
		for (int j = 0; j < com_back.size(); j++) {
			//注注：考虑两个节点已经合并的情况
//			System.out.println("----" + com_back.size());
			if(j != node && com.get(j).contains(sim_max) && !com.get(j).contains(node)){
//				System.out.println("====" + com.get(j));
				//遍历查找node结点所在数组的下标
				int index = 0;
				for (int m = 0; m < com_back.size(); m ++)
					for (int n = 0; n < com_back.get(m).size(); n ++ )
						if (com_back.get(m).get(n).equals(node))
							index = m;
				//2021/4/28日修改
//				System.out.println("相似度最大点的标签(下标)" + j);
//				com.get(j).add(node);
//				remove(com.get(index), node);	
				
				com.get(j).addAll(com.get(index));
				com.get(index).clear();
				
//				com.get(index).addAll(com.get(j));
//				com.get(j).clear();
			}
		}
//		System.out.println("=====" + com);
	}

	public static void remove(List list, int node) {
		for(int i=0;i<list.size();i++) {
			if(list.get(i).equals(node)) {
				list.remove(i);
				i--;
			}
		}
	}


	//计算PC值
	public float[] calculate_PC(float[][] matrix, List<List> com) {
		sim_matrix = new SimilarityMatrix(matrix);
		degree = new int[matrix.length];
		
		
		degree_Com = new int[matrix.length][matrix.length];
		pc = new float[matrix.length];
		
		for (int i = 0; i < matrix.length; i ++ ) {
			degree[i] = sim_matrix.getDegree(matrix, i);
			for (int j = 0; j < com.size(); j ++ ) {
				for (int r = 0; r < com.get(j).size(); r ++ ) {
					if (matrix[i][(int) com.get(j).get(r)] != 0)
						degree_Com[i][j] += 1;
			//		System.out.println(degree_Com[i][j]);
				}	
				pc[i] += Math.pow((float)degree_Com[i][j] / degree[i], 2);
			//	System.out.println("****" + pc[i]);
			}
			pc[i] = 1 - pc[i];
		}	
//		for (int i = 0; i < pc.length; i ++ ) {
//			System.out.println("pc" + i + ": " +pc[i]);
//		}
		return pc;	
	}
	
	//判断list数组是否相同
	private boolean getDiffrent(List<List> list1, List<List> list2) {
        if (list1.size() != list2.size()) {
            return false;
        }
        for (int i = 0; i < list1.size(); i ++ ) {
        	if (list1.get(i).size() != list2.get(i).size()) 
        		return false;
        	if (list1.get(i).get(0) != list2.get(i).get(0))
        		return false;
        }
        return true;
    }	

	// 合并社区过程
	@SuppressWarnings({ "rawtypes" })
	public List<List> merge(float[][] matrix, List<List> similarity) {
		//记录社区是否发生变化
//		System.out.println("最初社区：" + com);
		do {
			//计算pc值 
			com_back.clear();
			//com_back = new ArrayList<List>(com);
			//注：不能用com_back = com,未赋值前com_back也会随com的变化而变化，应深拷贝  
			for (int k = 0; k < com.size(); ++k) {
				List list1 = new ArrayList(com.get(k));
				com_back.add(list1);
			}
			//----------------------------------------------------
			
			
				float[] pc = calculate_PC(matrix, com_back);
				boolean[] st = new boolean[pc.length];
				int index = 0;
				for (int k = 0; k < pc.length; k ++ ) {	
					float min = 1;  //pc值不会超过1
					for (int i = 0; i < pc.length; i ++ ) {
						if (pc[i] <= min && !st[i]) {
							min = pc[i];
							index = i;
						}
					}
					//每次找出pc值最小的结点
//					System.out.println("pc值最小的是" + index);
					st[index] = true;
//					System.out.println("+++++++++ ：" + com);
//					System.out.println("--------- ：" + com_back);
					first(index, similarity);
				}
	     
			
			
			for (int i = 0; i < matrix.length; i ++ )
				visited[i] = false;
//			System.out.println("合并前社区 ：" + com_back);
			// 处理结果(对com进行处理)   注：要放在一次合并之后
			com = ClearUp.clearUp(com);
//			System.out.println("第"+ time + "次合并后的社区：" + com);
			time ++;
			if (getDiffrent(com_back, com)) 
				end = false;
			else end = true;
		} while(end && time < 50);
		
		return com;
		// 计算模块度
		//float modu = UnsignedGlobalModularity.unsignedGlobalModularity(matrix, com);
		
	}

	SimilarityMatrix sim_matrix;
	int[] degree;	 //定义节点的度和
	int[][] degree_Com; //节点到社区的度
	float[] pc;
	@SuppressWarnings({ "rawtypes" })
	List<List> com = new ArrayList<List>();
	List<List> com_back = new ArrayList<List>();
	boolean[] visited; // 记录访问
	int time = 1; //迭代次数
	boolean end;
}