Re: [Boost-users] [BGL] All Possible Matchings (Hossein Haeri)

From: Grégoire Dooms (dooms_at_[hidden])
Date: 2006-07-04 03:45:54

boost-users-request_at_[hidden] wrote:

Message: 9
Date: Mon, 3 Jul 2006 16:46:55 +0100 (BST)
From: Hossein Haeri <powerprogman_at_[hidden]>
Subject: [Boost-users] [BGL] All Possible Matchings
To: boost-users_at_[hidden]
Message-ID: <20060703154655.35182.qmail_at_[hidden]>
Content-Type: text/plain; charset=iso-8859-1

        
> Dear all,
>
> I have a bipartite graph, and want to generate all its
> possible matchings. Any suggestions?
>
You should have a look at Constraint Programming and the Alldifferent constraint.
In CP, the task of filtering for a constraint over some integer variables amounts to partitioning, for each of its variables, the potential values into three categories: the values participating in all solutions (obviously at most one per variable), the values participating in some solutions, and the values participating in no solutions.

In the case of the Alldifferent constraint, it can be reinterpreted in graph matching terms:
Build a bipartite variable-value graph. A solution to the Alldifferent constraint is a maximum matching covering all variables in this graph.  Hence filtering can be done by identifying edges which belong to some/all/no max matching.

In a nutshell, the following property of matchings is used [Peterson] [Berge] :
M1 (+) M2 = P 
M1 (+) P = M2  
where P is an alternating path
(for instance, look at the LEDA book for a good exposition of this property and matching algorithms).
 
This property is used in matching algorithms with P an augmenting alternating path. If you consider "maintaining" paths (eg. non-augmenting and non-decreasing -- even length, starting at a free node and ending at a covered node, or an alternating cycle) and apply them on a max matching you get another max matching.

Here are a few references:

Ref. to the original paper : http://citeseer.ist.psu.edu/context/210815/0
A survey on this subject: http://citeseer.ist.psu.edu/579391.html (or http://www.cs.cornell.edu/~vanhoeve/papers/alldiff.pdf for a more recent/in progress version)
Slides by JC Regin: http://www.constraint-programming.com/people/regin/papers/GraphAndCP.pdf
Finally, an open-source implementation:
http://www.gecode.org/gecode-doc-latest/distinct_2dom_8icc-source.html

Hope this helps,
--
Grégoire Dooms.