Are there any plans to implement the minimum weight perfect matching algorithm without using BlossomV?

[angus-kan]

Currently, the minimum weight perfect matching (MWPM) algorithm relies on BlossomV.jl, a wrapper around Kolmogorov's BlossomV software, which has a research-only, non-commercial license. I'm wondering if there are any plans to use an open-source version, such as a pure julia rewrite or a different implementation with a similar performance like the MWPM algorithm in LEMON (http://lemon.cs.elte.hu/pub/doc/latest-svn/index.html), with a much more permissive license? I realize that this issue has been raised in the past (see https://discourse.julialang.org/t/should-we-consider-bindeps-abandoned/23616 and https://github.com/mlewe/BlossomV.jl/pull/15), but I'm a new user and haven't found a follow-up on this issue. So, I figure it doesn't hurt to ask. Thanks a lot in advance!

[simonschoelly]

There once was a jsoc project for that, but it failed. I tried to look into it myself a while ago, but these days I don't find time to do it. But a few years ago, someone implemented that algorithm for gsoc in Java, so it should definitely be doable.

[angus-kan]

Thanks for the quick response! Due to the similarity between the MWPM algorithm in LEMON and Kolmogorov's BlossomV, i.e., both are written in C++ and have the same time complexity and similar performance (as far as I know), perhaps it might be a less time-consuming and involved option to wrap the LEMON MWPM algorithm (http://lemon.cs.elte.hu/pub/doc/latest-svn/a00388.html) instead of writing a Julia implementation from scratch.

[simonschoelly]

That seems to be a good idea, although i have not heard of MWPM so far. It looks as if Lemon is under the boost software license, https://github.com/tpet/lemon/blob/master/LICENSE, and so far it is not clear to me, how well that plays with other open source licenses, but it seems to be fairly permissible. The best thing to do, is probably to wrap this in its own package, and then we can use that package as a dependency here.

[angus-kan]

I believe MWPM is the generic name of the algorithm, and BlossomV is a specific implementation of the algorithm. If I understand you correctly, your suggestion is to follow how BlossomV is currently used in GraphsMatching.jl.

[angus-kan]

@simonschoelly I've been looking into the java implementation (https://github.com/Toptachamann/jgrapht/tree/blossom-alg/jgrapht-core/src/main/java/org/jgrapht/alg/matching/blossom/v5). It heavily relies on pairing heaps, which isn't part of DataStructures.jl. They don't sound straightforward to implement given that they rely on pointers instead of arrays for referencing nodes in a heap. From the little that I've read, unlike in OOP languages, it is not recommended to use julia's pointers for referencing. Do you know of any julia implementation of pairing heaps?

[etiennedeg]

I don't think the choice of the priority queue is the most important detail of the algorithm, we could use the standard Priority queue of DataStructures, then switch to a better one like PairingHeap when it will be implemented (and even better, allow the PriorityQueue to be passed as an argument).

There is no need for pointers, just references, just take a look at the jaiva implementation which by definition have no pointers. AFAIK, there is no implementation of a PairingQueue in Julia, but I may have overlooked it.

[angus-kan]

In Z Galil - ACM Computing Surveys (CSUR), 1986 "Efficient algorithms for finding maximum matching in graphs", it's discussed that the complexity of the blossom algorithm depends on the fact that priority queue operations take O(log n) (some are O(1)). You're right that in principle I can use standard priority queue or binary heap in DataStructures. However, one problem I see is that an efficient merge/meld operation for heap or pq is not supported in DataStructures. That in principle can be coded up, but that takes O(n) time for binary heap (I'm not familiar with the priority queue in DataStructures, so I can't speak about that), but it takes O(log n) time for pairing heap. This operation is needed in the Blossom algorithm; so a slow heap will slow the algorithm down.

It's good to know that pointers aren't needed! Unfortunately, the java implementation uses pairing heaps from the jheaps library, which I'm not familiar with. Too bad julia doesn't have that yet.

[etiennedeg]

Ah, there is a PR for a Fibonacci heap, but it seems to be stuck for the moment.

[angus-kan]

Seems like it hasn't been touched in two years :'(

[angus-kan]

Is there anyway we can revive that thread? Or we can use/optimize that code? (I'm a newcomer to github/ the open-source environment; so I'm not familiar with the usual practices.)

I think having a fibonacci heap would be a great start for a julia implementation of BlossomV! Although the java implementation went from using fibonacci heaps to pairing heaps because pairing heaps have a better runtime in practice, since fibonacci heaps often have larger constant overhead and memory footprint. And BlossomV heavily relies on heaps. But again, this is not a complaint; it won't be difficult to switch to a pairing heap once it's available.

I also found that an issue asking for a pairing heap to be included, and the author of that issue actually wrote a static persistent and a mutable version. Unfortunately, his issue received no replies.

[angus-kan]

On a related note, the current max weighted matching algorithm in this library is implemented directly via an LP or MIP solver, depending on whether the graph is bipartite or not. Actually, max weighted matching can be reduced to the problem of minimum weight perfect matching, which can be solved using the Blossom algorithm. The general case is currently solved with an MIP solver, which could take exponential time as stated in the comments of the current implementation, but can be solved efficiently using the Blossom algorithm. Similar, the bipartite case can be solved using a (less complicated) Blossom algorithm efficiently.

Anyway, I'm sure there's a lot on your plate regarding the development of the julia graph library/ecosystem, but I just want to point out areas where this package can be improved with help from the wider community. And thanks a lot for your contributions; I quite enjoy using the graph libraries!

[etiennedeg]

The bipartite case is the assignment problem, it is solved by the Hungarian algorithm (we have a pure julia implementation). For the general case, it could be nice to rely on the Blossom algorithm.