lemon/planarity.h
changeset 848 e05b2b48515a
parent 797 30cb42e3e43a
child 828 5fd7fafc4470
equal deleted inserted replaced
0:c1e331e61456 1:dc25a8fbeaef
   135     template <typename Graph>
   135     template <typename Graph>
   136     struct ArcListNode {
   136     struct ArcListNode {
   137       typename Graph::Arc prev, next;
   137       typename Graph::Arc prev, next;
   138     };
   138     };
   139 
   139 
       
   140     template <typename Graph>
       
   141     class PlanarityChecking {
       
   142     private:
       
   143       
       
   144       TEMPLATE_GRAPH_TYPEDEFS(Graph);
       
   145 
       
   146       const Graph& _graph;
       
   147 
       
   148     private:
       
   149       
       
   150       typedef typename Graph::template NodeMap<Arc> PredMap;
       
   151       
       
   152       typedef typename Graph::template EdgeMap<bool> TreeMap;
       
   153       
       
   154       typedef typename Graph::template NodeMap<int> OrderMap;
       
   155       typedef std::vector<Node> OrderList;
       
   156 
       
   157       typedef typename Graph::template NodeMap<int> LowMap;
       
   158       typedef typename Graph::template NodeMap<int> AncestorMap;
       
   159 
       
   160       typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
       
   161       typedef std::vector<NodeDataNode> NodeData;
       
   162 
       
   163       typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
       
   164       typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
       
   165 
       
   166       typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
       
   167 
       
   168       typedef typename Graph::template NodeMap<bool> EmbedArc;
       
   169 
       
   170     public:
       
   171 
       
   172       PlanarityChecking(const Graph& graph) : _graph(graph) {}
       
   173 
       
   174       bool run() {
       
   175         typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
       
   176 
       
   177         PredMap pred_map(_graph, INVALID);
       
   178         TreeMap tree_map(_graph, false);
       
   179 
       
   180         OrderMap order_map(_graph, -1);
       
   181         OrderList order_list;
       
   182 
       
   183         AncestorMap ancestor_map(_graph, -1);
       
   184         LowMap low_map(_graph, -1);
       
   185 
       
   186         Visitor visitor(_graph, pred_map, tree_map,
       
   187                         order_map, order_list, ancestor_map, low_map);
       
   188         DfsVisit<Graph, Visitor> visit(_graph, visitor);
       
   189         visit.run();
       
   190 
       
   191         ChildLists child_lists(_graph);
       
   192         createChildLists(tree_map, order_map, low_map, child_lists);
       
   193 
       
   194         NodeData node_data(2 * order_list.size());
       
   195 
       
   196         EmbedArc embed_arc(_graph, false);
       
   197 
       
   198         MergeRoots merge_roots(_graph);
       
   199 
       
   200         for (int i = order_list.size() - 1; i >= 0; --i) {
       
   201 
       
   202           Node node = order_list[i];
       
   203 
       
   204           Node source = node;
       
   205           for (OutArcIt e(_graph, node); e != INVALID; ++e) {
       
   206             Node target = _graph.target(e);
       
   207 
       
   208             if (order_map[source] < order_map[target] && tree_map[e]) {
       
   209               initFace(target, node_data, order_map, order_list);
       
   210             }
       
   211           }
       
   212 
       
   213           for (OutArcIt e(_graph, node); e != INVALID; ++e) {
       
   214             Node target = _graph.target(e);
       
   215 
       
   216             if (order_map[source] < order_map[target] && !tree_map[e]) {
       
   217               embed_arc[target] = true;
       
   218               walkUp(target, source, i, pred_map, low_map,
       
   219                      order_map, order_list, node_data, merge_roots);
       
   220             }
       
   221           }
       
   222 
       
   223           for (typename MergeRoots::Value::iterator it =
       
   224                  merge_roots[node].begin(); 
       
   225                it != merge_roots[node].end(); ++it) {
       
   226             int rn = *it;
       
   227             walkDown(rn, i, node_data, order_list, child_lists,
       
   228                      ancestor_map, low_map, embed_arc, merge_roots);
       
   229           }
       
   230           merge_roots[node].clear();
       
   231 
       
   232           for (OutArcIt e(_graph, node); e != INVALID; ++e) {
       
   233             Node target = _graph.target(e);
       
   234 
       
   235             if (order_map[source] < order_map[target] && !tree_map[e]) {
       
   236               if (embed_arc[target]) {
       
   237                 return false;
       
   238               }
       
   239             }
       
   240           }
       
   241         }
       
   242 
       
   243         return true;
       
   244       }
       
   245 
       
   246     private:
       
   247 
       
   248       void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
       
   249                             const LowMap& low_map, ChildLists& child_lists) {
       
   250 
       
   251         for (NodeIt n(_graph); n != INVALID; ++n) {
       
   252           Node source = n;
       
   253 
       
   254           std::vector<Node> targets;
       
   255           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
       
   256             Node target = _graph.target(e);
       
   257 
       
   258             if (order_map[source] < order_map[target] && tree_map[e]) {
       
   259               targets.push_back(target);
       
   260             }
       
   261           }
       
   262 
       
   263           if (targets.size() == 0) {
       
   264             child_lists[source].first = INVALID;
       
   265           } else if (targets.size() == 1) {
       
   266             child_lists[source].first = targets[0];
       
   267             child_lists[targets[0]].prev = INVALID;
       
   268             child_lists[targets[0]].next = INVALID;
       
   269           } else {
       
   270             radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
       
   271             for (int i = 1; i < int(targets.size()); ++i) {
       
   272               child_lists[targets[i]].prev = targets[i - 1];
       
   273               child_lists[targets[i - 1]].next = targets[i];
       
   274             }
       
   275             child_lists[targets.back()].next = INVALID;
       
   276             child_lists[targets.front()].prev = INVALID;
       
   277             child_lists[source].first = targets.front();
       
   278           }
       
   279         }
       
   280       }
       
   281 
       
   282       void walkUp(const Node& node, Node root, int rorder,
       
   283                   const PredMap& pred_map, const LowMap& low_map,
       
   284                   const OrderMap& order_map, const OrderList& order_list,
       
   285                   NodeData& node_data, MergeRoots& merge_roots) {
       
   286 
       
   287         int na, nb;
       
   288         bool da, db;
       
   289 
       
   290         na = nb = order_map[node];
       
   291         da = true; db = false;
       
   292 
       
   293         while (true) {
       
   294 
       
   295           if (node_data[na].visited == rorder) break;
       
   296           if (node_data[nb].visited == rorder) break;
       
   297 
       
   298           node_data[na].visited = rorder;
       
   299           node_data[nb].visited = rorder;
       
   300 
       
   301           int rn = -1;
       
   302 
       
   303           if (na >= int(order_list.size())) {
       
   304             rn = na;
       
   305           } else if (nb >= int(order_list.size())) {
       
   306             rn = nb;
       
   307           }
       
   308 
       
   309           if (rn == -1) {
       
   310             int nn;
       
   311 
       
   312             nn = da ? node_data[na].prev : node_data[na].next;
       
   313             da = node_data[nn].prev != na;
       
   314             na = nn;
       
   315 
       
   316             nn = db ? node_data[nb].prev : node_data[nb].next;
       
   317             db = node_data[nn].prev != nb;
       
   318             nb = nn;
       
   319 
       
   320           } else {
       
   321 
       
   322             Node rep = order_list[rn - order_list.size()];
       
   323             Node parent = _graph.source(pred_map[rep]);
       
   324 
       
   325             if (low_map[rep] < rorder) {
       
   326               merge_roots[parent].push_back(rn);
       
   327             } else {
       
   328               merge_roots[parent].push_front(rn);
       
   329             }
       
   330 
       
   331             if (parent != root) {
       
   332               na = nb = order_map[parent];
       
   333               da = true; db = false;
       
   334             } else {
       
   335               break;
       
   336             }
       
   337           }
       
   338         }
       
   339       }
       
   340 
       
   341       void walkDown(int rn, int rorder, NodeData& node_data,
       
   342                     OrderList& order_list, ChildLists& child_lists,
       
   343                     AncestorMap& ancestor_map, LowMap& low_map,
       
   344                     EmbedArc& embed_arc, MergeRoots& merge_roots) {
       
   345 
       
   346         std::vector<std::pair<int, bool> > merge_stack;
       
   347 
       
   348         for (int di = 0; di < 2; ++di) {
       
   349           bool rd = di == 0;
       
   350           int pn = rn;
       
   351           int n = rd ? node_data[rn].next : node_data[rn].prev;
       
   352 
       
   353           while (n != rn) {
       
   354 
       
   355             Node node = order_list[n];
       
   356 
       
   357             if (embed_arc[node]) {
       
   358 
       
   359               // Merging components on the critical path
       
   360               while (!merge_stack.empty()) {
       
   361 
       
   362                 // Component root
       
   363                 int cn = merge_stack.back().first;
       
   364                 bool cd = merge_stack.back().second;
       
   365                 merge_stack.pop_back();
       
   366 
       
   367                 // Parent of component
       
   368                 int dn = merge_stack.back().first;
       
   369                 bool dd = merge_stack.back().second;
       
   370                 merge_stack.pop_back();
       
   371 
       
   372                 Node parent = order_list[dn];
       
   373 
       
   374                 // Erasing from merge_roots
       
   375                 merge_roots[parent].pop_front();
       
   376 
       
   377                 Node child = order_list[cn - order_list.size()];
       
   378 
       
   379                 // Erasing from child_lists
       
   380                 if (child_lists[child].prev != INVALID) {
       
   381                   child_lists[child_lists[child].prev].next =
       
   382                     child_lists[child].next;
       
   383                 } else {
       
   384                   child_lists[parent].first = child_lists[child].next;
       
   385                 }
       
   386 
       
   387                 if (child_lists[child].next != INVALID) {
       
   388                   child_lists[child_lists[child].next].prev =
       
   389                     child_lists[child].prev;
       
   390                 }
       
   391 
       
   392                 // Merging external faces
       
   393                 {
       
   394                   int en = cn;
       
   395                   cn = cd ? node_data[cn].prev : node_data[cn].next;
       
   396                   cd = node_data[cn].next == en;
       
   397 
       
   398                 }
       
   399 
       
   400                 if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
       
   401                 if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
       
   402 
       
   403               }
       
   404 
       
   405               bool d = pn == node_data[n].prev;
       
   406 
       
   407               if (node_data[n].prev == node_data[n].next &&
       
   408                   node_data[n].inverted) {
       
   409                 d = !d;
       
   410               }
       
   411 
       
   412               // Embedding arc into external face
       
   413               if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
       
   414               if (d) node_data[n].prev = rn; else node_data[n].next = rn;
       
   415               pn = rn;
       
   416 
       
   417               embed_arc[order_list[n]] = false;
       
   418             }
       
   419 
       
   420             if (!merge_roots[node].empty()) {
       
   421 
       
   422               bool d = pn == node_data[n].prev;
       
   423 
       
   424               merge_stack.push_back(std::make_pair(n, d));
       
   425 
       
   426               int rn = merge_roots[node].front();
       
   427 
       
   428               int xn = node_data[rn].next;
       
   429               Node xnode = order_list[xn];
       
   430 
       
   431               int yn = node_data[rn].prev;
       
   432               Node ynode = order_list[yn];
       
   433 
       
   434               bool rd;
       
   435               if (!external(xnode, rorder, child_lists, 
       
   436                             ancestor_map, low_map)) {
       
   437                 rd = true;
       
   438               } else if (!external(ynode, rorder, child_lists,
       
   439                                    ancestor_map, low_map)) {
       
   440                 rd = false;
       
   441               } else if (pertinent(xnode, embed_arc, merge_roots)) {
       
   442                 rd = true;
       
   443               } else {
       
   444                 rd = false;
       
   445               }
       
   446 
       
   447               merge_stack.push_back(std::make_pair(rn, rd));
       
   448 
       
   449               pn = rn;
       
   450               n = rd ? xn : yn;
       
   451 
       
   452             } else if (!external(node, rorder, child_lists,
       
   453                                  ancestor_map, low_map)) {
       
   454               int nn = (node_data[n].next != pn ?
       
   455                         node_data[n].next : node_data[n].prev);
       
   456 
       
   457               bool nd = n == node_data[nn].prev;
       
   458 
       
   459               if (nd) node_data[nn].prev = pn;
       
   460               else node_data[nn].next = pn;
       
   461 
       
   462               if (n == node_data[pn].prev) node_data[pn].prev = nn;
       
   463               else node_data[pn].next = nn;
       
   464 
       
   465               node_data[nn].inverted =
       
   466                 (node_data[nn].prev == node_data[nn].next && nd != rd);
       
   467 
       
   468               n = nn;
       
   469             }
       
   470             else break;
       
   471 
       
   472           }
       
   473 
       
   474           if (!merge_stack.empty() || n == rn) {
       
   475             break;
       
   476           }
       
   477         }
       
   478       }
       
   479 
       
   480       void initFace(const Node& node, NodeData& node_data,
       
   481                     const OrderMap& order_map, const OrderList& order_list) {
       
   482         int n = order_map[node];
       
   483         int rn = n + order_list.size();
       
   484 
       
   485         node_data[n].next = node_data[n].prev = rn;
       
   486         node_data[rn].next = node_data[rn].prev = n;
       
   487 
       
   488         node_data[n].visited = order_list.size();
       
   489         node_data[rn].visited = order_list.size();
       
   490 
       
   491       }
       
   492 
       
   493       bool external(const Node& node, int rorder,
       
   494                     ChildLists& child_lists, AncestorMap& ancestor_map,
       
   495                     LowMap& low_map) {
       
   496         Node child = child_lists[node].first;
       
   497 
       
   498         if (child != INVALID) {
       
   499           if (low_map[child] < rorder) return true;
       
   500         }
       
   501 
       
   502         if (ancestor_map[node] < rorder) return true;
       
   503 
       
   504         return false;
       
   505       }
       
   506 
       
   507       bool pertinent(const Node& node, const EmbedArc& embed_arc,
       
   508                      const MergeRoots& merge_roots) {
       
   509         return !merge_roots[node].empty() || embed_arc[node];
       
   510       }
       
   511 
       
   512     };
       
   513 
   140   }
   514   }
   141 
   515 
   142   /// \ingroup planar
   516   /// \ingroup planar
   143   ///
   517   ///
   144   /// \brief Planarity checking of an undirected simple graph
   518   /// \brief Planarity checking of an undirected simple graph
   145   ///
   519   ///
   146   /// This class implements the Boyer-Myrvold algorithm for planarity
   520   /// This function implements the Boyer-Myrvold algorithm for
   147   /// checking of an undirected graph. This class is a simplified
   521   /// planarity checking of an undirected graph. It is a simplified
   148   /// version of the PlanarEmbedding algorithm class because neither
   522   /// version of the PlanarEmbedding algorithm class because neither
   149   /// the embedding nor the kuratowski subdivisons are not computed.
   523   /// the embedding nor the kuratowski subdivisons are not computed.
   150   template <typename Graph>
   524   template <typename GR>
   151   class PlanarityChecking {
   525   bool checkPlanarity(const GR& graph) {
   152   private:
   526     _planarity_bits::PlanarityChecking<GR> pc(graph);
   153 
   527     return pc.run();
   154     TEMPLATE_GRAPH_TYPEDEFS(Graph);
   528   }
   155 
       
   156     const Graph& _graph;
       
   157 
       
   158   private:
       
   159 
       
   160     typedef typename Graph::template NodeMap<Arc> PredMap;
       
   161 
       
   162     typedef typename Graph::template EdgeMap<bool> TreeMap;
       
   163 
       
   164     typedef typename Graph::template NodeMap<int> OrderMap;
       
   165     typedef std::vector<Node> OrderList;
       
   166 
       
   167     typedef typename Graph::template NodeMap<int> LowMap;
       
   168     typedef typename Graph::template NodeMap<int> AncestorMap;
       
   169 
       
   170     typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
       
   171     typedef std::vector<NodeDataNode> NodeData;
       
   172 
       
   173     typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
       
   174     typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
       
   175 
       
   176     typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
       
   177 
       
   178     typedef typename Graph::template NodeMap<bool> EmbedArc;
       
   179 
       
   180   public:
       
   181 
       
   182     /// \brief Constructor
       
   183     ///
       
   184     /// \note The graph should be simple, i.e. parallel and loop arc
       
   185     /// free.
       
   186     PlanarityChecking(const Graph& graph) : _graph(graph) {}
       
   187 
       
   188     /// \brief Runs the algorithm.
       
   189     ///
       
   190     /// Runs the algorithm.
       
   191     /// \return %True when the graph is planar.
       
   192     bool run() {
       
   193       typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
       
   194 
       
   195       PredMap pred_map(_graph, INVALID);
       
   196       TreeMap tree_map(_graph, false);
       
   197 
       
   198       OrderMap order_map(_graph, -1);
       
   199       OrderList order_list;
       
   200 
       
   201       AncestorMap ancestor_map(_graph, -1);
       
   202       LowMap low_map(_graph, -1);
       
   203 
       
   204       Visitor visitor(_graph, pred_map, tree_map,
       
   205                       order_map, order_list, ancestor_map, low_map);
       
   206       DfsVisit<Graph, Visitor> visit(_graph, visitor);
       
   207       visit.run();
       
   208 
       
   209       ChildLists child_lists(_graph);
       
   210       createChildLists(tree_map, order_map, low_map, child_lists);
       
   211 
       
   212       NodeData node_data(2 * order_list.size());
       
   213 
       
   214       EmbedArc embed_arc(_graph, false);
       
   215 
       
   216       MergeRoots merge_roots(_graph);
       
   217 
       
   218       for (int i = order_list.size() - 1; i >= 0; --i) {
       
   219 
       
   220         Node node = order_list[i];
       
   221 
       
   222         Node source = node;
       
   223         for (OutArcIt e(_graph, node); e != INVALID; ++e) {
       
   224           Node target = _graph.target(e);
       
   225 
       
   226           if (order_map[source] < order_map[target] && tree_map[e]) {
       
   227             initFace(target, node_data, order_map, order_list);
       
   228           }
       
   229         }
       
   230 
       
   231         for (OutArcIt e(_graph, node); e != INVALID; ++e) {
       
   232           Node target = _graph.target(e);
       
   233 
       
   234           if (order_map[source] < order_map[target] && !tree_map[e]) {
       
   235             embed_arc[target] = true;
       
   236             walkUp(target, source, i, pred_map, low_map,
       
   237                    order_map, order_list, node_data, merge_roots);
       
   238           }
       
   239         }
       
   240 
       
   241         for (typename MergeRoots::Value::iterator it =
       
   242                merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
       
   243           int rn = *it;
       
   244           walkDown(rn, i, node_data, order_list, child_lists,
       
   245                    ancestor_map, low_map, embed_arc, merge_roots);
       
   246         }
       
   247         merge_roots[node].clear();
       
   248 
       
   249         for (OutArcIt e(_graph, node); e != INVALID; ++e) {
       
   250           Node target = _graph.target(e);
       
   251 
       
   252           if (order_map[source] < order_map[target] && !tree_map[e]) {
       
   253             if (embed_arc[target]) {
       
   254               return false;
       
   255             }
       
   256           }
       
   257         }
       
   258       }
       
   259 
       
   260       return true;
       
   261     }
       
   262 
       
   263   private:
       
   264 
       
   265     void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
       
   266                           const LowMap& low_map, ChildLists& child_lists) {
       
   267 
       
   268       for (NodeIt n(_graph); n != INVALID; ++n) {
       
   269         Node source = n;
       
   270 
       
   271         std::vector<Node> targets;
       
   272         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
       
   273           Node target = _graph.target(e);
       
   274 
       
   275           if (order_map[source] < order_map[target] && tree_map[e]) {
       
   276             targets.push_back(target);
       
   277           }
       
   278         }
       
   279 
       
   280         if (targets.size() == 0) {
       
   281           child_lists[source].first = INVALID;
       
   282         } else if (targets.size() == 1) {
       
   283           child_lists[source].first = targets[0];
       
   284           child_lists[targets[0]].prev = INVALID;
       
   285           child_lists[targets[0]].next = INVALID;
       
   286         } else {
       
   287           radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
       
   288           for (int i = 1; i < int(targets.size()); ++i) {
       
   289             child_lists[targets[i]].prev = targets[i - 1];
       
   290             child_lists[targets[i - 1]].next = targets[i];
       
   291           }
       
   292           child_lists[targets.back()].next = INVALID;
       
   293           child_lists[targets.front()].prev = INVALID;
       
   294           child_lists[source].first = targets.front();
       
   295         }
       
   296       }
       
   297     }
       
   298 
       
   299     void walkUp(const Node& node, Node root, int rorder,
       
   300                 const PredMap& pred_map, const LowMap& low_map,
       
   301                 const OrderMap& order_map, const OrderList& order_list,
       
   302                 NodeData& node_data, MergeRoots& merge_roots) {
       
   303 
       
   304       int na, nb;
       
   305       bool da, db;
       
   306 
       
   307       na = nb = order_map[node];
       
   308       da = true; db = false;
       
   309 
       
   310       while (true) {
       
   311 
       
   312         if (node_data[na].visited == rorder) break;
       
   313         if (node_data[nb].visited == rorder) break;
       
   314 
       
   315         node_data[na].visited = rorder;
       
   316         node_data[nb].visited = rorder;
       
   317 
       
   318         int rn = -1;
       
   319 
       
   320         if (na >= int(order_list.size())) {
       
   321           rn = na;
       
   322         } else if (nb >= int(order_list.size())) {
       
   323           rn = nb;
       
   324         }
       
   325 
       
   326         if (rn == -1) {
       
   327           int nn;
       
   328 
       
   329           nn = da ? node_data[na].prev : node_data[na].next;
       
   330           da = node_data[nn].prev != na;
       
   331           na = nn;
       
   332 
       
   333           nn = db ? node_data[nb].prev : node_data[nb].next;
       
   334           db = node_data[nn].prev != nb;
       
   335           nb = nn;
       
   336 
       
   337         } else {
       
   338 
       
   339           Node rep = order_list[rn - order_list.size()];
       
   340           Node parent = _graph.source(pred_map[rep]);
       
   341 
       
   342           if (low_map[rep] < rorder) {
       
   343             merge_roots[parent].push_back(rn);
       
   344           } else {
       
   345             merge_roots[parent].push_front(rn);
       
   346           }
       
   347 
       
   348           if (parent != root) {
       
   349             na = nb = order_map[parent];
       
   350             da = true; db = false;
       
   351           } else {
       
   352             break;
       
   353           }
       
   354         }
       
   355       }
       
   356     }
       
   357 
       
   358     void walkDown(int rn, int rorder, NodeData& node_data,
       
   359                   OrderList& order_list, ChildLists& child_lists,
       
   360                   AncestorMap& ancestor_map, LowMap& low_map,
       
   361                   EmbedArc& embed_arc, MergeRoots& merge_roots) {
       
   362 
       
   363       std::vector<std::pair<int, bool> > merge_stack;
       
   364 
       
   365       for (int di = 0; di < 2; ++di) {
       
   366         bool rd = di == 0;
       
   367         int pn = rn;
       
   368         int n = rd ? node_data[rn].next : node_data[rn].prev;
       
   369 
       
   370         while (n != rn) {
       
   371 
       
   372           Node node = order_list[n];
       
   373 
       
   374           if (embed_arc[node]) {
       
   375 
       
   376             // Merging components on the critical path
       
   377             while (!merge_stack.empty()) {
       
   378 
       
   379               // Component root
       
   380               int cn = merge_stack.back().first;
       
   381               bool cd = merge_stack.back().second;
       
   382               merge_stack.pop_back();
       
   383 
       
   384               // Parent of component
       
   385               int dn = merge_stack.back().first;
       
   386               bool dd = merge_stack.back().second;
       
   387               merge_stack.pop_back();
       
   388 
       
   389               Node parent = order_list[dn];
       
   390 
       
   391               // Erasing from merge_roots
       
   392               merge_roots[parent].pop_front();
       
   393 
       
   394               Node child = order_list[cn - order_list.size()];
       
   395 
       
   396               // Erasing from child_lists
       
   397               if (child_lists[child].prev != INVALID) {
       
   398                 child_lists[child_lists[child].prev].next =
       
   399                   child_lists[child].next;
       
   400               } else {
       
   401                 child_lists[parent].first = child_lists[child].next;
       
   402               }
       
   403 
       
   404               if (child_lists[child].next != INVALID) {
       
   405                 child_lists[child_lists[child].next].prev =
       
   406                   child_lists[child].prev;
       
   407               }
       
   408 
       
   409               // Merging external faces
       
   410               {
       
   411                 int en = cn;
       
   412                 cn = cd ? node_data[cn].prev : node_data[cn].next;
       
   413                 cd = node_data[cn].next == en;
       
   414 
       
   415               }
       
   416 
       
   417               if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
       
   418               if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
       
   419 
       
   420             }
       
   421 
       
   422             bool d = pn == node_data[n].prev;
       
   423 
       
   424             if (node_data[n].prev == node_data[n].next &&
       
   425                 node_data[n].inverted) {
       
   426               d = !d;
       
   427             }
       
   428 
       
   429             // Embedding arc into external face
       
   430             if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
       
   431             if (d) node_data[n].prev = rn; else node_data[n].next = rn;
       
   432             pn = rn;
       
   433 
       
   434             embed_arc[order_list[n]] = false;
       
   435           }
       
   436 
       
   437           if (!merge_roots[node].empty()) {
       
   438 
       
   439             bool d = pn == node_data[n].prev;
       
   440 
       
   441             merge_stack.push_back(std::make_pair(n, d));
       
   442 
       
   443             int rn = merge_roots[node].front();
       
   444 
       
   445             int xn = node_data[rn].next;
       
   446             Node xnode = order_list[xn];
       
   447 
       
   448             int yn = node_data[rn].prev;
       
   449             Node ynode = order_list[yn];
       
   450 
       
   451             bool rd;
       
   452             if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
       
   453               rd = true;
       
   454             } else if (!external(ynode, rorder, child_lists,
       
   455                                  ancestor_map, low_map)) {
       
   456               rd = false;
       
   457             } else if (pertinent(xnode, embed_arc, merge_roots)) {
       
   458               rd = true;
       
   459             } else {
       
   460               rd = false;
       
   461             }
       
   462 
       
   463             merge_stack.push_back(std::make_pair(rn, rd));
       
   464 
       
   465             pn = rn;
       
   466             n = rd ? xn : yn;
       
   467 
       
   468           } else if (!external(node, rorder, child_lists,
       
   469                                ancestor_map, low_map)) {
       
   470             int nn = (node_data[n].next != pn ?
       
   471                       node_data[n].next : node_data[n].prev);
       
   472 
       
   473             bool nd = n == node_data[nn].prev;
       
   474 
       
   475             if (nd) node_data[nn].prev = pn;
       
   476             else node_data[nn].next = pn;
       
   477 
       
   478             if (n == node_data[pn].prev) node_data[pn].prev = nn;
       
   479             else node_data[pn].next = nn;
       
   480 
       
   481             node_data[nn].inverted =
       
   482               (node_data[nn].prev == node_data[nn].next && nd != rd);
       
   483 
       
   484             n = nn;
       
   485           }
       
   486           else break;
       
   487 
       
   488         }
       
   489 
       
   490         if (!merge_stack.empty() || n == rn) {
       
   491           break;
       
   492         }
       
   493       }
       
   494     }
       
   495 
       
   496     void initFace(const Node& node, NodeData& node_data,
       
   497                   const OrderMap& order_map, const OrderList& order_list) {
       
   498       int n = order_map[node];
       
   499       int rn = n + order_list.size();
       
   500 
       
   501       node_data[n].next = node_data[n].prev = rn;
       
   502       node_data[rn].next = node_data[rn].prev = n;
       
   503 
       
   504       node_data[n].visited = order_list.size();
       
   505       node_data[rn].visited = order_list.size();
       
   506 
       
   507     }
       
   508 
       
   509     bool external(const Node& node, int rorder,
       
   510                   ChildLists& child_lists, AncestorMap& ancestor_map,
       
   511                   LowMap& low_map) {
       
   512       Node child = child_lists[node].first;
       
   513 
       
   514       if (child != INVALID) {
       
   515         if (low_map[child] < rorder) return true;
       
   516       }
       
   517 
       
   518       if (ancestor_map[node] < rorder) return true;
       
   519 
       
   520       return false;
       
   521     }
       
   522 
       
   523     bool pertinent(const Node& node, const EmbedArc& embed_arc,
       
   524                    const MergeRoots& merge_roots) {
       
   525       return !merge_roots[node].empty() || embed_arc[node];
       
   526     }
       
   527 
       
   528   };
       
   529 
   529 
   530   /// \ingroup planar
   530   /// \ingroup planar
   531   ///
   531   ///
   532   /// \brief Planar embedding of an undirected simple graph
   532   /// \brief Planar embedding of an undirected simple graph
   533   ///
   533   ///
   710 
   710 
   711     /// \brief Gives back the calculated embedding map
   711     /// \brief Gives back the calculated embedding map
   712     ///
   712     ///
   713     /// The returned map contains the successor of each arc in the
   713     /// The returned map contains the successor of each arc in the
   714     /// graph.
   714     /// graph.
   715     const EmbeddingMap& embedding() const {
   715     const EmbeddingMap& embeddingMap() const {
   716       return _embedding;
   716       return _embedding;
   717     }
   717     }
   718 
   718 
   719     /// \brief Gives back true if the undirected arc is in the
   719     /// \brief Gives back true if the undirected arc is in the
   720     /// kuratowski subdivision
   720     /// kuratowski subdivision