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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-07-12 18:25:18

On 7/12/07, Jean-Francois Bastien <jfbastien_at_[hidden]> 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