1 /* Copyright 2017 The TensorFlow Authors. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 #include <queue> 16 #include <vector> 17 #include "tensorflow/core/framework/op_kernel.h" 18 #include "tensorflow/core/framework/tensor.h" 19 #include "tensorflow/core/framework/types.h" 20 21 namespace { 22 23 struct DistancePair { DistancePair__anonbba58b350111::DistancePair24 DistancePair(int i1, int i2, double d) : index1(i1), index2(i2), dist(d) {} 25 operator <__anonbba58b350111::DistancePair26 bool operator<(const DistancePair& b1) const { return b1.dist < dist; } 27 28 int index1, index2; 29 float dist; 30 }; 31 32 } // namespace 33 34 namespace tensorflow { 35 36 class BipartiteMatchOp : public OpKernel { 37 public: BipartiteMatchOp(OpKernelConstruction * context)38 explicit BipartiteMatchOp(OpKernelConstruction* context) : OpKernel(context) { 39 OP_REQUIRES_OK(context, context->GetAttr("top_k", &top_k_)); 40 } 41 Compute(OpKernelContext * context)42 void Compute(OpKernelContext* context) override { 43 const Tensor& input_distance_mat = context->input(0); 44 OP_REQUIRES(context, input_distance_mat.dims() == 2, 45 errors::InvalidArgument( 46 "distance_mat should be 2-dimensional, but got ", 47 input_distance_mat.shape().DebugString())); 48 const int num_input_rows = input_distance_mat.dim_size(0); 49 const int num_input_columns = input_distance_mat.dim_size(1); 50 51 const Tensor& input_num_valid_rows = context->input(1); 52 OP_REQUIRES( 53 context, input_num_valid_rows.NumElements() == 1, 54 errors::InvalidArgument( 55 "num_valid_rows argument should be a tensor with 1 element, " 56 "but got ", 57 input_num_valid_rows.NumElements())); 58 59 const float num_valid_rows_f = input_num_valid_rows.flat<float>()(0); 60 int num_valid_rows = num_input_rows; 61 // If num_valid_rows_f is non-negative, use it to set num_valid_rows. 62 if (num_valid_rows_f >= 0) { 63 num_valid_rows = static_cast<int>(num_valid_rows_f + 0.1); 64 } 65 OP_REQUIRES( 66 context, num_input_rows >= num_valid_rows, 67 errors::InvalidArgument("There should be at least ", num_valid_rows, 68 " rows in distance_mat, but only got ", 69 num_input_rows, " rows.")); 70 71 // If negative or zero then set it to the maximum possible matches. 72 auto valid_top_k = top_k_; 73 74 if (valid_top_k <= 0) { 75 valid_top_k = num_valid_rows * num_input_columns; 76 } 77 78 // Create output tensors. 79 Tensor* row_to_column_match_indices = nullptr; 80 OP_REQUIRES_OK(context, 81 context->allocate_output(0, TensorShape({num_input_rows}), 82 &row_to_column_match_indices)); 83 Tensor* column_to_row_match_indices = nullptr; 84 OP_REQUIRES_OK(context, 85 context->allocate_output(1, TensorShape({num_input_columns}), 86 &column_to_row_match_indices)); 87 88 TTypes<float, 2>::ConstTensor distance_mat = 89 input_distance_mat.shaped<float, 2>( 90 {num_input_rows, num_input_columns}); 91 92 // Greedy bi-partite matching. 93 std::priority_queue<DistancePair> match_queue; 94 95 for (int index1 = 0; index1 < num_valid_rows; index1++) { 96 for (int index2 = 0; index2 < num_input_columns; index2++) { 97 match_queue.push( 98 DistancePair(index1, index2, distance_mat(index1, index2))); 99 } 100 } 101 102 std::vector<int> row_to_col_match_vec(num_input_rows, -1); 103 std::vector<int> col_to_row_match_vec(num_input_columns, -1); 104 int index = 0; 105 while (!match_queue.empty()) { 106 const auto& match = match_queue.top(); 107 if (row_to_col_match_vec[match.index1] == -1 && 108 col_to_row_match_vec[match.index2] == -1) { 109 row_to_col_match_vec[match.index1] = match.index2; 110 col_to_row_match_vec[match.index2] = match.index1; 111 112 index++; 113 if (index >= valid_top_k) { 114 break; 115 } 116 } 117 match_queue.pop(); 118 } 119 120 // Set the output tensors. 121 row_to_column_match_indices->vec<int>() = 122 TTypes<int>::Vec(row_to_col_match_vec.data(), num_input_rows); 123 column_to_row_match_indices->vec<int>() = 124 TTypes<int>::Vec(col_to_row_match_vec.data(), num_input_columns); 125 } 126 127 private: 128 int top_k_; 129 }; 130 131 REGISTER_KERNEL_BUILDER(Name("BipartiteMatch").Device(DEVICE_CPU), 132 BipartiteMatchOp); 133 134 } // namespace tensorflow 135