On 7/12/07, Jean-Francois Bastien wrote:

Hello,

I am just starting on using boost::graph and I would like to solve the following problem: I have a potentially unbalanced complete weighted bipartite graph and I would like to find the maximum weighted maximum cardinality matching for it.

The immediate candidate for this seems to be the checked_edmonds_maximum_cardinality_matching. I realize that my graph is bipartite and that Edmond's algorithm is for general graph, but the graph library doesn't seem to have an algorithm optimized for bipartite graphs (please correct me if I'm wrong on this).

My problem is this: in reading the documentation and the code I seem to understand that the implementation doesn't take into account the weight of the graphs. I'd like to know if it does take weights into account or not before I dive into learning the boost::graph library just to realize that it doesn't solve my problem.

If the implementation doesn't take weights into account then is there another algorithm (or combination thereof) that I've overlooked from the library which could solve my problem?

Hi Jean-Francois, Sorry, but the BGL currently doesn't have an implementation of weighted matching, even for bipartite graphs. Edmonds' algorithm works only on unweighted graphs. Regards, Aaron