On Nov 30, 2007 4:46 AM, Alessio Dore
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