Optimal bipartite graph matching algorithm gem for Ruby.
Ruby
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
lib
test
.gitignore
README.md
Rakefile
graphmatch.gemspec

README.md

graphmatch

Optimal bipartite graph matching algorithm gem for Ruby. It uses the Ford-Fulkerson max-flow algorithm with a super-source and super-sink to maximally match graphs.

The augmentation paths are found with either breadth-first search or Bellman-Ford. BFS is faster for unweighted matching, while Bellman-Ford can be used for min-cost max-flow matching given the edge weights. Note: for weighted matching with Ford-Fulkerson, the edge weights must be integers otherwise the algorithm may not be able to determine a matching!

Further documentation can be found here: http://rubydoc.info/gems/graphmatch/

Example usage

Unweighted matching

left = ['a', 'b', 'c']
right = [1, 2, 3]
edges = {'a' => {2 => 0},
         'b' => {2 => 0, 3 => 0},
         'c' => {1 => 0, 3 => 0}}

Graphmatch.match(left, right, edges)
==> {'a' => 2, 'b' => 3, 'c' => 1}

Weighted matching

left = ['a', 'b', 'c']
right = [1, 2, 3]
edges = {'a' => {1 => 100, 2 => 10, 3 => 1},
         'b' => {1 => 10, 2 => 1, 3 => 100},
         'c' => {1 => 1, 2 => 100, 3 => 10}}

Graphmatch.match(left, right, edges)
==> {'a' => 3, 'b' => 2, 'c' => 1}