maxmatching (version 0.1.0)

blossom: 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

Value

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

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