LEMON/LEMON-official Changeset - r862:58c330ad0b5c

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r862:58c330ad0b5c

« 861:30cb42

863:6be1f9 »

r862:58c330ad0b5c

Sun, 04 Oct 2009 10:15:32

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Planarity checking function instead of class (#62)

0 2 0

default

2 files changed with 388 insertions and 385 deletions:

lemon/planarity.h

382

test/planarity_test.cc

↑ Collapse diff ↑

lemon/planarity.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_PLANARITY_H
 		#define LEMON_PLANARITY_H
 		/// \ingroup planar
 		/// \file
 		/// \brief Planarity checking, embedding, drawing and coloring
 		#include <vector>
 		#include <list>
 		#include <lemon/dfs.h>
 		#include <lemon/bfs.h>
 		#include <lemon/radix_sort.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		#include <lemon/bucket_heap.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/edge_set.h>
 		#include <lemon/color.h>
 		#include <lemon/dim2.h>
 		namespace lemon {
 		  namespace _planarity_bits {
 		    template <typename Graph>
 		    struct PlanarityVisitor : DfsVisitor<Graph> {
 		      TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		      typedef typename Graph::template NodeMap<Arc> PredMap;
 		      typedef typename Graph::template EdgeMap<bool> TreeMap;
 		      typedef typename Graph::template NodeMap<int> OrderMap;
 		      typedef std::vector<Node> OrderList;
 		      typedef typename Graph::template NodeMap<int> LowMap;
 		      typedef typename Graph::template NodeMap<int> AncestorMap;
 		      PlanarityVisitor(const Graph& graph,
 		                       PredMap& pred_map, TreeMap& tree_map,
 		                       OrderMap& order_map, OrderList& order_list,
 		                       AncestorMap& ancestor_map, LowMap& low_map)
 		        : _graph(graph), _pred_map(pred_map), _tree_map(tree_map),
 		          _order_map(order_map), _order_list(order_list),
 		          _ancestor_map(ancestor_map), _low_map(low_map) {}
 		      void reach(const Node& node) {
 		        _order_map[node] = _order_list.size();
 		        _low_map[node] = _order_list.size();
 		        _ancestor_map[node] = _order_list.size();
 		        _order_list.push_back(node);
+		      }
 		      void discover(const Arc& arc) {
 		        Node source = _graph.source(arc);
 		        Node target = _graph.target(arc);
 		        _tree_map[arc] = true;
 		        _pred_map[target] = arc;
+		      }
 		      void examine(const Arc& arc) {
 		        Node source = _graph.source(arc);
 		        Node target = _graph.target(arc);
 		        if (_order_map[target] < _order_map[source] && !_tree_map[arc]) {
 		          if (_low_map[source] > _order_map[target]) {
 		            _low_map[source] = _order_map[target];
+		          }
 		          if (_ancestor_map[source] > _order_map[target]) {
 		            _ancestor_map[source] = _order_map[target];
+		          }
+		        }
+		      }
 		      void backtrack(const Arc& arc) {
 		        Node source = _graph.source(arc);
 		        Node target = _graph.target(arc);
 		        if (_low_map[source] > _low_map[target]) {
 		          _low_map[source] = _low_map[target];
+		        }
+		      }
 		      const Graph& _graph;
 		      PredMap& _pred_map;
 		      TreeMap& _tree_map;
 		      OrderMap& _order_map;
 		      OrderList& _order_list;
 		      AncestorMap& _ancestor_map;
 		      LowMap& _low_map;
 		    };
 		    template <typename Graph, bool embedding = true>
 		    struct NodeDataNode {
 		      int prev, next;
 		      int visited;
 		      typename Graph::Arc first;
 		      bool inverted;
 		    };
 		    template <typename Graph>
 		    struct NodeDataNode<Graph, false> {
 		      int prev, next;
 		      int visited;
 		    };
 		    template <typename Graph>
 		    struct ChildListNode {
 		      typedef typename Graph::Node Node;
 		      Node first;
 		      Node prev, next;
 		    };
 		    template <typename Graph>
 		    struct ArcListNode {
 		      typename Graph::Arc prev, next;
 		    };
 		    template <typename Graph>
 		    class PlanarityChecking {
 		    private:
 		      TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		      const Graph& _graph;
 		    private:
 		      typedef typename Graph::template NodeMap<Arc> PredMap;
 		      typedef typename Graph::template EdgeMap<bool> TreeMap;
 		      typedef typename Graph::template NodeMap<int> OrderMap;
 		      typedef std::vector<Node> OrderList;
 		      typedef typename Graph::template NodeMap<int> LowMap;
 		      typedef typename Graph::template NodeMap<int> AncestorMap;
 		      typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
 		      typedef std::vector<NodeDataNode> NodeData;
 		      typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
 		      typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
 		      typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
 		      typedef typename Graph::template NodeMap<bool> EmbedArc;
 		    public:
 		      PlanarityChecking(const Graph& graph) : _graph(graph) {}
 		      bool run() {
 		        typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
 		        PredMap pred_map(_graph, INVALID);
 		        TreeMap tree_map(_graph, false);
 		        OrderMap order_map(_graph, -1);
 		        OrderList order_list;
 		        AncestorMap ancestor_map(_graph, -1);
 		        LowMap low_map(_graph, -1);
 		        Visitor visitor(_graph, pred_map, tree_map,
 		                        order_map, order_list, ancestor_map, low_map);
 		        DfsVisit<Graph, Visitor> visit(_graph, visitor);
 		        visit.run();
 		        ChildLists child_lists(_graph);
 		        createChildLists(tree_map, order_map, low_map, child_lists);
 		        NodeData node_data(2 * order_list.size());
 		        EmbedArc embed_arc(_graph, false);
 		        MergeRoots merge_roots(_graph);
 		        for (int i = order_list.size() - 1; i >= 0; --i) {
 		          Node node = order_list[i];
 		          Node source = node;
 		          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		            Node target = _graph.target(e);
 		            if (order_map[source] < order_map[target] && tree_map[e]) {
 		              initFace(target, node_data, order_map, order_list);
+		            }
+		          }
 		          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		            Node target = _graph.target(e);
 		            if (order_map[source] < order_map[target] && !tree_map[e]) {
 		              embed_arc[target] = true;
 		              walkUp(target, source, i, pred_map, low_map,
 		                     order_map, order_list, node_data, merge_roots);
+		            }
+		          }
 		          for (typename MergeRoots::Value::iterator it =
 		                 merge_roots[node].begin();
 		               it != merge_roots[node].end(); ++it) {
 		            int rn = *it;
 		            walkDown(rn, i, node_data, order_list, child_lists,
 		                     ancestor_map, low_map, embed_arc, merge_roots);
+		          }
 		          merge_roots[node].clear();
 		          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		            Node target = _graph.target(e);
 		            if (order_map[source] < order_map[target] && !tree_map[e]) {
 		              if (embed_arc[target]) {
 		                return false;
+		              }
+		            }
+		          }
+		        }
 		        return true;
+		      }
 		    private:
 		      void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
 		                            const LowMap& low_map, ChildLists& child_lists) {
 		        for (NodeIt n(_graph); n != INVALID; ++n) {
 		          Node source = n;
 		          std::vector<Node> targets;
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node target = _graph.target(e);
 		            if (order_map[source] < order_map[target] && tree_map[e]) {
 		              targets.push_back(target);
+		            }
+		          }
 		          if (targets.size() == 0) {
 		            child_lists[source].first = INVALID;
 		          } else if (targets.size() == 1) {
 		            child_lists[source].first = targets[0];
 		            child_lists[targets[0]].prev = INVALID;
 		            child_lists[targets[0]].next = INVALID;
 		          } else {
 		            radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
 		            for (int i = 1; i < int(targets.size()); ++i) {
 		              child_lists[targets[i]].prev = targets[i - 1];
 		              child_lists[targets[i - 1]].next = targets[i];
+		            }
 		            child_lists[targets.back()].next = INVALID;
 		            child_lists[targets.front()].prev = INVALID;
 		            child_lists[source].first = targets.front();
+		          }
+		        }
+		      }
 		      void walkUp(const Node& node, Node root, int rorder,
 		                  const PredMap& pred_map, const LowMap& low_map,
 		                  const OrderMap& order_map, const OrderList& order_list,
 		                  NodeData& node_data, MergeRoots& merge_roots) {
 		        int na, nb;
 		        bool da, db;
 		        na = nb = order_map[node];
 		        da = true; db = false;
 		        while (true) {
 		          if (node_data[na].visited == rorder) break;
 		          if (node_data[nb].visited == rorder) break;
 		          node_data[na].visited = rorder;
 		          node_data[nb].visited = rorder;
 		          int rn = -1;
 		          if (na >= int(order_list.size())) {
 		            rn = na;
 		          } else if (nb >= int(order_list.size())) {
 		            rn = nb;
+		          }
 		          if (rn == -1) {
 		            int nn;
 		            nn = da ? node_data[na].prev : node_data[na].next;
 		            da = node_data[nn].prev != na;
 		            na = nn;
 		            nn = db ? node_data[nb].prev : node_data[nb].next;
 		            db = node_data[nn].prev != nb;
 		            nb = nn;
 		          } else {
 		            Node rep = order_list[rn - order_list.size()];
 		            Node parent = _graph.source(pred_map[rep]);
 		            if (low_map[rep] < rorder) {
 		              merge_roots[parent].push_back(rn);
 		            } else {
 		              merge_roots[parent].push_front(rn);
+		            }
 		            if (parent != root) {
 		              na = nb = order_map[parent];
 		              da = true; db = false;
 		            } else {
 		              break;
+		            }
+		          }
+		        }
+		      }
 		      void walkDown(int rn, int rorder, NodeData& node_data,
 		                    OrderList& order_list, ChildLists& child_lists,
 		                    AncestorMap& ancestor_map, LowMap& low_map,
 		                    EmbedArc& embed_arc, MergeRoots& merge_roots) {
 		        std::vector<std::pair<int, bool> > merge_stack;
 		        for (int di = 0; di < 2; ++di) {
 		          bool rd = di == 0;
 		          int pn = rn;
 		          int n = rd ? node_data[rn].next : node_data[rn].prev;
 		          while (n != rn) {
 		            Node node = order_list[n];
 		            if (embed_arc[node]) {
 		              // Merging components on the critical path
 		              while (!merge_stack.empty()) {
 		                // Component root
 		                int cn = merge_stack.back().first;
 		                bool cd = merge_stack.back().second;
 		                merge_stack.pop_back();
 		                // Parent of component
 		                int dn = merge_stack.back().first;
 		                bool dd = merge_stack.back().second;
 		                merge_stack.pop_back();
 		                Node parent = order_list[dn];
 		                // Erasing from merge_roots
 		                merge_roots[parent].pop_front();
 		                Node child = order_list[cn - order_list.size()];
 		                // Erasing from child_lists
 		                if (child_lists[child].prev != INVALID) {
 		                  child_lists[child_lists[child].prev].next =
 		                    child_lists[child].next;
 		                } else {
 		                  child_lists[parent].first = child_lists[child].next;
+		                }
 		                if (child_lists[child].next != INVALID) {
 		                  child_lists[child_lists[child].next].prev =
 		                    child_lists[child].prev;
+		                }
 		                // Merging external faces
+		                {
 		                  int en = cn;
 		                  cn = cd ? node_data[cn].prev : node_data[cn].next;
 		                  cd = node_data[cn].next == en;
+		                }
 		                if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
 		                if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
+		              }
 		              bool d = pn == node_data[n].prev;
 		              if (node_data[n].prev == node_data[n].next &&
 		                  node_data[n].inverted) {
 		                d = !d;
+		              }
 		              // Embedding arc into external face
 		              if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
 		              if (d) node_data[n].prev = rn; else node_data[n].next = rn;
 		              pn = rn;
 		              embed_arc[order_list[n]] = false;
+		            }
 		            if (!merge_roots[node].empty()) {
 		              bool d = pn == node_data[n].prev;
 		              merge_stack.push_back(std::make_pair(n, d));
 		              int rn = merge_roots[node].front();
 		              int xn = node_data[rn].next;
 		              Node xnode = order_list[xn];
 		              int yn = node_data[rn].prev;
 		              Node ynode = order_list[yn];
 		              bool rd;
 		              if (!external(xnode, rorder, child_lists,
 		                            ancestor_map, low_map)) {
 		                rd = true;
 		              } else if (!external(ynode, rorder, child_lists,
 		                                   ancestor_map, low_map)) {
 		                rd = false;
 		              } else if (pertinent(xnode, embed_arc, merge_roots)) {
 		                rd = true;
 		              } else {
 		                rd = false;
+		              }
 		              merge_stack.push_back(std::make_pair(rn, rd));
 		              pn = rn;
 		              n = rd ? xn : yn;
 		            } else if (!external(node, rorder, child_lists,
 		                                 ancestor_map, low_map)) {
 		              int nn = (node_data[n].next != pn ?
 		                        node_data[n].next : node_data[n].prev);
 		              bool nd = n == node_data[nn].prev;
 		              if (nd) node_data[nn].prev = pn;
 		              else node_data[nn].next = pn;
 		              if (n == node_data[pn].prev) node_data[pn].prev = nn;
 		              else node_data[pn].next = nn;
 		              node_data[nn].inverted =
 		                (node_data[nn].prev == node_data[nn].next && nd != rd);
 		              n = nn;
+		            }
 		            else break;
+		          }
 		          if (!merge_stack.empty() || n == rn) {
 		            break;
+		          }
+		        }
+		      }
 		      void initFace(const Node& node, NodeData& node_data,
 		                    const OrderMap& order_map, const OrderList& order_list) {
 		        int n = order_map[node];
 		        int rn = n + order_list.size();
 		        node_data[n].next = node_data[n].prev = rn;
 		        node_data[rn].next = node_data[rn].prev = n;
 		        node_data[n].visited = order_list.size();
 		        node_data[rn].visited = order_list.size();
+		      }
 		      bool external(const Node& node, int rorder,
 		                    ChildLists& child_lists, AncestorMap& ancestor_map,
 		                    LowMap& low_map) {
 		        Node child = child_lists[node].first;
 		        if (child != INVALID) {
 		          if (low_map[child] < rorder) return true;
+		        }
 		        if (ancestor_map[node] < rorder) return true;
 		        return false;
+		      }
 		      bool pertinent(const Node& node, const EmbedArc& embed_arc,
 		                     const MergeRoots& merge_roots) {
 		        return !merge_roots[node].empty() || embed_arc[node];
+		      }
 		    };
+		  }
 		  /// \ingroup planar
 		  ///
 		  /// \brief Planarity checking of an undirected simple graph
 		  ///
 		  /// This class implements the Boyer-Myrvold algorithm for planarity
 		  /// checking of an undirected graph. This class is a simplified
 		  /// This function implements the Boyer-Myrvold algorithm for
 		  /// planarity checking of an undirected graph. It is a simplified
 		  /// version of the PlanarEmbedding algorithm class because neither
 		  /// the embedding nor the kuratowski subdivisons are not computed.
 		  template <typename Graph>
 		  class PlanarityChecking {
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    const Graph& _graph;
 		  private:
 		    typedef typename Graph::template NodeMap<Arc> PredMap;
 		    typedef typename Graph::template EdgeMap<bool> TreeMap;
 		    typedef typename Graph::template NodeMap<int> OrderMap;
 		    typedef std::vector<Node> OrderList;
 		    typedef typename Graph::template NodeMap<int> LowMap;
 		    typedef typename Graph::template NodeMap<int> AncestorMap;
 		    typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
 		    typedef std::vector<NodeDataNode> NodeData;
 		    typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
 		    typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
 		    typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
 		    typedef typename Graph::template NodeMap<bool> EmbedArc;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// \note The graph should be simple, i.e. parallel and loop arc
 		    /// free.
 		    PlanarityChecking(const Graph& graph) : _graph(graph) {}
 		    /// \brief Runs the algorithm.
 		    ///
 		    /// Runs the algorithm.
 		    /// \return %True when the graph is planar.
 		    bool run() {
 		      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
 		      PredMap pred_map(_graph, INVALID);
 		      TreeMap tree_map(_graph, false);
 		      OrderMap order_map(_graph, -1);
 		      OrderList order_list;
 		      AncestorMap ancestor_map(_graph, -1);
 		      LowMap low_map(_graph, -1);
 		      Visitor visitor(_graph, pred_map, tree_map,
 		                      order_map, order_list, ancestor_map, low_map);
 		      DfsVisit<Graph, Visitor> visit(_graph, visitor);
 		      visit.run();
 		      ChildLists child_lists(_graph);
 		      createChildLists(tree_map, order_map, low_map, child_lists);
 		      NodeData node_data(2 * order_list.size());
 		      EmbedArc embed_arc(_graph, false);
 		      MergeRoots merge_roots(_graph);
 		      for (int i = order_list.size() - 1; i >= 0; --i) {
 		        Node node = order_list[i];
 		        Node source = node;
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && tree_map[e]) {
 		            initFace(target, node_data, order_map, order_list);
+		          }
+		        }
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && !tree_map[e]) {
 		            embed_arc[target] = true;
 		            walkUp(target, source, i, pred_map, low_map,
 		                   order_map, order_list, node_data, merge_roots);
+		          }
+		        }
 		        for (typename MergeRoots::Value::iterator it =
 		               merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
 		          int rn = *it;
 		          walkDown(rn, i, node_data, order_list, child_lists,
 		                   ancestor_map, low_map, embed_arc, merge_roots);
+		        }
 		        merge_roots[node].clear();
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && !tree_map[e]) {
 		            if (embed_arc[target]) {
 		              return false;
+		            }
+		          }
+		        }
+		      }
 		      return true;
+		    }
 		  private:
 		    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
 		                          const LowMap& low_map, ChildLists& child_lists) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        Node source = n;
 		        std::vector<Node> targets;
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && tree_map[e]) {
 		            targets.push_back(target);
+		          }
+		        }
 		        if (targets.size() == 0) {
 		          child_lists[source].first = INVALID;
 		        } else if (targets.size() == 1) {
 		          child_lists[source].first = targets[0];
 		          child_lists[targets[0]].prev = INVALID;
 		          child_lists[targets[0]].next = INVALID;
 		        } else {
 		          radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
 		          for (int i = 1; i < int(targets.size()); ++i) {
 		            child_lists[targets[i]].prev = targets[i - 1];
 		            child_lists[targets[i - 1]].next = targets[i];
+		          }
 		          child_lists[targets.back()].next = INVALID;
 		          child_lists[targets.front()].prev = INVALID;
 		          child_lists[source].first = targets.front();
+		        }
+		      }
+		    }
 		    void walkUp(const Node& node, Node root, int rorder,
 		                const PredMap& pred_map, const LowMap& low_map,
 		                const OrderMap& order_map, const OrderList& order_list,
 		                NodeData& node_data, MergeRoots& merge_roots) {
 		      int na, nb;
 		      bool da, db;
 		      na = nb = order_map[node];
 		      da = true; db = false;
 		      while (true) {
 		        if (node_data[na].visited == rorder) break;
 		        if (node_data[nb].visited == rorder) break;
 		        node_data[na].visited = rorder;
 		        node_data[nb].visited = rorder;
 		        int rn = -1;
 		        if (na >= int(order_list.size())) {
 		          rn = na;
 		        } else if (nb >= int(order_list.size())) {
 		          rn = nb;
+		        }
 		        if (rn == -1) {
 		          int nn;
 		          nn = da ? node_data[na].prev : node_data[na].next;
 		          da = node_data[nn].prev != na;
 		          na = nn;
 		          nn = db ? node_data[nb].prev : node_data[nb].next;
 		          db = node_data[nn].prev != nb;
 		          nb = nn;
 		        } else {
 		          Node rep = order_list[rn - order_list.size()];
 		          Node parent = _graph.source(pred_map[rep]);
 		          if (low_map[rep] < rorder) {
 		            merge_roots[parent].push_back(rn);
 		          } else {
 		            merge_roots[parent].push_front(rn);
+		          }
 		          if (parent != root) {
 		            na = nb = order_map[parent];
 		            da = true; db = false;
 		          } else {
 		            break;
+		          }
+		        }
+		      }
+		    }
 		    void walkDown(int rn, int rorder, NodeData& node_data,
 		                  OrderList& order_list, ChildLists& child_lists,
 		                  AncestorMap& ancestor_map, LowMap& low_map,
 		                  EmbedArc& embed_arc, MergeRoots& merge_roots) {
 		      std::vector<std::pair<int, bool> > merge_stack;
 		      for (int di = 0; di < 2; ++di) {
 		        bool rd = di == 0;
 		        int pn = rn;
 		        int n = rd ? node_data[rn].next : node_data[rn].prev;
 		        while (n != rn) {
 		          Node node = order_list[n];
 		          if (embed_arc[node]) {
 		            // Merging components on the critical path
 		            while (!merge_stack.empty()) {
 		              // Component root
 		              int cn = merge_stack.back().first;
 		              bool cd = merge_stack.back().second;
 		              merge_stack.pop_back();
 		              // Parent of component
 		              int dn = merge_stack.back().first;
 		              bool dd = merge_stack.back().second;
 		              merge_stack.pop_back();
 		              Node parent = order_list[dn];
 		              // Erasing from merge_roots
 		              merge_roots[parent].pop_front();
 		              Node child = order_list[cn - order_list.size()];
 		              // Erasing from child_lists
 		              if (child_lists[child].prev != INVALID) {
 		                child_lists[child_lists[child].prev].next =
 		                  child_lists[child].next;
 		              } else {
 		                child_lists[parent].first = child_lists[child].next;
+		              }
 		              if (child_lists[child].next != INVALID) {
 		                child_lists[child_lists[child].next].prev =
 		                  child_lists[child].prev;
+		              }
 		              // Merging external faces
+		              {
 		                int en = cn;
 		                cn = cd ? node_data[cn].prev : node_data[cn].next;
 		                cd = node_data[cn].next == en;
+		              }
 		              if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
 		              if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
+		            }
 		            bool d = pn == node_data[n].prev;
 		            if (node_data[n].prev == node_data[n].next &&
 		                node_data[n].inverted) {
 		              d = !d;
+		            }
 		            // Embedding arc into external face
 		            if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
 		            if (d) node_data[n].prev = rn; else node_data[n].next = rn;
 		            pn = rn;
 		            embed_arc[order_list[n]] = false;
+		          }
 		          if (!merge_roots[node].empty()) {
 		            bool d = pn == node_data[n].prev;
 		            merge_stack.push_back(std::make_pair(n, d));
 		            int rn = merge_roots[node].front();
 		            int xn = node_data[rn].next;
 		            Node xnode = order_list[xn];
 		            int yn = node_data[rn].prev;
 		            Node ynode = order_list[yn];
 		            bool rd;
 		            if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
 		              rd = true;
 		            } else if (!external(ynode, rorder, child_lists,
 		                                 ancestor_map, low_map)) {
 		              rd = false;
 		            } else if (pertinent(xnode, embed_arc, merge_roots)) {
 		              rd = true;
 		            } else {
 		              rd = false;
+		            }
 		            merge_stack.push_back(std::make_pair(rn, rd));
 		            pn = rn;
 		            n = rd ? xn : yn;
 		          } else if (!external(node, rorder, child_lists,
 		                               ancestor_map, low_map)) {
 		            int nn = (node_data[n].next != pn ?
 		                      node_data[n].next : node_data[n].prev);
 		            bool nd = n == node_data[nn].prev;
 		            if (nd) node_data[nn].prev = pn;
 		            else node_data[nn].next = pn;
 		            if (n == node_data[pn].prev) node_data[pn].prev = nn;
 		            else node_data[pn].next = nn;
 		            node_data[nn].inverted =
 		              (node_data[nn].prev == node_data[nn].next && nd != rd);
 		            n = nn;
+		          }
 		          else break;
+		        }
 		        if (!merge_stack.empty() || n == rn) {
 		          break;
+		        }
+		      }
+		    }
 		    void initFace(const Node& node, NodeData& node_data,
 		                  const OrderMap& order_map, const OrderList& order_list) {
 		      int n = order_map[node];
 		      int rn = n + order_list.size();
 		      node_data[n].next = node_data[n].prev = rn;
 		      node_data[rn].next = node_data[rn].prev = n;
 		      node_data[n].visited = order_list.size();
 		      node_data[rn].visited = order_list.size();
+		    }
 		    bool external(const Node& node, int rorder,
 		                  ChildLists& child_lists, AncestorMap& ancestor_map,
 		                  LowMap& low_map) {
 		      Node child = child_lists[node].first;
 		      if (child != INVALID) {
 		        if (low_map[child] < rorder) return true;
+		      }
 		      if (ancestor_map[node] < rorder) return true;
 		      return false;
+		    }
 		    bool pertinent(const Node& node, const EmbedArc& embed_arc,
 		                   const MergeRoots& merge_roots) {
 		      return !merge_roots[node].empty() || embed_arc[node];
+		    }
-		  };
+		  template <typename GR>
 		  bool checkPlanarity(const GR& graph) {
 		    _planarity_bits::PlanarityChecking<GR> pc(graph);
 		    return pc.run();
+		  }
 		  /// \ingroup planar
 		  ///
 		  /// \brief Planar embedding of an undirected simple graph
 		  ///
 		  /// This class implements the Boyer-Myrvold algorithm for planar
 		  /// embedding of an undirected graph. The planar embedding is an
 		  /// ordering of the outgoing edges of the nodes, which is a possible
 		  /// configuration to draw the graph in the plane. If there is not
 		  /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
 		  /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on
 		  /// 3 ANode and 3 BNode) subdivision.
 		  ///
 		  /// The current implementation calculates either an embedding or a
 		  /// Kuratowski subdivision. The running time of the algorithm is
 		  /// \f$ O(n) \f$.
 		  template <typename Graph>
 		  class PlanarEmbedding {
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    const Graph& _graph;
 		    typename Graph::template ArcMap<Arc> _embedding;
 		    typename Graph::template EdgeMap<bool> _kuratowski;
 		  private:
 		    typedef typename Graph::template NodeMap<Arc> PredMap;
 		    typedef typename Graph::template EdgeMap<bool> TreeMap;
 		    typedef typename Graph::template NodeMap<int> OrderMap;
 		    typedef std::vector<Node> OrderList;
 		    typedef typename Graph::template NodeMap<int> LowMap;
 		    typedef typename Graph::template NodeMap<int> AncestorMap;
 		    typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
 		    typedef std::vector<NodeDataNode> NodeData;
 		    typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
 		    typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
 		    typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
 		    typedef typename Graph::template NodeMap<Arc> EmbedArc;
 		    typedef _planarity_bits::ArcListNode<Graph> ArcListNode;
 		    typedef typename Graph::template ArcMap<ArcListNode> ArcLists;
 		    typedef typename Graph::template NodeMap<bool> FlipMap;
 		    typedef typename Graph::template NodeMap<int> TypeMap;
 		    enum IsolatorNodeType {
 		      HIGHX = 6, LOWX = 7,
 		      HIGHY = 8, LOWY = 9,
 		      ROOT = 10, PERTINENT = 11,
 		      INTERNAL = 12
 		    };
 		  public:
 		    /// \brief The map for store of embedding
 		    typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
 		    /// \brief Constructor
 		    ///
 		    /// \note The graph should be simple, i.e. parallel and loop arc
 		    /// free.
 		    PlanarEmbedding(const Graph& graph)
 		      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
 		    /// \brief Runs the algorithm.
 		    ///
 		    /// Runs the algorithm.
 		    /// \param kuratowski If the parameter is false, then the
 		    /// algorithm does not compute a Kuratowski subdivision.
 		    ///\return %True when the graph is planar.
 		    bool run(bool kuratowski = true) {
 		      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
 		      PredMap pred_map(_graph, INVALID);
 		      TreeMap tree_map(_graph, false);
 		      OrderMap order_map(_graph, -1);
 		      OrderList order_list;
 		      AncestorMap ancestor_map(_graph, -1);
 		      LowMap low_map(_graph, -1);
 		      Visitor visitor(_graph, pred_map, tree_map,
 		                      order_map, order_list, ancestor_map, low_map);
 		      DfsVisit<Graph, Visitor> visit(_graph, visitor);
 		      visit.run();
 		      ChildLists child_lists(_graph);
 		      createChildLists(tree_map, order_map, low_map, child_lists);
 		      NodeData node_data(2 * order_list.size());
 		      EmbedArc embed_arc(_graph, INVALID);
 		      MergeRoots merge_roots(_graph);
 		      ArcLists arc_lists(_graph);
 		      FlipMap flip_map(_graph, false);
 		      for (int i = order_list.size() - 1; i >= 0; --i) {
 		        Node node = order_list[i];
 		        node_data[i].first = INVALID;
 		        Node source = node;
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && tree_map[e]) {
 		            initFace(target, arc_lists, node_data,
 		                     pred_map, order_map, order_list);
+		          }
+		        }
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && !tree_map[e]) {
 		            embed_arc[target] = e;
 		            walkUp(target, source, i, pred_map, low_map,
 		                   order_map, order_list, node_data, merge_roots);
+		          }
+		        }
 		        for (typename MergeRoots::Value::iterator it =
 		               merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
 		          int rn = *it;
 		          walkDown(rn, i, node_data, arc_lists, flip_map, order_list,
 		                   child_lists, ancestor_map, low_map, embed_arc, merge_roots);
+		        }
 		        merge_roots[node].clear();
 		        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && !tree_map[e]) {
 		            if (embed_arc[target] != INVALID) {
 		              if (kuratowski) {
 		                isolateKuratowski(e, node_data, arc_lists, flip_map,
 		                                  order_map, order_list, pred_map, child_lists,
 		                                  ancestor_map, low_map,
 		                                  embed_arc, merge_roots);
+		              }
 		              return false;
+		            }
+		          }
+		        }
+		      }
 		      for (int i = 0; i < int(order_list.size()); ++i) {
 		        mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
 		                            child_lists, arc_lists);
 		        storeEmbedding(order_list[i], node_data, order_map, pred_map,
 		                       arc_lists, flip_map);
+		      }
 		      return true;
+		    }
 		    /// \brief Gives back the successor of an arc
 		    ///
 		    /// Gives back the successor of an arc. This function makes
 		    /// possible to query the cyclic order of the outgoing arcs from
 		    /// a node.
 		    Arc next(const Arc& arc) const {
 		      return _embedding[arc];
+		    }
 		    /// \brief Gives back the calculated embedding map
 		    ///
 		    /// The returned map contains the successor of each arc in the
 		    /// graph.
-		    const EmbeddingMap& embedding() const {
+		    const EmbeddingMap& embeddingMap() const {
 		      return _embedding;
+		    }
 		    /// \brief Gives back true if the undirected arc is in the
 		    /// kuratowski subdivision
 		    ///
 		    /// Gives back true if the undirected arc is in the kuratowski
 		    /// subdivision
 		    /// \note The \c run() had to be called with true value.
 		    bool kuratowski(const Edge& edge) {
 		      return _kuratowski[edge];
+		    }
 		  private:
 		    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
 		                          const LowMap& low_map, ChildLists& child_lists) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        Node source = n;
 		        std::vector<Node> targets;
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node target = _graph.target(e);
 		          if (order_map[source] < order_map[target] && tree_map[e]) {
 		            targets.push_back(target);
+		          }
+		        }
 		        if (targets.size() == 0) {
 		          child_lists[source].first = INVALID;
 		        } else if (targets.size() == 1) {
 		          child_lists[source].first = targets[0];
 		          child_lists[targets[0]].prev = INVALID;
 		          child_lists[targets[0]].next = INVALID;
 		        } else {
 		          radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
 		          for (int i = 1; i < int(targets.size()); ++i) {
 		            child_lists[targets[i]].prev = targets[i - 1];
 		            child_lists[targets[i - 1]].next = targets[i];
+		          }
 		          child_lists[targets.back()].next = INVALID;
 		          child_lists[targets.front()].prev = INVALID;
 		          child_lists[source].first = targets.front();
+		        }
+		      }
+		    }
 		    void walkUp(const Node& node, Node root, int rorder,
 		                const PredMap& pred_map, const LowMap& low_map,
 		                const OrderMap& order_map, const OrderList& order_list,
 		                NodeData& node_data, MergeRoots& merge_roots) {
 		      int na, nb;
 		      bool da, db;
 		      na = nb = order_map[node];
 		      da = true; db = false;
 		      while (true) {
 		        if (node_data[na].visited == rorder) break;
 		        if (node_data[nb].visited == rorder) break;
 		        node_data[na].visited = rorder;
 		        node_data[nb].visited = rorder;
 		        int rn = -1;
 		        if (na >= int(order_list.size())) {
 		          rn = na;
 		        } else if (nb >= int(order_list.size())) {
 		          rn = nb;
+		        }
 		        if (rn == -1) {
 		          int nn;
 		          nn = da ? node_data[na].prev : node_data[na].next;
 		          da = node_data[nn].prev != na;
 		          na = nn;
 		          nn = db ? node_data[nb].prev : node_data[nb].next;
 		          db = node_data[nn].prev != nb;
 		          nb = nn;
 		        } else {
 		          Node rep = order_list[rn - order_list.size()];
 		          Node parent = _graph.source(pred_map[rep]);
 		          if (low_map[rep] < rorder) {
 		            merge_roots[parent].push_back(rn);
 		          } else {
 		            merge_roots[parent].push_front(rn);
+		          }
 		          if (parent != root) {
 		            na = nb = order_map[parent];
 		            da = true; db = false;
 		          } else {
 		            break;
+		          }
+		        }
+		      }
+		    }
 		    void walkDown(int rn, int rorder, NodeData& node_data,
 		                  ArcLists& arc_lists, FlipMap& flip_map,
 		                  OrderList& order_list, ChildLists& child_lists,
 		                  AncestorMap& ancestor_map, LowMap& low_map,
 		                  EmbedArc& embed_arc, MergeRoots& merge_roots) {
 		      std::vector<std::pair<int, bool> > merge_stack;
 		      for (int di = 0; di < 2; ++di) {
 		        bool rd = di == 0;
 		        int pn = rn;
 		        int n = rd ? node_data[rn].next : node_data[rn].prev;
 		        while (n != rn) {
 		          Node node = order_list[n];
 		          if (embed_arc[node] != INVALID) {
 		            // Merging components on the critical path
 		            while (!merge_stack.empty()) {
 		              // Component root
 		              int cn = merge_stack.back().first;
 		              bool cd = merge_stack.back().second;
 		              merge_stack.pop_back();
 		              // Parent of component
 		              int dn = merge_stack.back().first;
 		              bool dd = merge_stack.back().second;
 		              merge_stack.pop_back();
 		              Node parent = order_list[dn];
 		              // Erasing from merge_roots
 		              merge_roots[parent].pop_front();
 		              Node child = order_list[cn - order_list.size()];
 		              // Erasing from child_lists
 		              if (child_lists[child].prev != INVALID) {
 		                child_lists[child_lists[child].prev].next =
 		                  child_lists[child].next;
 		              } else {
 		                child_lists[parent].first = child_lists[child].next;
+		              }
 		              if (child_lists[child].next != INVALID) {
 		                child_lists[child_lists[child].next].prev =
 		                  child_lists[child].prev;
+		              }
 		              // Merging arcs + flipping
 		              Arc de = node_data[dn].first;
 		              Arc ce = node_data[cn].first;
 		              flip_map[order_list[cn - order_list.size()]] = cd != dd;
 		              if (cd != dd) {
 		                std::swap(arc_lists[ce].prev, arc_lists[ce].next);
 		                ce = arc_lists[ce].prev;
 		                std::swap(arc_lists[ce].prev, arc_lists[ce].next);
+		              }
+		              {
 		                Arc dne = arc_lists[de].next;
 		                Arc cne = arc_lists[ce].next;
 		                arc_lists[de].next = cne;
 		                arc_lists[ce].next = dne;
 		                arc_lists[dne].prev = ce;
 		                arc_lists[cne].prev = de;
+		              }
 		              if (dd) {
 		                node_data[dn].first = ce;
+		              }
 		              // Merging external faces
+		              {
 		                int en = cn;
 		                cn = cd ? node_data[cn].prev : node_data[cn].next;
 		                cd = node_data[cn].next == en;
 		                 if (node_data[cn].prev == node_data[cn].next &&
 		                    node_data[cn].inverted) {
 		                   cd = !cd;
+		                 }
+		              }
 		              if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
 		              if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
+		            }
 		            bool d = pn == node_data[n].prev;
 		            if (node_data[n].prev == node_data[n].next &&
 		                node_data[n].inverted) {
 		              d = !d;
+		            }
 		            // Add new arc
+		            {
 		              Arc arc = embed_arc[node];
 		              Arc re = node_data[rn].first;
 		              arc_lists[arc_lists[re].next].prev = arc;
 		              arc_lists[arc].next = arc_lists[re].next;
 		              arc_lists[arc].prev = re;
 		              arc_lists[re].next = arc;
 		              if (!rd) {
 		                node_data[rn].first = arc;
+		              }
 		              Arc rev = _graph.oppositeArc(arc);
 		              Arc e = node_data[n].first;
 		              arc_lists[arc_lists[e].next].prev = rev;
 		              arc_lists[rev].next = arc_lists[e].next;
 		              arc_lists[rev].prev = e;
 		              arc_lists[e].next = rev;
 		              if (d) {
 		                node_data[n].first = rev;
+		              }
+		            }
 		            // Embedding arc into external face
 		            if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
 		            if (d) node_data[n].prev = rn; else node_data[n].next = rn;
 		            pn = rn;
 		            embed_arc[order_list[n]] = INVALID;
+		          }
 		          if (!merge_roots[node].empty()) {
 		            bool d = pn == node_data[n].prev;
 		            if (node_data[n].prev == node_data[n].next &&
 		                node_data[n].inverted) {
 		              d = !d;
+		            }
 		            merge_stack.push_back(std::make_pair(n, d));
 		            int rn = merge_roots[node].front();
 		            int xn = node_data[rn].next;
 		            Node xnode = order_list[xn];
 		            int yn = node_data[rn].prev;
 		            Node ynode = order_list[yn];
 		            bool rd;
 		            if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
 		              rd = true;
 		            } else if (!external(ynode, rorder, child_lists,
 		                                 ancestor_map, low_map)) {
 		              rd = false;
 		            } else if (pertinent(xnode, embed_arc, merge_roots)) {
 		              rd = true;
 		            } else {
 		              rd = false;
+		            }
 		            merge_stack.push_back(std::make_pair(rn, rd));
 		            pn = rn;
 		            n = rd ? xn : yn;
 		          } else if (!external(node, rorder, child_lists,
 		                               ancestor_map, low_map)) {
 		            int nn = (node_data[n].next != pn ?
 		                      node_data[n].next : node_data[n].prev);
 		            bool nd = n == node_data[nn].prev;
 		            if (nd) node_data[nn].prev = pn;
 		            else node_data[nn].next = pn;
 		            if (n == node_data[pn].prev) node_data[pn].prev = nn;
 		            else node_data[pn].next = nn;
 		            node_data[nn].inverted =
 		              (node_data[nn].prev == node_data[nn].next && nd != rd);
 		            n = nn;
+		          }
 		          else break;
+		        }
 		        if (!merge_stack.empty() || n == rn) {
 		          break;
+		        }
+		      }
+		    }
 		    void initFace(const Node& node, ArcLists& arc_lists,
 		                  NodeData& node_data, const PredMap& pred_map,
 		                  const OrderMap& order_map, const OrderList& order_list) {
 		      int n = order_map[node];
 		      int rn = n + order_list.size();
 		      node_data[n].next = node_data[n].prev = rn;
 		      node_data[rn].next = node_data[rn].prev = n;
 		      node_data[n].visited = order_list.size();
 		      node_data[rn].visited = order_list.size();
 		      node_data[n].inverted = false;
 		      node_data[rn].inverted = false;
 		      Arc arc = pred_map[node];
 		      Arc rev = _graph.oppositeArc(arc);
 		      node_data[rn].first = arc;
 		      node_data[n].first = rev;
 		      arc_lists[arc].prev = arc;
 		      arc_lists[arc].next = arc;
 		      arc_lists[rev].prev = rev;
 		      arc_lists[rev].next = rev;
+		    }
 		    void mergeRemainingFaces(const Node& node, NodeData& node_data,
 		                             OrderList& order_list, OrderMap& order_map,
 		                             ChildLists& child_lists, ArcLists& arc_lists) {
 		      while (child_lists[node].first != INVALID) {
 		        int dd = order_map[node];
 		        Node child = child_lists[node].first;
 		        int cd = order_map[child] + order_list.size();
 		        child_lists[node].first = child_lists[child].next;
 		        Arc de = node_data[dd].first;
 		        Arc ce = node_data[cd].first;
 		        if (de != INVALID) {
 		          Arc dne = arc_lists[de].next;
 		          Arc cne = arc_lists[ce].next;
 		          arc_lists[de].next = cne;
 		          arc_lists[ce].next = dne;
 		          arc_lists[dne].prev = ce;
 		          arc_lists[cne].prev = de;
+		        }
 		        node_data[dd].first = ce;
+		      }
+		    }
 		    void storeEmbedding(const Node& node, NodeData& node_data,
 		                        OrderMap& order_map, PredMap& pred_map,
 		                        ArcLists& arc_lists, FlipMap& flip_map) {
 		      if (node_data[order_map[node]].first == INVALID) return;
 		      if (pred_map[node] != INVALID) {
 		        Node source = _graph.source(pred_map[node]);
 		        flip_map[node] = flip_map[node] != flip_map[source];
+		      }
 		      Arc first = node_data[order_map[node]].first;
 		      Arc prev = first;
 		      Arc arc = flip_map[node] ?
 		        arc_lists[prev].prev : arc_lists[prev].next;
 		      _embedding[prev] = arc;
 		      while (arc != first) {
 		        Arc next = arc_lists[arc].prev == prev ?
 		          arc_lists[arc].next : arc_lists[arc].prev;
 		        prev = arc; arc = next;
 		        _embedding[prev] = arc;
+		      }
+		    }
 		    bool external(const Node& node, int rorder,
 		                  ChildLists& child_lists, AncestorMap& ancestor_map,
 		                  LowMap& low_map) {
 		      Node child = child_lists[node].first;
 		      if (child != INVALID) {
 		        if (low_map[child] < rorder) return true;
+		      }
 		      if (ancestor_map[node] < rorder) return true;
 		      return false;
+		    }
 		    bool pertinent(const Node& node, const EmbedArc& embed_arc,
 		                   const MergeRoots& merge_roots) {
 		      return !merge_roots[node].empty() || embed_arc[node] != INVALID;
+		    }
 		    int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
 		                 AncestorMap& ancestor_map, LowMap& low_map) {
 		      int low_point;
 		      Node child = child_lists[node].first;
 		      if (child != INVALID) {
 		        low_point = low_map[child];
 		      } else {
 		        low_point = order_map[node];
+		      }
 		      if (low_point > ancestor_map[node]) {
 		        low_point = ancestor_map[node];
+		      }
 		      return low_point;
+		    }
 		    int findComponentRoot(Node root, Node node, ChildLists& child_lists,
 		                          OrderMap& order_map, OrderList& order_list) {
 		      int order = order_map[root];
 		      int norder = order_map[node];
 		      Node child = child_lists[root].first;
 		      while (child != INVALID) {
 		        int corder = order_map[child];
 		        if (corder > order && corder < norder) {
 		          order = corder;
+		        }
 		        child = child_lists[child].next;
+		      }
 		      return order + order_list.size();
+		    }
 		    Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data,
 		                       EmbedArc& embed_arc, MergeRoots& merge_roots) {
 		      Node wnode =_graph.target(node_data[order_map[node]].first);
 		      while (!pertinent(wnode, embed_arc, merge_roots)) {
 		        wnode = _graph.target(node_data[order_map[wnode]].first);
+		      }
 		      return wnode;
+		    }
 		    Node findExternal(Node node, int rorder, OrderMap& order_map,
 		                      ChildLists& child_lists, AncestorMap& ancestor_map,
 		                      LowMap& low_map, NodeData& node_data) {
 		      Node wnode =_graph.target(node_data[order_map[node]].first);
 		      while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
 		        wnode = _graph.target(node_data[order_map[wnode]].first);
+		      }
 		      return wnode;
+		    }
 		    void markCommonPath(Node node, int rorder, Node& wnode, Node& znode,
 		                        OrderList& order_list, OrderMap& order_map,
 		                        NodeData& node_data, ArcLists& arc_lists,
 		                        EmbedArc& embed_arc, MergeRoots& merge_roots,
 		                        ChildLists& child_lists, AncestorMap& ancestor_map,
 		                        LowMap& low_map) {
 		      Node cnode = node;
 		      Node pred = INVALID;
 		      while (true) {
 		        bool pert = pertinent(cnode, embed_arc, merge_roots);
 		        bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
 		        if (pert && ext) {
 		          if (!merge_roots[cnode].empty()) {
 		            int cn = merge_roots[cnode].back();
 		            if (low_map[order_list[cn - order_list.size()]] < rorder) {
 		              Arc arc = node_data[cn].first;
 		              _kuratowski.set(arc, true);
 		              pred = cnode;
 		              cnode = _graph.target(arc);
 		              continue;
+		            }
+		          }
 		          wnode = znode = cnode;
 		          return;
 		        } else if (pert) {
 		          wnode = cnode;
 		          while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
 		            Arc arc = node_data[order_map[cnode]].first;
 		            if (_graph.target(arc) == pred) {
 		              arc = arc_lists[arc].next;
+		            }
 		            _kuratowski.set(arc, true);
 		            Node next = _graph.target(arc);
 		            pred = cnode; cnode = next;
+		          }
 		          znode = cnode;
 		          return;
 		        } else if (ext) {
 		          znode = cnode;
 		          while (!pertinent(cnode, embed_arc, merge_roots)) {
 		            Arc arc = node_data[order_map[cnode]].first;
 		            if (_graph.target(arc) == pred) {
 		              arc = arc_lists[arc].next;
+		            }
 		            _kuratowski.set(arc, true);
 		            Node next = _graph.target(arc);
 		            pred = cnode; cnode = next;
+		          }
 		          wnode = cnode;
 		          return;
 		        } else {
 		          Arc arc = node_data[order_map[cnode]].first;
 		          if (_graph.target(arc) == pred) {
 		            arc = arc_lists[arc].next;
+		          }
 		          _kuratowski.set(arc, true);
 		          Node next = _graph.target(arc);
 		          pred = cnode; cnode = next;
+		        }
+		      }
+		    }
 		    void orientComponent(Node root, int rn, OrderMap& order_map,
 		                         PredMap& pred_map, NodeData& node_data,
 		                         ArcLists& arc_lists, FlipMap& flip_map,
 		                         TypeMap& type_map) {
 		      node_data[order_map[root]].first = node_data[rn].first;
 		      type_map[root] = 1;
 		      std::vector<Node> st, qu;
 		      st.push_back(root);
 		      while (!st.empty()) {
 		        Node node = st.back();
 		        st.pop_back();
 		        qu.push_back(node);
 		        Arc arc = node_data[order_map[node]].first;
 		        if (type_map[_graph.target(arc)] == 0) {
 		          st.push_back(_graph.target(arc));
 		          type_map[_graph.target(arc)] = 1;
+		        }
 		        Arc last = arc, pred = arc;
 		        arc = arc_lists[arc].next;
 		        while (arc != last) {
 		          if (type_map[_graph.target(arc)] == 0) {
 		            st.push_back(_graph.target(arc));
 		            type_map[_graph.target(arc)] = 1;
+		          }
 		          Arc next = arc_lists[arc].next != pred ?
 		            arc_lists[arc].next : arc_lists[arc].prev;
 		          pred = arc; arc = next;
+		        }
+		      }
 		      type_map[root] = 2;
 		      flip_map[root] = false;
 		      for (int i = 1; i < int(qu.size()); ++i) {
 		        Node node = qu[i];
 		        while (type_map[node] != 2) {
 		          st.push_back(node);
 		          type_map[node] = 2;
 		          node = _graph.source(pred_map[node]);
+		        }
 		        bool flip = flip_map[node];
 		        while (!st.empty()) {
 		          node = st.back();
 		          st.pop_back();
 		          flip_map[node] = flip != flip_map[node];
 		          flip = flip_map[node];
 		          if (flip) {
 		            Arc arc = node_data[order_map[node]].first;
 		            std::swap(arc_lists[arc].prev, arc_lists[arc].next);
 		            arc = arc_lists[arc].prev;
 		            std::swap(arc_lists[arc].prev, arc_lists[arc].next);
 		            node_data[order_map[node]].first = arc;
+		          }
+		        }
+		      }
 		      for (int i = 0; i < int(qu.size()); ++i) {
 		        Arc arc = node_data[order_map[qu[i]]].first;
 		        Arc last = arc, pred = arc;
 		        arc = arc_lists[arc].next;
 		        while (arc != last) {
 		          if (arc_lists[arc].next == pred) {
 		            std::swap(arc_lists[arc].next, arc_lists[arc].prev);
+		          }
 		          pred = arc; arc = arc_lists[arc].next;
+		        }
+		      }
+		    }
 		    void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode,
 		                      OrderMap& order_map, NodeData& node_data,
 		                      TypeMap& type_map) {
 		      Node node = _graph.target(node_data[order_map[root]].first);
 		      while (node != ynode) {
 		        type_map[node] = HIGHY;
 		        node = _graph.target(node_data[order_map[node]].first);
+		      }
 		      while (node != wnode) {
 		        type_map[node] = LOWY;
 		        node = _graph.target(node_data[order_map[node]].first);
+		      }
 		      node = _graph.target(node_data[order_map[wnode]].first);
 		      while (node != xnode) {
 		        type_map[node] = LOWX;
 		        node = _graph.target(node_data[order_map[node]].first);
+		      }
 		      type_map[node] = LOWX;
 		      node = _graph.target(node_data[order_map[xnode]].first);
 		      while (node != root) {
 		        type_map[node] = HIGHX;
 		        node = _graph.target(node_data[order_map[node]].first);
+		      }
 		      type_map[wnode] = PERTINENT;
 		      type_map[root] = ROOT;
+		    }
 		    void findInternalPath(std::vector<Arc>& ipath,
 		                          Node wnode, Node root, TypeMap& type_map,
 		                          OrderMap& order_map, NodeData& node_data,
 		                          ArcLists& arc_lists) {
 		      std::vector<Arc> st;
 		      Node node = wnode;
 		      while (node != root) {
 		        Arc arc = arc_lists[node_data[order_map[node]].first].next;
 		        st.push_back(arc);
 		        node = _graph.target(arc);
+		      }
 		      while (true) {
 		        Arc arc = st.back();
 		        if (type_map[_graph.target(arc)] == LOWX ||
 		            type_map[_graph.target(arc)] == HIGHX) {
 		          break;
+		        }
 		        if (type_map[_graph.target(arc)] == 2) {
 		          type_map[_graph.target(arc)] = 3;
 		          arc = arc_lists[_graph.oppositeArc(arc)].next;
 		          st.push_back(arc);
 		        } else {
 		          st.pop_back();
 		          arc = arc_lists[arc].next;
 		          while (_graph.oppositeArc(arc) == st.back()) {
 		            arc = st.back();
 		            st.pop_back();
 		            arc = arc_lists[arc].next;
+		          }
 		          st.push_back(arc);
+		        }
+		      }
 		      for (int i = 0; i < int(st.size()); ++i) {
 		        if (type_map[_graph.target(st[i])] != LOWY &&
 		            type_map[_graph.target(st[i])] != HIGHY) {
 		          for (; i < int(st.size()); ++i) {
 		            ipath.push_back(st[i]);
+		          }
+		        }
+		      }
+		    }
 		    void setInternalFlags(std::vector<Arc>& ipath, TypeMap& type_map) {
 		      for (int i = 1; i < int(ipath.size()); ++i) {
 		        type_map[_graph.source(ipath[i])] = INTERNAL;
+		      }
+		    }
 		    void findPilePath(std::vector<Arc>& ppath,
 		                      Node root, TypeMap& type_map, OrderMap& order_map,
 		                      NodeData& node_data, ArcLists& arc_lists) {
 		      std::vector<Arc> st;
 		      st.push_back(_graph.oppositeArc(node_data[order_map[root]].first));
 		      st.push_back(node_data[order_map[root]].first);
 		      while (st.size() > 1) {
 		        Arc arc = st.back();
 		        if (type_map[_graph.target(arc)] == INTERNAL) {
 		          break;
+		        }
 		        if (type_map[_graph.target(arc)] == 3) {
 		          type_map[_graph.target(arc)] = 4;
 		          arc = arc_lists[_graph.oppositeArc(arc)].next;
 		          st.push_back(arc);
 		        } else {
 		          st.pop_back();
 		          arc = arc_lists[arc].next;
 		          while (!st.empty() && _graph.oppositeArc(arc) == st.back()) {
 		            arc = st.back();
 		            st.pop_back();
 		            arc = arc_lists[arc].next;
+		          }
 		          st.push_back(arc);
+		        }
+		      }
 		      for (int i = 1; i < int(st.size()); ++i) {
 		        ppath.push_back(st[i]);
+		      }
+		    }
 		    int markExternalPath(Node node, OrderMap& order_map,
 		                         ChildLists& child_lists, PredMap& pred_map,
 		                         AncestorMap& ancestor_map, LowMap& low_map) {
 		      int lp = lowPoint(node, order_map, child_lists,
 		                        ancestor_map, low_map);
 		      if (ancestor_map[node] != lp) {
 		        node = child_lists[node].first;
 		        _kuratowski[pred_map[node]] = true;
 		        while (ancestor_map[node] != lp) {
 		          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		            Node tnode = _graph.target(e);
 		            if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) {
 		              node = tnode;
 		              _kuratowski[e] = true;
 		              break;
+		            }
+		          }
+		        }
+		      }
 		      for (OutArcIt e(_graph, node); e != INVALID; ++e) {
 		        if (order_map[_graph.target(e)] == lp) {
 		          _kuratowski[e] = true;
 		          break;
+		        }
+		      }
 		      return lp;
+		    }
 		    void markPertinentPath(Node node, OrderMap& order_map,
 		                           NodeData& node_data, ArcLists& arc_lists,
 		                           EmbedArc& embed_arc, MergeRoots& merge_roots) {
 		      while (embed_arc[node] == INVALID) {
 		        int n = merge_roots[node].front();
 		        Arc arc = node_data[n].first;
 		        _kuratowski.set(arc, true);
 		        Node pred = node;
 		        node = _graph.target(arc);
 		        while (!pertinent(node, embed_arc, merge_roots)) {
 		          arc = node_data[order_map[node]].first;
 		          if (_graph.target(arc) == pred) {
 		            arc = arc_lists[arc].next;
+		          }
 		          _kuratowski.set(arc, true);
 		          pred = node;
 		          node = _graph.target(arc);
+		        }
+		      }
 		      _kuratowski.set(embed_arc[node], true);
+		    }
 		    void markPredPath(Node node, Node snode, PredMap& pred_map) {
 		      while (node != snode) {
 		        _kuratowski.set(pred_map[node], true);
 		        node = _graph.source(pred_map[node]);
+		      }
+		    }
 		    void markFacePath(Node ynode, Node xnode,
 		                      OrderMap& order_map, NodeData& node_data) {
 		      Arc arc = node_data[order_map[ynode]].first;
 		      Node node = _graph.target(arc);
 		      _kuratowski.set(arc, true);
 		      while (node != xnode) {
 		        arc = node_data[order_map[node]].first;
 		        _kuratowski.set(arc, true);
 		        node = _graph.target(arc);
+		      }
+		    }
 		    void markInternalPath(std::vector<Arc>& path) {
 		      for (int i = 0; i < int(path.size()); ++i) {
 		        _kuratowski.set(path[i], true);
+		      }
+		    }
 		    void markPilePath(std::vector<Arc>& path) {
 		      for (int i = 0; i < int(path.size()); ++i) {
 		        _kuratowski.set(path[i], true);
+		      }
+		    }
 		    void isolateKuratowski(Arc arc, NodeData& node_data,
 		                           ArcLists& arc_lists, FlipMap& flip_map,
 		                           OrderMap& order_map, OrderList& order_list,
 		                           PredMap& pred_map, ChildLists& child_lists,
 		                           AncestorMap& ancestor_map, LowMap& low_map,
 		                           EmbedArc& embed_arc, MergeRoots& merge_roots) {
 		      Node root = _graph.source(arc);
 		      Node enode = _graph.target(arc);
 		      int rorder = order_map[root];
 		      TypeMap type_map(_graph, 0);
 		      int rn = findComponentRoot(root, enode, child_lists,
 		                                 order_map, order_list);
 		      Node xnode = order_list[node_data[rn].next];
 		      Node ynode = order_list[node_data[rn].prev];
 		      // Minor-A
+		      {
 		        while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
 		          if (!merge_roots[xnode].empty()) {
 		            root = xnode;
 		            rn = merge_roots[xnode].front();
 		          } else {
 		            root = ynode;
 		            rn = merge_roots[ynode].front();
+		          }
 		          xnode = order_list[node_data[rn].next];
 		          ynode = order_list[node_data[rn].prev];
+		        }
 		        if (root != _graph.source(arc)) {
 		          orientComponent(root, rn, order_map, pred_map,
 		                          node_data, arc_lists, flip_map, type_map);
 		          markFacePath(root, root, order_map, node_data);
 		          int xlp = markExternalPath(xnode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          int ylp = markExternalPath(ynode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
 		          Node lwnode = findPertinent(ynode, order_map, node_data,
 		                                      embed_arc, merge_roots);
 		          markPertinentPath(lwnode, order_map, node_data, arc_lists,
 		                            embed_arc, merge_roots);
 		          return;
+		        }
+		      }
 		      orientComponent(root, rn, order_map, pred_map,
 		                      node_data, arc_lists, flip_map, type_map);
 		      Node wnode = findPertinent(ynode, order_map, node_data,
 		                                 embed_arc, merge_roots);
 		      setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map);
 		      //Minor-B
 		      if (!merge_roots[wnode].empty()) {
 		        int cn = merge_roots[wnode].back();
 		        Node rep = order_list[cn - order_list.size()];
 		        if (low_map[rep] < rorder) {
 		          markFacePath(root, root, order_map, node_data);
 		          int xlp = markExternalPath(xnode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          int ylp = markExternalPath(ynode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          Node lwnode, lznode;
 		          markCommonPath(wnode, rorder, lwnode, lznode, order_list,
 		                         order_map, node_data, arc_lists, embed_arc,
 		                         merge_roots, child_lists, ancestor_map, low_map);
 		          markPertinentPath(lwnode, order_map, node_data, arc_lists,
 		                            embed_arc, merge_roots);
 		          int zlp = markExternalPath(lznode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          int minlp = xlp < ylp ? xlp : ylp;
 		          if (zlp < minlp) minlp = zlp;
 		          int maxlp = xlp > ylp ? xlp : ylp;
 		          if (zlp > maxlp) maxlp = zlp;
 		          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
 		          return;
+		        }
+		      }
 		      Node pxnode, pynode;
 		      std::vector<Arc> ipath;
 		      findInternalPath(ipath, wnode, root, type_map, order_map,
 		                       node_data, arc_lists);
 		      setInternalFlags(ipath, type_map);
 		      pynode = _graph.source(ipath.front());
 		      pxnode = _graph.target(ipath.back());
 		      wnode = findPertinent(pynode, order_map, node_data,
 		                            embed_arc, merge_roots);
 		      // Minor-C
+		      {
 		        if (type_map[_graph.source(ipath.front())] == HIGHY) {
 		          if (type_map[_graph.target(ipath.back())] == HIGHX) {
 		            markFacePath(xnode, pxnode, order_map, node_data);
+		          }
 		          markFacePath(root, xnode, order_map, node_data);
 		          markPertinentPath(wnode, order_map, node_data, arc_lists,
 		                            embed_arc, merge_roots);
 		          markInternalPath(ipath);
 		          int xlp = markExternalPath(xnode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          int ylp = markExternalPath(ynode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
 		          return;
+		        }
 		        if (type_map[_graph.target(ipath.back())] == HIGHX) {
 		          markFacePath(ynode, root, order_map, node_data);
 		          markPertinentPath(wnode, order_map, node_data, arc_lists,
 		                            embed_arc, merge_roots);
 		          markInternalPath(ipath);
 		          int xlp = markExternalPath(xnode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          int ylp = markExternalPath(ynode, order_map, child_lists,
 		                                     pred_map, ancestor_map, low_map);
 		          markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
 		          return;
+		        }
+		      }
 		      std::vector<Arc> ppath;
 		      findPilePath(ppath, root, type_map, order_map, node_data, arc_lists);
 		      // Minor-D
 		      if (!ppath.empty()) {
 		        markFacePath(ynode, xnode, order_map, node_data);
 		        markPertinentPath(wnode, order_map, node_data, arc_lists,
 		                          embed_arc, merge_roots);
 		        markPilePath(ppath);
 		        markInternalPath(ipath);
 		        int xlp = markExternalPath(xnode, order_map, child_lists,
 		                                   pred_map, ancestor_map, low_map);
 		        int ylp = markExternalPath(ynode, order_map, child_lists,
 		                                   pred_map, ancestor_map, low_map);
 		        markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
 		        return;
+		      }
 		      // Minor-E*
+		      {
 		        if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
 		          Node znode = findExternal(pynode, rorder, order_map,
 		                                    child_lists, ancestor_map,
 		                                    low_map, node_data);
 		          if (type_map[znode] == LOWY) {
 		            markFacePath(root, xnode, order_map, node_data);
 		            markPertinentPath(wnode, order_map, node_data, arc_lists,
 		                              embed_arc, merge_roots);
 		            markInternalPath(ipath);
 		            int xlp = markExternalPath(xnode, order_map, child_lists,
 		                                       pred_map, ancestor_map, low_map);
 		            int zlp = markExternalPath(znode, order_map, child_lists,
 		                                       pred_map, ancestor_map, low_map);
 		            markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map);
 		          } else {
 		            markFacePath(ynode, root, order_map, node_data);
 		            markPertinentPath(wnode, order_map, node_data, arc_lists,
 		                              embed_arc, merge_roots);
 		            markInternalPath(ipath);
 		            int ylp = markExternalPath(ynode, order_map, child_lists,
 		                                       pred_map, ancestor_map, low_map);
 		            int zlp = markExternalPath(znode, order_map, child_lists,
 		                                       pred_map, ancestor_map, low_map);
 		            markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map);
+		          }
 		          return;
+		        }
 		        int xlp = markExternalPath(xnode, order_map, child_lists,
 		                                   pred_map, ancestor_map, low_map);
 		        int ylp = markExternalPath(ynode, order_map, child_lists,
 		                                   pred_map, ancestor_map, low_map);
 		        int wlp = markExternalPath(wnode, order_map, child_lists,
 		                                   pred_map, ancestor_map, low_map);
 		        if (wlp > xlp && wlp > ylp) {
 		          markFacePath(root, root, order_map, node_data);
 		          markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
 		          return;
+		        }
 		        markInternalPath(ipath);
 		        markPertinentPath(wnode, order_map, node_data, arc_lists,
 		                          embed_arc, merge_roots);
 		        if (xlp > ylp && xlp > wlp) {
 		          markFacePath(root, pynode, order_map, node_data);
 		          markFacePath(wnode, xnode, order_map, node_data);
 		          markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map);
 		          return;
+		        }
 		        if (ylp > xlp && ylp > wlp) {
 		          markFacePath(pxnode, root, order_map, node_data);
 		          markFacePath(ynode, wnode, order_map, node_data);
 		          markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map);
 		          return;
+		        }
 		        if (pynode != ynode) {
 		          markFacePath(pxnode, wnode, order_map, node_data);
 		          int minlp = xlp < ylp ? xlp : ylp;
 		          if (wlp < minlp) minlp = wlp;
 		          int maxlp = xlp > ylp ? xlp : ylp;
 		          if (wlp > maxlp) maxlp = wlp;
 		          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
 		          return;
+		        }
 		        if (pxnode != xnode) {
 		          markFacePath(wnode, pynode, order_map, node_data);
 		          int minlp = xlp < ylp ? xlp : ylp;
 		          if (wlp < minlp) minlp = wlp;
 		          int maxlp = xlp > ylp ? xlp : ylp;
 		          if (wlp > maxlp) maxlp = wlp;
 		          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
 		          return;
+		        }
 		        markFacePath(root, root, order_map, node_data);
 		        int minlp = xlp < ylp ? xlp : ylp;
 		        if (wlp < minlp) minlp = wlp;
 		        markPredPath(root, order_list[minlp], pred_map);
 		        return;
+		      }
+		    }
 		  };
 		  namespace _planarity_bits {
 		    template <typename Graph, typename EmbeddingMap>
 		    void makeConnected(Graph& graph, EmbeddingMap& embedding) {
 		      DfsVisitor<Graph> null_visitor;
 		      DfsVisit<Graph, DfsVisitor<Graph> > dfs(graph, null_visitor);
 		      dfs.init();
 		      typename Graph::Node u = INVALID;
 		      for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		        if (!dfs.reached(n)) {
 		          dfs.addSource(n);
 		          dfs.start();
 		          if (u == INVALID) {
 		            u = n;
 		          } else {
 		            typename Graph::Node v = n;
 		            typename Graph::Arc ue = typename Graph::OutArcIt(graph, u);
 		            typename Graph::Arc ve = typename Graph::OutArcIt(graph, v);
 		            typename Graph::Arc e = graph.direct(graph.addEdge(u, v), true);
 		            if (ue != INVALID) {
 		              embedding[e] = embedding[ue];
 		              embedding[ue] = e;
 		            } else {
 		              embedding[e] = e;
+		            }
 		            if (ve != INVALID) {
 		              embedding[graph.oppositeArc(e)] = embedding[ve];
 		              embedding[ve] = graph.oppositeArc(e);
 		            } else {
 		              embedding[graph.oppositeArc(e)] = graph.oppositeArc(e);
+		            }
+		          }
+		        }
+		      }
+		    }
 		    template <typename Graph, typename EmbeddingMap>
 		    void makeBiNodeConnected(Graph& graph, EmbeddingMap& embedding) {
 		      typename Graph::template ArcMap<bool> processed(graph);
 		      std::vector<typename Graph::Arc> arcs;
 		      for (typename Graph::ArcIt e(graph); e != INVALID; ++e) {
 		        arcs.push_back(e);
+		      }
 		      IterableBoolMap<Graph, typename Graph::Node> visited(graph, false);
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        typename Graph::Arc pp = arcs[i];
 		        if (processed[pp]) continue;
 		        typename Graph::Arc e = embedding[graph.oppositeArc(pp)];
 		        processed[e] = true;
 		        visited.set(graph.source(e), true);
 		        typename Graph::Arc p = e, l = e;
 		        e = embedding[graph.oppositeArc(e)];
 		        while (e != l) {
 		          processed[e] = true;
 		          if (visited[graph.source(e)]) {
 		            typename Graph::Arc n =
 		              graph.direct(graph.addEdge(graph.source(p),
 		                                           graph.target(e)), true);
 		            embedding[n] = p;
 		            embedding[graph.oppositeArc(pp)] = n;
 		            embedding[graph.oppositeArc(n)] =
 		              embedding[graph.oppositeArc(e)];
 		            embedding[graph.oppositeArc(e)] =
 		              graph.oppositeArc(n);
 		            p = n;
 		            e = embedding[graph.oppositeArc(n)];
 		          } else {
 		            visited.set(graph.source(e), true);
 		            pp = p;
 		            p = e;
 		            e = embedding[graph.oppositeArc(e)];
+		          }
+		        }
 		        visited.setAll(false);
+		      }
+		    }
 		    template <typename Graph, typename EmbeddingMap>
 		    void makeMaxPlanar(Graph& graph, EmbeddingMap& embedding) {
 		      typename Graph::template NodeMap<int> degree(graph);
 		      for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		        degree[n] = countIncEdges(graph, n);
+		      }
 		      typename Graph::template ArcMap<bool> processed(graph);
 		      IterableBoolMap<Graph, typename Graph::Node> visited(graph, false);
 		      std::vector<typename Graph::Arc> arcs;
 		      for (typename Graph::ArcIt e(graph); e != INVALID; ++e) {
 		        arcs.push_back(e);
+		      }
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        typename Graph::Arc e = arcs[i];
 		        if (processed[e]) continue;
 		        processed[e] = true;
 		        typename Graph::Arc mine = e;
 		        int mind = degree[graph.source(e)];
 		        int face_size = 1;
 		        typename Graph::Arc l = e;
 		        e = embedding[graph.oppositeArc(e)];
 		        while (l != e) {
 		          processed[e] = true;
 		          ++face_size;
 		          if (degree[graph.source(e)] < mind) {
 		            mine = e;
 		            mind = degree[graph.source(e)];
+		          }
 		          e = embedding[graph.oppositeArc(e)];
+		        }
 		        if (face_size < 4) {
 		          continue;
+		        }
 		        typename Graph::Node s = graph.source(mine);
 		        for (typename Graph::OutArcIt e(graph, s); e != INVALID; ++e) {
 		          visited.set(graph.target(e), true);
+		        }
 		        typename Graph::Arc oppe = INVALID;
 		        e = embedding[graph.oppositeArc(mine)];
 		        e = embedding[graph.oppositeArc(e)];
 		        while (graph.target(e) != s) {
 		          if (visited[graph.source(e)]) {
 		            oppe = e;
 		            break;
+		          }
 		          e = embedding[graph.oppositeArc(e)];
+		        }
 		        visited.setAll(false);
 		        if (oppe == INVALID) {
 		          e = embedding[graph.oppositeArc(mine)];
 		          typename Graph::Arc pn = mine, p = e;
 		          e = embedding[graph.oppositeArc(e)];
 		          while (graph.target(e) != s) {
 		            typename Graph::Arc n =
 		              graph.direct(graph.addEdge(s, graph.source(e)), true);
 		            embedding[n] = pn;
 		            embedding[graph.oppositeArc(n)] = e;
 		            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
 		            pn = n;
 		            p = e;
 		            e = embedding[graph.oppositeArc(e)];
+		          }
 		          embedding[graph.oppositeArc(e)] = pn;
 		        } else {
 		          mine = embedding[graph.oppositeArc(mine)];
 		          s = graph.source(mine);
 		          oppe = embedding[graph.oppositeArc(oppe)];
 		          typename Graph::Node t = graph.source(oppe);
 		          typename Graph::Arc ce = graph.direct(graph.addEdge(s, t), true);
 		          embedding[ce] = mine;
 		          embedding[graph.oppositeArc(ce)] = oppe;
 		          typename Graph::Arc pn = ce, p = oppe;
 		          e = embedding[graph.oppositeArc(oppe)];
 		          while (graph.target(e) != s) {
 		            typename Graph::Arc n =
 		              graph.direct(graph.addEdge(s, graph.source(e)), true);
 		            embedding[n] = pn;
 		            embedding[graph.oppositeArc(n)] = e;
 		            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
 		            pn = n;
 		            p = e;
 		            e = embedding[graph.oppositeArc(e)];
+		          }
 		          embedding[graph.oppositeArc(e)] = pn;
 		          pn = graph.oppositeArc(ce), p = mine;
 		          e = embedding[graph.oppositeArc(mine)];
 		          while (graph.target(e) != t) {
 		            typename Graph::Arc n =
 		              graph.direct(graph.addEdge(t, graph.source(e)), true);
 		            embedding[n] = pn;
 		            embedding[graph.oppositeArc(n)] = e;
 		            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
 		            pn = n;
 		            p = e;
 		            e = embedding[graph.oppositeArc(e)];
+		          }
 		          embedding[graph.oppositeArc(e)] = pn;
+		        }
+		      }
+		    }
+		  }
 		  /// \ingroup planar
 		  ///
 		  /// \brief Schnyder's planar drawing algorithm
 		  ///
 		  /// The planar drawing algorithm calculates positions for the nodes
 		  /// in the plane which coordinates satisfy that if the arcs are
 		  /// represented with straight lines then they will not intersect
 		  /// each other.
 		  ///
 		  /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
 		  /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square.
 		  /// The time complexity of the algorithm is O(n).
 		  template <typename Graph>
 		  class PlanarDrawing {
 		  public:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    /// \brief The point type for store coordinates
 		    typedef dim2::Point<int> Point;
 		    /// \brief The map type for store coordinates
 		    typedef typename Graph::template NodeMap<Point> PointMap;
 		    /// \brief Constructor
 		    ///
 		    /// Constructor
 		    /// \pre The graph should be simple, i.e. loop and parallel arc free.
 		    PlanarDrawing(const Graph& graph)
 		      : _graph(graph), _point_map(graph) {}
 		  private:
 		    template <typename AuxGraph, typename AuxEmbeddingMap>
 		    void drawing(const AuxGraph& graph,
 		                 const AuxEmbeddingMap& next,
 		                 PointMap& point_map) {
 		      TEMPLATE_GRAPH_TYPEDEFS(AuxGraph);
 		      typename AuxGraph::template ArcMap<Arc> prev(graph);
 		      for (NodeIt n(graph); n != INVALID; ++n) {
 		        Arc e = OutArcIt(graph, n);
 		        Arc p = e, l = e;
 		        e = next[e];
 		        while (e != l) {
 		          prev[e] = p;
 		          p = e;
 		          e = next[e];
+		        }
 		        prev[e] = p;
+		      }
 		      Node anode, bnode, cnode;
+		      {
 		        Arc e = ArcIt(graph);
 		        anode = graph.source(e);
 		        bnode = graph.target(e);
 		        cnode = graph.target(next[graph.oppositeArc(e)]);
+		      }
 		      IterableBoolMap<AuxGraph, Node> proper(graph, false);
 		      typename AuxGraph::template NodeMap<int> conn(graph, -1);
 		      conn[anode] = conn[bnode] = -2;
+		      {
 		        for (OutArcIt e(graph, anode); e != INVALID; ++e) {
 		          Node m = graph.target(e);
 		          if (conn[m] == -1) {
 		            conn[m] = 1;
+		          }
+		        }
 		        conn[cnode] = 2;
 		        for (OutArcIt e(graph, bnode); e != INVALID; ++e) {
 		          Node m = graph.target(e);
 		          if (conn[m] == -1) {
 		            conn[m] = 1;
 		          } else if (conn[m] != -2) {
 		            conn[m] += 1;
 		            Arc pe = graph.oppositeArc(e);
 		            if (conn[graph.target(next[pe])] == -2) {
 		              conn[m] -= 1;
+		            }
 		            if (conn[graph.target(prev[pe])] == -2) {
 		              conn[m] -= 1;
+		            }
 		            proper.set(m, conn[m] == 1);
+		          }
+		        }
+		      }
 		      typename AuxGraph::template ArcMap<int> angle(graph, -1);
 		      while (proper.trueNum() != 0) {
 		        Node n = typename IterableBoolMap<AuxGraph, Node>::TrueIt(proper);
 		        proper.set(n, false);
 		        conn[n] = -2;
 		        for (OutArcIt e(graph, n); e != INVALID; ++e) {
 		          Node m = graph.target(e);
 		          if (conn[m] == -1) {
 		            conn[m] = 1;
 		          } else if (conn[m] != -2) {
 		            conn[m] += 1;
 		            Arc pe = graph.oppositeArc(e);
 		            if (conn[graph.target(next[pe])] == -2) {
 		              conn[m] -= 1;
+		            }
 		            if (conn[graph.target(prev[pe])] == -2) {
 		              conn[m] -= 1;
+		            }
 		            proper.set(m, conn[m] == 1);
+		          }
+		        }
+		        {
 		          Arc e = OutArcIt(graph, n);
 		          Arc p = e, l = e;
 		          e = next[e];
 		          while (e != l) {
 		            if (conn[graph.target(e)] == -2 && conn[graph.target(p)] == -2) {
 		              Arc f = e;
 		              angle[f] = 0;
 		              f = next[graph.oppositeArc(f)];
 		              angle[f] = 1;
 		              f = next[graph.oppositeArc(f)];
 		              angle[f] = 2;
+		            }
 		            p = e;
 		            e = next[e];
+		          }
 		          if (conn[graph.target(e)] == -2 && conn[graph.target(p)] == -2) {
 		            Arc f = e;
 		            angle[f] = 0;
 		            f = next[graph.oppositeArc(f)];
 		            angle[f] = 1;
 		            f = next[graph.oppositeArc(f)];
 		            angle[f] = 2;
+		          }
+		        }
+		      }
 		      typename AuxGraph::template NodeMap<Node> apred(graph, INVALID);
 		      typename AuxGraph::template NodeMap<Node> bpred(graph, INVALID);
 		      typename AuxGraph::template NodeMap<Node> cpred(graph, INVALID);
 		      typename AuxGraph::template NodeMap<int> apredid(graph, -1);
 		      typename AuxGraph::template NodeMap<int> bpredid(graph, -1);
 		      typename AuxGraph::template NodeMap<int> cpredid(graph, -1);
 		      for (ArcIt e(graph); e != INVALID; ++e) {
 		        if (angle[e] == angle[next[e]]) {
 		          switch (angle[e]) {
 		          case 2:
 		            apred[graph.target(e)] = graph.source(e);
 		            apredid[graph.target(e)] = graph.id(graph.source(e));
 		            break;
 		          case 1:
 		            bpred[graph.target(e)] = graph.source(e);
 		            bpredid[graph.target(e)] = graph.id(graph.source(e));
 		            break;
 		          case 0:
 		            cpred[graph.target(e)] = graph.source(e);
 		            cpredid[graph.target(e)] = graph.id(graph.source(e));
 		            break;
+		          }
+		        }
+		      }
 		      cpred[anode] = INVALID;
 		      cpred[bnode] = INVALID;
 		      std::vector<Node> aorder, border, corder;
+		      {
 		        typename AuxGraph::template NodeMap<bool> processed(graph, false);
 		        std::vector<Node> st;
 		        for (NodeIt n(graph); n != INVALID; ++n) {
 		          if (!processed[n] && n != bnode && n != cnode) {
 		            st.push_back(n);
 		            processed[n] = true;
 		            Node m = apred[n];
 		            while (m != INVALID && !processed[m]) {
 		              st.push_back(m);

test/planarity_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <iostream>
 		#include <lemon/planarity.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/connectivity.h>
 		#include <lemon/dim2.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::dim2;
 		const int lgfn = 4;
 		const std::string lgf[lgfn] = {
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "@edges\n"
 		  "     label\n"
 		  "0 1  0\n"
 		  "0 2  0\n"
 		  "0 3  0\n"
 		  "0 4  0\n"
 		  "1 2  0\n"
 		  "1 3  0\n"
 		  "1 4  0\n"
 		  "2 3  0\n"
 		  "2 4  0\n"
 		  "3 4  0\n",
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "@edges\n"
 		  "     label\n"
 		  "0 1  0\n"
 		  "0 2  0\n"
 		  "0 3  0\n"
 		  "0 4  0\n"
 		  "1 2  0\n"
 		  "1 3  0\n"
 		  "2 3  0\n"
 		  "2 4  0\n"
 		  "3 4  0\n",
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "@edges\n"
 		  "     label\n"
 		  "0 3  0\n"
 		  "0 4  0\n"
 		  "0 5  0\n"
 		  "1 3  0\n"
 		  "1 4  0\n"
 		  "1 5  0\n"
 		  "2 3  0\n"
 		  "2 4  0\n"
 		  "2 5  0\n",
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "@edges\n"
 		  "     label\n"
 		  "0 3  0\n"
 		  "0 4  0\n"
 		  "0 5  0\n"
 		  "1 3  0\n"
 		  "1 4  0\n"
 		  "1 5  0\n"
 		  "2 3  0\n"
 		  "2 5  0\n"
 		};
 		typedef SmartGraph Graph;
 		GRAPH_TYPEDEFS(Graph);
 		typedef PlanarEmbedding<SmartGraph> PE;
 		typedef PlanarDrawing<SmartGraph> PD;
 		typedef PlanarColoring<SmartGraph> PC;
 		void checkEmbedding(const Graph& graph, PE& pe) {
 		  int face_num = 0;
 		  Graph::ArcMap<int> face(graph, -1);
 		  for (ArcIt a(graph); a != INVALID; ++a) {
 		    if (face[a] == -1) {
 		      Arc b = a;
 		      while (face[b] == -1) {
 		        face[b] = face_num;
 		        b = pe.next(graph.oppositeArc(b));
+		      }
 		      check(face[b] == face_num, "Wrong face");
 		      ++face_num;
+		    }
+		  }
 		  check(face_num + countNodes(graph) - countConnectedComponents(graph) ==
 		        countEdges(graph) + 1, "Euler test does not passed");
+		}
 		void checkKuratowski(const Graph& graph, PE& pe) {
 		  std::map<int, int> degs;
 		  for (NodeIt n(graph); n != INVALID; ++n) {
 		    int deg = 0;
 		    for (IncEdgeIt e(graph, n); e != INVALID; ++e) {
 		      if (pe.kuratowski(e)) {
 		        ++deg;
+		      }
+		    }
 		    ++degs[deg];
+		  }
 		  for (std::map<int, int>::iterator it = degs.begin(); it != degs.end(); ++it) {
 		    check(it->first == 0 || it->first == 2 ||
 		          (it->first == 3 && it->second == 6) ||
 		          (it->first == 4 && it->second == 5),
 		          "Wrong degree in Kuratowski graph");
+		  }
 		  // Not full test
 		  check((degs[3] == 0) != (degs[4] == 0), "Wrong Kuratowski graph");
+		}
 		bool intersect(Point<int> e1, Point<int> e2, Point<int> f1, Point<int> f2) {
 		  int l, r;
 		  if (std::min(e1.x, e2.x) > std::max(f1.x, f2.x)) return false;
 		  if (std::max(e1.x, e2.x) < std::min(f1.x, f2.x)) return false;
 		  if (std::min(e1.y, e2.y) > std::max(f1.y, f2.y)) return false;
 		  if (std::max(e1.y, e2.y) < std::min(f1.y, f2.y)) return false;
 		  l = (e2.x - e1.x) * (f1.y - e1.y) - (e2.y - e1.y) * (f1.x - e1.x);
 		  r = (e2.x - e1.x) * (f2.y - e1.y) - (e2.y - e1.y) * (f2.x - e1.x);
 		  if (!((l >= 0 && r <= 0) || (l <= 0 && r >= 0))) return false;
 		  l = (f2.x - f1.x) * (e1.y - f1.y) - (f2.y - f1.y) * (e1.x - f1.x);
 		  r = (f2.x - f1.x) * (e2.y - f1.y) - (f2.y - f1.y) * (e2.x - f1.x);
 		  if (!((l >= 0 && r <= 0) || (l <= 0 && r >= 0))) return false;
 		  return true;
+		}
 		bool collinear(Point<int> p, Point<int> q, Point<int> r) {
 		  int v;
 		  v = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
 		  if (v != 0) return false;
 		  v = (q.x - p.x) * (r.x - p.x) + (q.y - p.y) * (r.y - p.y);
 		  if (v < 0) return false;
 		  return true;
+		}
 		void checkDrawing(const Graph& graph, PD& pd) {
 		  for (Graph::NodeIt n(graph); n != INVALID; ++n) {
 		    Graph::NodeIt m(n);
 		    for (++m; m != INVALID; ++m) {
 		      check(pd[m] != pd[n], "Two nodes with identical coordinates");
+		    }
+		  }
 		  for (Graph::EdgeIt e(graph); e != INVALID; ++e) {
 		    for (Graph::EdgeIt f(e); f != e; ++f) {
 		      Point<int> e1 = pd[graph.u(e)];
 		      Point<int> e2 = pd[graph.v(e)];
 		      Point<int> f1 = pd[graph.u(f)];
 		      Point<int> f2 = pd[graph.v(f)];
 		      if (graph.u(e) == graph.u(f)) {
 		        check(!collinear(e1, e2, f2), "Wrong drawing");
 		      } else if (graph.u(e) == graph.v(f)) {
 		        check(!collinear(e1, e2, f1), "Wrong drawing");
 		      } else if (graph.v(e) == graph.u(f)) {
 		        check(!collinear(e2, e1, f2), "Wrong drawing");
 		      } else if (graph.v(e) == graph.v(f)) {
 		        check(!collinear(e2, e1, f1), "Wrong drawing");
 		      } else {
 		        check(!intersect(e1, e2, f1, f2), "Wrong drawing");
+		      }
+		    }
+		  }
+		}
 		void checkColoring(const Graph& graph, PC& pc, int num) {
 		  for (NodeIt n(graph); n != INVALID; ++n) {
 		    check(pc.colorIndex(n) >= 0 && pc.colorIndex(n) < num,
 		          "Wrong coloring");
+		  }
 		  for (EdgeIt e(graph); e != INVALID; ++e) {
 		    check(pc.colorIndex(graph.u(e)) != pc.colorIndex(graph.v(e)),
 		          "Wrong coloring");
+		  }
+		}
 		int main() {
 		  for (int i = 0; i < lgfn; ++i) {
 		    std::istringstream lgfs(lgf[i]);
 		    SmartGraph graph;
 		    graphReader(graph, lgfs).run();
 		    check(simpleGraph(graph), "Test graphs must be simple");
 		    PE pe(graph);
-		    if (pe.run()) {
+		    bool planar = pe.run();
 		    check(checkPlanarity(graph) == planar, "Planarity checking failed");
 		    if (planar) {
 		      checkEmbedding(graph, pe);
 		      PlanarDrawing<Graph> pd(graph);
-		      pd.run(pe.embedding());
+		      pd.run(pe.embeddingMap());
 		      checkDrawing(graph, pd);
 		      PlanarColoring<Graph> pc(graph);
-		      pc.runFiveColoring(pe.embedding());
+		      pc.runFiveColoring(pe.embeddingMap());
 		      checkColoring(graph, pc, 5);
 		    } else {
 		      checkKuratowski(graph, pe);
+		    }
+		  }
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account