#include #include #include #include #include #include #include #include #include #include #include using namespace std; #include "torus-common.h" /* Returns true if in any 4-critical triangle-free graph H represented by a template with face F, F is also a face in H. This is the case if |f| <= 5, or if theta(f)={|f|}. */ static bool is_empty_face (const face &f) { int len = f.length (); if (len <= 5) return true; if (f.num_floating (len) == 0) return false; assert (f.num_floating (len) == 1 && f.floating_faces.size () == 1); return true; } /* The same, but FLFACES maps ids to values. */ static bool is_empty_face_un (const face &f, const vector &flfaces) { int len = f.length (); if (len <= 5) return true; if (f.floating_faces.size () != 1) return false; int id = f.floating_faces.begin ()->first; return flfaces[id] == len; } /* Returns true if the face F is quadrangulated in any represented graph, i.e., if theta(F)=empty set. */ static bool is_quadrangulated_face (const face &f) { return f.floating_faces.empty (); } /* Replaces the ids of elements of theta functions in the template G by the lengths stored in FACES. Converse to assign_flface_numbers. */ static void replace_floating_by_lengths (surf_graph *g, const vector &faces) { for (int f = 0; f < g->nfs (); f++) { if (!g->fs[f].es) continue; flfmap ff = g->fs[f].floating_faces; g->fs[f].floating_faces.clear (); for (flfmap::iterator i = ff.begin (); i != ff.end (); ++i) g->fs[f].add_floating (faces[i->first]); } } /* Finds a critical subtemplate of G, and if not yet seen before, adds it to a queue of templates to process. */ static rct obstrs_reg; static vector to_process; static void add_obstr (surf_graph *g) { assert (!g->is_colorable_wno ()); g->minimize (); assert (g->is_minimal ()); vector code; g->get_min_code (code); #pragma omp critical { if (!register_cd (obstrs_reg, code)) { to_process.push_back (g); for (vector::iterator i = code.begin (); i != code.end (); ++i) printf (" %d", *i); printf ("\n"); fflush (stdout); } else delete g; } } /* Replaces the values in the multisets assigned by the theta function of the template G by unique identifiers, and stores the values at the corresponding places in the FACES vector. */ static void assign_flface_numbers (surf_graph *g, vector &faces) { for (int f = 0; f < g->nfs (); f++) { if (!g->fs[f].es) continue; flfmap ff = g->fs[f].floating_faces; g->fs[f].floating_faces.clear (); for (flfmap::iterator i = ff.begin (); i != ff.end (); ++i) { if (i->first < 5 || i->first > 7) abort (); for (int j = 0; j < i->second; j++) { int a = faces.size (); faces.push_back (i->first); g->fs[f].add_floating (a); } } } } /* Finds an edge in the template G that corresponds to the edge E of a subtemplate of G. */ static edge * transl_edge (edge *e, surf_graph *g) { int u = e->opp->to; int v = e->to; return g->vs[u].edge_to (v); } /* Returns true if a 4-critical triangle-free graph embedded in a surface can contain a closed walk of length LEN bounding a disk with faces of INSIDE in it. FACES maps ids of faces to lengths. */ static bool valid_disk (int len, const flfmap &inside, const vector *faces) { int n[3] = {0, 0, 0}; for (auto i : inside) { if (faces) n[(*faces)[i.first] - 5] += i.second; else n[i.first - 5] += i.second; } if ((len & 1) != ((n[0]+n[2]) & 1)) return false; return len >= mincrit_oface (n[0], n[1], n[2]); } /* Callback for valid_obstacle. */ struct sepcycle_test : public elist_test { surf_graph *g; const vector *faces; sepcycle_test (surf_graph *_g, const vector *fs) : g (_g), faces (fs) { } virtual bool operator() (vector &cyc) { int len = cyc.size (); if (len <= 3) return true; flfmap inside; int nin = g->vs_inside_cycle (cyc, &inside); if (nin < 0) return false; if (len <= 5 && nin > 0) return true; return !valid_disk (len, inside, faces); } }; /* Tests whether the template G can represent a triangle-free 4-critical graph, by testing whether short separating cycles do not contain too many/too large theta elements inside. FACES records the lengths assigned to the theta elements. */ static bool valid_obstacle (surf_graph *g, const vector *faces) { for (int f = 0; f < g->nfs (); f++) if (g->fs[f].es && !valid_disk (g->fs[f].length (), g->fs[f].floating_faces, faces)) return false; sepcycle_test test (g, faces); if (g->cycles (8, test)) return false; return true; } /* Callback for extendable_3coloring_wn. */ struct exists_coloring_check_wno_un_winding : public coloring_callback { surf_graph *g; const vector *flfaces; const map *winding; exists_coloring_check_wno_un_winding (surf_graph &_g, const vector &_f, const map &_w) : g(&_g), flfaces(&_f), winding (&_w) { } virtual bool operator() (unsigned col[]) { for (int f = 0; f < g->nfs (); f++) { if (!g->fs[f].es) continue; int w = g->winding_number (f, col, NULL); bool any_unset = false, any_set = false; int wset = 0; for (auto i : g->fs[f].floating_faces) { int el = i.first; if (winding->count (el) > 0) { wset += winding->at (el); any_set = true; } else any_unset = true; } assert (!any_set || !any_unset); if (any_unset) { if (!check_winding_number (g->fs[f].floating_faces, w, flfaces)) return false; } else if (w != wset) return false; } return true; } }; /* Tests whether the coloring COL of a subtemplate of G extends to G so that the winding numbers assigned to some of the faces are given in WINDING. FLFACES maps the ids of elements in the theta function to lengths. */ static bool extendable_3coloring_wn (const vector &flfaces, surf_graph *g, const coloring &col, const map &winding) { exists_coloring_check_wno_un_winding cb (*g, flfaces, winding); unsigned color[g->nvs ()]; return g->find_coloring (color, cb, col); } /* Record of a region of a template that can be traversed by a path. */ struct traversable_region { edge *tgt; set faces; set vertices; set tgt_angle; void reach (int v) { vertices.erase (v); } bool operator()(int f) const { return faces.count (f) > 0; } bool operator()(int f, edge *to) const { if (faces.count (f) == 0) return false; if (to->to != tgt->to) return vertices.count (to->to) > 0; return to->opp->to == tgt->opp->to || tgt_angle.count (to->opp->to) > 0; } bool operator()(edge *e) const { if (e->to != tgt->to) return vertices.count (e->to) > 0; return tgt_angle.count (e->opp->to) > 0; } }; /* Marks in TRAV the part of the template G that can be traversed by a path from F to T in the face to their left in a subtemplate. FLFACES maps the ids of elements in the theta function to lengths. */ static void mark_traversable_edges_and_faces (const vector &flfaces, surf_graph *g, edge *f, edge *t, traversable_region &trav) { trav.tgt = t; vector boundary; for (edge_iter_face e(f); !e.end_p (); ++e) boundary.push_back (transl_edge (*e, g)); g->mark_interior (boundary); for (int a = 0; a < g->nfs (); a++) if (g->fs[a].seen) { for (edge_iter_face ei(g->fs[a]); !ei.end_p (); ++ei) { edge *e = *ei; if (!g->vs[e->to].seen) trav.vertices.insert (e->to); } if (!is_empty_face_un (g->fs[a], flfaces)) trav.faces.insert (a); } edge *el = transl_edge (t->face_next ()->prev, g); edge *el_lst = transl_edge (t->opp, g); for (; el != el_lst; el = el->prev) trav.tgt_angle.insert (el->to); } /* Returns false if we can determine that it is not possible to add a path from V to T of length LEN in the template G, across faces and edges marked in TRAV. */ static bool trace_traversable_path (surf_graph *g, const traversable_region &trav, int v, int t, int len) { if (len == 0) return v == t; if (v == t) return false; for (edge_iter_nbr ei(g->vs[v]); !ei.end_p (); ++ei) { edge *e = *ei; if (trav (e) && trace_traversable_path (g, trav, v, e->to, len - 1)) return true; int f = e->left; if (!trav (f)) continue; int flen = g->fs[f].length (), d = 1; bool must_be_even = is_quadrangulated_face (g->fs[f]); for (edge *te = e; te != e->face_prev (); te = te->face_next (), d++) { if (!trav (f, te)) continue; int od = min (d, flen - d); int sl = max (1, 4 - od); if (must_be_even && ((sl + od) & 1) == 1) sl++; int step = must_be_even ? 2 : 1; for (int l = sl; l <= len; l += step) if (trace_traversable_path (g, trav, te->to, t, len - l)) return true; } } return false; } /* Add path splitting through the face from F to T, of length LEN, with the elements of theta marked in LFTFS moved to the region on the left of the path. */ struct kill_path { edge *f, *t; int len; vector lftfs; kill_path (edge *_f, edge *_t, int _len, const vector &_lft) : f(_f), t(_t), len(_len), lftfs(_lft) { } /* Returns false if we can determine that it is not possible to add this path to a supertemplate G. FLFACES maps the ids of elements in the theta function to lengths. */ bool plausible (const vector &flfaces, surf_graph *g) { traversable_region trav; mark_traversable_edges_and_faces (flfaces, g, f, t, trav); return trace_traversable_path (g, trav, f->to, t->to, len); } }; typedef list kill_paths; typedef map wn_assignment; struct wnas_subset { vector lftfs; int rwno; wnas_subset (int n) : lftfs (n, false), rwno(0) { } }; /* Adds to KPS all kill paths from F to T (arc between them has winding number ARCW) that kill the partition of the theta elements described in S. */ static void gen_kill_paths (edge *f, edge *t, int arcw, const wnas_subset &s, kill_paths &kps) { for (int len = abs (arcw - s.rwno) - 2; len > 0; len -= 2) kps.emplace_back (kill_path (f, t, len, s.lftfs)); } /* Adds all subsets of the winding number assignment to faces between BEG and END to ACT and stores the results in PART. */ static void gen_wnas_subsets (wn_assignment::const_iterator beg, wn_assignment::const_iterator end, wnas_subset &act, list &part) { if (beg == end) { part.push_back (act); return; } int id = beg->first; int val = beg->second; ++beg; wnas_subset l(act), r(act); l.lftfs[id] = true; r.rwno += val; gen_wnas_subsets (beg, end, l, part); gen_wnas_subsets (beg, end, r, part); } /* Adds to KPS all paths that can prevent COL from coloring the subgraph drawn inside the face F with a given assignment WNAS of winding numbers to the theta elements. TOT gives the total number of theta elements in the whole graph. */ static void paths_killing_wn_assignment (face &f, unsigned col[], const wn_assignment &wnas, int tot, kill_paths &kps) { list part; wnas_subset act (tot); gen_wnas_subsets (wnas.begin (), wnas.end (), act, part); int a = 0; for (edge_iter_face i1(f); !i1.end_p (); ++i1, a++) (*i1)->cid = a; for (edge_iter_face i1(f); !i1.end_p (); ++i1) { edge *ef = *i1; int arcw = 0; for (edge *et = ef->face_next (); et != ef; et = et->face_next ()) { arcw += elwind (col[et->opp->to], col[et->to]); if (ef->cid < et->cid) for (wnas_subset &s : part) gen_kill_paths (ef, et, arcw, s, kps); } } } /* Stores in WNAS all possible assignments of winding numbers extending act to faces between BEG and END (whose lengths are given in FLFACES) summing to WNO. */ static void winding_number_assignments (const vector &flfaces, int wno, flfmap::const_iterator beg, flfmap::const_iterator end, wn_assignment &act, list &wnas) { if (beg == end) { if (wno == 0) wnas.emplace_back (act); return; } int af = beg->first; int afl = flfaces[af]; ++beg; int s, t; if (afl == 5 || afl == 7) { s = -3; t = 3; } else { assert (afl == 6); s = -6; t = 6; } for (int a = s; a <= t; a += 6) { wn_assignment nw(act); nw[af] = a; winding_number_assignments (flfaces, wno - a, beg, end, nw, wnas); } } /* Stores in WNAS all possible assignments of winding numbers to faces in FLF (whose lengths are given in FLFACES) summing to WNO. */ static void winding_number_assignments (const flfmap &flf, const vector &flfaces, int wno, list &wnas) { wn_assignment act; winding_number_assignments (flfaces, wno, flf.begin (), flf.end (), act, wnas); } struct way_wn { wn_assignment winding_numbers; kill_paths kps; way_wn (wn_assignment &_w, kill_paths &_k) : winding_numbers (_w), kps (_k) { } }; /* A way how to kill a 3-coloring. */ struct way { /* The face to that the paths should be added. */ int f; /* For each assignment of winding numbers to the elements of theta(f), which paths can be used to prevent the coloring to extend with this winding number assignment? */ list wn_kills; way (surf_graph *g, const vector &flfaces, int _f, unsigned col[]) : f(_f), wn_kills () { int w = g->winding_number (f, col); list pos_wnos; winding_number_assignments (g->fs[f].floating_faces, flfaces, w, pos_wnos); for (wn_assignment &wnas : pos_wnos) { kill_paths kps; paths_killing_wn_assignment (g->fs[f], col, wnas, flfaces.size (), kps); wn_kills.emplace_back (way_wn (wnas, kps)); } } void get_paths (list &ps) { for (way_wn &i : wn_kills) ps.push_back (&i.kps); } /* Delete parts of the plan to kill the coloring COL which are impossible to realize or whose goals were already achieved in the supertemplate G. FLFACES maps the ids of elements in the theta function to lengths. */ void prune (const vector &flfaces, surf_graph *g, const coloring &col) { for (list::iterator a = wn_kills.begin (); a != wn_kills.end (); ) { way_wn &w = *a; if (!extendable_3coloring_wn (flfaces, g, col, w.winding_numbers)) { a = wn_kills.erase (a); continue; } for (kill_paths::iterator p = w.kps.begin (); p != w.kps.end (); ) { if (!p->plausible (flfaces, g)) p = w.kps.erase (p); else ++p; } ++a; } assert (!wn_kills.empty ()); } int complexity (void) { int c = 1; for (way_wn &i : wn_kills) c *= i.kps.size (); return c; } }; /* Distribute the elements of theta functions in the template G according to the possibilities listed in POS; faces for some elements are already fixed in THELMAP. Store all valid results in WITH_P. FLFACES maps the ids of elements in the theta function to lengths. */ static void distribute_floating (const vector &flfaces, surf_graph *g, vector &thelmap, const vector > &pos, list &with_p) { if (thelmap.size () < flfaces.size ()) { int a = thelmap.size (); thelmap.push_back (0); for (int i : pos[a]) { thelmap[a] = i; distribute_floating (flfaces, g, thelmap, pos, with_p); } thelmap.pop_back (); return; } surf_graph *ng = new surf_graph (*g); for (int f = 0; f < ng->nfs (); f++) ng->fs[f].floating_faces.clear (); int n = thelmap.size (); for (int i = 0; i < n; i++) ng->fs[thelmap[i]].add_floating (i); if (valid_obstacle (ng, &flfaces)) with_p.push_back (ng); else delete ng; } /* We have added the path PTH to the template G, implementing the path described (with respect to a subtemplate) by P. Distribute the elements of theta functions in the newly created faces in all possible ways matching P.lftfs, and store the results in WITH_P. FLFACES maps the ids of elements in the theta function to lengths. */ static void distribute_floating (const vector &flfaces, surf_graph *g, const vector &pth, const kill_path &p, list &with_p) { /* Find the boundary of the region to the left of PTH. */ vector boundary; assert ((int) pth.size () == p.len + 1); for (int i = 1; i <= p.len; i++) boundary.push_back (g->vs[pth[i-1]].edge_to (pth[i])); for (edge *e = p.t; e != p.f; e = e->face_next ()) boundary.push_back (transl_edge (e->face_next (), g)); g->mark_interior (boundary); /* Gather possible faces in which the elements of theta functions may lie. */ int imthe = flfaces.size (); vector > pos (imthe); for (int f = 0; f < g->nfs (); f++) if (g->fs[f].es) for (auto i : g->fs[f].floating_faces) { if (g->fs[f].seen && !p.lftfs[i.first]) continue; if (!g->fs[f].seen && p.lftfs[i.first]) continue; if (flfaces[i.first] > g->fs[f].length ()) continue; pos[i.first].push_back (f); } for (int i = 0; i < imthe; i++) if (pos[i].empty ()) return; vector thelmap; distribute_floating (flfaces, g, thelmap, pos, with_p); } /* Adds a path described by P (with respect to a subtemplate, across faces and edges marked in TRAV) to a template G in all possible ways, storing the results in WITH_P; part of the added path described in PTH has already been constructed, LEN edges need to be added yet. FLFACES maps the ids of elements in the theta function to lengths. */ static void add_traversable_path (const vector &flfaces, surf_graph *g, const traversable_region &trav, const vector &pth, int len, const kill_path &p, list &with_p) { int t = p.t->to; int v = pth.back (); if (len == 0) { if (v == t) distribute_floating (flfaces, g, pth, p, with_p); return; } if (v == t) return; for (edge_iter_nbr ei(g->vs[v]); !ei.end_p (); ++ei) { edge *e = *ei; if (trav (e)) { vector npt (pth); traversable_region ntrav (trav); npt.push_back (e->to); ntrav.reach (e->to); add_traversable_path (flfaces, g, ntrav, npt, len - 1, p, with_p); } int f = e->left; if (!trav (f)) continue; bool must_be_even = is_quadrangulated_face (g->fs[f]); int d = 1; for (edge *te = e; te != e->face_prev (); te = te->face_next (), d++) { if (!trav (f, te)) continue; int od = g->distance (v, te->to); int sl = max (1, 4 - od); if (must_be_even && ((sl + d) & 1) == 1) sl++; int step = must_be_even ? 2 : 1; for (int l = sl; l <= len; l += step) { vector npt (pth); traversable_region ntrav (trav); surf_graph *ng = new surf_graph (*g); flfmap mr; vector nwe; ng->split_face (transl_edge (e->face_prev (), ng), transl_edge (te, ng), l, mr, nwe); /* We now use floating_faces to record all theta element ids that could potentially be contained in the face. */ edge *fe = nwe.front (); int fl = fe->left, fr = fe->opp->left; ng->fs[fr].floating_faces = ng->fs[fl].floating_faces; /* Update traversable faces conservatively. */ if (ng->fs[fl].length () <= 5) ntrav.faces.erase (fl); if (ng->fs[fr].length () > 5) ntrav.faces.insert (fr); ntrav.reach (te->to); for (edge *pe : nwe) npt.push_back (pe->to); add_traversable_path (flfaces, ng, ntrav, npt, len - l, p, with_p); delete ng; } } } } /* Adds a path described by P (with respect to a subtemplate) to a template G in all possible ways, storing the results in WITH_P. FLFACES maps the ids of elements in the theta function to lengths. */ static void add_killing_path (const vector &flfaces, surf_graph *g, kill_path &p, list &with_p) { traversable_region trav; mark_traversable_edges_and_faces (flfaces, g, p.f, p.t, trav); vector apath{p.f->to}; add_traversable_path (flfaces, g, trav, apath, p.len, p, with_p); } /* Adds to ADDED all the ways how to add paths to the template G as described in the list between A and EN (with respect to its subtemplate). FLFACES maps the ids of elements in the theta function to lengths. */ static void add_killing_paths_list (const vector &flfaces, surf_graph *g, list::iterator a, list::iterator en, list &added) { if (a == en) { added.push_back (new surf_graph (*g)); return; } list::iterator nx = a; ++nx; for (kill_path &p : **a) if (p.plausible (flfaces, g)) { list with_p; add_killing_path (flfaces, g, p, with_p); for (surf_graph *h : with_p) { add_killing_paths_list (flfaces, h, nx, en, added); delete h; } } } /* Adds to ADDED all the ways how to add paths to the template G as described in W (with respect to its subtemplate). FLFACES maps the ids of elements in the theta function to lengths. */ static void add_killing_paths (const vector &flfaces, surf_graph *g, way &w, list &added) { list to_add; w.get_paths (to_add); add_killing_paths_list (flfaces, g, to_add.begin (), to_add.end (), added); } /* Callback for extendable_3coloring. */ struct exists_coloring_check_wno_un : public coloring_callback { surf_graph *g; const vector *flfaces; exists_coloring_check_wno_un (surf_graph &_g, const vector &_f) : g(&_g), flfaces(&_f) { } virtual bool operator() (unsigned col[]) { return g->check_winding_numbers (col, NULL, flfaces); } }; /* Tests whether the coloring COL of a subtemplate of G extends to G. FLFACES maps the ids of elements in the theta function to lengths. */ static bool extendable_3coloring (const vector &flfaces, surf_graph *g, const coloring &col) { exists_coloring_check_wno_un cb (*g, flfaces); unsigned color[g->nvs ()]; return g->find_coloring (color, cb, col); } /* A 3-coloring of a template and all possible ways how to extend the template so that it is no longer its 3-coloring. */ struct plan { coloring col; list ways; int complexity; plan (unsigned c[], int n) : col (c, c + n) { } void update_complexity (void) { complexity = 0; for (way &w : ways) complexity += w.complexity (); } /* Delete parts of the plan which are impossible to realize or whose goals were already achieved in the supertemplate G. FLFACES maps the ids of elements in the theta function to lengths. */ void prune (const vector &flfaces, surf_graph *g) { for (list::iterator w = ways.begin (); w != ways.end (); ) { w->prune (flfaces, g, col); /* If it is no longer possible to kill the coloring within the face considered by W, delete W. */ if (w->complexity () == 0) w = ways.erase (w); else ++w; } update_complexity (); } /* Determine and record in WAYS the ways how to prevent the coloring COL from extending in a supertemplate of the template G. FLFACES maps the ids of elements in the theta function to lengths. */ void determine_ways_to_kill (surf_graph *g, const vector &flfaces) { unsigned c[g->nvs ()]; for (int i = 0; i < g->nvs (); i++) c[i] = col[i]; for (int f = 0; f < g->nfs (); f++) if (g->fs[f].es && g->fs[f].length () >= 6) { way w (g, flfaces, f, c); if (w.complexity () > 0) ways.emplace_back (w); } update_complexity (); } bool operator<(const plan &p) const { return complexity < p.complexity; } }; /* Callback for collecting all the proper 3-colorings of a template. */ struct collect_colorings : public coloring_callback { surf_graph *g; list *ret; collect_colorings (surf_graph &_g, list &_r) : g(&_g), ret(&_r) { } virtual bool operator() (unsigned col[]) { if (g->check_winding_numbers (col, 0)) ret->emplace_back (plan (col, g->nvs ())); return false; } }; /* Expands the template G to a non-3-colorable one in all possible (non-homeomorphic, minimal) ways, eliminating the remaining colorings of its subtemplate according to the plans stored in PS. FLFACES maps the ids of elements in the theta function to lengths. */ static void expand_to_noncol_with_plans (const vector &flfaces, surf_graph *g, list &ps) { /* No more colorings to kill? */ if (ps.empty ()) { replace_floating_by_lengths (g, flfaces); add_obstr (g); return; } /* Find a coloring which is the hardest to kill. */ list::iterator api = min_element (ps.begin (), ps.end ()); if (api->ways.empty ()) { /* If there is no way to kill this coloring, the template cannot be extended to a non-3-colorable one. */ delete g; return; } plan ap = *api; ps.erase (api); for (way &w : ap.ways) { /* Get all supertemplates that implement the paths described in W. */ list gwkills; add_killing_paths (flfaces, g, w, gwkills); for (surf_graph *gwk : gwkills) { list gwkps; /* Filter out the colorings that no longer extend. */ for (plan &p : ps) if (extendable_3coloring (flfaces, gwk, p.col)) gwkps.emplace_back (p); /* Prune out the ways that are no longer realizable. */ for (plan &p : gwkps) p.prune (flfaces, gwk); expand_to_noncol_with_plans (flfaces, gwk, gwkps); } } delete g; } static rct etonc_codes; static int tot; /* Expands the template G to a non-3-colorable one in all possible (non-homeomorphic, minimal) ways. */ static void expand_to_noncol (surf_graph *g) { #pragma omp critical { tot++; } /* If the template is not 3-colorable, there is nothing to do. Record some critical subtemplate of G. */ if (!g->is_colorable_wno ()) { add_obstr (g); return; } /* If we have processed the same template before, there is no point in doing so again. */ vector code; g->get_min_code (code); bool seen_before; #pragma omp critical { seen_before = register_cd (etonc_codes, code); } if (seen_before) { delete g; return; } /* Collect the 3-colorings of the template. */ list ps; collect_colorings cb(*g, ps); unsigned color[g->nvs ()]; g->find_coloring (color, cb); /* As different elements in the image of theta of the same value can receive different values in the winding number assignments, we need to keep track of them individually. To achieve this, replace their lengths with unique ids, and store the lengths in the FLFACES array at the corresponding positions. */ vector flfaces; assign_flface_numbers (g, flfaces); /* Determine all the possible ways how to prevent each of the colorings from extending. */ for (plan &p : ps) p.determine_ways_to_kill (g, flfaces); expand_to_noncol_with_plans (flfaces, new surf_graph (*g), ps); delete g; } /* Sets up the theta function of F to be |F|, unless |F| = 4, in which case it is the empty set*/ static void make_face_empty (face &f) { int len = f.length (); f.floating_faces.clear (); if (len > 4) f.add_floating (len); } /* Finds a unique element of the theta function of the template G of value 6 or 7. Returns false if there is no such element, true otherwise. In the latter case, LEN is set to the value of the element and F to the number of the face such that LEN belongs to theta(F). */ static bool large_floating (surf_graph *g, int &f, int &len) { f = -1; for (int a = 0; a < g->nfs (); a++) if (g->fs[a].es) { flfmap &af = g->fs[a].floating_faces; for (flfmap::iterator t = af.begin (); t != af.end (); ++t) { assert (t->first <= 7); if (t->first <= 5) continue; assert (t->second == 1); if (f >= 0) abort (); f = a; len = t->first; } } return f >= 0; } /* Adds all possible boosts of the template G to the list BS. */ static void amplifications (surf_graph *g, vector &s) { if (valid_obstacle (g, NULL)) amps.push_back (new surf_graph (*g)); /* As 5 only amplifies to itself, we only care about values 6 and 7. Since the template is relevant, there can only be one such element. */ int f, len; if (!large_floating (g, f, len)) return; surf_graph *ng; if (len == 6) { /* 6 amplifies to itself or an empty set. */ ng = new surf_graph (*g); ng->fs[f].remove_floating (6); if (valid_obstacle (ng, NULL)) amps.push_back (ng); else delete ng; } if (len == 7) { /* 7 amplifies to itself or 5. */ ng = new surf_graph (*g); ng->fs[f].remove_floating (7); ng->fs[f].add_floating (5); if (valid_obstacle (ng, NULL)) amps.push_back (ng); else delete ng; } } /* Adds all possible boosts of the template G inside face F to the list BS. */ static void boosts (surf_graph *g, int f, list &bs) { bs.push_back (new surf_graph (*g)); if (is_quadrangulated_face (g->fs[f])) return; /* Simplifying things, there should be at most one element of theta(f) of length greater than 5, and this element is 6 or 7. Since 5 only boosts back to 5, we only need to consider this single element. */ int n6 = g->fs[f].num_floating (6); int n7 = g->fs[f].num_floating (7); assert (n6 + n7 <= 1); surf_graph *ng; /* 6 boosts to itself, 5 5, or empty set. */ if (n6) { ng = new surf_graph (*g); ng->fs[f].remove_floating (6); ng->fs[f].add_floating (5, 2); bs.push_back (ng); ng = new surf_graph (*g); ng->fs[f].remove_floating (6); bs.push_back (ng); } /* 7 boosts to itself, 6 5, 5 5 5, or 5. */ if (n7) { ng = new surf_graph (*g); ng->fs[f].remove_floating (7); ng->fs[f].add_floating (6); ng->fs[f].add_floating (5); bs.push_back (ng); ng = new surf_graph (*g); ng->fs[f].remove_floating (7); ng->fs[f].add_floating (5, 3); bs.push_back (ng); ng = new surf_graph (*g); ng->fs[f].remove_floating (7); ng->fs[f].add_floating (5); bs.push_back (ng); } } /* Applies the operation (ii-a) in the template G to edge E and angle EF0->left, adding the results to the queue PARTIALS. */ static void uncontract_and_boost (surf_graph *g, edge *e, edge *ef0, list &partials) { vector es{e, ef0}; surf_graph *ng = new surf_graph (*g, evec_updater (es)); e = es[0]; ef0 = es[1]; ng->shear (e, ef0); boosts (ng, ef0->left, partials); delete ng; } /* Adds partial expansions of template G at a vertex incident with angles to the left of EF0 (marking the face f_0) and E (marking the other angle into which we cut or split) to the queue PARTIALS. */ static void gen_partial_expansions_angles (surf_graph *g, edge *ef0, edge *e, list &partials) { face &fe = g->fs[e->left]; int v = ef0->opp->to; assert (v == e->opp->to); /* The case (i-b) with the edge not present in the template. The revealed edge should be a chord, as otherwise the result is the same as in the case (iii-b). */ if (!is_empty_face (fe)) { /* All non-empty faces of the templates we consider turn out to be quadrangulated, which simplifies the addition (we do not need to worry about distribution of theta(e->left)). */ assert (is_quadrangulated_face (fe)); for (edge *tgt = e->face_next ()->face_next (); tgt != e; tgt = tgt->face_next ()->face_next ()) if (g->distance (v, tgt->to) >= 3) { vector ue{ef0, e->face_prev (), tgt}; surf_graph *with_e = new surf_graph (*g, evec_updater (ue)); flfmap mr; vector nwe; with_e->split_face (ue[1], ue[2], 1, mr, nwe); uncontract_and_boost (with_e, nwe[0], ue[0], partials); delete with_e; } } /* The case (ii-b). We cannot split a 4-face. */ if (!is_quadrangulated_face (fe) && fe.length () >= 6) { /* All non-quadrangulated faces of the templates we consider turn out to be empty, which simplifies the addition (we must add a chord to the face of the template, and the chord dictates the sizes of the faces resulting from the split. */ assert (is_empty_face (fe)); for (edge_iter_face tgt(fe); !tgt.end_p (); ++tgt) if (g->distance (v, (*tgt)->to) >= 3) { vector ue{ef0, e, (*tgt)}; surf_graph *with_e = new surf_graph (*g, evec_updater (ue)); flfmap mr; vector nwe; with_e->split_face (ue[1]->face_prev (), ue[2], 1, mr, nwe); make_face_empty (with_e->fs[nwe[0]->left]); make_face_empty (with_e->fs[nwe[0]->opp->left]); uncontract_and_boost (with_e, nwe[0], ue[0], partials); delete with_e; } } /* The case (iii-b). */ vector ue{ef0, e}; surf_graph *decon = new surf_graph (*g, evec_updater (ue)); int f0, f1; decon->decontract_2path (ue[0], ue[1]->prev, f0, f1); list one_boost; boosts (decon, f0, one_boost); delete decon; for (surf_graph *h : one_boost) { boosts (h, f1, partials); delete h; } } /* Adds partial expansions of template G at the vertex V to the queue PARTIALS. */ static void gen_partial_expansions_vertex (surf_graph *g, int v, list &partials) { for (edge_iter_nbr e1(g->vs[v]); !e1.end_p (); ++e1) { /* The angle corresponding to the face f_0 is to the left of EF0. */ edge *ef0 = *e1; /* The case (i-b) with the edge present in the template. The edge should not be incident with the angle, as otherwise the result is an amplification of a subtemplate of G, which we will consider elsewhere. */ for (edge_iter_nbr e2(g->vs[v]); !e2.end_p (); ++e2) { edge *e = *e2; if (e == ef0 || e == ef0->prev) continue; uncontract_and_boost (g, e, ef0, partials); } for (edge_iter_nbr e2(g->vs[v]); !e2.end_p (); ++e2) { edge *e = *e2; /* In all the cases, the result we would obtain if we selected the same angle as for f_0 would be an amplification of a subtemplate of G. */ if (e == ef0) continue; gen_partial_expansions_angles (g, ef0, e, partials); } } } /* Adds all partial expansions of template G to the queue PARTIALS. */ static void gen_partial_expansions (surf_graph *g, list &partials) { /* Expansion within a face of the template can leave the template unchanged. */ partials.push_back (new surf_graph (*g)); for (int f = 0; f < g->nfs (); f++) if (g->fs[f].es) { /* If the face of the template is also a face of any 4-critical triangle-free graph represented by it, it is not possible to do any partial expansion at a vertex inside this face. If the face is quadrangulated, then any partial expansion within it results in an unchanged template, which we already added. It turns out that all faces of the templates we consider have this property; hence, we do not need to implement the parts (i-a), (ii-a), and (iii-a) of the definition of the partial expansion. */ assert (is_empty_face (g->fs[f]) || is_quadrangulated_face (g->fs[f])); } for (int v = 0; v < g->nvs (); v++) if (g->vs[v].es) gen_partial_expansions_vertex (g, v, partials); } /* Makes a graph G into a template by having the theta function assign to each face f the set {|f|}. */ static void templatify (surf_graph *g) { for (int f = 0; f < g->nfs (); f++) make_face_empty (g->fs[f]); } int main (int argc, char *argv[]) { vector code; int inito; omp_set_dynamic(0); /* Read the basic graphs or templates. */ while (read_code (stdin, code)) { surf_graph *g = new surf_graph (code); /* Unless we pass a parameter to the program, we receive graphs rather than templates as an input. Turn the graphs into templates by setting up theta function assigning to each face f set {|f|}. */ if (argc == 1) templatify (g); add_obstr (g); } inito = obstrs_reg.size (); fprintf (stderr, "%d obsts\n", inito); while (!to_process.empty ()) { fprintf (stderr, "%d to process\n", (int) to_process.size ()); /* For each template in the queue, generate all possible expansions and queue those for processing. */ vector exps; for (surf_graph *g : to_process) { list partials; gen_partial_expansions (g, partials); delete g; for (surf_graph *p : partials) { amplifications (p, exps); delete p; } } to_process.clear (); int ns = exps.size (); int k = 0; #pragma omp parallel for num_threads(15) schedule(dynamic) for (k = 0; k < ns; k++) { #pragma omp critical { fprintf (stderr, " split %d / %d (%d seen %d tot %d top)\n", k, ns, (int) etonc_codes.size (), tot, (int) to_process.size ()); exps[k]->print (stderr); } expand_to_noncol (exps[k]); } } fprintf (stderr, "%d initial obstructions expanded to %d final.\n", inito, (int) obstrs_reg.size ()); return 0; }