Hungarian Algorithm with Mutual Pairs?

Question

I'm trying to use the following implementation of the Hungarian Algorithm: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm.

I would like the modify this algorithm so that I can pair a set with itself. That is to say, if "a" is assigned to "b," "b" is also assigned to "a." The only idea I've had is changing the following.

for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty)
    {
            yx[cy] = cx;  
            xy[cx] = cy;  
    }

To the following:

for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty)
    {
            yx[cy] = cx; yx[cx]=cy;
            xy[cx] = cy; xy[cy]=cx;
    }

So that the algorithm always checks paths where the pairings are mutual. However, I'm rather sure this is wrong - the code usually segfaults.

I tried fixing the problem by changing if (max_match == n) to a looser constraint, like if (max_match >= n-1), so that the algorithm is content with a sub-perfect matching. This works sometimes, and when it does, it creates some mutual pairs like I wanted, but some vertices are left unpaired. And there are still segmentation faults.

So, is there any way to fix this problem? Are there other more suitable algorithms for this?

Answer 1

I think what you want is a version of a maximum matching for a graph that is not bipartite. There is an algorithm described for this at http://en.wikipedia.org/wiki/Blossom_algorithm, and the very last paragraph talks about the weighted case. You want a minimum cost matching, but every maximum matching has the same number of edges, so if you negate the cost of each link, or subtract the costs from some very large constant, you turn minimum into maximum.

The general maximum problem is sufficiently constant that I think you will have trouble getting the Hungarian algorithm to do it, because if you could do it with the Hungarian algorithm people wouldn't find the general problem so complicated.