Finds maximum matchings in weighted bipartite graphs, using the Hungarian algorithm.
Add this line to your application's Gemfile:
gem 'bipartite_graph'
And then execute:
$ bundle
Or install it yourself as:
$ gem install bipartite_graph
graph = BipartiteGraph.new
graph.add_edge('x1', 'y1', 1)
graph.add_edge('x1', 'y2', 6)
graph.add_edge('x2', 'y2', 8)
graph.add_edge('x2', 'y3', 6)
graph.add_edge('x3', 'y1', 4)
graph.add_edge('x3', 'y3', 1)
matching = graph.max_weight_matching
matching.edges.map { |e| [e.from, e.to] } #=> ['x1', 'y2'], ['x2', 'y3'], ['x3', 'y1']
matching.edges.sum(&:weight) #=> 16- Fork it ( https://github.com/tomclose/bipartite_graph/fork )
- Create your feature branch (
git checkout -b my-new-feature) - Commit your changes (
git commit -am 'Add some feature') - Push to the branch (
git push origin my-new-feature) - Create a new Pull Request
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent