kwarray.algo_assignment module

A convinient interface to solving assignment problems with the Hungarian algorithm (also known as Munkres or maximum linear-sum-assignment).

The core implementation of munkres in in scipy. Recent versions are written in C, so their speed should be reflected here.

Todo

kwarray.algo_assignment.mindist_assignment(vecs1, vecs2, p=2)[source]

Finds minimum cost assignment between two sets of D dimensional vectors.

Parameters:

  • vecs1 (np.ndarray) – NxD array of vectors representing items in vecs1

  • vecs2 (np.ndarray) – MxD array of vectors representing items in vecs2

  • p (float) – L-p norm to use. Default is 2 (aka Eucliedean)

Returns:

tuple containing assignments of rows in vecs1 to

rows in vecs2, and the total distance between assigned pairs.

Return type:

Tuple[list, float]

Note

Thin wrapper around mincost_assignment

CommandLine

xdoctest -m ~/code/kwarray/kwarray/algo_assignment.py mindist_assignment

CommandLine

xdoctest -m ~/code/kwarray/kwarray/algo_assignment.py mindist_assignment

Example

>>> # xdoctest: +REQUIRES(module:scipy)
>>> # Rows are detections in img1, cols are detections in img2
>>> rng = np.random.RandomState(43)
>>> vecs1 = rng.randint(0, 10, (5, 2))
>>> vecs2 = rng.randint(0, 10, (7, 2))
>>> ret = mindist_assignment(vecs1, vecs2)
>>> print('Total error: {:.4f}'.format(ret[1]))
Total error: 8.2361
>>> print('Assignment: {}'.format(ret[0]))  # xdoc: +IGNORE_WANT
Assignment: [(0, 0), (1, 3), (2, 5), (3, 2), (4, 6)]
kwarray.algo_assignment.mincost_assignment(cost)[source]

Finds the minimum cost assignment based on a NxM cost matrix, subject to the constraint that each row can match at most one column and each column can match at most one row. Any pair with a cost of infinity will not be assigned.

Parameters:

cost (ndarray) – NxM matrix, cost[i, j] is the cost to match i and j

Returns:

tuple containing a list of assignment of rows

and columns, and the total cost of the assignment.

Return type:

Tuple[list, float]

CommandLine

xdoctest -m ~/code/kwarray/kwarray/algo_assignment.py mincost_assignment

Example

>>> # xdoctest: +REQUIRES(module:scipy)
>>> # Costs to match item i in set1 with item j in set2.
>>> cost = np.array([
>>>     [9, 2, 1, 9],
>>>     [4, 1, 5, 5],
>>>     [9, 9, 2, 4],
>>> ])
>>> ret = mincost_assignment(cost)
>>> print('Assignment: {}'.format(ret[0]))
>>> print('Total cost: {}'.format(ret[1]))
Assignment: [(0, 2), (1, 1), (2, 3)]
Total cost: 6

Example

>>> # xdoctest: +REQUIRES(module:scipy)
>>> cost = np.array([
>>>     [0, 0, 0, 0],
>>>     [4, 1, 5, -np.inf],
>>>     [9, 9, np.inf, 4],
>>>     [9, -2, np.inf, 4],
>>> ])
>>> ret = mincost_assignment(cost)
>>> print('Assignment: {}'.format(ret[0]))
>>> print('Total cost: {}'.format(ret[1]))
Assignment: [(0, 2), (1, 3), (2, 0), (3, 1)]
Total cost: -inf

Example

>>> # xdoctest: +REQUIRES(module:scipy)
>>> cost = np.array([
>>>     [0, 0, 0, 0],
>>>     [4, 1, 5, -3],
>>>     [1, 9, np.inf, 0.1],
>>>     [np.inf, np.inf, np.inf, 100],
>>> ])
>>> ret = mincost_assignment(cost)
>>> print('Assignment: {}'.format(ret[0]))
>>> print('Total cost: {}'.format(ret[1]))
Assignment: [(0, 2), (1, 1), (2, 0), (3, 3)]
Total cost: 102.0
kwarray.algo_assignment.maxvalue_assignment(value)[source]

Finds the maximum value assignment based on a NxM value matrix. Any pair with a non-positive value will not be assigned.

Parameters:

value (ndarray) – NxM matrix, value[i, j] is the value of matching i and j

Returns:

tuple containing a list of assignment of rows

and columns, and the total value of the assignment.

Return type:

Tuple[list, float]

CommandLine

xdoctest -m ~/code/kwarray/kwarray/algo_assignment.py maxvalue_assignment

Example

>>> # xdoctest: +REQUIRES(module:scipy)
>>> # Costs to match item i in set1 with item j in set2.
>>> value = np.array([
>>>     [9, 2, 1, 3],
>>>     [4, 1, 5, 5],
>>>     [9, 9, 2, 4],
>>>     [-1, -1, -1, -1],
>>> ])
>>> ret = maxvalue_assignment(value)
>>> # Note, depending on the scipy version the assignment might change
>>> # but the value should always be the same.
>>> print('Total value: {}'.format(ret[1]))
Total value: 23.0
>>> print('Assignment: {}'.format(ret[0]))  # xdoc: +IGNORE_WANT
Assignment: [(0, 0), (1, 3), (2, 1)]

>>> ret = maxvalue_assignment(np.array([[np.inf]]))
>>> print('Assignment: {}'.format(ret[0]))
>>> print('Total value: {}'.format(ret[1]))
Assignment: [(0, 0)]
Total value: inf

>>> ret = maxvalue_assignment(np.array([[0]]))
>>> print('Assignment: {}'.format(ret[0]))
>>> print('Total value: {}'.format(ret[1]))
Assignment: []
Total value: 0