package two;

import java.util.ArrayList;
import java.util.List;

import one.ClearUp;

public class Merge_tryM {
	
	public float[] calculate_PC2(float[][] matrix, List<List> com) {
		pc2 = new float[com.size()];
		w_Com = new float[com.size()][com.size()];
		w_num = new float[com.size()];
		
		//计算两两社区的权重
		for (int i = 0; i < com.size(); i ++ ) {
			for (int j = 0; j < com.size(); j ++ ) {
				if (i != j) {
					for (int k = 0; k < com.get(i).size(); k ++)
						for (int t = 0; t < com.get(j).size(); t ++) {
							if (matrix[(int) com.get(i).get(k)][(int) com.get(j).get(t)] != 0)
								w_Com[i][j] += 1;
						}
				}
//			System.out.printf(w_Com[i][j] + " " );
			}
//			System.out.println();
		}
		
		for (int i = 0; i < com.size(); i ++) {
			for (int j = 0; j < com.size(); j ++ ) 
				w_num[i] += w_Com[i][j];
//			System.out.println(w_num[i]);
		}
				
		float num = 0; //用于存权重的平方和
		for (int i = 0; i < com.size(); i ++) {
			num = 0; //每从迭代清零
			for (int j = 0; j < com.size(); j ++ ) 
				 num += (float) Math.pow(w_Com[i][j], 2);
//			System.out.println("-------" + num);
			pc2[i] = (float) (1 - num / Math.pow(w_num[i], 2));
//			System.out.println("====" + pc2[i]);
		}		
		return pc2;
	}
	
	public List<List> merge_try(float[][] matrix, List<List> com) {
		do {
			//com_back.clear();
			com_back = new ArrayList();
			for (int k = 0; k < com.size(); k ++) {  //将com复制给com_back
				List list1 = new ArrayList(com.get(k));
				com_back.add(list1);
			}
			
			//**************采用模块度合并
			UnsignedGlobalModularity cm = new UnsignedGlobalModularity();
			M = cm.unsignedGlobalModularity(matrix, com_back);
//			System.out.println("合并前社区的模块度值为：" + M);
			
			
			//找出pc值最大的社区
			float[] pc2 = calculate_PC2(matrix, com);
			float max_pc2 = 0;  
			int index_pc2 = 0; //记录pc值最大的社区
			
			for (int i = 0; i < pc2.length; i ++ ) {
				if (pc2[i] > max_pc2) {
					max_pc2 = pc2[i];
					index_pc2 = i;
				}
			}
//			System.out.println("pc2值最大的社区：" + index_pc2);
		
			//把权重最大社区合并
//			float max_w = 0;
//			int index_w = 0;
//			for (int j = 0; j < com.size(); j ++ ) {
//				if (w_Com[index_pc2][j] > max_w) {  
//					max_w = w_Com[index_pc2][j];
//					index_w = j;
//				}		
//			}
//			System.out.println("权重最大的社区：" + index_w);
			
			for (int i = 0; i < com_back.size(); i ++ ) {
				if (i != index_pc2) {
					com = new ArrayList<List>();
					for (int k = 0; k < com_back.size(); k ++) {  //将com_back复制给com
						List list1 = new ArrayList(com_back.get(k));
						com.add(list1);
					}
					com.get(index_pc2).addAll(com.get(i));
					com.get(i).clear();
					com = ClearUp.clearUp(com);  //清除空白社区
//					System.out.println("***" + com);
					M1 = cm.unsignedGlobalModularity(matrix, com);
					if (M1 > M) {
						M = M1;
						com_max = new ArrayList<List>();
						for (int k = 0; k < com.size(); k ++) {  //将com_back复制给com
							List list1 = new ArrayList(com.get(k));
							com_max.add(list1);
						}
//						System.out.println("-----" + com_max);
					}
						
				}
			}
			
//			System.out.println("合并后社区的模块度值为：" + M);
		}while(M < M1);
		if (com_max != null)
			return com_max;
		else
			return com_back;
	}
	
	float[] pc2;
	float[][] w_Com; //社区和社区的连边权重
	float[] w_num; //某一社区到其他社区的权重之和
	List<List> com_back; 
	List<List> com_max;
	float M;
	float M1;

}