partitionwith2points.cpp

实验描述：分布式数据库的算法partition的具体实现。即通过该算法找到关系数据库最优分裂点(2个）

#include<iostream.h>
#include<stdio.h>//
//the algorithm is to partion a R using the knowlege of DDBS
//by liangjian 
//time is 2006.5.5
 class Help{
public: int *COQHelp;	   	
 public: int *CTQHelp; 
 public: int *CBQHelp;
public: int *CMQHelp;
		  //CTQHelp=new int[dimofAUM+1];
		  //COQHelp=new int[dimofAUM+1];
		  //CBQHelp=new int[dimofAUM+1];
  };  Help QQhelp;    
void main(){
	int dimofAUM,temp1;
	int **AUM,**acc,**AA, **BB,**CA,**temp,*HelpPartition,**ilikett;
	int *locMatrix;
    int best,z,bestloc1,bestloc2;
	int i,j,k,loc,index;
	class key{public:int value;
	         public:   int loc;
	};
  key max;
//int* GenerateCTQHelp(int x,int dimofAUM,int **AUM );
 //int* GenerateCBQHelp(int y,int dimofAUM,int **AUM );
 //int* GenerateCOQHelp(int dimofAUM,int *CTQHelp,int *CBQHelp );
 int CalculateCTQ(int x,int dimofAUM,int **AUM,int **acc);
 int CalculateCBQ(int x,int dimofAUM,int **AUM,int **acc);
 int CalculateCOQ( int dimofAUM,int **acc);
 int CalculateCMQ(int x,int y,int dimofAUM,int **AUM,int **acc);
int bond(int r,int c,int dimofAUM,int **AA,int index,int **CA);
	int cont(int r,int m,int c,int index,int **AA,int **CA,int dimofAUM);
cout<<"本程序经由课本上例子测试，测试结果通过！"<<endl;	
cout<<"为了简化程序，站点数字固定为Attribute Usage Matrix的维数-1，这样是为了和课本上的例子匹配"<<endl;
cout<<"同样为了和课本上的例子程序匹配，ref的值设定为1。我这样简单化是为了不让细节影响BEA算法和partition算法的实现." <<endl; 
ini:   cout<<"now input the dimension of the Attribute Usage Matrix"<<endl;
	cin>>dimofAUM;
//CBQHelp=new int[dimofAUM+1];
   QQhelp.CTQHelp=new int[dimofAUM+1];
   QQhelp.COQHelp=new int[dimofAUM+1];
   QQhelp.CBQHelp=new int[dimofAUM+1];
   QQhelp.CMQHelp=new int[dimofAUM+1];
    //COQHelp=new int[dimofAUM+1]; 
ilikett =new int*[dimofAUM];
	for(i=0;i<dimofAUM;++i)
	 ilikett [i]=new int[dimofAUM];
  HelpPartition =new int[dimofAUM];
	  AUM =new int*[dimofAUM];
	for(i=0;i<dimofAUM;++i)
	 AUM[i]=new int[dimofAUM];
	AA =new int*[dimofAUM];
	for(i=0;i<dimofAUM;++i)
	 AA[i]=new int[dimofAUM];
 BB =new int*[dimofAUM];
	 for(i=0;i<dimofAUM;++i)
 BB[i]=new int[dimofAUM];
	CA =new int*[dimofAUM];
	for(i=0;i<dimofAUM;++i)
	 CA[i]=new int[dimofAUM];
    acc=new int*[dimofAUM];
	for(i=0;i<dimofAUM-1;++i)
		acc[i]=new int[dimofAUM];
	temp=new int*[dimofAUM];
	for(i=0;i<dimofAUM-1;++i)
		temp[i]=new int[dimofAUM];
	locMatrix=new int[dimofAUM];
	//a=new int[dimofAUM];
            cout<<"input the respective values of the Attribute Usage Matrix"<<endl;
			cout<<"Remember!the value must be 1 or 0"<<endl;
	for(i=0;i<dimofAUM;i++){
for(j=0;j<dimofAUM;j++)
	{
		cin>>AUM[i][j];
	    printf("AUM[%d][%d]=%d",i,j,AUM[i][j]);
		cout<<endl;
		if(!(AUM[i][j]==0||AUM[i][j]==1)){
			cerr << " 出错！";
			return;                      }  
}}
//AUM[0][0]=1;AUM[0][1]=0;AUM[0][2]=1;AUM[0][3]=0;AUM[1][0]=0;AUM[1][1]=1;AUM[1][2]=1;AUM[1][3]=0;AUM[2][0]=0;AUM[2][1]=1;
//AUM[2][2]=0;AUM[2][3]=1;AUM[3][0]=0;AUM[3][1]=0;AUM[3][2]=1;AUM[3][3]=1;
 cout<<"Now input acc matrix and the value must be not smaller than 0"<<endl;
 for(i=0;i<dimofAUM;i++)
  for(j=0;j<dimofAUM;j++)
	BB[i][j]=0;
 acc=BB;//BB的地址变成acc,acc's addr equal BB!
for(i=0;i<dimofAUM;++i)  
	for(j=0;j<dimofAUM-1;++j){
 cin>>acc[i][j];
	 printf("acc[%d][%d]=%d",i,j,acc[i][j]);
 cout<<endl;}
 //acc[0][0]=15;acc[0][1]=20;acc[0][2]=10;acc[1][0]=5;acc[1][1]=0;acc[1][2]=0;
 //acc[2][0]=25;acc[2][1]=25;acc[2][2]=25;acc[3][0]=3;acc[3][1]=0;acc[3][2]=0;
	 //the Attribute Affinity Matrix
	 for(i=0;i<dimofAUM;i++)
			for(j=0;j<dimofAUM;j++)
				AA[i][j]=0;
	 for(k=0;k<dimofAUM;k++)
	    for(i=0;i<dimofAUM;i++)
			for(j=i;j<dimofAUM;j++){
			 if(AUM[k][i]==1&&AUM[k][j]==1)
				 for(int p=0;p<dimofAUM-1; p++)
					 AA[i][j]+=acc[k][p];
				 AA[j][i]=AA[i][j];}
				 for(i=0;i<dimofAUM;i++)
			for(j=0;j<dimofAUM;j++){
					cout<<"  "<<"AA["<<i<<"]["<<j<<"]"<<" "<<AA[i][j];    
					if(j==dimofAUM-1)cout<<endl;
				}//AA appear!
//Now the BEA belowfor(i=0;i<dimofAUM;i++)
	for(i=0;i<dimofAUM;i++)
			for(j=0;j<dimofAUM;j++)
				CA[i][j]=0;		 
	             //for(j=0;j<2;j++)
			for(i=0;i<dimofAUM;i++)
				CA[i][0]=AA[i][0];
			for(i=0;i<dimofAUM;i++)
				CA[i][1]=AA[i][1];
			locMatrix[0]=0;locMatrix[1]=1;
			index=2;
			while(index<=dimofAUM-1){
				max.value=0;
			 for(i=0;i<=index-1;i++)
				 if(max.value<cont(i-1,index,i,index,AA,CA,dimofAUM)){
					  max.value=cont(i-1,index,i,index,AA,CA,dimofAUM);
					  max.loc=i;}
				 if(max.value<cont(index-1,index,index+1,index,AA,CA,dimofAUM)){
			max.value=cont(index-1,index,index+1,index,AA,CA,dimofAUM);
			max.loc=index;}
			 loc=max.loc;
			 locMatrix[index]=loc;
			    for(j=index;j>loc;j--)
					for(i=0;i<dimofAUM;i++)
                  CA[i][j]=CA[i][j-1];
				for(i=0;i<dimofAUM;i++)
					CA[i][loc]=AA[i][index];     
					++index;}            
			for(i=0;i<dimofAUM;++i)
				for(j=0;j<dimofAUM;++j)
				{
					cout<<"  "<<"CA["<<i<<"]["<<j<<"]"<<" "<<CA[i][j] ;
					if(j==dimofAUM-1)cout<<endl;
				}
				///generate CA below
				for(i=0;i<dimofAUM;i++)
					HelpPartition[i]=i;
			    for(i=0;i<dimofAUM;i++)
				{int count=i;
					if(locMatrix[i]<i){
				 temp1=HelpPartition[i];
				  for(k=i-1;k>=locMatrix[i];k--){
					 HelpPartition[count]=HelpPartition[k];
						  --count;}
					    HelpPartition[locMatrix[i]]=temp1;
				}
				  else 
					   HelpPartition[locMatrix[i]] =locMatrix[i] ;}
				for(i=2;i<dimofAUM;i++)
				{  temp=ilikett;
				  int count=i;
				  if(locMatrix[i]<i){
				  for(j=0;j<dimofAUM;j++)
					  temp[i][j]=CA[i][j];
				  for(k=i-1;k>=locMatrix[i];k--){
					  for(j=0;j<dimofAUM;j++)
						 CA[count][j]=CA[k][j];
						  --count;}
					  for(j=0;j<dimofAUM;j++)
						  CA[locMatrix[i]][j]=temp[i][j];
				}
				  else 
					  for(j=0;j<dimofAUM;j++)
						  CA[locMatrix[i]][j]=CA[i][j];
				}
				for(i=0;i<dimofAUM;++i)
				for(j=0;j<dimofAUM;++j)
				{
					cout<<"  "<<"CA["<<i<<"]["<<j<<"]"<<" "<<CA[i][j] ;
					if(j==dimofAUM-1)cout<<endl;
				}
				//now the partition
best=0; 
		    //temp=CalculateCOQ(dimofAUM,GenerateCTQHelp(dimofAUM-2,dimofAUM,AUM),GenerateCBQHelp(dimofAUM-1,dimofAUM,AUM),acc);
//best=CalculateCTQ(dimofAUM-2,dimofAUM,AUM,acc)*CalculateCBQ(dimofAUM-2,dimofAUM,AUM,acc)-CalculateCOQ(dimofAUM,acc)*CalculateCOQ(dimofAUM,acc);
//bestloc=dimofAUM-2;
for(i=dimofAUM-2;i>=1;i--)
for(j=i-1;j>=0;j--){     
z=CalculateCTQ(j,dimofAUM,AUM,acc)*CalculateCBQ(i,dimofAUM,AUM,acc)*CalculateCMQ(j,i,dimofAUM,AUM,acc)-CalculateCOQ(dimofAUM,acc)*CalculateCOQ(dimofAUM,acc)*CalculateCOQ(dimofAUM,acc);
if(z>best){
	bestloc1=i;
	bestloc2=j;
	best=z;}}
cout<<"best="<<best;
cout<<"bestloc1="<<bestloc1<<endl;
cout<<"bestloc2="<<bestloc2<<endl;
for(i=0;i<dimofAUM;i++)
cout<<"  "<<HelpPartition[i];
cout<<"R1 is ";
for(i=0;i<=bestloc2;i++)
	if(HelpPartition[i]==0)
	{for(i=0;i<=bestloc2;i++)
			cout<<HelpPartition[i]<<endl;}
	else{cout<<0;
	for(i=0;i<=bestloc2;i++)
		cout<<HelpPartition[i]<<endl;}
cout<<"---------"<<endl;
cout<<"R2 is ";
 
for(i=bestloc2+1;i<=bestloc1;i++)

	if(HelpPartition[i]==0)
	{for(i=0;i<=bestloc2;i++)
			cout<<HelpPartition[i]<<endl;}
	else{cout<<0;
	for(i=bestloc2+1;i<=bestloc1;i++)
		cout<<HelpPartition[i]<<endl;}
//cout<<HelpPartition[i]<<endl;
cout<<"R3 is ";
//cout<<0;
for(i=bestloc1+1;i<dimofAUM;i++)

	if(HelpPartition[i]==0)
	{for(i=0;i<=bestloc2;i++)
			cout<<HelpPartition[i]<<endl;}
	else{cout<<0;
	for(i=bestloc1+1;i<dimofAUM;i++)
		cout<<HelpPartition[i]<<endl;}
//cout<<HelpPartition[i]<<endl;
//release memory
			//
delete []locMatrix;
for(i=0;i<dimofAUM-1;i++) delete[] temp[i];
delete[] temp;
for(i=0;i<dimofAUM-1;i++) delete[] acc[i];
delete[] acc;
for(i=0;i<dimofAUM;i++) delete[] CA[i];
delete[] CA;
//for(i=0;i<dimofAUM;i++) delete[] BB[i];
//delete[] BB;
for(i=0;i<dimofAUM;i++) delete[] AA[i];
delete[] AA;
for(i=0;i<dimofAUM;i++) delete[] AUM[i];
delete[] AUM;
delete[] HelpPartition;
//for(i=0;i<dimofAUM;i++) delete[] ilikett[i];
//delete[] ilikett;
goto ini;				
			 } 
//int* GenerateCTQHelp(int x,int dimofAUM,int **AUM)
//int* GenerateCBQHelp(int y,int dimofAUM,int **AUM)
//int* GenerateCOQHelp(int dimofAUM,int *CTQHelp,int *CBQHelp)
int CalculateCTQ(int x,int dimofAUM,int **AUM,int **acc){
int CTQ=0,m=0;
//int q=0;
//class Help QQhelp;
//  key qq;
//qq.value=0;
//int *CTQHelp;
//CTQHelp=GenerateCTQHelp(x,dimofAUM,AUM);
//int*CTQHelp;
for(int i=0;i<dimofAUM+1;i++)
QQhelp.CTQHelp[i]=-1;
 for(int j=x;j>=0;j--)
	  for(int i=0;i<dimofAUM;i++)        
		 if(AUM[i][j]==1)
		{    int isok=0;
			 for(int k=0;k<=x;++k){
			    if(QQhelp.CTQHelp[k]==i)
					isok=1;       }
              	//else if(QQhelp.CTQHelp[k]==-1)
					//QQhelp.CTQHelp[k]=i;
				 if(isok==0)
				 {QQhelp.CTQHelp[m]=i;
				 ++m;}}
 //the GenerateCTQ() before;
		   //return CTQHelp;}
   for(i=0;QQhelp.CTQHelp[i]!=-1;i++)
	   for(int j=0;j<dimofAUM-1;j++)
		   CTQ+=acc[QQhelp.CTQHelp[i]][j];
	   return CTQ;}
int CalculateCBQ(int x,int dimofAUM,int **AUM,int **acc){
int CBQ=0,m=0;
 //int *CBQHelp=0;
	//CBQHelp=GenerateCBQHelp(x+1,dimofAUM,AUM);
       //int*CBQHelp;
	 for(int i=0;i<dimofAUM+1;i++)
	    QQhelp.CBQHelp[i]=-1;
  for(int j=x+1;j<=dimofAUM-1;j++)
	  for(int i=0;i<dimofAUM;i++)        
		 if(AUM[i][j]==1)
		{  int isok=0;
			 for(int k=0;k<=dimofAUM-x-1;++k){
			    if(QQhelp.CBQHelp[k]==i)
					isok=1;       }
              	//else if(QQhelp.CTQHelp[k]==-1)
					//QQhelp.CTQHelp[k]=i;
				 if(isok==0)
				 {QQhelp.CBQHelp[m]=i; 
				 ++m;}}
 		   //return CBQHelp;
 for(i=0;QQhelp.CBQHelp[i]!=-1;i++)
	   for(int j=0;j<dimofAUM-1;j++)
	CBQ+=acc[QQhelp.CBQHelp[i]][j];
	   return CBQ;}
int CalculateCOQ(int dimofAUM,int **acc){
	int COQ=0;
	//int *COQHelp;
	//COQHelp=GenerateCOQHelp(dimofAUM,Help,CBQHelp);
	{for(int i=0;i<dimofAUM+1;i++)
	 QQhelp.COQHelp[i]=-1;
	int k=0,p=0;
	 //int*COQHelp;
A:	while(k<dimofAUM){
		for(i=0;i<dimofAUM;i++){
			if(k==QQhelp.CTQHelp[i]){++k;goto A;}}
		  for(i=0;i<dimofAUM;i++)
			   if(k==QQhelp.CBQHelp[i]){++k;goto A;}
			 for(i=0;i<dimofAUM;i++)
			   if(k==QQhelp.CMQHelp[i]){++k;goto A;}  
		QQhelp.COQHelp[p]=k;
		p++;
		k++;
	}
//return COQHelp;}
   for(i=0;QQhelp.COQHelp[i]!=-1;i++)
	   for(int j=0;j<dimofAUM-1;j++)
		  COQ+=acc[i][j];
	  return COQ;}
	}
int CalculateCMQ(int x,int y,int dimofAUM,int **AUM,int **acc){
int CMQ=0,m=0;
//int q=0;
//class Help QQhelp;
//  key qq;
//qq.value=0;
//int *CTQHelp;
//CTQHelp=GenerateCTQHelp(x,dimofAUM,AUM);
//int*CTQHelp;
for(int i=0;i<dimofAUM+1;i++)
QQhelp.CMQHelp[i]=-1;
 for(int j=x+1;j<=y;j++)
	  for(int i=0;i<dimofAUM;i++)        
		 if(AUM[i][j]==1)
		{  int isok=0;
			 for(int k=0;k<=dimofAUM;++k){
			    if(QQhelp.CMQHelp[k]==i)
					isok=1;       }
              	//else if(QQhelp.CTQHelp[k]==-1)
					//QQhelp.CTQHelp[k]=i;
				 if(isok==0)
				 {QQhelp.CMQHelp[m]=i;
				 ++m;}}
 //the GenerateCTQ() before;
		   //return CTQHelp;}
   for(i=0;QQhelp.CMQHelp[i]!=-1;i++)
	   for(int j=0;j<dimofAUM-1;j++)
		   CMQ+=acc[QQhelp.CMQHelp[i]][j];
	   return CMQ;}
int bond(int r,int c,int dimofAUM,int **AA,int index,int **CA)
{  //AA =new int*[dimofAUM];
	//for(i=0;i<dimofAUM;++i)
	 //AA[i]=new int[dimofAUM];
	 
	//CA =new int*[dimofAUM];
	//for(i=0;i<dimofAUM;++i)
	 //CA[i]=new int[dimofAUM];
	int  result1=0;
	if(r==-1||c==-1||r==dimofAUM||c==dimofAUM)
		return   result1=0;
	else if(r==index){
	for(int i=0;i<dimofAUM;i++)
	result1+=AA[i][r]*CA[i][c];
	return   result1;}
	else if(c==index)
	{for(int i=0;i<dimofAUM;i++)
	result1+=CA[i][r]*AA[i][c];
	return   result1;}
	else {for(int i=0;i<dimofAUM;i++)
	result1+=CA[i][r]*CA[i][c];
	return   result1;}
}
 	int cont(int r,int m,int c,int index,int **AA,int **CA,int dimofAUM)
	{ int result2=0 ;
	//if(c>m)
      //bond(m,c,dimofAUM,AA)=0;
		//bond(r,c,dimofAUM,AA)=0;}
//result2=2*bond(r,m,dimofAUM,AA);
       result2=2*(bond(r,m,dimofAUM,AA,index,CA)+bond(m,c,dimofAUM,AA,index,CA)-bond(r,c,dimofAUM,AA,index,CA));
	   return  result2;
	   }