Package Exports

maximum-matching
maximum-matching/dist/index.js

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (maximum-matching) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

Typescript Maximum Matching 📘

Implementation of Edmonds’ Blossom algorithm for a maximum matching in graphs with Typescript and graphology

Installation 💾

yarn add maximum-matching

# or

npm install maximum-matching

# ...

Usage 🔬

First we need to create our graph. You can use a regular one from graphology or our MatchingGraph

import { MatchingGraph, maximumMatching } from 'maximum-matching'

const graph = new MatchingGraph()

graph.addNode('1')
graph.addNode('2')
graph.addNode('3')
graph.addNode('4')

// 1 - 2
// |   |
// 3 - 4
graph.addEdge('1', '2')
graph.addEdge('2', '4')
graph.addEdge('4', '3')
graph.addEdge('3', '1')

Then we can use the maximumMatching function to calculate it

const result = maximumMatching(graph)
// [ [ '1', '2' ], [ '3', '4' ] ]

Special cases 🧐

When it is not possible to create a perfect matching (e.g. in graphs with an odd number of nodes), it can be interesting to use the maximumMatchingGraph function, which returns a MatchingGraph

This is simply a subclass of UndirectedGraph from graphology that has useful methods for working with matchings.

In most cases you may not want to use them, but a very interesting one is .unpairedNodes(), which lets you know which nodes are unpaired after running the algorithm.

import { maximumMatchingGraph, MatchingGraph } from 'maximum-matching'

const graph = new MatchingGraph()

graph.addNode('Peter')
graph.addNode('Dave')
graph.addNode('Maria')
graph.addNode('Sara')
graph.addNode('Daniel')

// Peter - Dave
//  |       |
// Maria - Sara - Daniel
graph.addEdge('Daniel', 'Sara')
graph.addEdge('Sara', 'Maria')
graph.addEdge('Maria', 'Peter')
graph.addEdge('Peter', 'Dave')
graph.addEdge('Dave', 'Sara')

const resultGraph = maximumMatchingGraph(graph)

const maximumMatching = resultGraph.matching()
// [ [ 'Maria', 'Peter' ], [ 'Dave', 'Sara' ] ]

const unpairedNodes = resultGraph.unpairedNodes()
// [ 'Daniel' ]

calling the .matching() method in the resulting graph is the same thing as using the maximumMatching function directly.

Theory 🎓

Formal proof: Stanford University

Simplified proof: Made by me (Spanish)

Author 🧑‍🔬

Developed by Julio César Castro López