Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
53 lines (40 sloc) 1.61 KB

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