GraphsMatching.jl: matching algorithms for Graphs.jl

struct MatchingResult{U}
    weight::U
    mate::Vector{Int}
end

A type representing the result of a matching algorithm.

weight: total weight of the matching

mate:    `mate[i] = j` if vertex `i` is matched to vertex `j`.
         `mate[i] = -1` for unmatched vertices.

Returns an array of mates from a dictionary that maps edges to {0,1}

maximumweightmatching(g::Graph, w::Dict{Edge,Real} -> Dict{Edge,Int64}

Given a graph g and an edgemap w containing weights associated to edges, returns a matching with the maximum total weight. w is a dictionary that maps edges i => j to weights. If no weight parameter is given, all edges will be considered to have weight 1 (results in max cardinality matching)

The efficiency of the algorithm depends on the input graph:

• If the graph is bipartite, then the LP relaxation is integral.
• If the graph is not bipartite, then it requires a MIP solver and

the computation time may grow exponentially.

The package JuMP.jl and one of its supported solvers is required.

Returns MatchingResult containing:

• a solve status (indicating whether the problem was solved to optimality)
• the optimal cost
• a list of each vertex's match (or -1 for unmatched vertices)

maximumweightmatching_reduction(g::Graph, w::Matrix{Real}) -> Array{Edge}

Given a graph g and an edgemap w containing weights associated to edges, returns a matching with the maximum total weight. w is an adjacent matrix that maps edges i => j to weights. If no weight parameter is given, all edges will be considered to have weight 1

This algorithm uses a reduction based on the minimumweightperfect_matching function to find the maximum weight matching (see https://homepages.cwi.nl/~schaefer/ftp/pdf/masters-thesis.pdf section 1.5.1).

Return an array of edges contained in the matching.