package two;

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

import one.ClearUp;

/**
 * 对不符合弱社区定义的社区进行合并，选择与其连边数最多的社区进行合并
 * 弱社区定义：社区中所有节点与社区内部节点的度数之和大于社区中所有节点与社区外部节点连接的度数之和
 */
public class Merge_Low {
	//计算社区内部连接边数 弱社区定义：a * d(in) > d(out)，a默认为2,此处取1
	public List<List> merge_low(float[][] matrix, List<List> com) {		
		do {				
			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);
			}
			
			//遍历每个社区,判断是否为弱社区，如果不是就进行合并
			for (int i = 0; i < com_back.size(); i ++ ) {
				dout = new int[com_back.size()]; 	//初始化数组
				din = 0;							//每次循环都要将它重新赋值
				d = 0;
				
				for (int j = 0; j < com_back.get(i).size(); j ++ ) {
					//计算第i个社区的内度
					for (int k = j + 1; k < com_back.get(i).size(); k ++ ) {
						if (matrix[(int) com_back.get(i).get(j)][(int) com_back.get(i).get(k)] != 0) {
							din ++;
						}
					}
					//计算第i个社区的外度
					for (int s = 0; s < com_back.size(); s ++ ) {
						for (int t = 0; t < com_back.get(s).size(); t ++ ) {
							int x = (int) com_back.get(i).get(j);
							int y = (int) com_back.get(s).get(t);
							if (matrix[x][y] != 0 && s != i) {
								dout[s] ++;
								d ++;
							}
						}
					}
				}
				
				//判断弱社区
//				System.out.println(i + "的内度：" + din);
//				System.out.println(i + "的外度：" + d);
				max_d = 0; //社区i的外度最大的社区
				if (din * 1.5 < d) {
//					System.out.println(com_back.get(i) + "为弱社区");
					int res = 0;
					for (int k = 0; k < com.size(); k ++ ) {
						if (dout[k] > res) {
							res = dout[k];
							 max_d = k;
						}
					}

//					System.out.println(com_back.get(i) + "的最相似社区" +  max_d);
					com.get(i).addAll(com.get(max_d)); //合并
					com.get(max_d).clear();
				}
			}
			//一轮合并后对社区进行处理，清除空社区
			com = ClearUp.clearUp(com);
//			System.out.println("合并前社区：" + com_back);
//			System.out.println("合并后的社区：" + com);			
		} while (com_back.size() != com.size());
		return com;
	}
	
	List<List> com_back = new ArrayList();  //记录上一次的社区划分
	int din; //内度
	int[] dout; //存储对其他每个社区的度
	int d; //每个社区的外度之和
	int max_d; //存储与社区连接边数最多的社区的编号
}