Home Manual Reference Source

:cherry_blossom: @graph-algorithm/maximum-matching

Maximum matching algorithms for JavaScript. Parent is js-algorithms. See docs.

import maximumMatching, {iter} from '@graph-algorithm/maximum-matching';
const edges = [[1, 2, 10], [2, 3, 11]] ;
const matching = maximumMatching(edges) ; // [-1, -1, 3, 2]
[...iter(matching)]; // [ [2, 3] ]

import maximumCardinalityMatching from '@graph-algorithm/maximum-matching/cardinality';
for (const edge of iter(maximumCardinalityMatching([[1, 2], [2, 3], [3, 4]]))) {
    console.log(edge);
}
// [1,2]
// [3,4]

License Version Tests Dependencies Dev dependencies GitHub issues Downloads

Code issues Code maintainability Code coverage (cov) Code technical debt Documentation Package size

:clap: Credits

The implementation of Edmond's blossom algorithm is adapted from Joris van Rantwijk's python implementation (python source). All credit for the implementation goes to him and others that helped him.

Another adaptation by Matt Krick distributed under the MIT license is available here.