[Lemon-devel] Feature Request - Matching Algorithm

[Alpár Jüttner]

Hi,

> I would like to find the n best solutions to a matching problem in a 
> bipartite graph.
> I have implemented Murty's algorithm 
> (http://www.jstor.org/stable/168595) based an the 
> MaxWeightedPerfectMatching class and the SubDigraph adaptor. Everything 
> works out fine so far.
> 
> Now, I would like to speed up the algorithm by using the three proposed 
> improvements of Miller (http://dx.doi.org/10.1109/7.599256). I have 
> already implemented proposals 2 and 3 by using the existing lemon tools. 
> Yet the first proposal cannot be realized without adding new features to 
> the library.
> 
> It would be great if I could init() a matching object on a subgraph and 
> disable an edge or node afterwards without have to call the full init() 
> method again before start().


Unfortunately init() does quite a complex task, and I don't exactly see
how a "warm reset" you propose should actually work.

The situation is however more complex and more promising at the same
time. Using MaxWeightedPerfectMatching for your problem is an overkill,
for it is actually an implementation of Edmond's algorithm for general
graphs. A bipartite matching algorithm can be easily faster by
magnitude.

We currently do not have bipartite matching algorithm in LEMON basically
because it is waiting for the finalization of the concept an and
implementation of bipartite graphs.

There is however an proposal for that, that is already quite usable, see
https://lemon.cs.elte.hu/trac/lemon/ticket/69 for it. I try to speed up
the finalization of this project.

We do already have a bipartite matching implementation of above, it has
not been made public yet.

If you are willing to play with these tools - with the strong disclaimer
that they are in an experimental status - we can put together a
repository containing both the bipartite graphs and the matching
algorithms for you.

Let me know if you are interested.
(I CC-d Balázs, the main developer of bipartite graphs and Előd, how
implemented the matching algorithms.)

> I would also like to copy an initialized matching object, disable 
> different sets of edges and nodes and solve these diffentent 
> configurations independently, maybe even in parallel.

I don't think that initialization is much slower than copying the
object. As far as the parallelization is concerned, the one and only
point where the core of lemon is not thread safe is the graph map
allocation.

For example, it means that you must run the init() methods of the
MaxWeightedPerfectMatching sequentially, but then the start() methods -
which actually contribute the most to the running time - can be executed
in parallel.


Regards,
Alpár