最佳匹配·可视化.cpp

最佳匹配·可视化c++实现

#include <windows.h>
#include <stdio.h>

HWND hwnd;
char str[255];
const int SCREEN_WIDTH = 640, SCREEN_HEIGHT = 480;
const int UP_MARGIN = SCREEN_HEIGHT / 4, DOWN_MARGIN = SCREEN_HEIGHT / 3;
int maxX, maxY;	/* screen dimensions */
HDC hdc, memdc; /* store the virtual device handle */
HBITMAP hbit; /* store the virtual bitmap */
HBRUSH hbrush; /* store the brush handle */
HGDIOBJ hOldbit,hOldbrush;
HPEN hOldpen;	/* handle of old pen */
HPEN hRedpen, hGreenpen, hBluepen, hYellowpen;	/* create pens */
PAINTSTRUCT paintstruct;

char szWinName[] = "MyWin";	/* name of window class */
LRESULT CALLBACK WindowFunc(HWND, UINT, WPARAM, LPARAM);

#include <iostream.h>				// 为了调用 cout 函数
#include <stdlib.h>					// 为了调用 srand 和 rand 函数
#include <time.h>					// 为了调用 time 函数

const int VERTEX_OF_X = 5;			// 设置二分图 G 中 X 点集的大小为 VERTEX_OF_X
const int VERTEX_OF_Y = 5;			// 设置二分图 G 中 Y 点集的大小为 VERTEX_OF_Y
const int MIN_WEIGHT = 0;			// 设置二分图 G 中边权最小值
const int MAX_WEIGHT = 9;			// 设置二分图 G 中边权最大值

int xPosX[VERTEX_OF_X];
int xPosY[VERTEX_OF_X];
int yPosX[VERTEX_OF_Y];
int yPosY[VERTEX_OF_Y];

signed int Weight[VERTEX_OF_X][VERTEX_OF_Y];// 用于标记二分图 G = (X, E, Y) 中的已知边集 E
											// 说明：Weight 的值表示边权（可正可负）。
signed int LabelX[VERTEX_OF_X];				// 用于在寻找最佳匹配过程中对 X 的点作标记
											// 说明：LabelX 的值应当满足 LabelX + LabelY >= Weight[X][Y]。
signed int LabelY[VERTEX_OF_Y];				// 用于在寻找最佳匹配过程中对 Y 的点作标记
											// 说明：LabelY 的值应当满足 LabelX + LabelY >= Weight[X][Y]。
int Edge[VERTEX_OF_X][VERTEX_OF_Y];			// 用于标记二分图 G = (X, E, Y) 中的已知边集 E
											// 说明：Edge 的值为 0 表示无，为 1 表示有。
int Match[VERTEX_OF_X][VERTEX_OF_Y];		// 用于标记二分图 G = (X, E, Y) 中的最佳匹配 M
											// 说明：Match 的值为 0 表示无，1 表示有。

void InitWeight();					// 用于初始化 Weight
void InitLabelX();					// 用于初始化 LabelX
void InitLabelY();					// 用于初始化 LabelY
void InitEdge();					// 用于初始化 Edge
void InitMatch();					// 用于初始化 Match

void DisplayWeight();				// 用于显示 Weight
void DisplayLabelX();				// 用于显示 LabelX
void DisplayLabelY();				// 用于显示 LabelY
void DisplayEdge();					// 用于显示 Edge
void DisplayMatch();				// 用于显示 Match

void GenerateWeight();				// 用于随机产生 Weight
void GenerateInitialMatch();		// 用于产生初始化匹配 Match
void GetFeasibleVertexLabeling();	// 对二分图 G 进行任意可行顶点标号 L
void DetermineEqualitySubgraph();	// 确定相对应于 L 的等同子图 GL
void GenerateOptimalAssignment();	// 用于产生最佳匹配

int GetNumberOfWeight();			// 用于获取边集 Weight 的大小
int GetNumberOfEdge();				// 用于获取等同子图 GL 的边集 Edge 的大小
int GetSizeOfMatch();				// 用于获取匹配 M 的大小
int IsMCompleteForG();				// 确定 Match 是否为 Weight 的完美匹配

int S[VERTEX_OF_X];					// 用于产生最佳匹配，存放 X 的顶点
int T[VERTEX_OF_Y];					// 用于产生最佳匹配，存放 Y 的顶点
int JS[VERTEX_OF_Y];				// 用于产生最佳匹配，存放 X 的邻接顶点
int TC[VERTEX_OF_Y];				// 用于产生最佳匹配，存放 Y 的顶点，是 T 关于 Y 的补集

int SizeOfS;						// 用于记录集合 S 的当前大小
int SizeOfT;						// 用于记录集合 T 的当前大小
int SizeOfJS;						// 用于记录集合 JS 的当前大小
int SizeOfTC;						// 用于记录集合 TC 的当前大小

void InitS();						// 用于初始化 S
void InitT();						// 用于初始化 T
void InitJS();						// 用于初始化 JS
void InitTC();						// 用于初始化 TC

void DisplayS();					// 用于显示 S
void DisplayT();					// 用于显示 T
void DisplayJS();					// 用于显示 JS
void DisplayTC();					// 用于显示 TC

int GenerateS();					// 产生 S 并对其进行整理（包含排序和去重）
void DefragT();						// 对 T 进行整理（包含排序和去重）
void GenerateJS();					// 产生 JS 并对其进行整理（包含排序和去重）
void GenerateTC();					// 产生 TC 并对其进行整理（包含排序和去重）
int IsJSEqualT();					// 判断 JS 和 T 是否相等

int Al;								// 用于存放 Al 的值
int FindAl();						// 计算 Al 的值并返回
void ConstructANewLabeling();		// 构建一个新的标号 L'
void FindMAlternatingPath(int x);	// 发现一个从 X 到 Y 的 M - 交错路径
void GenerateLargerMatching(int y);	// 根据 M - 交错路径 产生 Gl 中的一个更大的匹配 M'
int GetSumOfWeight();				// 计算最佳匹配中的边权之和

signed int MarkX[VERTEX_OF_X];		// 用于在寻找 M - 交错路径 过程中对 X 的点作标记
									// 说明：MarkX 的值为 -2（初始无标记），-1（标记为 * ），j（标记为 Yj）。
signed int MarkY[VERTEX_OF_Y];		// 用于在寻找 M - 交错路径 过程中对 Y 的点作标记
									// 说明：MarkY 的值为 -2（初始无标记），-1（标记为 * ），i（标记为 Xi）。
signed int ScanX[VERTEX_OF_X];		// 用于在寻找 M - 交错路径 过程中对 X 的点作扫描
									// 说明：ScanX 的值为 0（初始未扫描），1（已扫描）。
signed int ScanY[VERTEX_OF_Y];		// 用于在寻找 M - 交错路径 过程中对 Y 的点作扫描
									// 说明：ScanX 的值为 0（初始未扫描），1（已扫描）。

void InitMarkX();					// 用于初始化 MarkX
void InitMarkY();					// 用于初始化 MarkY
void InitScanX();					// 用于初始化 ScanX
void InitScanY();					// 用于初始化 ScanY

void DisplayMarkX();				// 用于显示 MarkX
void DisplayMarkY();				// 用于显示 MarkY
void DisplayScanX();				// 用于显示 ScanX
void DisplayScanY();				// 用于显示 ScanY

int WINAPI WinMain(HINSTANCE hThisInst, HINSTANCE hPrevInst, LPSTR lpszArgs,int nWinMode)
{
	MSG msg;
	WNDCLASSEX wcl;

	/* Define a window class. */
	wcl.cbSize = sizeof(WNDCLASSEX);
	wcl.hInstance = hThisInst; /* handle to this instance */
	wcl.lpszClassName = szWinName; /* window class name */
	wcl.lpfnWndProc = WindowFunc; /* window function */
	wcl.style = 0; /* default style */

	wcl.hIcon = LoadIcon(NULL,IDI_APPLICATION); /* standard icon */
	wcl.hIconSm = LoadIcon(NULL,IDI_WINLOGO); /* SMALL ICON */
	wcl.hCursor = LoadCursor(NULL,IDC_ARROW); /* cursor style */

	/* Specify name of menu resource. This will be overridden. */
	wcl.lpszMenuName = NULL; /* main menu */
	wcl.cbClsExtra = 0; /* no extra information needed */
	wcl.cbWndExtra = 0;	/* no extra information needed */
	
	/* Make the windows backgraoud white */
	wcl.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH);

	/* Register the window class. */
	if(!RegisterClassEx(&wcl))
		return 0;

	/* Now that a window class has been registered, a window can be created. */
	hwnd = CreateWindow(
			szWinName,	/* name of window class */
			"最佳匹配·可视化", /* title */
			WS_OVERLAPPEDWINDOW, /* window style - normal */
			CW_USEDEFAULT,	/* X coordinate - let Winodws decide */
			CW_USEDEFAULT,	/* Y coordinate - let Windows decide */
			SCREEN_WIDTH,	/* width - let Windows decide */
			SCREEN_HEIGHT,	/* height - let Windows decide */
			HWND_DESKTOP, /* no parent window */
			NULL,  /*  no menu */
			hThisInst, /* handle of this instance of the program */
			NULL /* no additional arguments */
			);

	/* Display the windows. */
	ShowWindow(hwnd, nWinMode);
	UpdateWindow(hwnd);

	// 初始化随机数发生器
	srand((unsigned)time(NULL));

	// 初始化 Weight, LabelX, LabelY, Edge, Match
	InitWeight();
	InitLabelX();
	InitLabelY();
	InitEdge();
	InitMatch();
	
	// 随机产生二分图 G 中的有权边集 Weight
	GenerateWeight();
	DisplayWeight();

	// Start with an arbitrary feasible vertex labeling l, determine Gl, and choose
	// an arbitrary matching M in Gl.
	
	// 对二分图 G 进行任意可行顶点标号 L（Feasible Vertex Labeling），
	GetFeasibleVertexLabeling();
	//DisplayLabelX();
	//DisplayLabelY();

	// 并由此确定相对应于 L 的等同子图 GL 的无权边集（Equality Subgraph for L）。
	DetermineEqualitySubgraph();
	//DisplayEdge();
	
	// 寻找等同子图 GL 中的一个任意的初始化匹配 M
	GenerateInitialMatch();
	//cout << "初始化匹配为" << endl;
	//DisplayMatch();

	// 使用 The Kuhn-Munkres Algorithm 算法（亦称为 the Hungarian method 方法）产生最佳匹配
	GenerateOptimalAssignment();

	/* Create the message loop. */
	while (GetMessage(&msg, NULL, 0, 0)){
		TranslateMessage(&msg); /* translate keyboard messages */
		DispatchMessage(&msg); /* return control to Windows 98 */
	}
	return msg.wParam;
}
/* This function is called by Windows 98 and is passed 
	messages from the message gueue.
*/
LRESULT CALLBACK WindowFunc(HWND hwnd, UINT message,WPARAM wParam, LPARAM lParam)
{	
	switch(message) {
	case WM_CREATE:
		/* get screen coordinates */
		maxX = GetSystemMetrics(SM_CXSCREEN);
		maxY = GetSystemMetrics(SM_CYSCREEN);

		/* make a compatible memory image */
		hdc = GetDC(hwnd);
		memdc = CreateCompatibleDC(hdc);
		
		hbit = CreateCompatibleBitmap(hdc,maxX,maxY);
		hOldbit = SelectObject(memdc,hbit);

		hbrush = (HBRUSH)GetStockObject(WHITE_BRUSH);
		hOldbrush = SelectObject(memdc,hbrush);

		PatBlt(memdc,0,0,maxX,maxY,PATCOPY);

		hRedpen = CreatePen(PS_SOLID, 2, RGB(255,0,0));
		hGreenpen = CreatePen(PS_SOLID, 2, RGB(0,255,0));
		hBluepen = CreatePen(PS_SOLID, 2, RGB(0,0,255));
		hYellowpen = CreatePen(PS_SOLID, 4, RGB(255,255,0));

		hOldpen = (HPEN)SelectObject(memdc,hRedpen);
		SelectObject(memdc,hOldpen);

		ReleaseDC(hwnd,hdc);
		break;
	case WM_PAINT:
		hdc = BeginPaint(hwnd,&paintstruct); /* get DC */
		/* now,copy memory image onto screen */
		BitBlt(hdc,0,0,maxX,maxY,memdc,0,0,SRCCOPY);
		EndPaint(hwnd,&paintstruct); /* release DC */
		break;
	case WM_DESTROY: /* terminate the program */
		/* delete pens */
		DeleteObject(hRedpen);
		DeleteObject(hGreenpen);
		DeleteObject(hBluepen);
		DeleteObject(hYellowpen);

		SelectObject(memdc,hOldbrush);
		DeleteObject(hbrush);

		SelectObject(memdc,hOldbit);
		DeleteObject(hbit);

		DeleteDC(memdc);
		PostQuitMessage(0);
		break;
	default:
		/* Let Windows 98 process any messages not specified in the preceding switch statement. */
		return DefWindowProc(hwnd,message,wParam,lParam);
	}
	return 0;
}

void GenerateOptimalAssignment(){
	int i, j, k, x, y, z;
	// 1. If M is complete for G, then M is optimal. Stop. Otherwise, there is some unmatched
	//    x (- X. Set S = {x} and T = NULL.
Step1:
	if (IsMCompleteForG() == 1){
		//cout << "M is optimal. Stop." << endl;
		cout << "最佳匹配（其权和为 " << GetSumOfWeight() << " ）为" << endl;
		DisplayMatch();
		return;
	}
	else{
		//cout << "There is some unmatched x (- X." << endl;
		InitS();
		x = GenerateS();
		//DisplayS();
		InitT();
	}

	// 2. If Jgl(S) != T, go to step 3. Otherwise, Jgl(S) = T. Find
	//						Al	=	min	{ l(x) + l(y) - w(xy) }
	//							x(-S, y(-Tc
	//	  where Tc denotes the complement of T in Y, and construct a new labeling l' by
	//								l(v) - Al		for v (- S
	//						l'(v) = l(v) + Al		for v (- T
	//								l(v)			otherwise
	//	  Note that Al > 0 and Jgl'(S) != T. Replace l by l' and gl by gl'.
Step2:
	InitJS();
	GenerateJS();
	//DisplayJS();

	DefragT();
	//DisplayT();

	if (IsJSEqualT() == 0){
		goto Step3;
	}
	else{
		InitTC();
		GenerateTC();
		//DisplayTC();

		Al = FindAl();
		//cout << "Al = " << Al << endl;	// Note that Al > 0.

		ConstructANewLabeling();
		//DisplayLabelX();
		//DisplayLabelY();

		DetermineEqualitySubgraph();
		//DisplayEdge();

		InitJS();
		GenerateJS();
		//DisplayJS();
		//cout << "IsJSEqualT() = " << IsJSEqualT() << endl;	// Note that JS != T.
	}

	// 3. Choose a vertex y in Jgl(S), not in T. If y is matched in M, say with z (- X,
	//    replace S by S + {z} and T by T + {y}, and go to step 2. Otherwise, there will
	//    be an M-alternating path from x to y, and we may use this path to find a larger
	//    matching M' in Gl. Replace M by M' and go to step 1.
Step3:
	for (j = 0; j < SizeOfJS; j++){
		for (k = 0; k < SizeOfT; k++){
			if (T[k] == JS[j]){
				break;
			}
		}
		if (k == SizeOfT){
			y = JS[j];
			break;
		}
	}

	for (i = 0; i < VERTEX_OF_X; i++){
		if (Match[i][y] == 1){
			z = i;
			break;
		}
	}
	if (i != VERTEX_OF_X){
		S[SizeOfS++] = z;
		T[SizeOfT++] = y;
		goto Step2;
	}
	else{
		InitMarkX();		InitMarkY();		InitScanX();		InitScanY();
		//DisplayMarkX();	DisplayMarkY();		DisplayScanX();		DisplayScanY();
		FindMAlternatingPath(x);
		GenerateLargerMatching(y);
		goto Step1;
	}
}

int GetSumOfWeight(){
	int SumOfWeight = 0;
	for (int i = 0; i < VERTEX_OF_X; i++){
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (Match[i][j] == 1){
				SumOfWeight = SumOfWeight + Weight[i][j];
			}
		}
	}
	return SumOfWeight;
}

void FindMAlternatingPath(int x){
	int i, j, NewMarkAddToX, NewMarkAddToY;
	NewMarkAddToX = 0;
	MarkX[x] = -1;
	NewMarkAddToX++;
	while (NewMarkAddToX != 0){
		NewMarkAddToY = 0;
		for (i = 0; i < VERTEX_OF_X; i++){
			if ((MarkX[i] != -2) && (ScanX[i] == 0)){
				for (j = 0; j < VERTEX_OF_Y; j++){
					if ((MarkY[j] == -2) && (Edge[i][j] == 1) && (Match[i][j] == 0)){
						MarkY[j] = i;
						NewMarkAddToY++;
					}
				}
				ScanX[i] = 1;
			}
		}
		if (NewMarkAddToY == 0)
			return;
		NewMarkAddToX = 0;
		for (j = 0; j < VERTEX_OF_Y; j++){
			if ((MarkY[j] != -2) && (ScanY[j] == 0)){
				for (i = 0; i < VERTEX_OF_X; i++){
					if ((MarkX[i] == -2) && (Edge[i][j] == 1) && (Match[i][j] == 1)){
						MarkX[i] = j;
						NewMarkAddToX++;
					}
				}
				ScanY[j] = 1;
			}
		}
	}
}

void GenerateLargerMatching(int y){
	int i, j, flag;
	flag = 1;
	i = MarkY[y];
	Match[i][y] = 1;
	while (MarkX[i] != -1){
		if (flag == 1){
			flag = 0;
			j = MarkX[i];
			Match[i][j] = 0;
		}
		else{
			flag = 1;
			i = MarkY[j];
			Match[i][j] = 1;
		}
	}
}


void ConstructANewLabeling(){
	for (int i = 0; i < SizeOfS; i++){
		LabelX[S[i]] = LabelX[S[i]] - Al;
	}
	for (int j = 0; j < SizeOfT; j++){
		LabelY[T[j]] = LabelY[T[j]] + Al;
	}
}

int FindAl(){
	int min = LabelX[S[0]] + LabelY[TC[0]] - Weight[S[0]][TC[0]];
	for (int i = 0; i < SizeOfS; i++){
		for (int j = 0; j < SizeOfTC; j++){
			if (LabelX[S[i]] + LabelY[TC[j]] - Weight[S[i]][TC[j]] < min){
				min = LabelX[S[i]] + LabelY[TC[j]] - Weight[S[i]][TC[j]];
			}
		}
	}
	return min;
}

void GenerateTC(){
	int j, k, l, temp;
	// Step 1: 产生
	for (j = 0; j < VERTEX_OF_Y; j++){
		for (k = 0; k < SizeOfT; k++){
			if (T[k] == j){
				break;
			}
		}
		if (k == SizeOfT)
			TC[SizeOfTC++] = j;
	}
	// Step 2: 排序
	for (j = 0; j < SizeOfTC; j++){
		for (k = j + 1; k < SizeOfTC; k++){
			if (TC[j] > TC[k]){
				temp = TC[j];
				TC[j] = TC[k];