pygmtools.linear_solvers.hungarian
- pygmtools.linear_solvers.hungarian(s, n1=None, n2=None, unmatch1=None, unmatch2=None, nproc: int = 1, backend=None)[source]
Solve optimal LAP permutation by hungarian algorithm. The time cost is \(O(n^3)\).
- Parameters
s – \((b\times n_1 \times n_2)\) input 3d tensor. \(b\): batch size. Non-batched input is also supported if
sis of size \((n_1 \times n_2)\)n1 – \((b)\) (optional) number of objects in dim1
n2 – \((b)\) (optional) number of objects in dim2
unmatch1 – (optional, new in
0.3.0) \((b\times n_1)\) the scores indicating the objects in dim1 is unmatchedunmatch2 – (optional, new in
0.3.0) \((b\times n_2)\) the scores indicating the objects in dim2 is unmatchednproc – (default: 1, i.e. no parallel) number of parallel processes
backend – (default:
pygmtools.BACKENDvariable) the backend for computation.
- Returns
\((b\times n_1 \times n_2)\) optimal permutation matrix
Note
The parallelization is based on multi-processing workers that run on multiple CPU cores.
Note
For all backends,
scipy.optimize.linear_sum_assignmentis called to solve the LAP, therefore the computation is based onnumpyandscipy. Thebackendargument of this function only affects the input-output data type.Note
We support batched instances with different number of nodes, therefore
n1andn2are required to specify the exact number of objects of each dimension in the batch. If not specified, we assume the batched matrices are not padded and all elements inn1are equal, all inn2are equal.Warning
This function can work with or without maximal inlier matching:
With maximal inlier matching (the default mode). If
unmatch1=Noneandunmatch2=None, the solver aims to match as many nodes as possible. The corresponding linear assignment problem is\[\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}\]where the constraint \(\mathbf{X}\mathbf{1} = \mathbf{1}\) urges the solver to match as many inlier nodes as possible.
Without maximal inlier matching (new in
0.3.0). Ifunmatch1andunmatch2are notNone, the solver is allowed to match nodes to void nodes, and the corresponding scores for matching to void nodes are specified byunmatch1andunmatch2. The following (modified) linear assignment problem is considered:\[\begin{split}&\max_{\mathbf{X}} \ \texttt{tr}(\mathbf{X}^\top \mathbf{S}^\prime)\\ s.t. \quad &\mathbf{X} \in \{0, 1\}^{n_1+1\times n_2+1}, \ \mathbf{X}_{[0:n_1, :]}\mathbf{1} = \mathbf{1}, \ \mathbf{X}_{[:, 0:n_2]}^\top\mathbf{1} \leq \mathbf{1}\end{split}\]where the last column and last row of \(\mathbf{S}^\prime\) are
unmatch1andunmatch2, respectively.For example, if you want to solve the following problem (note that both consrtraints are \(\leq\))
\[\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} \leq \mathbf{1}, \ \mathbf{X}^\top\mathbf{1} \leq \mathbf{1}\end{split}\]you can simply set
unmatch1andunmatch2as zero vectors.
Numpy Example
>>> import numpy as np >>> import pygmtools as pygm >>> pygm.set_backend('numpy') >>> np.random.seed(0) # 2-dimensional (non-batched) input >>> s_2d = np.random.rand(5, 5) >>> s_2d array([[0.5488135 , 0.71518937, 0.60276338, 0.54488318, 0.4236548 ], [0.64589411, 0.43758721, 0.891773 , 0.96366276, 0.38344152], [0.79172504, 0.52889492, 0.56804456, 0.92559664, 0.07103606], [0.0871293 , 0.0202184 , 0.83261985, 0.77815675, 0.87001215], [0.97861834, 0.79915856, 0.46147936, 0.78052918, 0.11827443]]) >>> x = pygm.hungarian(s_2d) >>> x array([[0., 1., 0., 0., 0.], [0., 0., 1., 0., 0.], [0., 0., 0., 1., 0.], [0., 0., 0., 0., 1.], [1., 0., 0., 0., 0.]]) # 3-dimensional (batched) input >>> s_3d = np.random.rand(3, 5, 5) >>> n1 = n2 = np.array([3, 4, 5]) >>> x = pygm.hungarian(s_3d, n1, n2) >>> x array([[[0., 0., 1., 0., 0.], [0., 1., 0., 0., 0.], [1., 0., 0., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]], [[1., 0., 0., 0., 0.], [0., 1., 0., 0., 0.], [0., 0., 1., 0., 0.], [0., 0., 0., 1., 0.], [0., 0., 0., 0., 0.]], [[0., 0., 1., 0., 0.], [1., 0., 0., 0., 0.], [0., 0., 0., 0., 1.], [0., 1., 0., 0., 0.], [0., 0., 0., 1., 0.]]]) # allow matching to void nodes by setting unmatch1 and unmatch2 >>> s_2d = np.random.randn(5, 5) >>> s_2d array([[-1.16514984, 0.90082649, 0.46566244, -1.53624369, 1.48825219], [ 1.89588918, 1.17877957, -0.17992484, -1.07075262, 1.05445173], [-0.40317695, 1.22244507, 0.20827498, 0.97663904, 0.3563664 ], [ 0.70657317, 0.01050002, 1.78587049, 0.12691209, 0.40198936], [ 1.8831507 , -1.34775906, -1.270485 , 0.96939671, -1.17312341]]) >>> unmatch1 = np.random.randn(5) >>> unmatch1 array([ 1.94362119, -0.41361898, -0.74745481, 1.92294203, 1.48051479]) >>> unmatch2 = np.random.randn(5) >>> unmatch2 array([ 1.86755896, 0.90604466, -0.86122569, 1.91006495, -0.26800337]) >>> x = pygm.hungarian(s_2d, unmatch1=unmatch1, unmatch2=unmatch2) >>> x array([[0., 0., 0., 0., 0.], [0., 0., 0., 0., 1.], [0., 0., 1., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]])
Pytorch Example
>>> import torch >>> import pygmtools as pygm >>> pygm.set_backend('pytorch') >>> np.random.seed(0) # 2-dimensional (non-batched) input >>> s_2d = torch.from_numpy(np.random.rand(5, 5)) >>> s_2d tensor([[0.5488, 0.7152, 0.6028, 0.5449, 0.4237], [0.6459, 0.4376, 0.8918, 0.9637, 0.3834], [0.7917, 0.5289, 0.5680, 0.9256, 0.0710], [0.0871, 0.0202, 0.8326, 0.7782, 0.8700], [0.9786, 0.7992, 0.4615, 0.7805, 0.1183]], dtype=torch.float64) >>> x = pygm.hungarian(s_2d) >>> x tensor([[0., 1., 0., 0., 0.], [0., 0., 1., 0., 0.], [0., 0., 0., 1., 0.], [0., 0., 0., 0., 1.], [1., 0., 0., 0., 0.]], dtype=torch.float64) # 3-dimensional (batched) input >>> s_3d = torch.from_numpy(np.random.rand(3, 5, 5)) >>> n1 = n2 = torch.tensor([3, 4, 5]) >>> x = pygm.hungarian(s_3d, n1, n2) >>> x tensor([[[0., 0., 1., 0., 0.], [0., 1., 0., 0., 0.], [1., 0., 0., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]], [[1., 0., 0., 0., 0.], [0., 1., 0., 0., 0.], [0., 0., 1., 0., 0.], [0., 0., 0., 1., 0.], [0., 0., 0., 0., 0.]], [[0., 0., 1., 0., 0.], [1., 0., 0., 0., 0.], [0., 0., 0., 0., 1.], [0., 1., 0., 0., 0.], [0., 0., 0., 1., 0.]]], dtype=torch.float64) # allow matching to void nodes by setting unmatch1 and unmatch2 >>> s_2d = torch.from_numpy(np.random.randn(5, 5)) >>> s_2d tensor([[-1.1651, 0.9008, 0.4657, -1.5362, 1.4883], [ 1.8959, 1.1788, -0.1799, -1.0708, 1.0545], [-0.4032, 1.2224, 0.2083, 0.9766, 0.3564], [ 0.7066, 0.0105, 1.7859, 0.1269, 0.4020], [ 1.8832, -1.3478, -1.2705, 0.9694, -1.1731]], dtype=torch.float64) >>> unmatch1 = torch.from_numpy(np.random.randn(5)) >>> unmatch1 tensor([ 1.9436, -0.4136, -0.7475, 1.9229, 1.4805], dtype=torch.float64) >>> unmatch2 = torch.from_numpy(np.random.randn(5)) >>> unmatch2 tensor([ 1.8676, 0.9060, -0.8612, 1.9101, -0.2680], dtype=torch.float64) >>> x = pygm.hungarian(s_2d, unmatch1=unmatch1, unmatch2=unmatch2) >>> x tensor([[0., 0., 0., 0., 0.], [0., 0., 0., 0., 1.], [0., 0., 1., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]], dtype=torch.float64)
Paddle Example
>>> import paddle >>> import pygmtools as pygm >>> pygm.set_backend('paddle') >>> np.random.seed(0) # 2-dimensional (non-batched) input >>> s_2d = paddle.to_tensor(np.random.rand(5, 5)) >>> s_2d Tensor(shape=[5, 5], dtype=float64, place=Place(cpu), stop_gradient=True, [[0.54881350, 0.71518937, 0.60276338, 0.54488318, 0.42365480], [0.64589411, 0.43758721, 0.89177300, 0.96366276, 0.38344152], [0.79172504, 0.52889492, 0.56804456, 0.92559664, 0.07103606], [0.08712930, 0.02021840, 0.83261985, 0.77815675, 0.87001215], [0.97861834, 0.79915856, 0.46147936, 0.78052918, 0.11827443]]) >>> x = pygm.hungarian(s_2d) >>> x Tensor(shape=[5, 5], dtype=float64, place=Place(cpu), stop_gradient=True, [[0., 1., 0., 0., 0.], [0., 0., 1., 0., 0.], [0., 0., 0., 1., 0.], [0., 0., 0., 0., 1.], [1., 0., 0., 0., 0.]]) # 3-dimensional (batched) input >>> s_3d = paddle.to_tensor(np.random.rand(3, 5, 5)) >>> n1 = n2 = paddle.to_tensor([3, 4, 5]) >>> x = pygm.hungarian(s_3d, n1, n2) >>> x Tensor(shape=[3, 5, 5], dtype=float64, place=Place(cpu), stop_gradient=True, [[[0., 0., 1., 0., 0.], [0., 1., 0., 0., 0.], [1., 0., 0., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]], [[1., 0., 0., 0., 0.], [0., 1., 0., 0., 0.], [0., 0., 1., 0., 0.], [0., 0., 0., 1., 0.], [0., 0., 0., 0., 0.]], [[0., 0., 1., 0., 0.], [1., 0., 0., 0., 0.], [0., 0., 0., 0., 1.], [0., 1., 0., 0., 0.], [0., 0., 0., 1., 0.]]]) # allow matching to void nodes by setting unmatch1 and unmatch2 >>> s_2d = paddle.to_tensor(np.random.randn(5, 5)) >>> s_2d Tensor(shape=[5, 5], dtype=float64, place=Place(cpu), stop_gradient=True, [[-1.16514984, 0.90082649, 0.46566244, -1.53624369, 1.48825219], [ 1.89588918, 1.17877957, -0.17992484, -1.07075262, 1.05445173], [-0.40317695, 1.22244507, 0.20827498, 0.97663904, 0.35636640], [ 0.70657317, 0.01050002, 1.78587049, 0.12691209, 0.40198936], [ 1.88315070, -1.34775906, -1.27048500, 0.96939671, -1.17312341]]) >>> unmatch1 = paddle.to_tensor(np.random.randn(5)) >>> unmatch1 Tensor(shape=[5], dtype=float64, place=Place(cpu), stop_gradient=True, [ 1.94362119, -0.41361898, -0.74745481, 1.92294203, 1.48051479]) >>> unmatch2 = paddle.to_tensor(np.random.randn(5)) >>> unmatch2 Tensor(shape=[5], dtype=float64, place=Place(cpu), stop_gradient=True, [ 1.86755896, 0.90604466, -0.86122569, 1.91006495, -0.26800337]) >>> x = pygm.hungarian(s_2d, unmatch1=unmatch1, unmatch2=unmatch2) >>> x Tensor(shape=[5, 5], dtype=float64, place=Place(cpu), stop_gradient=True, [[0., 0., 0., 0., 0.], [0., 0., 0., 0., 1.], [0., 0., 1., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]])
Jittor Example
>>> import jittor as jt >>> import pygmtools as pygm >>> pygm.set_backend('jittor') >>> np.random.seed(0) # 2-dimensional (non-batched) input >>> s_2d = pygm.utils.from_numpy(np.random.rand(5, 5)) >>> s_2d jt.Var([[0.5488135 0.71518934 0.60276335 0.5448832 0.4236548 ] [0.6458941 0.4375872 0.891773 0.96366274 0.3834415 ] [0.79172504 0.5288949 0.56804454 0.92559665 0.07103606] [0.0871293 0.0202184 0.83261985 0.77815676 0.87001216] [0.9786183 0.7991586 0.46147937 0.7805292 0.11827443]], dtype=float32) >>> x = pygm.hungarian(s_2d) >>> x jt.Var([[0. 1. 0. 0. 0.] [0. 0. 1. 0. 0.] [0. 0. 0. 1. 0.] [0. 0. 0. 0. 1.] [1. 0. 0. 0. 0.]], dtype=float32) # 3-dimensional (batched) input >>> s_3d = pygm.utils.from_numpy(np.random.rand(3, 5, 5)) >>> n1 = n2 = jt.Var([3, 4, 5]) >>> x = pygm.hungarian(s_3d, n1, n2) >>> x jt.Var([[[0. 0. 1. 0. 0.] [0. 1. 0. 0. 0.] [1. 0. 0. 0. 0.] [0. 0. 0. 0. 0.] [0. 0. 0. 0. 0.]] [[1. 0. 0. 0. 0.] [0. 1. 0. 0. 0.] [0. 0. 1. 0. 0.] [0. 0. 0. 1. 0.] [0. 0. 0. 0. 0.]] [[0. 0. 1. 0. 0.] [1. 0. 0. 0. 0.] [0. 0. 0. 0. 1.] [0. 1. 0. 0. 0.] [0. 0. 0. 1. 0.]]], dtype=float32) # allow matching to void nodes by setting unmatch1 and unmatch2 >>> s_2d = pygm.utils.from_numpy(np.random.randn(5, 5)) >>> s_2d jt.Var([[-1.1651498 0.9008265 0.46566245 -1.5362437 1.4882522 ] [ 1.8958892 1.1787796 -0.17992483 -1.0707526 1.0544517 ] [-0.40317693 1.222445 0.20827498 0.97663903 0.3563664 ] [ 0.7065732 0.01050002 1.7858706 0.12691209 0.40198937] [ 1.8831507 -1.347759 -1.270485 0.9693967 -1.1731234 ]], dtype=float32) >>> unmatch1 = pygm.utils.from_numpy(np.random.randn(5)) >>> unmatch1 jt.Var([ 1.9436212 -0.41361898 -0.7474548 1.922942 1.4805148 ], dtype=float32) >>> unmatch2 = pygm.utils.from_numpy(np.random.randn(5)) >>> unmatch2 jt.Var([ 1.867559 0.90604466 -0.86122566 1.9100649 -0.26800337], dtype=float32) >>> x = pygm.hungarian(s_2d, unmatch1=unmatch1, unmatch2=unmatch2) >>> x jt.Var([[0. 0. 0. 0. 0.] [0. 0. 0. 0. 1.] [0. 0. 1. 0. 0.] [0. 0. 0. 0. 0.] [0. 0. 0. 0. 0.]], dtype=float32)
MindSpore Example
>>> import mindspore >>> import pygmtools as pygm >>> pygm.set_backend('mindspore') >>> np.random.seed(0) # 2-dimensional (non-batched) input >>> s_2d = mindspore.Tensor(np.random.rand(5, 5)) >>> s_2d Tensor(shape=[5, 5], dtype=Float64, value= [[5.48813504e-001, 7.15189366e-001, 6.02763376e-001, 5.44883183e-001, 4.23654799e-001], [6.45894113e-001, 4.37587211e-001, 8.91773001e-001, 9.63662761e-001, 3.83441519e-001], [7.91725038e-001, 5.28894920e-001, 5.68044561e-001, 9.25596638e-001, 7.10360582e-002], [8.71292997e-002, 2.02183974e-002, 8.32619846e-001, 7.78156751e-001, 8.70012148e-001], [9.78618342e-001, 7.99158564e-001, 4.61479362e-001, 7.80529176e-001, 1.18274426e-001]]) >>> x = pygm.hungarian(s_2d) >>> x Tensor(shape=[5, 5], dtype=Float64, value= [[0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 1.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 1.00000000e+000], [1.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000]]) # 3-dimensional (batched) input >>> s_3d = mindspore.Tensor(np.random.rand(3, 5, 5)) >>> n1 = n2 = mindspore.Tensor([3, 4, 5]) >>> x = pygm.hungarian(s_3d, n1, n2) >>> x Tensor(shape=[3, 5, 5], dtype=Float64, value= [[[0.00000000e+000, 0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [1.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000]], [[1.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 1.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000]], [[0.00000000e+000, 0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000], [1.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 1.00000000e+000], [0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 1.00000000e+000, 0.00000000e+000]]]) # allow matching to void nodes by setting unmatch1 and unmatch2 >>> s_2d = mindspore.Tensor(np.random.randn(5, 5)) >>> s_2d Tensor(shape=[5, 5], dtype=Float64, value= [[-1.16514984e+000, 9.00826487e-001, 4.65662440e-001, -1.53624369e+000, 1.48825219e+000], [1.89588918e+000, 1.17877957e+000, -1.79924836e-001, -1.07075262e+000, 1.05445173e+000], [-4.03176947e-001, 1.22244507e+000, 2.08274978e-001, 9.76639036e-001, 3.56366397e-001], [7.06573168e-001, 1.05000207e-002, 1.78587049e+000, 1.26912093e-001, 4.01989363e-001], [1.88315070e+000, -1.34775906e+000, -1.27048500e+000, 9.69396708e-001, -1.17312341e+000]]) >>> unmatch1 = mindspore.Tensor(np.random.randn(5)) >>> unmatch1 Tensor(shape=[5], dtype=Float64, value= [1.94362119e+000, -4.13618981e-001, -7.47454811e-001, 1.92294203e+000, 1.48051479e+000]) >>> unmatch2 = mindspore.Tensor(np.random.randn(5)) >>> unmatch2 Tensor(shape=[5], dtype=Float64, value= [1.86755896e+000, 9.06044658e-001, -8.61225685e-001, 1.91006495e+000, -2.68003371e-001]) >>> x = pygm.hungarian(s_2d, unmatch1=unmatch1, unmatch2=unmatch2) >>> x Tensor(shape=[5, 5], dtype=Float64, value= [[0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 1.00000000e+000], [0.00000000e+000, 0.00000000e+000, 1.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000], [0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000, 0.00000000e+000]])
Tensorflow Example
>>> import tensorflow as tf >>> import pygmtools as pygm >>> pygm.set_backend('tensorflow') >>> np.random.seed(0) # 2-dimensional (non-batched) input >>> s_2d = tf.constant(np.random.rand(5, 5)) >>> s_2d <tf.Tensor: shape=(5, 5), dtype=float64, numpy= array([[0.5488135 , 0.71518937, 0.60276338, 0.54488318, 0.4236548 ], [0.64589411, 0.43758721, 0.891773 , 0.96366276, 0.38344152], [0.79172504, 0.52889492, 0.56804456, 0.92559664, 0.07103606], [0.0871293 , 0.0202184 , 0.83261985, 0.77815675, 0.87001215], [0.97861834, 0.79915856, 0.46147936, 0.78052918, 0.11827443]])> >>> x = pygm.hungarian(s_2d) >>> x <tf.Tensor: shape=(5, 5), dtype=float64, numpy= array([[0., 1., 0., 0., 0.], [0., 0., 1., 0., 0.], [0., 0., 0., 1., 0.], [0., 0., 0., 0., 1.], [1., 0., 0., 0., 0.]])> # 3-dimensional (batched) input >>> s_3d = tf.constant(np.random.rand(3, 5, 5)) >>> n1 = n2 = tf.constant([3, 4, 5]) >>> x = pygm.hungarian(s_3d, n1, n2) >>> x <tf.Tensor: shape=(3, 5, 5), dtype=float64, numpy= array([[[0., 0., 1., 0., 0.], [0., 1., 0., 0., 0.], [1., 0., 0., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]], [[1., 0., 0., 0., 0.], [0., 1., 0., 0., 0.], [0., 0., 1., 0., 0.], [0., 0., 0., 1., 0.], [0., 0., 0., 0., 0.]], [[0., 0., 1., 0., 0.], [1., 0., 0., 0., 0.], [0., 0., 0., 0., 1.], [0., 1., 0., 0., 0.], [0., 0., 0., 1., 0.]]])> # allow matching to void nodes by setting unmatch1 and unmatch2 >>> s_2d = tf.constant(np.random.randn(5, 5)) >>> s_2d <tf.Tensor: shape=(5, 5), dtype=float64, numpy= array([[-1.16514984, 0.90082649, 0.46566244, -1.53624369, 1.48825219], [ 1.89588918, 1.17877957, -0.17992484, -1.07075262, 1.05445173], [-0.40317695, 1.22244507, 0.20827498, 0.97663904, 0.3563664 ], [ 0.70657317, 0.01050002, 1.78587049, 0.12691209, 0.40198936], [ 1.8831507 , -1.34775906, -1.270485 , 0.96939671, -1.17312341]])> >>> unmatch1 = tf.constant(np.random.randn(5)) >>> unmatch1 <tf.Tensor: shape=(5,), dtype=float64, numpy=array([ 1.94362119, -0.41361898, -0.74745481, 1.92294203, 1.48051479])> >>> unmatch2 = tf.constant(np.random.randn(5)) >>> unmatch2 <tf.Tensor: shape=(5,), dtype=float64, numpy=array([ 1.86755896, 0.90604466, -0.86122569, 1.91006495, -0.26800337])> >>> x = pygm.hungarian(s_2d, unmatch1=unmatch1, unmatch2=unmatch2) >>> x <tf.Tensor: shape=(5, 5), dtype=float64, numpy= array([[0., 0., 0., 0., 0.], [0., 0., 0., 0., 1.], [0., 0., 1., 0., 0.], [0., 0., 0., 0., 0.], [0., 0., 0., 0., 0.]])>
Note
If you find this graph matching solver useful for your research, please cite:
@article{hungarian, title={Algorithms for the assignment and transportation problems}, author={Munkres, James}, journal={Journal of the society for industrial and applied mathematics}, volume={5}, number={1}, pages={32--38}, year={1957}, publisher={SIAM} }