kl.c

VLSi KL partitioning Algorithm based programme for 100 nodes. It s dynamic progremme so by changing

#include<stdio.h>
#include<stdlib.h>
#define MAX 101

int main()
{

	int i,j,k,node1,node2,alliter;
	long int maxgain;
	int net1[MAX],net2[MAX],a[MAX][MAX];
	/*int a[MAX][MAX]={
			0,0,0,0,0,0,0,
			0,0,1,2,3,2,4,
			0,1,0,1,4,2,1,
			0,2,1,0,3,2,1,
			0,3,4,3,0,4,3,
			0,2,2,2,4,0,2,
			0,4,1,1,3,2,0};*/

	
	long int gain[MAX][MAX];

	int inter[MAX];
	int ext[MAX];
	int d[MAX];
	int node_stat[MAX][3];
	//int net1[MAX]={0,1,2,3,0,0,0};
	//int net2[MAX]={0,0,0,0,4,5,6};
	//int net1[MAX]={0,1,2,3,0,0,0};
 
	//int net2[MAX]={0,0,0,0,4,5,6};
	
	for(i=0;i<MAX;i++)
	{
		for(j=0;j<=i+1;j++)
		{
			if(i==0)
				a[i][j]=0;
			else if(j==0)
				a[i][j]=0;
			else if(i==j)
			{
				a[i][j]=0;
			}
			else
				a[i][j]=random()%50;
		}
	}
	
	for(i=MAX-1;i>=0;i--)
	{
		for(j=MAX-1;j>=i;j--)
		{
			a[i][j]=a[j][i];
		}
	}

	printf("|");
	for(i=0;i<(MAX+1)/2;i++)
	{
		net1[i]=i;
		net2[i]=0;
		node_stat[i][0]=i;
		node_stat[i][1]=(i!=0)?1:0;
		node_stat[i][2]=0;

		//printf(" %d %d %d %d %d \n",net1[i],net2[i],node_stat[i][0],node_stat[i][1],node_stat[i][2]);

	}
	for(i=(MAX+1)/2;i<MAX;i++)
	{
		net2[i]=i;
		net1[i]=0;
		node_stat[i][0]=i;
		node_stat[i][1]=2;
		node_stat[i][2]=0;
		//printf(" %d %d %d %d %d \n",net1[i],net2[i],node_stat[i][0],node_stat[i][1],node_stat[i][2]);

	}


	/*int node_stat[MAX][3]={
				0,0,0,
				1,1,0,
				2,1,0,
				3,1,0,
				4,2,0,
				5,2,0,
				6,2,0};*/
	for(i=0;i<MAX;i++)
	{
		for(j=0;j<MAX;j++)
		{
			//printf(" %d ",a[i][j]);
		}
		//printf("\n");

	}
	alliter=0;
	while(alliter+1 < MAX)
	{
		//printf("External Internal Difference\n");
		for(i=0;i<MAX;i++)
		{
			ext[i]=0;
			inter[i]=0;
			if(node_stat[i][1]==1)
			{
				for(j=0;j<MAX;j++)
				{
					ext[i]+=a[i][net2[j]];
				}
				for(k=0;k<MAX;k++)
				{
					inter[i]+=a[i][net1[k]];
				}
			}
			else if(node_stat[i][1]==2)
			{
				for(j=0;j<MAX;j++)
				{
					ext[i]+=a[net1[j]][i];
				}
				for(k=0;k<MAX;k++)
				{
					inter[i]+=a[net2[k]][i];
				}
			}
	
			d[i]=ext[i]-inter[i];
			//printf("%d \t %d \t %d\n",ext[i],inter[i],d[i]);

		}	

		maxgain=-2147483647;
		//free(maxgain);
		//maxgain=(int *)realloc(maxgain,sizeof(int));
		node1=0;
		node2=0;
		for(i=0;i<MAX;i++)
		{
			for(j=0;j<MAX;j++)
			{
				if(net1[i]==0 || net2[j]==0 || node_stat[i][2]==1 || node_stat[j][2]==1){
					gain[i][j]=0;
				}
				else
				{
					gain[i][j]=d[net1[i]]+d[net2[j]]-2*(a[net1[i]][net2[j]]);
					if(maxgain<gain[i][j])
					{
						maxgain=gain[i][j];
						node1=i;
						node2=j;
					}
				}
				//printf("  %d  ",gain[i][j]);
			}
			//printf("\n");
		}
	
		printf("Maximum gain : %d \t Exchange %d and %d \n",maxgain,node1,node2);
		net1[node1]=0;
                net2[node1]=node1;
                net2[node2]=0;
                net1[node2]=node2;
                node_stat[node1][1]=2;
                node_stat[node2][1]=1;
		node_stat[node1][2]=1;
		node_stat[node2][2]=1;
		alliter=alliter+2;
	}
}