TTK
Loading...
Searching...
No Matches
AssignmentExhaustive.h
Go to the documentation of this file.
1
16
17#pragma once
18
19#include <AssignmentSolver.h>
20#include <Debug.h>
21
22#include <iterator>
23#include <limits>
24#include <map>
25#include <queue>
26#include <set>
27
28namespace ttk {
29
30 template <class dataType>
31 class AssignmentExhaustive : virtual public Debug,
32 public AssignmentSolver<dataType> {
33
34 public:
36
37 ~AssignmentExhaustive() override = default;
38
39 int run(std::vector<MatchingType> &matchings) override;
40
41 void setSaveAsgn(bool doSave) {
42 saveAsgn = doSave;
43 }
44
45 dataType tryAssignment(std::vector<int> &asgn,
46 std::vector<MatchingType> &matchings);
47
48 std::string vectorToString(std::vector<dataType> &my_vector) {
49 std::stringstream result;
50 std::copy(my_vector.begin(), my_vector.end(),
51 std::ostream_iterator<dataType>(result, ""));
52 return result.str();
53 }
54
55 void enumerateAssignments(unsigned int min_dim,
56 unsigned int max_dim,
57 std::vector<std::vector<int>> &allAsgn) {
58 std::queue<std::tuple<std::vector<int>, std::vector<int>, bool,
59 std::vector<bool>, int>>
60 queue;
61
62 std::vector<int> asgn_temp, unasgn_temp;
63 std::vector<bool> done_temp(max_dim, false);
64 queue.push(std::make_tuple(asgn_temp, unasgn_temp, false, done_temp, -1));
65
66 while(!queue.empty()) {
67 auto queueElem = queue.front();
68 queue.pop();
69 std::vector<int> asgn = std::get<0>(queueElem);
70 std::vector<int> unasgn = std::get<1>(queueElem);
71 bool toUnasgn = std::get<2>(queueElem);
72 std::vector<bool> done = std::get<3>(queueElem);
73 unsigned int maxDone = std::get<4>(queueElem);
74
75 unsigned int ind = asgn.size();
76 for(unsigned int j = 0; j < max_dim + 1; ++j) {
77 std::vector<int> new_asgn(asgn);
78 std::vector<int> new_unasgn(unasgn);
79 std::vector<bool> new_done(done);
80 int new_maxDone = maxDone;
81 if(j < max_dim) {
82 if(not done[j]) {
83 if(ind >= min_dim and maxDone > j)
84 continue;
85 } else
86 continue;
87
88 if(not toUnasgn) {
89 new_asgn.push_back(j);
90 if(ind >= min_dim)
91 new_maxDone = std::max(maxDone, j);
92 } else {
93 new_unasgn.push_back(j);
94 new_maxDone = std::max(maxDone, j);
95 }
96 new_done[j] = true;
97
98 unsigned int new_ind = new_asgn.size();
99 if(new_ind == max_dim) {
100 // A new assignment is made here
101 for(auto &new_unasgn_elem : new_unasgn)
102 new_asgn.push_back(new_unasgn_elem);
103 // std::sort(new_asgn.begin()+min_dim, new_asgn.end());
104 allAsgn.push_back(new_asgn);
105 } else
106 queue.push(std::make_tuple(
107 new_asgn, new_unasgn, false, new_done, new_maxDone));
108
109 } else {
110 if(not toUnasgn and ind < min_dim) {
111 new_asgn.push_back(max_dim);
112 queue.push(std::make_tuple(
113 new_asgn, new_unasgn, true, new_done, new_maxDone));
114 }
115 }
116 }
117 }
118 }
119
120 void printAssignments(std::vector<std::vector<int>> &allAsgn) {
122 std::stringstream ss;
123 ss << "{";
124 for(auto &vecTemp : allAsgn) {
125 ss << "{";
126 for(unsigned int i = 0; i < vecTemp.size(); ++i) {
127 auto valTemp = vecTemp[i];
128 ss << valTemp;
129 if(i != vecTemp.size() - 1)
130 ss << ",";
131 }
132 ss << "}, ";
133 }
134 ss << "}";
137 }
138
139 private:
140 // This attribute will store the computed assignments
141 std::map<std::string, std::vector<std::vector<int>>> savedAsgn;
142 bool saveAsgn = false;
143 };
144
145 template <typename dataType>
147 std::vector<int> &asgn, std::vector<MatchingType> &matchings) {
148 unsigned int nRows = this->costMatrix.size() - 1;
149 unsigned int nCols = this->costMatrix[0].size() - 1;
150 // int max_dim = std::max(nRows, nCols);
151 unsigned int min_dim = std::min(nRows, nCols);
152 bool transpose = nRows > nCols;
153
154 dataType cost = 0;
155 for(unsigned int ind = 0; ind < asgn.size(); ++ind) {
156 int indMatrix = std::min(ind, min_dim);
157 int i = (!transpose) ? indMatrix : asgn[ind];
158 int j = (!transpose) ? asgn[ind] : indMatrix;
159 cost += this->costMatrix[i][j];
160 matchings.push_back(std::make_tuple(i, j, this->costMatrix[i][j]));
161 }
162 return cost;
163 }
164
165 template <typename dataType>
167 std::vector<MatchingType> &matchings) {
168 int nRows = this->costMatrix.size() - 1;
169 int nCols = this->costMatrix[0].size() - 1;
170 int max_dim = std::max(nRows, nCols);
171 int min_dim = std::min(nRows, nCols);
172
173 // --- Construct all possible assignments
174 std::vector<std::vector<int>> allAsgn;
175 // We hard write the basic assignments to avoid the call of
176 // enumerateAssignments
177 // These assignments are automatically generated by enumerateAssignments
178 if(min_dim == 1 and max_dim == 1)
179 allAsgn = {{0}, {1, 0}};
180 else if(min_dim == 1 and max_dim == 2)
181 allAsgn = {{0, 1}, {2, 0, 1}, {1, 0}};
182 else if(min_dim == 1 and max_dim == 3)
183 allAsgn = {{0, 1, 2}, {3, 0, 1, 2}, {1, 0, 2}, {2, 0, 1}};
184 else if(min_dim == 1 and max_dim == 4)
185 allAsgn = {{0, 1, 2, 3},
186 {4, 0, 1, 2, 3},
187 {1, 0, 2, 3},
188 {2, 0, 1, 3},
189 {3, 0, 1, 2}};
190 else if(min_dim == 1 and max_dim == 5)
191 allAsgn = {{0, 1, 2, 3, 4}, {5, 0, 1, 2, 3, 4}, {1, 0, 2, 3, 4},
192 {2, 0, 1, 3, 4}, {3, 0, 1, 2, 4}, {4, 0, 1, 2, 3}};
193 else if(min_dim == 1 and max_dim == 6)
194 allAsgn = {{0, 1, 2, 3, 4, 5}, {6, 0, 1, 2, 3, 4, 5}, {1, 0, 2, 3, 4, 5},
195 {2, 0, 1, 3, 4, 5}, {3, 0, 1, 2, 4, 5}, {4, 0, 1, 2, 3, 5},
196 {5, 0, 1, 2, 3, 4}};
197 else if(min_dim == 2 and max_dim == 2)
198 allAsgn = {{0, 1}, {0, 2, 1}, {2, 1, 0}, {2, 2, 0, 1},
199 {1, 0}, {1, 2, 0}, {2, 0, 1}};
200 else {
201 std::stringstream ss;
202 ss << min_dim << "_" << max_dim;
203 std::string asgnName = ss.str();
204 // not found
205 if(not saveAsgn or savedAsgn.find(asgnName) == savedAsgn.end()) {
206 if(saveAsgn)
208 enumerateAssignments(min_dim, max_dim, allAsgn);
209 if(saveAsgn) {
210 savedAsgn[asgnName] = allAsgn;
211 std::stringstream ss2;
212 ss2 << allAsgn.size() << " done";
214 }
215 } else
216 allAsgn = savedAsgn[asgnName];
217 }
218
219 // --- Try these assignments and get the better
220 dataType bestCost = std::numeric_limits<dataType>::max();
221 std::vector<MatchingType> bestMatching;
222 for(std::vector<int> &asgn : allAsgn) {
223 std::vector<MatchingType> tempMatching;
224 dataType cost = tryAssignment(asgn, tempMatching);
225 if(bestCost > cost) {
226 bestCost = cost;
227 bestMatching = tempMatching;
228 }
229 }
230 matchings = bestMatching;
231
232 return 0;
233 }
234
235} // namespace ttk
~AssignmentExhaustive() override=default
void printAssignments(std::vector< std::vector< int > > &allAsgn)
std::string vectorToString(std::vector< dataType > &my_vector)
void enumerateAssignments(unsigned int min_dim, unsigned int max_dim, std::vector< std::vector< int > > &allAsgn)
int run(std::vector< MatchingType > &matchings) override
dataType tryAssignment(std::vector< int > &asgn, std::vector< MatchingType > &matchings)
Minimalist debugging class.
Definition: Debug.h:88
int printMsg(const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const
Definition: Debug.h:118
The Topology ToolKit.
printMsg(debug::output::GREEN+"                           "+debug::output::ENDCOLOR+debug::output::GREEN+"▒"+debug::output::ENDCOLOR+debug::output::GREEN+"▒▒▒▒▒▒▒▒▒▒▒▒▒░"+debug::output::ENDCOLOR, debug::Priority::PERFORMANCE, debug::LineMode::NEW, stream)