Skip to content

Latest commit

 

History

History
212 lines (172 loc) · 7.12 KB

README.md

File metadata and controls

212 lines (172 loc) · 7.12 KB
Raw

GraphMatching

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

Build Status Code Climate

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]]

MCM is O(e * v)

See Benchmarking MCM in Complete Bigraphs

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]]

MCM is O(v ^ 3)

See Benchmarking MCM in Complete Graphs

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

MWM is O(n ^ (3/4) m log N)

See Benchmarking MWM in Complete Bigraphs

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.

MWM is O(mn log n)

See Benchmarking MWM in Complete Graphs

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'
g1 = RGL::AdjacencyGraph['a', 'b']
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.

Glossary

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)