mymaxmatch.h

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

#ifndef __myMaxMatch_h__
#define __myMaxMatch_h__
#include"myGraph.h"
#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
#define DEBUGMYMAXMATCH 1//调试开关
class MyMaxMatch  
{
public:
	class MyBlossom;
	class MyHut;
	MyMaxMatch(MyGraph& graph);
	virtual ~MyMaxMatch();

	//MyGraph& compute();//计算最大匹配
	void compute();
	void initial();//初始化
	char testMatchV();//检查图中的饱和点根据不同的返回值转向不同的处理
	int getExposed();//获得一个非饱和节点，返回下标否则返回-1
	//选择一条与T中某个外点ii关联的不属于T&testEdge的边(ii,j),返回j
	int selectEdge(int& ii);

	char growTree();//构造图中的交替树根据不同的返回值转向不同的处理
	void processP(int j);//处理增广链
	int getBlossom();//得到花苞得到当前图中的花苞，把花苞的点依次存放到blossom中，并返回花苞的个数
	void processB();//处理花苞
	void shrink();//收缩花苞
	void ufoldAll();//展开所有的花苞
//	void getHut();//获得匈牙利树
	void processHut();//处理匈牙利树
	//打印匹配边调试用
	void printM();
	//打印图的点和边调试用
	void printG();
	//打印交错树的点和边调试用
	void printT();


	MyGraph g;//输入的图的副本
	vector<MyBlossom> B;//图中依次形成的花苞（0-n）
	
	int k;//匈牙利树的下标
	int pj;//处理增广路径时的回溯起点下标
	int **T;//交替树应该是有向图，树根列全是-1，树边全是1，无边是0，花苞相连外点处边为2
	vector<MyHut> Ts;//匈牙利树的数组
	int **matchEdge;//图的匹配边集合
	int **testEdge;//标志一条边是否被检测??
	int *expose;//是否是非饱和节点
	int *label;//记录点的标记是外部点还是别的等
	vector<int> bVertex;//人造节点,静态数组，如果不是它的点那么为负数
};
//花苞
class MyMaxMatch::MyBlossom
{//花苞节点
public:
	MyBlossom();
	//
	MyBlossom(const MyBlossom& b);
	~MyBlossom();
	//初始化花苞的边,供外部调用
	void initialE();
	//打印花苞节点，调试时用
	void printBlossom();
	//打印花苞的边,调试时用
	void printEdge();
	//
	MyBlossom& operator=(const MyBlossom& b);
	//记录花苞的所有边
	int** Edge;
	//记录花苞中所有的点
	vector<int> vertex;//花苞的节点
	//记录花苞对应的基点数组的下标,也是表示第几个花苞的下标
	int vIndex;
	//记录花苞如果是匈牙利树的花苞，则需要修改的的匈牙利树数组的下标
	int treeIndex;
	//一个传递图的节点数的外部变量的拷贝。
	int n;
};

//匈牙利树
class MyMaxMatch::MyHut
{//匈牙利树的结构
public:
	MyHut();
	MyHut(int num);
	MyHut(const MyHut& h);
	~MyHut();
	MyHut& operator=(const MyHut& h);
	void printTreeMatch();
	void printTree();
	vector<int> tv;//记录匈牙利树的节点
	int** tree;//记录匈牙利树
	int **treeMatch;//记录匈牙利树的匹配边
	int num;//记录边的维数
};
#endif