CNM算法C++实现

科技前沿 • 2025-01-17 08:47 • 阅读 111

大家好，我是讯享网，很高兴认识大家。

博主第一次写社团划分的算法，原本CNM算法应该是通过维护一个大根堆来实现的，因为对这个算法还没那么熟，所以用的普通方法和邻接矩阵来实现的。不过不管怎么说，算法的基于贪婪策略，根据模块度划分社团的核心思想一定是不变的。公式的话，应该已经有不少文章介绍，大家可以参考，我就只贴代码了。

#include<iostream> #include<cstring> #define N 110 #define INF  using namespace std; int n,M,row,col,A[N][N],book[N],root[N]; float delta_Q[N][N],a[N],Q,now_Q_change; void readData(); void initialize(); float themax(); void update_Q_delta(); void printResult(); int main() { cin>>n; Q=0; memset(book,0,sizeof(book)); readData(); initialize(); now_Q_change=themax(); //cout<<"now_Q_change是:"<<now_Q_change<<endl; while (now_Q_change>0) { //cout<<"(row,col):("<<row<<","<<col<<")"<<endl; book[col]=1; root[col]=row; cout<<"root["<<col<<"]:"<<row<<endl; cout<<"curmax:"<<now_Q_change<<endl; Q+=now_Q_change; update_Q_delta(); now_Q_change=themax(); cout<<"now_Q_change是:"<<now_Q_change<<endl; } printResult(); return 0; } void readData() { for (int i=1;i<=n;i++) root[i]=-1; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { cin>>A[i][j]; if (A[i][j]&&i>j) M++; } } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (A[i][j]!=0) { a[i]++; } delta_Q[i][j]=-INF; } } for (int i=1;i<=n;i++) { a[i]/=(2*M); } return; } void initialize() { float temp=0.5; temp/=M; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (A[i][j]>0) { delta_Q[i][j]=temp-a[i]*a[j]; } else delta_Q[i][j]=0; } } return ; } float themax() { float curmax=-INF; for (int i=1;i<=n;i++) { if (book[i]==1) continue; for (int j=1;j<=n;j++) { if (book[j]==1) continue; if (curmax<delta_Q[i][j]) { curmax=delta_Q[i][j]; row=i; col=j; } } } cout<<"(row,col):("<<row<<","<<col<<")"<<endl; return curmax; } void update_Q_delta() { //row行消失，只更新col行和col列，col列用col行对称过去即可 for (int i=1;i<=n;i++) { if (book[i]==1||col==i) continue; if (A[col][i]!=0&&A[row][i]!=0) { delta_Q[col][i]=delta_Q[col][i]+delta_Q[row][i]; } else if (A[col][i]!=0&&A[row][i]==0) { delta_Q[col][i]=delta_Q[col][i]-2*a[row]*a[i]; } else if (A[col][i]==0&&A[row][i]!=0) { delta_Q[col][i]=delta_Q[row][i]-2*a[col]*a[i]; } } for (int i=1;i<=n;i++) { if (book[i]==1) continue; delta_Q[i][col]=delta_Q[col][i]; } a[col]+=a[row]; return ; } void printResult() { cout<<"Q值为:"<<Q<<endl; for (int i=1;i<=n;i++) { cout<<"节点"<<i<<"的根为："<<root[i]<<endl; } for (int i=1;i<=n;i++) { int now=i; while (root[now]!=-1) { now=root[now]; } cout<<"节点"<<i<<"的根是节点："<<now<<endl; } return ; }

讯享网

测试数据及结果：

讯享网

CNM算法C++实现

相关推荐