Planarity checking function instead of class (#62)
authorBalazs Dezso <deba@inf.elte.hu>
Sun, 04 Oct 2009 10:15:32 +0200
changeset 79858c330ad0b5c
parent 797 30cb42e3e43a
child 799 6be1f9bd2ac0
Planarity checking function instead of class (#62)
lemon/planarity.h
test/planarity_test.cc
     1.1 --- a/lemon/planarity.h	Wed Sep 09 15:32:03 2009 +0200
     1.2 +++ b/lemon/planarity.h	Sun Oct 04 10:15:32 2009 +0200
     1.3 @@ -137,395 +137,395 @@
     1.4        typename Graph::Arc prev, next;
     1.5      };
     1.6  
     1.7 +    template <typename Graph>
     1.8 +    class PlanarityChecking {
     1.9 +    private:
    1.10 +      
    1.11 +      TEMPLATE_GRAPH_TYPEDEFS(Graph);
    1.12 +
    1.13 +      const Graph& _graph;
    1.14 +
    1.15 +    private:
    1.16 +      
    1.17 +      typedef typename Graph::template NodeMap<Arc> PredMap;
    1.18 +      
    1.19 +      typedef typename Graph::template EdgeMap<bool> TreeMap;
    1.20 +      
    1.21 +      typedef typename Graph::template NodeMap<int> OrderMap;
    1.22 +      typedef std::vector<Node> OrderList;
    1.23 +
    1.24 +      typedef typename Graph::template NodeMap<int> LowMap;
    1.25 +      typedef typename Graph::template NodeMap<int> AncestorMap;
    1.26 +
    1.27 +      typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
    1.28 +      typedef std::vector<NodeDataNode> NodeData;
    1.29 +
    1.30 +      typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
    1.31 +      typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
    1.32 +
    1.33 +      typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
    1.34 +
    1.35 +      typedef typename Graph::template NodeMap<bool> EmbedArc;
    1.36 +
    1.37 +    public:
    1.38 +
    1.39 +      PlanarityChecking(const Graph& graph) : _graph(graph) {}
    1.40 +
    1.41 +      bool run() {
    1.42 +        typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
    1.43 +
    1.44 +        PredMap pred_map(_graph, INVALID);
    1.45 +        TreeMap tree_map(_graph, false);
    1.46 +
    1.47 +        OrderMap order_map(_graph, -1);
    1.48 +        OrderList order_list;
    1.49 +
    1.50 +        AncestorMap ancestor_map(_graph, -1);
    1.51 +        LowMap low_map(_graph, -1);
    1.52 +
    1.53 +        Visitor visitor(_graph, pred_map, tree_map,
    1.54 +                        order_map, order_list, ancestor_map, low_map);
    1.55 +        DfsVisit<Graph, Visitor> visit(_graph, visitor);
    1.56 +        visit.run();
    1.57 +
    1.58 +        ChildLists child_lists(_graph);
    1.59 +        createChildLists(tree_map, order_map, low_map, child_lists);
    1.60 +
    1.61 +        NodeData node_data(2 * order_list.size());
    1.62 +
    1.63 +        EmbedArc embed_arc(_graph, false);
    1.64 +
    1.65 +        MergeRoots merge_roots(_graph);
    1.66 +
    1.67 +        for (int i = order_list.size() - 1; i >= 0; --i) {
    1.68 +
    1.69 +          Node node = order_list[i];
    1.70 +
    1.71 +          Node source = node;
    1.72 +          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
    1.73 +            Node target = _graph.target(e);
    1.74 +
    1.75 +            if (order_map[source] < order_map[target] && tree_map[e]) {
    1.76 +              initFace(target, node_data, order_map, order_list);
    1.77 +            }
    1.78 +          }
    1.79 +
    1.80 +          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
    1.81 +            Node target = _graph.target(e);
    1.82 +
    1.83 +            if (order_map[source] < order_map[target] && !tree_map[e]) {
    1.84 +              embed_arc[target] = true;
    1.85 +              walkUp(target, source, i, pred_map, low_map,
    1.86 +                     order_map, order_list, node_data, merge_roots);
    1.87 +            }
    1.88 +          }
    1.89 +
    1.90 +          for (typename MergeRoots::Value::iterator it =
    1.91 +                 merge_roots[node].begin(); 
    1.92 +               it != merge_roots[node].end(); ++it) {
    1.93 +            int rn = *it;
    1.94 +            walkDown(rn, i, node_data, order_list, child_lists,
    1.95 +                     ancestor_map, low_map, embed_arc, merge_roots);
    1.96 +          }
    1.97 +          merge_roots[node].clear();
    1.98 +
    1.99 +          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
   1.100 +            Node target = _graph.target(e);
   1.101 +
   1.102 +            if (order_map[source] < order_map[target] && !tree_map[e]) {
   1.103 +              if (embed_arc[target]) {
   1.104 +                return false;
   1.105 +              }
   1.106 +            }
   1.107 +          }
   1.108 +        }
   1.109 +
   1.110 +        return true;
   1.111 +      }
   1.112 +
   1.113 +    private:
   1.114 +
   1.115 +      void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
   1.116 +                            const LowMap& low_map, ChildLists& child_lists) {
   1.117 +
   1.118 +        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.119 +          Node source = n;
   1.120 +
   1.121 +          std::vector<Node> targets;
   1.122 +          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   1.123 +            Node target = _graph.target(e);
   1.124 +
   1.125 +            if (order_map[source] < order_map[target] && tree_map[e]) {
   1.126 +              targets.push_back(target);
   1.127 +            }
   1.128 +          }
   1.129 +
   1.130 +          if (targets.size() == 0) {
   1.131 +            child_lists[source].first = INVALID;
   1.132 +          } else if (targets.size() == 1) {
   1.133 +            child_lists[source].first = targets[0];
   1.134 +            child_lists[targets[0]].prev = INVALID;
   1.135 +            child_lists[targets[0]].next = INVALID;
   1.136 +          } else {
   1.137 +            radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
   1.138 +            for (int i = 1; i < int(targets.size()); ++i) {
   1.139 +              child_lists[targets[i]].prev = targets[i - 1];
   1.140 +              child_lists[targets[i - 1]].next = targets[i];
   1.141 +            }
   1.142 +            child_lists[targets.back()].next = INVALID;
   1.143 +            child_lists[targets.front()].prev = INVALID;
   1.144 +            child_lists[source].first = targets.front();
   1.145 +          }
   1.146 +        }
   1.147 +      }
   1.148 +
   1.149 +      void walkUp(const Node& node, Node root, int rorder,
   1.150 +                  const PredMap& pred_map, const LowMap& low_map,
   1.151 +                  const OrderMap& order_map, const OrderList& order_list,
   1.152 +                  NodeData& node_data, MergeRoots& merge_roots) {
   1.153 +
   1.154 +        int na, nb;
   1.155 +        bool da, db;
   1.156 +
   1.157 +        na = nb = order_map[node];
   1.158 +        da = true; db = false;
   1.159 +
   1.160 +        while (true) {
   1.161 +
   1.162 +          if (node_data[na].visited == rorder) break;
   1.163 +          if (node_data[nb].visited == rorder) break;
   1.164 +
   1.165 +          node_data[na].visited = rorder;
   1.166 +          node_data[nb].visited = rorder;
   1.167 +
   1.168 +          int rn = -1;
   1.169 +
   1.170 +          if (na >= int(order_list.size())) {
   1.171 +            rn = na;
   1.172 +          } else if (nb >= int(order_list.size())) {
   1.173 +            rn = nb;
   1.174 +          }
   1.175 +
   1.176 +          if (rn == -1) {
   1.177 +            int nn;
   1.178 +
   1.179 +            nn = da ? node_data[na].prev : node_data[na].next;
   1.180 +            da = node_data[nn].prev != na;
   1.181 +            na = nn;
   1.182 +
   1.183 +            nn = db ? node_data[nb].prev : node_data[nb].next;
   1.184 +            db = node_data[nn].prev != nb;
   1.185 +            nb = nn;
   1.186 +
   1.187 +          } else {
   1.188 +
   1.189 +            Node rep = order_list[rn - order_list.size()];
   1.190 +            Node parent = _graph.source(pred_map[rep]);
   1.191 +
   1.192 +            if (low_map[rep] < rorder) {
   1.193 +              merge_roots[parent].push_back(rn);
   1.194 +            } else {
   1.195 +              merge_roots[parent].push_front(rn);
   1.196 +            }
   1.197 +
   1.198 +            if (parent != root) {
   1.199 +              na = nb = order_map[parent];
   1.200 +              da = true; db = false;
   1.201 +            } else {
   1.202 +              break;
   1.203 +            }
   1.204 +          }
   1.205 +        }
   1.206 +      }
   1.207 +
   1.208 +      void walkDown(int rn, int rorder, NodeData& node_data,
   1.209 +                    OrderList& order_list, ChildLists& child_lists,
   1.210 +                    AncestorMap& ancestor_map, LowMap& low_map,
   1.211 +                    EmbedArc& embed_arc, MergeRoots& merge_roots) {
   1.212 +
   1.213 +        std::vector<std::pair<int, bool> > merge_stack;
   1.214 +
   1.215 +        for (int di = 0; di < 2; ++di) {
   1.216 +          bool rd = di == 0;
   1.217 +          int pn = rn;
   1.218 +          int n = rd ? node_data[rn].next : node_data[rn].prev;
   1.219 +
   1.220 +          while (n != rn) {
   1.221 +
   1.222 +            Node node = order_list[n];
   1.223 +
   1.224 +            if (embed_arc[node]) {
   1.225 +
   1.226 +              // Merging components on the critical path
   1.227 +              while (!merge_stack.empty()) {
   1.228 +
   1.229 +                // Component root
   1.230 +                int cn = merge_stack.back().first;
   1.231 +                bool cd = merge_stack.back().second;
   1.232 +                merge_stack.pop_back();
   1.233 +
   1.234 +                // Parent of component
   1.235 +                int dn = merge_stack.back().first;
   1.236 +                bool dd = merge_stack.back().second;
   1.237 +                merge_stack.pop_back();
   1.238 +
   1.239 +                Node parent = order_list[dn];
   1.240 +
   1.241 +                // Erasing from merge_roots
   1.242 +                merge_roots[parent].pop_front();
   1.243 +
   1.244 +                Node child = order_list[cn - order_list.size()];
   1.245 +
   1.246 +                // Erasing from child_lists
   1.247 +                if (child_lists[child].prev != INVALID) {
   1.248 +                  child_lists[child_lists[child].prev].next =
   1.249 +                    child_lists[child].next;
   1.250 +                } else {
   1.251 +                  child_lists[parent].first = child_lists[child].next;
   1.252 +                }
   1.253 +
   1.254 +                if (child_lists[child].next != INVALID) {
   1.255 +                  child_lists[child_lists[child].next].prev =
   1.256 +                    child_lists[child].prev;
   1.257 +                }
   1.258 +
   1.259 +                // Merging external faces
   1.260 +                {
   1.261 +                  int en = cn;
   1.262 +                  cn = cd ? node_data[cn].prev : node_data[cn].next;
   1.263 +                  cd = node_data[cn].next == en;
   1.264 +
   1.265 +                }
   1.266 +
   1.267 +                if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
   1.268 +                if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
   1.269 +
   1.270 +              }
   1.271 +
   1.272 +              bool d = pn == node_data[n].prev;
   1.273 +
   1.274 +              if (node_data[n].prev == node_data[n].next &&
   1.275 +                  node_data[n].inverted) {
   1.276 +                d = !d;
   1.277 +              }
   1.278 +
   1.279 +              // Embedding arc into external face
   1.280 +              if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
   1.281 +              if (d) node_data[n].prev = rn; else node_data[n].next = rn;
   1.282 +              pn = rn;
   1.283 +
   1.284 +              embed_arc[order_list[n]] = false;
   1.285 +            }
   1.286 +
   1.287 +            if (!merge_roots[node].empty()) {
   1.288 +
   1.289 +              bool d = pn == node_data[n].prev;
   1.290 +
   1.291 +              merge_stack.push_back(std::make_pair(n, d));
   1.292 +
   1.293 +              int rn = merge_roots[node].front();
   1.294 +
   1.295 +              int xn = node_data[rn].next;
   1.296 +              Node xnode = order_list[xn];
   1.297 +
   1.298 +              int yn = node_data[rn].prev;
   1.299 +              Node ynode = order_list[yn];
   1.300 +
   1.301 +              bool rd;
   1.302 +              if (!external(xnode, rorder, child_lists, 
   1.303 +                            ancestor_map, low_map)) {
   1.304 +                rd = true;
   1.305 +              } else if (!external(ynode, rorder, child_lists,
   1.306 +                                   ancestor_map, low_map)) {
   1.307 +                rd = false;
   1.308 +              } else if (pertinent(xnode, embed_arc, merge_roots)) {
   1.309 +                rd = true;
   1.310 +              } else {
   1.311 +                rd = false;
   1.312 +              }
   1.313 +
   1.314 +              merge_stack.push_back(std::make_pair(rn, rd));
   1.315 +
   1.316 +              pn = rn;
   1.317 +              n = rd ? xn : yn;
   1.318 +
   1.319 +            } else if (!external(node, rorder, child_lists,
   1.320 +                                 ancestor_map, low_map)) {
   1.321 +              int nn = (node_data[n].next != pn ?
   1.322 +                        node_data[n].next : node_data[n].prev);
   1.323 +
   1.324 +              bool nd = n == node_data[nn].prev;
   1.325 +
   1.326 +              if (nd) node_data[nn].prev = pn;
   1.327 +              else node_data[nn].next = pn;
   1.328 +
   1.329 +              if (n == node_data[pn].prev) node_data[pn].prev = nn;
   1.330 +              else node_data[pn].next = nn;
   1.331 +
   1.332 +              node_data[nn].inverted =
   1.333 +                (node_data[nn].prev == node_data[nn].next && nd != rd);
   1.334 +
   1.335 +              n = nn;
   1.336 +            }
   1.337 +            else break;
   1.338 +
   1.339 +          }
   1.340 +
   1.341 +          if (!merge_stack.empty() || n == rn) {
   1.342 +            break;
   1.343 +          }
   1.344 +        }
   1.345 +      }
   1.346 +
   1.347 +      void initFace(const Node& node, NodeData& node_data,
   1.348 +                    const OrderMap& order_map, const OrderList& order_list) {
   1.349 +        int n = order_map[node];
   1.350 +        int rn = n + order_list.size();
   1.351 +
   1.352 +        node_data[n].next = node_data[n].prev = rn;
   1.353 +        node_data[rn].next = node_data[rn].prev = n;
   1.354 +
   1.355 +        node_data[n].visited = order_list.size();
   1.356 +        node_data[rn].visited = order_list.size();
   1.357 +
   1.358 +      }
   1.359 +
   1.360 +      bool external(const Node& node, int rorder,
   1.361 +                    ChildLists& child_lists, AncestorMap& ancestor_map,
   1.362 +                    LowMap& low_map) {
   1.363 +        Node child = child_lists[node].first;
   1.364 +
   1.365 +        if (child != INVALID) {
   1.366 +          if (low_map[child] < rorder) return true;
   1.367 +        }
   1.368 +
   1.369 +        if (ancestor_map[node] < rorder) return true;
   1.370 +
   1.371 +        return false;
   1.372 +      }
   1.373 +
   1.374 +      bool pertinent(const Node& node, const EmbedArc& embed_arc,
   1.375 +                     const MergeRoots& merge_roots) {
   1.376 +        return !merge_roots[node].empty() || embed_arc[node];
   1.377 +      }
   1.378 +
   1.379 +    };
   1.380 +
   1.381    }
   1.382  
   1.383    /// \ingroup planar
   1.384    ///
   1.385    /// \brief Planarity checking of an undirected simple graph
   1.386    ///
   1.387 -  /// This class implements the Boyer-Myrvold algorithm for planarity
   1.388 -  /// checking of an undirected graph. This class is a simplified
   1.389 +  /// This function implements the Boyer-Myrvold algorithm for
   1.390 +  /// planarity checking of an undirected graph. It is a simplified
   1.391    /// version of the PlanarEmbedding algorithm class because neither
   1.392    /// the embedding nor the kuratowski subdivisons are not computed.
   1.393 -  template <typename Graph>
   1.394 -  class PlanarityChecking {
   1.395 -  private:
   1.396 -
   1.397 -    TEMPLATE_GRAPH_TYPEDEFS(Graph);
   1.398 -
   1.399 -    const Graph& _graph;
   1.400 -
   1.401 -  private:
   1.402 -
   1.403 -    typedef typename Graph::template NodeMap<Arc> PredMap;
   1.404 -
   1.405 -    typedef typename Graph::template EdgeMap<bool> TreeMap;
   1.406 -
   1.407 -    typedef typename Graph::template NodeMap<int> OrderMap;
   1.408 -    typedef std::vector<Node> OrderList;
   1.409 -
   1.410 -    typedef typename Graph::template NodeMap<int> LowMap;
   1.411 -    typedef typename Graph::template NodeMap<int> AncestorMap;
   1.412 -
   1.413 -    typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
   1.414 -    typedef std::vector<NodeDataNode> NodeData;
   1.415 -
   1.416 -    typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
   1.417 -    typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
   1.418 -
   1.419 -    typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
   1.420 -
   1.421 -    typedef typename Graph::template NodeMap<bool> EmbedArc;
   1.422 -
   1.423 -  public:
   1.424 -
   1.425 -    /// \brief Constructor
   1.426 -    ///
   1.427 -    /// \note The graph should be simple, i.e. parallel and loop arc
   1.428 -    /// free.
   1.429 -    PlanarityChecking(const Graph& graph) : _graph(graph) {}
   1.430 -
   1.431 -    /// \brief Runs the algorithm.
   1.432 -    ///
   1.433 -    /// Runs the algorithm.
   1.434 -    /// \return %True when the graph is planar.
   1.435 -    bool run() {
   1.436 -      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
   1.437 -
   1.438 -      PredMap pred_map(_graph, INVALID);
   1.439 -      TreeMap tree_map(_graph, false);
   1.440 -
   1.441 -      OrderMap order_map(_graph, -1);
   1.442 -      OrderList order_list;
   1.443 -
   1.444 -      AncestorMap ancestor_map(_graph, -1);
   1.445 -      LowMap low_map(_graph, -1);
   1.446 -
   1.447 -      Visitor visitor(_graph, pred_map, tree_map,
   1.448 -                      order_map, order_list, ancestor_map, low_map);
   1.449 -      DfsVisit<Graph, Visitor> visit(_graph, visitor);
   1.450 -      visit.run();
   1.451 -
   1.452 -      ChildLists child_lists(_graph);
   1.453 -      createChildLists(tree_map, order_map, low_map, child_lists);
   1.454 -
   1.455 -      NodeData node_data(2 * order_list.size());
   1.456 -
   1.457 -      EmbedArc embed_arc(_graph, false);
   1.458 -
   1.459 -      MergeRoots merge_roots(_graph);
   1.460 -
   1.461 -      for (int i = order_list.size() - 1; i >= 0; --i) {
   1.462 -
   1.463 -        Node node = order_list[i];
   1.464 -
   1.465 -        Node source = node;
   1.466 -        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
   1.467 -          Node target = _graph.target(e);
   1.468 -
   1.469 -          if (order_map[source] < order_map[target] && tree_map[e]) {
   1.470 -            initFace(target, node_data, order_map, order_list);
   1.471 -          }
   1.472 -        }
   1.473 -
   1.474 -        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
   1.475 -          Node target = _graph.target(e);
   1.476 -
   1.477 -          if (order_map[source] < order_map[target] && !tree_map[e]) {
   1.478 -            embed_arc[target] = true;
   1.479 -            walkUp(target, source, i, pred_map, low_map,
   1.480 -                   order_map, order_list, node_data, merge_roots);
   1.481 -          }
   1.482 -        }
   1.483 -
   1.484 -        for (typename MergeRoots::Value::iterator it =
   1.485 -               merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
   1.486 -          int rn = *it;
   1.487 -          walkDown(rn, i, node_data, order_list, child_lists,
   1.488 -                   ancestor_map, low_map, embed_arc, merge_roots);
   1.489 -        }
   1.490 -        merge_roots[node].clear();
   1.491 -
   1.492 -        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
   1.493 -          Node target = _graph.target(e);
   1.494 -
   1.495 -          if (order_map[source] < order_map[target] && !tree_map[e]) {
   1.496 -            if (embed_arc[target]) {
   1.497 -              return false;
   1.498 -            }
   1.499 -          }
   1.500 -        }
   1.501 -      }
   1.502 -
   1.503 -      return true;
   1.504 -    }
   1.505 -
   1.506 -  private:
   1.507 -
   1.508 -    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
   1.509 -                          const LowMap& low_map, ChildLists& child_lists) {
   1.510 -
   1.511 -      for (NodeIt n(_graph); n != INVALID; ++n) {
   1.512 -        Node source = n;
   1.513 -
   1.514 -        std::vector<Node> targets;
   1.515 -        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
   1.516 -          Node target = _graph.target(e);
   1.517 -
   1.518 -          if (order_map[source] < order_map[target] && tree_map[e]) {
   1.519 -            targets.push_back(target);
   1.520 -          }
   1.521 -        }
   1.522 -
   1.523 -        if (targets.size() == 0) {
   1.524 -          child_lists[source].first = INVALID;
   1.525 -        } else if (targets.size() == 1) {
   1.526 -          child_lists[source].first = targets[0];
   1.527 -          child_lists[targets[0]].prev = INVALID;
   1.528 -          child_lists[targets[0]].next = INVALID;
   1.529 -        } else {
   1.530 -          radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
   1.531 -          for (int i = 1; i < int(targets.size()); ++i) {
   1.532 -            child_lists[targets[i]].prev = targets[i - 1];
   1.533 -            child_lists[targets[i - 1]].next = targets[i];
   1.534 -          }
   1.535 -          child_lists[targets.back()].next = INVALID;
   1.536 -          child_lists[targets.front()].prev = INVALID;
   1.537 -          child_lists[source].first = targets.front();
   1.538 -        }
   1.539 -      }
   1.540 -    }
   1.541 -
   1.542 -    void walkUp(const Node& node, Node root, int rorder,
   1.543 -                const PredMap& pred_map, const LowMap& low_map,
   1.544 -                const OrderMap& order_map, const OrderList& order_list,
   1.545 -                NodeData& node_data, MergeRoots& merge_roots) {
   1.546 -
   1.547 -      int na, nb;
   1.548 -      bool da, db;
   1.549 -
   1.550 -      na = nb = order_map[node];
   1.551 -      da = true; db = false;
   1.552 -
   1.553 -      while (true) {
   1.554 -
   1.555 -        if (node_data[na].visited == rorder) break;
   1.556 -        if (node_data[nb].visited == rorder) break;
   1.557 -
   1.558 -        node_data[na].visited = rorder;
   1.559 -        node_data[nb].visited = rorder;
   1.560 -
   1.561 -        int rn = -1;
   1.562 -
   1.563 -        if (na >= int(order_list.size())) {
   1.564 -          rn = na;
   1.565 -        } else if (nb >= int(order_list.size())) {
   1.566 -          rn = nb;
   1.567 -        }
   1.568 -
   1.569 -        if (rn == -1) {
   1.570 -          int nn;
   1.571 -
   1.572 -          nn = da ? node_data[na].prev : node_data[na].next;
   1.573 -          da = node_data[nn].prev != na;
   1.574 -          na = nn;
   1.575 -
   1.576 -          nn = db ? node_data[nb].prev : node_data[nb].next;
   1.577 -          db = node_data[nn].prev != nb;
   1.578 -          nb = nn;
   1.579 -
   1.580 -        } else {
   1.581 -
   1.582 -          Node rep = order_list[rn - order_list.size()];
   1.583 -          Node parent = _graph.source(pred_map[rep]);
   1.584 -
   1.585 -          if (low_map[rep] < rorder) {
   1.586 -            merge_roots[parent].push_back(rn);
   1.587 -          } else {
   1.588 -            merge_roots[parent].push_front(rn);
   1.589 -          }
   1.590 -
   1.591 -          if (parent != root) {
   1.592 -            na = nb = order_map[parent];
   1.593 -            da = true; db = false;
   1.594 -          } else {
   1.595 -            break;
   1.596 -          }
   1.597 -        }
   1.598 -      }
   1.599 -    }
   1.600 -
   1.601 -    void walkDown(int rn, int rorder, NodeData& node_data,
   1.602 -                  OrderList& order_list, ChildLists& child_lists,
   1.603 -                  AncestorMap& ancestor_map, LowMap& low_map,
   1.604 -                  EmbedArc& embed_arc, MergeRoots& merge_roots) {
   1.605 -
   1.606 -      std::vector<std::pair<int, bool> > merge_stack;
   1.607 -
   1.608 -      for (int di = 0; di < 2; ++di) {
   1.609 -        bool rd = di == 0;
   1.610 -        int pn = rn;
   1.611 -        int n = rd ? node_data[rn].next : node_data[rn].prev;
   1.612 -
   1.613 -        while (n != rn) {
   1.614 -
   1.615 -          Node node = order_list[n];
   1.616 -
   1.617 -          if (embed_arc[node]) {
   1.618 -
   1.619 -            // Merging components on the critical path
   1.620 -            while (!merge_stack.empty()) {
   1.621 -
   1.622 -              // Component root
   1.623 -              int cn = merge_stack.back().first;
   1.624 -              bool cd = merge_stack.back().second;
   1.625 -              merge_stack.pop_back();
   1.626 -
   1.627 -              // Parent of component
   1.628 -              int dn = merge_stack.back().first;
   1.629 -              bool dd = merge_stack.back().second;
   1.630 -              merge_stack.pop_back();
   1.631 -
   1.632 -              Node parent = order_list[dn];
   1.633 -
   1.634 -              // Erasing from merge_roots
   1.635 -              merge_roots[parent].pop_front();
   1.636 -
   1.637 -              Node child = order_list[cn - order_list.size()];
   1.638 -
   1.639 -              // Erasing from child_lists
   1.640 -              if (child_lists[child].prev != INVALID) {
   1.641 -                child_lists[child_lists[child].prev].next =
   1.642 -                  child_lists[child].next;
   1.643 -              } else {
   1.644 -                child_lists[parent].first = child_lists[child].next;
   1.645 -              }
   1.646 -
   1.647 -              if (child_lists[child].next != INVALID) {
   1.648 -                child_lists[child_lists[child].next].prev =
   1.649 -                  child_lists[child].prev;
   1.650 -              }
   1.651 -
   1.652 -              // Merging external faces
   1.653 -              {
   1.654 -                int en = cn;
   1.655 -                cn = cd ? node_data[cn].prev : node_data[cn].next;
   1.656 -                cd = node_data[cn].next == en;
   1.657 -
   1.658 -              }
   1.659 -
   1.660 -              if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
   1.661 -              if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
   1.662 -
   1.663 -            }
   1.664 -
   1.665 -            bool d = pn == node_data[n].prev;
   1.666 -
   1.667 -            if (node_data[n].prev == node_data[n].next &&
   1.668 -                node_data[n].inverted) {
   1.669 -              d = !d;
   1.670 -            }
   1.671 -
   1.672 -            // Embedding arc into external face
   1.673 -            if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
   1.674 -            if (d) node_data[n].prev = rn; else node_data[n].next = rn;
   1.675 -            pn = rn;
   1.676 -
   1.677 -            embed_arc[order_list[n]] = false;
   1.678 -          }
   1.679 -
   1.680 -          if (!merge_roots[node].empty()) {
   1.681 -
   1.682 -            bool d = pn == node_data[n].prev;
   1.683 -
   1.684 -            merge_stack.push_back(std::make_pair(n, d));
   1.685 -
   1.686 -            int rn = merge_roots[node].front();
   1.687 -
   1.688 -            int xn = node_data[rn].next;
   1.689 -            Node xnode = order_list[xn];
   1.690 -
   1.691 -            int yn = node_data[rn].prev;
   1.692 -            Node ynode = order_list[yn];
   1.693 -
   1.694 -            bool rd;
   1.695 -            if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
   1.696 -              rd = true;
   1.697 -            } else if (!external(ynode, rorder, child_lists,
   1.698 -                                 ancestor_map, low_map)) {
   1.699 -              rd = false;
   1.700 -            } else if (pertinent(xnode, embed_arc, merge_roots)) {
   1.701 -              rd = true;
   1.702 -            } else {
   1.703 -              rd = false;
   1.704 -            }
   1.705 -
   1.706 -            merge_stack.push_back(std::make_pair(rn, rd));
   1.707 -
   1.708 -            pn = rn;
   1.709 -            n = rd ? xn : yn;
   1.710 -
   1.711 -          } else if (!external(node, rorder, child_lists,
   1.712 -                               ancestor_map, low_map)) {
   1.713 -            int nn = (node_data[n].next != pn ?
   1.714 -                      node_data[n].next : node_data[n].prev);
   1.715 -
   1.716 -            bool nd = n == node_data[nn].prev;
   1.717 -
   1.718 -            if (nd) node_data[nn].prev = pn;
   1.719 -            else node_data[nn].next = pn;
   1.720 -
   1.721 -            if (n == node_data[pn].prev) node_data[pn].prev = nn;
   1.722 -            else node_data[pn].next = nn;
   1.723 -
   1.724 -            node_data[nn].inverted =
   1.725 -              (node_data[nn].prev == node_data[nn].next && nd != rd);
   1.726 -
   1.727 -            n = nn;
   1.728 -          }
   1.729 -          else break;
   1.730 -
   1.731 -        }
   1.732 -
   1.733 -        if (!merge_stack.empty() || n == rn) {
   1.734 -          break;
   1.735 -        }
   1.736 -      }
   1.737 -    }
   1.738 -
   1.739 -    void initFace(const Node& node, NodeData& node_data,
   1.740 -                  const OrderMap& order_map, const OrderList& order_list) {
   1.741 -      int n = order_map[node];
   1.742 -      int rn = n + order_list.size();
   1.743 -
   1.744 -      node_data[n].next = node_data[n].prev = rn;
   1.745 -      node_data[rn].next = node_data[rn].prev = n;
   1.746 -
   1.747 -      node_data[n].visited = order_list.size();
   1.748 -      node_data[rn].visited = order_list.size();
   1.749 -
   1.750 -    }
   1.751 -
   1.752 -    bool external(const Node& node, int rorder,
   1.753 -                  ChildLists& child_lists, AncestorMap& ancestor_map,
   1.754 -                  LowMap& low_map) {
   1.755 -      Node child = child_lists[node].first;
   1.756 -
   1.757 -      if (child != INVALID) {
   1.758 -        if (low_map[child] < rorder) return true;
   1.759 -      }
   1.760 -
   1.761 -      if (ancestor_map[node] < rorder) return true;
   1.762 -
   1.763 -      return false;
   1.764 -    }
   1.765 -
   1.766 -    bool pertinent(const Node& node, const EmbedArc& embed_arc,
   1.767 -                   const MergeRoots& merge_roots) {
   1.768 -      return !merge_roots[node].empty() || embed_arc[node];
   1.769 -    }
   1.770 -
   1.771 -  };
   1.772 +  template <typename GR>
   1.773 +  bool checkPlanarity(const GR& graph) {
   1.774 +    _planarity_bits::PlanarityChecking<GR> pc(graph);
   1.775 +    return pc.run();
   1.776 +  }
   1.777  
   1.778    /// \ingroup planar
   1.779    ///
   1.780 @@ -712,7 +712,7 @@
   1.781      ///
   1.782      /// The returned map contains the successor of each arc in the
   1.783      /// graph.
   1.784 -    const EmbeddingMap& embedding() const {
   1.785 +    const EmbeddingMap& embeddingMap() const {
   1.786        return _embedding;
   1.787      }
   1.788  
     2.1 --- a/test/planarity_test.cc	Wed Sep 09 15:32:03 2009 +0200
     2.2 +++ b/test/planarity_test.cc	Sun Oct 04 10:15:32 2009 +0200
     2.3 @@ -239,15 +239,18 @@
     2.4      check(simpleGraph(graph), "Test graphs must be simple");
     2.5  
     2.6      PE pe(graph);
     2.7 -    if (pe.run()) {
     2.8 +    bool planar = pe.run();
     2.9 +    check(checkPlanarity(graph) == planar, "Planarity checking failed");
    2.10 +
    2.11 +    if (planar) {
    2.12        checkEmbedding(graph, pe);
    2.13  
    2.14        PlanarDrawing<Graph> pd(graph);
    2.15 -      pd.run(pe.embedding());
    2.16 +      pd.run(pe.embeddingMap());
    2.17        checkDrawing(graph, pd);
    2.18  
    2.19        PlanarColoring<Graph> pc(graph);
    2.20 -      pc.runFiveColoring(pe.embedding());
    2.21 +      pc.runFiveColoring(pe.embeddingMap());
    2.22        checkColoring(graph, pc, 5);
    2.23  
    2.24      } else {