deba@797: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@797:  *
deba@797:  * This file is a part of LEMON, a generic C++ optimization library.
deba@797:  *
alpar@1092:  * Copyright (C) 2003-2013
deba@797:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@797:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@797:  *
deba@797:  * Permission to use, modify and distribute this software is granted
deba@797:  * provided that this copyright notice appears in all copies. For
deba@797:  * precise terms see the accompanying LICENSE file.
deba@797:  *
deba@797:  * This software is provided "AS IS" with no warranty of any kind,
deba@797:  * express or implied, and with no claim as to its suitability for any
deba@797:  * purpose.
deba@797:  *
deba@797:  */
deba@797: 
deba@797: #ifndef LEMON_PLANARITY_H
deba@797: #define LEMON_PLANARITY_H
deba@797: 
deba@797: /// \ingroup planar
deba@797: /// \file
deba@797: /// \brief Planarity checking, embedding, drawing and coloring
deba@797: 
deba@797: #include <vector>
deba@797: #include <list>
deba@797: 
deba@797: #include <lemon/dfs.h>
deba@797: #include <lemon/bfs.h>
deba@797: #include <lemon/radix_sort.h>
deba@797: #include <lemon/maps.h>
deba@797: #include <lemon/path.h>
deba@797: #include <lemon/bucket_heap.h>
deba@797: #include <lemon/adaptors.h>
deba@797: #include <lemon/edge_set.h>
deba@797: #include <lemon/color.h>
deba@797: #include <lemon/dim2.h>
deba@797: 
deba@797: namespace lemon {
deba@797: 
deba@797:   namespace _planarity_bits {
deba@797: 
deba@797:     template <typename Graph>
deba@797:     struct PlanarityVisitor : DfsVisitor<Graph> {
deba@797: 
deba@797:       TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@797: 
deba@797:       typedef typename Graph::template NodeMap<Arc> PredMap;
deba@797: 
deba@797:       typedef typename Graph::template EdgeMap<bool> TreeMap;
deba@797: 
deba@797:       typedef typename Graph::template NodeMap<int> OrderMap;
deba@797:       typedef std::vector<Node> OrderList;
deba@797: 
deba@797:       typedef typename Graph::template NodeMap<int> LowMap;
deba@797:       typedef typename Graph::template NodeMap<int> AncestorMap;
deba@797: 
deba@797:       PlanarityVisitor(const Graph& graph,
deba@797:                        PredMap& pred_map, TreeMap& tree_map,
deba@797:                        OrderMap& order_map, OrderList& order_list,
deba@797:                        AncestorMap& ancestor_map, LowMap& low_map)
deba@797:         : _graph(graph), _pred_map(pred_map), _tree_map(tree_map),
deba@797:           _order_map(order_map), _order_list(order_list),
deba@797:           _ancestor_map(ancestor_map), _low_map(low_map) {}
deba@797: 
deba@797:       void reach(const Node& node) {
deba@797:         _order_map[node] = _order_list.size();
deba@797:         _low_map[node] = _order_list.size();
deba@797:         _ancestor_map[node] = _order_list.size();
deba@797:         _order_list.push_back(node);
deba@797:       }
deba@797: 
deba@797:       void discover(const Arc& arc) {
deba@797:         Node target = _graph.target(arc);
deba@797: 
deba@797:         _tree_map[arc] = true;
deba@797:         _pred_map[target] = arc;
deba@797:       }
deba@797: 
deba@797:       void examine(const Arc& arc) {
deba@797:         Node source = _graph.source(arc);
deba@797:         Node target = _graph.target(arc);
deba@797: 
deba@797:         if (_order_map[target] < _order_map[source] && !_tree_map[arc]) {
deba@797:           if (_low_map[source] > _order_map[target]) {
deba@797:             _low_map[source] = _order_map[target];
deba@797:           }
deba@797:           if (_ancestor_map[source] > _order_map[target]) {
deba@797:             _ancestor_map[source] = _order_map[target];
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       void backtrack(const Arc& arc) {
deba@797:         Node source = _graph.source(arc);
deba@797:         Node target = _graph.target(arc);
deba@797: 
deba@797:         if (_low_map[source] > _low_map[target]) {
deba@797:           _low_map[source] = _low_map[target];
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       const Graph& _graph;
deba@797:       PredMap& _pred_map;
deba@797:       TreeMap& _tree_map;
deba@797:       OrderMap& _order_map;
deba@797:       OrderList& _order_list;
deba@797:       AncestorMap& _ancestor_map;
deba@797:       LowMap& _low_map;
deba@797:     };
deba@797: 
deba@797:     template <typename Graph, bool embedding = true>
deba@797:     struct NodeDataNode {
deba@797:       int prev, next;
deba@797:       int visited;
deba@797:       typename Graph::Arc first;
deba@797:       bool inverted;
deba@797:     };
deba@797: 
deba@797:     template <typename Graph>
deba@797:     struct NodeDataNode<Graph, false> {
deba@797:       int prev, next;
deba@797:       int visited;
deba@797:     };
deba@797: 
deba@797:     template <typename Graph>
deba@797:     struct ChildListNode {
deba@797:       typedef typename Graph::Node Node;
deba@797:       Node first;
deba@797:       Node prev, next;
deba@797:     };
deba@797: 
deba@797:     template <typename Graph>
deba@797:     struct ArcListNode {
deba@797:       typename Graph::Arc prev, next;
deba@797:     };
deba@797: 
deba@798:     template <typename Graph>
deba@798:     class PlanarityChecking {
deba@798:     private:
alpar@877: 
deba@798:       TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@798: 
deba@798:       const Graph& _graph;
deba@798: 
deba@798:     private:
alpar@877: 
deba@798:       typedef typename Graph::template NodeMap<Arc> PredMap;
alpar@877: 
deba@798:       typedef typename Graph::template EdgeMap<bool> TreeMap;
alpar@877: 
deba@798:       typedef typename Graph::template NodeMap<int> OrderMap;
deba@798:       typedef std::vector<Node> OrderList;
deba@798: 
deba@798:       typedef typename Graph::template NodeMap<int> LowMap;
deba@798:       typedef typename Graph::template NodeMap<int> AncestorMap;
deba@798: 
deba@798:       typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
deba@798:       typedef std::vector<NodeDataNode> NodeData;
deba@798: 
deba@798:       typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
deba@798:       typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
deba@798: 
deba@798:       typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
deba@798: 
deba@798:       typedef typename Graph::template NodeMap<bool> EmbedArc;
deba@798: 
deba@798:     public:
deba@798: 
deba@798:       PlanarityChecking(const Graph& graph) : _graph(graph) {}
deba@798: 
deba@798:       bool run() {
deba@798:         typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
deba@798: 
deba@798:         PredMap pred_map(_graph, INVALID);
deba@798:         TreeMap tree_map(_graph, false);
deba@798: 
deba@798:         OrderMap order_map(_graph, -1);
deba@798:         OrderList order_list;
deba@798: 
deba@798:         AncestorMap ancestor_map(_graph, -1);
deba@798:         LowMap low_map(_graph, -1);
deba@798: 
deba@798:         Visitor visitor(_graph, pred_map, tree_map,
deba@798:                         order_map, order_list, ancestor_map, low_map);
deba@798:         DfsVisit<Graph, Visitor> visit(_graph, visitor);
deba@798:         visit.run();
deba@798: 
deba@798:         ChildLists child_lists(_graph);
deba@798:         createChildLists(tree_map, order_map, low_map, child_lists);
deba@798: 
deba@798:         NodeData node_data(2 * order_list.size());
deba@798: 
deba@798:         EmbedArc embed_arc(_graph, false);
deba@798: 
deba@798:         MergeRoots merge_roots(_graph);
deba@798: 
deba@798:         for (int i = order_list.size() - 1; i >= 0; --i) {
deba@798: 
deba@798:           Node node = order_list[i];
deba@798: 
deba@798:           Node source = node;
deba@798:           for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@798:             Node target = _graph.target(e);
deba@798: 
deba@798:             if (order_map[source] < order_map[target] && tree_map[e]) {
deba@798:               initFace(target, node_data, order_map, order_list);
deba@798:             }
deba@798:           }
deba@798: 
deba@798:           for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@798:             Node target = _graph.target(e);
deba@798: 
deba@798:             if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@798:               embed_arc[target] = true;
deba@798:               walkUp(target, source, i, pred_map, low_map,
deba@798:                      order_map, order_list, node_data, merge_roots);
deba@798:             }
deba@798:           }
deba@798: 
deba@798:           for (typename MergeRoots::Value::iterator it =
alpar@877:                  merge_roots[node].begin();
deba@798:                it != merge_roots[node].end(); ++it) {
deba@798:             int rn = *it;
deba@798:             walkDown(rn, i, node_data, order_list, child_lists,
deba@798:                      ancestor_map, low_map, embed_arc, merge_roots);
deba@798:           }
deba@798:           merge_roots[node].clear();
deba@798: 
deba@798:           for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@798:             Node target = _graph.target(e);
deba@798: 
deba@798:             if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@798:               if (embed_arc[target]) {
deba@798:                 return false;
deba@798:               }
deba@798:             }
deba@798:           }
deba@798:         }
deba@798: 
deba@798:         return true;
deba@798:       }
deba@798: 
deba@798:     private:
deba@798: 
deba@798:       void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
deba@798:                             const LowMap& low_map, ChildLists& child_lists) {
deba@798: 
deba@798:         for (NodeIt n(_graph); n != INVALID; ++n) {
deba@798:           Node source = n;
deba@798: 
deba@798:           std::vector<Node> targets;
deba@798:           for (OutArcIt e(_graph, n); e != INVALID; ++e) {
deba@798:             Node target = _graph.target(e);
deba@798: 
deba@798:             if (order_map[source] < order_map[target] && tree_map[e]) {
deba@798:               targets.push_back(target);
deba@798:             }
deba@798:           }
deba@798: 
deba@798:           if (targets.size() == 0) {
deba@798:             child_lists[source].first = INVALID;
deba@798:           } else if (targets.size() == 1) {
deba@798:             child_lists[source].first = targets[0];
deba@798:             child_lists[targets[0]].prev = INVALID;
deba@798:             child_lists[targets[0]].next = INVALID;
deba@798:           } else {
deba@798:             radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
deba@798:             for (int i = 1; i < int(targets.size()); ++i) {
deba@798:               child_lists[targets[i]].prev = targets[i - 1];
deba@798:               child_lists[targets[i - 1]].next = targets[i];
deba@798:             }
deba@798:             child_lists[targets.back()].next = INVALID;
deba@798:             child_lists[targets.front()].prev = INVALID;
deba@798:             child_lists[source].first = targets.front();
deba@798:           }
deba@798:         }
deba@798:       }
deba@798: 
deba@798:       void walkUp(const Node& node, Node root, int rorder,
deba@798:                   const PredMap& pred_map, const LowMap& low_map,
deba@798:                   const OrderMap& order_map, const OrderList& order_list,
deba@798:                   NodeData& node_data, MergeRoots& merge_roots) {
deba@798: 
deba@798:         int na, nb;
deba@798:         bool da, db;
deba@798: 
deba@798:         na = nb = order_map[node];
deba@798:         da = true; db = false;
deba@798: 
deba@798:         while (true) {
deba@798: 
deba@798:           if (node_data[na].visited == rorder) break;
deba@798:           if (node_data[nb].visited == rorder) break;
deba@798: 
deba@798:           node_data[na].visited = rorder;
deba@798:           node_data[nb].visited = rorder;
deba@798: 
deba@798:           int rn = -1;
deba@798: 
deba@798:           if (na >= int(order_list.size())) {
deba@798:             rn = na;
deba@798:           } else if (nb >= int(order_list.size())) {
deba@798:             rn = nb;
deba@798:           }
deba@798: 
deba@798:           if (rn == -1) {
deba@798:             int nn;
deba@798: 
deba@798:             nn = da ? node_data[na].prev : node_data[na].next;
deba@798:             da = node_data[nn].prev != na;
deba@798:             na = nn;
deba@798: 
deba@798:             nn = db ? node_data[nb].prev : node_data[nb].next;
deba@798:             db = node_data[nn].prev != nb;
deba@798:             nb = nn;
deba@798: 
deba@798:           } else {
deba@798: 
deba@798:             Node rep = order_list[rn - order_list.size()];
deba@798:             Node parent = _graph.source(pred_map[rep]);
deba@798: 
deba@798:             if (low_map[rep] < rorder) {
deba@798:               merge_roots[parent].push_back(rn);
deba@798:             } else {
deba@798:               merge_roots[parent].push_front(rn);
deba@798:             }
deba@798: 
deba@798:             if (parent != root) {
deba@798:               na = nb = order_map[parent];
deba@798:               da = true; db = false;
deba@798:             } else {
deba@798:               break;
deba@798:             }
deba@798:           }
deba@798:         }
deba@798:       }
deba@798: 
deba@798:       void walkDown(int rn, int rorder, NodeData& node_data,
deba@798:                     OrderList& order_list, ChildLists& child_lists,
deba@798:                     AncestorMap& ancestor_map, LowMap& low_map,
deba@798:                     EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@798: 
deba@798:         std::vector<std::pair<int, bool> > merge_stack;
deba@798: 
deba@798:         for (int di = 0; di < 2; ++di) {
deba@798:           bool rd = di == 0;
deba@798:           int pn = rn;
deba@798:           int n = rd ? node_data[rn].next : node_data[rn].prev;
deba@798: 
deba@798:           while (n != rn) {
deba@798: 
deba@798:             Node node = order_list[n];
deba@798: 
deba@798:             if (embed_arc[node]) {
deba@798: 
deba@798:               // Merging components on the critical path
deba@798:               while (!merge_stack.empty()) {
deba@798: 
deba@798:                 // Component root
deba@798:                 int cn = merge_stack.back().first;
deba@798:                 bool cd = merge_stack.back().second;
deba@798:                 merge_stack.pop_back();
deba@798: 
deba@798:                 // Parent of component
deba@798:                 int dn = merge_stack.back().first;
deba@798:                 bool dd = merge_stack.back().second;
deba@798:                 merge_stack.pop_back();
deba@798: 
deba@798:                 Node parent = order_list[dn];
deba@798: 
deba@798:                 // Erasing from merge_roots
deba@798:                 merge_roots[parent].pop_front();
deba@798: 
deba@798:                 Node child = order_list[cn - order_list.size()];
deba@798: 
deba@798:                 // Erasing from child_lists
deba@798:                 if (child_lists[child].prev != INVALID) {
deba@798:                   child_lists[child_lists[child].prev].next =
deba@798:                     child_lists[child].next;
deba@798:                 } else {
deba@798:                   child_lists[parent].first = child_lists[child].next;
deba@798:                 }
deba@798: 
deba@798:                 if (child_lists[child].next != INVALID) {
deba@798:                   child_lists[child_lists[child].next].prev =
deba@798:                     child_lists[child].prev;
deba@798:                 }
deba@798: 
deba@798:                 // Merging external faces
deba@798:                 {
deba@798:                   int en = cn;
deba@798:                   cn = cd ? node_data[cn].prev : node_data[cn].next;
deba@798:                   cd = node_data[cn].next == en;
deba@798: 
deba@798:                 }
deba@798: 
deba@798:                 if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
deba@798:                 if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
deba@798: 
deba@798:               }
deba@798: 
deba@798:               bool d = pn == node_data[n].prev;
deba@798: 
deba@798:               if (node_data[n].prev == node_data[n].next &&
deba@798:                   node_data[n].inverted) {
deba@798:                 d = !d;
deba@798:               }
deba@798: 
deba@798:               // Embedding arc into external face
deba@798:               if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
deba@798:               if (d) node_data[n].prev = rn; else node_data[n].next = rn;
deba@798:               pn = rn;
deba@798: 
deba@798:               embed_arc[order_list[n]] = false;
deba@798:             }
deba@798: 
deba@798:             if (!merge_roots[node].empty()) {
deba@798: 
deba@798:               bool d = pn == node_data[n].prev;
deba@798: 
deba@798:               merge_stack.push_back(std::make_pair(n, d));
deba@798: 
deba@798:               int rn = merge_roots[node].front();
deba@798: 
deba@798:               int xn = node_data[rn].next;
deba@798:               Node xnode = order_list[xn];
deba@798: 
deba@798:               int yn = node_data[rn].prev;
deba@798:               Node ynode = order_list[yn];
deba@798: 
deba@798:               bool rd;
alpar@877:               if (!external(xnode, rorder, child_lists,
deba@798:                             ancestor_map, low_map)) {
deba@798:                 rd = true;
deba@798:               } else if (!external(ynode, rorder, child_lists,
deba@798:                                    ancestor_map, low_map)) {
deba@798:                 rd = false;
deba@798:               } else if (pertinent(xnode, embed_arc, merge_roots)) {
deba@798:                 rd = true;
deba@798:               } else {
deba@798:                 rd = false;
deba@798:               }
deba@798: 
deba@798:               merge_stack.push_back(std::make_pair(rn, rd));
deba@798: 
deba@798:               pn = rn;
deba@798:               n = rd ? xn : yn;
deba@798: 
deba@798:             } else if (!external(node, rorder, child_lists,
deba@798:                                  ancestor_map, low_map)) {
deba@798:               int nn = (node_data[n].next != pn ?
deba@798:                         node_data[n].next : node_data[n].prev);
deba@798: 
deba@798:               bool nd = n == node_data[nn].prev;
deba@798: 
deba@798:               if (nd) node_data[nn].prev = pn;
deba@798:               else node_data[nn].next = pn;
deba@798: 
deba@798:               if (n == node_data[pn].prev) node_data[pn].prev = nn;
deba@798:               else node_data[pn].next = nn;
deba@798: 
deba@798:               node_data[nn].inverted =
deba@798:                 (node_data[nn].prev == node_data[nn].next && nd != rd);
deba@798: 
deba@798:               n = nn;
deba@798:             }
deba@798:             else break;
deba@798: 
deba@798:           }
deba@798: 
deba@798:           if (!merge_stack.empty() || n == rn) {
deba@798:             break;
deba@798:           }
deba@798:         }
deba@798:       }
deba@798: 
deba@798:       void initFace(const Node& node, NodeData& node_data,
deba@798:                     const OrderMap& order_map, const OrderList& order_list) {
deba@798:         int n = order_map[node];
deba@798:         int rn = n + order_list.size();
deba@798: 
deba@798:         node_data[n].next = node_data[n].prev = rn;
deba@798:         node_data[rn].next = node_data[rn].prev = n;
deba@798: 
deba@798:         node_data[n].visited = order_list.size();
deba@798:         node_data[rn].visited = order_list.size();
deba@798: 
deba@798:       }
deba@798: 
deba@798:       bool external(const Node& node, int rorder,
deba@798:                     ChildLists& child_lists, AncestorMap& ancestor_map,
deba@798:                     LowMap& low_map) {
deba@798:         Node child = child_lists[node].first;
deba@798: 
deba@798:         if (child != INVALID) {
deba@798:           if (low_map[child] < rorder) return true;
deba@798:         }
deba@798: 
deba@798:         if (ancestor_map[node] < rorder) return true;
deba@798: 
deba@798:         return false;
deba@798:       }
deba@798: 
deba@798:       bool pertinent(const Node& node, const EmbedArc& embed_arc,
deba@798:                      const MergeRoots& merge_roots) {
deba@798:         return !merge_roots[node].empty() || embed_arc[node];
deba@798:       }
deba@798: 
deba@798:     };
deba@798: 
deba@797:   }
deba@797: 
deba@797:   /// \ingroup planar
deba@797:   ///
deba@797:   /// \brief Planarity checking of an undirected simple graph
deba@797:   ///
deba@798:   /// This function implements the Boyer-Myrvold algorithm for
kpeter@828:   /// planarity checking of an undirected simple graph. It is a simplified
deba@797:   /// version of the PlanarEmbedding algorithm class because neither
kpeter@828:   /// the embedding nor the Kuratowski subdivisons are computed.
deba@798:   template <typename GR>
deba@798:   bool checkPlanarity(const GR& graph) {
deba@798:     _planarity_bits::PlanarityChecking<GR> pc(graph);
deba@798:     return pc.run();
deba@798:   }
deba@797: 
deba@797:   /// \ingroup planar
deba@797:   ///
deba@797:   /// \brief Planar embedding of an undirected simple graph
deba@797:   ///
deba@797:   /// This class implements the Boyer-Myrvold algorithm for planar
kpeter@828:   /// embedding of an undirected simple graph. The planar embedding is an
deba@797:   /// ordering of the outgoing edges of the nodes, which is a possible
deba@797:   /// configuration to draw the graph in the plane. If there is not
kpeter@828:   /// such ordering then the graph contains a K<sub>5</sub> (full graph
kpeter@828:   /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
kpeter@828:   /// 3 Red and 3 Blue nodes) subdivision.
deba@797:   ///
deba@797:   /// The current implementation calculates either an embedding or a
kpeter@828:   /// Kuratowski subdivision. The running time of the algorithm is O(n).
kpeter@828:   ///
kpeter@828:   /// \see PlanarDrawing, checkPlanarity()
deba@797:   template <typename Graph>
deba@797:   class PlanarEmbedding {
deba@797:   private:
deba@797: 
deba@797:     TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@797: 
deba@797:     const Graph& _graph;
deba@797:     typename Graph::template ArcMap<Arc> _embedding;
deba@797: 
deba@797:     typename Graph::template EdgeMap<bool> _kuratowski;
deba@797: 
deba@797:   private:
deba@797: 
deba@797:     typedef typename Graph::template NodeMap<Arc> PredMap;
deba@797: 
deba@797:     typedef typename Graph::template EdgeMap<bool> TreeMap;
deba@797: 
deba@797:     typedef typename Graph::template NodeMap<int> OrderMap;
deba@797:     typedef std::vector<Node> OrderList;
deba@797: 
deba@797:     typedef typename Graph::template NodeMap<int> LowMap;
deba@797:     typedef typename Graph::template NodeMap<int> AncestorMap;
deba@797: 
deba@797:     typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
deba@797:     typedef std::vector<NodeDataNode> NodeData;
deba@797: 
deba@797:     typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
deba@797:     typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
deba@797: 
deba@797:     typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
deba@797: 
deba@797:     typedef typename Graph::template NodeMap<Arc> EmbedArc;
deba@797: 
deba@797:     typedef _planarity_bits::ArcListNode<Graph> ArcListNode;
deba@797:     typedef typename Graph::template ArcMap<ArcListNode> ArcLists;
deba@797: 
deba@797:     typedef typename Graph::template NodeMap<bool> FlipMap;
deba@797: 
deba@797:     typedef typename Graph::template NodeMap<int> TypeMap;
deba@797: 
deba@797:     enum IsolatorNodeType {
deba@797:       HIGHX = 6, LOWX = 7,
deba@797:       HIGHY = 8, LOWY = 9,
deba@797:       ROOT = 10, PERTINENT = 11,
deba@797:       INTERNAL = 12
deba@797:     };
deba@797: 
deba@797:   public:
deba@797: 
kpeter@828:     /// \brief The map type for storing the embedding
kpeter@828:     ///
kpeter@828:     /// The map type for storing the embedding.
kpeter@828:     /// \see embeddingMap()
deba@797:     typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
deba@797: 
deba@797:     /// \brief Constructor
deba@797:     ///
kpeter@828:     /// Constructor.
kpeter@828:     /// \pre The graph must be simple, i.e. it should not
kpeter@828:     /// contain parallel or loop arcs.
deba@797:     PlanarEmbedding(const Graph& graph)
deba@797:       : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
deba@797: 
kpeter@828:     /// \brief Run the algorithm.
deba@797:     ///
kpeter@828:     /// This function runs the algorithm.
kpeter@828:     /// \param kuratowski If this parameter is set to \c false, then the
deba@797:     /// algorithm does not compute a Kuratowski subdivision.
kpeter@828:     /// \return \c true if the graph is planar.
deba@797:     bool run(bool kuratowski = true) {
deba@797:       typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
deba@797: 
deba@797:       PredMap pred_map(_graph, INVALID);
deba@797:       TreeMap tree_map(_graph, false);
deba@797: 
deba@797:       OrderMap order_map(_graph, -1);
deba@797:       OrderList order_list;
deba@797: 
deba@797:       AncestorMap ancestor_map(_graph, -1);
deba@797:       LowMap low_map(_graph, -1);
deba@797: 
deba@797:       Visitor visitor(_graph, pred_map, tree_map,
deba@797:                       order_map, order_list, ancestor_map, low_map);
deba@797:       DfsVisit<Graph, Visitor> visit(_graph, visitor);
deba@797:       visit.run();
deba@797: 
deba@797:       ChildLists child_lists(_graph);
deba@797:       createChildLists(tree_map, order_map, low_map, child_lists);
deba@797: 
deba@797:       NodeData node_data(2 * order_list.size());
deba@797: 
deba@797:       EmbedArc embed_arc(_graph, INVALID);
deba@797: 
deba@797:       MergeRoots merge_roots(_graph);
deba@797: 
deba@797:       ArcLists arc_lists(_graph);
deba@797: 
deba@797:       FlipMap flip_map(_graph, false);
deba@797: 
deba@797:       for (int i = order_list.size() - 1; i >= 0; --i) {
deba@797: 
deba@797:         Node node = order_list[i];
deba@797: 
deba@797:         node_data[i].first = INVALID;
deba@797: 
deba@797:         Node source = node;
deba@797:         for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797:           Node target = _graph.target(e);
deba@797: 
deba@797:           if (order_map[source] < order_map[target] && tree_map[e]) {
deba@797:             initFace(target, arc_lists, node_data,
deba@797:                      pred_map, order_map, order_list);
deba@797:           }
deba@797:         }
deba@797: 
deba@797:         for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797:           Node target = _graph.target(e);
deba@797: 
deba@797:           if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@797:             embed_arc[target] = e;
deba@797:             walkUp(target, source, i, pred_map, low_map,
deba@797:                    order_map, order_list, node_data, merge_roots);
deba@797:           }
deba@797:         }
deba@797: 
deba@797:         for (typename MergeRoots::Value::iterator it =
deba@797:                merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
deba@797:           int rn = *it;
deba@797:           walkDown(rn, i, node_data, arc_lists, flip_map, order_list,
deba@797:                    child_lists, ancestor_map, low_map, embed_arc, merge_roots);
deba@797:         }
deba@797:         merge_roots[node].clear();
deba@797: 
deba@797:         for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797:           Node target = _graph.target(e);
deba@797: 
deba@797:           if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@797:             if (embed_arc[target] != INVALID) {
deba@797:               if (kuratowski) {
deba@797:                 isolateKuratowski(e, node_data, arc_lists, flip_map,
deba@797:                                   order_map, order_list, pred_map, child_lists,
deba@797:                                   ancestor_map, low_map,
deba@797:                                   embed_arc, merge_roots);
deba@797:               }
deba@797:               return false;
deba@797:             }
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       for (int i = 0; i < int(order_list.size()); ++i) {
deba@797: 
deba@797:         mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
deba@797:                             child_lists, arc_lists);
deba@797:         storeEmbedding(order_list[i], node_data, order_map, pred_map,
deba@797:                        arc_lists, flip_map);
deba@797:       }
deba@797: 
deba@797:       return true;
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Give back the successor of an arc
deba@797:     ///
kpeter@828:     /// This function gives back the successor of an arc. It makes
deba@797:     /// possible to query the cyclic order of the outgoing arcs from
deba@797:     /// a node.
deba@797:     Arc next(const Arc& arc) const {
deba@797:       return _embedding[arc];
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Give back the calculated embedding map
deba@797:     ///
kpeter@828:     /// This function gives back the calculated embedding map, which
kpeter@828:     /// contains the successor of each arc in the cyclic order of the
kpeter@828:     /// outgoing arcs of its source node.
deba@798:     const EmbeddingMap& embeddingMap() const {
deba@797:       return _embedding;
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Give back \c true if the given edge is in the Kuratowski
kpeter@828:     /// subdivision
deba@797:     ///
kpeter@828:     /// This function gives back \c true if the given edge is in the found
kpeter@828:     /// Kuratowski subdivision.
kpeter@828:     /// \pre The \c run() function must be called with \c true parameter
kpeter@828:     /// before using this function.
kpeter@828:     bool kuratowski(const Edge& edge) const {
deba@797:       return _kuratowski[edge];
deba@797:     }
deba@797: 
deba@797:   private:
deba@797: 
deba@797:     void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
deba@797:                           const LowMap& low_map, ChildLists& child_lists) {
deba@797: 
deba@797:       for (NodeIt n(_graph); n != INVALID; ++n) {
deba@797:         Node source = n;
deba@797: 
deba@797:         std::vector<Node> targets;
deba@797:         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
deba@797:           Node target = _graph.target(e);
deba@797: 
deba@797:           if (order_map[source] < order_map[target] && tree_map[e]) {
deba@797:             targets.push_back(target);
deba@797:           }
deba@797:         }
deba@797: 
deba@797:         if (targets.size() == 0) {
deba@797:           child_lists[source].first = INVALID;
deba@797:         } else if (targets.size() == 1) {
deba@797:           child_lists[source].first = targets[0];
deba@797:           child_lists[targets[0]].prev = INVALID;
deba@797:           child_lists[targets[0]].next = INVALID;
deba@797:         } else {
deba@797:           radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
deba@797:           for (int i = 1; i < int(targets.size()); ++i) {
deba@797:             child_lists[targets[i]].prev = targets[i - 1];
deba@797:             child_lists[targets[i - 1]].next = targets[i];
deba@797:           }
deba@797:           child_lists[targets.back()].next = INVALID;
deba@797:           child_lists[targets.front()].prev = INVALID;
deba@797:           child_lists[source].first = targets.front();
deba@797:         }
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void walkUp(const Node& node, Node root, int rorder,
deba@797:                 const PredMap& pred_map, const LowMap& low_map,
deba@797:                 const OrderMap& order_map, const OrderList& order_list,
deba@797:                 NodeData& node_data, MergeRoots& merge_roots) {
deba@797: 
deba@797:       int na, nb;
deba@797:       bool da, db;
deba@797: 
deba@797:       na = nb = order_map[node];
deba@797:       da = true; db = false;
deba@797: 
deba@797:       while (true) {
deba@797: 
deba@797:         if (node_data[na].visited == rorder) break;
deba@797:         if (node_data[nb].visited == rorder) break;
deba@797: 
deba@797:         node_data[na].visited = rorder;
deba@797:         node_data[nb].visited = rorder;
deba@797: 
deba@797:         int rn = -1;
deba@797: 
deba@797:         if (na >= int(order_list.size())) {
deba@797:           rn = na;
deba@797:         } else if (nb >= int(order_list.size())) {
deba@797:           rn = nb;
deba@797:         }
deba@797: 
deba@797:         if (rn == -1) {
deba@797:           int nn;
deba@797: 
deba@797:           nn = da ? node_data[na].prev : node_data[na].next;
deba@797:           da = node_data[nn].prev != na;
deba@797:           na = nn;
deba@797: 
deba@797:           nn = db ? node_data[nb].prev : node_data[nb].next;
deba@797:           db = node_data[nn].prev != nb;
deba@797:           nb = nn;
deba@797: 
deba@797:         } else {
deba@797: 
deba@797:           Node rep = order_list[rn - order_list.size()];
deba@797:           Node parent = _graph.source(pred_map[rep]);
deba@797: 
deba@797:           if (low_map[rep] < rorder) {
deba@797:             merge_roots[parent].push_back(rn);
deba@797:           } else {
deba@797:             merge_roots[parent].push_front(rn);
deba@797:           }
deba@797: 
deba@797:           if (parent != root) {
deba@797:             na = nb = order_map[parent];
deba@797:             da = true; db = false;
deba@797:           } else {
deba@797:             break;
deba@797:           }
deba@797:         }
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void walkDown(int rn, int rorder, NodeData& node_data,
deba@797:                   ArcLists& arc_lists, FlipMap& flip_map,
deba@797:                   OrderList& order_list, ChildLists& child_lists,
deba@797:                   AncestorMap& ancestor_map, LowMap& low_map,
deba@797:                   EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@797: 
deba@797:       std::vector<std::pair<int, bool> > merge_stack;
deba@797: 
deba@797:       for (int di = 0; di < 2; ++di) {
deba@797:         bool rd = di == 0;
deba@797:         int pn = rn;
deba@797:         int n = rd ? node_data[rn].next : node_data[rn].prev;
deba@797: 
deba@797:         while (n != rn) {
deba@797: 
deba@797:           Node node = order_list[n];
deba@797: 
deba@797:           if (embed_arc[node] != INVALID) {
deba@797: 
deba@797:             // Merging components on the critical path
deba@797:             while (!merge_stack.empty()) {
deba@797: 
deba@797:               // Component root
deba@797:               int cn = merge_stack.back().first;
deba@797:               bool cd = merge_stack.back().second;
deba@797:               merge_stack.pop_back();
deba@797: 
deba@797:               // Parent of component
deba@797:               int dn = merge_stack.back().first;
deba@797:               bool dd = merge_stack.back().second;
deba@797:               merge_stack.pop_back();
deba@797: 
deba@797:               Node parent = order_list[dn];
deba@797: 
deba@797:               // Erasing from merge_roots
deba@797:               merge_roots[parent].pop_front();
deba@797: 
deba@797:               Node child = order_list[cn - order_list.size()];
deba@797: 
deba@797:               // Erasing from child_lists
deba@797:               if (child_lists[child].prev != INVALID) {
deba@797:                 child_lists[child_lists[child].prev].next =
deba@797:                   child_lists[child].next;
deba@797:               } else {
deba@797:                 child_lists[parent].first = child_lists[child].next;
deba@797:               }
deba@797: 
deba@797:               if (child_lists[child].next != INVALID) {
deba@797:                 child_lists[child_lists[child].next].prev =
deba@797:                   child_lists[child].prev;
deba@797:               }
deba@797: 
deba@797:               // Merging arcs + flipping
deba@797:               Arc de = node_data[dn].first;
deba@797:               Arc ce = node_data[cn].first;
deba@797: 
deba@797:               flip_map[order_list[cn - order_list.size()]] = cd != dd;
deba@797:               if (cd != dd) {
deba@797:                 std::swap(arc_lists[ce].prev, arc_lists[ce].next);
deba@797:                 ce = arc_lists[ce].prev;
deba@797:                 std::swap(arc_lists[ce].prev, arc_lists[ce].next);
deba@797:               }
deba@797: 
deba@797:               {
deba@797:                 Arc dne = arc_lists[de].next;
deba@797:                 Arc cne = arc_lists[ce].next;
deba@797: 
deba@797:                 arc_lists[de].next = cne;
deba@797:                 arc_lists[ce].next = dne;
deba@797: 
deba@797:                 arc_lists[dne].prev = ce;
deba@797:                 arc_lists[cne].prev = de;
deba@797:               }
deba@797: 
deba@797:               if (dd) {
deba@797:                 node_data[dn].first = ce;
deba@797:               }
deba@797: 
deba@797:               // Merging external faces
deba@797:               {
deba@797:                 int en = cn;
deba@797:                 cn = cd ? node_data[cn].prev : node_data[cn].next;
deba@797:                 cd = node_data[cn].next == en;
deba@797: 
deba@797:                  if (node_data[cn].prev == node_data[cn].next &&
deba@797:                     node_data[cn].inverted) {
deba@797:                    cd = !cd;
deba@797:                  }
deba@797:               }
deba@797: 
deba@797:               if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
deba@797:               if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
deba@797: 
deba@797:             }
deba@797: 
deba@797:             bool d = pn == node_data[n].prev;
deba@797: 
deba@797:             if (node_data[n].prev == node_data[n].next &&
deba@797:                 node_data[n].inverted) {
deba@797:               d = !d;
deba@797:             }
deba@797: 
deba@797:             // Add new arc
deba@797:             {
deba@797:               Arc arc = embed_arc[node];
deba@797:               Arc re = node_data[rn].first;
deba@797: 
deba@797:               arc_lists[arc_lists[re].next].prev = arc;
deba@797:               arc_lists[arc].next = arc_lists[re].next;
deba@797:               arc_lists[arc].prev = re;
deba@797:               arc_lists[re].next = arc;
deba@797: 
deba@797:               if (!rd) {
deba@797:                 node_data[rn].first = arc;
deba@797:               }
deba@797: 
deba@797:               Arc rev = _graph.oppositeArc(arc);
deba@797:               Arc e = node_data[n].first;
deba@797: 
deba@797:               arc_lists[arc_lists[e].next].prev = rev;
deba@797:               arc_lists[rev].next = arc_lists[e].next;
deba@797:               arc_lists[rev].prev = e;
deba@797:               arc_lists[e].next = rev;
deba@797: 
deba@797:               if (d) {
deba@797:                 node_data[n].first = rev;
deba@797:               }
deba@797: 
deba@797:             }
deba@797: 
deba@797:             // Embedding arc into external face
deba@797:             if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
deba@797:             if (d) node_data[n].prev = rn; else node_data[n].next = rn;
deba@797:             pn = rn;
deba@797: 
deba@797:             embed_arc[order_list[n]] = INVALID;
deba@797:           }
deba@797: 
deba@797:           if (!merge_roots[node].empty()) {
deba@797: 
deba@797:             bool d = pn == node_data[n].prev;
deba@797:             if (node_data[n].prev == node_data[n].next &&
deba@797:                 node_data[n].inverted) {
deba@797:               d = !d;
deba@797:             }
deba@797: 
deba@797:             merge_stack.push_back(std::make_pair(n, d));
deba@797: 
deba@797:             int rn = merge_roots[node].front();
deba@797: 
deba@797:             int xn = node_data[rn].next;
deba@797:             Node xnode = order_list[xn];
deba@797: 
deba@797:             int yn = node_data[rn].prev;
deba@797:             Node ynode = order_list[yn];
deba@797: 
deba@797:             bool rd;
deba@797:             if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
deba@797:               rd = true;
deba@797:             } else if (!external(ynode, rorder, child_lists,
deba@797:                                  ancestor_map, low_map)) {
deba@797:               rd = false;
deba@797:             } else if (pertinent(xnode, embed_arc, merge_roots)) {
deba@797:               rd = true;
deba@797:             } else {
deba@797:               rd = false;
deba@797:             }
deba@797: 
deba@797:             merge_stack.push_back(std::make_pair(rn, rd));
deba@797: 
deba@797:             pn = rn;
deba@797:             n = rd ? xn : yn;
deba@797: 
deba@797:           } else if (!external(node, rorder, child_lists,
deba@797:                                ancestor_map, low_map)) {
deba@797:             int nn = (node_data[n].next != pn ?
deba@797:                       node_data[n].next : node_data[n].prev);
deba@797: 
deba@797:             bool nd = n == node_data[nn].prev;
deba@797: 
deba@797:             if (nd) node_data[nn].prev = pn;
deba@797:             else node_data[nn].next = pn;
deba@797: 
deba@797:             if (n == node_data[pn].prev) node_data[pn].prev = nn;
deba@797:             else node_data[pn].next = nn;
deba@797: 
deba@797:             node_data[nn].inverted =
deba@797:               (node_data[nn].prev == node_data[nn].next && nd != rd);
deba@797: 
deba@797:             n = nn;
deba@797:           }
deba@797:           else break;
deba@797: 
deba@797:         }
deba@797: 
deba@797:         if (!merge_stack.empty() || n == rn) {
deba@797:           break;
deba@797:         }
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void initFace(const Node& node, ArcLists& arc_lists,
deba@797:                   NodeData& node_data, const PredMap& pred_map,
deba@797:                   const OrderMap& order_map, const OrderList& order_list) {
deba@797:       int n = order_map[node];
deba@797:       int rn = n + order_list.size();
deba@797: 
deba@797:       node_data[n].next = node_data[n].prev = rn;
deba@797:       node_data[rn].next = node_data[rn].prev = n;
deba@797: 
deba@797:       node_data[n].visited = order_list.size();
deba@797:       node_data[rn].visited = order_list.size();
deba@797: 
deba@797:       node_data[n].inverted = false;
deba@797:       node_data[rn].inverted = false;
deba@797: 
deba@797:       Arc arc = pred_map[node];
deba@797:       Arc rev = _graph.oppositeArc(arc);
deba@797: 
deba@797:       node_data[rn].first = arc;
deba@797:       node_data[n].first = rev;
deba@797: 
deba@797:       arc_lists[arc].prev = arc;
deba@797:       arc_lists[arc].next = arc;
deba@797: 
deba@797:       arc_lists[rev].prev = rev;
deba@797:       arc_lists[rev].next = rev;
deba@797: 
deba@797:     }
deba@797: 
deba@797:     void mergeRemainingFaces(const Node& node, NodeData& node_data,
deba@797:                              OrderList& order_list, OrderMap& order_map,
deba@797:                              ChildLists& child_lists, ArcLists& arc_lists) {
deba@797:       while (child_lists[node].first != INVALID) {
deba@797:         int dd = order_map[node];
deba@797:         Node child = child_lists[node].first;
deba@797:         int cd = order_map[child] + order_list.size();
deba@797:         child_lists[node].first = child_lists[child].next;
deba@797: 
deba@797:         Arc de = node_data[dd].first;
deba@797:         Arc ce = node_data[cd].first;
deba@797: 
deba@797:         if (de != INVALID) {
deba@797:           Arc dne = arc_lists[de].next;
deba@797:           Arc cne = arc_lists[ce].next;
deba@797: 
deba@797:           arc_lists[de].next = cne;
deba@797:           arc_lists[ce].next = dne;
deba@797: 
deba@797:           arc_lists[dne].prev = ce;
deba@797:           arc_lists[cne].prev = de;
deba@797:         }
deba@797: 
deba@797:         node_data[dd].first = ce;
deba@797: 
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void storeEmbedding(const Node& node, NodeData& node_data,
deba@797:                         OrderMap& order_map, PredMap& pred_map,
deba@797:                         ArcLists& arc_lists, FlipMap& flip_map) {
deba@797: 
deba@797:       if (node_data[order_map[node]].first == INVALID) return;
deba@797: 
deba@797:       if (pred_map[node] != INVALID) {
deba@797:         Node source = _graph.source(pred_map[node]);
deba@797:         flip_map[node] = flip_map[node] != flip_map[source];
deba@797:       }
deba@797: 
deba@797:       Arc first = node_data[order_map[node]].first;
deba@797:       Arc prev = first;
deba@797: 
deba@797:       Arc arc = flip_map[node] ?
deba@797:         arc_lists[prev].prev : arc_lists[prev].next;
deba@797: 
deba@797:       _embedding[prev] = arc;
deba@797: 
deba@797:       while (arc != first) {
deba@797:         Arc next = arc_lists[arc].prev == prev ?
deba@797:           arc_lists[arc].next : arc_lists[arc].prev;
deba@797:         prev = arc; arc = next;
deba@797:         _embedding[prev] = arc;
deba@797:       }
deba@797:     }
deba@797: 
deba@797: 
deba@797:     bool external(const Node& node, int rorder,
deba@797:                   ChildLists& child_lists, AncestorMap& ancestor_map,
deba@797:                   LowMap& low_map) {
deba@797:       Node child = child_lists[node].first;
deba@797: 
deba@797:       if (child != INVALID) {
deba@797:         if (low_map[child] < rorder) return true;
deba@797:       }
deba@797: 
deba@797:       if (ancestor_map[node] < rorder) return true;
deba@797: 
deba@797:       return false;
deba@797:     }
deba@797: 
deba@797:     bool pertinent(const Node& node, const EmbedArc& embed_arc,
deba@797:                    const MergeRoots& merge_roots) {
deba@797:       return !merge_roots[node].empty() || embed_arc[node] != INVALID;
deba@797:     }
deba@797: 
deba@797:     int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
deba@797:                  AncestorMap& ancestor_map, LowMap& low_map) {
deba@797:       int low_point;
deba@797: 
deba@797:       Node child = child_lists[node].first;
deba@797: 
deba@797:       if (child != INVALID) {
deba@797:         low_point = low_map[child];
deba@797:       } else {
deba@797:         low_point = order_map[node];
deba@797:       }
deba@797: 
deba@797:       if (low_point > ancestor_map[node]) {
deba@797:         low_point = ancestor_map[node];
deba@797:       }
deba@797: 
deba@797:       return low_point;
deba@797:     }
deba@797: 
deba@797:     int findComponentRoot(Node root, Node node, ChildLists& child_lists,
deba@797:                           OrderMap& order_map, OrderList& order_list) {
deba@797: 
deba@797:       int order = order_map[root];
deba@797:       int norder = order_map[node];
deba@797: 
deba@797:       Node child = child_lists[root].first;
deba@797:       while (child != INVALID) {
deba@797:         int corder = order_map[child];
deba@797:         if (corder > order && corder < norder) {
deba@797:           order = corder;
deba@797:         }
deba@797:         child = child_lists[child].next;
deba@797:       }
deba@797:       return order + order_list.size();
deba@797:     }
deba@797: 
deba@797:     Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data,
deba@797:                        EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@797:       Node wnode =_graph.target(node_data[order_map[node]].first);
deba@797:       while (!pertinent(wnode, embed_arc, merge_roots)) {
deba@797:         wnode = _graph.target(node_data[order_map[wnode]].first);
deba@797:       }
deba@797:       return wnode;
deba@797:     }
deba@797: 
deba@797: 
deba@797:     Node findExternal(Node node, int rorder, OrderMap& order_map,
deba@797:                       ChildLists& child_lists, AncestorMap& ancestor_map,
deba@797:                       LowMap& low_map, NodeData& node_data) {
deba@797:       Node wnode =_graph.target(node_data[order_map[node]].first);
deba@797:       while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
deba@797:         wnode = _graph.target(node_data[order_map[wnode]].first);
deba@797:       }
deba@797:       return wnode;
deba@797:     }
deba@797: 
deba@797:     void markCommonPath(Node node, int rorder, Node& wnode, Node& znode,
deba@797:                         OrderList& order_list, OrderMap& order_map,
deba@797:                         NodeData& node_data, ArcLists& arc_lists,
deba@797:                         EmbedArc& embed_arc, MergeRoots& merge_roots,
deba@797:                         ChildLists& child_lists, AncestorMap& ancestor_map,
deba@797:                         LowMap& low_map) {
deba@797: 
deba@797:       Node cnode = node;
deba@797:       Node pred = INVALID;
deba@797: 
deba@797:       while (true) {
deba@797: 
deba@797:         bool pert = pertinent(cnode, embed_arc, merge_roots);
deba@797:         bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
deba@797: 
deba@797:         if (pert && ext) {
deba@797:           if (!merge_roots[cnode].empty()) {
deba@797:             int cn = merge_roots[cnode].back();
deba@797: 
deba@797:             if (low_map[order_list[cn - order_list.size()]] < rorder) {
deba@797:               Arc arc = node_data[cn].first;
deba@797:               _kuratowski.set(arc, true);
deba@797: 
deba@797:               pred = cnode;
deba@797:               cnode = _graph.target(arc);
deba@797: 
deba@797:               continue;
deba@797:             }
deba@797:           }
deba@797:           wnode = znode = cnode;
deba@797:           return;
deba@797: 
deba@797:         } else if (pert) {
deba@797:           wnode = cnode;
deba@797: 
deba@797:           while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
deba@797:             Arc arc = node_data[order_map[cnode]].first;
deba@797: 
deba@797:             if (_graph.target(arc) == pred) {
deba@797:               arc = arc_lists[arc].next;
deba@797:             }
deba@797:             _kuratowski.set(arc, true);
deba@797: 
deba@797:             Node next = _graph.target(arc);
deba@797:             pred = cnode; cnode = next;
deba@797:           }
deba@797: 
deba@797:           znode = cnode;
deba@797:           return;
deba@797: 
deba@797:         } else if (ext) {
deba@797:           znode = cnode;
deba@797: 
deba@797:           while (!pertinent(cnode, embed_arc, merge_roots)) {
deba@797:             Arc arc = node_data[order_map[cnode]].first;
deba@797: 
deba@797:             if (_graph.target(arc) == pred) {
deba@797:               arc = arc_lists[arc].next;
deba@797:             }
deba@797:             _kuratowski.set(arc, true);
deba@797: 
deba@797:             Node next = _graph.target(arc);
deba@797:             pred = cnode; cnode = next;
deba@797:           }
deba@797: 
deba@797:           wnode = cnode;
deba@797:           return;
deba@797: 
deba@797:         } else {
deba@797:           Arc arc = node_data[order_map[cnode]].first;
deba@797: 
deba@797:           if (_graph.target(arc) == pred) {
deba@797:             arc = arc_lists[arc].next;
deba@797:           }
deba@797:           _kuratowski.set(arc, true);
deba@797: 
deba@797:           Node next = _graph.target(arc);
deba@797:           pred = cnode; cnode = next;
deba@797:         }
deba@797: 
deba@797:       }
deba@797: 
deba@797:     }
deba@797: 
deba@797:     void orientComponent(Node root, int rn, OrderMap& order_map,
deba@797:                          PredMap& pred_map, NodeData& node_data,
deba@797:                          ArcLists& arc_lists, FlipMap& flip_map,
deba@797:                          TypeMap& type_map) {
deba@797:       node_data[order_map[root]].first = node_data[rn].first;
deba@797:       type_map[root] = 1;
deba@797: 
deba@797:       std::vector<Node> st, qu;
deba@797: 
deba@797:       st.push_back(root);
deba@797:       while (!st.empty()) {
deba@797:         Node node = st.back();
deba@797:         st.pop_back();
deba@797:         qu.push_back(node);
deba@797: 
deba@797:         Arc arc = node_data[order_map[node]].first;
deba@797: 
deba@797:         if (type_map[_graph.target(arc)] == 0) {
deba@797:           st.push_back(_graph.target(arc));
deba@797:           type_map[_graph.target(arc)] = 1;
deba@797:         }
deba@797: 
deba@797:         Arc last = arc, pred = arc;
deba@797:         arc = arc_lists[arc].next;
deba@797:         while (arc != last) {
deba@797: 
deba@797:           if (type_map[_graph.target(arc)] == 0) {
deba@797:             st.push_back(_graph.target(arc));
deba@797:             type_map[_graph.target(arc)] = 1;
deba@797:           }
deba@797: 
deba@797:           Arc next = arc_lists[arc].next != pred ?
deba@797:             arc_lists[arc].next : arc_lists[arc].prev;
deba@797:           pred = arc; arc = next;
deba@797:         }
deba@797: 
deba@797:       }
deba@797: 
deba@797:       type_map[root] = 2;
deba@797:       flip_map[root] = false;
deba@797: 
deba@797:       for (int i = 1; i < int(qu.size()); ++i) {
deba@797: 
deba@797:         Node node = qu[i];
deba@797: 
deba@797:         while (type_map[node] != 2) {
deba@797:           st.push_back(node);
deba@797:           type_map[node] = 2;
deba@797:           node = _graph.source(pred_map[node]);
deba@797:         }
deba@797: 
deba@797:         bool flip = flip_map[node];
deba@797: 
deba@797:         while (!st.empty()) {
deba@797:           node = st.back();
deba@797:           st.pop_back();
deba@797: 
deba@797:           flip_map[node] = flip != flip_map[node];
deba@797:           flip = flip_map[node];
deba@797: 
deba@797:           if (flip) {
deba@797:             Arc arc = node_data[order_map[node]].first;
deba@797:             std::swap(arc_lists[arc].prev, arc_lists[arc].next);
deba@797:             arc = arc_lists[arc].prev;
deba@797:             std::swap(arc_lists[arc].prev, arc_lists[arc].next);
deba@797:             node_data[order_map[node]].first = arc;
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       for (int i = 0; i < int(qu.size()); ++i) {
deba@797: 
deba@797:         Arc arc = node_data[order_map[qu[i]]].first;
deba@797:         Arc last = arc, pred = arc;
deba@797: 
deba@797:         arc = arc_lists[arc].next;
deba@797:         while (arc != last) {
deba@797: 
deba@797:           if (arc_lists[arc].next == pred) {
deba@797:             std::swap(arc_lists[arc].next, arc_lists[arc].prev);
deba@797:           }
deba@797:           pred = arc; arc = arc_lists[arc].next;
deba@797:         }
deba@797: 
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode,
deba@797:                       OrderMap& order_map, NodeData& node_data,
deba@797:                       TypeMap& type_map) {
deba@797:       Node node = _graph.target(node_data[order_map[root]].first);
deba@797: 
deba@797:       while (node != ynode) {
deba@797:         type_map[node] = HIGHY;
deba@797:         node = _graph.target(node_data[order_map[node]].first);
deba@797:       }
deba@797: 
deba@797:       while (node != wnode) {
deba@797:         type_map[node] = LOWY;
deba@797:         node = _graph.target(node_data[order_map[node]].first);
deba@797:       }
deba@797: 
deba@797:       node = _graph.target(node_data[order_map[wnode]].first);
deba@797: 
deba@797:       while (node != xnode) {
deba@797:         type_map[node] = LOWX;
deba@797:         node = _graph.target(node_data[order_map[node]].first);
deba@797:       }
deba@797:       type_map[node] = LOWX;
deba@797: 
deba@797:       node = _graph.target(node_data[order_map[xnode]].first);
deba@797:       while (node != root) {
deba@797:         type_map[node] = HIGHX;
deba@797:         node = _graph.target(node_data[order_map[node]].first);
deba@797:       }
deba@797: 
deba@797:       type_map[wnode] = PERTINENT;
deba@797:       type_map[root] = ROOT;
deba@797:     }
deba@797: 
deba@797:     void findInternalPath(std::vector<Arc>& ipath,
deba@797:                           Node wnode, Node root, TypeMap& type_map,
deba@797:                           OrderMap& order_map, NodeData& node_data,
deba@797:                           ArcLists& arc_lists) {
deba@797:       std::vector<Arc> st;
deba@797: 
deba@797:       Node node = wnode;
deba@797: 
deba@797:       while (node != root) {
deba@797:         Arc arc = arc_lists[node_data[order_map[node]].first].next;
deba@797:         st.push_back(arc);
deba@797:         node = _graph.target(arc);
deba@797:       }
deba@797: 
deba@797:       while (true) {
deba@797:         Arc arc = st.back();
deba@797:         if (type_map[_graph.target(arc)] == LOWX ||
deba@797:             type_map[_graph.target(arc)] == HIGHX) {
deba@797:           break;
deba@797:         }
deba@797:         if (type_map[_graph.target(arc)] == 2) {
deba@797:           type_map[_graph.target(arc)] = 3;
deba@797: 
deba@797:           arc = arc_lists[_graph.oppositeArc(arc)].next;
deba@797:           st.push_back(arc);
deba@797:         } else {
deba@797:           st.pop_back();
deba@797:           arc = arc_lists[arc].next;
deba@797: 
deba@797:           while (_graph.oppositeArc(arc) == st.back()) {
deba@797:             arc = st.back();
deba@797:             st.pop_back();
deba@797:             arc = arc_lists[arc].next;
deba@797:           }
deba@797:           st.push_back(arc);
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       for (int i = 0; i < int(st.size()); ++i) {
deba@797:         if (type_map[_graph.target(st[i])] != LOWY &&
deba@797:             type_map[_graph.target(st[i])] != HIGHY) {
deba@797:           for (; i < int(st.size()); ++i) {
deba@797:             ipath.push_back(st[i]);
deba@797:           }
deba@797:         }
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void setInternalFlags(std::vector<Arc>& ipath, TypeMap& type_map) {
deba@797:       for (int i = 1; i < int(ipath.size()); ++i) {
deba@797:         type_map[_graph.source(ipath[i])] = INTERNAL;
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void findPilePath(std::vector<Arc>& ppath,
deba@797:                       Node root, TypeMap& type_map, OrderMap& order_map,
deba@797:                       NodeData& node_data, ArcLists& arc_lists) {
deba@797:       std::vector<Arc> st;
deba@797: 
deba@797:       st.push_back(_graph.oppositeArc(node_data[order_map[root]].first));
deba@797:       st.push_back(node_data[order_map[root]].first);
deba@797: 
deba@797:       while (st.size() > 1) {
deba@797:         Arc arc = st.back();
deba@797:         if (type_map[_graph.target(arc)] == INTERNAL) {
deba@797:           break;
deba@797:         }
deba@797:         if (type_map[_graph.target(arc)] == 3) {
deba@797:           type_map[_graph.target(arc)] = 4;
deba@797: 
deba@797:           arc = arc_lists[_graph.oppositeArc(arc)].next;
deba@797:           st.push_back(arc);
deba@797:         } else {
deba@797:           st.pop_back();
deba@797:           arc = arc_lists[arc].next;
deba@797: 
deba@797:           while (!st.empty() && _graph.oppositeArc(arc) == st.back()) {
deba@797:             arc = st.back();
deba@797:             st.pop_back();
deba@797:             arc = arc_lists[arc].next;
deba@797:           }
deba@797:           st.push_back(arc);
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       for (int i = 1; i < int(st.size()); ++i) {
deba@797:         ppath.push_back(st[i]);
deba@797:       }
deba@797:     }
deba@797: 
deba@797: 
deba@797:     int markExternalPath(Node node, OrderMap& order_map,
deba@797:                          ChildLists& child_lists, PredMap& pred_map,
deba@797:                          AncestorMap& ancestor_map, LowMap& low_map) {
deba@797:       int lp = lowPoint(node, order_map, child_lists,
deba@797:                         ancestor_map, low_map);
deba@797: 
deba@797:       if (ancestor_map[node] != lp) {
deba@797:         node = child_lists[node].first;
deba@797:         _kuratowski[pred_map[node]] = true;
deba@797: 
deba@797:         while (ancestor_map[node] != lp) {
deba@797:           for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797:             Node tnode = _graph.target(e);
deba@797:             if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) {
deba@797:               node = tnode;
deba@797:               _kuratowski[e] = true;
deba@797:               break;
deba@797:             }
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797:         if (order_map[_graph.target(e)] == lp) {
deba@797:           _kuratowski[e] = true;
deba@797:           break;
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       return lp;
deba@797:     }
deba@797: 
deba@797:     void markPertinentPath(Node node, OrderMap& order_map,
deba@797:                            NodeData& node_data, ArcLists& arc_lists,
deba@797:                            EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@797:       while (embed_arc[node] == INVALID) {
deba@797:         int n = merge_roots[node].front();
deba@797:         Arc arc = node_data[n].first;
deba@797: 
deba@797:         _kuratowski.set(arc, true);
deba@797: 
deba@797:         Node pred = node;
deba@797:         node = _graph.target(arc);
deba@797:         while (!pertinent(node, embed_arc, merge_roots)) {
deba@797:           arc = node_data[order_map[node]].first;
deba@797:           if (_graph.target(arc) == pred) {
deba@797:             arc = arc_lists[arc].next;
deba@797:           }
deba@797:           _kuratowski.set(arc, true);
deba@797:           pred = node;
deba@797:           node = _graph.target(arc);
deba@797:         }
deba@797:       }
deba@797:       _kuratowski.set(embed_arc[node], true);
deba@797:     }
deba@797: 
deba@797:     void markPredPath(Node node, Node snode, PredMap& pred_map) {
deba@797:       while (node != snode) {
deba@797:         _kuratowski.set(pred_map[node], true);
deba@797:         node = _graph.source(pred_map[node]);
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void markFacePath(Node ynode, Node xnode,
deba@797:                       OrderMap& order_map, NodeData& node_data) {
deba@797:       Arc arc = node_data[order_map[ynode]].first;
deba@797:       Node node = _graph.target(arc);
deba@797:       _kuratowski.set(arc, true);
deba@797: 
deba@797:       while (node != xnode) {
deba@797:         arc = node_data[order_map[node]].first;
deba@797:         _kuratowski.set(arc, true);
deba@797:         node = _graph.target(arc);
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void markInternalPath(std::vector<Arc>& path) {
deba@797:       for (int i = 0; i < int(path.size()); ++i) {
deba@797:         _kuratowski.set(path[i], true);
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void markPilePath(std::vector<Arc>& path) {
deba@797:       for (int i = 0; i < int(path.size()); ++i) {
deba@797:         _kuratowski.set(path[i], true);
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     void isolateKuratowski(Arc arc, NodeData& node_data,
deba@797:                            ArcLists& arc_lists, FlipMap& flip_map,
deba@797:                            OrderMap& order_map, OrderList& order_list,
deba@797:                            PredMap& pred_map, ChildLists& child_lists,
deba@797:                            AncestorMap& ancestor_map, LowMap& low_map,
deba@797:                            EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@797: 
deba@797:       Node root = _graph.source(arc);
deba@797:       Node enode = _graph.target(arc);
deba@797: 
deba@797:       int rorder = order_map[root];
deba@797: 
deba@797:       TypeMap type_map(_graph, 0);
deba@797: 
deba@797:       int rn = findComponentRoot(root, enode, child_lists,
deba@797:                                  order_map, order_list);
deba@797: 
deba@797:       Node xnode = order_list[node_data[rn].next];
deba@797:       Node ynode = order_list[node_data[rn].prev];
deba@797: 
deba@797:       // Minor-A
deba@797:       {
deba@797:         while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
deba@797: 
deba@797:           if (!merge_roots[xnode].empty()) {
deba@797:             root = xnode;
deba@797:             rn = merge_roots[xnode].front();
deba@797:           } else {
deba@797:             root = ynode;
deba@797:             rn = merge_roots[ynode].front();
deba@797:           }
deba@797: 
deba@797:           xnode = order_list[node_data[rn].next];
deba@797:           ynode = order_list[node_data[rn].prev];
deba@797:         }
deba@797: 
deba@797:         if (root != _graph.source(arc)) {
deba@797:           orientComponent(root, rn, order_map, pred_map,
deba@797:                           node_data, arc_lists, flip_map, type_map);
deba@797:           markFacePath(root, root, order_map, node_data);
deba@797:           int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797:           int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797:           markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797:           Node lwnode = findPertinent(ynode, order_map, node_data,
deba@797:                                       embed_arc, merge_roots);
deba@797: 
deba@797:           markPertinentPath(lwnode, order_map, node_data, arc_lists,
deba@797:                             embed_arc, merge_roots);
deba@797: 
deba@797:           return;
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       orientComponent(root, rn, order_map, pred_map,
deba@797:                       node_data, arc_lists, flip_map, type_map);
deba@797: 
deba@797:       Node wnode = findPertinent(ynode, order_map, node_data,
deba@797:                                  embed_arc, merge_roots);
deba@797:       setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map);
deba@797: 
deba@797: 
deba@797:       //Minor-B
deba@797:       if (!merge_roots[wnode].empty()) {
deba@797:         int cn = merge_roots[wnode].back();
deba@797:         Node rep = order_list[cn - order_list.size()];
deba@797:         if (low_map[rep] < rorder) {
deba@797:           markFacePath(root, root, order_map, node_data);
deba@797:           int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797:           int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797: 
deba@797:           Node lwnode, lznode;
deba@797:           markCommonPath(wnode, rorder, lwnode, lznode, order_list,
deba@797:                          order_map, node_data, arc_lists, embed_arc,
deba@797:                          merge_roots, child_lists, ancestor_map, low_map);
deba@797: 
deba@797:           markPertinentPath(lwnode, order_map, node_data, arc_lists,
deba@797:                             embed_arc, merge_roots);
deba@797:           int zlp = markExternalPath(lznode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797: 
deba@797:           int minlp = xlp < ylp ? xlp : ylp;
deba@797:           if (zlp < minlp) minlp = zlp;
deba@797: 
deba@797:           int maxlp = xlp > ylp ? xlp : ylp;
deba@797:           if (zlp > maxlp) maxlp = zlp;
deba@797: 
deba@797:           markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@797: 
deba@797:           return;
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       Node pxnode, pynode;
deba@797:       std::vector<Arc> ipath;
deba@797:       findInternalPath(ipath, wnode, root, type_map, order_map,
deba@797:                        node_data, arc_lists);
deba@797:       setInternalFlags(ipath, type_map);
deba@797:       pynode = _graph.source(ipath.front());
deba@797:       pxnode = _graph.target(ipath.back());
deba@797: 
deba@797:       wnode = findPertinent(pynode, order_map, node_data,
deba@797:                             embed_arc, merge_roots);
deba@797: 
deba@797:       // Minor-C
deba@797:       {
deba@797:         if (type_map[_graph.source(ipath.front())] == HIGHY) {
deba@797:           if (type_map[_graph.target(ipath.back())] == HIGHX) {
deba@797:             markFacePath(xnode, pxnode, order_map, node_data);
deba@797:           }
deba@797:           markFacePath(root, xnode, order_map, node_data);
deba@797:           markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797:                             embed_arc, merge_roots);
deba@797:           markInternalPath(ipath);
deba@797:           int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797:           int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797:           markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797:           return;
deba@797:         }
deba@797: 
deba@797:         if (type_map[_graph.target(ipath.back())] == HIGHX) {
deba@797:           markFacePath(ynode, root, order_map, node_data);
deba@797:           markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797:                             embed_arc, merge_roots);
deba@797:           markInternalPath(ipath);
deba@797:           int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797:           int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797:                                      pred_map, ancestor_map, low_map);
deba@797:           markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797:           return;
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       std::vector<Arc> ppath;
deba@797:       findPilePath(ppath, root, type_map, order_map, node_data, arc_lists);
deba@797: 
deba@797:       // Minor-D
deba@797:       if (!ppath.empty()) {
deba@797:         markFacePath(ynode, xnode, order_map, node_data);
deba@797:         markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797:                           embed_arc, merge_roots);
deba@797:         markPilePath(ppath);
deba@797:         markInternalPath(ipath);
deba@797:         int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797:                                    pred_map, ancestor_map, low_map);
deba@797:         int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797:                                    pred_map, ancestor_map, low_map);
deba@797:         markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797:         return;
deba@797:       }
deba@797: 
deba@797:       // Minor-E*
deba@797:       {
deba@797: 
deba@797:         if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
deba@797:           Node znode = findExternal(pynode, rorder, order_map,
deba@797:                                     child_lists, ancestor_map,
deba@797:                                     low_map, node_data);
deba@797: 
deba@797:           if (type_map[znode] == LOWY) {
deba@797:             markFacePath(root, xnode, order_map, node_data);
deba@797:             markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797:                               embed_arc, merge_roots);
deba@797:             markInternalPath(ipath);
deba@797:             int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797:                                        pred_map, ancestor_map, low_map);
deba@797:             int zlp = markExternalPath(znode, order_map, child_lists,
deba@797:                                        pred_map, ancestor_map, low_map);
deba@797:             markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map);
deba@797:           } else {
deba@797:             markFacePath(ynode, root, order_map, node_data);
deba@797:             markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797:                               embed_arc, merge_roots);
deba@797:             markInternalPath(ipath);
deba@797:             int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797:                                        pred_map, ancestor_map, low_map);
deba@797:             int zlp = markExternalPath(znode, order_map, child_lists,
deba@797:                                        pred_map, ancestor_map, low_map);
deba@797:             markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map);
deba@797:           }
deba@797:           return;
deba@797:         }
deba@797: 
deba@797:         int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797:                                    pred_map, ancestor_map, low_map);
deba@797:         int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797:                                    pred_map, ancestor_map, low_map);
deba@797:         int wlp = markExternalPath(wnode, order_map, child_lists,
deba@797:                                    pred_map, ancestor_map, low_map);
deba@797: 
deba@797:         if (wlp > xlp && wlp > ylp) {
deba@797:           markFacePath(root, root, order_map, node_data);
deba@797:           markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797:           return;
deba@797:         }
deba@797: 
deba@797:         markInternalPath(ipath);
deba@797:         markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797:                           embed_arc, merge_roots);
deba@797: 
deba@797:         if (xlp > ylp && xlp > wlp) {
deba@797:           markFacePath(root, pynode, order_map, node_data);
deba@797:           markFacePath(wnode, xnode, order_map, node_data);
deba@797:           markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map);
deba@797:           return;
deba@797:         }
deba@797: 
deba@797:         if (ylp > xlp && ylp > wlp) {
deba@797:           markFacePath(pxnode, root, order_map, node_data);
deba@797:           markFacePath(ynode, wnode, order_map, node_data);
deba@797:           markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map);
deba@797:           return;
deba@797:         }
deba@797: 
deba@797:         if (pynode != ynode) {
deba@797:           markFacePath(pxnode, wnode, order_map, node_data);
deba@797: 
deba@797:           int minlp = xlp < ylp ? xlp : ylp;
deba@797:           if (wlp < minlp) minlp = wlp;
deba@797: 
deba@797:           int maxlp = xlp > ylp ? xlp : ylp;
deba@797:           if (wlp > maxlp) maxlp = wlp;
deba@797: 
deba@797:           markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@797:           return;
deba@797:         }
deba@797: 
deba@797:         if (pxnode != xnode) {
deba@797:           markFacePath(wnode, pynode, order_map, node_data);
deba@797: 
deba@797:           int minlp = xlp < ylp ? xlp : ylp;
deba@797:           if (wlp < minlp) minlp = wlp;
deba@797: 
deba@797:           int maxlp = xlp > ylp ? xlp : ylp;
deba@797:           if (wlp > maxlp) maxlp = wlp;
deba@797: 
deba@797:           markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@797:           return;
deba@797:         }
deba@797: 
deba@797:         markFacePath(root, root, order_map, node_data);
deba@797:         int minlp = xlp < ylp ? xlp : ylp;
deba@797:         if (wlp < minlp) minlp = wlp;
deba@797:         markPredPath(root, order_list[minlp], pred_map);
deba@797:         return;
deba@797:       }
deba@797: 
deba@797:     }
deba@797: 
deba@797:   };
deba@797: 
deba@797:   namespace _planarity_bits {
deba@797: 
deba@797:     template <typename Graph, typename EmbeddingMap>
deba@797:     void makeConnected(Graph& graph, EmbeddingMap& embedding) {
deba@797:       DfsVisitor<Graph> null_visitor;
deba@797:       DfsVisit<Graph, DfsVisitor<Graph> > dfs(graph, null_visitor);
deba@797:       dfs.init();
deba@797: 
deba@797:       typename Graph::Node u = INVALID;
deba@797:       for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@797:         if (!dfs.reached(n)) {
deba@797:           dfs.addSource(n);
deba@797:           dfs.start();
deba@797:           if (u == INVALID) {
deba@797:             u = n;
deba@797:           } else {
deba@797:             typename Graph::Node v = n;
deba@797: 
deba@797:             typename Graph::Arc ue = typename Graph::OutArcIt(graph, u);
deba@797:             typename Graph::Arc ve = typename Graph::OutArcIt(graph, v);
deba@797: 
deba@797:             typename Graph::Arc e = graph.direct(graph.addEdge(u, v), true);
deba@797: 
deba@797:             if (ue != INVALID) {
deba@797:               embedding[e] = embedding[ue];
deba@797:               embedding[ue] = e;
deba@797:             } else {
deba@797:               embedding[e] = e;
deba@797:             }
deba@797: 
deba@797:             if (ve != INVALID) {
deba@797:               embedding[graph.oppositeArc(e)] = embedding[ve];
deba@797:               embedding[ve] = graph.oppositeArc(e);
deba@797:             } else {
deba@797:               embedding[graph.oppositeArc(e)] = graph.oppositeArc(e);
deba@797:             }
deba@797:           }
deba@797:         }
deba@797:       }
deba@797:     }
deba@797: 
deba@797:     template <typename Graph, typename EmbeddingMap>
deba@797:     void makeBiNodeConnected(Graph& graph, EmbeddingMap& embedding) {
deba@797:       typename Graph::template ArcMap<bool> processed(graph);
deba@797: 
deba@797:       std::vector<typename Graph::Arc> arcs;
deba@797:       for (typename Graph::ArcIt e(graph); e != INVALID; ++e) {
deba@797:         arcs.push_back(e);
deba@797:       }
deba@797: 
deba@797:       IterableBoolMap<Graph, typename Graph::Node> visited(graph, false);
deba@797: 
deba@797:       for (int i = 0; i < int(arcs.size()); ++i) {
deba@797:         typename Graph::Arc pp = arcs[i];
deba@797:         if (processed[pp]) continue;
deba@797: 
deba@797:         typename Graph::Arc e = embedding[graph.oppositeArc(pp)];
deba@797:         processed[e] = true;
deba@797:         visited.set(graph.source(e), true);
deba@797: 
deba@797:         typename Graph::Arc p = e, l = e;
deba@797:         e = embedding[graph.oppositeArc(e)];
deba@797: 
deba@797:         while (e != l) {
deba@797:           processed[e] = true;
deba@797: 
deba@797:           if (visited[graph.source(e)]) {
deba@797: 
deba@797:             typename Graph::Arc n =
deba@797:               graph.direct(graph.addEdge(graph.source(p),
deba@797:                                            graph.target(e)), true);
deba@797:             embedding[n] = p;
deba@797:             embedding[graph.oppositeArc(pp)] = n;
deba@797: 
deba@797:             embedding[graph.oppositeArc(n)] =
deba@797:               embedding[graph.oppositeArc(e)];
deba@797:             embedding[graph.oppositeArc(e)] =
deba@797:               graph.oppositeArc(n);
deba@797: 
deba@797:             p = n;
deba@797:             e = embedding[graph.oppositeArc(n)];
deba@797:           } else {
deba@797:             visited.set(graph.source(e), true);
deba@797:             pp = p;
deba@797:             p = e;
deba@797:             e = embedding[graph.oppositeArc(e)];
deba@797:           }
deba@797:         }
deba@797:         visited.setAll(false);
deba@797:       }
deba@797:     }
deba@797: 
deba@797: 
deba@797:     template <typename Graph, typename EmbeddingMap>
deba@797:     void makeMaxPlanar(Graph& graph, EmbeddingMap& embedding) {
deba@797: 
deba@797:       typename Graph::template NodeMap<int> degree(graph);
deba@797: 
deba@797:       for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@797:         degree[n] = countIncEdges(graph, n);
deba@797:       }
deba@797: 
deba@797:       typename Graph::template ArcMap<bool> processed(graph);
deba@797:       IterableBoolMap<Graph, typename Graph::Node> visited(graph, false);
deba@797: 
deba@797:       std::vector<typename Graph::Arc> arcs;
deba@797:       for (typename Graph::ArcIt e(graph); e != INVALID; ++e) {
deba@797:         arcs.push_back(e);
deba@797:       }
deba@797: 
deba@797:       for (int i = 0; i < int(arcs.size()); ++i) {
deba@797:         typename Graph::Arc e = arcs[i];
deba@797: 
deba@797:         if (processed[e]) continue;
deba@797:         processed[e] = true;
deba@797: 
deba@797:         typename Graph::Arc mine = e;
deba@797:         int mind = degree[graph.source(e)];
deba@797: 
deba@797:         int face_size = 1;
deba@797: 
deba@797:         typename Graph::Arc l = e;
deba@797:         e = embedding[graph.oppositeArc(e)];
deba@797:         while (l != e) {
deba@797:           processed[e] = true;
deba@797: 
deba@797:           ++face_size;
deba@797: 
deba@797:           if (degree[graph.source(e)] < mind) {
deba@797:             mine = e;
deba@797:             mind = degree[graph.source(e)];
deba@797:           }
deba@797: 
deba@797:           e = embedding[graph.oppositeArc(e)];
deba@797:         }
deba@797: 
deba@797:         if (face_size < 4) {
deba@797:           continue;
deba@797:         }
deba@797: 
deba@797:         typename Graph::Node s = graph.source(mine);
deba@797:         for (typename Graph::OutArcIt e(graph, s); e != INVALID; ++e) {
deba@797:           visited.set(graph.target(e), true);
deba@797:         }
deba@797: 
deba@797:         typename Graph::Arc oppe = INVALID;
deba@797: 
deba@797:         e = embedding[graph.oppositeArc(mine)];
deba@797:         e = embedding[graph.oppositeArc(e)];
deba@797:         while (graph.target(e) != s) {
deba@797:           if (visited[graph.source(e)]) {
deba@797:             oppe = e;
deba@797:             break;
deba@797:           }
deba@797:           e = embedding[graph.oppositeArc(e)];
deba@797:         }
deba@797:         visited.setAll(false);
deba@797: 
deba@797:         if (oppe == INVALID) {
deba@797: 
deba@797:           e = embedding[graph.oppositeArc(mine)];
deba@797:           typename Graph::Arc pn = mine, p = e;
deba@797: 
deba@797:           e = embedding[graph.oppositeArc(e)];
deba@797:           while (graph.target(e) != s) {
deba@797:             typename Graph::Arc n =
deba@797:               graph.direct(graph.addEdge(s, graph.source(e)), true);
deba@797: 
deba@797:             embedding[n] = pn;
deba@797:             embedding[graph.oppositeArc(n)] = e;
deba@797:             embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
deba@797: 
deba@797:             pn = n;
deba@797: 
deba@797:             p = e;
deba@797:             e = embedding[graph.oppositeArc(e)];
deba@797:           }
deba@797: 
deba@797:           embedding[graph.oppositeArc(e)] = pn;
deba@797: 
deba@797:         } else {
deba@797: 
deba@797:           mine = embedding[graph.oppositeArc(mine)];
deba@797:           s = graph.source(mine);
deba@797:           oppe = embedding[graph.oppositeArc(oppe)];
deba@797:           typename Graph::Node t = graph.source(oppe);
deba@797: 
deba@797:           typename Graph::Arc ce = graph.direct(graph.addEdge(s, t), true);
deba@797:           embedding[ce] = mine;
deba@797:           embedding[graph.oppositeArc(ce)] = oppe;
deba@797: 
deba@797:           typename Graph::Arc pn = ce, p = oppe;
deba@797:           e = embedding[graph.oppositeArc(oppe)];
deba@797:           while (graph.target(e) != s) {
deba@797:             typename Graph::Arc n =
deba@797:               graph.direct(graph.addEdge(s, graph.source(e)), true);
deba@797: 
deba@797:             embedding[n] = pn;
deba@797:             embedding[graph.oppositeArc(n)] = e;
deba@797:             embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
deba@797: 
deba@797:             pn = n;
deba@797: 
deba@797:             p = e;
deba@797:             e = embedding[graph.oppositeArc(e)];
deba@797: 
deba@797:           }
deba@797:           embedding[graph.oppositeArc(e)] = pn;
deba@797: 
deba@797:           pn = graph.oppositeArc(ce), p = mine;
deba@797:           e = embedding[graph.oppositeArc(mine)];
deba@797:           while (graph.target(e) != t) {
deba@797:             typename Graph::Arc n =
deba@797:               graph.direct(graph.addEdge(t, graph.source(e)), true);
deba@797: 
deba@797:             embedding[n] = pn;
deba@797:             embedding[graph.oppositeArc(n)] = e;
deba@797:             embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
deba@797: 
deba@797:             pn = n;
deba@797: 
deba@797:             p = e;
deba@797:             e = embedding[graph.oppositeArc(e)];
deba@797: 
deba@797:           }
deba@797:           embedding[graph.oppositeArc(e)] = pn;
deba@797:         }
deba@797:       }
deba@797:     }
deba@797: 
deba@797:   }
deba@797: 
deba@797:   /// \ingroup planar
deba@797:   ///
deba@797:   /// \brief Schnyder's planar drawing algorithm
deba@797:   ///
deba@797:   /// The planar drawing algorithm calculates positions for the nodes
kpeter@828:   /// in the plane. These coordinates satisfy that if the edges are
kpeter@828:   /// represented with straight lines, then they will not intersect
deba@797:   /// each other.
deba@797:   ///
kpeter@828:   /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
kpeter@828:   /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
deba@797:   /// The time complexity of the algorithm is O(n).
kpeter@828:   ///
kpeter@828:   /// \see PlanarEmbedding
deba@797:   template <typename Graph>
deba@797:   class PlanarDrawing {
deba@797:   public:
deba@797: 
deba@797:     TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@797: 
kpeter@828:     /// \brief The point type for storing coordinates
deba@797:     typedef dim2::Point<int> Point;
kpeter@828:     /// \brief The map type for storing the coordinates of the nodes
deba@797:     typedef typename Graph::template NodeMap<Point> PointMap;
deba@797: 
deba@797: 
deba@797:     /// \brief Constructor
deba@797:     ///
deba@797:     /// Constructor
kpeter@828:     /// \pre The graph must be simple, i.e. it should not
kpeter@828:     /// contain parallel or loop arcs.
deba@797:     PlanarDrawing(const Graph& graph)
deba@797:       : _graph(graph), _point_map(graph) {}
deba@797: 
deba@797:   private:
deba@797: 
deba@797:     template <typename AuxGraph, typename AuxEmbeddingMap>
deba@797:     void drawing(const AuxGraph& graph,
deba@797:                  const AuxEmbeddingMap& next,
deba@797:                  PointMap& point_map) {
deba@797:       TEMPLATE_GRAPH_TYPEDEFS(AuxGraph);
deba@797: 
deba@797:       typename AuxGraph::template ArcMap<Arc> prev(graph);
deba@797: 
deba@797:       for (NodeIt n(graph); n != INVALID; ++n) {
deba@797:         Arc e = OutArcIt(graph, n);
deba@797: 
deba@797:         Arc p = e, l = e;
deba@797: 
deba@797:         e = next[e];
deba@797:         while (e != l) {
deba@797:           prev[e] = p;
deba@797:           p = e;
deba@797:           e = next[e];
deba@797:         }
deba@797:         prev[e] = p;
deba@797:       }
deba@797: 
deba@797:       Node anode, bnode, cnode;
deba@797: 
deba@797:       {
deba@797:         Arc e = ArcIt(graph);
deba@797:         anode = graph.source(e);
deba@797:         bnode = graph.target(e);
deba@797:         cnode = graph.target(next[graph.oppositeArc(e)]);
deba@797:       }
deba@797: 
deba@797:       IterableBoolMap<AuxGraph, Node> proper(graph, false);
deba@797:       typename AuxGraph::template NodeMap<int> conn(graph, -1);
deba@797: 
deba@797:       conn[anode] = conn[bnode] = -2;
deba@797:       {
deba@797:         for (OutArcIt e(graph, anode); e != INVALID; ++e) {
deba@797:           Node m = graph.target(e);
deba@797:           if (conn[m] == -1) {
deba@797:             conn[m] = 1;
deba@797:           }
deba@797:         }
deba@797:         conn[cnode] = 2;
deba@797: 
deba@797:         for (OutArcIt e(graph, bnode); e != INVALID; ++e) {
deba@797:           Node m = graph.target(e);
deba@797:           if (conn[m] == -1) {
deba@797:             conn[m] = 1;
deba@797:           } else if (conn[m] != -2) {
deba@797:             conn[m] += 1;
deba@797:             Arc pe = graph.oppositeArc(e);
deba@797:             if (conn[graph.target(next[pe])] == -2) {
deba@797:               conn[m] -= 1;
deba@797:             }
deba@797:             if (conn[graph.target(prev[pe])] == -2) {
deba@797:               conn[m] -= 1;
deba@797:             }
deba@797: 
deba@797:             proper.set(m, conn[m] == 1);
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797: 
deba@797:       typename AuxGraph::template ArcMap<int> angle(graph, -1);
deba@797: 
deba@797:       while (proper.trueNum() != 0) {
deba@797:         Node n = typename IterableBoolMap<AuxGraph, Node>::TrueIt(proper);
deba@797:         proper.set(n, false);
deba@797:         conn[n] = -2;
deba@797: 
deba@797:         for (OutArcIt e(graph, n); e != INVALID; ++e) {
deba@797:           Node m = graph.target(e);
deba@797:           if (conn[m] == -1) {
deba@797:             conn[m] = 1;
deba@797:           } else if (conn[m] != -2) {
deba@797:             conn[m] += 1;
deba@797:             Arc pe = graph.oppositeArc(e);
deba@797:             if (conn[graph.target(next[pe])] == -2) {
deba@797:               conn[m] -= 1;
deba@797:             }
deba@797:             if (conn[graph.target(prev[pe])] == -2) {
deba@797:               conn[m] -= 1;
deba@797:             }
deba@797: 
deba@797:             proper.set(m, conn[m] == 1);
deba@797:           }
deba@797:         }
deba@797: 
deba@797:         {
deba@797:           Arc e = OutArcIt(graph, n);
deba@797:           Arc p = e, l = e;
deba@797: 
deba@797:           e = next[e];
deba@797:           while (e != l) {
deba@797: 
deba@797:             if (conn[graph.target(e)] == -2 && conn[graph.target(p)] == -2) {
deba@797:               Arc f = e;
deba@797:               angle[f] = 0;
deba@797:               f = next[graph.oppositeArc(f)];
deba@797:               angle[f] = 1;
deba@797:               f = next[graph.oppositeArc(f)];
deba@797:               angle[f] = 2;
deba@797:             }
deba@797: 
deba@797:             p = e;
deba@797:             e = next[e];
deba@797:           }
deba@797: 
deba@797:           if (conn[graph.target(e)] == -2 && conn[graph.target(p)] == -2) {
deba@797:             Arc f = e;
deba@797:             angle[f] = 0;
deba@797:             f = next[graph.oppositeArc(f)];
deba@797:             angle[f] = 1;
deba@797:             f = next[graph.oppositeArc(f)];
deba@797:             angle[f] = 2;
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       typename AuxGraph::template NodeMap<Node> apred(graph, INVALID);
deba@797:       typename AuxGraph::template NodeMap<Node> bpred(graph, INVALID);
deba@797:       typename AuxGraph::template NodeMap<Node> cpred(graph, INVALID);
deba@797: 
deba@797:       typename AuxGraph::template NodeMap<int> apredid(graph, -1);
deba@797:       typename AuxGraph::template NodeMap<int> bpredid(graph, -1);
deba@797:       typename AuxGraph::template NodeMap<int> cpredid(graph, -1);
deba@797: 
deba@797:       for (ArcIt e(graph); e != INVALID; ++e) {
deba@797:         if (angle[e] == angle[next[e]]) {
deba@797:           switch (angle[e]) {
deba@797:           case 2:
deba@797:             apred[graph.target(e)] = graph.source(e);
deba@797:             apredid[graph.target(e)] = graph.id(graph.source(e));
deba@797:             break;
deba@797:           case 1:
deba@797:             bpred[graph.target(e)] = graph.source(e);
deba@797:             bpredid[graph.target(e)] = graph.id(graph.source(e));
deba@797:             break;
deba@797:           case 0:
deba@797:             cpred[graph.target(e)] = graph.source(e);
deba@797:             cpredid[graph.target(e)] = graph.id(graph.source(e));
deba@797:             break;
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       cpred[anode] = INVALID;
deba@797:       cpred[bnode] = INVALID;
deba@797: 
deba@797:       std::vector<Node> aorder, border, corder;
deba@797: 
deba@797:       {
deba@797:         typename AuxGraph::template NodeMap<bool> processed(graph, false);
deba@797:         std::vector<Node> st;
deba@797:         for (NodeIt n(graph); n != INVALID; ++n) {
deba@797:           if (!processed[n] && n != bnode && n != cnode) {
deba@797:             st.push_back(n);
deba@797:             processed[n] = true;
deba@797:             Node m = apred[n];
deba@797:             while (m != INVALID && !processed[m]) {
deba@797:               st.push_back(m);
deba@797:               processed[m] = true;
deba@797:               m = apred[m];
deba@797:             }
deba@797:             while (!st.empty()) {
deba@797:               aorder.push_back(st.back());
deba@797:               st.pop_back();
deba@797:             }
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       {
deba@797:         typename AuxGraph::template NodeMap<bool> processed(graph, false);
deba@797:         std::vector<Node> st;
deba@797:         for (NodeIt n(graph); n != INVALID; ++n) {
deba@797:           if (!processed[n] && n != cnode && n != anode) {
deba@797:             st.push_back(n);
deba@797:             processed[n] = true;
deba@797:             Node m = bpred[n];
deba@797:             while (m != INVALID && !processed[m]) {
deba@797:               st.push_back(m);
deba@797:               processed[m] = true;
deba@797:               m = bpred[m];
deba@797:             }
deba@797:             while (!st.empty()) {
deba@797:               border.push_back(st.back());
deba@797:               st.pop_back();
deba@797:             }
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       {
deba@797:         typename AuxGraph::template NodeMap<bool> processed(graph, false);
deba@797:         std::vector<Node> st;
deba@797:         for (NodeIt n(graph); n != INVALID; ++n) {
deba@797:           if (!processed[n] && n != anode && n != bnode) {
deba@797:             st.push_back(n);
deba@797:             processed[n] = true;
deba@797:             Node m = cpred[n];
deba@797:             while (m != INVALID && !processed[m]) {
deba@797:               st.push_back(m);
deba@797:               processed[m] = true;
deba@797:               m = cpred[m];
deba@797:             }
deba@797:             while (!st.empty()) {
deba@797:               corder.push_back(st.back());
deba@797:               st.pop_back();
deba@797:             }
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       typename AuxGraph::template NodeMap<int> atree(graph, 0);
deba@797:       for (int i = aorder.size() - 1; i >= 0; --i) {
deba@797:         Node n = aorder[i];
deba@797:         atree[n] = 1;
deba@797:         for (OutArcIt e(graph, n); e != INVALID; ++e) {
deba@797:           if (apred[graph.target(e)] == n) {
deba@797:             atree[n] += atree[graph.target(e)];
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       typename AuxGraph::template NodeMap<int> btree(graph, 0);
deba@797:       for (int i = border.size() - 1; i >= 0; --i) {
deba@797:         Node n = border[i];
deba@797:         btree[n] = 1;
deba@797:         for (OutArcIt e(graph, n); e != INVALID; ++e) {
deba@797:           if (bpred[graph.target(e)] == n) {
deba@797:             btree[n] += btree[graph.target(e)];
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       typename AuxGraph::template NodeMap<int> apath(graph, 0);
deba@797:       apath[bnode] = apath[cnode] = 1;
deba@797:       typename AuxGraph::template NodeMap<int> apath_btree(graph, 0);
deba@797:       apath_btree[bnode] = btree[bnode];
deba@797:       for (int i = 1; i < int(aorder.size()); ++i) {
deba@797:         Node n = aorder[i];
deba@797:         apath[n] = apath[apred[n]] + 1;
deba@797:         apath_btree[n] = btree[n] + apath_btree[apred[n]];
deba@797:       }
deba@797: 
deba@797:       typename AuxGraph::template NodeMap<int> bpath_atree(graph, 0);
deba@797:       bpath_atree[anode] = atree[anode];
deba@797:       for (int i = 1; i < int(border.size()); ++i) {
deba@797:         Node n = border[i];
deba@797:         bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
deba@797:       }
deba@797: 
deba@797:       typename AuxGraph::template NodeMap<int> cpath(graph, 0);
deba@797:       cpath[anode] = cpath[bnode] = 1;
deba@797:       typename AuxGraph::template NodeMap<int> cpath_atree(graph, 0);
deba@797:       cpath_atree[anode] = atree[anode];
deba@797:       typename AuxGraph::template NodeMap<int> cpath_btree(graph, 0);
deba@797:       cpath_btree[bnode] = btree[bnode];
deba@797:       for (int i = 1; i < int(corder.size()); ++i) {
deba@797:         Node n = corder[i];
deba@797:         cpath[n] = cpath[cpred[n]] + 1;
deba@797:         cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
deba@797:         cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
deba@797:       }
deba@797: 
deba@797:       typename AuxGraph::template NodeMap<int> third(graph);
deba@797:       for (NodeIt n(graph); n != INVALID; ++n) {
deba@797:         point_map[n].x =
deba@797:           bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
deba@797:         point_map[n].y =
deba@797:           cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
deba@797:       }
deba@797: 
deba@797:     }
deba@797: 
deba@797:   public:
deba@797: 
kpeter@828:     /// \brief Calculate the node positions
deba@797:     ///
kpeter@828:     /// This function calculates the node positions on the plane.
kpeter@828:     /// \return \c true if the graph is planar.
deba@797:     bool run() {
deba@797:       PlanarEmbedding<Graph> pe(_graph);
deba@797:       if (!pe.run()) return false;
deba@797: 
deba@1181:       run(pe.embeddingMap());
deba@797:       return true;
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Calculate the node positions according to a
deba@797:     /// combinatorical embedding
deba@797:     ///
kpeter@828:     /// This function calculates the node positions on the plane.
kpeter@828:     /// The given \c embedding map should contain a valid combinatorical
kpeter@828:     /// embedding, i.e. a valid cyclic order of the arcs.
kpeter@828:     /// It can be computed using PlanarEmbedding.
deba@797:     template <typename EmbeddingMap>
deba@797:     void run(const EmbeddingMap& embedding) {
deba@797:       typedef SmartEdgeSet<Graph> AuxGraph;
deba@797: 
deba@1182:       if (countNodes(_graph) < 3) {
deba@1182:         int y = 0;
deba@1182:         for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
deba@1182:           _point_map[n].x = 0;
deba@1182:           _point_map[n].y = y++;
deba@1182:         }
deba@1182:         return;
deba@1182:       }
deba@1182: 
deba@797:       if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {
deba@797:         drawing(_graph, embedding, _point_map);
deba@797:         return;
deba@797:       }
deba@797: 
deba@797:       AuxGraph aux_graph(_graph);
deba@797:       typename AuxGraph::template ArcMap<typename AuxGraph::Arc>
deba@797:         aux_embedding(aux_graph);
deba@797: 
deba@797:       {
deba@797: 
deba@797:         typename Graph::template EdgeMap<typename AuxGraph::Edge>
deba@797:           ref(_graph);
deba@797: 
deba@797:         for (EdgeIt e(_graph); e != INVALID; ++e) {
deba@797:           ref[e] = aux_graph.addEdge(_graph.u(e), _graph.v(e));
deba@797:         }
deba@797: 
deba@797:         for (EdgeIt e(_graph); e != INVALID; ++e) {
deba@797:           Arc ee = embedding[_graph.direct(e, true)];
deba@797:           aux_embedding[aux_graph.direct(ref[e], true)] =
deba@797:             aux_graph.direct(ref[ee], _graph.direction(ee));
deba@797:           ee = embedding[_graph.direct(e, false)];
deba@797:           aux_embedding[aux_graph.direct(ref[e], false)] =
deba@797:             aux_graph.direct(ref[ee], _graph.direction(ee));
deba@797:         }
deba@797:       }
deba@797:       _planarity_bits::makeConnected(aux_graph, aux_embedding);
deba@797:       _planarity_bits::makeBiNodeConnected(aux_graph, aux_embedding);
deba@797:       _planarity_bits::makeMaxPlanar(aux_graph, aux_embedding);
deba@797:       drawing(aux_graph, aux_embedding, _point_map);
deba@797:     }
deba@797: 
deba@797:     /// \brief The coordinate of the given node
deba@797:     ///
kpeter@828:     /// This function returns the coordinate of the given node.
deba@797:     Point operator[](const Node& node) const {
deba@797:       return _point_map[node];
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Return the grid embedding in a node map
deba@797:     ///
kpeter@828:     /// This function returns the grid embedding in a node map of
kpeter@828:     /// \c dim2::Point<int> coordinates.
deba@797:     const PointMap& coords() const {
deba@797:       return _point_map;
deba@797:     }
deba@797: 
deba@797:   private:
deba@797: 
deba@797:     const Graph& _graph;
deba@797:     PointMap _point_map;
deba@797: 
deba@797:   };
deba@797: 
deba@797:   namespace _planarity_bits {
deba@797: 
deba@797:     template <typename ColorMap>
deba@797:     class KempeFilter {
deba@797:     public:
deba@797:       typedef typename ColorMap::Key Key;
deba@797:       typedef bool Value;
deba@797: 
deba@797:       KempeFilter(const ColorMap& color_map,
deba@797:                   const typename ColorMap::Value& first,
deba@797:                   const typename ColorMap::Value& second)
deba@797:         : _color_map(color_map), _first(first), _second(second) {}
deba@797: 
deba@797:       Value operator[](const Key& key) const {
deba@797:         return _color_map[key] == _first || _color_map[key] == _second;
deba@797:       }
deba@797: 
deba@797:     private:
deba@797:       const ColorMap& _color_map;
deba@797:       typename ColorMap::Value _first, _second;
deba@797:     };
deba@797:   }
deba@797: 
deba@797:   /// \ingroup planar
deba@797:   ///
deba@797:   /// \brief Coloring planar graphs
deba@797:   ///
deba@797:   /// The graph coloring problem is the coloring of the graph nodes
kpeter@828:   /// so that there are no adjacent nodes with the same color. The
kpeter@828:   /// planar graphs can always be colored with four colors, which is
kpeter@828:   /// proved by Appel and Haken. Their proofs provide a quadratic
deba@797:   /// time algorithm for four coloring, but it could not be used to
kpeter@828:   /// implement an efficient algorithm. The five and six coloring can be
kpeter@828:   /// made in linear time, but in this class, the five coloring has
deba@797:   /// quadratic worst case time complexity. The two coloring (if
deba@797:   /// possible) is solvable with a graph search algorithm and it is
deba@797:   /// implemented in \ref bipartitePartitions() function in LEMON. To
kpeter@828:   /// decide whether a planar graph is three colorable is NP-complete.
deba@797:   ///
deba@797:   /// This class contains member functions for calculate colorings
deba@797:   /// with five and six colors. The six coloring algorithm is a simple
deba@797:   /// greedy coloring on the backward minimum outgoing order of nodes.
kpeter@828:   /// This order can be computed by selecting the node with least
kpeter@828:   /// outgoing arcs to unprocessed nodes in each phase. This order
deba@797:   /// guarantees that when a node is chosen for coloring it has at
deba@797:   /// most five already colored adjacents. The five coloring algorithm
deba@797:   /// use the same method, but if the greedy approach fails to color
deba@797:   /// with five colors, i.e. the node has five already different
deba@797:   /// colored neighbours, it swaps the colors in one of the connected
deba@797:   /// two colored sets with the Kempe recoloring method.
deba@797:   template <typename Graph>
deba@797:   class PlanarColoring {
deba@797:   public:
deba@797: 
deba@797:     TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@797: 
kpeter@828:     /// \brief The map type for storing color indices
deba@797:     typedef typename Graph::template NodeMap<int> IndexMap;
kpeter@828:     /// \brief The map type for storing colors
kpeter@828:     ///
kpeter@828:     /// The map type for storing colors.
kpeter@828:     /// \see Palette, Color
deba@797:     typedef ComposeMap<Palette, IndexMap> ColorMap;
deba@797: 
deba@797:     /// \brief Constructor
deba@797:     ///
kpeter@828:     /// Constructor.
kpeter@828:     /// \pre The graph must be simple, i.e. it should not
kpeter@828:     /// contain parallel or loop arcs.
deba@797:     PlanarColoring(const Graph& graph)
deba@797:       : _graph(graph), _color_map(graph), _palette(0) {
deba@797:       _palette.add(Color(1,0,0));
deba@797:       _palette.add(Color(0,1,0));
deba@797:       _palette.add(Color(0,0,1));
deba@797:       _palette.add(Color(1,1,0));
deba@797:       _palette.add(Color(1,0,1));
deba@797:       _palette.add(Color(0,1,1));
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Return the node map of color indices
deba@797:     ///
kpeter@828:     /// This function returns the node map of color indices. The values are
kpeter@828:     /// in the range \c [0..4] or \c [0..5] according to the coloring method.
deba@797:     IndexMap colorIndexMap() const {
deba@797:       return _color_map;
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Return the node map of colors
deba@797:     ///
kpeter@828:     /// This function returns the node map of colors. The values are among
kpeter@828:     /// five or six distinct \ref lemon::Color "colors".
deba@797:     ColorMap colorMap() const {
deba@797:       return composeMap(_palette, _color_map);
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Return the color index of the node
deba@797:     ///
kpeter@828:     /// This function returns the color index of the given node. The value is
kpeter@828:     /// in the range \c [0..4] or \c [0..5] according to the coloring method.
deba@797:     int colorIndex(const Node& node) const {
deba@797:       return _color_map[node];
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Return the color of the node
deba@797:     ///
kpeter@828:     /// This function returns the color of the given node. The value is among
kpeter@828:     /// five or six distinct \ref lemon::Color "colors".
deba@797:     Color color(const Node& node) const {
deba@797:       return _palette[_color_map[node]];
deba@797:     }
deba@797: 
deba@797: 
kpeter@828:     /// \brief Calculate a coloring with at most six colors
deba@797:     ///
deba@797:     /// This function calculates a coloring with at most six colors. The time
deba@797:     /// complexity of this variant is linear in the size of the graph.
kpeter@828:     /// \return \c true if the algorithm could color the graph with six colors.
kpeter@828:     /// If the algorithm fails, then the graph is not planar.
kpeter@828:     /// \note This function can return \c true if the graph is not
kpeter@828:     /// planar, but it can be colored with at most six colors.
deba@797:     bool runSixColoring() {
deba@797: 
deba@797:       typename Graph::template NodeMap<int> heap_index(_graph, -1);
deba@797:       BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
deba@797: 
deba@797:       for (NodeIt n(_graph); n != INVALID; ++n) {
deba@797:         _color_map[n] = -2;
deba@797:         heap.push(n, countOutArcs(_graph, n));
deba@797:       }
deba@797: 
deba@797:       std::vector<Node> order;
deba@797: 
deba@797:       while (!heap.empty()) {
deba@797:         Node n = heap.top();
deba@797:         heap.pop();
deba@797:         _color_map[n] = -1;
deba@797:         order.push_back(n);
deba@797:         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
deba@797:           Node t = _graph.runningNode(e);
deba@797:           if (_color_map[t] == -2) {
deba@797:             heap.decrease(t, heap[t] - 1);
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       for (int i = order.size() - 1; i >= 0; --i) {
deba@797:         std::vector<bool> forbidden(6, false);
deba@797:         for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {
deba@797:           Node t = _graph.runningNode(e);
deba@797:           if (_color_map[t] != -1) {
deba@797:             forbidden[_color_map[t]] = true;
deba@797:           }
deba@797:         }
deba@797:                for (int k = 0; k < 6; ++k) {
deba@797:           if (!forbidden[k]) {
deba@797:             _color_map[order[i]] = k;
deba@797:             break;
deba@797:           }
deba@797:         }
deba@797:         if (_color_map[order[i]] == -1) {
deba@797:           return false;
deba@797:         }
deba@797:       }
deba@797:       return true;
deba@797:     }
deba@797: 
deba@797:   private:
deba@797: 
deba@797:     bool recolor(const Node& u, const Node& v) {
deba@797:       int ucolor = _color_map[u];
deba@797:       int vcolor = _color_map[v];
deba@797:       typedef _planarity_bits::KempeFilter<IndexMap> KempeFilter;
deba@797:       KempeFilter filter(_color_map, ucolor, vcolor);
deba@797: 
deba@797:       typedef FilterNodes<const Graph, const KempeFilter> KempeGraph;
deba@797:       KempeGraph kempe_graph(_graph, filter);
deba@797: 
deba@797:       std::vector<Node> comp;
deba@797:       Bfs<KempeGraph> bfs(kempe_graph);
deba@797:       bfs.init();
deba@797:       bfs.addSource(u);
deba@797:       while (!bfs.emptyQueue()) {
deba@797:         Node n = bfs.nextNode();
deba@797:         if (n == v) return false;
deba@797:         comp.push_back(n);
deba@797:         bfs.processNextNode();
deba@797:       }
deba@797: 
deba@797:       int scolor = ucolor + vcolor;
deba@797:       for (int i = 0; i < static_cast<int>(comp.size()); ++i) {
deba@797:         _color_map[comp[i]] = scolor - _color_map[comp[i]];
deba@797:       }
deba@797: 
deba@797:       return true;
deba@797:     }
deba@797: 
deba@797:     template <typename EmbeddingMap>
deba@797:     void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) {
deba@797:       std::vector<Node> nodes;
deba@797:       nodes.reserve(4);
deba@797: 
deba@797:       for (Arc e = OutArcIt(_graph, node); e != INVALID; e = embedding[e]) {
deba@797:         Node t = _graph.target(e);
deba@797:         if (_color_map[t] != -1) {
deba@797:           nodes.push_back(t);
deba@797:           if (nodes.size() == 4) break;
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       int color = _color_map[nodes[0]];
deba@797:       if (recolor(nodes[0], nodes[2])) {
deba@797:         _color_map[node] = color;
deba@797:       } else {
deba@797:         color = _color_map[nodes[1]];
deba@797:         recolor(nodes[1], nodes[3]);
deba@797:         _color_map[node] = color;
deba@797:       }
deba@797:     }
deba@797: 
deba@797:   public:
deba@797: 
kpeter@828:     /// \brief Calculate a coloring with at most five colors
deba@797:     ///
deba@797:     /// This function calculates a coloring with at most five
deba@797:     /// colors. The worst case time complexity of this variant is
deba@797:     /// quadratic in the size of the graph.
kpeter@828:     /// \param embedding This map should contain a valid combinatorical
kpeter@828:     /// embedding, i.e. a valid cyclic order of the arcs.
kpeter@828:     /// It can be computed using PlanarEmbedding.
deba@797:     template <typename EmbeddingMap>
deba@797:     void runFiveColoring(const EmbeddingMap& embedding) {
deba@797: 
deba@797:       typename Graph::template NodeMap<int> heap_index(_graph, -1);
deba@797:       BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
deba@797: 
deba@797:       for (NodeIt n(_graph); n != INVALID; ++n) {
deba@797:         _color_map[n] = -2;
deba@797:         heap.push(n, countOutArcs(_graph, n));
deba@797:       }
deba@797: 
deba@797:       std::vector<Node> order;
deba@797: 
deba@797:       while (!heap.empty()) {
deba@797:         Node n = heap.top();
deba@797:         heap.pop();
deba@797:         _color_map[n] = -1;
deba@797:         order.push_back(n);
deba@797:         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
deba@797:           Node t = _graph.runningNode(e);
deba@797:           if (_color_map[t] == -2) {
deba@797:             heap.decrease(t, heap[t] - 1);
deba@797:           }
deba@797:         }
deba@797:       }
deba@797: 
deba@797:       for (int i = order.size() - 1; i >= 0; --i) {
deba@797:         std::vector<bool> forbidden(5, false);
deba@797:         for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {
deba@797:           Node t = _graph.runningNode(e);
deba@797:           if (_color_map[t] != -1) {
deba@797:             forbidden[_color_map[t]] = true;
deba@797:           }
deba@797:         }
deba@797:         for (int k = 0; k < 5; ++k) {
deba@797:           if (!forbidden[k]) {
deba@797:             _color_map[order[i]] = k;
deba@797:             break;
deba@797:           }
deba@797:         }
deba@797:         if (_color_map[order[i]] == -1) {
deba@797:           kempeRecoloring(order[i], embedding);
deba@797:         }
deba@797:       }
deba@797:     }
deba@797: 
kpeter@828:     /// \brief Calculate a coloring with at most five colors
deba@797:     ///
deba@797:     /// This function calculates a coloring with at most five
deba@797:     /// colors. The worst case time complexity of this variant is
deba@797:     /// quadratic in the size of the graph.
kpeter@828:     /// \return \c true if the graph is planar.
deba@797:     bool runFiveColoring() {
deba@797:       PlanarEmbedding<Graph> pe(_graph);
deba@797:       if (!pe.run()) return false;
deba@797: 
deba@797:       runFiveColoring(pe.embeddingMap());
deba@797:       return true;
deba@797:     }
deba@797: 
deba@797:   private:
deba@797: 
deba@797:     const Graph& _graph;
deba@797:     IndexMap _color_map;
deba@797:     Palette _palette;
deba@797:   };
deba@797: 
deba@797: }
deba@797: 
deba@797: #endif