/***** Claire Pennarun, November 2016 TO COMPILE THE FILE: g++ -std=c++11 PeoGeneration.cpp -o peo TO EXECUTE: ./peo k (where k is the number of edges of the wanted maps) *****/ #include #include #include #include #include #include #include #include #include using namespace std; #define T unsigned long long int #define S 128 static T computeNewPathSplit(int length, bitset& path, int pos, int dir){ string f_path = path.to_string(); stringstream s_res; string sub = f_path.substr(f_path.size()- length + pos, f_path.npos); s_res << dir; s_res << sub; bitset new_path(string(s_res.str())); return new_path.to_ulong(); } vector splitChildren(int length, bitset& path){ short int sum = 0; vector res; res.reserve(length/2); string path_string = path.to_string(); string subs = path_string.substr(path_string.size()-length,path_string.npos); int dir; for(int i = 0; i < subs.size(); i++){ (subs[i] == '0' ? sum += 1 : sum -= 1); if(sum == 1 || sum == -1){ dir = ((sum==1)?0:1); T child = computeNewPathSplit(length, path, i+1, dir); res.push_back(child); } } return res; } vector concatene(int length, bitset& path, int length2, bitset& path2){ vector liste_res; liste_res.reserve(2); string f_path = path.to_string(); string s_path = path2.to_string(); stringstream res_path; res_path << 0; res_path << f_path.substr(f_path.size()-length,f_path.npos); res_path << 1; res_path << s_path.substr(s_path.size()-length2,s_path.npos); bitset new_path(string(res_path.str())); T res1 = new_path.to_ulong(); liste_res.push_back(res1); stringstream res_path2; res_path2 << 1; res_path2 << f_path.substr(f_path.size()-length,f_path.npos); res_path2 << 0; res_path2 << s_path.substr(s_path.size()-length2,s_path.npos); bitset new_path2(string(res_path2.str())); T res2 = new_path2.to_ulong(); liste_res.push_back(res2); return liste_res; } static T firstLoop(int length, bitset& path, bool dir){ int or_s; (dir ? or_s = 0: or_s=1); stringstream res_s; string tmp = path.to_string(); res_s << or_s; res_s << 1-or_s; res_s << tmp.substr(tmp.size()-length,tmp.npos); bitset res(string(res_s.str())); return res.to_ulong(); } static T lastLoop(int length, bitset& path, bool dir){ int or_s; (dir ? or_s = 0: or_s=1); string tmp = path.to_string(); stringstream res_s; res_s << or_s; res_s << tmp.substr(tmp.size()-length,tmp.npos); res_s << 1-or_s; bitset res(string(res_s.str())); return res.to_ulong(); } vector allLoopsChildren(int length, bitset& path){ vector v_res; v_res.reserve(4); v_res.push_back(firstLoop(length, path, false)); v_res.push_back(firstLoop(length, path, true)); if(length != 0){ v_res.push_back(lastLoop(length, path, false)); v_res.push_back(lastLoop(length, path, true)); } return v_res; } T generation_next(vector< unordered_map >& liste_gen, int k){ cout << "********" << endl << "computing generation " << k << endl; // If the orientation results from the addition of a loop or from a split on // a orientation with k-1 edges for (auto it : liste_gen[k-1]){ int i = it.first; bitset b_set(i); vector splits = splitChildren(2*b_set.count(), b_set); // splits for(auto d:splits) liste_gen[k][d] += liste_gen[k-1][i]; vector loops = allLoopsChildren(2*b_set.count(), b_set); // loops for(auto d:loops) liste_gen[k][d] += liste_gen[k-1][i]; } // If the orientation results from merging two orientations A and B with // respectively i and j edges (i+j = k-1) for(int i = 1; i <= k-2; i++){ int j = k-1-i; for (auto it2 : liste_gen[i]){ int m = it2.first; bitset b_set1(m); for(auto it3 : liste_gen[j]){ int l = it3.first; bitset b_set2(l); vector first_cont = concatene(2*b_set1.count(), b_set1, 2*b_set2.count(), b_set2); for(auto d:first_cont) liste_gen[k][d] += liste_gen[i][m] * liste_gen[j][l]; } } } T sum = 0; for(auto it4 :liste_gen[k]){ int i = it4.first; sum += liste_gen[k][i]; } return sum; } int main(int argc, char* argv[]){ if(argc < 2) cout << "an argument is needed!" << endl; int gen_max = atoi(argv[1]); vector< unordered_map > liste_gen; for(int i=0; i <= gen_max; i++){ unordered_map temp; liste_gen.push_back(temp); } liste_gen[0][0] = 1; for(int k = 1; k <= gen_max; k++) cout << generation_next(liste_gen, k) << " planar Eulerian orientations with " << k << " edges" << endl; }