Implement Matching Algorithms

[milsen]

In GitLab by @ni-tro on Nov 18, 2020, 13:33

The OGDF lacks efficient algorithms for the usual matching problems:

• [ ] minimum/maximum weight perfect matching in bipartite/general graphs
• [x] maximum cardinality matching in bipartite (already done by https://git.tcs.uos.de/ogdf-devs/OGDF/-/commit/c9ce7f55e2a0eed2ae30f197b326b99057f74f3e) general graphs.

It could be useful to refer to a state-of-the-art implementation of Edmond's Blossom algorithm, such as V. Kolmogorov's "Blossom V" (article, source).

[milsen]

In GitLab by @ni-tro on Apr 12, 2021, 10:24

@joschie has layed the foundation in this branch: https://git.tcs.uos.de/ogdf-devs/OGDF/-/tree/jschierbaum-thesis-matchings

If we continue this branch, there is still some work to do:

• [ ] Write interface for the Maximum Weight Matching problem.
• [ ] Use the union find data structure according to Cook et al.
• [ ] Use efficient data structures throughout the algorithm (e.g. use an EdgeArray to mark edges that are currently in a matching).

If we decide to start from scratch, we should survey existing implementations first (e.g. "Blossom V" mentioned above).