Re: [Boost-users] BGL : maximum weighted matching

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-12-01 14:09:11

On Nov 30, 2007 4:46 AM, Alessio Dore <dore_at_[hidden]> wrote:
> Dear all,
>
> I am implementing an algorithm for which I would need to compute the
> maximum weighted matching of a bipartite graphs. I have seen that LEDA
> libraries has this sort of functions but their license is restrictive.
> BGL allows maximum cardinality matching but, if I understood well, it
> works for non-weighted graphs. In a previous message on this list it was
> mentioned that this functionality could have been added but I didn't
> find it. Is it available? Does anyone of you know if there are other
> libraries to perform it?

Hi Alessio,

You're correct - the BGL has an implementation of an algorithm to find
a maximum matching in an unweighted graph, but doesn't yet have a
maximum weighted matching algorithm, even for bipartite graphs. A
recent message on on the boost development mailing list had a link to
a C implementation of maximum weighted matching for graphs (not just
bipartite):

http://lists.boost.org/Archives/boost/2007/10/129535.php

This is the only such free implementation I've seen.

Regards,
Aaron