sanitorysocial

#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;}
   }
}
}
//--------------------------------------------------