COIN-OR::LEMON - Graph Library

Changeset 798:58c330ad0b5c in lemon-1.2


Ignore:
Timestamp:
10/04/09 10:15:32 (14 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Planarity checking function instead of class (#62)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/planarity.h

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

    r797 r798  
    240240
    241241    PE pe(graph);
    242     if (pe.run()) {
     242    bool planar = pe.run();
     243    check(checkPlanarity(graph) == planar, "Planarity checking failed");
     244
     245    if (planar) {
    243246      checkEmbedding(graph, pe);
    244247
    245248      PlanarDrawing<Graph> pd(graph);
    246       pd.run(pe.embedding());
     249      pd.run(pe.embeddingMap());
    247250      checkDrawing(graph, pd);
    248251
    249252      PlanarColoring<Graph> pc(graph);
    250       pc.runFiveColoring(pe.embedding());
     253      pc.runFiveColoring(pe.embeddingMap());
    251254      checkColoring(graph, pc, 5);
    252255
Note: See TracChangeset for help on using the changeset viewer.