#include <math.h>
#include <string>
#include <iostream>
#include <fstream>
#include <cctype>
#include <time.h>
#include <stdio.h>
using namespace std;
int readstring(string a);
clock_t BeginTimer();
clock_t EndTimer(clock_t begin);
void writefile(string filename, int x, int y, double value);
void updatefile(string filename, int x, int y, double value);
double readfile(string filename, int x, int y);
int main()
{
double begin = BeginTimer();
cout<<"start timer"<<endl;
//-----------------------------------
ifstream instream, partition;
instream.open("sample2.net");
if(instream.is_open()){cout <<"open successful"<<endl;}
else{return 0;}
ofstream outfile("data4.txt");
if(outfile.is_open()){cout <<"open successful"<<endl;}
else{return 0;}
ofstream connectivitymatrix("connectivity matrix.txt");//clear connectivitymatrix
connectivitymatrix<<" ";
connectivitymatrix.close();
ofstream clustermatrix("cluster matrix.txt");//clear clustermatrix
clustermatrix<<" ";
clustermatrix.close();
ofstream gainmatrix("gain matrix.txt");//clear gainmatrix
gainmatrix<<" ";
gainmatrix.close();
ofstream nodesinnet("nodes in net.txt");//clear gainmatrix
nodesinnet<<" ";
nodesinnet.close();
//-----------------------------------------------------------------------------------
int nodes=0, nets=0, maxnodespernet=20, store[maxnodespernet],nodespernet=0, i=0, j=0, netscount=0;
string temp;
instream>>temp; instream>>nodes; instream>>temp; instream>>nets; instream>>temp;
for(i=0;i<nets;i++)//set file[][] to -1 //file will store every node in every net
{
for(j=0;j<maxnodespernet;j++)
{writefile("nodes in net.txt",i,j,-10000);}}
//---------------------------------------------------------
cout<<"writing connectivity matrix"<<endl;
if(nodes%2==1){nodes++;}//add another node if node# is odd. No affect because it is disconnected from others
for(i=0;i<nodes;i++)//set matrix[][] to 0
{
for(j=0;j<nodes;j++)
{
writefile("connectivity matrix.txt",i,j,-0.0000000011111111111111);}} //create space for undating data
//-----------------------------------------------------------------------------------------
while(1)
{
for(i=0;i<maxnodespernet;i++){store[i]=0;}//set store[] to 0, nodes'# will be stored.
instream>>netscount; instream>>temp; //cout<<"netscount "<<netscount<<endl;//find the net to work on
for(i=0;1;i++)
{
instream>>temp; if(instream.eof()){break;}//detecting the end of file
if(!isdigit(temp[0])){break;}else{store[i]=readstring(temp);
updatefile("nodes in net.txt", netscount, i, store[i]);
}
//file[netscount][i]=store[i];}//read nodes in a net
//cout<<"store["<<i<<"] "<<store[i]<<endl;
nodespernet++;
}//cout<<"nodespernet "<<nodespernet<<endl;//find out # of nodes per net
//-------------------------------------------------------------------------
for(i=0;i<nodespernet;i++)//write matrix clique model
{
for(j=nodespernet-1;j>i;j--)
{
double result = readfile("connectivity matrix.txt", store[i], store[j]);
result+=1/(double)nodespernet;
updatefile("connectivity matrix.txt", store[i], store[j], result);
// matrix[store[i]][store[j]]=matrix[store[i]][store[j]]+1/(double)nodespernet;
updatefile("connectivity matrix.txt", store[j], store[i], result);
// matrix[store[j]][store[i]]=matrix[store[i]][store[j]];//symmetry of the matrix
}
}nodespernet=0;//reset # of nodes per net for next measurement
if(netscount==nets-1){break;} //finish every net
}
//-----------------------------------------------------------------
cout<<"connectivity matrix done"<<endl;
instream.close();
//-----------------------------------------------------------------
cout<<"clusting"<<endl;
int cluster[nodes][2];//heavy edge cluster, each cluster contains two nodes
for(i=0;i<nodes;i++)//set cluster[][] to -1
{cluster[i][0]=-1; cluster[i][1]=-1;}
//-------------------------------------------------------------------
double heavyedge=-1; int clusternode=0, k=0, jmax=-1;
for(i=0;i<nodes;i++)//pick a node
{
for(k=0;k<nodes;k++)//check if the node has been clustered
{if(cluster[k][1]==i || cluster[k][0]==i){break;}}
if(cluster[k][1]!=i && cluster[k][0]!=i){//if not clustered select the node
cluster[clusternode][0]=i;
if(clusternode>=0.3*nodes)//cluster to 0.7 of origin size
{ //clusternode+nodes-2*clusternode<=0.7*nodes
cluster[clusternode][1]=cluster[clusternode][0];//treat unclustered cell as clustered with itself
}else{
for(j=0;j<nodes;j++)//find another node
{
for(k=0;k<nodes;k++)//check if the node has been clustered
{if(cluster[k][1]==j || cluster[k][0]==j){break;}}
double r1 = readfile("connectivity matrix.txt", i, j); //cout<<i<<" "<<j<<" "<<r1<<endl;
if(cluster[k][1]!=j && cluster[k][0]!=j && r1>heavyedge)//not clustered
{heavyedge=r1; jmax=j;}//find the order of the heaviest edge
}
heavyedge=-1;//reset heavyedge for next round measurement
cluster[clusternode][1]=jmax;//select the node with heaviest edges
}
clusternode++;
}
}
//----------------------------------------------------------------------------
for(i=0;i<nodes;i++)//set matrix2[][] to 0
{
for(j=0;j<nodes;j++)
{writefile("cluster matrix.txt",i,j,-0.0000000011111111111111);}}
//-----------------------------------------------------------------------------
int matrix2used=0;
for(i=0;i<nodes;i++)//matrix2[][] contains # of edges between 2 clusters
{
if(cluster[i][0]==-1){matrix2used=i; break;}//all cells done
for(j=i+1;j<nodes;j++)
{
if(cluster[j][0]==-1){break;}//all cells done
double r1 = readfile("connectivity matrix.txt", cluster[i][0], cluster[j][0]);
double r2 = readfile("connectivity matrix.txt", cluster[i][0], cluster[j][1]);
double r3 = readfile("connectivity matrix.txt", cluster[i][1], cluster[j][0]);
double r4 = readfile("connectivity matrix.txt", cluster[i][1], cluster[j][1]);
updatefile("cluster matrix.txt", i, j, r1+r2+r3+r4);
// matrix2[i][j]=r1+r2+r3+r4;
// matrix2[i][j]=matrix[cluster[i][0]][cluster[j][0]]+matrix[cluster[i][0]][cluster[j][1]]
// +matrix[cluster[i][1]][cluster[j][0]]+matrix[cluster[i][1]][cluster[j][1]];
if(cluster[i][0]==cluster[i][1])//for unclustered cell treated as clusted with itself, edges/2
{
double r6 = readfile("cluster matrix.txt", i, j);
updatefile("cluster matrix.txt", i, j, r6/2); }
//matrix2[i][j]/=2;}
double r5 = readfile("cluster matrix.txt", i, j);
updatefile("cluster matrix.txt", j, i, r5);
//matrix2[j][i]=matrix2[i][j];//symmetry of matrix2
}}
//--------------------------------------------------------------------------
if(matrix2used%2==1)//using KL algorithm
{cluster[matrix2used][0]=matrix2used; //if sizeA=sizeB+1,add a cluster to B
cluster[matrix2used][1]=matrix2used;
for(i=0;i<=matrix2used;i++)//The dummy cluster is disconnected from others
{
writefile("cluster matrix.txt",matrix2used,i,-0.0000000011111111111111);
writefile("cluster matrix.txt",i,matrix2used,-0.0000000011111111111111);
}
//{matrix2[matrix2used][i]=0; matrix2[i][matrix2used]=0;}
matrix2used++;//cluster added
}
cout<<"clustering done"<<endl;
//------------------------------------------------------------------------
int finalpartitionA[matrix2used/2], finalpartitionB[matrix2used/2];
for(i=0;i<matrix2used/2;i++)//set finalpartition[] to -1
{finalpartitionA[i]=-1; finalpartitionB[i]=-1;}
//--------------------------------------------------------------------
//--------------------------------------------------------------------
cout<<"KL partitioning"<<endl;
int round=0;
while(round<1)//# of round for KL
{
//--------------------------------------------------------------------------
int store4[matrix2used/2], store5[matrix2used/2];//store cluster partition A, B
for(i=0;i<matrix2used/2;i++){store4[i]=-1; store5[i]=-1;}//set store4,5[] to -1
if(round==0)//first random partition
{
j=0; k=0;
for(i=0;i<matrix2used;i++)//first partition, store even cluster in A, odd cluster in B
{
if(i%2==0){store4[j]=i; j++;}else{store5[k]=i;k++;}
}
}
else//select the best patition from previous KL as initial partition
{
for(i=0;i<matrix2used/2;i++)
{store4[i]=finalpartitionA[i]; store5[i]=finalpartitionB[i];}
}
cout<<endl;outfile<<endl;
//----------------------------------------------------------------------------
for(i=0;i<matrix2used;i++)//set gain matrix to -10000
{
for(j=0;j<matrix2used;j++)
{
writefile("gain matrix.txt",i,j,-111111111111111);
//matrixg[i][j]=-10000;
}}
//----------------------------------------------------------------------------
int fixedcluster[matrix2used];// swapped clusters will be fixed
for(i=0;i<matrix2used;i++)// set fixedcluster[] to -1
{fixedcluster[i]=-1;}
int swaps=0;//set # of swaps to 0
//-------------------------------------------------------------------------------
double record_gainmax=0, total_gain_in_a_round=0;
while(1) //swapping for most gain till every cluster is swapped
{
if(total_gain_in_a_round>record_gainmax){record_gainmax=total_gain_in_a_round;}
//-----------------------------------------------------------------------------
double d[matrix2used];//d=external edge#-internal edge#
for(i=0; i<matrix2used;i++){d[i]=0;}//set d[] to 0
int p=0, q=0;
for(i=0;i<matrix2used;i++)
{
for(p=0;p<matrix2used/2;p++)//cluster in A q==1, in B q==0
{q=0; if(store4[p]==i){q=1; break;}}
if(q==1)//if select a cluster in A
{
for(j=0;j<matrix2used;j++)
{
for(p=0;p<matrix2used/2;p++)//internal cluster Q==1, external Q==0
{q=0; if(store4[p]==j){q=1; break;}}
if(q==1)
{
double r7 = readfile("cluster matrix.txt", i, j);
d[i]-=r7;}
//{d[i]-=matrix2[i][j];}//subtract internal edges
else
{
double r8 = readfile("cluster matrix.txt", i, j);
d[i]+=r8;}
//{d[i]+=matrix2[i][j];}//add external edges
}}
else{//if select a cluster in B
for(j=0;j<matrix2used;j++)
{
for(p=0;p<matrix2used/2;p++)//internal cluster Q==1, external Q==0
{q=0; if(store5[p]==j){q=1; break;}}
if(q==1)
{
double r9 = readfile("cluster matrix.txt", i, j);
d[i]-=r9;}
//{d[i]-=matrix2[i][j];}//subtract internal edges
else
{
double r10 = readfile("cluster matrix.txt", i, j);
d[i]+=r10;}
//{d[i]+=matrix2[i][j];}//add external edges
}}}
//--------------------------------------------------------------------
cout<<"calculating gain"<<endl;
double gainmax=-10000; int imax=-1; jmax=-1;
for(i=0;i<matrix2used;i++)//find gain matrix & gainmax
{
for(j=i+1;j<matrix2used;j++)
{
double r11 = readfile("cluster matrix.txt", i, j);
updatefile("gain matrix.txt", i, j, d[i]+d[j]-2*r11);
//matrixg[i][j]=d[i]+d[j]-2*r11;
//matrixg[i][j]=d[i]+d[j]-2*matrix2[i][j];//gAB=dA+dB-2cAB
double r12 = readfile("cluster matrix.txt", i, j);
updatefile("gain matrix.txt", j, i, r12);
//matrixg[j][i]=matrixg[i][j];//symmetry of matrixg[][]
q=0;
for(p=0;fixedcluster[p]!=-1;p++)//find out if clusters are fixed
{if(fixedcluster[p]==i||fixedcluster[p]==j){q=1; break;}}
if(q==1){j++; break;}//we can't swap fixed cluster, find another cluster
double r13 = readfile("gain matrix.txt", i, j);
if(r13>gainmax)
//if(matrixg[i][j]>gainmax)//if find a bigger gain
{ q=0; //update the gain if 2 clusters are in different partition
for(p=0;p<matrix2used/2;p++)
{if(store4[p]==i){q=1; break;}}
if(q==1)//if cluster#i in store4[], cluster#j in store5[], update gain
{
for(p=0;p<matrix2used/2;p++)
{if(store5[p]==j){
double r14 = readfile("gain matrix.txt", i, j);
gainmax=r14;
//gainmax=matrixg[i][j];
imax=i; jmax=j; break;}}
}else{//if cluster#i in store5[], cluster#j in store4[], update gain
for(p=0;p<matrix2used/2;p++)
{if(store4[p]==j){
double r15 = readfile("gain matrix.txt", i, j);
gainmax=r15;
//gainmax=matrixg[i][j];
imax=i; jmax=j; break;}}
}}}}
//--------------------------------------------------------------------
total_gain_in_a_round+=gainmax;
//---------------------------------------------------------------------------------
for(i=0;i<matrix2used/2;i++)//swapping 2 clusters with max gain
{if(store4[i]==imax){store4[i]=jmax; break;} if(store4[i]==jmax){store4[i]=imax; break;}}
for(i=0;i<matrix2used/2;i++)
{if(store5[i]==imax){store5[i]=jmax; break;} if(store5[i]==jmax){store5[i]=imax; break;}}
//---------------------------------------------------------------------------
for(i=0;fixedcluster[i]!=-1;i++){}// find a place to store fixed cluster #
fixedcluster[i]=imax; fixedcluster[i+1]=jmax; //fix 2 swapped clusters
swaps++;//update # of swaps
//-----------------------------------------------------------------------------
if(total_gain_in_a_round>record_gainmax)//find the peak of total gain->check size criteria->update final partition
{
int partitionsize=0; //if 0.4<partitionsize/totalsize<0.6, new partition will be considered
for(i=0;i<matrix2used/2;i++)
{
if(cluster[store4[i]][0]==cluster[store4[i]][1])
{partitionsize++;}//a single node clustered with itself, partitionsize+1
else{partitionsize+=2;}//2 nodes cluster, partitionsize+2
}//cout<<"partitionsize "<<partitionsize<<endl;
if(0.4<=(double)partitionsize/(double)nodes && (double)partitionsize/(double)nodes<=0.6)
{
for(i=0;i<matrix2used/2;i++) //size criteria satisfied, update finalpartition
{finalpartitionA[i]=store4[i]; finalpartitionB[i]=store5[i];}
}
}
//------------------------------------------------------------------------
if(swaps==matrix2used/2){break;}//every cluster has been swapped
}
//------------------------------------------------------------------------
cout<<endl<<endl<<endl<<endl;
cout<<"round "<<round+1<<" done. Total net cut reduced "<<record_gainmax<<endl;
cout<<"final partition"<<endl;
outfile<<endl<<endl<<endl<<endl;
outfile<<"round "<<round+1<<" done. Total net cut reduced "<<record_gainmax<<endl;
outfile<<"final partition"<<endl;
for(i=0;i<matrix2used/2;i++)
{
cout<<cluster[finalpartitionA[i]][0];
if(cluster[finalpartitionA[i]][0]!=cluster[finalpartitionA[i]][1]){cout<<","<<cluster[finalpartitionA[i]][1];}
cout<<" ";
cout<<cluster[finalpartitionB[i]][0];
if(cluster[finalpartitionB[i]][0]!=cluster[finalpartitionB[i]][1]){cout<<","<<cluster[finalpartitionB[i]][1];}
cout<<endl;
outfile<<cluster[finalpartitionA[i]][0];
if(cluster[finalpartitionA[i]][0]!=cluster[finalpartitionA[i]][1]){outfile<<","<<cluster[finalpartitionA[i]][1];}
outfile<<" ";
outfile<<cluster[finalpartitionB[i]][0];
if(cluster[finalpartitionB[i]][0]!=cluster[finalpartitionB[i]][1]){outfile<<","<<cluster[finalpartitionB[i]][1];}
outfile<<endl;
}
//---------------------------------------------------------------------------
round++;
}
//----------------------------------------------------------------------------
//------------------------------------------------------------------------------
int netcut=0, A=0, B=0; //find netcut after partition
for(i=0;i<nets;i++)//select a net
{ A=0; B=0;
double r17 = readfile("nodes in net.txt", i, j);
for(j=0;r17!=-10000;j++)
{r17 = readfile("nodes in net.txt", i, j);
//for(j=0;file[i][j]!=-1;j++)//load node # in the net
//cout<<i<<"i "<<j<<"j "<<r17<<" ";
for(k=0;k<matrix2used/2;k++)//if nodes in the nets are in different partition, netcut++
{
if(r17==cluster[finalpartitionA[k]][0]||r17==cluster[finalpartitionA[k]][1]){A=1;break;}
if(r17==cluster[finalpartitionB[k]][0]||r17==cluster[finalpartitionB[k]][1]){B=1;break;}
// if(file[i][j]==cluster[finalpartitionA[k]][0]||file[i][j]==cluster[finalpartitionA[k]][1]){A=1;break;}
// if(file[i][j]==cluster[finalpartitionB[k]][0]||file[i][j]==cluster[finalpartitionB[k]][1]){B=1;break;}
}
if(A==1&&B==1){netcut++;}
}
}
//---------------------------------------------------------------------------
cout<<"final netcut "<<netcut<<endl;
outfile<<"final netcut "<<netcut<<endl;
//---------------------------------------------------------------------------
float elapTicks;
float elapMilli, elapSeconds;
elapTicks = EndTimer(begin); // stop the timer, and calculete the time taken
elapMilli = elapTicks/1000; // milliseconds from Begin to End
elapSeconds = elapMilli/1000; // seconds from Begin to End
cout<<"time elaplsed "<<elapSeconds<<"s"<<endl;
outfile<<"time elaplsed "<<elapSeconds<<"s"<<endl;
cout<<"done"<<endl;
outfile.close();
return 0;
}
//--------------------------------------------------
int readstring(string a)
{
int num=0;
for(char* b = &a[0];*b!='\0';b++){num=10*num+*b-'0';}
return num;
}
//--------------------------------------------------
clock_t BeginTimer()
{
//timer declaration
clock_t Begin; //initialize Begin
Begin = clock() * CLK_TCK; //start the timer
return Begin;
}
clock_t EndTimer(clock_t begin)
{
clock_t End;
End = clock() * CLK_TCK; //stop the timer
return End;
}
//------------------------------------------------------
void writefile(string filename, int x, int y, double value)
{
//cout<<"write "<<x<<","<<y<<" ";
ofstream file;
file.open(filename.c_str(), fstream::app);
file<<" : "<<x<<" "<<y<<" "<<value<<endl;//leave space before colon for data update
file.close;
}
//----------------------------------------------------
double readfile(string filename, int x, int y)
{
//cout<<"read "<<x<<","<<y<<" ";
string colon;
int a=-1, b=-1;
double result;
ifstream file;
file.open(filename.c_str());
file>>colon;
while(1)
{
file>>a>>b;
if(a==x && b==y)
{
file>>result;
file.close();
return result;
}else{
file>>colon;
while(colon[0]!=':'){file>>colon;}
}
}
}
//----------------------------------------------------
void updatefile(string filename, int x, int y, double value)
{
string colon;
int a=-1, b=-1;
int position;
fstream file;
file.open(filename.c_str(), ios::out | ios::in);
//cout<<"update "<<x<<","<<y<<" ";
file>>colon;
while(1)
{
file>>a>>b;
if(a==x && b==y)
{
position=file.tellg();
file.seekg (position);
for(char a='a';a!=' ';)
{
a = file.get();
file.seekg (position);
position--;
}
file.seekg (position+2);
file<<" "<<value<<" ";
file.close();
return;
}else{
file>>colon;
while(colon[0]!=':'){file>>colon;}
}
}
}
//--------------------------------------------------
No comments:
Post a Comment