drawings_of_cliques
functions.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <cmath>
4 #include <memory>
5 #include <iterator>
6 #include <iostream>
7 #include <vector>
8 #include <list>
9 #include <algorithm>
10 #include <set>
11 #include <unordered_map>
12 #include <fstream>
13 #include <string>
14 #include <thread>
15 #include <mutex>
16 
17 using namespace std;
18 
19 #ifndef M_PI
20 #define M_PI 3.14159265358979323846
21 #endif
22 
23 #ifndef SIZE_OF_ARRAY
24 #define SIZE_OF_ARRAY 10
25 #endif
26 
27 
28 #define x first
29 #define y second
30 
31 using array_4D = vector<vector<vector<vector<bool> > > >;
32 
33 inline long long fact[SIZE_OF_ARRAY + 5];
34 
35 inline void precount_factorials(){
36  fact[0] = 1;
37  for(int i = 1; i < SIZE_OF_ARRAY + 5;i++)
38  fact[i] = i * fact[i-1];
39  //cout << fact[SIZE_OF_ARRAY -1] << endl;
40 }
41 
42 
47  unordered_map<string, bool> canonic_fingerprints;
48  mutex shared_mutex;
49 };
50 
51 struct Vertex;
52 struct Edge;
53 struct Face;
54 
58 struct graph {
59 
60  /*normal part*/
61  int number_of_vertices = 0; //just real vertices
62 
63  int realized = 0;
64  bool done = false;
65 
66  int index;
67 
68  list<Edge> edges;
69 
70  shared_ptr<Face> outer_face;
71 
72  ofstream output_file;
73 
74  void close_files() {
75  output_file.close();
76  }
77 
78  graph(int n, int i, shared_ptr<canonic_wraper> shared_canonics) {
79  index = i;
80  canonic_fingerprints_wraper = shared_canonics;
81 
82  number_of_vertices = n;
83  outer_face = make_shared<Face>();
84 
85  starts.resize(number_of_vertices);
86  for (int i = 0; i < number_of_vertices;i++) {
87  starts[i].resize(number_of_vertices);
88  }
89 
90  blocked.resize(number_of_vertices);
91  for (int i = 0; i < number_of_vertices;i++) {
92  blocked[i].resize(number_of_vertices);
93  for (int j = 0; j < number_of_vertices;j++) {
94  blocked[i][j].resize(number_of_vertices);
95  for (int k = 0; k < number_of_vertices;k++) {
96  blocked[i][j][k].resize(number_of_vertices);
97  for (int l = 0; l < number_of_vertices;l++) {
98  blocked[i][j][k][l] = false;
99  }
100  }
101  }
102  }
103 
104 
105  string string_index = index < 10 ? "0" + to_string(index) : to_string(index);
106  auto output_path = "data/graph"
107  + to_string(n) + "_" + string_index + ".txt";
108  output_file.open(output_path);
109 
110  cout << "opened " << output_path << endl;
111 
112 
114  }
115 
116  void add_edge(shared_ptr<Vertex> a, shared_ptr<Vertex> b, shared_ptr<Face> face, int a_index, int b_index, bool outer_face_bool = false);
117  void add_vertex(Edge* edge);
118 
119  void delete_edge_back(bool outer_face_bool = false);
120  void delete_vertex(Vertex* a);
121 
122  /*finger print part*/
123 
124  //number of edges indexer
125 
129  vector<Edge*> segments;
130 
135 
140  vector<vector<int> > starts;
141 
142  shared_ptr<canonic_wraper> canonic_fingerprints_wraper;
143 
144  void create_special_vertex(int index);
145  void recolor_fingerprint(const string& rotation);
146  void create_base_star();
147  void create_all_special_vertices();
148  void find_the_way_to_intersect(int s_index, int t_index, int a, int b);
149  //void intersect();
150  bool is_correct_fingerprint(const string& fingerprint);
151  void create_all_possible_drawings();
152 
153  string find_canonic_fingerprint(const string& fingerprint);
154 
155  bool is_some_of_faces_incorrect(Edge* edge);
156  bool is_face_incorrect(shared_ptr<Face> face);
157 
158  void print_counters(Face* f);
159 
160 
161 };
162 
166 struct Vertex {
168 
169  int index_;
170 
171  Vertex() {}
172 
173  //it is really good to be the opposite one because when you create new vertex
174  //from the edge side then it is good to go from the intersection opposite side
175  Vertex(Edge* to) : to_(to) {}
176 };
177 
181 struct Face {
183 
184  Face() {
185  for (int i = 0; i < SIZE_OF_ARRAY + 5;i++)
186  counter_of_same_last_edges[i] = 0;
187  }
188 
189  //Face(Edge* edge) : edge_(edge) {}
190 
191 
192  //int counter_of_last_edges = 0;
193  int counter_of_same_last_edges[SIZE_OF_ARRAY + 5];
194 };
195 
199 struct Edge {
200  int index_ = 0;
201 
205 
206  shared_ptr<Vertex> from_;
207  shared_ptr<Vertex> to_;
208 
209  shared_ptr<Face> face_;
210 
211  Edge() {}
212 
213  Edge(Edge* next, Edge* prev, Edge* opposite, shared_ptr<Vertex> from, shared_ptr<Vertex> to, shared_ptr<Face> face, int index) :
214  next_(next), prev_(prev), opposite_(opposite), from_(from), to_(to), face_(face), index_(index) {}
215 
216  bool operator==(const Edge& a) {
217  return (from_ == a.from_ && to_ == a.to_);
218  }
219 
220  bool operator!=(const Edge& a) {
221  return !(*this == a);
222  }
223 
224 };
225 
226 inline void print_graph(graph* g) {
227  cout << "number of edges: " << g->edges.size() << endl;
228 
229  int i = 0;
230  for (auto it : g->edges) {
231  cout << it.from_ << ":from to:" << it.to_ << " face:" << it.face_ << " prev:" << it.prev_->index_ << " next:" << it.next_->index_
232  << " opp:" << ((it.opposite_ == nullptr) ? -1 : it.opposite_->index_) << " index:" << it.index_ << " s: " << i << endl;
233  i++;
234  }
235 }
236 
237 
238 inline void graph::print_counters(Face* f) {
239  for (int i = 0; i < number_of_vertices - 1;i++)
240  cout << f->counter_of_same_last_edges[i] << " ";
241  cout << endl;
242 }
243 
253 inline void graph::add_edge(shared_ptr<Vertex> a, shared_ptr<Vertex> b, shared_ptr<Face> face, int a_index, int b_index, bool outer_face_bool) {
254 
255  Edge* toa = nullptr, * tob = nullptr, * froma = nullptr, * fromb = nullptr;
256 
257  toa = a->to_;
258  froma = toa->next_;
259 
260  tob = b->to_;
261  fromb = tob->next_;
262 
263  auto new_face = !outer_face_bool ? make_shared<Face>() : outer_face; //new face or old face when creating star
264 
265  Edge ab_edge(fromb, toa, nullptr, a, b, face, a_index*100 + b_index); //edge from a to b
266  edges.push_back(ab_edge); //number_of_edges++;
267  Edge* ab_edge_ptr = &edges.back();
268  segments.push_back(ab_edge_ptr);
269 
270  //print_graph(this);
271 
272  Edge ba_edge(froma, tob, ab_edge_ptr, b, a, new_face, b_index*100 + a_index); //edge from b to a
273  edges.push_back(ba_edge); //number_of_edges++;
274  Edge* ba_edge_ptr = &edges.back();
275  segments.push_back(ba_edge_ptr);
276 
277  //print_graph(this);
278 
279  ab_edge_ptr->opposite_ = ba_edge_ptr; //setting opposite edge that has been already made and face edge
280  new_face->edge_ = ba_edge_ptr;
281 
282  /*if it throws an exception it is allright because we are tryint to connect unconnectable vertices*/
283  froma->prev_ = ba_edge_ptr; //changing neighborhood edges
284  toa->next_ = ab_edge_ptr;
285  fromb->prev_ = ab_edge_ptr;
286  tob->next_ = ba_edge_ptr;
287 
288  //print_graph(this);
289 
290  if (!outer_face_bool) { //because if it is outer face it is not needed so it can be quicker
291  auto start_edge = ba_edge_ptr; //setting the face property to all edges around this face
292  auto cur_edge = start_edge->next_;
293  while (start_edge != cur_edge) {
294  cur_edge->face_ = new_face;
295  if ((cur_edge->index_ / 100 == number_of_vertices - 1) != (cur_edge->index_ % 100 == number_of_vertices - 1)) {
296  new_face->counter_of_same_last_edges[min(cur_edge->index_ / 100, cur_edge->index_ % 100)]++;
297  }
298  cur_edge = cur_edge->next_;
299  }
300 
301  for (int i = 0; i < number_of_vertices - 1;i++) {
302  face->counter_of_same_last_edges[i] -= new_face->counter_of_same_last_edges[i];
303  }
304 
305  }
306 
307 
308  if (((ab_edge_ptr->index_ / 100) == (number_of_vertices -1)) != ((ab_edge_ptr->index_ % 100) == (number_of_vertices - 1))) {
309  new_face->counter_of_same_last_edges[min(ab_edge_ptr->index_ / 100, ab_edge_ptr->index_ % 100)]++;
310  face->counter_of_same_last_edges[min(ab_edge_ptr->index_ / 100, ab_edge_ptr->index_ % 100)]++;
311  }
312 
313 
314  face->edge_ = ab_edge_ptr;
315 
316 
317 }
318 
323 inline void graph::add_vertex(Edge* edge) {
324 
325 
326  auto opposite = edge->opposite_;
327 
328 
329  auto a = edge->from_;
330  auto b = edge->to_;
331 
332  auto new_vertex = make_shared<Vertex>(edge); //edge is going to this vertex //"edge" it is important because after adding vertex we add teh edge to the same direction (not face, face can be same anyway)
333  new_vertex->index_ = -1;
334 
335  edges.push_back(Edge(edge->next_, edge, opposite, new_vertex, b, edge->face_, edge->index_)); //new vertex to b, part of normal edge
336  auto tob = &edges.back();
337  segments.push_back(tob);
338 
339  edges.push_back(Edge(opposite->next_, opposite, edge, new_vertex, a, opposite->face_, opposite->index_)); //create from new_vertex to a, part of opposite
340  auto toa = &edges.back();
341  segments.push_back(toa);
342 
343  edge->to_ = new_vertex; //changing properties of edge
344  edge->next_ = tob;
345  edge->opposite_ = toa;
346 
347  opposite->to_ = new_vertex; //changing properties of opposite
348  opposite->next_ = toa;
349  opposite->opposite_ = tob;
350 
351  if ((edge->index_ / 100 == number_of_vertices - 1) != (edge->index_ % 100 == number_of_vertices - 1)) {
352  edge->face_->counter_of_same_last_edges[min(edge->index_ / 100, edge->index_ % 100)]++;
353  opposite->face_->counter_of_same_last_edges[min(edge->index_ / 100, edge->index_ % 100)]++;
354  }
355 
356 
357 }
358 
363 inline void graph::delete_edge_back(bool outer_face_bool) {
364 
365  auto edge = edges.back();
366  auto opposite = *edge.opposite_;
367 
368  auto a = edge.from_;
369  auto b = edge.to_;
370 
371  auto face = edge.face_;
372 
373  auto froma = opposite.next_;
374  auto toa = edge.prev_;
375  auto fromb = edge.next_;
376  auto tob = opposite.prev_;
377 
378  /*update faces first!*/
379 
380  auto cur_edge = opposite.next_;
381  if (!outer_face_bool) {
382  while (opposite != *cur_edge) {
383  cur_edge->face_ = face;
384  if ((cur_edge->index_ / 100 == number_of_vertices - 1) != (cur_edge->index_ % 100 == number_of_vertices - 1)) {
385  face->counter_of_same_last_edges[min(cur_edge->index_ / 100, cur_edge->index_ % 100)]++;
386  }
387  cur_edge = cur_edge->next_;
388  }
389  }
390 
391 
392  /*recconect edges*/
393  froma->prev_ = toa;
394  toa->next_ = froma;
395  fromb->prev_ = tob;
396  tob->next_ = fromb;
397 
398  /*update edges if there the bad ones*/
399  a->to_ = toa;
400  b->to_ = tob;
401 
402  face->edge_ = froma;
403 
404  outer_face = face; //just to end up with outer face
405 
406  /* delete the edge from list, pop from segments should be out of this function */
407 
408  if ((edge.index_ / 100 == number_of_vertices - 1) != (edge.index_ % 100 == number_of_vertices - 1)) {
409  face->counter_of_same_last_edges[min(edge.index_ / 100, edge.index_ % 100)]--;
410  }
411 
412  segments.pop_back();segments.pop_back();
413  edges.pop_back();edges.pop_back();
414 
415 }
420 inline void graph::delete_vertex(Vertex* vertex) {
421 
422  // getting the right variables
423  auto edge = vertex->to_;
424 
425  auto toa = edge->opposite_;
426  auto tob = edge->next_;
427  auto edge_opposite = tob->opposite_;
428 
429  auto a = toa->to_;
430  auto b = tob->to_;
431 
432  // reconnecting edges and therefore removing the vertex
433 
434  edge->to_ = b;
435  edge_opposite->to_ = a;
436  edge->next_ = tob->next_;
437  edge_opposite->next_ = toa->next_;
438 
439  //setting opposites
440  edge->opposite_ = edge_opposite;
441  edge_opposite->opposite_ = edge;
442 
443  //removig the edges from the back of segments and edges
444  //because of the order and recursive algorithm we know they are the last one
445 
446  // face changing, importnat!
447  edge->face_->edge_ = edge;
448  edge_opposite->face_->edge_ = edge_opposite;
449 
450 
451  if ((edge->index_ / 100 == number_of_vertices - 1) != (edge->index_ % 100 == number_of_vertices - 1)) {
452  edge->face_->counter_of_same_last_edges[min(edge->index_ / 100, edge->index_ % 100)]--;
453  edge_opposite->face_->counter_of_same_last_edges[min(edge->index_ / 100, edge->index_ % 100)]--;
454  }
455 
456  segments.pop_back(); segments.pop_back();
457  edges.pop_back(); edges.pop_back();
458 
459 }
460 
465 inline void graph::create_special_vertex(int index) {
466 
467  vector<shared_ptr<Vertex> > special_vertices;
468 
469  /*create vertices with coordinates*/
470  for (int i = 0; i < number_of_vertices - 1;i++) {
471  auto new_vertex = make_shared<Vertex>();
472  new_vertex->index_ = index; //the real index of vertex
473  special_vertices.push_back(new_vertex);
474  }
475 
476 
477  /* edges created */
478  for (int i = 0; i < number_of_vertices - 1;i++) {
479  auto first_vertex = special_vertices[i];
480  auto second_vertex = special_vertices[(i + 1) % (number_of_vertices - 1)];
481  edges.push_back(Edge(nullptr, nullptr, nullptr, first_vertex, second_vertex, outer_face, 100*index + index));
482  second_vertex->to_ = &edges.back();
483  segments.push_back(&edges.back());
484  }
485 
486  /* dependencies set */
487  for (int i = 0; i < number_of_vertices - 1;i++) {
488  special_vertices[i]->to_->prev_ = special_vertices[((i - 1) + (number_of_vertices - 1)) % (number_of_vertices - 1)]->to_;
489  special_vertices[i]->to_->next_ = special_vertices[(i + 1) % (number_of_vertices - 1)]->to_;
490  }
491 
492  /* outer face needs face*/
493  outer_face->edge_ = &edges.back();
494 
495 }
496 
501 inline void graph::recolor_fingerprint(const string& fingerprint) { //fingerprint does include the first ro (0..n), otherwise do the first rotation manually
502 
503  for(int i = 0; i < number_of_vertices;i++){
504  for (int j = 0; j < number_of_vertices - 1;j++) { //every vertex has n-1 around itself
505  starts[i][fingerprint[i * (number_of_vertices - 1) + j] - '0'] = i * (number_of_vertices - 1) + j;
506  }
507  }
508 }
509 
513 inline void graph::create_base_star() {
514  for (int i = 1; i < number_of_vertices;i++) {
515  add_edge(segments[starts[0][i]]->from_, segments[starts[i][0]]->from_, outer_face, 0, i, true); //from vertex is that in rotation
516  }
517 }
518 
523 
524  for (int i = 0; i < number_of_vertices;i++) { //the rest of a star
525  create_special_vertex(i);
526  }
527 }
528 
538 inline void graph::find_the_way_to_intersect(int s_index, int t_index, int a, int b) {
539 
540  //cout << a << " " << b << endl;
541  auto seg = segments[s_index]->next_;
542 
543  //print_graph(this);
544 
545  //cout << "" << endl;
546 
547  while (seg != segments[s_index]) { //the first doesnt have to be considered because it is either beggining segment so it cannot be intersected or it has been already intersected
548 
549  if (seg == segments[t_index]) {
550 
551  add_edge(segments[s_index]->from_, segments[t_index]->from_, segments[s_index]->face_, a, b);
552 
553 
554  if (b < number_of_vertices - 2) { //the last vertex is out due to heuristics
555  find_the_way_to_intersect(starts[a][b + 1], starts[b + 1][a], a, b + 1);
556 
557  if (done) return;
558 
559  }
560  else if ((b == number_of_vertices - 2) && (a < number_of_vertices - 3)) {
561  find_the_way_to_intersect(starts[a + 1][a + 2], starts[a + 2][a + 1], a + 1, a + 2);
562 
563  if (done) return;
564  }
565  else if ((b == number_of_vertices - 2) && (a == number_of_vertices - 3)) {
566  find_the_way_to_intersect(starts[1][b + 1], starts[b + 1][1], 1, b + 1);
567 
568  if (done) return;
569  }
570  else if ((b == number_of_vertices - 1) && (a < number_of_vertices - 2)) {
571  find_the_way_to_intersect(starts[a + 1][b], starts[b][a + 1], a + 1, b);
572 
573  if (done) return;
574  }
575  else {
576 
577  //print_graph(this);
578  realized++;
579  done = true;
580  return;
581 
582  }
583 
584  delete_edge_back();
585  }
586 
587  auto index_first_end = seg->index_ / 100;
588  auto index_second_end = seg->index_ % 100;
589 
590  if (!blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)]) { //if there is same index, always true // it can be divided edge so we need to look at the ends of it to get the indices of vertices
591 
592  //print_graph(this);
593 
594  //intersecting
595  blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] = true;
596  add_vertex(seg);
597  add_edge(segments[s_index]->from_, segments[edges.size() - 1]->from_, segments[s_index]->face_, a, b);
598 
599 
600 
601  /*important! changing to_ to the opposite direction */
602  segments[edges.size() - 3]->from_->to_ = segments[edges.size() - 3]->prev_;
603 
604  if(max(a, b) != number_of_vertices - 1 || !is_some_of_faces_incorrect(segments[edges.size() - 2])){
605  //try to go further
606  //cout << "#############IN####################" << endl;
607  find_the_way_to_intersect(edges.size() - 3, t_index, a, b); //it is 3rd from the end, because it was added as second in add_vertex and then 2 more were added in add_edge
608  if (done) {
609  blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] = false;
610  return;
611  }
612  }
613  //cout << a << " " << b << endl;
614 
615  //segments[edges.size() - 3]->from_->to_ = segments[edges.size() - 3];
616 
617  //undo-intersect //not commutative!
618  delete_edge_back();
619  delete_vertex((seg->to_).get());
620  blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] = false;
621  }
622  seg = seg->next_;
623  }
624 }
625 
626 
634  auto opposite = edge->opposite_;
635 
636 
637  if(is_face_incorrect(edge->face_) || is_face_incorrect(opposite->face_)){
638  //cout << "face incorrect" << endl;
639  return true;
640  }
641  return false;
642 }
643 
644 
650 inline bool graph::is_face_incorrect(shared_ptr<Face> face) {
651  int sum = 0;
652  for(int i = 0; i < number_of_vertices - 1;i++){
653  if (face->counter_of_same_last_edges[i] >= 2) //treshold by article
654  return true;
655  //cout << face->counter_of_same_last_edges[i] << " ";
656 
657  sum += (face->counter_of_same_last_edges[i] > 0);
658  }
659  //cout << endl;
660  if(sum >= 3)
661  return true;
662  return false;
663 }
664 
665 
666 inline long long factorial(int n) {
667  return fact[n];
668 }
669 
670 
674 struct fingerprints {
675  vector<int> states;
676  long long treshold;
677  bool done = false;
678  vector<string> fingerprint;
679 
680  ifstream input_file;
682  // Set up the treshold (number of permutation of given string), then generate first rotation systems and reset the states to zeroes
684  fingerprints(int n, int index) {
685  treshold = n; //its length is n-1 and -1 because 0 is on fixed position
686 
687  string string_index = index < 10 ? "0" + to_string(index) : to_string(index);
688  auto input_path = "data/graph"
689  + to_string(n - 1) + "_" + string_index + ".txt";
690 
691  //cout << "input " << input_path << endl;
692  input_file.open(input_path);
693 
694  cout << "opened also " << input_path << endl;
695 
696  string rotation_system;
697  if (!getline(input_file, rotation_system)) {
698  done = true;
699  }
700 
701  for (int i = 0; i < n - 1;i++) {
702  fingerprint.push_back(rotation_system.substr(i * (n - 2), (n - 2)) + to_string(n - 1));
703  }
704 
705  string last_rotation;
706  for (int i = 0; i < n - 1;i++)
707  last_rotation += (i + '0');
708 
709  fingerprint.push_back(last_rotation);
710 
711  for (int i = 0; i < n;i++) {
712  states.push_back(0);
713  }
714 
715 
716  }
717 
719  // Get new fingerprint and then move to the next one until it is possible.
721  string get_next() {
722  string res;
723  for_each(fingerprint.begin(), fingerprint.end(), [&](const string& part) {res += part;});
724 
725  for (long long i = states.size() - 1; i >= 0;i--) {
726  if (i == states.size() - 1) {
727  if (states[i] == factorial(treshold - 2) - 1) { // -2 because first position is fixed for "0"
728  states[i] = 0;
729  next_permutation(fingerprint[i].begin() + 1, fingerprint[i].end());
730  }
731  else {
732  states[i]++;
733  next_permutation(fingerprint[i].begin() + 1, fingerprint[i].end());
734  break;
735  }
736  }
737  else {
738  if (states[i] == (treshold - 2) - 1) {
739  if (i == 0) {
740  string rotation_system;
741  if (!getline(input_file, rotation_system)) {
742  done = true;
743  return res;
744  }
745 
746  fingerprint.clear();
747  for (int i = 0; i < treshold - 1;i++) {
748  fingerprint.push_back(rotation_system.substr(i * (treshold - 2), (treshold - 2)) + to_string(treshold - 1));
749  }
750 
751  string last_rotation;
752  for (int i = 0; i < treshold - 1;i++)
753  last_rotation += (i + '0');
754 
755  fingerprint.push_back(last_rotation);
756 
757  states.clear();
758  for (int i = 0; i < treshold;i++) {
759  states.push_back(0);
760  }
761  }
762  else {
763  states[i] = 0;
764  fingerprint[i] = fingerprint[i][0] + fingerprint[i].substr(2) + fingerprint[i][1];
765  }
766  }
767  else {
768  swap(fingerprint[i][(treshold - 2) - states[i]], fingerprint[i][(treshold - 2) - (states[i] + 1)]);
769  states[i]++;
770  break;
771  }
772  }
773  }
774 
775  return res;
776  }
777 };
778 
779 
790 
791  for (int i = 0; i < number_of_vertices;i++) {
792  for (int j = 0; j < number_of_vertices;j++) {
793  for (int k = 0; k < number_of_vertices;k++) {
794  for (int l = 0; l < number_of_vertices;l++) {
795  set<int> tmp = { i, j, k, l };
796  if (tmp.size() < 4) {
797  blocked[i][j][k][l] = true;
798  }
799 
800  }
801  }
802  }
803  }
804 
805  auto generator_of_fingerprints = fingerprints(number_of_vertices, index);
806 
807  while (!generator_of_fingerprints.done) {
808  auto fingerprint = generator_of_fingerprints.get_next();
809 
810  //check the fingerprint
811  if (!is_correct_fingerprint(fingerprint)) continue;
812 
813 
814  //checking labeling
815  fingerprint = find_canonic_fingerprint(fingerprint);
816 
817 
818  {
819  lock_guard<mutex> canonic_lock(canonic_fingerprints_wraper->shared_mutex);
820  if (canonic_fingerprints_wraper->canonic_fingerprints[fingerprint]) continue;
821  canonic_fingerprints_wraper->canonic_fingerprints[fingerprint] = true;
822  }
823 
824  //cout << "after lock guard" << endl;
825 
826  create_all_special_vertices();
827  recolor_fingerprint(fingerprint);
828  create_base_star();
829 
830  //cout << fingerprint << endl;
831 
832  find_the_way_to_intersect(starts[1][2], starts[2][1], 1, 2);
833 
834  //print_graph(this);
835  if (done) {
836  cout << "yes" << endl;
837  output_file << fingerprint << "\n";
838  }
839 
840  edges.resize(0); segments.resize(0);
841  done = false;
842  outer_face = make_shared<Face>();
843  }
844 
845  close_files();
846 
847  cout << "realized " << realized << endl;
848 }
849 
863 
864  string fingerprint;
866  bool done = false;
868  string result;
869  bool invers = false;
870 
871  int counter = 0;
872  int counter_rotation = 0;
873 
874  string create_permutation(const string& rotation1, const string& roration2) {
875 
876  string permutation = "";
877  for (int i = 0; i < number_of_vertices;i++)
878  permutation += (i + '0');
879 
880  int sum_r1 = ((number_of_vertices - 1) * (number_of_vertices))/ 2;
881  int sum_r2 = sum_r1;
882 
883  for (int i = 0; i < rotation1.size();i++) {
884  permutation[rotation1[i] - '0'] = roration2[i];
885  sum_r1 -= (rotation1[i] - '0');
886  sum_r2 -= (roration2[i] - '0');
887  }
888 
889  permutation[sum_r1] = sum_r2 + '0'; //last
890  return permutation;
891  }
892 
893  smart_permutations(const string& fingerprint, int number_of_vertices) {
894  this->fingerprint = fingerprint;
895  this->number_of_vertices = number_of_vertices;
896 
897  for (int i = 1; i < number_of_vertices;i++)
898  first_rotation += (i + '0');
899 
900  }
901 
902  string next() {
903 
904  result = create_permutation(fingerprint.substr((number_of_vertices - 1) * counter, number_of_vertices - 1), first_rotation);
905  //cout << result << ":result " << endl;
906 
907  if (invers && counter == number_of_vertices - 1 && counter_rotation == number_of_vertices - 2) {
908  done = true;
909  return result;
910  }
911 
912  if (invers && counter_rotation == number_of_vertices - 2) {
913  invers = false;
914  counter++;
915  counter_rotation = 0;
916 
917  first_rotation = "";
918  for (int i = 1; i < number_of_vertices;i++)
919  first_rotation += (i + '0');
920  }
921  else if (counter_rotation == number_of_vertices - 2) {
922  counter_rotation = 0;
923  invers = true;
924 
925  first_rotation = "1";
926  for (int i = 1; i < number_of_vertices - 1;i++)
927  first_rotation += ((number_of_vertices - i) + '0');
928 
929  //rotate(first_rotation.begin(), first_rotation.begin() + 1, first_rotation.end());
930  }
931  else {
932  counter_rotation++;
933  rotate(first_rotation.begin(), first_rotation.begin() + 1, first_rotation.end());
934  }
935 
936  return result;
937  }
938 };
939 
945 inline string graph::find_canonic_fingerprint(const string& fingerprint) {
946 
947  auto permutations = smart_permutations(fingerprint, number_of_vertices);
948 
949  auto min_fingerprint = fingerprint;
950  auto cur_fingerprint = fingerprint;
951  auto new_fingerprint = fingerprint;
952 
953  do {
954  auto permutation_holder = permutations.next();
955 
956  cur_fingerprint = fingerprint;
957  new_fingerprint = fingerprint;
958 
959  for (int i = 0; i < number_of_vertices;i++) {
960  int rotation_index = -1;
961  for (int j = 0; j < number_of_vertices - 1;j++) {
962  int index = (number_of_vertices - 1) * i + j;
963 
964  if (permutation_holder[cur_fingerprint[index] - '0'] == '0'
965  || (rotation_index == -1 && permutation_holder[cur_fingerprint[index] - '0'] == '1')) rotation_index = j;
966 
967  cur_fingerprint[index] = permutation_holder[cur_fingerprint[index] - '0'];
968  }
969 
970  rotate(cur_fingerprint.begin() + (number_of_vertices - 1) * i,
971  cur_fingerprint.begin() + (number_of_vertices - 1) * i + rotation_index,
972  cur_fingerprint.begin() + (number_of_vertices - 1) * (i + 1));
973  }
974  for (int i = 0; i < number_of_vertices;i++) {
975  new_fingerprint.replace((number_of_vertices - 1) * (permutation_holder[i] - '0'), number_of_vertices - 1,
976  cur_fingerprint, i * (number_of_vertices - 1), number_of_vertices - 1);
977  }
978 
979  min_fingerprint = min(min_fingerprint, new_fingerprint);
980 
981  for (int i = 0; i < number_of_vertices;i++) {
982  auto inv_part = new_fingerprint.substr(i * (number_of_vertices - 1) + 1, number_of_vertices - 2);
983  reverse(inv_part.begin(), inv_part.end());
984  new_fingerprint.replace(i * (number_of_vertices - 1) + 1, number_of_vertices - 2, inv_part);
985  }
986 
987  min_fingerprint = min(min_fingerprint, new_fingerprint);
988 
989  } while (!permutations.done);
990 
991  //cout << minimal_permutation << endl;
992  return min_fingerprint;
993 
994 }
995 
996 
997 inline string find_lexical_min_rotation(string str)
998 {
999  // To store lexicographic minimum string
1000  string min = str;
1001 
1002  for (int i = 0; i < str.length(); i++)
1003  {
1004  // left rotate string by 1 unit
1005  rotate(str.begin(), str.begin() + 1, str.end());
1006 
1007  // check if the rotation is minimum so far
1008  if (str.compare(min) < 0)
1009  min = str;
1010  }
1011 
1012  return min;
1013 }
1014 
1020 inline bool is_correct_K4(vector<int> orders[4]) {
1021  int number_of_positive_rotation = 0;
1022 
1023  for (int i = 0; i < 4;i++) {
1024 
1025  string rotation;
1026  for_each(orders[i].begin(), orders[i].end(), [&](int part) {rotation += to_string(part);});
1027 
1028  auto minimal_rotation = find_lexical_min_rotation(rotation);
1029  if (minimal_rotation[1] < minimal_rotation[2])
1030  number_of_positive_rotation++;
1031  }
1032 
1033  if (number_of_positive_rotation % 2 == 0)
1034  return true;
1035  return false;
1036 
1037 }
1038 
1044 inline bool graph::is_correct_fingerprint(const string& fingerprint) { //checking all K4
1045 
1046  int i[4];
1047 
1048  for (i[0] = 0; i[0] < number_of_vertices;i[0]++) {
1049  for (i[1] = i[0] + 1; i[1] < number_of_vertices;i[1]++) {
1050  for (i[2] = i[1] + 1; i[2] < number_of_vertices;i[2]++) {
1051  for (i[3] = i[2] + 1; i[3] < number_of_vertices;i[3]++) {
1052 
1053  vector<int> order[4];
1054 
1055  for (int v = 0; v < 4;v++) {
1056  for (int u = 0; u < number_of_vertices - 1;u++) {
1057  if (fingerprint[u + i[v] * (number_of_vertices - 1)] - '0' == i[(1 + v) % 4]
1058  || fingerprint[u + i[v] * (number_of_vertices - 1)] - '0' == i[(2 + v) % 4]
1059 
1060  || fingerprint[u + i[v] * (number_of_vertices - 1)] - '0' == i[(3 + v) % 4])
1061  {
1062  order[v].push_back(fingerprint[u + i[v] * (number_of_vertices - 1)] - '0');
1063  }
1064  }
1065  }
1066 
1067  if (!is_correct_K4(order)) return false;
1068  }
1069  }
1070  }
1071  }
1072 
1073  return true;
1074 }
void print_graph(graph *g)
Definition: functions.hpp:226
void precount_factorials()
Definition: functions.hpp:35
bool is_correct_K4(vector< int > orders[4])
Check if given rotations of K4 form a realizable K4.
Definition: functions.hpp:1020
long long fact[SIZE_OF_ARRAY+5]
Definition: functions.hpp:33
#define SIZE_OF_ARRAY
Definition: functions.hpp:24
long long factorial(int n)
Definition: functions.hpp:666
string find_lexical_min_rotation(string str)
Definition: functions.hpp:997
vector< vector< vector< vector< bool > > > > array_4D
Definition: functions.hpp:31
Structure to store the edge containing information about next_, prev_, opposite_ edges and vertices a...
Definition: functions.hpp:199
Edge * prev_
Definition: functions.hpp:203
Edge()
Definition: functions.hpp:211
bool operator!=(const Edge &a)
Definition: functions.hpp:220
bool operator==(const Edge &a)
Definition: functions.hpp:216
shared_ptr< Vertex > from_
Definition: functions.hpp:206
Edge * opposite_
Definition: functions.hpp:204
shared_ptr< Vertex > to_
Definition: functions.hpp:207
shared_ptr< Face > face_
Definition: functions.hpp:209
int index_
Definition: functions.hpp:200
Edge * next_
Definition: functions.hpp:202
Edge(Edge *next, Edge *prev, Edge *opposite, shared_ptr< Vertex > from, shared_ptr< Vertex > to, shared_ptr< Face > face, int index)
Definition: functions.hpp:213
Structure to store a face containing about one edge incident to it
Definition: functions.hpp:181
Edge * edge_
Definition: functions.hpp:182
int counter_of_same_last_edges[SIZE_OF_ARRAY+5]
Definition: functions.hpp:193
Face()
Definition: functions.hpp:184
Class to store vertex, containing information about edge to_ going into it
Definition: functions.hpp:166
int index_
Definition: functions.hpp:169
Edge * to_
Definition: functions.hpp:167
Vertex(Edge *to)
Definition: functions.hpp:175
Vertex()
Definition: functions.hpp:171
Wraper for comunicating through threads
Definition: functions.hpp:46
unordered_map< string, bool > canonic_fingerprints
Definition: functions.hpp:47
mutex shared_mutex
Definition: functions.hpp:48
Structure for generating all fingerprints iteratively.
Definition: functions.hpp:674
long long treshold
Definition: functions.hpp:676
ifstream input_file
Definition: functions.hpp:680
vector< string > fingerprint
Definition: functions.hpp:678
vector< int > states
Definition: functions.hpp:675
fingerprints(int n, int index)
Definition: functions.hpp:684
string get_next()
Definition: functions.hpp:721
Main class to store all the information about graph, edges, vertices, ...
Definition: functions.hpp:58
ofstream output_file
Definition: functions.hpp:72
void find_the_way_to_intersect(int s_index, int t_index, int a, int b)
Main algorithm described in psedocode in thesis. It recursively tries all the possible ways how to pu...
Definition: functions.hpp:538
bool is_correct_fingerprint(const string &fingerprint)
Function to check whether the fingerprint consists only of realizable K4's.
Definition: functions.hpp:1044
string find_canonic_fingerprint(const string &fingerprint)
Function to find canonic fingerprint through all needed rellabelings of itself (and inversion)
Definition: functions.hpp:945
vector< vector< int > > starts
Array which for given pair of vertice i, j return the index in vector segments so the "dummy" edge ("...
Definition: functions.hpp:140
int index
Definition: functions.hpp:66
void delete_vertex(Vertex *a)
Deleting given intersection vertex.
Definition: functions.hpp:420
void close_files()
Definition: functions.hpp:74
void create_base_star()
Function to create all edges incident to vertex 0.
Definition: functions.hpp:513
shared_ptr< canonic_wraper > canonic_fingerprints_wraper
Definition: functions.hpp:142
void recolor_fingerprint(const string &rotation)
Setting values of array starts to values of given fingerprint.
Definition: functions.hpp:501
void print_counters(Face *f)
Definition: functions.hpp:238
shared_ptr< Face > outer_face
Definition: functions.hpp:70
bool is_some_of_faces_incorrect(Edge *edge)
Function to check if current operation of adding edge did not cause violation of one theorems providi...
Definition: functions.hpp:633
void create_all_special_vertices()
Function to create all "dummy" vertices
Definition: functions.hpp:522
array_4D blocked
4D array to check which edges already intersect
Definition: functions.hpp:134
list< Edge > edges
Definition: functions.hpp:68
vector< Edge * > segments
Vector to store (pointers on) edges.
Definition: functions.hpp:129
void create_all_possible_drawings()
Function to try all possible drawings, First getting all the fingerprints then checking if all K4's a...
Definition: functions.hpp:789
void create_special_vertex(int index)
Creating the "dummy" vertex (circle) representing real vertex.
Definition: functions.hpp:465
void add_edge(shared_ptr< Vertex > a, shared_ptr< Vertex > b, shared_ptr< Face > face, int a_index, int b_index, bool outer_face_bool=false)
Function to add new (part of) edge between vertices a and b through the face
Definition: functions.hpp:253
void delete_edge_back(bool outer_face_bool=false)
Deleting the last added edge.
Definition: functions.hpp:363
void add_vertex(Edge *edge)
Creating new vertec on the edge as a new intersection.
Definition: functions.hpp:323
bool is_face_incorrect(shared_ptr< Face > face)
Function to check whether the face do not violate the (heuristic) theorems conditions.
Definition: functions.hpp:650
graph(int n, int i, shared_ptr< canonic_wraper > shared_canonics)
Definition: functions.hpp:78
Structure to go through only needed fingerprints. First try all rellabilings of rotation producing "1...
Definition: functions.hpp:862
string create_permutation(const string &rotation1, const string &roration2)
Definition: functions.hpp:874
string fingerprint
Definition: functions.hpp:864
int number_of_vertices
Definition: functions.hpp:865
string first_rotation
Definition: functions.hpp:867
string result
Definition: functions.hpp:868
smart_permutations(const string &fingerprint, int number_of_vertices)
Definition: functions.hpp:893
string next()
Definition: functions.hpp:902