search

JuliaGraphs / LightGraphsMatching.jl

Matching algorithms for LightGraphs.jl
Other
13 stars 6 forks source link

Dependency-less matching algorithm? #6

Open dourouc05 opened 6 years ago

dourouc05 commented 6 years ago

I was trying to compute matchings with this package, I had a problem when installing the dependency BlossomV.jl (https://github.com/mlewe/BlossomV.jl/issues/12). Then, I saw that the other way to solve matchings is to use mathematical programming. However, what I expected from this package was rather an implementation of the Hungarian algorithm (provided by BlossomV.jl, but not available on most platforms). Would it be possible to consider adding a pure-Julia implementation, so that it is ensured to work on all platforms? (Either coding one for this package, or using something like https://github.com/Gnimuc/Hungarian.jl or https://github.com/FugroRoames/Munkres.jl.)

matbesancon commented 6 years ago

For the Hungarian algorithm, can you use a max-weight matching? This one does not depend on BlossomV but on JuMP & MathProg, the mathematical programming ecosystem. All you need is a MIP solver and JuMP installed (which is more build-friendly than BlossomV)

But you're right a pure Julia implementation would be great and overall, removing heavy dependencies. I'll try to replace JuMP with plain MathProgBase as was done in LightGraphsFlows.jl, the Hungarian algorithm is a special case of max-weight matching, not sure it would be easier/more efficient than an optimization approach

dourouc05 commented 6 years ago

Indeed: my current implementation already uses JuMP, but I was eager to compare to other algorithms in my use case (I have a very large number of quite small matchings to solve).

What would be your preferred way of implementing pure-Julia implementations within LightGraphsMatching.jl? I don't think it is a good idea to get rid of the MIP technique or of BlossomV (except if it is slower than a Julia solution), so I'd better not replace existing code for this. Maybe rename the current functions to explicit the method they are using, and have the current name choose the best algorithm available (BlossomV if possible, then MIP if JuMP is installed, otherwise pure Julia, or something like that)?

matbesancon commented 6 years ago

Yes this could be great. This is what has been done in other parts of the JuliaGraphs ecosystem, like in LightGraphsFlows.jl: flow algorithms can be plugged as parameters to the maxflow function. Once we have enough different implementations to differentiate, a similar interface can be built up with: maxmatch(g, algorithm) and maxmatch(g, algorithm, weights) or equivalent.

Feel free to take a look at the flow package and give a try at alternative solving methods ;)

dourouc05 commented 6 years ago

OK, I will make a few experiments and let you know about the result! Thank you for your answers!

Gnimuc commented 5 years ago

since the original code of BlossomV is released under a very strict license, we should drop it as suggested in https://github.com/JuliaGraphs/LightGraphsMatching.jl/pull/12#issuecomment-434500352 .