Finding maximum weighted graph matchings

[Laurens Van Houtven]

Hi!

I'm trying to find a maximum weighted graph matching for a given graph. Searching for this has proven difficult; search engines like to give me results that involve a lot of pattern matching and not a lot of graph matching.

I know algorithms for this exist; specifically variants of Edmonds' Blossom algorithm (which finds maximal matchings on arbitrary graphs, but says nothing about weights). I've found Loom, a Clojure graph library, which doesn't appear to implement this algorithm. I've found JGraphT, which only implements the unweighted version.

thanks!
lvh

[François Rey]

I recently searched for other graph algorithms and did not find much
more than what you probably know: JUNG, JGraphT, Loom, Tinkerpop.
So my guess is that you'll be very lucky to find an implementation in
java, let alone in clojure.
Be prepared to write your own.

[Paul deGrandis]

I've written general versions of Blossom and Blossom V in the past, and every so often a similar question comes up on this mailing list.

I'd personally love to see both algorithms contributed to Loom if OP is up for the task.

Paul

[Laurens Van Houtven]

Hi,

On Tuesday, March 18, 2014 3:02:01 PM UTC+1, Paul deGrandis wrote:

I've written general versions of Blossom and Blossom V in the past, and every so often a similar question comes up on this mailing list.

I'm guessing that wasn't in clojure? :-(

Do you happen to know what happens when you throw Blossom V at a graph that doesn't have a perfect matching? E.g. for my use case, hotel room pairing, there's a 1/2 chance the graph ends up having an odd number of nodes... IIUC it won't terminate, but you can detect that it won't, so then you can just give the best-effort solution anyway?
 

I'd personally love to see both algorithms contributed to Loom if OP is up for the task.

I'm afraid I've got a convex optimization problem in terms of financial aid grant sizes to solve first before I can start writing that code :-)

cheers
lvh

[Jason Felice]

I thought matching was a dual of max flow, so weighted matching was a dual of min cost max flow (relabling edges with infinity minus cost).

The simplest algorithm to implement would be Ford-Fulkerson with Floyd-Warshall to find augmenting paths.  The most efficient would be Dinic's, I think?

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Andy Fingerhut]

That is true for maximum matching (weighted or not) in bipartite graphs.

Max (weighted) flow methods do not work for matchings in general graphs.

Andy