Matching in a general graph

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
User avatar
ReynaldoGil
Posts: 38
Joined: 6 years ago
Location: Santiago de Cuba
Gender: None specified

Matching in a general graph

Post by ReynaldoGil » 6 years ago

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...



User avatar
ReynaldoGil
Posts: 38
Joined: 6 years ago
Location: Santiago de Cuba
Gender: None specified

Re: Matching in a general graph

Post by ReynaldoGil » 6 years ago

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;
}

User avatar
xshaka
Posts: 10
Joined: 6 years ago
Gender: None specified

Re: Matching in a general graph

Post by xshaka » 6 years ago

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
Posts: 1
Joined: 5 years ago
Gender: None specified

Re: Matching in a general graph

Post by whodunit » 5 years ago

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?

Post Reply

Return to “Algorithms”