[Boost-users] [Graph] Maximum Cardinality Matching: weighted?

From: Jean-Francois Bastien (jfbastien_at_[hidden])
Date: 2007-07-12 14:48:07

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?

Sincerely,

JF