gn算法的java实现

import java.io.*; import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.SQLException; import java.sql.Statement; import java.util.*; import javax.servlet.ServletException; import javax.servlet.annotation.WebServlet; import javax.servlet.http.HttpServlet; import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; import java.io.IOException; @WebServlet(name = "dataPreprocessing", urlPatterns = "/dataPreprocessing") public class dataPreprocessing extends HttpServlet { private double[][] linkMatrix;// 原始数据，在算法中不断删除边 private double[][] originMatrix;// 用于存储原始数据 public List<Double> Qlist;// Q的集合 public List<edgeInfo> deleteEgdes;// 删除的边 public ArrayList<nodeInfo> previousNodes;// Gn算法中一次已经成功入队的节点 public ArrayList<nodeInfo> currentNodes;// Gn算法中的当前节点 public ArrayList<ArrayList<nodeInfo>> resultList; public ArrayList<nodeInfo> record;// Gn算法中上一次访问过节点 public double[] disArray;// Gn算法中一次的各个边的距离 public double[] weightArray;// Gn算法中一次的各边的权重 public double[][] disMatrix;// 用于记录源节点与其他节点的距离 public double[][] sumDisMatix;// 记录边介数 private int MAX_NUM;// 最大的数目 private int coperationNum;// 统计社团的数目 private int[] belong;// 用于区别节点所述社团 // 节点对象 public class nodeInfo { public List<Integer> parentNodes;// 父节点 public List<Integer> childrenNodes; // 子节点 public int name; // public double weightOfNode;//点权, public nodeInfo(int n) { parentNodes = new ArrayList<Integer>(); childrenNodes = new ArrayList<Integer>(); name = n; // weightOfNode=1; } } // 边对象 private class edgeInfo { public int start;// 开始的节点 public int end;// 结束的节点 public double weightOfEdge;// 边权 public void setInfo(int a, int b, double c) { this.start = a; this.end = b; this.weightOfEdge = c; } } // 初始化变量 private void inits() { MAX_NUM = 110; linkMatrix = new double[MAX_NUM][MAX_NUM]; originMatrix = new double[MAX_NUM][MAX_NUM]; Qlist = new ArrayList<Double>(); deleteEgdes = new ArrayList<edgeInfo>(); resultList = new ArrayList<ArrayList<nodeInfo>>(); } private nodeInfo findNodeInfoById(int n, ArrayList<nodeInfo> l) { for (int i = 0; i < l.size(); i++) { if (l.get(i).name == n) return l.get(i); } return null; } // 计算权值并保存初始矩阵 public void calWeights() { double max = 0; double min = 0; for (int i = 0; i < MAX_NUM; i++) { for (int j = 0; j < MAX_NUM; j++) { linkMatrix[i][j] = linkMatrix[i][j];// 输入自己的赋值语句，计算linkMatrix矩阵 } } /* * for(int i=0;i<MAX_NUM;i++) for(int j=0;j<MAX_NUM;j++) * if(max<linkMatrix[i][j]) { max=linkMatrix[i][j]; * //System.out.print(max+" "+"i"+i+" j"+j+"\n"); } for(int i=0;i<MAX_NUM;i++) * for(int j=0;j<MAX_NUM;j++) if(min>linkMatrix[i][j]) { min=linkMatrix[i][j]; } * for(int i=0;i<MAX_NUM;i++) { for(int j=0;j<MAX_NUM;j++) { * linkMatrix[i][j]=(linkMatrix[i][j]-min)/(max-min); } } */ for (int i = 0; i < MAX_NUM; i++) { for (int j = 0; j < MAX_NUM; j++) { originMatrix[i][j] = linkMatrix[i][j]; } } } public boolean isNodeOut(int n) { for (int i = 0; i < MAX_NUM; i++) { if (linkMatrix[n][i] > 0) return false; } return true; } public void calGn() { while (true) { sumDisMatix = new double[MAX_NUM][MAX_NUM]; coperationNum = 0; belong = new int[MAX_NUM]; // 使用GN算法计算每一个点，从而得出边介数 for (int i = 0; i < MAX_NUM; i++) if (isNodeOut(i) == false) { calOneNodeGn(i); } double max = 0; int x = 0, y = 0; // 累加Q值 for (int i = 0; i < MAX_NUM; i++) for (int j = 0; j < MAX_NUM; j++) { if (linkMatrix[i][j] > 0) sumDisMatix[i][j] = sumDisMatix[i][j] / linkMatrix[i][j]; else { sumDisMatix[i][j] = 0; } } for (int i = 0; i < MAX_NUM; i++) for (int j = 0; j < MAX_NUM; j++) if (max < sumDisMatix[i][j]) { max = sumDisMatix[i][j]; x = i; y = j; } if (max == 0) { break; } calQ(); deleEdge(x, y); } // 查找最大的Q值，此时为最佳划分 double maxq = 0; int index = 0; for (int i = 0; i < Qlist.size(); i++) { if (maxq < Qlist.get(i)) { maxq = Qlist.get(i); index = i; } } System.out.print("maxQ:" + maxq + " " + "index:" + index); } public double calQ() { double Q = 0; double M = 0; double sum = 0; double[] k = new double[MAX_NUM]; for (int i = 0; i < MAX_NUM; i++) for (int j = 0; j < MAX_NUM; j++) { M += linkMatrix[i][j]; } M = M / 2; for (int i = 0; i < MAX_NUM; i++) for (int j = 0; j < MAX_NUM; j++) if (linkMatrix[i][j] > 0) { k[i] += linkMatrix[i][j]; } for (int i = 0; i < MAX_NUM; i++) for (int j = 0; j < MAX_NUM; j++) { if (belong[i] == belong[j]) sum += (linkMatrix[i][j] - k[i] * k[j] / (2 * M)); } Q = sum / (2 * M); Qlist.add(Q); // System.out.print(Q+"\n"); return Q; } // 计算一个节点 public void calOneNodeGn(int n) { if (isNodeOut(n) == true) return; disMatrix = new double[MAX_NUM][MAX_NUM]; previousNodes = new ArrayList<dataPreprocessing.nodeInfo>(); disArray = new double[MAX_NUM]; weightArray = new double[MAX_NUM]; Boolean isStop = false; int deep1 = 2; currentNodes = new ArrayList<dataPreprocessing.nodeInfo>(); singleNodeGNFirst(new nodeInfo(n), 1); // 不断往下寻找，建立以节点n为源节点的树 while (isStop == false) { isStop = true; record = currentNodes; currentNodes = new ArrayList<dataPreprocessing.nodeInfo>(); for (int i = 0; i < record.size(); i++) { boolean ldl = singleNodeGN(record.get(i), deep1);// 如果还有子节点，继续循环 if (ldl == true) isStop = false; } deep1++; // System.out.print(previousNodes.size()+"\n"); } for (int i = 0; i < previousNodes.size(); i++) { nodeInfo ne = previousNodes.get(i); if (ne.childrenNodes.size() == 0) for (int j = 0; j < ne.parentNodes.size(); j++) { int x = ne.parentNodes.get(j); disMatrix[i][x] = weightArray[x] / weightArray[i]; disMatrix[x][i] = disMatrix[i][x]; } } // 对叶子节点进行赋初值 double max = 0; int num = 0; for (int i = 0; i < MAX_NUM; i++) if (max < disArray[i]) { max = disArray[i]; num = i; } // 此时把previousNodes中与最后一个相同的节点归为同一社团，并且标记 int first = previousNodes.size() - 1; if (belong[first] == 0) { coperationNum++; belong[first] = coperationNum; } for (int i = previousNodes.size() - 1; i >= 0; i--) { int x = previousNodes.get(i).name; if (belong[x] == 0) belong[x] = coperationNum; } // 进行第二步,计算各边的权重 for (int i = previousNodes.size() - 1; i >= 0; i--) singleSencondStep(previousNodes.get(i).name, n); // 计算边介数 for (int i = 0; i < MAX_NUM; i++) for (int j = 0; j < MAX_NUM; j++) { sumDisMatix[i][j] += disMatrix[i][j]; } } // 计算各边的权重 public void singleSencondStep(int n, int source) { nodeInfo neInfo = findNodeInfoById(n, previousNodes); for (int j = 0; j < neInfo.parentNodes.size(); j++) { nodeInfo pa = findNodeInfoById(neInfo.parentNodes.get(j), previousNodes); double q = 1; for (int k = 0; k < neInfo.childrenNodes.size(); k++) q += disMatrix[n][neInfo.childrenNodes.get(k)]; int x = neInfo.parentNod