TTK
Loading...
Searching...
No Matches
PersistenceDiagramAuction.h
Go to the documentation of this file.
1#pragma once
2
4
5#include <limits>
6
7namespace ttk {
9
10 public:
12 return bidders_.size();
13 }
14
16
19 std::vector<KDT *> default_correspondence_kdt_map_{};
20 std::vector<KDT *> &correspondence_kdt_map_{
22
23 inline void initLowerBoundCostWeight(double delta_lim) {
24 lowerBoundCostWeight_ = 1 + delta_lim;
25 }
26
27 double initLowerBoundCost(const int kdt_index = 0);
28
30 double geometricalFactor,
31 double lambda,
32 double delta_lim,
33 bool use_kdTree)
34 : wasserstein_{wasserstein}, geometricalFactor_{geometricalFactor},
35 lambda_{lambda}, delta_lim_{delta_lim}, use_kdt_{use_kdTree} {
36 }
37
39 GoodDiagram &goods,
40 int wasserstein,
41 double geometricalFactor,
42 double lambda,
43 double delta_lim,
44 KDT &kdt,
45 std::vector<KDT *> &correspondence_kdt_map,
46 double epsilon = {},
47 double initial_diag_price = {},
48 bool use_kdTree = true)
49 : kdt_{kdt}, correspondence_kdt_map_{correspondence_kdt_map},
50 bidders_{bidders}, goods_{goods} {
51
52 n_bidders_ = bidders.size();
53 n_goods_ = goods.size();
54
55 for(int i = 0; i < n_bidders_; i++) {
56 // Add diagonal goods
57 Bidder &b = bidders_[i];
58 Good g{b.x_, b.y_, true, -b.id_ - 1};
59 g.projectOnDiagonal();
60 if(b.diagonal_price_ > 0) {
61 g.setPrice(b.diagonal_price_);
62 } else {
63 g.setPrice(initial_diag_price);
64 }
65 diagonal_goods_.emplace_back(g);
66 std::pair<int, double> pair = std::make_pair(i, g.getPrice());
67 diagonal_queue_.push(pair);
68 }
69 for(int i = 0; i < n_goods_; i++) {
70 // Add diagonal bidders
71 Good &g = goods_[i];
72 Bidder b{g.x_, g.y_, true, -g.id_ - 1};
73 b.projectOnDiagonal();
74 b.setPositionInAuction(bidders_.size());
75 bidders_.emplace_back(b);
76 }
77
78 epsilon_ = epsilon;
79 wasserstein_ = wasserstein;
80 delta_lim_ = delta_lim;
81 geometricalFactor_ = geometricalFactor;
82 lambda_ = lambda;
83
84 use_kdt_ = (use_kdTree && !goods_.empty());
85 }
86
87 void runAuctionRound(int &n_biddings, const int kdt_index = 0);
88 double getMatchingsAndDistance(std::vector<MatchingType> &matchings,
89 bool get_diagonal_matches = false);
90 double run(std::vector<MatchingType> &matchings, const int kdt_index = 0);
91 double run() {
92 std::vector<MatchingType> matchings{};
93 return this->run(matchings);
94 }
95 double getMaximalPrice();
96
97 void BuildAuctionDiagrams(const BidderDiagram &BD, const GoodDiagram &GD) {
98 this->n_bidders_ = BD.size();
99 this->n_goods_ = GD.size();
100 // delete_kdTree_ = false;
101 this->bidders_ = BD;
102 this->goods_ = GD;
103
104 for(int i = 0; i < n_bidders_; i++) {
105 // Add diagonal goods
106 Bidder &b = bidders_[i];
107 Good g{b.x_, b.y_, true, -b.id_ - 1};
108 g.projectOnDiagonal();
109 diagonal_goods_.emplace_back(g);
110 std::pair<int, double> pair = std::make_pair(i, g.getPrice());
111 diagonal_queue_.push(pair);
112 }
113 for(int i = 0; i < n_goods_; i++) {
114 // Add diagonal bidders
115 Good &g = goods_[i];
116 Bidder b{g.x_, g.y_, true, -g.id_ - 1};
117 b.projectOnDiagonal();
118 b.setPositionInAuction(bidders_.size());
119 bidders_.emplace_back(b);
120 }
121 if(!goods_.empty()) {
122 // use_kdt_ = use_kdt_;
123 this->buildKDTree();
124 } else {
125 use_kdt_ = false;
126 }
127 }
128
129 void BuildAuctionDiagrams(const DiagramType &diagram1,
130 const DiagramType &diagram2) {
131 n_bidders_ = diagram1.size();
132 n_goods_ = diagram2.size();
133 this->setBidders(diagram1);
134 this->setGoods(diagram2);
135 for(int i = 0; i < n_bidders_; i++) {
136 // Add diagonal goods
137 Bidder &b = bidders_[i];
138 Good g{b.x_, b.y_, true, -b.id_ - 1};
139 g.projectOnDiagonal();
140 diagonal_goods_.emplace_back(g);
141 std::pair<int, double> pair = std::make_pair(i, g.getPrice());
142 diagonal_queue_.push(pair);
143 }
144 for(int i = 0; i < n_goods_; i++) {
145 // Add diagonal bidders
146 Good &g = goods_[i];
147 Bidder b{g.x_, g.y_, true, -g.id_ - 1};
148 b.projectOnDiagonal();
149 b.setPositionInAuction(bidders_.size());
150 bidders_.emplace_back(b);
151 }
152 if(!bidders_.empty()) {
153 use_kdt_ = true;
154 this->buildKDTree();
155 } else {
156 use_kdt_ = false;
157 }
158 }
159
160 void setBidders(const DiagramType &diagram1) {
161 for(size_t i = 0; i < diagram1.size(); i++) {
162 // Add bidder to bidders
163 Bidder b{diagram1[i], static_cast<int>(i), lambda_};
164 b.setPositionInAuction(bidders_.size());
165 bidders_.emplace_back(b);
166 }
167 n_bidders_ = bidders_.size();
168 }
169
170 void setGoods(const DiagramType &diagram2) {
171 for(size_t i = 0; i < diagram2.size(); i++) {
172 // Add bidder to bidders
173 Good g{diagram2[i], static_cast<int>(i), lambda_};
174 goods_.emplace_back(g);
175 }
176 n_goods_ = goods_.size();
177 }
178
179 void buildKDTree() {
180 Timer t;
182 const int dimension
183 = geometricalFactor_ >= 1 ? (geometricalFactor_ <= 0 ? 3 : 2) : 5;
184 std::vector<double> coordinates;
185 for(size_t i = 0; i < goods_.size(); i++) {
186 Good &g = goods_[i];
187 if(geometricalFactor_ > 0) {
188 coordinates.push_back(geometricalFactor_ * g.x_);
189 coordinates.push_back(geometricalFactor_ * g.y_);
190 }
191 if(geometricalFactor_ < 1) {
192 coordinates.push_back((1 - geometricalFactor_) * g.coords_[0]);
193 coordinates.push_back((1 - geometricalFactor_) * g.coords_[1]);
194 coordinates.push_back((1 - geometricalFactor_) * g.coords_[2]);
195 }
196 }
198 = kdt_.build(coordinates.data(), goods_.size(), dimension);
199 }
200
201 void setEpsilon(const double epsilon) {
202 epsilon_ = epsilon;
203 }
204
206 double max_persistence = 0;
207 for(const auto &b : this->bidders_) {
208 double persistence = b.getPersistence();
209 if(persistence > max_persistence) {
210 max_persistence = persistence;
211 }
212 }
213 for(const auto &g : this->goods_) {
214 double persistence = g.getPersistence();
215 if(persistence > max_persistence) {
216 max_persistence = persistence;
217 }
218 }
219 this->epsilon_ = 5.0 / 4 * Geometry::pow(max_persistence, wasserstein_);
220 }
221
223 for(size_t i = 0; i < bidders_.size(); i++) {
224 Bidder &b = bidders_[i];
225 b.resetProperty();
226 unassignedBidders_.push(i);
227 }
228 }
229
231 for(auto &g : this->goods_) {
232 g.setOwner(-1);
233 }
234 for(auto &g : this->diagonal_goods_) {
235 g.setOwner(-1);
236 }
237 }
238
240 double d = 0;
241 for(size_t i = 0; i < bidders_.size(); i++) {
242 Bidder &b = bidders_[i];
244 }
245 return d;
246 }
247
249 double d = this->getMatchingDistance();
250 if(d < 1e-6 or d <= (lowerBoundCost_ * lowerBoundCostWeight_)) {
251 return 0;
252 }
253 double denominator = d - bidders_.size() * epsilon_;
254 if(denominator <= 0) {
255 return 1;
256 } else {
257 return Geometry::pow(d / denominator, 1 / ((float)wasserstein_)) - 1;
258 }
259 }
260
262 for(size_t i = 0; i < diagonal_goods_.size(); i++) {
263 Bidder &b = bidders_[i];
264 b.setDiagonalPrice(diagonal_goods_[i].getPrice());
265 }
266 }
267
269 if(diagonal_goods_.empty()) {
270 return 0;
271 }
272 double min_price = std::numeric_limits<double>::max();
273 for(size_t i = 0; i < diagonal_goods_.size(); i++) {
274 double price = diagonal_goods_[i].getPrice();
275 if(price < min_price) {
276 min_price = price;
277 }
278 }
279 return min_price;
280 }
281
282 protected:
283 int wasserstein_{2}; // Power in Wassertsein distance (by default set to 2)
289 std::priority_queue<std::pair<int, double>,
290 std::vector<std::pair<int, double>>,
291 Compare>
293 std::queue<int> unassignedBidders_{};
294
296 int n_goods_{0};
297
298 double epsilon_{1};
300 double lambda_{};
301 // lambda : 0<=lambda<=1
302 // parametrizes the point used for the physical (critical) coordinates of
303 // the persistence paired lambda = 1 : extremum (min if pair min-sad, max if
304 // pair sad-max) lambda = 0 : saddle (bad stability) lambda = 1/2 : middle
305 // of the 2 critical points of the pair
306 double delta_lim_{};
308 bool use_kdt_{true};
309
310 }; // namespace ttk
311} // namespace ttk
void setDiagonalPrice(const double price)
KDTree< double, std::array< double, 5 > > KDT
const Good & getProperty() const
Minimalist debugging class.
Definition: Debug.h:88
TTK KD-Tree.
Definition: KDTree.h:21
KDTreeMap build(dataType *data, const int &ptNumber, const int &dimension, const std::vector< std::vector< dataType > > &weights={}, const int weight_number=1)
Definition: KDTree.h:144
double cost(const PersistenceDiagramAuctionActor &g, const int wasserstein, const double geometricalFactor) const
void runAuctionRound(int &n_biddings, const int kdt_index=0)
std::vector< KDT * > & correspondence_kdt_map_
std::priority_queue< std::pair< int, double >, std::vector< std::pair< int, double > >, Compare > diagonal_queue_
void setEpsilon(const double epsilon)
void BuildAuctionDiagrams(const DiagramType &diagram1, const DiagramType &diagram2)
double initLowerBoundCost(const int kdt_index=0)
double getMatchingsAndDistance(std::vector< MatchingType > &matchings, bool get_diagonal_matches=false)
PersistenceDiagramAuction(BidderDiagram &bidders, GoodDiagram &goods, int wasserstein, double geometricalFactor, double lambda, double delta_lim, KDT &kdt, std::vector< KDT * > &correspondence_kdt_map, double epsilon={}, double initial_diag_price={}, bool use_kdTree=true)
std::vector< KDT * > default_correspondence_kdt_map_
void BuildAuctionDiagrams(const BidderDiagram &BD, const GoodDiagram &GD)
void initLowerBoundCostWeight(double delta_lim)
PersistenceDiagramAuction(int wasserstein, double geometricalFactor, double lambda, double delta_lim, bool use_kdTree)
void setGoods(const DiagramType &diagram2)
void setBidders(const DiagramType &diagram1)
T1 pow(const T1 val, const T2 n)
Definition: Geometry.h:411
The Topology ToolKit.
std::vector< Bidder > BidderDiagram
std::vector< PersistencePair > DiagramType
Persistence Diagram type as a vector of Persistence pairs.
std::vector< Good > GoodDiagram