Skip to content

graph-algorithm/maximum-matching

Folders and files

NameName
Last commit message
Last commit date
Feb 20, 2025
Apr 15, 2021
Feb 25, 2024
Feb 25, 2024
Feb 25, 2024
Apr 15, 2021
Feb 25, 2024
Jul 24, 2021
Feb 25, 2024
Apr 15, 2021
Sep 7, 2014
Feb 25, 2024
May 9, 2025
Apr 26, 2021
Apr 15, 2021
May 9, 2025

Repository files navigation

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

import {iter, weight as maximumMatching} 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 {opt as maximumCardinalityMatching} from '@graph-algorithm/maximum-matching/cardinality/index.js';
for (const edge of iter(maximumCardinalityMatching([[1, 2], [2, 3], [3, 4]]))) {
	console.log(edge);
}
// [1,2]
// [3,4]

License Version Tests Dependencies GitHub issues Downloads

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

πŸ‘ 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.