API

minimum_weight_perfect_matching(g, w::Dict{Edge,Real}; tmaxscale)
minimum_weight_perfect_matching(g, w::Dict{Edge,Real}, cutoff; tmaxscale)
minimum_weight_perfect_matching(g, w::Dict{Edge,Real}, algorithm::AbstractMinimumWeightPerfectMatchingAlgorithm; tmaxscale)
minimum_weight_perfect_matching(g, w::Dict{Edge,Real}, cutoff, algorithm::AbstractMinimumWeightPerfectMatchingAlgorithm; tmaxscale)

Given a graph g and an edgemap w containing weights associated to edges, returns a matching with the mimimum total weight among the ones containing exactly nv(g)/2 edges.

Edges in g not present in w will not be considered for the matching.

You can use the algorithm argument to specify the algorithm to use.

A cutoff argument can be given, to reduce the computational time by excluding edges with weights higher than the cutoff (effective only for some algorithms, not for the default LEMONMWPMAlgorithm).

When the weights are non-integer types, the keyword argument tmaxscale can be used to scale the weights to integer values. In case of error try to change tmaxscale (default is tmaxscale=10). The scaling is as follows:

tmax = typemax(Int32) / tmaxscale
weight = round(Int32, (weight-minimum_weight) / max(maximum_weight-minimum_weight, 1) * tmax)

The returned object is of type MatchingResult.

See also: BlossomVAlgorithm

maximum_weight_maximal_matching{T<:Real}(g, w::Dict{Edge,T})

Given a bipartite graph g and an edge map w containing weights associated to edges, returns a matching with the maximum total weight among the ones containing the greatest number of edges.

Edges in g not present in w will not be considered for the matching.

A cutoff keyword argument can be given, to reduce computational times excluding edges with weights lower than the cutoff.

Finally, a specific algorithm can be chosen (algorithm keyword argument); each algorithm has specific dependencies. For instance:

• If algorithm=HungarianAlgorithm() (the default), the package Hungarian.jl is used. This algorithm is always polynomial in time, with complexity O(n³).
• If algorithm=LPAlgorithm(), the package JuMP.jl and one of its supported solvers is required. In this case, the algorithm relies on a linear relaxation on of the matching problem, which is guaranteed to have integer solution on bipartite graphs. A solver must be provided with the optimizer keyword parameter.

The returned object is of type MatchingResult.

LEMONMWPMAlgorithm()

Use the LEMON C++ implementation of minimum weight perfect matching.

See also: minimum_weight_perfect_matching, BlossomVAlgorithm

LPAlgorithm <: AbstractMaximumWeightMaximalMatchingAlgorithm

Forces the maximumweightmaximal_matching function to use a linear programming formulation.

HungarianAlgorithm <: AbstractMaximumWeightMaximalMatchingAlgorithm

Forces the maximumweightmaximal_matching function to use the Hungarian algorithm.

BlossomVAlgorithm()

Use the BlossomV algorithm to find the minimum weight perfect matching. Depends on the BlossomV.jl package. You have to call using BlossomV before using this algorithm.

This algorithm dispatches to the BlossomV library, a C library for finding minimum weight perfect matchings in general graphs. The BlossomV library is not open source, and thus we can not distribute a a precompiled binary with GraphsMatching.jl. We attempt to build it on installation, but unlike typical Julia packages, the build process is prone to failure if you do not have all the dependencies installed. If BlossomV.jl does not work on your system, consider using the LEMONGraphs.jl algorithm instead (the default algorithm), which we distribute precompiled on all platforms.

See also: minimum_weight_perfect_matching, LEMONMWPMAlgorithm