search

sbromberger / LightGraphs.jl

An optimized graphs package for the Julia programming language
Other
672 stars 185 forks source link

matching algorithm #194

Closed CarloLucibello closed 9 years ago

CarloLucibello commented 9 years ago

A matching algorithm would be a great addition to LG, but its implementation would be long and difficult, in fact very few graph libraries support it (e.g. Lemon has some fast and general implementations).

In the case of bipartite graphs though the maximum weight perfect matching can be stated as a linear programming problem whose solutions happen to be integers. Therefore I could provide a solver for this particular case if any of you think it is appriopriate. This would also mean adding a linear solver library to REQUIRE.

Bye, Carlo

PS I think that Lemon licence would allow for a julia port, provided we obtain permission from the authors. Translating thousands of lines of C++ code would be a huge task per se though

CarloLucibello commented 9 years ago

unless @pranavtbhat wants to take a try at implementing another Edmonds's algorithm :)

sbromberger commented 9 years ago

I'm ok with this proposal. We can also include it as a conditional dependency (much like we do with GraphMatrices). Thanks!

pranavtbhat commented 9 years ago

Haha. The algorithm seems to be incredibly complicated! Could give it a shot in my holidays.

jpfairbanks commented 9 years ago

We could in the short term include a greedy maximal weighted matching right?