Calculates the graph matching with the Konig matching theorem

Dénes Kőnig matching.cpp

/*
 * Dénes Kőnig matching.cpp
 * This file is part of Dénes Kőnig matching
 *
 * Copyright (C) 2014 - Giacomo Bergami
 *
 * Dénes Kőnig matching is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Dénes Kőnig matching is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Dénes Kőnig matching; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, 
 * Boston, MA  02110-1301  USA
 */
 
 

#include <utility>
#include <array>
#include <list>
#include <map>
#include <iostream>
#include <algorithm>

template <class T, size_t ROW, size_t COL>
using Matrix = std::array<std::array<T, COL>, ROW>;

std::list<int> L, R;

Matrix<bool,11,11> graph; // 10 x 10 ~ Graph Definition 
std::array<int,11> l_label; // dim: 10 ~ L labelled vertices
std::array<int,11> r_label; // dim: 10 ~ R labelled vertices
std::list<std::pair<int,int>>  Matching; // New incoming matches
//Assumption. We first enumerate vertices from U and then from V
int first_v_num = -1;

//initializes the graph
void memset_zero() {
	for (int i=1; i<=10; i++) {
		for (int j=1; j<=10; j++)
			graph[i][j] = 0;     //no edge
	}
}

//inserting in the match
void setmatch(std::list<std::pair<int,int>>* obj, int i, int j) {
	if (i<=j)
		obj->push_back(std::make_pair(i,j));
	else
		obj->push_back(std::make_pair(j,i));
}

//Computes (M\P) \/ (P\M)
std::list<std::pair<int,int>> setmatch(std::list<std::pair<int,int>>* M, std::list<std::pair<int,int>>* P) {
	std::list<std::pair<int,int>> result;
	//not very efficient implementation. Harsh, but fair
	for (std::pair<int,int> l : *M) {
		int lx, ly, rx, ry;
		if (l.first<l.second) {
			lx = l.first;
			ly = l.second;
		} else {
			lx = l.second;
			ly = l.first;
		}
		bool got = false;
		for (std::pair<int,int> r : *P) {
			if (r.first<r.second) {
				rx = r.first;
				ry = r.second;
			} else {
				rx = r.second;
				ry = r.first;
			}
			if ((rx == lx) && (ry == ly)) {
				got = true;
				break;
			}
		}
		if (!got) 
			result.push_back(std::make_pair(lx,ly));
	}
	//
	for (std::pair<int,int> l : *P) {
		int lx, ly, rx, ry;
		if (l.first<l.second) {
			lx = l.first;
			ly = l.second;
		} else {
			lx = l.second;
			ly = l.first;
		}
		bool got = false;
		for (std::pair<int,int> r : *M) {
			if (r.first<r.second) {
				rx = r.first;
				ry = r.second;
			} else {
				rx = r.second;
				ry = r.first;
			}
			if ((rx == lx) && (ry == ly)) {
				got = true;
				break;
			}
		}
		if (!got) 
			result.push_back(std::make_pair(lx,ly));
	}
	return result;
}

//Updates L
void addL(int v) {
	if (std::find(L.begin(),L.end(),v)==L.end())
		L.push_back(v);
}
 
//Re-cleans the data structures
void init() {
	//Clearing the labelled ones
	R.clear();
	//Clearing the labels
	for (int i=1; i<=10; i++) {
		l_label[i] = r_label[i] = 0; //no label
	}
	std::array<bool,11> a;
	for (int j=1; j<=10; j++)
		a[j] = true;
	for (std::pair<int,int> p : Matching) {
		a[p.first] = false;
	}
	for (int j=1; j<first_v_num; j++)
		if (a[j]) 
			addL(j);
}


//Updates R
void addR(int v) {
	if (std::find(R.begin(),R.end(),v)==R.end())
		R.push_back(v);
}

//Left branch
void scan_leftvertex(int v) {
	L.remove(v);
	std::cout << "scan_leftvertex(" << v << ")" << std::endl;
	for (int j=1; j<=10; j++)
		if (graph[v][j] == 1) {
			if (l_label[j]==0) { //j is unlabeled 
				//std::cout << "ENTER" << std::endl;
				l_label[j] = v;
				addR(j);
			}
		}
	/*std::cout << "++++ R={";
	for (int x : R) 
		std::cout << x << ",";
	std::cout << "}" << std::endl;*/
}

//Required print
void print_state() {
	std::cout << "L={";
	for (int x : L) 
		std::cout << x << ",";
	std::cout << "}  ";
	std::cout << "R={";
	for (int x : R) 
		std::cout << x << ",";
	std::cout << "}" << std::endl;
}

//Right branch
void scan_rightvertex(int v) {
	R.remove(v);
	std::cout << "scan_rightvertex(" << v << ")" << std::endl;
	for (std::pair<int,int> p : Matching) //for each edge, find a matching edge
		if (v==p.second) { //is a matching edge
			r_label[p.first] = v;
			addL(p.first);
			return; //found: quit procedure
		} 
	//if there is no matching edge
	std::list<std::pair<int,int>> P;
	int counter = 0; 
	int old = -1;
	std::cout << "P={";
	while (v!=0) {
		if (old!=-1)
			P.push_back(std::make_pair(old,v));
		old = v;
		std::cout << v << ",";
		if (!counter) 
			v = l_label[v];
		else
			v = r_label[v];
		counter = (counter+1)%2;
		//
	}
	std::cout << "}" << std::endl;
	std::list<std::pair<int,int>> tmpM = setmatch(&Matching,&P);
	Matching = tmpM;
	init(); //re-cleans all
}

//Chose the desired vertex
int choose() {
	if (R.empty()) {
		return L.front();
	} else for (int r : R) {
		bool has = false;
		for (std::pair<int,int> p : Matching) {
			if (r==p.second) {
				has = true;
				break;
			}
		}
		if (!has) 
			return r;
	}
	return R.front();
}

int main(void) {
 
	memset_zero();
	
	//Initializing the graph
	graph[1][6] = 1;
	
	graph[2][6] = 1;
	graph[2][7] = 1;
	graph[2][9] = 1;
	
	graph[3][6] = 1;
	graph[3][8] = 1;
	graph[3][9] = 1;
	
	graph[4][7] = 1;
	graph[4][8] = 1;
	graph[4][9] = 1;
	graph[4][10] = 1;
	
	graph[5][7] = 1;
	
	//Setting the part where V stars (distinguish U)
	first_v_num = 6;
	
	//Initialize matching
	
	init();//TODO
	
	std::cout << L.empty() << " " << R.empty() << std::endl;
	
	while (((!L.empty()) || (!R.empty()))) {
		print_state();
		std::cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << std::endl;
		int c = choose();//TODO
		if (std::find(L.begin(),L.end(),c) != L.end()) // if L contains c
			scan_leftvertex(c);
		else
			scan_rightvertex(c);
	}
	print_state();

}