25 std::vector<DiagramType> &final_centroids,
26 std::vector<std::vector<std::vector<std::vector<MatchingType>>>>
27 &all_matchings_per_type_and_cluster) {
29 all_matchings_per_type_and_cluster.resize(
k_);
30 for(
int c = 0; c <
k_; c++) {
31 all_matchings_per_type_and_cluster[c].resize(3);
32 for(
int i = 0; i < 3; i++) {
36 int matchings_only =
false;
46 matchings_only =
true;
51 std::vector<bool *> current_prec;
56 std::vector<bool *> current_dos;
57 current_dos.emplace_back(&
do_min_);
58 current_dos.emplace_back(&
do_sad_);
59 current_dos.emplace_back(&
do_max_);
60 bool converged =
false;
61 std::vector<bool> diagrams_complete(3);
62 for(
int c = 0; c < 3; c++) {
66 double total_time = 0;
70 cost_ = std::numeric_limits<double>::max();
71 double min_cost_min = std::numeric_limits<double>::max();
72 double min_cost_max = std::numeric_limits<double>::max();
73 double min_cost_sad = std::numeric_limits<double>::max();
75 double last_min_cost_obtained_min = -1;
76 double last_min_cost_obtained_sad = -1;
77 double last_min_cost_obtained_max = -1;
78 std::vector<double> epsilon0(3);
79 std::vector<double> epsilon_candidate(3);
80 std::vector<double> rho(3);
83 std::vector<double> max_persistence(3);
84 std::vector<double> lowest_persistence(3);
85 std::vector<double> min_persistence(3);
87 const auto square = [](
const double a) {
return a * a; };
89 for(
int i_crit = 0; i_crit < 3; i_crit++) {
92 min_persistence[i_crit] = 0;
93 epsilon_[i_crit] = square(0.5 * max_persistence[i_crit])
99 std::vector<int> min_points_to_add(3);
100 min_points_to_add[0] = 10;
101 min_points_to_add[1] = 10;
102 min_points_to_add[2] = 10;
106 min_points_to_add[0] = std::numeric_limits<int>::max();
107 min_points_to_add[1] = std::numeric_limits<int>::max();
108 min_points_to_add[2] = std::numeric_limits<int>::max();
110 std::vector<std::vector<double>> min_diag_price(3);
111 std::vector<std::vector<double>> min_off_diag_price(3);
112 for(
int c = 0; c < 3; ++c) {
114 min_diag_price[c].emplace_back(0);
115 min_off_diag_price[c].emplace_back(0);
119 max_persistence, min_persistence, min_diag_price, min_off_diag_price,
120 min_points_to_add,
false,
true);
122 for(
int c = 0; c < 3; c++) {
123 if(min_persistence[c] <= lowest_persistence[c]) {
124 diagrams_complete[c] =
true;
127 bool all_diagrams_complete
128 = diagrams_complete[0] && diagrams_complete[1] && diagrams_complete[2];
129 if(all_diagrams_complete) {
158 for(
int i_crit = 0; i_crit < 3; i_crit++) {
159 if(*(current_dos[i_crit])) {
160 rho[i_crit] = min_persistence[i_crit] > 0
172 for(
int i_crit = 0; i_crit < 3; i_crit++) {
173 if(*(current_dos[i_crit])) {
174 epsilon_candidate[i_crit] = square(min_persistence[i_crit]) / 8.;
175 if(epsilon_candidate[i_crit] >
epsilon_[i_crit]) {
178 epsilon_[i_crit] = epsilon_candidate[i_crit];
186 min_persistence[0] = 0;
187 min_points_to_add[0] = std::numeric_limits<int>::max();
192 min_persistence[1] = 0;
193 min_points_to_add[1] = std::numeric_limits<int>::max();
198 min_persistence[2] = 0;
199 min_points_to_add[2] = std::numeric_limits<int>::max();
204 min_persistence, rho, min_diag_price, min_off_diag_price,
205 min_points_to_add,
true,
false);
209 for(
int i_crit = 0; i_crit < 3; i_crit++) {
210 if(*(current_dos[i_crit])) {
211 if(min_persistence[i_crit] <= lowest_persistence[i_crit]) {
212 diagrams_complete[i_crit] =
true;
217 if(diagrams_complete[0] && diagrams_complete[1]
218 && diagrams_complete[2]) {
220 all_diagrams_complete =
true;
226 &min_off_diag_price, &min_diag_price,
227 all_matchings_per_type_and_cluster, matchings_only);
238 for(
int i_crit = 0; i_crit < 3; i_crit++) {
239 if(*(current_dos[i_crit]) ) {
240 epsilon_candidate[i_crit] = std::min(
241 std::max(max_shift_vec[i_crit] / 8.,
epsilon_[i_crit] / 5.),
244 if((epsilon_candidate[i_crit] <
epsilon_[i_crit]
245 && !diagrams_complete[i_crit])
246 || diagrams_complete[i_crit]) {
247 epsilon_[i_crit] = epsilon_candidate[i_crit];
255 this->
printMsg(
"[min barycenter] epsilon under minimal value ",
259 diagrams_complete[0] =
true;
262 this->
printMsg(
"[sad barycenter] epsilon under minimal value ",
266 diagrams_complete[1] =
true;
269 this->
printWrn(
"[max barycenter] epsilon under minimal value ");
272 diagrams_complete[2] =
true;
275 if(diagrams_complete[0] && diagrams_complete[1]
276 && diagrams_complete[2]) {
278 all_diagrams_complete =
true;
308 if(cost_min_ < min_cost_min && n_iterations_ > 2
309 && diagrams_complete[0] ) {
311 last_min_cost_obtained_min = 0;
313 last_min_cost_obtained_min += 1;
314 if(last_min_cost_obtained_min > 1) {
319 if(cost_sad_ < min_cost_sad && n_iterations_ > 2
320 && diagrams_complete[1] ) {
322 last_min_cost_obtained_sad = 0;
324 last_min_cost_obtained_sad += 1;
325 if(last_min_cost_obtained_sad > 1 && diagrams_complete[1]) {
330 if(cost_max_ < min_cost_max && n_iterations_ > 2
331 && diagrams_complete[2] ) {
333 last_min_cost_obtained_max = 0;
335 last_min_cost_obtained_max += 1;
336 if(last_min_cost_obtained_max > 1 && diagrams_complete[2]) {
345 converged = converged
347 && !
do_max_ && (precision_criterion_reached))
362 all_diagrams_complete =
true;
363 diagrams_complete[0] =
true;
364 diagrams_complete[1] =
true;
365 diagrams_complete[2] =
true;
370 <<
" == complete : " << all_diagrams_complete
372 <<
" , converged : " << converged << std::endl;
378 std::vector<std::vector<std::string>>
const rows{
382 {matchings_only ?
"Wasserstein Distance" :
"Final Cost",
393 this->
printMsg(
"Clustering result:");
406 final_centroids.resize(
k_);
408 for(
int c = 0; c <
k_; c++) {
418 for(
int c = 0; c <
k_; ++c) {
422 int const removeFirstPairMin
424 int addedFirstPairMax = 0;
425 int addedFirstPairMin = removeFirstPairMin;
435 addedFirstPairMax = 1;
443 addedFirstPairMin = 1;
447 for(
size_t i = addedFirstPairMin; i <
centroids_min_[c].size(); ++i) {
454 this->
printMsg(
"Found a abnormally high persistence in min diagram",
468 this->
printMsg(
"Found a abnormally high persistence in sad diagram",
475 for(
size_t i = addedFirstPairMax; i <
centroids_max_[c].size(); ++i) {
490 this->
printMsg(
"Found a abnormally high persistence in min diagram",
507 std::vector<std::vector<std::vector<std::vector<MatchingType>>>>
508 &previous_matchings) {
509 for(
int c = 0; c < k_; c++) {
510 for(
size_t i = 0; i < clustering_[c].size(); i++) {
511 int const diagram_id = clustering_[c][i];
512 if(original_dos[0]) {
514 std::vector<int> new_to_old_id(
515 current_bidder_diagrams_min_[diagram_id].size(), -1);
516 for(
size_t j = 0; j < current_bidder_ids_min_[diagram_id].size(); j++) {
517 int const new_id = current_bidder_ids_min_[diagram_id][j];
519 new_to_old_id[new_id] = j;
523 std::vector<MatchingType> matchings_diagram_i;
524 for(
size_t j = 0; j < previous_matchings[c][0][i].size(); j++) {
526 int const new_id = std::get<0>(m);
527 if(new_id >= 0 && std::get<1>(m) >= 0) {
528 std::get<0>(m) = new_to_old_id[new_id];
529 matchings_diagram_i.emplace_back(m);
530 }
else if(std::get<1>(m)
533 matchings_diagram_i.emplace_back(m);
536 previous_matchings[c][0][i].resize(matchings_diagram_i.size());
537 previous_matchings[c][0][i] = matchings_diagram_i;
539 if(original_dos[1]) {
541 std::vector<int> new_to_old_id(
542 current_bidder_diagrams_saddle_[diagram_id].size());
543 for(
size_t j = 0; j < current_bidder_ids_sad_[diagram_id].size(); j++) {
544 int const new_id = current_bidder_ids_sad_[diagram_id][j];
546 new_to_old_id[new_id] = j;
551 std::vector<MatchingType> matchings_diagram_i;
552 for(
size_t j = 0; j < previous_matchings[c][1][i].size(); j++) {
554 int const new_id = std::get<0>(m);
555 if(new_id >= 0 && std::get<1>(m) >= 0) {
556 int const old_id = new_to_old_id[new_id];
558 std::get<0>(m) = old_id;
559 matchings_diagram_i.emplace_back(m);
563 std::get<0>(m) = old_id;
564 matchings_diagram_i.emplace_back(m);
567 }
else if(std::get<1>(m)
570 matchings_diagram_i.emplace_back(m);
573 previous_matchings[c][1][i].resize(matchings_diagram_i.size());
574 previous_matchings[c][1][i] = matchings_diagram_i;
576 if(original_dos[2]) {
578 std::vector<int> new_to_old_id(
579 current_bidder_diagrams_max_[diagram_id].size());
580 for(
size_t j = 0; j < current_bidder_ids_max_[diagram_id].size(); j++) {
581 int const new_id = current_bidder_ids_max_[diagram_id][j];
583 new_to_old_id[new_id] = j;
588 std::vector<MatchingType> matchings_diagram_i;
589 for(
size_t j = 0; j < previous_matchings[c][2][i].size(); j++) {
591 int const new_id = std::get<0>(m);
592 if(new_id >= 0 && std::get<1>(m) >= 0) {
593 int const old_id = new_to_old_id[new_id];
595 std::get<0>(m) = old_id;
596 matchings_diagram_i.emplace_back(m);
600 std::get<0>(m) = old_id;
601 matchings_diagram_i.emplace_back(m);
604 }
else if(std::get<1>(m)
607 matchings_diagram_i.emplace_back(m);
610 previous_matchings[c][2][i].resize(matchings_diagram_i.size());
611 previous_matchings[c][2][i] = matchings_diagram_i;
946 std::vector<int> indexes_clusters;
947 int const random_idx = deterministic_ ? 0 : rand() % numberOfInputs_;
948 indexes_clusters.emplace_back(random_idx);
952 = diagramToCentroid(current_bidder_diagrams_min_[random_idx]);
953 centroids_min_.emplace_back(centroid_min);
957 = diagramToCentroid(current_bidder_diagrams_saddle_[random_idx]);
958 centroids_saddle_.emplace_back(centroid_sad);
962 = diagramToCentroid(current_bidder_diagrams_max_[random_idx]);
963 centroids_max_.emplace_back(centroid_max);
966 const auto square = [](
const double a) {
return a * a; };
968 while((
int)indexes_clusters.size() < k_) {
969 std::vector<double> min_distance_to_centroid(numberOfInputs_);
970 std::vector<double> probabilities(numberOfInputs_);
973 double maximal_distance = 0;
974 int candidate_centroid = 0;
976 for(
int i = 0; i < numberOfInputs_; i++) {
978 min_distance_to_centroid[i] = std::numeric_limits<double>::max();
979 if(std::find(indexes_clusters.begin(), indexes_clusters.end(), i)
980 != indexes_clusters.end()) {
982 min_distance_to_centroid[i] = 0;
985 for(
size_t j = 0; j < indexes_clusters.size(); ++j) {
990 = centroidWithZeroPrices(centroids_min_[j]);
991 distance += computeDistance(
992 current_bidder_diagrams_min_[i], centroid_min, 0.01);
996 = centroidWithZeroPrices(centroids_saddle_[j]);
997 distance += computeDistance(
998 current_bidder_diagrams_saddle_[i], centroid_saddle, 0.01);
1002 = centroidWithZeroPrices(centroids_max_[j]);
1003 distance += computeDistance(
1004 current_bidder_diagrams_max_[i], centroid_max, 0.01);
1006 if(distance < min_distance_to_centroid[i]) {
1007 min_distance_to_centroid[i] = distance;
1011 probabilities[i] = square(min_distance_to_centroid[i]);
1015 if(deterministic_ && min_distance_to_centroid[i] > maximal_distance) {
1016 maximal_distance = min_distance_to_centroid[i];
1017 candidate_centroid = i;
1021 std::random_device rd;
1022 std::mt19937 gen(rd());
1023 std::discrete_distribution<int> distribution(
1024 probabilities.begin(), probabilities.end());
1026 if(!deterministic_) {
1027 candidate_centroid = distribution(gen);
1030 indexes_clusters.emplace_back(candidate_centroid);
1033 = diagramToCentroid(current_bidder_diagrams_min_[candidate_centroid]);
1034 centroids_min_.emplace_back(centroid_min);
1037 GoodDiagram const centroid_sad = diagramToCentroid(
1038 current_bidder_diagrams_saddle_[candidate_centroid]);
1039 centroids_saddle_.emplace_back(centroid_sad);
1043 = diagramToCentroid(current_bidder_diagrams_max_[candidate_centroid]);
1044 centroids_max_.emplace_back(centroid_max);
1282 getCentroidDistanceMatrix();
1283 old_clustering_ = clustering_;
1286 initializeEmptyClusters();
1287 bool const do_min = original_dos[0];
1288 bool const do_sad = original_dos[1];
1289 bool const do_max = original_dos[2];
1291 for(
int i = 0; i < numberOfInputs_; ++i) {
1295 D1_min = diagramWithZeroPrices(current_bidder_diagrams_min_[i]);
1298 D1_sad = diagramWithZeroPrices(current_bidder_diagrams_saddle_[i]);
1301 D1_max = diagramWithZeroPrices(current_bidder_diagrams_max_[i]);
1304 for(
int c = 0; c < k_; ++c) {
1305 if(inv_clustering_[i] == -1) {
1308 if(deterministic_) {
1309 inv_clustering_[i] = i % k_;
1311 std::cout <<
" - ASSIGNED TO A RANDOM CLUSTER " <<
'\n';
1312 inv_clustering_[i] = rand() % (k_);
1317 centroids_with_price_min_[i]
1318 = centroidWithZeroPrices(centroids_min_[inv_clustering_[i]]);
1321 centroids_with_price_saddle_[i]
1322 = centroidWithZeroPrices(centroids_saddle_[inv_clustering_[i]]);
1325 centroids_with_price_max_[i]
1326 = centroidWithZeroPrices(centroids_max_[inv_clustering_[i]]);
1330 if(c != inv_clustering_[i] && u_[i] > l_[i][c]
1331 && u_[i] > 0.5 * centroidsDistanceMatrix_[inv_clustering_[i]][c]) {
1334 double distance = 0;
1335 GoodDiagram centroid_min, centroid_sad, centroid_max;
1338 = centroidWithZeroPrices(centroids_min_[inv_clustering_[i]]);
1339 distance += computeDistance(D1_min, centroid_min, 0.01);
1343 = centroidWithZeroPrices(centroids_saddle_[inv_clustering_[i]]);
1344 distance += computeDistance(D1_sad, centroid_sad, 0.01);
1348 = centroidWithZeroPrices(centroids_max_[inv_clustering_[i]]);
1349 distance += computeDistance(D1_max, centroid_max, 0.01);
1353 l_[i][inv_clustering_[i]] = distance;
1356 if((n_iterations_ > 2 || n_iterations_ < 1)
1357 && (u_[i] > l_[i][c]
1359 > 0.5 * centroidsDistanceMatrix_[inv_clustering_[i]][c])) {
1361 GoodDiagram centroid_min, centroid_sad, centroid_max;
1362 double distance = 0;
1365 centroid_min = centroidWithZeroPrices(centroids_min_[c]);
1367 = diagramWithZeroPrices(current_bidder_diagrams_min_[i]);
1368 distance += computeDistance(diagram_min, centroid_min, 0.01);
1371 centroid_sad = centroidWithZeroPrices(centroids_saddle_[c]);
1373 = diagramWithZeroPrices(current_bidder_diagrams_saddle_[i]);
1374 distance += computeDistance(diagram_sad, centroid_sad, 0.01);
1377 centroid_max = centroidWithZeroPrices(centroids_max_[c]);
1379 = diagramWithZeroPrices(current_bidder_diagrams_max_[i]);
1380 distance += computeDistance(diagram_max, centroid_max, 0.01);
1382 l_[i][c] = distance;
1385 if(distance < u_[i]) {
1387 resetDosToOriginalValues();
1388 barycenter_inputs_reset_flag =
true;
1390 inv_clustering_[i] = c;
1393 centroids_with_price_min_[i]
1394 = centroidWithZeroPrices(centroids_min_[c]);
1397 centroids_with_price_saddle_[i]
1398 = centroidWithZeroPrices(centroids_saddle_[c]);
1401 centroids_with_price_max_[i]
1402 = centroidWithZeroPrices(centroids_max_[c]);
1409 invertInverseClusters();
1410 for(
int c = 0; c < k_; ++c) {
1411 if(clustering_[c].empty()) {
1412 std::cout <<
"Adding artificial centroid because a cluster was empty"
1414 bool idx_acceptable =
false;
1417 std::vector<double> copy_of_u(u_.size());
1419 while(!idx_acceptable) {
1420 auto argMax = std::max_element(copy_of_u.begin(), copy_of_u.end());
1421 idx = std::distance(copy_of_u.begin(), argMax);
1422 if(inv_clustering_[idx] < k_ && inv_clustering_[idx] >= 0
1423 && clustering_[inv_clustering_[idx]].size() > 1) {
1424 idx_acceptable =
true;
1425 int const cluster_removal = inv_clustering_[idx];
1427 clustering_[cluster_removal].erase(
1428 std::remove(clustering_[cluster_removal].
begin(),
1429 clustering_[cluster_removal].
end(), idx),
1430 clustering_[cluster_removal].
end());
1432 if(copy_of_u.size() > (
size_t)idx) {
1433 copy_of_u.erase(argMax);
1435 idx_acceptable =
true;
1436 int cluster_max = 0;
1437 if(!clustering_[cluster_max].empty()) {
1438 idx = clustering_[cluster_max][0];
1440 for(
int i_test = 1; i_test < k_; i_test++) {
1441 if(clustering_[i_test].size() > clustering_[cluster_max].size()) {
1442 cluster_max = i_test;
1443 idx = clustering_[cluster_max][0];
1446 int const cluster_removal = inv_clustering_[idx];
1447 clustering_[cluster_removal].erase(
1448 std::remove(clustering_[cluster_removal].
begin(),
1449 clustering_[cluster_removal].
end(), idx),
1450 clustering_[cluster_removal].
end());
1455 clustering_[c].emplace_back(idx);
1456 inv_clustering_[idx] = c;
1460 = diagramToCentroid(current_bidder_diagrams_min_[idx]);
1461 centroids_with_price_min_[idx]
1462 = centroidWithZeroPrices(centroids_min_[c]);
1465 centroids_saddle_[c]
1466 = diagramToCentroid(current_bidder_diagrams_saddle_[idx]);
1467 centroids_with_price_saddle_[idx]
1468 = centroidWithZeroPrices(centroids_saddle_[c]);
1472 = diagramToCentroid(current_bidder_diagrams_max_[idx]);
1473 centroids_with_price_max_[idx]
1474 = centroidWithZeroPrices(centroids_max_[c]);
1476 resetDosToOriginalValues();
1477 barycenter_inputs_reset_flag =
true;
1483 std::vector<std::vector<double>> *min_price,
1484 std::vector<std::vector<double>> *min_diag_price,
1485 std::vector<std::vector<std::vector<std::vector<MatchingType>>>>
1486 &all_matchings_per_type_and_cluster,
1487 int only_matchings) {
1488 barycenter_inputs_reset_flag =
true;
1489 std::vector<double> max_shift_vector(3);
1490 max_shift_vector[0] = 0;
1491 max_shift_vector[1] = 0;
1492 max_shift_vector[2] = 0;
1493 double max_shift_c_min = 0;
1494 double max_shift_c_sad = 0;
1495 double max_shift_c_max = 0;
1496 double max_wasserstein_shift = 0;
1497 bool precision_min =
true;
1498 bool precision_sad =
true;
1499 bool precision_max =
true;
1501 double const sq_dist_min = cost_min_;
1502 double const sq_dist_sad = cost_sad_;
1503 double const sq_dist_max = cost_max_;
1514 for(
int c = 0; c < k_; ++c) {
1515 if(!clustering_[c].empty()) {
1516 std::vector<GoodDiagram> centroids_with_price_min,
1517 centroids_with_price_sad, centroids_with_price_max;
1519 for(
int const idx : clustering_[c]) {
1522 std::vector<int>::iterator
const i = std::find(
1523 old_clustering_[c].
begin(), old_clustering_[c].
end(), idx);
1524 int const pos = (i == old_clustering_[c].end())
1526 : std::distance(old_clustering_[c].
begin(), i);
1530 centroids_with_price_min.emplace_back(
1531 centroids_with_price_min_[idx]);
1534 centroids_with_price_sad.emplace_back(
1535 centroids_with_price_saddle_[idx]);
1538 centroids_with_price_max.emplace_back(
1539 centroids_with_price_max_[idx]);
1542 int number_of_points_min = 0;
1543 int number_of_points_max = 0;
1544 int number_of_points_sad = 0;
1549 centroids_with_price_min.emplace_back(
1550 centroidWithZeroPrices(centroids_min_[c]));
1551 current_bidder_diagrams_min_[idx]
1552 = diagramWithZeroPrices(current_bidder_diagrams_min_[idx]);
1553 number_of_points_min += centroids_with_price_min_[idx].size()
1554 + current_bidder_diagrams_min_[idx].size();
1557 centroids_with_price_sad.emplace_back(
1558 centroidWithZeroPrices(centroids_saddle_[c]));
1559 current_bidder_diagrams_saddle_[idx]
1560 = diagramWithZeroPrices(current_bidder_diagrams_saddle_[idx]);
1561 number_of_points_sad
1562 += centroids_with_price_saddle_[idx].size()
1563 + current_bidder_diagrams_saddle_[idx].size();
1566 centroids_with_price_max.emplace_back(
1567 centroidWithZeroPrices(centroids_max_[c]));
1568 current_bidder_diagrams_max_[idx]
1569 = diagramWithZeroPrices(current_bidder_diagrams_max_[idx]);
1570 number_of_points_max += centroids_with_price_max_[idx].size()
1571 + current_bidder_diagrams_max_[idx].size();
1574 if(n_iterations_ > 1) {
1585 double estimated_delta_lim
1587 / sqrt(1 - number_of_points_min * epsilon_[0] / sq_dist_min)
1589 if(estimated_delta_lim > 1) {
1590 estimated_delta_lim = 1;
1592 computeDistance(&(current_bidder_diagrams_min_[idx]),
1593 &(centroids_with_price_min[count]),
1594 estimated_delta_lim);
1599 double estimated_delta_lim
1601 / sqrt(1 - number_of_points_sad * epsilon_[1] / sq_dist_sad)
1603 if(estimated_delta_lim > 1) {
1604 estimated_delta_lim = 1;
1606 computeDistance(&(current_bidder_diagrams_saddle_[idx]),
1607 &(centroids_with_price_sad[count]),
1608 estimated_delta_lim);
1613 double estimated_delta_lim
1615 / sqrt(1 - number_of_points_max * epsilon_[2] / sq_dist_max)
1617 if(estimated_delta_lim > 1) {
1618 estimated_delta_lim = 1;
1620 computeDistance(&(current_bidder_diagrams_max_[idx]),
1621 &(centroids_with_price_max[count]),
1622 estimated_delta_lim);
1628 double total_cost = 0;
1629 double wasserstein_shift = 0;
1634 std::vector<std::vector<MatchingType>> all_matchings;
1635 std::vector<int> sizes;
1636 Timer const time_preprocess_bary;
1637 std::vector<BidderDiagram> diagrams_c_min;
1638 if(barycenter_inputs_reset_flag) {
1639 for(
int const idx : clustering_[c]) {
1640 diagrams_c_min.emplace_back(current_bidder_diagrams_min_[idx]);
1642 sizes.resize(diagrams_c_min.size());
1643 for(
size_t i = 0; i < diagrams_c_min.size(); i++) {
1644 sizes[i] = diagrams_c_min[i].size();
1646 barycenter_computer_min_[c].setNumberOfInputs(diagrams_c_min.size());
1647 barycenter_computer_min_[c].setCurrentBidders(diagrams_c_min);
1649 std::vector<GoodDiagram> barycenter_goods(clustering_[c].size());
1650 for(
size_t i_diagram = 0; i_diagram < clustering_[c].size();
1652 barycenter_goods[i_diagram]
1653 = centroids_with_price_min_[clustering_[c][i_diagram]];
1655 barycenter_computer_min_[c].setCurrentBarycenter(barycenter_goods);
1656 all_matchings.resize(diagrams_c_min.size());
1658 sizes.resize(barycenter_computer_min_[c].getCurrentBidders().size());
1660 i < barycenter_computer_min_[c].getCurrentBidders().size(); i++) {
1662 = barycenter_computer_min_[c].getCurrentBidders().at(i).size();
1664 diagrams_c_min.resize(
1665 barycenter_computer_min_[c].getCurrentBidders().size());
1666 all_matchings.resize(
1667 barycenter_computer_min_[c].getCurrentBidders().size());
1671 bool use_kdt =
false;
1672 if(!barycenter_computer_min_[c].getCurrentBarycenter()[0].empty()) {
1673 pair = barycenter_computer_min_[c].getKDTree();
1677 barycenter_computer_min_[c].runMatching(
1678 &total_cost, epsilon_[0], sizes, *pair.first, pair.second,
1679 &(min_diag_price->at(0)), &(min_price->at(0)), &(all_matchings),
1680 use_kdt, only_matchings);
1681 for(
size_t ii = 0; ii < all_matchings.size(); ii++) {
1682 all_matchings_per_type_and_cluster[c][0][ii].resize(
1683 all_matchings[ii].size());
1684 all_matchings_per_type_and_cluster[c][0][ii] = all_matchings[ii];
1686 for(
int ii = all_matchings.size(); ii < numberOfInputs_; ii++) {
1687 all_matchings_per_type_and_cluster[c][0][ii].resize(0);
1691 = barycenter_computer_min_[c].isPrecisionObjectiveMet(deltaLim_, 0);
1692 cost_min_ += total_cost;
1693 Timer const time_update;
1694 if(!only_matchings) {
1696 = barycenter_computer_min_[c].updateBarycenter(all_matchings);
1699 if(max_shift_c_min > max_shift_vector[0]) {
1700 max_shift_vector[0] = max_shift_c_min;
1705 diagrams_c_min = barycenter_computer_min_[c].getCurrentBidders();
1706 centroids_with_price_min
1707 = barycenter_computer_min_[c].getCurrentBarycenter();
1709 for(
int const idx : clustering_[c]) {
1710 current_bidder_diagrams_min_[idx] = diagrams_c_min[i];
1711 centroids_with_price_min_[idx] = centroids_with_price_min[i];
1715 GoodDiagram const old_centroid = centroids_min_[c];
1716 centroids_min_[c] = centroidWithZeroPrices(
1717 centroids_with_price_min_[clustering_[c][0]]);
1719 if(use_accelerated_) {
1721 += computeDistance(old_centroid, centroids_min_[c], 0.01);
1726 std::vector<std::vector<MatchingType>> all_matchings;
1728 std::vector<int> sizes;
1730 std::vector<BidderDiagram> diagrams_c_min;
1731 if(barycenter_inputs_reset_flag) {
1732 for(
int const idx : clustering_[c]) {
1733 diagrams_c_min.emplace_back(current_bidder_diagrams_saddle_[idx]);
1735 sizes.resize(diagrams_c_min.size());
1736 for(
size_t i = 0; i < diagrams_c_min.size(); i++) {
1737 sizes[i] = diagrams_c_min[i].size();
1739 barycenter_computer_sad_[c].setNumberOfInputs(diagrams_c_min.size());
1740 barycenter_computer_sad_[c].setCurrentBidders(diagrams_c_min);
1741 std::vector<GoodDiagram> barycenter_goods(clustering_[c].size());
1742 for(
size_t i_diagram = 0; i_diagram < clustering_[c].size();
1744 barycenter_goods[i_diagram]
1745 = centroids_with_price_saddle_[clustering_[c][i_diagram]];
1747 barycenter_computer_sad_[c].setCurrentBarycenter(barycenter_goods);
1748 all_matchings.resize(diagrams_c_min.size());
1750 sizes.resize(barycenter_computer_sad_[c].getCurrentBidders().size());
1752 i < barycenter_computer_sad_[c].getCurrentBidders().size(); i++) {
1754 = barycenter_computer_sad_[c].getCurrentBidders().at(i).size();
1756 all_matchings.resize(
1757 barycenter_computer_sad_[c].getCurrentBidders().size());
1758 diagrams_c_min.resize(
1759 barycenter_computer_sad_[c].getCurrentBidders().size());
1763 bool use_kdt =
false;
1764 if(!barycenter_computer_sad_[c].getCurrentBarycenter()[0].empty()) {
1765 pair = barycenter_computer_sad_[c].getKDTree();
1769 barycenter_computer_sad_[c].runMatching(
1770 &total_cost, epsilon_[1], sizes, *pair.first, pair.second,
1771 &(min_diag_price->at(1)), &(min_price->at(1)), &(all_matchings),
1772 use_kdt, only_matchings);
1773 for(
size_t ii = 0; ii < all_matchings.size(); ii++) {
1774 all_matchings_per_type_and_cluster[c][1][ii].resize(
1775 all_matchings[ii].size());
1776 all_matchings_per_type_and_cluster[c][1][ii] = all_matchings[ii];
1778 for(
int ii = all_matchings.size(); ii < numberOfInputs_; ii++) {
1779 all_matchings_per_type_and_cluster[c][1][ii].resize(0);
1783 = barycenter_computer_sad_[c].isPrecisionObjectiveMet(deltaLim_, 0);
1784 if(!only_matchings) {
1786 = barycenter_computer_sad_[c].updateBarycenter(all_matchings);
1789 cost_sad_ += total_cost;
1791 if(max_shift_c_sad > max_shift_vector[1]) {
1792 max_shift_vector[1] = max_shift_c_sad;
1797 diagrams_c_min = barycenter_computer_sad_[c].getCurrentBidders();
1798 centroids_with_price_sad
1799 = barycenter_computer_sad_[c].getCurrentBarycenter();
1801 for(
int const idx : clustering_[c]) {
1802 current_bidder_diagrams_saddle_[idx] = diagrams_c_min[i];
1803 centroids_with_price_saddle_[idx] = centroids_with_price_sad[i];
1806 GoodDiagram const old_centroid = centroids_saddle_[c];
1807 centroids_saddle_[c] = centroidWithZeroPrices(
1808 centroids_with_price_saddle_[clustering_[c][0]]);
1809 if(use_accelerated_)
1811 += computeDistance(old_centroid, centroids_saddle_[c], 0.01);
1815 std::vector<std::vector<MatchingType>> all_matchings;
1816 Timer const time_preprocess_bary;
1818 std::vector<int> sizes;
1819 std::vector<BidderDiagram> diagrams_c_min;
1820 if(barycenter_inputs_reset_flag) {
1821 for(
int const idx : clustering_[c]) {
1822 diagrams_c_min.emplace_back(current_bidder_diagrams_max_[idx]);
1824 sizes.resize(diagrams_c_min.size());
1825 for(
size_t i = 0; i < diagrams_c_min.size(); i++) {
1826 sizes[i] = diagrams_c_min[i].size();
1828 barycenter_computer_max_[c].setNumberOfInputs(diagrams_c_min.size());
1829 barycenter_computer_max_[c].setCurrentBidders(diagrams_c_min);
1830 std::vector<GoodDiagram> barycenter_goods(clustering_[c].size());
1831 for(
size_t i_diagram = 0; i_diagram < clustering_[c].size();
1833 barycenter_goods[i_diagram]
1834 = centroids_with_price_max_[clustering_[c][i_diagram]];
1836 barycenter_computer_max_[c].setCurrentBarycenter(barycenter_goods);
1837 all_matchings.resize(diagrams_c_min.size());
1839 sizes.resize(barycenter_computer_max_[c].getCurrentBidders().size());
1841 i < barycenter_computer_max_[c].getCurrentBidders().size(); i++) {
1843 = barycenter_computer_max_[c].getCurrentBidders().at(i).size();
1846 diagrams_c_min.resize(
1847 barycenter_computer_max_[c].getCurrentBidders().size());
1848 all_matchings.resize(
1849 barycenter_computer_max_[c].getCurrentBidders().size());
1853 bool use_kdt =
false;
1854 if(!barycenter_computer_max_[c].getCurrentBarycenter()[0].empty()) {
1855 pair = barycenter_computer_max_[c].getKDTree();
1859 barycenter_computer_max_[c].runMatching(
1860 &total_cost, epsilon_[2], sizes, *pair.first, pair.second,
1861 &(min_diag_price->at(2)), &(min_price->at(2)), &(all_matchings),
1862 use_kdt, only_matchings);
1863 for(
size_t ii = 0; ii < all_matchings.size(); ii++) {
1864 all_matchings_per_type_and_cluster[c][2][ii].resize(
1865 all_matchings[ii].size());
1866 all_matchings_per_type_and_cluster[c][2][ii] = all_matchings[ii];
1868 for(
int ii = all_matchings.size(); ii < numberOfInputs_; ii++) {
1869 all_matchings_per_type_and_cluster[c][2][ii].resize(0);
1872 = barycenter_computer_max_[c].isPrecisionObjectiveMet(deltaLim_, 0);
1874 cost_max_ += total_cost;
1875 Timer const time_update;
1876 if(!only_matchings) {
1878 = barycenter_computer_max_[c].updateBarycenter(all_matchings);
1880 if(max_shift_c_max > max_shift_vector[2]) {
1881 max_shift_vector[2] = max_shift_c_max;
1886 diagrams_c_min = barycenter_computer_max_[c].getCurrentBidders();
1887 centroids_with_price_max
1888 = barycenter_computer_max_[c].getCurrentBarycenter();
1890 for(
int const idx : clustering_[c]) {
1891 current_bidder_diagrams_max_[idx] = diagrams_c_min[i];
1892 centroids_with_price_max_[idx] = centroids_with_price_max[i];
1895 GoodDiagram const old_centroid = centroids_max_[c];
1896 centroids_max_[c] = centroidWithZeroPrices(
1897 centroids_with_price_max_[clustering_[c][0]]);
1898 if(use_accelerated_) {
1900 += computeDistance(old_centroid, centroids_max_[c], 0.01);
1904 cost_ = cost_min_ + cost_sad_ + cost_max_;
1905 if(wasserstein_shift > max_wasserstein_shift) {
1906 max_wasserstein_shift = wasserstein_shift;
1908 if(use_accelerated_) {
1909 for(
int i = 0; i < numberOfInputs_; ++i) {
1920 for(
int const idx : clustering_[c]) {
1936 precision_min_ = precision_min;
1937 precision_sad_ = precision_sad;
1938 precision_max_ = precision_max;
1939 precision_criterion_ = precision_min && precision_sad && precision_max;
1940 barycenter_inputs_reset_flag =
false;
1941 return max_shift_vector;
2020 std::vector<double> &previous_min_persistence,
2021 std::vector<double> &min_persistence,
2022 std::vector<std::vector<double>> &initial_diagonal_prices,
2023 std::vector<std::vector<double>> &initial_off_diagonal_prices,
2024 std::vector<int> &min_points_to_add,
2025 bool add_points_to_barycenter,
2026 bool first_enrichment) {
2028 std::vector<double> new_min_persistence = min_persistence;
2031 new_min_persistence[0] = previous_min_persistence[0];
2034 new_min_persistence[1] = previous_min_persistence[1];
2037 new_min_persistence[2] = previous_min_persistence[2];
2042 size_t max_diagram_size_min{};
2043 size_t max_diagram_size_sad{};
2044 size_t max_diagram_size_max{};
2046 for(
int i = 0; i < numberOfInputs_; i++) {
2047 if(current_bidder_diagrams_min_[i].size() > max_diagram_size_min) {
2048 max_diagram_size_min = current_bidder_diagrams_min_[i].size();
2053 for(
int i = 0; i < numberOfInputs_; i++) {
2054 if(current_bidder_diagrams_saddle_[i].size() > max_diagram_size_sad) {
2055 max_diagram_size_sad = current_bidder_diagrams_saddle_[i].size();
2060 for(
int i = 0; i < numberOfInputs_; i++) {
2061 if(current_bidder_diagrams_max_[i].size() > max_diagram_size_max) {
2062 max_diagram_size_max = current_bidder_diagrams_max_[i].size();
2066 int const max_points_to_add_min
2067 = std::max(min_points_to_add[0],
2068 min_points_to_add[0] + (
int)(max_diagram_size_min / 10));
2069 int const max_points_to_add_sad
2070 = std::max(min_points_to_add[1],
2071 min_points_to_add[1] + (
int)(max_diagram_size_sad / 10));
2072 int const max_points_to_add_max
2073 = std::max(min_points_to_add[2],
2074 min_points_to_add[2] + (
int)(max_diagram_size_max / 10));
2077 std::vector<std::vector<int>> candidates_to_be_added_min(numberOfInputs_);
2078 std::vector<std::vector<int>> candidates_to_be_added_sad(numberOfInputs_);
2079 std::vector<std::vector<int>> candidates_to_be_added_max(numberOfInputs_);
2080 std::vector<std::vector<int>> idx_min(numberOfInputs_);
2081 std::vector<std::vector<int>> idx_sad(numberOfInputs_);
2082 std::vector<std::vector<int>> idx_max(numberOfInputs_);
2085 for(
int i = 0; i < numberOfInputs_; i++) {
2086 std::vector<double> persistences;
2087 for(
size_t j = 0; j < bidder_diagrams_min_[i].size(); j++) {
2088 Bidder const b = bidder_diagrams_min_[i].at(j);
2090 if(persistence >= min_persistence[0]
2091 && persistence <= previous_min_persistence[0]) {
2092 candidates_to_be_added_min[i].emplace_back(j);
2093 idx_min[i].emplace_back(idx_min[i].size());
2094 persistences.emplace_back(persistence);
2098 idx_min[i].
begin(), idx_min[i].
end(), [&persistences](
int &a,
int &b) {
2099 return ((persistences[a] > persistences[b])
2100 || ((persistences[a] == persistences[b]) && (a > b)));
2102 int const size = candidates_to_be_added_min[i].size();
2103 if(size >= max_points_to_add_min) {
2104 double const last_persistence_added_min
2105 = persistences[idx_min[i][max_points_to_add_min - 1]];
2106 if(first_enrichment) {
2109 new_min_persistence[0] = last_persistence_added_min;
2111 if(last_persistence_added_min < new_min_persistence[0])
2112 new_min_persistence[0] = last_persistence_added_min;
2115 if(last_persistence_added_min > new_min_persistence[0]) {
2116 new_min_persistence[0] = last_persistence_added_min;
2124 for(
int i = 0; i < numberOfInputs_; i++) {
2125 std::vector<double> persistences;
2126 for(
size_t j = 0; j < bidder_diagrams_saddle_[i].size(); j++) {
2127 Bidder const b = bidder_diagrams_saddle_[i].at(j);
2129 if(persistence >= min_persistence[1]
2130 && persistence <= previous_min_persistence[1]) {
2131 candidates_to_be_added_sad[i].emplace_back(j);
2132 idx_sad[i].emplace_back(idx_sad[i].size());
2133 persistences.emplace_back(persistence);
2137 idx_sad[i].
begin(), idx_sad[i].
end(), [&persistences](
int &a,
int &b) {
2138 return ((persistences[a] > persistences[b])
2139 || ((persistences[a] == persistences[b]) && (a > b)));
2141 int const size = candidates_to_be_added_sad[i].size();
2142 if(size >= max_points_to_add_sad) {
2143 double const last_persistence_added_sad
2144 = persistences[idx_sad[i][max_points_to_add_sad - 1]];
2145 if(first_enrichment) {
2148 new_min_persistence[1] = last_persistence_added_sad;
2150 if(last_persistence_added_sad < new_min_persistence[1])
2151 new_min_persistence[1] = last_persistence_added_sad;
2154 if(last_persistence_added_sad > new_min_persistence[1]) {
2155 new_min_persistence[1] = last_persistence_added_sad;
2162 for(
int i = 0; i < numberOfInputs_; i++) {
2163 std::vector<double> persistences;
2164 for(
size_t j = 0; j < bidder_diagrams_max_[i].size(); j++) {
2165 Bidder const b = bidder_diagrams_max_[i].at(j);
2167 if(persistence >= min_persistence[2]
2168 && persistence <= previous_min_persistence[2]) {
2169 candidates_to_be_added_max[i].emplace_back(j);
2170 idx_max[i].emplace_back(idx_max[i].size());
2171 persistences.emplace_back(persistence);
2175 idx_max[i].
begin(), idx_max[i].
end(), [&persistences](
int &a,
int &b) {
2176 return ((persistences[a] > persistences[b])
2177 || ((persistences[a] == persistences[b]) && (a > b)));
2179 int const size = candidates_to_be_added_max[i].size();
2180 if(size >= max_points_to_add_max) {
2181 double const last_persistence_added_max
2182 = persistences[idx_max[i][max_points_to_add_max - 1]];
2183 if(first_enrichment) {
2186 new_min_persistence[2] = last_persistence_added_max;
2188 if(last_persistence_added_max < new_min_persistence[2])
2189 new_min_persistence[2] = last_persistence_added_max;
2192 if(last_persistence_added_max > new_min_persistence[2]) {
2193 new_min_persistence[2] = last_persistence_added_max;
2202 int compteur_for_adding_points = 0;
2203 for(
int i = 0; i < numberOfInputs_; i++) {
2204 int const size = candidates_to_be_added_min[i].size();
2205 for(
int j = 0; j < std::min(max_points_to_add_min, size); j++) {
2206 Bidder b = bidder_diagrams_min_[i].at(
2207 candidates_to_be_added_min[i][idx_min[i][j]]);
2209 if(persistence >= new_min_persistence[0]) {
2210 b.
id_ = current_bidder_diagrams_min_[i].size();
2213 current_bidder_diagrams_min_[i].emplace_back(b);
2214 current_bidder_ids_min_[i]
2215 [candidates_to_be_added_min[i][idx_min[i][j]]]
2216 = current_bidder_diagrams_min_[i].size() - 1;
2218 if(use_accelerated_ && n_iterations_ > 0) {
2219 for(
int c = 0; c < k_; ++c) {
2224 - persistence / sqrt(2),
2233 Geometry::pow(u_[i], 1. / wasserstein_) + persistence / sqrt(2),
2237 int const to_be_added_to_barycenter
2238 = deterministic_ ? compteur_for_adding_points % numberOfInputs_
2239 : rand() % numberOfInputs_;
2240 if(to_be_added_to_barycenter == 0 && add_points_to_barycenter) {
2241 for(
int k = 0; k < numberOfInputs_; k++) {
2242 if(inv_clustering_[i] == inv_clustering_[k]) {
2244 b.
x_, b.
y_,
false, centroids_with_price_min_[k].size());
2245 g.
setPrice(initial_off_diagonal_prices[0][k]);
2248 centroids_with_price_min_[k].emplace_back(g);
2252 b.
x_, b.
y_,
false, centroids_min_[inv_clustering_[i]].size());
2254 centroids_min_[inv_clustering_[i]].emplace_back(g);
2257 compteur_for_adding_points++;
2262 int compteur_for_adding_points = 0;
2263 for(
int i = 0; i < numberOfInputs_; i++) {
2264 int const size = candidates_to_be_added_sad[i].size();
2265 for(
int j = 0; j < std::min(max_points_to_add_sad, size); j++) {
2266 Bidder b = bidder_diagrams_saddle_[i].at(
2267 candidates_to_be_added_sad[i][idx_sad[i][j]]);
2269 if(persistence >= new_min_persistence[1]) {
2270 b.
id_ = current_bidder_diagrams_saddle_[i].size();
2273 current_bidder_diagrams_saddle_[i].emplace_back(b);
2274 current_bidder_ids_sad_[i]
2275 [candidates_to_be_added_sad[i][idx_sad[i][j]]]
2276 = current_bidder_diagrams_saddle_[i].size() - 1;
2278 if(use_accelerated_ && n_iterations_ > 0) {
2279 for(
int c = 0; c < k_; ++c) {
2284 - persistence / sqrt(2),
2293 Geometry::pow(u_[i], 1. / wasserstein_) + persistence / sqrt(2),
2297 int const to_be_added_to_barycenter
2298 = deterministic_ ? compteur_for_adding_points % numberOfInputs_
2299 : rand() % numberOfInputs_;
2300 if(to_be_added_to_barycenter == 0 && add_points_to_barycenter) {
2301 for(
int k = 0; k < numberOfInputs_; k++) {
2302 if(inv_clustering_[i] == inv_clustering_[k]) {
2304 b.
x_, b.
y_,
false, centroids_with_price_saddle_[k].size());
2305 g.
setPrice(initial_off_diagonal_prices[1][k]);
2308 centroids_with_price_saddle_[k].emplace_back(g);
2313 compteur_for_adding_points++;
2318 int compteur_for_adding_points = 0;
2319 for(
int i = 0; i < numberOfInputs_; i++) {
2320 int const size = candidates_to_be_added_max[i].size();
2321 for(
int j = 0; j < std::min(max_points_to_add_max, size); j++) {
2322 Bidder b = bidder_diagrams_max_[i].at(
2323 candidates_to_be_added_max[i][idx_max[i][j]]);
2325 if(persistence >= new_min_persistence[2]) {
2326 b.
id_ = current_bidder_diagrams_max_[i].size();
2329 current_bidder_diagrams_max_[i].emplace_back(b);
2330 current_bidder_ids_max_[i]
2331 [candidates_to_be_added_max[i][idx_max[i][j]]]
2332 = current_bidder_diagrams_max_[i].size() - 1;
2334 if(use_accelerated_ && n_iterations_ > 0) {
2335 for(
int c = 0; c < k_; ++c) {
2340 - persistence / sqrt(2),
2349 Geometry::pow(u_[i], 1. / wasserstein_) + persistence / sqrt(2),
2353 int const to_be_added_to_barycenter
2354 = deterministic_ ? compteur_for_adding_points % numberOfInputs_
2355 : rand() % numberOfInputs_;
2356 if(to_be_added_to_barycenter == 0 && add_points_to_barycenter) {
2357 for(
int k = 0; k < numberOfInputs_; k++) {
2358 if(inv_clustering_[i] == inv_clustering_[k]) {
2360 b.
x_, b.
y_,
false, centroids_with_price_max_[k].size());
2361 g.
setPrice(initial_off_diagonal_prices[2][k]);
2364 centroids_with_price_max_[k].emplace_back(g);
2368 b.
x_, b.
y_,
false, centroids_max_[inv_clustering_[i]].size());
2370 centroids_max_[inv_clustering_[i]].emplace_back(g);
2373 compteur_for_adding_points++;
2378 return new_min_persistence;
2382 std::vector<double> & ) {
2385 barycenter_computer_min_.resize(k_);
2386 for(
int c = 0; c < k_; c++) {
2387 std::vector<BidderDiagram> diagrams_c;
2388 for(
int const idx : clustering_[c]) {
2389 diagrams_c.emplace_back(current_bidder_diagrams_min_[idx]);
2391 barycenter_computer_min_[c] = {};
2392 barycenter_computer_min_[c].setThreadNumber(threadNumber_);
2393 barycenter_computer_min_[c].setWasserstein(wasserstein_);
2394 barycenter_computer_min_[c].setDiagramType(0);
2395 barycenter_computer_min_[c].setUseProgressive(
false);
2396 barycenter_computer_min_[c].setDeterministic(
true);
2397 barycenter_computer_min_[c].setGeometricalFactor(geometrical_factor_);
2398 barycenter_computer_min_[c].setDebugLevel(debugLevel_);
2399 barycenter_computer_min_[c].setNumberOfInputs(diagrams_c.size());
2400 barycenter_computer_min_[c].setCurrentBidders(diagrams_c);
2401 barycenter_computer_min_[c].setNonMatchingWeight(nonMatchingWeight_);
2405 barycenter_computer_sad_.resize(k_);
2406 for(
int c = 0; c < k_; c++) {
2407 std::vector<BidderDiagram> diagrams_c;
2408 for(
int const idx : clustering_[c]) {
2409 diagrams_c.emplace_back(current_bidder_diagrams_saddle_[idx]);
2411 barycenter_computer_sad_[c] = {};
2412 barycenter_computer_sad_[c].setThreadNumber(threadNumber_);
2413 barycenter_computer_sad_[c].setWasserstein(wasserstein_);
2414 barycenter_computer_sad_[c].setDiagramType(1);
2415 barycenter_computer_sad_[c].setUseProgressive(
false);
2416 barycenter_computer_sad_[c].setDeterministic(
true);
2417 barycenter_computer_sad_[c].setGeometricalFactor(geometrical_factor_);
2418 barycenter_computer_sad_[c].setDebugLevel(debugLevel_);
2419 barycenter_computer_sad_[c].setNumberOfInputs(diagrams_c.size());
2420 barycenter_computer_sad_[c].setCurrentBidders(diagrams_c);
2421 barycenter_computer_sad_[c].setNonMatchingWeight(nonMatchingWeight_);
2423 std::vector<GoodDiagram> barycenter_goods(clustering_[c].size());
2424 for(
size_t i_diagram = 0; i_diagram < clustering_[c].size();
2426 barycenter_goods[i_diagram]
2427 = centroids_with_price_saddle_[clustering_[c][i_diagram]];
2429 barycenter_computer_sad_[c].setCurrentBarycenter(barycenter_goods);
2433 barycenter_computer_max_.resize(k_);
2434 for(
int c = 0; c < k_; c++) {
2435 std::vector<BidderDiagram> diagrams_c;
2436 for(
int const idx : clustering_[c]) {
2437 diagrams_c.emplace_back(current_bidder_diagrams_max_[idx]);
2439 barycenter_computer_max_[c] = {};
2440 barycenter_computer_max_[c].setDiagrams(inputDiagramsMax_);
2441 barycenter_computer_max_[c].setThreadNumber(threadNumber_);
2442 barycenter_computer_max_[c].setWasserstein(wasserstein_);
2443 barycenter_computer_max_[c].setDiagramType(2);
2444 barycenter_computer_max_[c].setUseProgressive(
false);
2445 barycenter_computer_max_[c].setDeterministic(
true);
2446 barycenter_computer_max_[c].setGeometricalFactor(geometrical_factor_);
2447 barycenter_computer_max_[c].setDebugLevel(debugLevel_);
2448 barycenter_computer_max_[c].setNumberOfInputs(diagrams_c.size());
2449 barycenter_computer_max_[c].setCurrentBidders(diagrams_c);
2450 barycenter_computer_max_[c].setNonMatchingWeight(nonMatchingWeight_);
2452 std::vector<GoodDiagram> barycenter_goods(clustering_[c].size());
2453 for(
size_t i_diagram = 0; i_diagram < clustering_[c].size();
2455 barycenter_goods[i_diagram]
2456 = centroids_with_price_max_[clustering_[c][i_diagram]];
2458 barycenter_computer_max_[c].setCurrentBarycenter(barycenter_goods);
2591 std::vector<std::vector<MatchingType>> &matchings,
2592 std::vector<std::vector<int>> &bidders_ids,
2593 std::vector<BidderDiagram> ¤t_bidder_diagrams,
2594 std::vector<BidderDiagram> &bidder_diagrams,
2597 auto &matchings0 = matchings[0];
2598 auto &diagram0 = bidder_diagrams[0];
2599 auto ¤t_diagram0 = current_bidder_diagrams[0];
2600 auto &ids0 = bidders_ids[0];
2602 auto &matchings1 = matchings[1];
2603 auto &diagram1 = bidder_diagrams[1];
2604 auto ¤t_diagram1 = current_bidder_diagrams[1];
2605 auto &ids1 = bidders_ids[1];
2607 std::vector<int> new_to_old_id(current_diagram1.size());
2609 for(
size_t j = 0; j < ids1.size(); j++) {
2610 int const new_id = ids1[j];
2612 new_to_old_id[new_id] = j;
2616 std::vector<MatchingType> matching_to_add(0);
2617 std::vector<MatchingType> matching_to_add2(0);
2619 for(
size_t i = 0; i < matchings1.size(); i++) {
2621 int const bidderId = std::get<0>(t);
2622 int const goodId = std::get<1>(t);
2625 Bidder const b = diagram1.at(new_to_old_id[bidderId]);
2626 double const bx = b.
x_;
2627 double const by = b.
y_;
2629 Good const g = barycenter.at(goodId);
2630 double const gx = g.
x_;
2631 double const gy = g.
y_;
2632 barycenter.at(goodId).x_ = (bx + gx) / 2;
2633 barycenter.at(goodId).y_ = (by + gy) / 2;
2636 std::get<2>(t) /= 4;
2639 double gx = (bx + by) / 2;
2640 double gy = (bx + by) / 2;
2643 double const cost = nonMatchingWeight_
2647 = std::make_tuple(bidderId, barycenter.size(), cost);
2648 MatchingType const t3 = std::make_tuple(-1, barycenter.size(), cost);
2649 Good const g =
Good(gx, gy,
false, barycenter.size());
2651 barycenter.emplace_back(g);
2652 matching_to_add.emplace_back(t2);
2653 matching_to_add2.emplace_back(t3);
2657 Good const g = barycenter.at(goodId);
2658 double const gx = (g.
x_ + g.
y_) / 2;
2659 double const gy = (g.
x_ + g.
y_) / 2;
2660 barycenter.at(goodId).
x_ = (gx + g.
x_) / 2;
2661 barycenter.at(goodId).y_ = (gy + g.
y_) / 2;
2662 std::get<2>(t) /= 4;
2666 for(
size_t j = 0; j < matching_to_add.size(); j++) {
2667 matchings1.emplace_back(matching_to_add[j]);
2669 for(
size_t j = 0; j < matching_to_add2.size(); j++) {
2670 matchings0.emplace_back(matching_to_add2[j]);
2676 std::vector<int> new_to_old_id2(current_diagram0.size());
2678 for(
size_t j = 0; j < ids0.size(); j++) {
2679 int const new_id = ids0[j];
2681 new_to_old_id2[new_id] = j;
2685 for(
size_t i = 0; i < matchings0.size(); i++) {
2687 int const bidderId = std::get<0>(t);
2688 int const goodId = std::get<1>(t);
2690 if(bidderId >= 0 and goodId >= 0) {
2691 Bidder const b = diagram0.at(new_to_old_id2[bidderId]);
2692 double const bx = b.
x_;
2693 double const by = b.
y_;
2694 Good const g = barycenter.at(goodId);
2695 double const gx = g.
x_;
2696 double const gy = g.
y_;
2699 std::get<2>(t) = cost;