11 #include <unordered_map>
20 #define M_PI 3.14159265358979323846
24 #define SIZE_OF_ARRAY 10
31 using array_4D = vector<vector<vector<vector<bool> > > >;
61 int number_of_vertices = 0;
78 graph(
int n,
int i, shared_ptr<canonic_wraper> shared_canonics) {
80 canonic_fingerprints_wraper = shared_canonics;
82 number_of_vertices = n;
83 outer_face = make_shared<Face>();
85 starts.resize(number_of_vertices);
86 for (
int i = 0; i < number_of_vertices;i++) {
87 starts[i].resize(number_of_vertices);
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;
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);
110 cout <<
"opened " << output_path << endl;
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);
119 void delete_edge_back(
bool outer_face_bool =
false);
120 void delete_vertex(
Vertex* a);
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);
150 bool is_correct_fingerprint(
const string& fingerprint);
151 void create_all_possible_drawings();
153 string find_canonic_fingerprint(
const string& fingerprint);
155 bool is_some_of_faces_incorrect(
Edge* edge);
156 bool is_face_incorrect(shared_ptr<Face> face);
158 void print_counters(
Face* f);
186 counter_of_same_last_edges[i] = 0;
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) {}
217 return (from_ == a.
from_ && to_ == a.
to_);
221 return !(*
this == a);
227 cout <<
"number of edges: " << g->
edges.size() << endl;
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;
239 for (
int i = 0; i < number_of_vertices - 1;i++)
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) {
255 Edge* toa =
nullptr, * tob =
nullptr, * froma =
nullptr, * fromb =
nullptr;
263 auto new_face = !outer_face_bool ? make_shared<Face>() : outer_face;
265 Edge ab_edge(fromb, toa,
nullptr, a, b, face, a_index*100 + b_index);
266 edges.push_back(ab_edge);
267 Edge* ab_edge_ptr = &edges.back();
268 segments.push_back(ab_edge_ptr);
272 Edge ba_edge(froma, tob, ab_edge_ptr, b, a, new_face, b_index*100 + a_index);
273 edges.push_back(ba_edge);
274 Edge* ba_edge_ptr = &edges.back();
275 segments.push_back(ba_edge_ptr);
280 new_face->edge_ = ba_edge_ptr;
283 froma->
prev_ = ba_edge_ptr;
284 toa->
next_ = ab_edge_ptr;
285 fromb->
prev_ = ab_edge_ptr;
286 tob->
next_ = ba_edge_ptr;
290 if (!outer_face_bool) {
291 auto start_edge = ba_edge_ptr;
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)]++;
298 cur_edge = cur_edge->next_;
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];
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)]++;
314 face->edge_ = ab_edge_ptr;
329 auto a = edge->
from_;
332 auto new_vertex = make_shared<Vertex>(edge);
333 new_vertex->index_ = -1;
336 auto tob = &edges.back();
337 segments.push_back(tob);
339 edges.push_back(
Edge(opposite->next_, opposite, edge, new_vertex, a, opposite->
face_, opposite->index_));
340 auto toa = &edges.back();
341 segments.push_back(toa);
343 edge->
to_ = new_vertex;
347 opposite->
to_ = new_vertex;
348 opposite->next_ = toa;
349 opposite->opposite_ = tob;
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)]++;
365 auto edge = edges.back();
366 auto opposite = *edge.opposite_;
371 auto face = edge.face_;
373 auto froma = opposite.next_;
374 auto toa = edge.prev_;
375 auto fromb = edge.next_;
376 auto tob = opposite.prev_;
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)]++;
387 cur_edge = cur_edge->next_;
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)]--;
412 segments.pop_back();segments.pop_back();
413 edges.pop_back();edges.pop_back();
423 auto edge = vertex->
to_;
426 auto tob = edge->
next_;
435 edge_opposite->to_ = a;
436 edge->next_ = tob->next_;
437 edge_opposite->next_ = toa->next_;
440 edge->opposite_ = edge_opposite;
441 edge_opposite->opposite_ = edge;
447 edge->face_->edge_ = edge;
448 edge_opposite->face_->edge_ = edge_opposite;
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)]--;
456 segments.pop_back(); segments.pop_back();
457 edges.pop_back(); edges.pop_back();
467 vector<shared_ptr<Vertex> > special_vertices;
470 for (
int i = 0; i < number_of_vertices - 1;i++) {
471 auto new_vertex = make_shared<Vertex>();
472 new_vertex->index_ = index;
473 special_vertices.push_back(new_vertex);
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());
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_;
493 outer_face->edge_ = &edges.back();
503 for(
int i = 0; i < number_of_vertices;i++){
504 for (
int j = 0; j < number_of_vertices - 1;j++) {
505 starts[i][fingerprint[i * (number_of_vertices - 1) + j] -
'0'] = i * (number_of_vertices - 1) + j;
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);
524 for (
int i = 0; i < number_of_vertices;i++) {
525 create_special_vertex(i);
541 auto seg = segments[s_index]->next_;
547 while (seg != segments[s_index]) {
549 if (seg == segments[t_index]) {
551 add_edge(segments[s_index]->from_, segments[t_index]->from_, segments[s_index]->face_, a, b);
554 if (b < number_of_vertices - 2) {
555 find_the_way_to_intersect(starts[a][b + 1], starts[b + 1][a], a, b + 1);
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);
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);
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);
587 auto index_first_end = seg->index_ / 100;
588 auto index_second_end = seg->index_ % 100;
590 if (!blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)]) {
595 blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] =
true;
597 add_edge(segments[s_index]->from_, segments[edges.size() - 1]->from_, segments[s_index]->face_, a, b);
602 segments[edges.size() - 3]->from_->to_ = segments[edges.size() - 3]->prev_;
604 if(max(a, b) != number_of_vertices - 1 || !is_some_of_faces_incorrect(segments[edges.size() - 2])){
607 find_the_way_to_intersect(edges.size() - 3, t_index, a, b);
609 blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] =
false;
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;
637 if(is_face_incorrect(edge->
face_) || is_face_incorrect(opposite->face_)){
652 for(
int i = 0; i < number_of_vertices - 1;i++){
653 if (face->counter_of_same_last_edges[i] >= 2)
657 sum += (face->counter_of_same_last_edges[i] > 0);
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";
692 input_file.open(input_path);
694 cout <<
"opened also " << input_path << endl;
696 string rotation_system;
697 if (!getline(input_file, rotation_system)) {
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));
705 string last_rotation;
706 for (
int i = 0; i < n - 1;i++)
707 last_rotation += (i +
'0');
709 fingerprint.push_back(last_rotation);
711 for (
int i = 0; i < n;i++) {
723 for_each(fingerprint.begin(), fingerprint.end(), [&](
const string& part) {res += part;});
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) {
729 next_permutation(fingerprint[i].begin() + 1, fingerprint[i].end());
733 next_permutation(fingerprint[i].begin() + 1, fingerprint[i].end());
738 if (states[i] == (treshold - 2) - 1) {
740 string rotation_system;
741 if (!getline(input_file, rotation_system)) {
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));
751 string last_rotation;
752 for (
int i = 0; i < treshold - 1;i++)
753 last_rotation += (i +
'0');
755 fingerprint.push_back(last_rotation);
758 for (
int i = 0; i < treshold;i++) {
764 fingerprint[i] = fingerprint[i][0] + fingerprint[i].substr(2) + fingerprint[i][1];
768 swap(fingerprint[i][(treshold - 2) - states[i]], fingerprint[i][(treshold - 2) - (states[i] + 1)]);
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;
805 auto generator_of_fingerprints =
fingerprints(number_of_vertices, index);
807 while (!generator_of_fingerprints.done) {
808 auto fingerprint = generator_of_fingerprints.get_next();
811 if (!is_correct_fingerprint(fingerprint))
continue;
815 fingerprint = find_canonic_fingerprint(fingerprint);
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;
826 create_all_special_vertices();
827 recolor_fingerprint(fingerprint);
832 find_the_way_to_intersect(starts[1][2], starts[2][1], 1, 2);
836 cout <<
"yes" << endl;
837 output_file << fingerprint <<
"\n";
840 edges.resize(0); segments.resize(0);
842 outer_face = make_shared<Face>();
847 cout <<
"realized " << realized << endl;
872 int counter_rotation = 0;
876 string permutation =
"";
877 for (
int i = 0; i < number_of_vertices;i++)
878 permutation += (i +
'0');
880 int sum_r1 = ((number_of_vertices - 1) * (number_of_vertices))/ 2;
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');
889 permutation[sum_r1] = sum_r2 +
'0';
894 this->fingerprint = fingerprint;
895 this->number_of_vertices = number_of_vertices;
897 for (
int i = 1; i < number_of_vertices;i++)
898 first_rotation += (i +
'0');
904 result = create_permutation(fingerprint.substr((number_of_vertices - 1) * counter, number_of_vertices - 1), first_rotation);
907 if (invers && counter == number_of_vertices - 1 && counter_rotation == number_of_vertices - 2) {
912 if (invers && counter_rotation == number_of_vertices - 2) {
915 counter_rotation = 0;
918 for (
int i = 1; i < number_of_vertices;i++)
919 first_rotation += (i +
'0');
921 else if (counter_rotation == number_of_vertices - 2) {
922 counter_rotation = 0;
925 first_rotation =
"1";
926 for (
int i = 1; i < number_of_vertices - 1;i++)
927 first_rotation += ((number_of_vertices - i) +
'0');
933 rotate(first_rotation.begin(), first_rotation.begin() + 1, first_rotation.end());
949 auto min_fingerprint = fingerprint;
950 auto cur_fingerprint = fingerprint;
951 auto new_fingerprint = fingerprint;
954 auto permutation_holder = permutations.next();
956 cur_fingerprint = fingerprint;
957 new_fingerprint = fingerprint;
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;
964 if (permutation_holder[cur_fingerprint[index] -
'0'] ==
'0'
965 || (rotation_index == -1 && permutation_holder[cur_fingerprint[index] -
'0'] ==
'1')) rotation_index = j;
967 cur_fingerprint[index] = permutation_holder[cur_fingerprint[index] -
'0'];
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));
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);
979 min_fingerprint = min(min_fingerprint, new_fingerprint);
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);
987 min_fingerprint = min(min_fingerprint, new_fingerprint);
989 }
while (!permutations.done);
992 return min_fingerprint;
1002 for (
int i = 0; i < str.length(); i++)
1005 rotate(str.begin(), str.begin() + 1, str.end());
1008 if (str.compare(min) < 0)
1021 int number_of_positive_rotation = 0;
1023 for (
int i = 0; i < 4;i++) {
1026 for_each(orders[i].begin(), orders[i].end(), [&](
int part) {rotation += to_string(part);});
1029 if (minimal_rotation[1] < minimal_rotation[2])
1030 number_of_positive_rotation++;
1033 if (number_of_positive_rotation % 2 == 0)
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]++) {
1053 vector<int> order[4];
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]
1060 || fingerprint[u + i[v] * (number_of_vertices - 1)] -
'0' == i[(3 + v) % 4])
1062 order[v].push_back(fingerprint[u + i[v] * (number_of_vertices - 1)] -
'0');
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