[Lemon-devel] Feature Request - Matching Algorithm

[Florian Schmidt]

Dear lemon developers,

lemon is a great library and I use it a lot in my daily work!
I have a feature request concerning the matching algorithms.

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().

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 am looking forward to your answer.

Regards,
Florian

-- 
Karlsruhe Institute of Technology (KIT)
Institute of Photogrammetry and Remote Sensing (IPF)

Dipl.-Ing. Florian Schmidt
Research Associate

Englerstrasse 7
Buildung 20.40
76131 Karlsruhe, Germany

Phone: +49 721 608-45028
Fax: +49 721 608-48450
Email: florian.schmidt at kit.edu
Web: http://www.ipf.kit.edu/

KIT – University of the State of Baden-Wuerttemberg and National 
Research Center of the Helmholtz Association