order.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include <iostream>
#include <fstream>
#include <random>

#include "rbmp.hpp"

int main(int argc, char* argv[]) {
  unsigned n = 100;
  unsigned m = 100;

  int opt;

  while ((opt = getopt(argc, argv, "n:m:")) != -1) {
    switch (opt) {
    case 'n':
      n = atoi(optarg);
      break;
    case 'm':
      m = (unsigned)atof(optarg);
      break;
    default:
      exit(1);
    }
  }

  Rng r;
  Graph G(n, r);

#pragma omp declare reduction(vec_int_plus : std::vector<long int> : \
                                  std::transform(omp_out.begin(), omp_out.end(), omp_in.begin(), omp_out.begin(), std::plus<long int>())) \
                      initializer(omp_priv = decltype(omp_orig)(omp_orig.size()))

  std::vector<long int> data_x(G.vertices.size());
  std::vector<long int> data_y(G.vertices.size());

  std::string filename = "order_" + std::to_string(n) + ".dat";
  std::ifstream input(filename);

  if (input.is_open()) {
    for (unsigned i = 0; i < G.vertices.size(); i++) {
      input >> data_x[i];
      input >> data_y[i];
    }

    input.close();
  }


#pragma omp parallel for reduction(vec_int_plus : data_x) reduction(vec_int_plus : data_y)
  for (unsigned i = 0; i < m; i++) {
    PerfectMatching pm(G.vertices.size(), G.edges.size());

    for (const Edge& e : G.edges) {
      pm.AddEdge(e.halfedges[0].getHead().index, e.halfedges[0].getTail().index, r.variate<double, std::exponential_distribution>(1));
    }

    pm.options.verbose = false;
    pm.Solve();

    for (unsigned i = 0; i < G.vertices.size() / 2; i++) {
      unsigned j = pm.GetMatch(i);

      data_x[i] += G.vertices[i].coordinate[0];
      data_y[i] += G.vertices[i].coordinate[1];
      data_x[i] -= G.vertices[j].coordinate[0];
      data_y[i] -= G.vertices[j].coordinate[1];

      data_x[j] += G.vertices[i].coordinate[0];
      data_y[j] += G.vertices[i].coordinate[1];
      data_x[j] -= G.vertices[j].coordinate[0];
      data_y[j] -= G.vertices[j].coordinate[1];
    }
  }

  std::ofstream output(filename);

  for (unsigned i = 0; i < G.vertices.size(); i++) {
    output << data_x[i] << " " << data_y[i] << std::endl;
  }

  output.close();

  return 0;
}