Maximum Graph Matching Library (NSD 2023 Spring NYCU Term Project)
All vertices are numbered from 0.
Maximum Cardinality Bipartite Matching
- Parameter
- Give
adjx
that for allx
in$X$ ,adjx[x]
stores all vertices in the other part,$Y$ , connected tox
and the number of vertices in$Y$ ,ny
.
- Give
- Return Value
- Return
mx
such thatmx[x]
is the matched vertex tox
or -1 if unmatched.
- Return
Maximum Weight Bipartite Matching
- Parameter
- Give a
$n$ by$n$ matrix,$weight$ .
- Give a
- Return Value
- Return
mx
such thatmx[x]
is the matched vertex tox
- Return
Maximum Cardinality Matching
- Parameter
- Give
adj
that for allu
,adj[u]
stores all vertices connected tou
.
- Give
- Return Value
- Return
mh
such thatmh[u]
is the matched vertex tou
or -1 if unmatched.
- Return
The module name is MGML
and all vertices are also numbered from 0.
The Python API are basically almost the same as C++ API.