blossom {maxmatching}

Blossom's algorithm

Description

Computes the weighted bipartite matching using Hungarian's algorithm

Usage

blossom(G, weighted = FALSE, maxcardinality = FALSE)

Arguments

G

The graph to compute the maximum cardinality matching

weighted

Whether the graph is weighted, if true, weights should be obtained by E(G)$weight

maxcardinality

Whether the maximum weight should be computed over all maximum cardinality matchings

Details

Blossom's algorithm for maximum cardinality matching for general graph

Efficiently compute the maximum weighted biparitite matching using the Hungarian algorithm (TODO: citation) Almost a direct port of Joris van Rantwijk's python code at http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py

Value

The maximum weighted matching for G, in a list of edges