hungarian_assigner.hpp

Go to the documentation of this file.

// Copyright 2018 the Autoware Foundation
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Co-developed by Tier IV, Inc. and Apex.AI, Inc.
 
#ifndef HUNGARIAN_ASSIGNER__HUNGARIAN_ASSIGNER_HPP_
#define HUNGARIAN_ASSIGNER__HUNGARIAN_ASSIGNER_HPP_
 
 
#define EIGEN_NO_MALLOC
#define EIGEN_STACK_ALLOCATION_LIMIT 0
 
#include <Eigen/Core>
#include <hungarian_assigner/visibility_control.hpp>
#include <utility>
#include <limits>
#include <array>
#include "common/types.hpp"
 
using autoware::common::types::bool8_t;
using autoware::common::types::float32_t;
 
namespace autoware
{
namespace fusion
{
namespace hungarian_assigner
{
 
using index_t = Eigen::Index;
 
template<uint16_t Capacity>
class HUNGARIAN_ASSIGNER_PUBLIC hungarian_assigner_c
{
  static_assert(Capacity > 0, "Capacity must be positive");
  enum mark_e : int8_t
  {
    NO_LINK = 0,   
    UNMARKED = 1,  
    ZERO = 2,      
    PRIMED = 3,    
    STARRED = 4    
  };
 
  using index2_t = std::pair<index_t, index_t>;
 
  class HUNGARIAN_ASSIGNER_LOCAL no_uncovered_values_c : public std::runtime_error
  {
public:
    no_uncovered_values_c();
  };  // class no_uncovered_values_c
 
public:
  static constexpr index_t UNASSIGNED = std::numeric_limits<index_t>::max();
  static constexpr float MAX_WEIGHT = 10000.F;
 
  hungarian_assigner_c();
 
  hungarian_assigner_c(const index_t num_rows, const index_t num_cols);
 
  void set_size(const index_t num_rows, const index_t num_cols);
 
  void set_weight(const float32_t weight, const index_t idx, const index_t jdx);
 
  void reset();
 
  void reset(const index_t num_rows, const index_t num_cols);
 
  bool8_t assign();
 
  // every row/job is guaranteed to have a worker
  index_t get_assignment(const index_t idx) const;
 
  // get unassigned workers/columns. User should know how many unassigned there will be apriori
  index_t get_unassigned(const index_t idx) const;
 
private:
  // TODO(gowtham.ranganathan): Workaround. Should calculate minimum while the weight is being
  //  set. Fix after #979.
  HUNGARIAN_ASSIGNER_LOCAL void find_minimums();
  HUNGARIAN_ASSIGNER_LOCAL bool8_t reduce_rows_and_init_zeros_and_check_result();
 
  HUNGARIAN_ASSIGNER_LOCAL bool8_t increment_starred_zeroes_and_check_result(index2_t loc);
 
  HUNGARIAN_ASSIGNER_LOCAL index2_t prime_uncovered_zero();
 
  HUNGARIAN_ASSIGNER_LOCAL bool8_t add_new_zero(index2_t & loc);
 
  HUNGARIAN_ASSIGNER_LOCAL bool8_t are_all_columns_covered() const;
 
  HUNGARIAN_ASSIGNER_LOCAL bool8_t find_uncovered_zero(index2_t & loc) const;
 
  HUNGARIAN_ASSIGNER_LOCAL bool8_t find_minimum_uncovered_value(
    index2_t & loc,
    float32_t & min_val) const;
 
  HUNGARIAN_ASSIGNER_LOCAL void update_uncovered_rows_and_cols();
 
  // TODO(gowtham.ranganathan): Workaround. There should be no need for m_is_max_matrix after #979
  // Matrix to track if a weight is unset (set to max means unset)
  Eigen::Matrix<bool8_t, Capacity, Capacity> m_is_max_matrix;
  Eigen::Matrix<float32_t, Capacity, Capacity> m_weight_matrix;
  Eigen::Matrix<int8_t, Capacity, Capacity> m_mark_matrix;
  Eigen::Matrix<index_t, Capacity, 1> m_row_min_idx;
  index_t m_num_rows;
  index_t m_num_cols;
  Eigen::Matrix<float32_t, Capacity, 1> m_row_min_weights;
  Eigen::Matrix<index_t, Capacity, 1> m_assignments;
  Eigen::Matrix<bool8_t, Capacity, 1> m_is_col_covered;
  Eigen::Matrix<bool8_t, Capacity, 1> m_is_row_covered;
  index_t m_num_uncovered_rows;
  index_t m_num_uncovered_cols;
  Eigen::Matrix<index_t, Capacity, 1> m_uncovered_rows;
  Eigen::Matrix<index_t, Capacity, 1> m_uncovered_cols;
  Eigen::Matrix<index2_t, 2 * Capacity, 1> m_augment_path;
  Eigen::Matrix<index2_t, Capacity, 1> m_primed_zero_locs;
  index_t m_num_primed_zeros;
};  // class hungarian_assigner_c
 
}  // namespace hungarian_assigner
}  // namespace fusion
}  // namespace autoware
#endif  // HUNGARIAN_ASSIGNER__HUNGARIAN_ASSIGNER_HPP_