mymaxmatch.cpp

也是一个关于匹配方面的程序

#include"myMaxMatch.h"

MyMaxMatch::MyMaxMatch(MyGraph& graph)
{
	//pred = NULL;
	k = 0;//得到匈牙利树的时候增加
	pj = -1;
	g = graph;//
	T = NULL;
	matchEdge = NULL;
	testEdge = NULL;
	expose = NULL;
	label = NULL;
	int i = 0;
	//分配交替树空间
	T = new int*[graph.n];
	for(i = 0; i < graph.n; i++)
	{
		T[i] = new int[graph.n];
	}
	for(i = 0; i < graph.n; i++)
	{
		register int j = 0;
		for(j = 0; j < graph.n; j++)
		{
			T[i][j] = 0;//0表示没有边
		}
	}
	//分配匹配边空间
	matchEdge = new int*[graph.n];
	for(i = 0; i < graph.n; i++)
	{
		matchEdge[i] = new int[graph.n];
	}
	for(i = 0; i < graph.n; i++)
	{
		for(register int j = 0; j < graph.n; j++)
		{
			matchEdge[i][j] = 0;
		}
	}
	//分配标记边(i,j)是否已经被检测的数组
	testEdge = new int*[graph.n];
	for(i = 0; i < graph.n; i++)
	{
		testEdge[i] = new int[graph.n];
	}
	for(i = 0; i < graph.n; i++)
	{
		for(register int j = 0; j < graph.n; j++)
		{
			testEdge[i][j] = 0;
		}
	}
	//分配非饱和点标志空间
	expose = new int[graph.n];
	for(i = 0; i < graph.n; i++)
	{
		expose[i] = 1;
	}
	//分配标志数组的空间
	label = new int[graph.n];
	for(i = 0; i < graph.n; i++)
	{
		label[i] = 0;
	}
}

MyMaxMatch::~MyMaxMatch()
{
	int i = 0;
	//释放交替树空间
	if(T != NULL)
	{
		for(i = 0; i < g.n; i++)
		{
			delete []T[i];
		}
		delete []T;
		T = NULL;
	}
	//释放匹配边空间
	if(matchEdge != NULL)
	{
		for(i = 0; i < g.n; i++)
		{
			delete []matchEdge[i];
		}
		delete []matchEdge;
		matchEdge = NULL;
	}
	//释放testEdge数组
	if(testEdge != NULL)
	{
		for(i = 0; i < g.n; i++)
		{
			delete []testEdge[i];
		}
		delete []testEdge;
		testEdge = NULL;
	}
	//释放expose数组
	delete []expose;
	expose = NULL;
	//释放标志数组
	delete []label;
	label = NULL;
}
//MyGraph& MyMaxMatch::compute()
void MyMaxMatch::compute()
{
	cout<<"开始计算最大权匹配..."<<endl;
	initial();//相关的内容都在构造函数中
L1: char c1 = testMatchV();//检查是否有至少2个非饱和点
	if(c1 == 'y')
	{//如果至少有2个非饱和点
L2:		char c2 = growTree();
		switch(c2)
		{
		case 'p'://T,label清空M变，G不变testEdge也应改变吧
			processP(pj);
#if DEBUGMYMAXMATCH == 1
			printM();
#endif
			goto L1;
			break;
		case 'b':
			goto L2;//???应该根,label不变,T,M,G变
			processB();
			break;
		case 'h'://G,M变，T,label清空
			processHut();
#if DEBUGMYMAXMATCH == 1
			printM();
#endif
			goto L1;
			break;
		default:
			break;
		}
	}
	ufoldAll();
	//return g;
}
void MyMaxMatch::initial()
{//初始化
}
char MyMaxMatch::testMatchV()
{//检查途中的饱和点.至多有一个非饱和点返回n,打开花苞；y,生长交替树
	//非饱和点多于1个就返回y生长交错树
	int count = 0;
	//!!!!!假设所有expose节点存在都有0.1两种取值
	register int i = 0;
	for(i = 0; i < g.n; i++)
	{
		if(g.Vertex[i].num > -1 && expose[i] == 1)
		{
			count ++;
			if(count > 1)
			{
				break;
			}
		}
	}
	if(count <= 1)
	{
		return 'n';//至多有一个饱和节点
	}	
	return 'y';//否则
}
int MyMaxMatch::getExposed()
{
	//int count = 0;//不需要检测是否多于两个非饱和点了，能进到这里就已经多于两个了
	//int index = -1;
	for(register int i = 0; i < g.n; i++)
	{
		if(g.Vertex[i].num > -1 && expose[i] == 1)
		{//非饱和
			//count++;
			//index = i;
			//if(count > 1)
			//{
				return i;
			//}
		}
	}
	//index = -1;
	return -1;
}
int MyMaxMatch::selectEdge(int& ii)
{//选择一条与T中某个外点ii关联的不属于T&testEdge的边(ii,j),返回j
	for(ii = 0; ii < g.n; ii++)
	{
		if(g.Vertex[ii].num > -1 && label[ii] == 1)
		{			
			for(int jj = 0; jj < g.n; jj++)
			{
				if((T[ii][jj] > 0) || (T[jj][ii] > 0) || T[jj][ii] ==-1)
				{//ii是树上的点，第一个判定条件是否多余?外部点必然是树上的点???
					//if(label[ii] == 1)
					
					for(register int j = 0; j < g.n; j++)
					{
						if(g.Vertex[j].num > -1)
						{//j是图上的点
							if(g.Edge[ii][j].isE == 1 && (T[ii][j] < 1 && T[j][ii] < 1) && (testEdge[ii][j] < 1 && testEdge[j][ii] < 1))
							{//j是与ii相关的不在树中的边???g.Edge[2][3]怎么不是1了？
								return j;
							}
						}						
					}
					
					break;//防止重复
				}
			}
		}//if(ii)
	}
	return -1;
}
char MyMaxMatch::growTree()
{//构造交替树.返回b,处理花苞；返回p处理增广路;返回h处理匈牙利树
#if DEBUGMYMAXMATCH == 1
				cout<<"...开始生长交错树..."<<endl;
#endif
	int i = getExposed();//选择一个树根
	//设置testEdge为空
	//此处在处理花苞的时候是否合理???
	int ii = 0;
	for(ii = 0; ii < g.n; ii++)
	{
		for(register int j = 0; j < g.n; j++)
		{
			testEdge[ii][j] = 0;
		}
	}
	////////////////
	if( i >= 0)
	{//存在非饱和点
		//把i设置为T的根，i列全部是-1//此处在处理花苞的时候是否合理???
		for(ii = 0; ii < g.n; ii++)
		{
			if(ii != i)
			{
				T[ii][i] = -1;//因为把i作为根,所以他没有前驱
			}			
		}
		label[i] = 1;
		ii = 0;
		//选择一条边(ii,j),其中ii是T中的某个外点，j不在T和testEdge中
		//step1:int j = selectEdge(ii);
		int j = -1;
		while(j = selectEdge(ii),j >= 0)
		{
			
			if(label[j] == -1)
			{//内部节点
				testEdge[ii][j] = 1;//goto step1;
			}
			else if(label[j] == 1)
			{//是外部节点
				T[ii][j] = 2;//2对应的两个节点为花苞的外部节点??
				processB();
				//return 'b';//处理花苞
			}
			else if(label[j] == 0 && expose[j])
			{//是非饱和的无标记点
				//processP(j);//从j回溯处理增广路
				T[ii][j] = 1;//此处应该加么???
				pj = j;
#if DEBUGMYMAXMATCH == 1
				cout<<"...生长交错树完毕..."<<endl;
#endif
				return 'p';//处理增广链				
			}
			else
			{//未标记的饱和点
				T[ii][j] = 1;
				int kk = 0;
				for(kk = 0; kk < g.n; kk++)
				{
					if(matchEdge[j][kk] == 1){break;}//??
				}//for(int kk = 0; kk < graph.n; kk++)
				T[j][kk] = 1;
				label[j] = -1;
				label[kk] = 1;				
			}
		}//while(j = selectEdge(ii),j >= 0)
		//processHut();
#if DEBUGMYMAXMATCH == 1
		cout<<"...生长交错树完毕..."<<endl;
#endif
		return 'h';//处理匈牙利树
				
	}//if( i > = 0)
	//至多有一个外部节点因为前面的检测不可能出现的情况
	//processHut();
#if DEBUGMYMAXMATCH == 1
				cout<<"...生长交错树完毕..."<<endl;
#endif
	return 'h';
}
void MyMaxMatch::processP(int j)
{//处理增广链
	//得到增广链
	cout<<"处理增广链"<<endl;
	vector<int> l;
	l.push_back(j);
	int i = 0;
	while(i < g.n)
	{
		if(T[i][j] == 1)
		{
			j = i;
			l.push_back(j);
			i = 0;
		}
		else
		{
			i++;
		}
	}//退出起点就意味着j到达了根
	int count = l.size();//记录节点个数

	//根据匹配边对增广链进行处理
	for(i = count - 1; i > 0; i--)
	{
		if(i & 1)
		{//如果i是奇数
			matchEdge[l[i]][l[i - 1]] = 1;
			matchEdge[l[i - 1]][l[i]] = 1;
		}
		else
		{
			matchEdge[l[i]][l[i - 1]] = 0;
			matchEdge[l[i - 1]][l[i]] = 0;
		}
		expose[l[i]] = 0;
	}
	expose[l[0]] = 0;

	//得到匈牙利树下次重新获取//testEdge呢？标号呢？
	for(i = 0; i < g.n; i++)
	{
		label[i] = 0;
		register int j = 0;
		for(j = 0; j < g.n; j++)
		{
			T[i][j] = 0;//0表示没有边
			testEdge[i][j] = 0;
		}
	}
		
}
int MyMaxMatch::getBlossom()
{//得到当前图中的花苞，把花苞的点依次存放到blossom中，并返回花苞的个数

	int i = 0;
	int j = 0;
	//B.insert(B.end(),*new MyBlossom());//???在末尾插入空元素这么困难么？
	//B.push_back(*new MyBlossom());
	MyBlossom tmpB;//建立一个临时花苞之后将插入花苞队列中
	tmpB.n = g.n;
	//???lkupdate按理说应该为tmpB类重载=和拷贝因为push_back有可能存在深度拷贝问题
	//tmpB.initialE();
	//end1,end2是花苞的两个互联的外部节点
	int end1 = 0;
	int end2 = 0;
	for(i = 0; i < g.n; i++)
	{
		for(j = 0; j < g.n; j++)
		{
			if(2 == T[i][j])
			{
				end1 = i;
				end2 = j;
			}
		}
	}//得到两个外部节点号
	//获取花苞的节点序列vertex[0]是基节点，顺时针/逆时针
	//利用花苞中除了基节点之外全是饱和节点的特性寻找基节点
	i = end1;
	while(expose[i] != 1)
	{//如果没有到达基节点
		tmpB.vertex.insert(tmpB.vertex.begin(),i);
		for(j = 0; j < g.n; j++)
		{
			if(T[j][i] == 1)
			{
				i = j;
				break;
			}
		}
	}
	tmpB.vertex.insert(tmpB.vertex.begin(),i);
	i = end2;
	while(expose[i] != 1)
	{//如果没有到达基节点
		tmpB.vertex.push_back(i);
		for(j = 0; j < g.n; j++)
		{
			if(T[j][i] == 1)
			{
				i = j;
				break;
			}
		}
	}
	B.push_back(tmpB);//插入花苞到花苞队列中去
	B.back().initialE();
	//至此获得了花苞的节点
	//int root = 0;//记录花苞基节点所在的节点号
#if DEBUGMYMAXMATCH == 1
	B.back().printBlossom();
	cout<<"num of blossom is :"<<B.back().vertex.size()<<endl;
#endif	
	return B.back().vertex.size();
}
void MyMaxMatch::processB()
{//处理花苞
#if DEBUGMYMAXMATCH == 1
				cout<<"...开始处理花苞..."<<endl;
#endif
	shrink();
#if DEBUGMYMAXMATCH == 1
	cout<<"...处理花苞完毕..."<<endl;
	printG();
	printT();
	printM();
#endif	
}
void MyMaxMatch::shrink()
{//收缩花苞
	int bnum = getBlossom();//获得花苞返回所含节点数
	int root = -1;
	printT();
	B.back().treeIndex = k;//该花苞所对应的匈牙利树得下标
	//int b = B.size();
	//收缩前
	int i = 0;
	for(i = 0; i < bnum; i++)
	{
		register int j = 0;
		for(j = 0; j < g.n; j++)
		{
			//记录花苞的边
			
			if(g.Vertex[j].num > -1)
			{
				//B.back().Edge[i][j] = 1;
				//B.back().Edge[j][i] = 1;
				B.back().Edge[B.back().vertex[i]][j] = g.Edge[B.back().vertex[i]][j].isE;
				B.back().Edge[j][B.back().vertex[i]] = g.Edge[j][B.back().vertex[i]].isE;
			}
		}
	}
	for(i = 0; i < bnum; i ++)
	{
		if(i != 0)
		{
			g.Vertex[B.back().vertex[i]].num = -1;//把花苞节点对应的节点号（除了根）去掉 
			
			//收缩花苞时去掉边和为收缩点添加边的过程
			register int j = 0;
			for(j = 0; j < g.n; j++)
			{
				register int e = g.Edge[B.back().vertex[i]][j].isE || g.Edge[B.back().vertex[0]][j].isE;
				g.Edge[B.back().vertex[i]][j].isE = 0;//去掉边
				g.Edge[j][B.back().vertex[i]].isE = 0;