mymaxmatch.cpp

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

				g.Edge[B.back().vertex[0]][j].isE = e;//把边添加到压缩后的点(基点)上
				g.Edge[j][B.back().vertex[0]].isE = e;
				

				e = matchEdge[B.back().vertex[i]][j] || matchEdge[B.back().vertex[0]][j];
				matchEdge[B.back().vertex[i]][j] = 0;//匹配边相关的都去掉
				matchEdge[j][B.back().vertex[i]] = 0;
				matchEdge[B.back().vertex[0]][j] = e;//把边添加到压缩后的匹配边虚节点上
				matchEdge[j][B.back().vertex[0]] = e;
				

				e = T[B.back().vertex[i]][j] || T[B.back().vertex[0]][j];
				int e2 = 0;
				e2 =T[j][B.back().vertex[i]] || T[j][B.back().vertex[0]];

				if(T[j][B.back().vertex[0]] == -1)
				{
					root = B.back().vertex[0];//记录根节点,因为花苞中只有基节点可能是树根 
				}
				//把边添加到压缩后的树点上
				T[B.back().vertex[i]][j] = 0;//交错树相关边也去掉
				T[j][B.back().vertex[i]] = 0;
				T[B.back().vertex[0]][j] = e;
				T[j][B.back().vertex[0]] = e2;

				/////////////
				e = testEdge[B.back().vertex[i]][j] || testEdge[B.back().vertex[0]][j];
				e2 = 0;
				e2 =testEdge[j][B.back().vertex[i]] || testEdge[j][B.back().vertex[0]];
				
				if(testEdge[j][B.back().vertex[0]] == -1)
				{
					root = B.back().vertex[0];//记录根节点,因为花苞中只有基节点可能是树根 
				}
				//把边添加到压缩后的树点上
				testEdge[B.back().vertex[i]][j] = 0;//交错树相关边也去掉
				testEdge[j][B.back().vertex[i]] = 0;
				testEdge[B.back().vertex[0]][j] = e;
				testEdge[j][B.back().vertex[0]] = e2;
											
				//e = g.Edge[j][B.back().vertex[i]].isE || g.Edge[j][B.back().vertex[0]].isE;
				//g.Edge[j][B.back().vertex[i]].isE = 0;//去掉反向边
				//g.Edge[j][B.back().vertex[0]].isE = e;//把反向边添加到压缩后的点(基点)上
				//matchEdge[j][B.back().vertex[i]] = 0;
				//T[j][B.back().vertex[i]] = 0;
			}
		}
		//if( i == 0)
		//		{
		//			register int j = 0;
		//			for(j = 0; j < g.n; j++)
		//			{
		//				//记录花苞的边
		//				if(g.Edge[B.back().vertex[i]][j].isE == 1)
		//				{
		//					B.back().Edge[0][j] = 1;
		//					B.back().Edge[j][0] = 1;
		//				}
		//			}
		//		}
		
	}
	
	g.Edge[B.back().vertex[0]][B.back().vertex[0]].isE = 0;//防止出现虚节点自己到自己有边的情况
	matchEdge[B.back().vertex[0]][B.back().vertex[0]] = 0;
	T[B.back().vertex[0]][B.back().vertex[0]] = 0;
	for(i = 0; i < g.n; i++)
	{
		T[i][root] = -1;
	}
	//收缩后
	bVertex.push_back(B.back().vertex[0]);//把花苞的虚节点压到bVertex中
	B.back().vIndex = bVertex.size() - 1;
}

void MyMaxMatch::ufoldAll()
{//展开所有的花苞,从后向前展开
#if DEBUGMYMAXMATCH == 1
				cout<<"...开始展开花苞..."<<endl;
				cout<<"这时的图"<<endl;
				int t = 0;
				t = Ts.size();//显示匈牙利树的个数
				printG();
				printM();
#endif
	while (bVertex.size() != 0)
	{
		int bcount = bVertex.size();//花苞数
		if(B.size() != bcount)
		{//如果花苞和虚节点数不一致报错
			cout<<"花苞和虚节点数不一致!"<<endl;
			exit(0);/////////
		}
		int i = 0;
		for(i = bcount - 1; i > -1; i--)
		{//从后往前展开人造节点
			//int bnum = B[bcount].vertex.size();//花苞虚节点数后面都以此为基础
#if DEBUGMYMAXMATCH == 1
			cout<<"现在将展开的花苞："<<endl;
			B.back().printBlossom();
			B.back().printEdge();
			if(k > 0)
			{//如果存在匈牙利树
				Ts[k-1].printTreeMatch();
			}
			
#endif
			int bnum = B.back().vertex.size();//花苞虚节点数
			//int tmp = bVertex[i];//调试用
			if(expose[bVertex[i]] != 1)
			{//如果人造节点是饱和的,则正常展开
#if DEBUGMYMAXMATCH == 1
				int bV = bVertex[i];
#endif
				if(g.Vertex[bVertex[i]].num > -1)
				{//如果人造节点?是图上的节点
					int outI = 0;
					for(outI = 0; outI < g.n; outI++)
					{//得到虚节点对应的匹配点
						if((g.Vertex[outI].num > -1) && (matchEdge[B.back().vertex[0]][outI] == 1))
						{
							break;
						}
					}
#if DEBUGMYMAXMATCH == 1
					printM();
#endif
					register int j = 0;
					for(j = 0; j < bnum; j++)
					{
						//把图原来的节点还原
						g.Vertex[B.back().vertex[j]].num = B.back().vertex[j];
						//g.Edge还原
						register int k = 0;
						for(k = 0; k < g.n; k++)
						{							
							g.Edge[B.back().vertex[j]][k].isE = B.back().Edge[B.back().vertex[j]][k];
							g.Edge[k][B.back().vertex[j]].isE = B.back().Edge[k][B.back().vertex[j]];
						}
					}

					int bJ = 0;
					for(bJ = 0; bJ < bnum; bJ++)
					{//outI匹配点对应的花苞内节点
#if DEBUGMYMAXMATCH == 1
						int t = B.back().vertex[bJ];
						int t2 = bVertex[i];
						int t3 = B.back().vertex[0];
#endif
						if(g.Edge[outI][B.back().vertex[bJ]].isE == 1)
						{
							break;
						}
					}/**/
					//bJ = B.back().vertex[bJ];

					for(j = 0; j < bnum; j++)
					{
						expose[B.back().vertex[j]] = 1;//展开花苞之前先把所有的花苞节点设为非饱和
					}
					
					matchEdge[B.back().vertex[bJ]][outI] = 1;
					matchEdge[outI][B.back().vertex[bJ]] = 1;
					expose[B.back().vertex[bJ]] = 0;//但是这个节点应该最终饱和
					expose[outI] = 0;

					for(j = 0; j < bnum; j++)
					{
						register int k = 0;
						//把匹配边还原
						if((j & 1) == 1 && (j < bnum))
						{//不让bJ成为花苞的饱和节点
							for(k = 0; k < g.n; k++)
							{//
								if(matchEdge[B.back().vertex[0]][k] == 1)
								{
									if(g.Edge[B.back().vertex[0]][k].isE == 0)
									{
										matchEdge[B.back().vertex[0]][k] = 0;
										matchEdge[k][B.back().vertex[0]] = 0;
									}
									break;
								}
							}
							//matchEdge[B.back().vertex[j]][B.back().vertex[j+1]] = 1;
							//matchEdge[B.back().vertex[j+1]][B.back().vertex[j]] = 1;
							//expose[B.back().vertex[j]] = 0;
							//expose[B.back().vertex[j+1]] = 0;
							matchEdge[B.back().vertex[(j + bJ) % (bnum)]][B.back().vertex[(j + bJ +1) % (bnum)]] = 1;
							matchEdge[B.back().vertex[(j + bJ +1) % (bnum)]][B.back().vertex[(j + bJ) % (bnum)]] = 1;
							expose[B.back().vertex[(j + bJ) % (bnum)]] = 0;
							expose[B.back().vertex[(j + bJ +1) % (bnum)]] = 0;
						}
					}
				}//if(g.Vertex[bVertex[i]].num > -1)
				else
				{//否则那么就是树上的节点
					//if(k < Ts.size())
					{
						if(B.back().treeIndex >= k-1)
						{//如果有它的匈牙利树:1/恢复节点(只能将节点插入匈牙利树结点)2/得到匈牙利树的饱和点3/恢复匹配边4/k
							int outI = 0;
							for(outI = 0; outI < g.n; outI++)
							{//得到虚节点对应的匹配点
								if(Ts[k].treeMatch[B.back().vertex[0]][outI] == 1)
								{
									break;
								}
							}
							
							int bJ = 0;
							for(bJ = 0; bJ < bnum; bJ++)
							{//outI匹配点对应的花苞内节点bJ
								if(B.back().Edge[outI][B.back().vertex[bJ]] == 1)
								{
									break;
								}
							}
							register int j = 0;
							
							
							//把花苞上的点加到匈牙利上面
							int t = 0;//把花苞上的点加到匈牙利树上的临时交换变量
							if(find(Ts[B.back().treeIndex].tv.begin(),Ts[B.back().treeIndex].tv.end(),B.back().vertex[0]) != Ts[B.back().treeIndex].tv.end())
							{//如果虚节点是树上的节点
								for(j = 1; j < bnum; j++)
								{//把花苞上的点加到匈牙利树上
									t = B.back().vertex[j];
									Ts[B.back().treeIndex].tv.push_back(t);
								}
								
								for(j = 0; j < bnum; j++)
								{
									expose[B.back().vertex[j]] = 1;//展开花苞之前先把所有的花苞节点设为非饱和
								}
								
								for(int k = 0; k < g.n; k++)
								{
									Ts[B.back().treeIndex].treeMatch[B.back().vertex[0]][k] = 0;
									Ts[B.back().treeIndex].treeMatch[k][B.back().vertex[0]] = 0;
								}
								
								Ts[k].treeMatch[B.back().vertex[bJ]][outI] = 1;
								Ts[k].treeMatch[outI][B.back().vertex[bJ]] = 1;
								expose[B.back().vertex[bJ]] = 0;//但是这个节点应该最终饱和
								expose[outI] = 0;
							}
							
							//因为虚节点是饱和的,所以考虑怎样找到花苞匹配边的还原???
							///???多于匈牙利树多于一个花苞以及多于一棵匈牙利树此处容易出现问题???
							
							for(j = 0; j < bnum; j++)
							{
								register int k = 0;
								
								//把匹配边还原
								if(((j & 1) == 1) && (j < bnum))
								{//奇数节点作为饱和边的起点,饱和点对应花苞内的节点？
									//Ts[B.back().treeIndex].treeMatch[B.back().vertex[j]][B.back().vertex[j + 1]] = 1;
									//Ts[B.back().treeIndex].treeMatch[B.back().vertex[j + 1]][B.back().vertex[j]] = 1;
									//expose[B.back().vertex[j]] = 0;
									//expose[B.back().vertex[j+1]] = 0;
									Ts[B.back().treeIndex].treeMatch[B.back().vertex[(j + bJ) % (bnum)]][B.back().vertex[(j + bJ + 1) % (bnum)]] = 1;
									Ts[B.back().treeIndex].treeMatch[B.back().vertex[(j + bJ + 1) % (bnum)]][B.back().vertex[(j + bJ) % (bnum)]] = 1;
									expose[B.back().vertex[(j + bJ) % (bnum)]] = 0;
									expose[B.back().vertex[(j + bJ +1) % (bnum)]] = 0;
#if DEBUGMYMAXMATCH == 1
									Ts[B.back().treeIndex].printTreeMatch();//lkdebug
#endif
								}						
							}						
						}	
						if(B.back().treeIndex == k-1)
						{
							k--;
						}
					}					
				}
#if DEBUGMYMAXMATCH == 1
				cout<<"展开之后"<<endl;
				printG();
				printM();
				if(k > 0)
				{
					Ts.back().printTreeMatch();
				}			
#endif
			}
			else
			{//否则任选一个节点作为饱和节点展开
				if(g.Vertex[bVertex[i]].num > -1)
				{//如果是图上的节点
					register int j = 0;
					for(j = 0; j < bnum; j++)
					{
						//把图原来的节点还原
						g.Vertex[B.back().vertex[j]].num = B.back().vertex[j];
						expose[B.back().vertex[j]] = 1;//展开花苞之前先把所有的花苞节点设为非饱和
					}
					for(j = 0; j < bnum; j++)
					{
						register int k = 0;
						//还原图原来的边
						for(k = 0; k < g.n; k++)
						{
							g.Edge[B.back().vertex[j]][k].isE = B.back().Edge[B.back().vertex[j]][k];
							g.Edge[k][B.back().vertex[j]].isE = B.back().Edge[k][B.back().vertex[j]];
						}
						//把匹配边还原
						if(((j & 1) == 0) && (j < bnum - 1))
						{//偶数节点作为饱和边的起点
							for(k = 0; k < g.n; k++)
							{//
								if(matchEdge[B.back().vertex[0]][k] == 1)
								{
									if(g.Edge[B.back().vertex[0]][k].isE == 0)
									{
										matchEdge[B.back().vertex[0]][k] = 0;
										matchEdge[k][B.back().vertex[0]] = 0;
									}
									break;
								}
							}
							matchEdge[B.back().vertex[j]][B.back().vertex[j+1]] = 1;
							matchEdge[B.back().vertex[j+1]][B.back().vertex[j]] = 1;
							expose[B.back().vertex[j]] = 0;
							expose[B.back().vertex[j+1]] = 0;
							//matchEdge[B.back().vertex[(j + bJ) % (bnum)]][B.back().vertex[(j + bJ +1) % (bnum)]] = 1;
							//matchEdge[B.back().vertex[(j + bJ +1) % (bnum)]][B.back().vertex[(j + bJ) % (bnum)]] = 1;
						}						
					}
				}
				else
				{//否则那么就是树上的节点
					//if(k < Ts.size())
					{
						if(B.back().treeIndex >= k-1)
						{//如果有它的匈牙利树
							register int j = 0;
							int t = 0;//把花苞上的点加到匈牙利树上的临时交换变量
							if(find(Ts[B.back().treeIndex].tv.begin(),Ts[B.back().treeIndex].tv.end(),B.back().vertex[0]) != Ts[B.back().treeIndex].tv.end())
							{//如果虚节点是树上的节点,此句没有用？
								for(j = 1; j < bnum; j++)
								{//把花苞上的点加到匈牙利树上
									t = B.back().vertex[j];
									Ts[B.back().treeIndex].tv.push_back(t);
								}
								for(int k = 0; k < g.n; k++)
								{
									Ts[B.back().treeIndex].treeMatch[B.back().vertex[0]][k] = 0;
									Ts[B.back().treeIndex].treeMatch[k][B.back().vertex[0]] = 0;
								}
							}
							for(j = 0; j < bnum; j++)
							{
								register int k = 0;
								//把匹配边还原
								if(((j & 1) == 0) && (j < bnum - 1))
								{//偶数节点作为饱和边的起点
									Ts[B.back().treeIndex].treeMatch[B.back().vertex[j]][B.back().vertex[j + 1]] = 1;
									Ts[B.back().treeIndex].treeMatch[B.back().vertex[j + 1]][B.back().vertex[j]] = 1;
									expose[B.back().vertex[j]] = 0;
									expose[B.back().vertex[j+1]] = 0;
									//Ts[B.back().treeIndex].treeMatch[B.back().vertex[(j + bJ) % (bnum)]][B.back().vertex[(j + bJ + 1) % (bnum)]] = 1;
									//Ts[B.back().treeIndex].treeMatch[B.back().vertex[(j + bJ + 1) % (bnum)]][B.back().vertex[(j + bJ) % (bnum)]] = 1;
#if DEBUGMYMAXMATCH == 1
									Ts[B.back().treeIndex].printTreeMatch();//lkdebug
#endif
								}						
							}
						}
						if(B.back().treeIndex == k-1)
						{
							k--;
						}
						
					}
					
				}
#if DEBUGMYMAXMATCH == 1
				cout<<"展开之后"<<endl;
				printG();
				printM();
				Ts.back().printTreeMatch();
#endif
			}
			//展开之后要去掉尾部
			bVertex.erase(bVertex.end()-1);
			B.erase(B.end()-1);
		}		
	}//while(bVertex.size)
	for(int i = 0; i < Ts.size(); i++)
	{
		int j = 0;
		int k = 0;
		for(j = 0; j < g.n; j++)
		{
			for(k = 0; k < g.n; k++)
			{
				matchEdge[j][k] = matchEdge[j][k] || Ts[i].treeMatch[j][k];
			}
		}
	}
#if DEBUGMYMAXMATCH == 1
				cout<<"...展开花苞完毕..."<<endl;
#endif	
}
/*void MyMaxMatch::getHut()
{}*/
void MyMaxMatch::processHut()
{//处理匈牙利树
#if DEBUGMYMAXMATCH == 1
				cout<<"...开始处理匈牙利树..."<<endl;
#endif
	vector<int> tv;//记录匈牙利树上面的点
	int i = 0;
	for(i = 0; i < g.n; i++)
	{
		register int j = 0;
		for(j = 0; j < g.n; j++)
		{
			if((T[i][j] > 0) || (T[j][i] > 0) || T[j][i] == -1)
			{
				tv.push_back(i);
				//cout<<i;
				break;
				
			}
		}
	}
	//增加一个匈牙利树结点每次都是从尾部
	k++;//指示下一次将要插入匈牙利树的下标
	Ts.push_back(*(new MyHut(g.n)));
	//Ts.back().num = g.n;
	Ts.back().tv = tv;
	Ts.back().tree = T;
	////在图上去掉匈牙利树上的点和与之关联的边,匹配边
#if DEBUGMYMAXMATCH == 1
	/*cout<<"下面显示T的点："<<endl;
	for(i = 0; i < tv.size(); i++)
	{
		cout<<Ts.back().tv[i]<<',';
	}
	cout<<endl;
	cout<<"T的点显示完毕"<<endl;*/
#endif
	//获取匈牙利树的匹配边
	for(i = 0; i < g.n; i++)
	{
		register int j = 0;
		for(j = 0; j < g.n; j++)
		{
#if DEBUGMYMAXMATCH == 1
			//cout<<tv[23];
			//cout<<Ts.back().tv[23];
			/*int **tmp = Ts.back().tree;
			cout<<"赋值后链表匈牙利树:"<<endl;
			int tmpi = 0;
			for(tmpi = 0; tmpi < g.n; tmpi++)
			{
				register int tmpj = 0;
				for(tmpj = 0; tmpj < g.n; tmpj++)
				{
					//cout<<tmp[tmpi][tmpj]<<',';
					//if(Ts.back().tree != NULL)
					cout<<Ts.back().tree[tmpi][tmpj]<<',';
				}
				cout<<endl;