@graphty/algorithms / index / indexed / maximumBipartiteMatching
Function: maximumBipartiteMatching() ​
maximumBipartiteMatching(
s,options?):BipartiteMatchingResult
Defined in: indexed/matching.ts:150
Maximum matching of a bipartite graph by augmenting paths (Kuhn's algorithm, O(V E)).
Tie rule: among the equally large matchings it returns the one 2.x returned. Left nodes search in the order a breadth-first walk first reaches them (roots in node order, as isBipartite colours), and every node tries its neighbours in the order of the edge that joins them, the earliest added first. The search is depth-first and iterative. Parallel arcs and arc direction (by default) make no difference to the matching size.
Parameters ​
s ​
GraphSnapshot
The snapshot
options? ​
The two sides, and which arcs to follow on a directed snapshot
Returns ​
The partner of every matched left node and the number of pairs
Throws ​
Error when the sides are inferred and the graph is not bipartite