search

jaredbeck / graph_matching

Finds maximum matchings in undirected graphs.
MIT License
45 stars 17 forks source link

readme

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

Glossary

References