最佳匹配·可视化.cpp

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

				TC[k] = temp;
			}
		}
	}
	// Step 3: 去重
	for (j = 0; j < SizeOfTC; j++){
		for (k = j + 1; k < SizeOfTC; k++){
			if (TC[k] == TC[j]){
				k--;
				SizeOfTC--;
				for (l = k; l < SizeOfTC; l++){
					TC[l] = TC[l + 1];
				}
			}
			else
				break;
		}
	}
}

int IsJSEqualT(){
	if (SizeOfJS != SizeOfT)
		return 0;
	else{
		for (int j = 0; j < SizeOfJS; j++){
			if (JS[j] != T[j]){
				break;
			}
		}
		if (j != SizeOfJS)
			return 0;
		else
			return 1;
	}
}

void DefragT(){
	int j, k, l, temp;
	// Step 1: 排序
	for (j = 0; j < SizeOfT; j++){
		for (k = j + 1; k < SizeOfT; k++){
			if (T[j] > T[k]){
				temp = T[j];
				T[j] = T[k];
				T[k] = temp;
			}
		}
	}
	// Step 2: 去重
	for (j = 0; j < SizeOfT; j++){
		for (k = j + 1; k < SizeOfT; k++){
			if (T[k] == T[j]){
				k--;
				SizeOfT--;
				for (l = k; l < SizeOfT; l++){
					T[l] = T[l + 1];
				}
			}
			else
				break;
		}
	}
}

void GenerateJS(){
	// Step 1: 产生
	for (int i = 0; i < SizeOfS; i++){
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (Edge[S[i]][j] == 1){
				JS[SizeOfJS++] = j;
			}
		}
	}
	int j, k, l, temp;
	// Step 2: 排序
	for (j = 0; j < SizeOfJS; j++){
		for (k = j + 1; k < SizeOfJS; k++){
			if (JS[j] > JS[k]){
				temp = JS[j];
				JS[j] = JS[k];
				JS[k] = temp;
			}
		}
	}
	// Step 3: 去重
	for (j = 0; j < SizeOfJS; j++){
		for (k = j + 1; k < SizeOfJS; k++){
			if (JS[k] == JS[j]){
				k--;
				SizeOfJS--;
				for (l = k; l < SizeOfJS; l++){
					JS[l] = JS[l + 1];
				}
			}
			else
				break;
		}
	}
}

int GenerateS(){
	// Step 1: 产生
	int s;
	for (int i = 0; i < VERTEX_OF_X; i++){
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (Match[i][j] == 1)
				break;
		}
		if (j == VERTEX_OF_Y){
			S[SizeOfS++] = i;
			s = i;
			break;
		}
	}
	int j, k, l, temp;
	// Step 2: 排序
	for (j = 0; j < SizeOfS; j++){
		for (k = j + 1; k < SizeOfS; k++){
			if (S[j] > S[k]){
				temp = S[j];
				S[j] = S[k];
				S[k] = temp;
			}
		}
	}
	// Step 3: 去重
	for (j = 0; j < SizeOfS; j++){
		for (k = j + 1; k < SizeOfS; k++){
			if (S[k] == S[j]){
				k--;
				SizeOfS--;
				for (l = k; l < SizeOfS; l++){
					S[l] = S[l + 1];
				}
			}
			else
				break;
		}
	}
	return s;
}

int IsMCompleteForG(){
	if ((VERTEX_OF_X == VERTEX_OF_Y) && (VERTEX_OF_X == GetSizeOfMatch())){
		int NumberOfEdge;
		for (int i = 0; i < VERTEX_OF_X; i++){
			NumberOfEdge = 0;
			for (int j = 0; j < VERTEX_OF_Y; j++){
				if (Match[i][j] == 1)
					NumberOfEdge++;
			}
			if (NumberOfEdge != 1)
				return 0;
		}
		for (int j = 0; j < VERTEX_OF_Y; j++){
			NumberOfEdge = 0;
			for (int i = 0; i < VERTEX_OF_X; i++){
				if (Match[i][j] == 1)
					NumberOfEdge++;
			}
			if (NumberOfEdge != 1)
				return 0;
		}
		return 1;
	}
	else
		return 0;
}

void GetFeasibleVertexLabeling(){
	int MaximumWeightWeight;
	for (int i = 0; i < VERTEX_OF_X; i++){
		MaximumWeightWeight = Weight[i][0];
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (Weight[i][j] > MaximumWeightWeight){
				MaximumWeightWeight = Weight[i][j];
			}
		}
		LabelX[i] = MaximumWeightWeight;
	}
	for (int j = 0; j < VERTEX_OF_Y; j++){
		LabelY[j] = 0;
	}
}

void DetermineEqualitySubgraph(){
	for (int i = 0; i < VERTEX_OF_X; i++){
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (LabelX[i] + LabelY[j] == Weight[i][j]){
				Edge[i][j] = 1;
			}
			else{
				Edge[i][j] = 0;			
			}
		}
	}
}

int GetNumberOfWeight(){
	int NumberOfWeight = 0;
	for (int i = 0; i < VERTEX_OF_X; i++){
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (Weight[i][j] >= MIN_WEIGHT && Weight[i][j] <= MAX_WEIGHT){
				NumberOfWeight++;
			}
		}
	}
	return NumberOfWeight;
}

int GetNumberOfEdge(){
	int NumberOfEdge = 0;
	for (int i = 0; i < VERTEX_OF_X; i++){
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (Edge[i][j] == 1){
				NumberOfEdge++;
			}
		}
	}
	return NumberOfEdge;
}

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

void GenerateInitialMatch(){
	for (int i = 0; i < VERTEX_OF_X; i++){
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (Edge[i][j] == 1 && Match[i][j] == 0){
				int hasVertexJGotWeights = 0;
				for (int k = 0; k < i; k++){
					if (Match[k][j] == 1){
						hasVertexJGotWeights = 1;
						break;
					}
				}
				if (hasVertexJGotWeights == 0){
					Match[i][j] = 1;
					break;	// 这里使用 return 替换 break 可使初始化匹配仅包含 1 条边。（不推荐）
				}
			}
		}	
	}
}

void GenerateWeight(){
	for (int i = 0; i < VERTEX_OF_X; i++)
		for (int j = 0; j < VERTEX_OF_Y; j++)
			Weight[i][j] = rand() % (MAX_WEIGHT - MIN_WEIGHT + 1) + MIN_WEIGHT;
}

void DisplayWeight(){
	int PosX, PosY, i, j;
	sprintf(str, "二分图 G 中的共有 %d 条有权边。", GetNumberOfWeight());
	TextOut(memdc, 50, 25, str, strlen(str)); /* output string */
	InvalidateRect(hwnd, NULL, 1); /* paint the screen */
	for (i = 0; i < VERTEX_OF_X; i++){
		PosX = SCREEN_WIDTH / (VERTEX_OF_X + 1) * (i + 1);
		PosY = 0 + UP_MARGIN;
		xPosX[i] = PosX;
		xPosY[i] = PosY;
		SetPixel(memdc, PosX, PosY, RGB(255, 0, 0));
		sprintf(str, "%d", i);
		TextOut(memdc, PosX, PosY - 15, str, strlen(str));
		InvalidateRect(hwnd, NULL, 1);
	}
	for (j = 0; j < VERTEX_OF_Y; j++){
		PosX = SCREEN_WIDTH / (VERTEX_OF_Y + 1) * (j + 1);
		PosY = SCREEN_HEIGHT - DOWN_MARGIN;
		yPosX[j] = PosX;
		yPosY[j] = PosY;
		SetPixel(memdc, PosX, PosY, RGB(255, 0, 0));
		sprintf(str, "%d", j);
		TextOut(memdc, PosX, PosY, str, strlen(str));
		InvalidateRect(hwnd, NULL, 1);
	}
	SelectObject(memdc, hYellowpen);
	for (i = 0; i < VERTEX_OF_X; i++){
		for (j = 0; j < VERTEX_OF_Y; j++){
			if (Weight[i][j] >= MIN_WEIGHT && Weight[i][j] <= MAX_WEIGHT){
				MoveToEx(memdc, xPosX[i], xPosY[i], NULL);
				LineTo(memdc, yPosX[j], yPosY[j]);
			}
		}
	}
	InvalidateRect(hwnd, NULL, 1);
}

void DisplayEdge(){
	cout << "等同子图 GL 中的无权边集" << endl;
	cout << "Edge（大小为 " << GetNumberOfEdge() << "）如下所示:" << endl << '*';
	for (int j = 0; j < VERTEX_OF_Y; j++)
		cout << '\t' << j;
	cout << endl;
	for (int i = 0; i < VERTEX_OF_X; i++){
		cout << i << '\t';
		for (int j = 0; j < VERTEX_OF_Y; j++)
			cout << Edge[i][j] << "\t";
		cout << endl;
	}
}

void InitWeight(){
	for (int i = 0; i < VERTEX_OF_X; i++)
		for (int j = 0; j < VERTEX_OF_Y; j++)
			Weight[i][j] = 0;
}

void InitEdge(){
	for (int i = 0; i < VERTEX_OF_X; i++)
		for (int j = 0; j < VERTEX_OF_Y; j++)
			Edge[i][j] = 0;
}

void DisplayS(){
	cout << "S（大小为 " << SizeOfS << " ）如下所示:" << endl;
	for (int i = 0; i < VERTEX_OF_X; i++)
		cout << S[i] << "\t";
	cout << endl;
}

void InitS(){
	SizeOfS = 0;
	for (int i = 0; i < VERTEX_OF_X; i++)
		S[i] = -1;
}

void DisplayJS(){
	cout << "JS（大小为 " << SizeOfJS << " ）如下所示:" << endl;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		cout << JS[j] << "\t";
	cout << endl;
}

void InitJS(){
	SizeOfJS = 0;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		JS[j] = -1;
}

void DisplayT(){
	cout << "T（大小为 " << SizeOfT << " ）如下所示:" << endl;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		cout << T[j] << "\t";
	cout << endl;
}

void InitT(){
	SizeOfT = 0;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		T[j] = -1;
}

void DisplayTC(){
	cout << "TC（大小为 " << SizeOfTC << " ）如下所示:" << endl;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		cout << TC[j] << "\t";
	cout << endl;
}

void InitTC(){
	SizeOfTC = 0;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		TC[j] = -1;
}

void DisplayLabelX(){
	cout << "LabelX 如下所示:" << endl;
	for (int i = 0; i < VERTEX_OF_X; i++)
		cout << LabelX[i] << "\t";
	cout << endl;
}

void InitLabelX(){
	for (int i = 0; i < VERTEX_OF_X; i++)
		LabelX[i] = -1;
}

void DisplayLabelY(){
	cout << "LabelY 如下所示:" << endl;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		cout << LabelY[j] << "\t";
	cout << endl;
}

void InitLabelY(){
	for (int j = 0; j < VERTEX_OF_Y; j++)
		LabelY[j] = -1;
}


void DisplayMatch(){
	sprintf(str, "二分图 G 中的最佳匹配包含 %d 条边。", GetSizeOfMatch());
	TextOut(memdc, 50, 50, str, strlen(str)); /* output string */
	sprintf(str, "其边权之和为 %d。", GetSumOfWeight());
	TextOut(memdc, 50, 75, str, strlen(str)); /* output string */
	InvalidateRect(hwnd, NULL, 1); /* paint the screen */
	SelectObject(memdc, hRedpen);
	for (int i = 0; i < VERTEX_OF_X; i++){
		for (int j = 0; j < VERTEX_OF_Y; j++){
			if (Match[i][j] == 1){
				MoveToEx(memdc, xPosX[i], xPosY[i], NULL);
				LineTo(memdc, yPosX[j], yPosY[j]);
			}
		}
	}
	InvalidateRect(hwnd, NULL, 1);
}

void InitMatch(){
	for (int i = 0; i < VERTEX_OF_X; i++)
		for (int j = 0; j < VERTEX_OF_Y; j++)
			Match[i][j] = 0;
}

void DisplayMarkX(){
	cout << "MarkX 如下所示:" << endl;
	for (int i = 0; i < VERTEX_OF_X; i++)
		cout << MarkX[i] << "\t";
	cout << endl;
}

void InitMarkX(){
	for (int i = 0; i < VERTEX_OF_X; i++)
		MarkX[i] = -2;
}

void DisplayMarkY(){
	cout << "MarkY 如下所示:" << endl;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		cout << MarkY[j] << "\t";
	cout << endl;
}

void InitMarkY(){
	for (int j = 0; j < VERTEX_OF_Y; j++)
		MarkY[j] = -2;
}

void DisplayScanX(){
	cout << "ScanX 如下所示:" << endl;
	for (int i = 0; i < VERTEX_OF_X; i++)
		cout << ScanX[i] << "\t";
	cout << endl;
}

void InitScanX(){
	for (int i = 0; i < VERTEX_OF_X; i++)
		ScanX[i] = 0;
}

void DisplayScanY(){
	cout << "ScanY 如下所示:" << endl;
	for (int j = 0; j < VERTEX_OF_Y; j++)
		cout << ScanY[j] << "\t";
	cout << endl;
}

void InitScanY(){
	for (int j = 0; j < VERTEX_OF_Y; j++)
		ScanY[j] = 0;
}