fm.cpp

一个用来进行分割的程序

// FM.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "node.h"
#include "LL.h"
#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define MAX 100

int left(node *nd);
void exchange(struct klnode &left,struct klnode &right);
int gain(struct klnode nd,int side);
int gg(struct klnode nd);
int cutnum();
void KL();
int iscon(struct klnode left,struct klnode right);

struct klnode{
int num;
bool lock;
};

struct klnode *bucket[2];
int len;
LL *vertex;
int main(int argc, char* argv[])
{
	FILE *file;
	node *nd;
	int i,j=0,k=0;
	int vi,vj;
	char str[MAX];
	if(argc==1)
	{
	printf("parameter error!\nsuch as:FM D:\\abc.net\n");
	return -1;
	}
    if((file=fopen(argv[1],"r+"))==NULL)
	 {
	 printf("open file error!\n");
	 return 0;
	 }
	memset(str,0,MAX);
    if((fgets(str,MAX,file))==NULL)
	{
	 printf("end of file!");
	 return 0;
	}
    sscanf(str,"len=%d",&len);
    bucket[0]=(struct klnode *)malloc(sizeof(struct klnode)*(len/2));
	bucket[1]=(struct klnode *)malloc(sizeof(struct klnode)*(len/2));
	for(i=0;i<len;i++)
	{
	  if(i<len/2)
	  {
	   bucket[0][j].num=i;
	   bucket[0][j].lock=false;
	   j++;
	  }
	  else
	  {
	  bucket[1][k].num=i;
	  bucket[1][k].lock=false;
	  k++;
	  }
	}
	vertex=new LL[len];
	memset(str,0,MAX);
	while((fgets(str,MAX,file)))
	{
	sscanf(str,"(%d,%d)",&vi,&vj);
	nd=new node(vj);
    vertex[vi].addhead(nd);
	nd=new node(vi);
	vertex[vj].addhead(nd);
	memset(str,0,MAX);
	}
    for(i=0;i<len;i++)
	{
	printf("node:%d-->",i); 
	for(j=0;j<vertex[i].getlength();j++)
	 printf("%d-->",vertex[i].getindex(j)->number);
	printf("NULL\n");
	}
	for(i=0;i<len/2;i++)
	printf("num=%d  gain=%d\n",bucket[0][i].num,gain(bucket[0][i],0));
	for(i=0;i<len/2;i++)
	printf("num=%d  gain=%d\n",bucket[1][i].num,gain(bucket[1][i],1));
    printf("original cut number:%d\n",cutnum());
	printf("after KL!\n");
	KL();
	for(i=0;i<len/2;i++)
	printf("num=%d  gain=%d\n",bucket[0][i].num,gain(bucket[0][i],0));
	for(i=0;i<len/2;i++)
	printf("num=%d  gain=%d\n",bucket[1][i].num,gain(bucket[1][i],1));
	printf("current cut number:%d\n",cutnum());
	return 0;
}

int iscon(struct klnode left,struct klnode right)
{
int i,j;
i=left.num;
for(j=0;j<vertex[i].getlength();j++)
  if(vertex[i].getindex(j)->number==right.num)
	  return 1;
return 0; 
}
void KL()
{
int maxcut=0,exl=0,exr=0;
int midgain;
int i,j,k,flag=0;
for(k=0;k<len/2;k++)
{
 for(i=0;i<len/2;i++)
  if(bucket[0][i].lock==false)
  {
   for(j=0;j<len/2;j++)
   {
     if(bucket[1][j].lock==false)
	  {
         midgain=gain(bucket[0][i],0)+gain(bucket[1][j],1);
         if(midgain>maxcut)
			 {
		      maxcut=midgain;
			  flag=1;
			  exl=i;exr=j;
			 }
	  }
   }
  }
  if(flag==1)
  {
   exchange(bucket[0][exl],bucket[1][exr]);
   maxcut=0;
   flag=0;
  }
}
}

int cutnum()
{
int i,j;
int res=0;
for(i=0;i<len/2;i++)
{
    j=gg(bucket[1][i]);
	res+=j;
	printf("gain=%d ",j);
}
printf("\n");
return res;
}

int gg(struct klnode nd)
{
int j,i,lg=0;
i=nd.num;
for(j=0;j<vertex[i].getlength();j++)
{
  if(left(vertex[i].getindex(j)))
  {
  lg++;
  }
}
return lg;
}
int gain(struct klnode nd,int side)
{
int res,j,i,lg=0,rg=0;
i=nd.num;
for(j=0;j<vertex[i].getlength();j++)
{
  if(left(vertex[i].getindex(j)))
  {
  lg++;
  }
  else
  {
  rg++;
  }
}
if(side==1)
res=lg-rg;
else
res=rg-lg;
return res;
}

int left(node *nd)
{
int i;
for(i=0;i<len/2;i++)
{
if(bucket[0][i].num==nd->number)
  return 1;
}
return 0;
}
void exchange(struct klnode &left,struct klnode &right)
{
struct klnode mid;
mid=left;
left=right;
right=mid;
left.lock=true;
right.lock=true;
}