getAssignment method

List<int> getAssignment()

Main method to compute the minimum cost assignment. Returns the matching as a list of assigned tasks for each agent (_xy). The total cost is not returned here, as this function is for assignment.

Returns a List<int> where result[i] is the index of the task assigned to agent i.

Implementation

List<int> getAssignment() {
  _labelIt(); // Initialize labels for X-vertices

  // Continue augmenting until a perfect matching is found (_matchCount == _n)
  // or no more augmenting paths can be found (e.g., if n != m)
  while (_matchCount < _n) {
    // Reset auxiliary structures for each augmentation attempt
    _inTreeX = List.filled(_n, false);
    _inTreeY = List.filled(_n, false);
    _prev = List.filled(_n, 0);
    _slack = List.filled(_n, 999999999); // Reset slack to a large value
    _slackX = List.filled(_n, 0);

    final int initialMatchCount = _matchCount;
    _augment(); // Attempt to find and apply one augmenting path

    // If no new match was found in this iteration and _matchCount < _n,
    // it implies the problem cannot form a perfect matching or
    // there are no more exposed X-vertices to start augmentation.
    if (_matchCount == initialMatchCount && _matchCount < _n) {
      break; // Cannot find more augmenting paths
    }
  }
  return _xy; // Return the final assignment
}