matching algorithm

[CarloLucibello]

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]

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

[sbromberger]

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

[pranavtbhat]

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

[jpfairbanks]

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