TTK
Loading...
Searching...
No Matches
AssignmentMunkres.h
Go to the documentation of this file.
1
4
5#pragma once
6
7#include <AssignmentSolver.h>
8
9#include <cmath>
10#include <iostream>
11#include <limits>
12
13namespace ttk {
14
15 template <class dataType>
16 class AssignmentMunkres : virtual public Debug,
17 public AssignmentSolver<dataType> {
18
19 public:
21 this->setDebugMsgPrefix("AssignmentMunkres");
22 }
23
24 ~AssignmentMunkres() override = default;
25
26 int run(std::vector<MatchingType> &matchings) override;
27
28 inline void clear() override {
30 pathCount = 0;
31 createdZeros.clear();
32 }
33
34 inline int setInput(std::vector<std::vector<dataType>> &C_) override {
36
37 createdZeros.clear();
38
39 auto r = (unsigned long)this->rowSize;
40 auto c = (unsigned long)this->colSize;
41
42 rowCover.resize(r);
43 colCover.resize(c);
44
45 rowLimitsMinus.resize(r);
46 rowLimitsPlus.resize(r);
47 colLimitsMinus.resize(c);
48 colLimitsPlus.resize(c);
49
50 M.resize(r);
51 for(int row = 0; row < this->rowSize; ++row)
52 M[row].resize(c);
53
54 int nbPaths = 1 + this->colSize + this->rowSize;
55 path.resize((unsigned long)nbPaths);
56 for(int p = 0; p < nbPaths; ++p)
57 path[p].resize(2);
58
59 resetMasks();
60
61 return 0;
62 }
63
64 inline void showCostMatrix() {
66 std::stringstream msg;
67 for(int r = 0; r < this->rowSize; ++r) {
68 msg << std::endl << " ";
69 for(int c = 0; c < this->colSize; ++c)
70 msg << std::fixed << std::setprecision(3) << (*C)[r][c] << " ";
71 }
72
73 this->printMsg(msg.str(), debug::Priority::DETAIL);
74 }
75
76 inline void showMaskMatrix() {
77 std::stringstream msg;
78 msg << std::endl << " | ";
79 for(int c = 0; c < this->colSize; ++c) {
80 msg << colCover[c] << " ";
81 }
82 msg << std::endl << " | ";
83 for(int c = 0; c < this->colSize; ++c) {
84 msg << "---";
85 }
86 msg << std::endl;
87 for(int r = 0; r < this->rowSize; ++r) {
88 msg << " " << rowCover[r] << " | ";
89 for(int c = 0; c < this->colSize; ++c)
90 msg << M[r][c] << " ";
91 msg << std::endl;
92 }
93 this->printMsg(msg.str(), debug::Priority::DETAIL);
94 }
95
96 private:
97 std::vector<std::vector<int>> M;
98 std::vector<bool> rowCover;
99 std::vector<bool> colCover;
100
101 std::vector<int> rowLimitsMinus;
102 std::vector<int> rowLimitsPlus;
103 std::vector<int> colLimitsMinus;
104 std::vector<int> colLimitsPlus;
105
106 std::vector<std::vector<int>> path;
107 std::vector<std::pair<int, int>> createdZeros;
108
109 int pathRow0;
110 int pathCol0;
111 int pathCount = 0;
112
113 // internal methods
114 int stepOne(int &step);
115
116 int stepTwo(int &step);
117
118 int stepThree(int &step);
119
120 int stepFour(int &step);
121 int findZero(int &row, int &col);
122 int findStarInRow(int row);
123
124 int stepFive(int &step);
125 int findStarInCol(int col);
126 int findPrimeInRow(int row);
127
128 int stepSix(int &step);
129
130 int stepSeven(int &step);
131
132 int affect(std::vector<MatchingType> &matchings,
133 const std::vector<std::vector<dataType>> &C);
134
135 int computeAffectationCost(const std::vector<std::vector<dataType>> &C);
136
137 inline bool isZero(dataType t) {
138 // return std::abs((double) t) < 1e-15;
139 return t == 0.;
140 }
141
142 inline int resetMasks() {
143 for(int r = 0; r < this->rowSize; ++r) {
144 rowCover[r] = false;
145 for(int c = 0; c < this->colSize; ++c)
146 M[r][c] = 0;
147 }
148 for(int c = 0; c < this->colSize; ++c)
149 colCover[c] = false;
150 return 0;
151 }
152
153 inline int copyInputMatrix(std::vector<std::vector<dataType>> &saveInput) {
155 int rS = this->rowSize;
156 int cS = this->colSize;
157
158 for(int r = 0; r < rS; ++r)
159 for(int c = 0; c < cS; ++c)
160 saveInput[r][c] = (*C)[r][c];
161
162 return 0;
163 }
164 };
165
166} // namespace ttk
167
int run(std::vector< MatchingType > &matchings) override
int setInput(std::vector< std::vector< dataType > > &C_) override
~AssignmentMunkres() override=default
virtual std::vector< std::vector< dataType > > getCostMatrix()
virtual int setInput(std::vector< std::vector< dataType > > &C_)
virtual std::vector< std::vector< dataType > > * getCostMatrixPointer()
Minimalist debugging class.
Definition: Debug.h:88
void setDebugMsgPrefix(const std::string &prefix)
Definition: Debug.h:364
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.