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

hungarian

Solve optimal LAP permutation by hungarian algorithm.

sinkhorn

Sinkhorn algorithm turns the input matrix into a doubly-stochastic matrix.