maximum-matching-graph
>> See the demo
Find maximum matchings in an arbitrary bipartite graphs with Node.js
and React.js
Algorithm
The Algorithm is, using the BFS and DFS traversal to find Augmenting Paths.
let M = null;
while(true) {
const P = findAugPath(M) // find augmenting path with respect to M
if (P == null){
break;
}
M = disjunctiveUnion(M, P) // symmetric difference: M <- M Δ P
}
return M;
Augmenting Path
An augmenting path has the conditions bellow:
- Is an alterantive path
- The start and end nodes are not saturated by the matching
Authors
- Alireza Kavian ( @alirezakay )
Acknowledgements
The algorithm implemented in Node JS, is adapted from my mate's code in written in python:
- Soheil Changizi
- maximum matching graph in python codes
License
This project is licensed under the MIT License - see the LICENSE file for details