code: def linear_sum_assignment(cost_matrix):
      """Solve the linear sum assignment problem.
  
      The linear sum assignment problem is also known as minimum weight matching
      in bipartite graphs. A problem instance is described by a matrix C, where
      each C[i,j] is the cost of matching vertex i of the first partite set
      (a "worker") and vertex j of the second set (a "job"). The goal is to find
      a complete assignment of workers to jobs of minimal cost.
  
      Formally, let X be a boolean matrix where :math:`X[i,j] = 1` iff row i is
      assigned to column j. Then the optimal assignment has cost
  
      .. math::
          \\min \\sum_i \\sum_j C_{i,j} X_{i,j}
  
      s.t. each row is assignment to at most one column, and each column to at
      most one row.
  
      This function can also solve a generalization of the classic assignment
      problem where the cost matrix is rectangular. If it has more rows than
      columns, then not every row needs to be assigned to a column, and vice
      versa.
  
      The method used is the Hungarian algorithm, also known as the Munkres or
      Kuhn-Munkres algorithm.
  
      Parameters
      ----------
      cost_matrix : array
          The cost matrix of the bipartite graph.
  
      Returns
      -------
      row_ind, col_ind : array
          An array of row indices and one of corresponding column indices giving
          the optimal assignment. The cost of the assignment can be computed
          as ``cost_matrix[row_ind, col_ind].sum()``. The row indices will be
          sorted; in the case of a square cost matrix they will be equal to
          ``numpy.arange(cost_matrix.shape[0])``.
  
      Notes
      -----
      .. versionadded:: 0.17.0
  
      Examples
      --------
      >>> cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])
      >>> from scipy.optimize import linear_sum_assignment
      >>> row_ind, col_ind = linear_sum_assignment(cost)
      >>> col_ind
      array([1, 0, 2])
      >>> cost[row_ind, col_ind].sum()
      5
  
      References
      ----------
      1. http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html
  
      2. Harold W. Kuhn. The Hungarian Method for the assignment problem.
         *Naval Research Logistics Quarterly*, 2:83-97, 1955.
  
      3. Harold W. Kuhn. Variants of the Hungarian method for assignment
         problems. *Naval Research Logistics Quarterly*, 3: 253-258, 1956.
  
      4. Munkres, J. Algorithms for the Assignment and Transportation Problems.
         *J. SIAM*, 5(1):32-38, March, 1957.
  
      5. https://en.wikipedia.org/wiki/Hungarian_algorithm
      """
      cost_matrix = np.asarray(cost_matrix)
      if len(cost_matrix.shape) != 2:
          raise ValueError(
              "expected a matrix (2-d array), got a %r array"
              % (cost_matrix.shape,)
          )
  
      if not (
          np.issubdtype(cost_matrix.dtype, np.number)
          or cost_matrix.dtype == np.dtype(np.bool)
      ):
          raise ValueError(
              "expected a matrix containing numerical entries, got %s"
              % (cost_matrix.dtype,)
          )
  
      if np.any(np.isinf(cost_matrix) | np.isnan(cost_matrix)):
          raise ValueError("matrix contains invalid numeric entries")
  
      if cost_matrix.dtype == np.dtype(np.bool):
          cost_matrix = cost_matrix.astype(np.int)
  
      # The algorithm expects more columns than rows in the cost matrix.
      if cost_matrix.shape[1] < cost_matrix.shape[0]:
          cost_matrix = cost_matrix.T
          transposed = True
      else:
          transposed = False
  
      state = _Hungary(cost_matrix)
  
      # No need to bother with assignments if one of the dimensions
      # of the cost matrix is zero-length.
      step = None if 0 in cost_matrix.shape else _step1
  
      while step is not None:
          step = step(state)
  
      if transposed:
          marked = state.marked.T
      else:
          marked = state.marked
      return np.nonzero(marked == 1)
  
file_path: catboost/contrib/python/scipy/py2/scipy/optimize/_hungarian.py
imports: import numpy
label_desc: Use image node_id 1 for calling a global function with example usage: linear_sum_assignment(cost_matrix) and returns: np