GN算法的实现

可以直接运行的代码，有详细文字说明,复杂网络中社团划分经典GN算法的实现

#include “MyGN.h“
#include “stdio.h“

int main（）{
	
	int ij;
	vector vec_relationship;//记录有链接的边。
	int max=0;//这个是max是点的个数
	
	//从文件input.txt读数据
	FILE *f_input = fopen（“input.txt“ “r“）;
	char *s = （char*）malloc（20）;
	char *c;
	
	if （f_input != NULL）
	{
		fgets（s 100 f_input）;
		
		int i = 0;
		
		for （i = 0; s[i] != ‘-‘; i++）
		{
			max = 10 * max + s[i] - 48;
		}
		
		while （feof（f_input） == 0）
		{
			fgets（s 100 f_input）;	
			
			int m = 0;
			int n = 0;
			
			for （i = 0; s[i] != ‘:‘; i++）
			{
				m = 10 * m + s[i] - 48;
			}
			for （i = i + 1; s[i] != ‘-‘; i++）
			{
				n = 10 * n + s[i] - 48;
			}
			
			V_side v_sd（m-1 n-1 1）;
			vec_relationship.push_back（v_sd）;
		}
		
	}
	
	fclose（f_input）;
	
	int *r_sign = new int[max];//记录矩阵中行号为i的元素（边）在vec_relationship 中出现的首索引
	//r_sign数组先统一赋值为-1
	for（i = 0; i < max; i++）
	{
		r_sign[i] = -1;
	}	
	
	GN_use::v_order（&vec_relationship r_sign max）;//对vec_relationship中的内容进行排序整理
	
	/*下面是GN算法的实现*/
	
	//当Q值最大时，Q_i存放数组result_temp[][]中对应的行号i，以便在输出结果的时候容易找到。		
	int Q_i=0;
	//result_temp_i是在存储各种Q值下分裂得到各个点的社团隶属情况要用到的行号下标变量，也就是数组result_temp[][]的行号下标，最后一次的分裂情况下的行号记录在result_temp_i中。
	int result_temp_i=0;
	//vec_result_temp数组每行下标0到max-1的是存放每个点隶属的集团号，存放每种Q 值下的分裂情况，每行对应一种情况，元素vec_result_temp.Q存放对应的Q值，		
	vector vec_result_temp; 
	//vec_V_remove_belong数组用来存放每次去除介数最大的边的隶属情况，比如v（ij）是在分裂为两个集团时去除的，则vec_V_remove_belong.x=i-1vec_V_remove_belong.x=j-1，若是
	//分裂为三个集团时去除的，则vec_V_remove_belong.belong_clique值为3
	vector vec_V_remove_belong;
	//若原始网络本身就是由几个孤立的社团构成的，original_community_alones+2是记录原始网络的孤立社团数目，
	//在vec_result_temp数组中，0到original_community_alones-1的行号记录的是原始网络中的社团检测情况。从行号为original_community_alones记录的是由于去除最大介数边的分裂情况。
	int original_community_alones=0;
	
	MyGN GN_DEAL（0）;
	
	GN_DEAL.GN_deal（&vec_relationshipr_signmax&vec_result_temp &vec_V_remove_belong）;//GN算法的入口函数
	
	original_community_alones=GN_DEAL.get_original_community_alones（）;
	Q_i=GN_DEAL.get_Q_i（）;
	result_temp_i=GN_DEAL.get_result_temp_i（）;
	
	//如果原始网络时由几个孤立社团构成，要输出
	//若原始网络本来是由几个孤立的社团组成的，要弄清楚，所求的社团数目是original_community_alones+1，因为original_community_alones的下标是从1开始的
	
	int k3out_temp=0;	
	if（original_community_alones!=0）{
		
		printf（“原始网络是由%d个孤立的社团构成的：\n“original_community_alones+1）;
		
		for（j=0; j		{
			printf（“\n集团%d：“（j+1））;
			for（k3=0; k3			{
				out_temp = vec_result_temp.at（original_community_alones-1）.point_belong_to[k3];
				if（out_temp==j）
				{
					printf（“%d  “k3+1）;
				}									
			}
			
		}	
	}
	else
	{
		for（int r_t = 0; r_t < max; r_t++）
			for（int c_t = r_t+1; c_t < max; c_t++ ）{
				GN_use::find_vec_index（r_t c_t r_sign &vec_relationship）;//int position = GN_use.position_find（r_tc_t）;
			}
			
			printf（“\n原始网络为：“）;
			
			for（i=0; i				printf（“%d  “i+1）;
			}
			
			printf（“\n\n“）;
	}
	
	//最后把分裂的最佳情况输出，注意Q_i

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     214016  2014-03-16 14:54  GN_c\Debug\GN.bsc

     文件     249904  2014-03-16 14:54  GN_c\Debug\GN.exe

     文件     274208  2014-03-16 14:54  GN_c\Debug\GN.ilk

     文件    1447744  2014-03-16 14:54  GN_c\Debug\GN.pch

     文件     476160  2014-03-16 14:54  GN_c\Debug\GN.pdb

     文件     139399  2014-03-16 14:54  GN_c\Debug\Test.obj

     文件          0  2014-03-16 14:54  GN_c\Debug\Test.sbr

     文件      66560  2014-03-16 14:54  GN_c\Debug\vc60.idb

     文件      94208  2014-03-16 14:54  GN_c\Debug\vc60.pdb

     文件        508  2013-04-20 10:11  GN_c\Dian.h

     文件       4673  2013-04-20 22:49  GN_c\GN.dsp

     文件        510  2013-04-19 16:16  GN_c\GN.dsw

     文件      74752  2014-03-16 14:59  GN_c\GN.ncb

     文件      53760  2014-03-16 14:59  GN_c\GN.opt

     文件       1007  2014-03-16 14:54  GN_c\GN.plg

     文件      16918  2013-04-21 10:24  GN_c\GN_use.h

     文件        552  2010-05-16 20:33  GN_c\input.txt

     文件      11542  2013-04-21 12:39  GN_c\MyGN.h

     文件        324  2013-04-20 10:02  GN_c\Point_belong.h

     文件       1054  2013-04-20 10:13  GN_c\Queue.h

     文件        366  2013-04-20 10:03  GN_c\S_remove_belong.h

     文件       7296  2014-03-12 17:05  GN_c\Test.cpp

     文件        608  2013-04-20 10:03  GN_c\V_side.h

     目录          0  2014-03-16 14:54  GN_c\Debug

     目录          0  2014-03-16 14:59  GN_c

----------- ---------  ---------- -----  ----

              3136069                    25