Matching in a general graph

[ReynaldoGil]

Does anybody know about an efficient implementation of an algorithm for solving this problem? I mean an implementation short enough to be written during a contest...

[ReynaldoGil]

Thanks mukel, I've been looking for it a long time, I'll let you know if I translate it, anyway some days ago I found this one, but I don't know wether it works or not

Code: Select all

#include <iostream>
#include <cstring>
using namespace std;

const int nMax = 250;
const bool black = false;
const bool red = true;

int n;
int arSize;
int nUnUsed;

bool a[nMax][nMax];
bool color[nMax][nMax];
bool viewed[nMax][nMax];
bool unUsed[nMax];
bool curViewed[nMax];
int vertex[nMax];
int ar[nMax];
int nAdj[nMax];
int Adj[nMax][nMax];


void init()
{
	for(int i = 0; i < n; i++)
		unUsed[i] = true;
}

int findNextFree(int findFrom)
{
	int i = findFrom;
	while (i < n && !unUsed[i]) i++;
	if (i == n) return -1;
	else return i;
}


void initAr()
{
	nUnUsed = 0;
	memset(curViewed, 0, sizeof curViewed);
	memset(viewed, 0, sizeof viewed);
}

bool initAllStop;
bool initNext(int index, int from, bool addnew)
{
	int parent = vertex[index - 1];
	int i = from;
	while (i <= nAdj[parent] - 1 &&
		   (
			!unUsed[Adj[parent][i]] ||
			viewed[parent][Adj[parent][i]] ||
			curViewed[Adj[parent][i]] ||
			!(
                index + 1 == 1 ||
			   (index + 1 == 2 && color[Adj[parent][i]][parent] == black) ||
			   (index + 1 > 2 && color[Adj[parent][i]][parent] != color[parent][vertex[index - 2]])
			)
		  )
        )
		i++;
	if (i > nAdj[parent] - 1)
	{
		i = from;
		while ((i <= nAdj[parent] - 1) &&
			   (
				(viewed[parent][Adj[parent][i]]) ||
				(curViewed[Adj[parent][i]]) ||
				(!((index + 1 == 1) ||
				   ((index + 1 == 2) && (color[Adj[parent][i]][parent] == black)) ||
				   ((index + 1 > 2) && (color[Adj[parent][i]][parent] != color[parent][vertex[index - 2]]))
				))
			   ))
			i++;
	}
	else initAllStop = true;
	if (i <= nAdj[parent] - 1)
	{
		if (!(addnew))
		{
			if (unUsed[vertex[index]])
				nUnUsed--;
			curViewed[vertex[index]] = false;
		}
		viewed[parent][Adj[parent][i]] = true;
		vertex[index] = Adj[parent][i];
		curViewed[Adj[parent][i]] = true;
		if (unUsed[Adj[parent][i]])
			nUnUsed++;
		ar[index] = i;
	}
	return (i <= nAdj[parent] - 1);
}

void initAll()
{
	bool cont = true;
	initAllStop = false;
	int i = arSize  - 1 + 1;
	while (cont && !initAllStop)
	{
		cont = initNext(i, 0, true);
		i++;
		if (cont) arSize++;
	}
}

bool doStep()
{
	bool cont = true;
	while ((cont) && (arSize > 0))
	{
		bool res = initNext(arSize  - 1, ar[arSize  - 1] + 1, false);
		if (res)
		{
			initAll();
			cont = false;
		}
		else
		{
			curViewed[vertex[arSize  - 1]] = false;
			if ((unUsed[vertex[arSize  - 1]]) && (arSize > 1))
				nUnUsed--;
			arSize--;
		}
	}
	return (arSize > 0);
}

void writeAr()
{
	for (int i = 0; i < arSize; i++)
	{
		cout << vertex[i];
		if (i != arSize - 1)
			cout << " ";
	}
	cout << endl;
}

bool findString()
{
	int findFrom = 0;
	bool fin  = false;
	bool noFree = false;
	while (!fin && !noFree)
	{
		int start = findNextFree(findFrom);
		findFrom = start + 1;
		noFree = (start == -1);
		if (!noFree && nAdj[start] > 0)
		{
			initAr();
			arSize = 1;
			vertex[arSize - 1] = start;
			ar[arSize - 1] = -1;
			curViewed[start] = true;
			initAll();
			bool cont = true;
			fin = arSize > 0 && nUnUsed > 0;
			while (cont && !fin)
			{
				cont = doStep();
				fin = arSize > 0 && nUnUsed > 0;
			}
		}
	}
	if (!noFree)
	{
		int end = arSize - 1;
		while ((end > 0) && (color[vertex[end]][vertex[end - 1]] != black))
			end--;
		bool fin2 = false;
		int i = 0;
		while (i <= end && !fin2)
		{
			unUsed[vertex[i]] = false;
			if (i > 0)
			{
			    if (i % 2 == 1)
				{
					color[vertex[i]][vertex[i - 1]] = red;
					color[vertex[i - 1]][vertex[i]] = red;
				}
				else
				{
					color[vertex[i]][vertex[i - 1]] = black;
					color[vertex[i - 1]][vertex[i]] = black;
				}
			}
			i++;
		}
	}
	return (!(noFree));
}

void writeList()
{
	int cnt = 0;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (color[i][j] == red)
				cnt += 2;
	cout << cnt << endl;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (color[i][j] == red)
				cout << i << " " << j  << endl;
}

void solve()
{
	init();
	bool chk = true;
	while (chk)
		chk = findString();
	writeList();
}

void clearA()
{
	for (int i = 0; i < n; i++)
	{
		nAdj[i] = 0;
		for (int j = 0; j < n; j++)
			a[i][j] = false;
	}
}

void addCon(int p1, int p2)
{
	if (!a[p1][p2])
	{
		nAdj[p1]++;
		Adj[p1][nAdj[p1] - 1] = p2;
		nAdj[p2]++;
		Adj[p2][nAdj[p2] - 1] = p1;
		a[p1][p2] = true;
		a[p2][p1] = true;
	}
}

void initData()
{
	cin >> n;
	n++;
	clearA();
	int p1, p2;
	while (!(cin.eof()))
	{
		cin >> p1 >> p2;
		addCon(p1, p2);
	}
/*
	n = 222;
	clearA();
	for (int i = 0; i < n * n; i++)
		addCon(rand() % n, rand() % n);
*/
}

int main()
{
	initData();
	solve();
	return 0;
}

[xshaka]

Actually, there is a known efficient algorithm for this problem: Edmonds algorithm (Edmonds not Edmonds-Karp, since that last one is for max flow). The idea is to build an arbitrary matching and then the algorithm improves it to make it maximum. Here you have my own implementation.

Code: Select all

struct edge {
	int v, nx;
};
const int MAXN = 1000, MAXE = 2000;
edge graph[MAXE];
int last[MAXN], match[MAXN], px[MAXN], base[MAXN], N, M, edges;
bool used[MAXN], blossom[MAXN], lused[MAXN];
inline void add_edge(int u, int v) {
	graph[edges] = (edge) {v, last[u]};
	last[u] = edges++;
	graph[edges] = (edge) {u, last[v]};
	last[v] = edges++;
}
void mark_path(int v, int b, int children) {
	while (base[v] != b) {
		blossom[base[v]] = blossom[base[match[v]]] = true;
		px[v] = children;
		children = match[v];
		v = px[match[v]];
	}
}
int lca(int a, int b) {
	memset(lused, 0, N);
	while (1) {
		lused[a = base[a]] = true;
		if (match[a] == -1)
			break;
		a = px[match[a]];
	}
	while (1) {
		b = base[b];
		if (lused[b])
			return b;
		b = px[match[b]];
	}
}
int find_path(int root) {
	memset(used, 0, N);
	memset(px, -1, sizeof(int) * N);
	for (int i = 0; i < N; ++i)
		base[i] = i;
	used[root] = true;
	queue<int> q;
	q.push(root);
	register int v, e, to, i;
	while (!q.empty()) {
		v = q.front(); q.pop();
		for (e = last[v]; e >= 0; e = graph[e].nx) {
			to = graph[e].v;
			if (base[v] == base[to] || match[v] == to)
				continue;
			if (to == root || (match[to] != -1 && px[match[to]] != -1)) {
				int curbase = lca(v, to);
				memset(blossom, 0, N);
				mark_path(v, curbase, to);
				mark_path(to, curbase, v);
				for (i = 0; i < N; ++i)
					if (blossom[base[i]]) {
						base[i] = curbase;
						if (!used[i]) {
							used[i] = true;
							q.push(i);
						}
					}
			} else if (px[to] == -1) {
				px[to] = v;
				if (match[to] == -1)
					return to;
				to = match[to];
				used[to] = true;
				q.push(to);
			}
		}
	}
	return -1;
}
void build_pre_matching() {
	register int u, e, v;
	for (u = 0; u < N; ++u)
		if (match[u] == -1)
			for (e = last[u]; e >= 0; e = graph[e].nx) {
				v = graph[e].v;
				if (match[v] == -1) {
					match[u] = v;
					match[v] = u;
					break;
				}
			}
}
void edmonds() {
	memset(match, 0xff, sizeof(int) * N);
	build_pre_matching();
	register int i, v, pv, ppv;
	for (i = 0; i < N; ++i)
		if (match[i] == -1) {
			v = find_path(i);
			while (v != -1) {
				pv = px[v], ppv = match[pv];
				match[v] = pv, match[pv] = v;
				v = ppv;
			}
		}
}

[whodunit]

Hi xshaka
Can you please explain me this code? Where do I give my graph? Do I need to make main class for taking input? And what are all the methods that I call?