Matching algorithms for LightGraphs.jl
Switch branches/tags
Clone or download

README.md

LightGraphsMatching

Build Status

Coverage Status

codecov

Matching algorithms on top of LightGraphs.

Usage

The results of any matching is returned as a MatchingResult struct containing the mate and weight fields.

Perfect matching

g =CompleteGraph(4)
w =Dict{Edge,Float64}()
w[Edge(1,3)] = 10
w[Edge(1,4)] = 0.5
w[Edge(2,3)] = 11
w[Edge(2,4)] = 2
w[Edge(1,2)] = 100

# find the perfect matching of minimum weight
match = minimum_weight_perfect_matching(g, w, 50)
# match.mate[1] == 4
# match.mate[4] == 1
# match.mate[2] == 3
# match.mate[3] == 2
# match.weight ≈ 11.5

Maximum weight matching

A maximum weight matching is solved as a Linear Programming problem and requires a LP solver respecting the MathProgBase solver interface. See MathProgBase documentation for more details.

using Cbc: CbcSolver #import a LP solver
g = CompleteGraph(3)
w = zeros(3,3)
w[1,2] = 1
w[3,2] = 1
w[1,3] = 1
match = maximum_weight_matching(g,CbcSolver(),w)
# match.weight ≈ 1