:py:mod:`kwarray.algo_assignment`
=================================

.. py:module:: kwarray.algo_assignment

.. autoapi-nested-parse::

   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::

      - [ ] Implement linear-time maximum weight matching approximation algorithm
        from this paper: https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf



Module Contents
---------------


Functions
~~~~~~~~~

.. autoapisummary::

   kwarray.algo_assignment.mindist_assignment
   kwarray.algo_assignment.mincost_assignment
   kwarray.algo_assignment.maxvalue_assignment



.. py:function:: mindist_assignment(vecs1, vecs2, p=2)

   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.
   :rtype: Tuple[list, float]

   .. rubric:: Notes

   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

   .. rubric:: 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)]


.. py:function:: mincost_assignment(cost)

   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.
   :rtype: Tuple[list, float]

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


   .. rubric:: 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

   .. rubric:: 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

   .. rubric:: 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


.. py:function:: maxvalue_assignment(value)

   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.
   :rtype: Tuple[list, float]

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

   .. rubric:: 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