pygmtools.linear_solvers
Classic (learning-free) linear assignment problem solvers. These linear assignment solvers are recommended to solve matching problems with only nodes (i.e. linear matching problems), or large-scale graph matching problems where the cost of QAP formulation is too high.
The linear assignment problem only considers nodes, and is also known as bipartite graph matching and linear matching:
\[\begin{split}&\max_{\mathbf{X}} \ \texttt{tr}(\mathbf{X}^\top \mathbf{S})\\
s.t. \quad &\mathbf{X} \in \{0, 1\}^{n_1\times n_2}, \ \mathbf{X}\mathbf{1} = \mathbf{1}, \ \mathbf{X}^\top\mathbf{1} \leq \mathbf{1}\end{split}\]
Functions
Solve optimal LAP permutation by hungarian algorithm. |
|
Sinkhorn algorithm turns the input matrix into a doubly-stochastic matrix. |