Matching

[pnevyk]

Hi,

I implemented an algorithm for maximum matching. It was also requested in #296.

The implementation uses Gabow's algorithm, which has O(|V|^3) time complexity. The state-of-the-art is O(sqrt(|V|) |E|) (a classical example is Micali-Vazirani). Wikipedia has article about an algorithm which is said to have O(|V|^2 |E|) time.

The issue with the state-of-the-art algorithms is that they are very complex. The algorithm implemented in this PR is much simpler to implement and I consider it a good start. A nice thing about it is that it uses labeling techniques to encode structure and does not require any complex data structures for blossom shrinking and expansion. The ultimate goal (not for this PR) is to implement a O(sqrt(|V|) |E|) algorithm - a good candidate might be this work, which seems to be quite accessible, but I haven't read it yet.

Looking forward to your thoughts and feedback.

[bluss]

Hi, at this moment the maintainers don't have so much time unfortunately, so there can be a lot of delay.

[pnevyk]

That's fine, take your time.

[ABorgna]

This is really clean. Thanks!
Can you rebase over master so the failing rustfmt test runs again ?

In addition to the comments, we might want to change the name of maximum_matching to gabow_maximum_matching or similar (as what happens with tarjan_scc and kosaraju_scc) so that future implementations using other algorithms can set different constraints without breaking the API.
@bluss do you have a preference on this?

[pnevyk]

Thanks! I will rebase.

Regarding the name change, here is my perspective. I am not sure whether this algorithm should be permanent in petgraph codebase. Its time complexity O(|V|^3) is significantly worse than the best I found O(sqrt(|V|) |E|). But I needed a maximum matching algorithm and chose Gabow for its simplicity as a least effort, and thought that others may benefit from it even though it's not state-of-the-art. I can imagine replacing the algorithm under the hoods in the future.

Nonetheless, thanks to its simplicity, this algorithm may be actually faster than very complicated state-of-the-art on some graphs. In that case, it would make sense to provide it through gabow_maximum_matching.

[bluss]

@pnevyk's rationale for a more specific name sounds good 🙂

[pnevyk]

There may be a little trouble however. This paper from 2017 advertises itself as "an accessible matching algorithm with time bound O(sqrt(|V|) |E|)" and by skimming the paper I can agree that it is, compared to what I saw in others. So I planned to give this a try. But the paper is written by Gabow as well.

But I am no expert on matching algorithms, I don't know which one should be included in petgraph.

[ABorgna]

Oh, right. We could check which algorithm are being used by other libraries too, but that one looks nice, simple, and asymptotically optimal.

For now, we can start merging this first implementation. Thanks for the work!