• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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