# jaredbeck / graph_matching

Finds maximum matchings in undirected graphs.
Ruby Python Gnuplot Shell

## Latest commit Fetching latest commit…
Cannot retrieve the latest commit at this time.

## Files

Type Name Latest commit message Commit time
Failed to load latest commit information. benchmark Feb 16, 2019 lib profile research spec Feb 9, 2020 .gitignore .rubocop.yml .rubocop_todo.yml .travis.yml Feb 16, 2019 CHANGELOG.md Gemfile LICENSE.txt Feb 23, 2014 README.md May 25, 2018 Rakefile graph_matching.gemspec

# GraphMatching

Efficient algorithms for maximum cardinality and maximum weighted matchings in undirected graphs. Uses the Ruby Graph Library (RGL).

## Algorithms

This library implements the four algorithms described by Galil (1986).

### 1. Maximum Cardinality Matching in Bipartite Graphs

Uses the Augmenting Path algorithm, which performs in O(e * v) where e is the number of edges, and v, the number of vertexes (benchmark).

```require 'graph_matching'
g = GraphMatching::Graph::Bigraph[1,3, 1,4, 2,3]
m = g.maximum_cardinality_matching
m.edges
#=> [[4, 1], [3, 2]]``` TO DO: This algorithm is inefficient compared to the Hopcroft-Karp algorithm which performs in O(e * sqrt(v)) in the worst case.

### 2. Maximum Cardinality Matching in General Graphs

Uses Gabow (1976) which performs in O(n^3).

```require 'graph_matching'
g = GraphMatching::Graph::Graph[1,2, 1,3, 1,4, 2,3, 2,4, 3,4]
m = g.maximum_cardinality_matching
m.edges
#=> [[2, 1], [4, 3]]``` Gabow (1976) is not the fastest algorithm, but it is "one exponent faster" than the original, Edmonds' blossom algorithm, which performs in O(n^4).

Faster algorithms include Even-Kariv (1975) and Micali-Vazirani (1980). Galil (1986) describes the latter as "a simpler approach".

### 3. Maximum Weighted Matching in Bipartite Graphs

Uses the Augmenting Path algorithm from Maximum Cardinality Matching, with the "scaling" approach described by Gabow (1983) and Galil (1986), which performs in O(n ^ (3/4) m log N).

```require 'graph_matching'
g = GraphMatching::Graph::WeightedBigraph[
[1, 2, 10],
[1, 3, 11]
]
m = g.maximum_weighted_matching
m.edges
#=> [[3, 1]]
m.weight(g)
#=> 11``` ### 4. Maximum Weighted Matching in General Graphs

A direct port of Van Rantwijk's implementation in python, while referring to Gabow (1985) and Galil (1986) for the big picture.

Unlike the other algorithms above, `WeightedGraph#maximum_weighted_matching` takes an argument, `max_cardinality`. If true, only maximum cardinality matchings will be considered.

```require 'graph_matching'
g = GraphMatching::Graph::WeightedGraph[
[1, 2, 10],
[2, 3, 21],
[3, 4, 10]
]
m = g.maximum_weighted_matching(false)
m.edges
#=> [[3, 2]]
m.weight(g)
#=> 21

m = g.maximum_weighted_matching(true)
m.edges
#=> [[2, 1], [4, 3]]
m.weight(g)
#=> 20```

The algorithm performs in O(mn log n) as described by Galil (1986) p. 34. ## Limitations

All vertexes in a `Graph` must be consecutive positive nonzero integers. This simplifies many algorithms. For your convenience, a module (`GraphMatching::IntegerVertexes`) is provided to convert the vertexes of any `RGL::MutableGraph` to integers.

```require 'graph_matching'
require 'graph_matching/integer_vertexes'
g2, legend = GraphMatching::IntegerVertexes.to_integers(g1)
g2.vertices
#=> [1, 2]
legend
#=> {1=>"a", 2=>"b"}```

## Troubleshooting

• If you have graphviz installed, calling `#print` on any `GraphMatching::Graph` will write a `png` to `/tmp` and `open` it.

## References

• Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics.
• Even, S. and Kariv, O. (1975). An O(n^2.5) Algorithm for Maximum Matching in General Graphs. Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 100-112
• Kusner, M. Edmonds's Blossom Algorithm (pdf)
• Gabow, H. J. (1973). Implementation of algorithms for maximum matching on nonbipartite graphs, Stanford Ph.D thesis.
• Gabow, H. N. (1976). An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs. Journal of the Association for Computing Machinery, Vol. 23, No. 2, pp. 221-234
• Gabow, H. N. (1983). Scaling algorithms for network problems. Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 248-257
• Gabow, H. N. (1985). A scaling algorithm for weighted matching on general graphs. Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 90-100
• Galil, Z. (1986). Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys. Vol. 18, No. 1, pp. 23-38
• Micali, S., and Vazirani, V. (1980). An O(e * sqrt(v)) Algorithm for finding maximal matching in general graphs. Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 17-27
• Van Rantwijk, J. (2013) Maximum Weighted Matching
• Stolee, D.
• West, D. B. (2001). Introduction to graph theory. Prentice Hall. p. 142
• Zwick, U. (2013). Lecture notes on: Maximum matching in bipartite and non-bipartite graphs (pdf)
You can’t perform that action at this time.