lemon/planarity.h
author Alpar Juttner <alpar@cs.elte.hu>
Sat, 25 May 2013 06:59:31 +0200
changeset 1064 fc3854d936f7
parent 877 141f9c0db4a3
child 1092 dceba191c00d
permissions -rw-r--r--
Enable/disable options for LP/MIP backends (#465)
deba@797
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@797
     2
 *
deba@797
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@797
     4
 *
alpar@877
     5
 * Copyright (C) 2003-2010
deba@797
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@797
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@797
     8
 *
deba@797
     9
 * Permission to use, modify and distribute this software is granted
deba@797
    10
 * provided that this copyright notice appears in all copies. For
deba@797
    11
 * precise terms see the accompanying LICENSE file.
deba@797
    12
 *
deba@797
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@797
    14
 * express or implied, and with no claim as to its suitability for any
deba@797
    15
 * purpose.
deba@797
    16
 *
deba@797
    17
 */
deba@797
    18
deba@797
    19
#ifndef LEMON_PLANARITY_H
deba@797
    20
#define LEMON_PLANARITY_H
deba@797
    21
deba@797
    22
/// \ingroup planar
deba@797
    23
/// \file
deba@797
    24
/// \brief Planarity checking, embedding, drawing and coloring
deba@797
    25
deba@797
    26
#include <vector>
deba@797
    27
#include <list>
deba@797
    28
deba@797
    29
#include <lemon/dfs.h>
deba@797
    30
#include <lemon/bfs.h>
deba@797
    31
#include <lemon/radix_sort.h>
deba@797
    32
#include <lemon/maps.h>
deba@797
    33
#include <lemon/path.h>
deba@797
    34
#include <lemon/bucket_heap.h>
deba@797
    35
#include <lemon/adaptors.h>
deba@797
    36
#include <lemon/edge_set.h>
deba@797
    37
#include <lemon/color.h>
deba@797
    38
#include <lemon/dim2.h>
deba@797
    39
deba@797
    40
namespace lemon {
deba@797
    41
deba@797
    42
  namespace _planarity_bits {
deba@797
    43
deba@797
    44
    template <typename Graph>
deba@797
    45
    struct PlanarityVisitor : DfsVisitor<Graph> {
deba@797
    46
deba@797
    47
      TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@797
    48
deba@797
    49
      typedef typename Graph::template NodeMap<Arc> PredMap;
deba@797
    50
deba@797
    51
      typedef typename Graph::template EdgeMap<bool> TreeMap;
deba@797
    52
deba@797
    53
      typedef typename Graph::template NodeMap<int> OrderMap;
deba@797
    54
      typedef std::vector<Node> OrderList;
deba@797
    55
deba@797
    56
      typedef typename Graph::template NodeMap<int> LowMap;
deba@797
    57
      typedef typename Graph::template NodeMap<int> AncestorMap;
deba@797
    58
deba@797
    59
      PlanarityVisitor(const Graph& graph,
deba@797
    60
                       PredMap& pred_map, TreeMap& tree_map,
deba@797
    61
                       OrderMap& order_map, OrderList& order_list,
deba@797
    62
                       AncestorMap& ancestor_map, LowMap& low_map)
deba@797
    63
        : _graph(graph), _pred_map(pred_map), _tree_map(tree_map),
deba@797
    64
          _order_map(order_map), _order_list(order_list),
deba@797
    65
          _ancestor_map(ancestor_map), _low_map(low_map) {}
deba@797
    66
deba@797
    67
      void reach(const Node& node) {
deba@797
    68
        _order_map[node] = _order_list.size();
deba@797
    69
        _low_map[node] = _order_list.size();
deba@797
    70
        _ancestor_map[node] = _order_list.size();
deba@797
    71
        _order_list.push_back(node);
deba@797
    72
      }
deba@797
    73
deba@797
    74
      void discover(const Arc& arc) {
deba@797
    75
        Node target = _graph.target(arc);
deba@797
    76
deba@797
    77
        _tree_map[arc] = true;
deba@797
    78
        _pred_map[target] = arc;
deba@797
    79
      }
deba@797
    80
deba@797
    81
      void examine(const Arc& arc) {
deba@797
    82
        Node source = _graph.source(arc);
deba@797
    83
        Node target = _graph.target(arc);
deba@797
    84
deba@797
    85
        if (_order_map[target] < _order_map[source] && !_tree_map[arc]) {
deba@797
    86
          if (_low_map[source] > _order_map[target]) {
deba@797
    87
            _low_map[source] = _order_map[target];
deba@797
    88
          }
deba@797
    89
          if (_ancestor_map[source] > _order_map[target]) {
deba@797
    90
            _ancestor_map[source] = _order_map[target];
deba@797
    91
          }
deba@797
    92
        }
deba@797
    93
      }
deba@797
    94
deba@797
    95
      void backtrack(const Arc& arc) {
deba@797
    96
        Node source = _graph.source(arc);
deba@797
    97
        Node target = _graph.target(arc);
deba@797
    98
deba@797
    99
        if (_low_map[source] > _low_map[target]) {
deba@797
   100
          _low_map[source] = _low_map[target];
deba@797
   101
        }
deba@797
   102
      }
deba@797
   103
deba@797
   104
      const Graph& _graph;
deba@797
   105
      PredMap& _pred_map;
deba@797
   106
      TreeMap& _tree_map;
deba@797
   107
      OrderMap& _order_map;
deba@797
   108
      OrderList& _order_list;
deba@797
   109
      AncestorMap& _ancestor_map;
deba@797
   110
      LowMap& _low_map;
deba@797
   111
    };
deba@797
   112
deba@797
   113
    template <typename Graph, bool embedding = true>
deba@797
   114
    struct NodeDataNode {
deba@797
   115
      int prev, next;
deba@797
   116
      int visited;
deba@797
   117
      typename Graph::Arc first;
deba@797
   118
      bool inverted;
deba@797
   119
    };
deba@797
   120
deba@797
   121
    template <typename Graph>
deba@797
   122
    struct NodeDataNode<Graph, false> {
deba@797
   123
      int prev, next;
deba@797
   124
      int visited;
deba@797
   125
    };
deba@797
   126
deba@797
   127
    template <typename Graph>
deba@797
   128
    struct ChildListNode {
deba@797
   129
      typedef typename Graph::Node Node;
deba@797
   130
      Node first;
deba@797
   131
      Node prev, next;
deba@797
   132
    };
deba@797
   133
deba@797
   134
    template <typename Graph>
deba@797
   135
    struct ArcListNode {
deba@797
   136
      typename Graph::Arc prev, next;
deba@797
   137
    };
deba@797
   138
deba@798
   139
    template <typename Graph>
deba@798
   140
    class PlanarityChecking {
deba@798
   141
    private:
alpar@877
   142
deba@798
   143
      TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@798
   144
deba@798
   145
      const Graph& _graph;
deba@798
   146
deba@798
   147
    private:
alpar@877
   148
deba@798
   149
      typedef typename Graph::template NodeMap<Arc> PredMap;
alpar@877
   150
deba@798
   151
      typedef typename Graph::template EdgeMap<bool> TreeMap;
alpar@877
   152
deba@798
   153
      typedef typename Graph::template NodeMap<int> OrderMap;
deba@798
   154
      typedef std::vector<Node> OrderList;
deba@798
   155
deba@798
   156
      typedef typename Graph::template NodeMap<int> LowMap;
deba@798
   157
      typedef typename Graph::template NodeMap<int> AncestorMap;
deba@798
   158
deba@798
   159
      typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
deba@798
   160
      typedef std::vector<NodeDataNode> NodeData;
deba@798
   161
deba@798
   162
      typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
deba@798
   163
      typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
deba@798
   164
deba@798
   165
      typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
deba@798
   166
deba@798
   167
      typedef typename Graph::template NodeMap<bool> EmbedArc;
deba@798
   168
deba@798
   169
    public:
deba@798
   170
deba@798
   171
      PlanarityChecking(const Graph& graph) : _graph(graph) {}
deba@798
   172
deba@798
   173
      bool run() {
deba@798
   174
        typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
deba@798
   175
deba@798
   176
        PredMap pred_map(_graph, INVALID);
deba@798
   177
        TreeMap tree_map(_graph, false);
deba@798
   178
deba@798
   179
        OrderMap order_map(_graph, -1);
deba@798
   180
        OrderList order_list;
deba@798
   181
deba@798
   182
        AncestorMap ancestor_map(_graph, -1);
deba@798
   183
        LowMap low_map(_graph, -1);
deba@798
   184
deba@798
   185
        Visitor visitor(_graph, pred_map, tree_map,
deba@798
   186
                        order_map, order_list, ancestor_map, low_map);
deba@798
   187
        DfsVisit<Graph, Visitor> visit(_graph, visitor);
deba@798
   188
        visit.run();
deba@798
   189
deba@798
   190
        ChildLists child_lists(_graph);
deba@798
   191
        createChildLists(tree_map, order_map, low_map, child_lists);
deba@798
   192
deba@798
   193
        NodeData node_data(2 * order_list.size());
deba@798
   194
deba@798
   195
        EmbedArc embed_arc(_graph, false);
deba@798
   196
deba@798
   197
        MergeRoots merge_roots(_graph);
deba@798
   198
deba@798
   199
        for (int i = order_list.size() - 1; i >= 0; --i) {
deba@798
   200
deba@798
   201
          Node node = order_list[i];
deba@798
   202
deba@798
   203
          Node source = node;
deba@798
   204
          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@798
   205
            Node target = _graph.target(e);
deba@798
   206
deba@798
   207
            if (order_map[source] < order_map[target] && tree_map[e]) {
deba@798
   208
              initFace(target, node_data, order_map, order_list);
deba@798
   209
            }
deba@798
   210
          }
deba@798
   211
deba@798
   212
          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@798
   213
            Node target = _graph.target(e);
deba@798
   214
deba@798
   215
            if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@798
   216
              embed_arc[target] = true;
deba@798
   217
              walkUp(target, source, i, pred_map, low_map,
deba@798
   218
                     order_map, order_list, node_data, merge_roots);
deba@798
   219
            }
deba@798
   220
          }
deba@798
   221
deba@798
   222
          for (typename MergeRoots::Value::iterator it =
alpar@877
   223
                 merge_roots[node].begin();
deba@798
   224
               it != merge_roots[node].end(); ++it) {
deba@798
   225
            int rn = *it;
deba@798
   226
            walkDown(rn, i, node_data, order_list, child_lists,
deba@798
   227
                     ancestor_map, low_map, embed_arc, merge_roots);
deba@798
   228
          }
deba@798
   229
          merge_roots[node].clear();
deba@798
   230
deba@798
   231
          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@798
   232
            Node target = _graph.target(e);
deba@798
   233
deba@798
   234
            if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@798
   235
              if (embed_arc[target]) {
deba@798
   236
                return false;
deba@798
   237
              }
deba@798
   238
            }
deba@798
   239
          }
deba@798
   240
        }
deba@798
   241
deba@798
   242
        return true;
deba@798
   243
      }
deba@798
   244
deba@798
   245
    private:
deba@798
   246
deba@798
   247
      void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
deba@798
   248
                            const LowMap& low_map, ChildLists& child_lists) {
deba@798
   249
deba@798
   250
        for (NodeIt n(_graph); n != INVALID; ++n) {
deba@798
   251
          Node source = n;
deba@798
   252
deba@798
   253
          std::vector<Node> targets;
deba@798
   254
          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
deba@798
   255
            Node target = _graph.target(e);
deba@798
   256
deba@798
   257
            if (order_map[source] < order_map[target] && tree_map[e]) {
deba@798
   258
              targets.push_back(target);
deba@798
   259
            }
deba@798
   260
          }
deba@798
   261
deba@798
   262
          if (targets.size() == 0) {
deba@798
   263
            child_lists[source].first = INVALID;
deba@798
   264
          } else if (targets.size() == 1) {
deba@798
   265
            child_lists[source].first = targets[0];
deba@798
   266
            child_lists[targets[0]].prev = INVALID;
deba@798
   267
            child_lists[targets[0]].next = INVALID;
deba@798
   268
          } else {
deba@798
   269
            radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
deba@798
   270
            for (int i = 1; i < int(targets.size()); ++i) {
deba@798
   271
              child_lists[targets[i]].prev = targets[i - 1];
deba@798
   272
              child_lists[targets[i - 1]].next = targets[i];
deba@798
   273
            }
deba@798
   274
            child_lists[targets.back()].next = INVALID;
deba@798
   275
            child_lists[targets.front()].prev = INVALID;
deba@798
   276
            child_lists[source].first = targets.front();
deba@798
   277
          }
deba@798
   278
        }
deba@798
   279
      }
deba@798
   280
deba@798
   281
      void walkUp(const Node& node, Node root, int rorder,
deba@798
   282
                  const PredMap& pred_map, const LowMap& low_map,
deba@798
   283
                  const OrderMap& order_map, const OrderList& order_list,
deba@798
   284
                  NodeData& node_data, MergeRoots& merge_roots) {
deba@798
   285
deba@798
   286
        int na, nb;
deba@798
   287
        bool da, db;
deba@798
   288
deba@798
   289
        na = nb = order_map[node];
deba@798
   290
        da = true; db = false;
deba@798
   291
deba@798
   292
        while (true) {
deba@798
   293
deba@798
   294
          if (node_data[na].visited == rorder) break;
deba@798
   295
          if (node_data[nb].visited == rorder) break;
deba@798
   296
deba@798
   297
          node_data[na].visited = rorder;
deba@798
   298
          node_data[nb].visited = rorder;
deba@798
   299
deba@798
   300
          int rn = -1;
deba@798
   301
deba@798
   302
          if (na >= int(order_list.size())) {
deba@798
   303
            rn = na;
deba@798
   304
          } else if (nb >= int(order_list.size())) {
deba@798
   305
            rn = nb;
deba@798
   306
          }
deba@798
   307
deba@798
   308
          if (rn == -1) {
deba@798
   309
            int nn;
deba@798
   310
deba@798
   311
            nn = da ? node_data[na].prev : node_data[na].next;
deba@798
   312
            da = node_data[nn].prev != na;
deba@798
   313
            na = nn;
deba@798
   314
deba@798
   315
            nn = db ? node_data[nb].prev : node_data[nb].next;
deba@798
   316
            db = node_data[nn].prev != nb;
deba@798
   317
            nb = nn;
deba@798
   318
deba@798
   319
          } else {
deba@798
   320
deba@798
   321
            Node rep = order_list[rn - order_list.size()];
deba@798
   322
            Node parent = _graph.source(pred_map[rep]);
deba@798
   323
deba@798
   324
            if (low_map[rep] < rorder) {
deba@798
   325
              merge_roots[parent].push_back(rn);
deba@798
   326
            } else {
deba@798
   327
              merge_roots[parent].push_front(rn);
deba@798
   328
            }
deba@798
   329
deba@798
   330
            if (parent != root) {
deba@798
   331
              na = nb = order_map[parent];
deba@798
   332
              da = true; db = false;
deba@798
   333
            } else {
deba@798
   334
              break;
deba@798
   335
            }
deba@798
   336
          }
deba@798
   337
        }
deba@798
   338
      }
deba@798
   339
deba@798
   340
      void walkDown(int rn, int rorder, NodeData& node_data,
deba@798
   341
                    OrderList& order_list, ChildLists& child_lists,
deba@798
   342
                    AncestorMap& ancestor_map, LowMap& low_map,
deba@798
   343
                    EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@798
   344
deba@798
   345
        std::vector<std::pair<int, bool> > merge_stack;
deba@798
   346
deba@798
   347
        for (int di = 0; di < 2; ++di) {
deba@798
   348
          bool rd = di == 0;
deba@798
   349
          int pn = rn;
deba@798
   350
          int n = rd ? node_data[rn].next : node_data[rn].prev;
deba@798
   351
deba@798
   352
          while (n != rn) {
deba@798
   353
deba@798
   354
            Node node = order_list[n];
deba@798
   355
deba@798
   356
            if (embed_arc[node]) {
deba@798
   357
deba@798
   358
              // Merging components on the critical path
deba@798
   359
              while (!merge_stack.empty()) {
deba@798
   360
deba@798
   361
                // Component root
deba@798
   362
                int cn = merge_stack.back().first;
deba@798
   363
                bool cd = merge_stack.back().second;
deba@798
   364
                merge_stack.pop_back();
deba@798
   365
deba@798
   366
                // Parent of component
deba@798
   367
                int dn = merge_stack.back().first;
deba@798
   368
                bool dd = merge_stack.back().second;
deba@798
   369
                merge_stack.pop_back();
deba@798
   370
deba@798
   371
                Node parent = order_list[dn];
deba@798
   372
deba@798
   373
                // Erasing from merge_roots
deba@798
   374
                merge_roots[parent].pop_front();
deba@798
   375
deba@798
   376
                Node child = order_list[cn - order_list.size()];
deba@798
   377
deba@798
   378
                // Erasing from child_lists
deba@798
   379
                if (child_lists[child].prev != INVALID) {
deba@798
   380
                  child_lists[child_lists[child].prev].next =
deba@798
   381
                    child_lists[child].next;
deba@798
   382
                } else {
deba@798
   383
                  child_lists[parent].first = child_lists[child].next;
deba@798
   384
                }
deba@798
   385
deba@798
   386
                if (child_lists[child].next != INVALID) {
deba@798
   387
                  child_lists[child_lists[child].next].prev =
deba@798
   388
                    child_lists[child].prev;
deba@798
   389
                }
deba@798
   390
deba@798
   391
                // Merging external faces
deba@798
   392
                {
deba@798
   393
                  int en = cn;
deba@798
   394
                  cn = cd ? node_data[cn].prev : node_data[cn].next;
deba@798
   395
                  cd = node_data[cn].next == en;
deba@798
   396
deba@798
   397
                }
deba@798
   398
deba@798
   399
                if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
deba@798
   400
                if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
deba@798
   401
deba@798
   402
              }
deba@798
   403
deba@798
   404
              bool d = pn == node_data[n].prev;
deba@798
   405
deba@798
   406
              if (node_data[n].prev == node_data[n].next &&
deba@798
   407
                  node_data[n].inverted) {
deba@798
   408
                d = !d;
deba@798
   409
              }
deba@798
   410
deba@798
   411
              // Embedding arc into external face
deba@798
   412
              if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
deba@798
   413
              if (d) node_data[n].prev = rn; else node_data[n].next = rn;
deba@798
   414
              pn = rn;
deba@798
   415
deba@798
   416
              embed_arc[order_list[n]] = false;
deba@798
   417
            }
deba@798
   418
deba@798
   419
            if (!merge_roots[node].empty()) {
deba@798
   420
deba@798
   421
              bool d = pn == node_data[n].prev;
deba@798
   422
deba@798
   423
              merge_stack.push_back(std::make_pair(n, d));
deba@798
   424
deba@798
   425
              int rn = merge_roots[node].front();
deba@798
   426
deba@798
   427
              int xn = node_data[rn].next;
deba@798
   428
              Node xnode = order_list[xn];
deba@798
   429
deba@798
   430
              int yn = node_data[rn].prev;
deba@798
   431
              Node ynode = order_list[yn];
deba@798
   432
deba@798
   433
              bool rd;
alpar@877
   434
              if (!external(xnode, rorder, child_lists,
deba@798
   435
                            ancestor_map, low_map)) {
deba@798
   436
                rd = true;
deba@798
   437
              } else if (!external(ynode, rorder, child_lists,
deba@798
   438
                                   ancestor_map, low_map)) {
deba@798
   439
                rd = false;
deba@798
   440
              } else if (pertinent(xnode, embed_arc, merge_roots)) {
deba@798
   441
                rd = true;
deba@798
   442
              } else {
deba@798
   443
                rd = false;
deba@798
   444
              }
deba@798
   445
deba@798
   446
              merge_stack.push_back(std::make_pair(rn, rd));
deba@798
   447
deba@798
   448
              pn = rn;
deba@798
   449
              n = rd ? xn : yn;
deba@798
   450
deba@798
   451
            } else if (!external(node, rorder, child_lists,
deba@798
   452
                                 ancestor_map, low_map)) {
deba@798
   453
              int nn = (node_data[n].next != pn ?
deba@798
   454
                        node_data[n].next : node_data[n].prev);
deba@798
   455
deba@798
   456
              bool nd = n == node_data[nn].prev;
deba@798
   457
deba@798
   458
              if (nd) node_data[nn].prev = pn;
deba@798
   459
              else node_data[nn].next = pn;
deba@798
   460
deba@798
   461
              if (n == node_data[pn].prev) node_data[pn].prev = nn;
deba@798
   462
              else node_data[pn].next = nn;
deba@798
   463
deba@798
   464
              node_data[nn].inverted =
deba@798
   465
                (node_data[nn].prev == node_data[nn].next && nd != rd);
deba@798
   466
deba@798
   467
              n = nn;
deba@798
   468
            }
deba@798
   469
            else break;
deba@798
   470
deba@798
   471
          }
deba@798
   472
deba@798
   473
          if (!merge_stack.empty() || n == rn) {
deba@798
   474
            break;
deba@798
   475
          }
deba@798
   476
        }
deba@798
   477
      }
deba@798
   478
deba@798
   479
      void initFace(const Node& node, NodeData& node_data,
deba@798
   480
                    const OrderMap& order_map, const OrderList& order_list) {
deba@798
   481
        int n = order_map[node];
deba@798
   482
        int rn = n + order_list.size();
deba@798
   483
deba@798
   484
        node_data[n].next = node_data[n].prev = rn;
deba@798
   485
        node_data[rn].next = node_data[rn].prev = n;
deba@798
   486
deba@798
   487
        node_data[n].visited = order_list.size();
deba@798
   488
        node_data[rn].visited = order_list.size();
deba@798
   489
deba@798
   490
      }
deba@798
   491
deba@798
   492
      bool external(const Node& node, int rorder,
deba@798
   493
                    ChildLists& child_lists, AncestorMap& ancestor_map,
deba@798
   494
                    LowMap& low_map) {
deba@798
   495
        Node child = child_lists[node].first;
deba@798
   496
deba@798
   497
        if (child != INVALID) {
deba@798
   498
          if (low_map[child] < rorder) return true;
deba@798
   499
        }
deba@798
   500
deba@798
   501
        if (ancestor_map[node] < rorder) return true;
deba@798
   502
deba@798
   503
        return false;
deba@798
   504
      }
deba@798
   505
deba@798
   506
      bool pertinent(const Node& node, const EmbedArc& embed_arc,
deba@798
   507
                     const MergeRoots& merge_roots) {
deba@798
   508
        return !merge_roots[node].empty() || embed_arc[node];
deba@798
   509
      }
deba@798
   510
deba@798
   511
    };
deba@798
   512
deba@797
   513
  }
deba@797
   514
deba@797
   515
  /// \ingroup planar
deba@797
   516
  ///
deba@797
   517
  /// \brief Planarity checking of an undirected simple graph
deba@797
   518
  ///
deba@798
   519
  /// This function implements the Boyer-Myrvold algorithm for
kpeter@828
   520
  /// planarity checking of an undirected simple graph. It is a simplified
deba@797
   521
  /// version of the PlanarEmbedding algorithm class because neither
kpeter@828
   522
  /// the embedding nor the Kuratowski subdivisons are computed.
deba@798
   523
  template <typename GR>
deba@798
   524
  bool checkPlanarity(const GR& graph) {
deba@798
   525
    _planarity_bits::PlanarityChecking<GR> pc(graph);
deba@798
   526
    return pc.run();
deba@798
   527
  }
deba@797
   528
deba@797
   529
  /// \ingroup planar
deba@797
   530
  ///
deba@797
   531
  /// \brief Planar embedding of an undirected simple graph
deba@797
   532
  ///
deba@797
   533
  /// This class implements the Boyer-Myrvold algorithm for planar
kpeter@828
   534
  /// embedding of an undirected simple graph. The planar embedding is an
deba@797
   535
  /// ordering of the outgoing edges of the nodes, which is a possible
deba@797
   536
  /// configuration to draw the graph in the plane. If there is not
kpeter@828
   537
  /// such ordering then the graph contains a K<sub>5</sub> (full graph
kpeter@828
   538
  /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
kpeter@828
   539
  /// 3 Red and 3 Blue nodes) subdivision.
deba@797
   540
  ///
deba@797
   541
  /// The current implementation calculates either an embedding or a
kpeter@828
   542
  /// Kuratowski subdivision. The running time of the algorithm is O(n).
kpeter@828
   543
  ///
kpeter@828
   544
  /// \see PlanarDrawing, checkPlanarity()
deba@797
   545
  template <typename Graph>
deba@797
   546
  class PlanarEmbedding {
deba@797
   547
  private:
deba@797
   548
deba@797
   549
    TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@797
   550
deba@797
   551
    const Graph& _graph;
deba@797
   552
    typename Graph::template ArcMap<Arc> _embedding;
deba@797
   553
deba@797
   554
    typename Graph::template EdgeMap<bool> _kuratowski;
deba@797
   555
deba@797
   556
  private:
deba@797
   557
deba@797
   558
    typedef typename Graph::template NodeMap<Arc> PredMap;
deba@797
   559
deba@797
   560
    typedef typename Graph::template EdgeMap<bool> TreeMap;
deba@797
   561
deba@797
   562
    typedef typename Graph::template NodeMap<int> OrderMap;
deba@797
   563
    typedef std::vector<Node> OrderList;
deba@797
   564
deba@797
   565
    typedef typename Graph::template NodeMap<int> LowMap;
deba@797
   566
    typedef typename Graph::template NodeMap<int> AncestorMap;
deba@797
   567
deba@797
   568
    typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
deba@797
   569
    typedef std::vector<NodeDataNode> NodeData;
deba@797
   570
deba@797
   571
    typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
deba@797
   572
    typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
deba@797
   573
deba@797
   574
    typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
deba@797
   575
deba@797
   576
    typedef typename Graph::template NodeMap<Arc> EmbedArc;
deba@797
   577
deba@797
   578
    typedef _planarity_bits::ArcListNode<Graph> ArcListNode;
deba@797
   579
    typedef typename Graph::template ArcMap<ArcListNode> ArcLists;
deba@797
   580
deba@797
   581
    typedef typename Graph::template NodeMap<bool> FlipMap;
deba@797
   582
deba@797
   583
    typedef typename Graph::template NodeMap<int> TypeMap;
deba@797
   584
deba@797
   585
    enum IsolatorNodeType {
deba@797
   586
      HIGHX = 6, LOWX = 7,
deba@797
   587
      HIGHY = 8, LOWY = 9,
deba@797
   588
      ROOT = 10, PERTINENT = 11,
deba@797
   589
      INTERNAL = 12
deba@797
   590
    };
deba@797
   591
deba@797
   592
  public:
deba@797
   593
kpeter@828
   594
    /// \brief The map type for storing the embedding
kpeter@828
   595
    ///
kpeter@828
   596
    /// The map type for storing the embedding.
kpeter@828
   597
    /// \see embeddingMap()
deba@797
   598
    typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
deba@797
   599
deba@797
   600
    /// \brief Constructor
deba@797
   601
    ///
kpeter@828
   602
    /// Constructor.
kpeter@828
   603
    /// \pre The graph must be simple, i.e. it should not
kpeter@828
   604
    /// contain parallel or loop arcs.
deba@797
   605
    PlanarEmbedding(const Graph& graph)
deba@797
   606
      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
deba@797
   607
kpeter@828
   608
    /// \brief Run the algorithm.
deba@797
   609
    ///
kpeter@828
   610
    /// This function runs the algorithm.
kpeter@828
   611
    /// \param kuratowski If this parameter is set to \c false, then the
deba@797
   612
    /// algorithm does not compute a Kuratowski subdivision.
kpeter@828
   613
    /// \return \c true if the graph is planar.
deba@797
   614
    bool run(bool kuratowski = true) {
deba@797
   615
      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
deba@797
   616
deba@797
   617
      PredMap pred_map(_graph, INVALID);
deba@797
   618
      TreeMap tree_map(_graph, false);
deba@797
   619
deba@797
   620
      OrderMap order_map(_graph, -1);
deba@797
   621
      OrderList order_list;
deba@797
   622
deba@797
   623
      AncestorMap ancestor_map(_graph, -1);
deba@797
   624
      LowMap low_map(_graph, -1);
deba@797
   625
deba@797
   626
      Visitor visitor(_graph, pred_map, tree_map,
deba@797
   627
                      order_map, order_list, ancestor_map, low_map);
deba@797
   628
      DfsVisit<Graph, Visitor> visit(_graph, visitor);
deba@797
   629
      visit.run();
deba@797
   630
deba@797
   631
      ChildLists child_lists(_graph);
deba@797
   632
      createChildLists(tree_map, order_map, low_map, child_lists);
deba@797
   633
deba@797
   634
      NodeData node_data(2 * order_list.size());
deba@797
   635
deba@797
   636
      EmbedArc embed_arc(_graph, INVALID);
deba@797
   637
deba@797
   638
      MergeRoots merge_roots(_graph);
deba@797
   639
deba@797
   640
      ArcLists arc_lists(_graph);
deba@797
   641
deba@797
   642
      FlipMap flip_map(_graph, false);
deba@797
   643
deba@797
   644
      for (int i = order_list.size() - 1; i >= 0; --i) {
deba@797
   645
deba@797
   646
        Node node = order_list[i];
deba@797
   647
deba@797
   648
        node_data[i].first = INVALID;
deba@797
   649
deba@797
   650
        Node source = node;
deba@797
   651
        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797
   652
          Node target = _graph.target(e);
deba@797
   653
deba@797
   654
          if (order_map[source] < order_map[target] && tree_map[e]) {
deba@797
   655
            initFace(target, arc_lists, node_data,
deba@797
   656
                     pred_map, order_map, order_list);
deba@797
   657
          }
deba@797
   658
        }
deba@797
   659
deba@797
   660
        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797
   661
          Node target = _graph.target(e);
deba@797
   662
deba@797
   663
          if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@797
   664
            embed_arc[target] = e;
deba@797
   665
            walkUp(target, source, i, pred_map, low_map,
deba@797
   666
                   order_map, order_list, node_data, merge_roots);
deba@797
   667
          }
deba@797
   668
        }
deba@797
   669
deba@797
   670
        for (typename MergeRoots::Value::iterator it =
deba@797
   671
               merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
deba@797
   672
          int rn = *it;
deba@797
   673
          walkDown(rn, i, node_data, arc_lists, flip_map, order_list,
deba@797
   674
                   child_lists, ancestor_map, low_map, embed_arc, merge_roots);
deba@797
   675
        }
deba@797
   676
        merge_roots[node].clear();
deba@797
   677
deba@797
   678
        for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797
   679
          Node target = _graph.target(e);
deba@797
   680
deba@797
   681
          if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@797
   682
            if (embed_arc[target] != INVALID) {
deba@797
   683
              if (kuratowski) {
deba@797
   684
                isolateKuratowski(e, node_data, arc_lists, flip_map,
deba@797
   685
                                  order_map, order_list, pred_map, child_lists,
deba@797
   686
                                  ancestor_map, low_map,
deba@797
   687
                                  embed_arc, merge_roots);
deba@797
   688
              }
deba@797
   689
              return false;
deba@797
   690
            }
deba@797
   691
          }
deba@797
   692
        }
deba@797
   693
      }
deba@797
   694
deba@797
   695
      for (int i = 0; i < int(order_list.size()); ++i) {
deba@797
   696
deba@797
   697
        mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
deba@797
   698
                            child_lists, arc_lists);
deba@797
   699
        storeEmbedding(order_list[i], node_data, order_map, pred_map,
deba@797
   700
                       arc_lists, flip_map);
deba@797
   701
      }
deba@797
   702
deba@797
   703
      return true;
deba@797
   704
    }
deba@797
   705
kpeter@828
   706
    /// \brief Give back the successor of an arc
deba@797
   707
    ///
kpeter@828
   708
    /// This function gives back the successor of an arc. It makes
deba@797
   709
    /// possible to query the cyclic order of the outgoing arcs from
deba@797
   710
    /// a node.
deba@797
   711
    Arc next(const Arc& arc) const {
deba@797
   712
      return _embedding[arc];
deba@797
   713
    }
deba@797
   714
kpeter@828
   715
    /// \brief Give back the calculated embedding map
deba@797
   716
    ///
kpeter@828
   717
    /// This function gives back the calculated embedding map, which
kpeter@828
   718
    /// contains the successor of each arc in the cyclic order of the
kpeter@828
   719
    /// outgoing arcs of its source node.
deba@798
   720
    const EmbeddingMap& embeddingMap() const {
deba@797
   721
      return _embedding;
deba@797
   722
    }
deba@797
   723
kpeter@828
   724
    /// \brief Give back \c true if the given edge is in the Kuratowski
kpeter@828
   725
    /// subdivision
deba@797
   726
    ///
kpeter@828
   727
    /// This function gives back \c true if the given edge is in the found
kpeter@828
   728
    /// Kuratowski subdivision.
kpeter@828
   729
    /// \pre The \c run() function must be called with \c true parameter
kpeter@828
   730
    /// before using this function.
kpeter@828
   731
    bool kuratowski(const Edge& edge) const {
deba@797
   732
      return _kuratowski[edge];
deba@797
   733
    }
deba@797
   734
deba@797
   735
  private:
deba@797
   736
deba@797
   737
    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
deba@797
   738
                          const LowMap& low_map, ChildLists& child_lists) {
deba@797
   739
deba@797
   740
      for (NodeIt n(_graph); n != INVALID; ++n) {
deba@797
   741
        Node source = n;
deba@797
   742
deba@797
   743
        std::vector<Node> targets;
deba@797
   744
        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
deba@797
   745
          Node target = _graph.target(e);
deba@797
   746
deba@797
   747
          if (order_map[source] < order_map[target] && tree_map[e]) {
deba@797
   748
            targets.push_back(target);
deba@797
   749
          }
deba@797
   750
        }
deba@797
   751
deba@797
   752
        if (targets.size() == 0) {
deba@797
   753
          child_lists[source].first = INVALID;
deba@797
   754
        } else if (targets.size() == 1) {
deba@797
   755
          child_lists[source].first = targets[0];
deba@797
   756
          child_lists[targets[0]].prev = INVALID;
deba@797
   757
          child_lists[targets[0]].next = INVALID;
deba@797
   758
        } else {
deba@797
   759
          radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
deba@797
   760
          for (int i = 1; i < int(targets.size()); ++i) {
deba@797
   761
            child_lists[targets[i]].prev = targets[i - 1];
deba@797
   762
            child_lists[targets[i - 1]].next = targets[i];
deba@797
   763
          }
deba@797
   764
          child_lists[targets.back()].next = INVALID;
deba@797
   765
          child_lists[targets.front()].prev = INVALID;
deba@797
   766
          child_lists[source].first = targets.front();
deba@797
   767
        }
deba@797
   768
      }
deba@797
   769
    }
deba@797
   770
deba@797
   771
    void walkUp(const Node& node, Node root, int rorder,
deba@797
   772
                const PredMap& pred_map, const LowMap& low_map,
deba@797
   773
                const OrderMap& order_map, const OrderList& order_list,
deba@797
   774
                NodeData& node_data, MergeRoots& merge_roots) {
deba@797
   775
deba@797
   776
      int na, nb;
deba@797
   777
      bool da, db;
deba@797
   778
deba@797
   779
      na = nb = order_map[node];
deba@797
   780
      da = true; db = false;
deba@797
   781
deba@797
   782
      while (true) {
deba@797
   783
deba@797
   784
        if (node_data[na].visited == rorder) break;
deba@797
   785
        if (node_data[nb].visited == rorder) break;
deba@797
   786
deba@797
   787
        node_data[na].visited = rorder;
deba@797
   788
        node_data[nb].visited = rorder;
deba@797
   789
deba@797
   790
        int rn = -1;
deba@797
   791
deba@797
   792
        if (na >= int(order_list.size())) {
deba@797
   793
          rn = na;
deba@797
   794
        } else if (nb >= int(order_list.size())) {
deba@797
   795
          rn = nb;
deba@797
   796
        }
deba@797
   797
deba@797
   798
        if (rn == -1) {
deba@797
   799
          int nn;
deba@797
   800
deba@797
   801
          nn = da ? node_data[na].prev : node_data[na].next;
deba@797
   802
          da = node_data[nn].prev != na;
deba@797
   803
          na = nn;
deba@797
   804
deba@797
   805
          nn = db ? node_data[nb].prev : node_data[nb].next;
deba@797
   806
          db = node_data[nn].prev != nb;
deba@797
   807
          nb = nn;
deba@797
   808
deba@797
   809
        } else {
deba@797
   810
deba@797
   811
          Node rep = order_list[rn - order_list.size()];
deba@797
   812
          Node parent = _graph.source(pred_map[rep]);
deba@797
   813
deba@797
   814
          if (low_map[rep] < rorder) {
deba@797
   815
            merge_roots[parent].push_back(rn);
deba@797
   816
          } else {
deba@797
   817
            merge_roots[parent].push_front(rn);
deba@797
   818
          }
deba@797
   819
deba@797
   820
          if (parent != root) {
deba@797
   821
            na = nb = order_map[parent];
deba@797
   822
            da = true; db = false;
deba@797
   823
          } else {
deba@797
   824
            break;
deba@797
   825
          }
deba@797
   826
        }
deba@797
   827
      }
deba@797
   828
    }
deba@797
   829
deba@797
   830
    void walkDown(int rn, int rorder, NodeData& node_data,
deba@797
   831
                  ArcLists& arc_lists, FlipMap& flip_map,
deba@797
   832
                  OrderList& order_list, ChildLists& child_lists,
deba@797
   833
                  AncestorMap& ancestor_map, LowMap& low_map,
deba@797
   834
                  EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@797
   835
deba@797
   836
      std::vector<std::pair<int, bool> > merge_stack;
deba@797
   837
deba@797
   838
      for (int di = 0; di < 2; ++di) {
deba@797
   839
        bool rd = di == 0;
deba@797
   840
        int pn = rn;
deba@797
   841
        int n = rd ? node_data[rn].next : node_data[rn].prev;
deba@797
   842
deba@797
   843
        while (n != rn) {
deba@797
   844
deba@797
   845
          Node node = order_list[n];
deba@797
   846
deba@797
   847
          if (embed_arc[node] != INVALID) {
deba@797
   848
deba@797
   849
            // Merging components on the critical path
deba@797
   850
            while (!merge_stack.empty()) {
deba@797
   851
deba@797
   852
              // Component root
deba@797
   853
              int cn = merge_stack.back().first;
deba@797
   854
              bool cd = merge_stack.back().second;
deba@797
   855
              merge_stack.pop_back();
deba@797
   856
deba@797
   857
              // Parent of component
deba@797
   858
              int dn = merge_stack.back().first;
deba@797
   859
              bool dd = merge_stack.back().second;
deba@797
   860
              merge_stack.pop_back();
deba@797
   861
deba@797
   862
              Node parent = order_list[dn];
deba@797
   863
deba@797
   864
              // Erasing from merge_roots
deba@797
   865
              merge_roots[parent].pop_front();
deba@797
   866
deba@797
   867
              Node child = order_list[cn - order_list.size()];
deba@797
   868
deba@797
   869
              // Erasing from child_lists
deba@797
   870
              if (child_lists[child].prev != INVALID) {
deba@797
   871
                child_lists[child_lists[child].prev].next =
deba@797
   872
                  child_lists[child].next;
deba@797
   873
              } else {
deba@797
   874
                child_lists[parent].first = child_lists[child].next;
deba@797
   875
              }
deba@797
   876
deba@797
   877
              if (child_lists[child].next != INVALID) {
deba@797
   878
                child_lists[child_lists[child].next].prev =
deba@797
   879
                  child_lists[child].prev;
deba@797
   880
              }
deba@797
   881
deba@797
   882
              // Merging arcs + flipping
deba@797
   883
              Arc de = node_data[dn].first;
deba@797
   884
              Arc ce = node_data[cn].first;
deba@797
   885
deba@797
   886
              flip_map[order_list[cn - order_list.size()]] = cd != dd;
deba@797
   887
              if (cd != dd) {
deba@797
   888
                std::swap(arc_lists[ce].prev, arc_lists[ce].next);
deba@797
   889
                ce = arc_lists[ce].prev;
deba@797
   890
                std::swap(arc_lists[ce].prev, arc_lists[ce].next);
deba@797
   891
              }
deba@797
   892
deba@797
   893
              {
deba@797
   894
                Arc dne = arc_lists[de].next;
deba@797
   895
                Arc cne = arc_lists[ce].next;
deba@797
   896
deba@797
   897
                arc_lists[de].next = cne;
deba@797
   898
                arc_lists[ce].next = dne;
deba@797
   899
deba@797
   900
                arc_lists[dne].prev = ce;
deba@797
   901
                arc_lists[cne].prev = de;
deba@797
   902
              }
deba@797
   903
deba@797
   904
              if (dd) {
deba@797
   905
                node_data[dn].first = ce;
deba@797
   906
              }
deba@797
   907
deba@797
   908
              // Merging external faces
deba@797
   909
              {
deba@797
   910
                int en = cn;
deba@797
   911
                cn = cd ? node_data[cn].prev : node_data[cn].next;
deba@797
   912
                cd = node_data[cn].next == en;
deba@797
   913
deba@797
   914
                 if (node_data[cn].prev == node_data[cn].next &&
deba@797
   915
                    node_data[cn].inverted) {
deba@797
   916
                   cd = !cd;
deba@797
   917
                 }
deba@797
   918
              }
deba@797
   919
deba@797
   920
              if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
deba@797
   921
              if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
deba@797
   922
deba@797
   923
            }
deba@797
   924
deba@797
   925
            bool d = pn == node_data[n].prev;
deba@797
   926
deba@797
   927
            if (node_data[n].prev == node_data[n].next &&
deba@797
   928
                node_data[n].inverted) {
deba@797
   929
              d = !d;
deba@797
   930
            }
deba@797
   931
deba@797
   932
            // Add new arc
deba@797
   933
            {
deba@797
   934
              Arc arc = embed_arc[node];
deba@797
   935
              Arc re = node_data[rn].first;
deba@797
   936
deba@797
   937
              arc_lists[arc_lists[re].next].prev = arc;
deba@797
   938
              arc_lists[arc].next = arc_lists[re].next;
deba@797
   939
              arc_lists[arc].prev = re;
deba@797
   940
              arc_lists[re].next = arc;
deba@797
   941
deba@797
   942
              if (!rd) {
deba@797
   943
                node_data[rn].first = arc;
deba@797
   944
              }
deba@797
   945
deba@797
   946
              Arc rev = _graph.oppositeArc(arc);
deba@797
   947
              Arc e = node_data[n].first;
deba@797
   948
deba@797
   949
              arc_lists[arc_lists[e].next].prev = rev;
deba@797
   950
              arc_lists[rev].next = arc_lists[e].next;
deba@797
   951
              arc_lists[rev].prev = e;
deba@797
   952
              arc_lists[e].next = rev;
deba@797
   953
deba@797
   954
              if (d) {
deba@797
   955
                node_data[n].first = rev;
deba@797
   956
              }
deba@797
   957
deba@797
   958
            }
deba@797
   959
deba@797
   960
            // Embedding arc into external face
deba@797
   961
            if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
deba@797
   962
            if (d) node_data[n].prev = rn; else node_data[n].next = rn;
deba@797
   963
            pn = rn;
deba@797
   964
deba@797
   965
            embed_arc[order_list[n]] = INVALID;
deba@797
   966
          }
deba@797
   967
deba@797
   968
          if (!merge_roots[node].empty()) {
deba@797
   969
deba@797
   970
            bool d = pn == node_data[n].prev;
deba@797
   971
            if (node_data[n].prev == node_data[n].next &&
deba@797
   972
                node_data[n].inverted) {
deba@797
   973
              d = !d;
deba@797
   974
            }
deba@797
   975
deba@797
   976
            merge_stack.push_back(std::make_pair(n, d));
deba@797
   977
deba@797
   978
            int rn = merge_roots[node].front();
deba@797
   979
deba@797
   980
            int xn = node_data[rn].next;
deba@797
   981
            Node xnode = order_list[xn];
deba@797
   982
deba@797
   983
            int yn = node_data[rn].prev;
deba@797
   984
            Node ynode = order_list[yn];
deba@797
   985
deba@797
   986
            bool rd;
deba@797
   987
            if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
deba@797
   988
              rd = true;
deba@797
   989
            } else if (!external(ynode, rorder, child_lists,
deba@797
   990
                                 ancestor_map, low_map)) {
deba@797
   991
              rd = false;
deba@797
   992
            } else if (pertinent(xnode, embed_arc, merge_roots)) {
deba@797
   993
              rd = true;
deba@797
   994
            } else {
deba@797
   995
              rd = false;
deba@797
   996
            }
deba@797
   997
deba@797
   998
            merge_stack.push_back(std::make_pair(rn, rd));
deba@797
   999
deba@797
  1000
            pn = rn;
deba@797
  1001
            n = rd ? xn : yn;
deba@797
  1002
deba@797
  1003
          } else if (!external(node, rorder, child_lists,
deba@797
  1004
                               ancestor_map, low_map)) {
deba@797
  1005
            int nn = (node_data[n].next != pn ?
deba@797
  1006
                      node_data[n].next : node_data[n].prev);
deba@797
  1007
deba@797
  1008
            bool nd = n == node_data[nn].prev;
deba@797
  1009
deba@797
  1010
            if (nd) node_data[nn].prev = pn;
deba@797
  1011
            else node_data[nn].next = pn;
deba@797
  1012
deba@797
  1013
            if (n == node_data[pn].prev) node_data[pn].prev = nn;
deba@797
  1014
            else node_data[pn].next = nn;
deba@797
  1015
deba@797
  1016
            node_data[nn].inverted =
deba@797
  1017
              (node_data[nn].prev == node_data[nn].next && nd != rd);
deba@797
  1018
deba@797
  1019
            n = nn;
deba@797
  1020
          }
deba@797
  1021
          else break;
deba@797
  1022
deba@797
  1023
        }
deba@797
  1024
deba@797
  1025
        if (!merge_stack.empty() || n == rn) {
deba@797
  1026
          break;
deba@797
  1027
        }
deba@797
  1028
      }
deba@797
  1029
    }
deba@797
  1030
deba@797
  1031
    void initFace(const Node& node, ArcLists& arc_lists,
deba@797
  1032
                  NodeData& node_data, const PredMap& pred_map,
deba@797
  1033
                  const OrderMap& order_map, const OrderList& order_list) {
deba@797
  1034
      int n = order_map[node];
deba@797
  1035
      int rn = n + order_list.size();
deba@797
  1036
deba@797
  1037
      node_data[n].next = node_data[n].prev = rn;
deba@797
  1038
      node_data[rn].next = node_data[rn].prev = n;
deba@797
  1039
deba@797
  1040
      node_data[n].visited = order_list.size();
deba@797
  1041
      node_data[rn].visited = order_list.size();
deba@797
  1042
deba@797
  1043
      node_data[n].inverted = false;
deba@797
  1044
      node_data[rn].inverted = false;
deba@797
  1045
deba@797
  1046
      Arc arc = pred_map[node];
deba@797
  1047
      Arc rev = _graph.oppositeArc(arc);
deba@797
  1048
deba@797
  1049
      node_data[rn].first = arc;
deba@797
  1050
      node_data[n].first = rev;
deba@797
  1051
deba@797
  1052
      arc_lists[arc].prev = arc;
deba@797
  1053
      arc_lists[arc].next = arc;
deba@797
  1054
deba@797
  1055
      arc_lists[rev].prev = rev;
deba@797
  1056
      arc_lists[rev].next = rev;
deba@797
  1057
deba@797
  1058
    }
deba@797
  1059
deba@797
  1060
    void mergeRemainingFaces(const Node& node, NodeData& node_data,
deba@797
  1061
                             OrderList& order_list, OrderMap& order_map,
deba@797
  1062
                             ChildLists& child_lists, ArcLists& arc_lists) {
deba@797
  1063
      while (child_lists[node].first != INVALID) {
deba@797
  1064
        int dd = order_map[node];
deba@797
  1065
        Node child = child_lists[node].first;
deba@797
  1066
        int cd = order_map[child] + order_list.size();
deba@797
  1067
        child_lists[node].first = child_lists[child].next;
deba@797
  1068
deba@797
  1069
        Arc de = node_data[dd].first;
deba@797
  1070
        Arc ce = node_data[cd].first;
deba@797
  1071
deba@797
  1072
        if (de != INVALID) {
deba@797
  1073
          Arc dne = arc_lists[de].next;
deba@797
  1074
          Arc cne = arc_lists[ce].next;
deba@797
  1075
deba@797
  1076
          arc_lists[de].next = cne;
deba@797
  1077
          arc_lists[ce].next = dne;
deba@797
  1078
deba@797
  1079
          arc_lists[dne].prev = ce;
deba@797
  1080
          arc_lists[cne].prev = de;
deba@797
  1081
        }
deba@797
  1082
deba@797
  1083
        node_data[dd].first = ce;
deba@797
  1084
deba@797
  1085
      }
deba@797
  1086
    }
deba@797
  1087
deba@797
  1088
    void storeEmbedding(const Node& node, NodeData& node_data,
deba@797
  1089
                        OrderMap& order_map, PredMap& pred_map,
deba@797
  1090
                        ArcLists& arc_lists, FlipMap& flip_map) {
deba@797
  1091
deba@797
  1092
      if (node_data[order_map[node]].first == INVALID) return;
deba@797
  1093
deba@797
  1094
      if (pred_map[node] != INVALID) {
deba@797
  1095
        Node source = _graph.source(pred_map[node]);
deba@797
  1096
        flip_map[node] = flip_map[node] != flip_map[source];
deba@797
  1097
      }
deba@797
  1098
deba@797
  1099
      Arc first = node_data[order_map[node]].first;
deba@797
  1100
      Arc prev = first;
deba@797
  1101
deba@797
  1102
      Arc arc = flip_map[node] ?
deba@797
  1103
        arc_lists[prev].prev : arc_lists[prev].next;
deba@797
  1104
deba@797
  1105
      _embedding[prev] = arc;
deba@797
  1106
deba@797
  1107
      while (arc != first) {
deba@797
  1108
        Arc next = arc_lists[arc].prev == prev ?
deba@797
  1109
          arc_lists[arc].next : arc_lists[arc].prev;
deba@797
  1110
        prev = arc; arc = next;
deba@797
  1111
        _embedding[prev] = arc;
deba@797
  1112
      }
deba@797
  1113
    }
deba@797
  1114
deba@797
  1115
deba@797
  1116
    bool external(const Node& node, int rorder,
deba@797
  1117
                  ChildLists& child_lists, AncestorMap& ancestor_map,
deba@797
  1118
                  LowMap& low_map) {
deba@797
  1119
      Node child = child_lists[node].first;
deba@797
  1120
deba@797
  1121
      if (child != INVALID) {
deba@797
  1122
        if (low_map[child] < rorder) return true;
deba@797
  1123
      }
deba@797
  1124
deba@797
  1125
      if (ancestor_map[node] < rorder) return true;
deba@797
  1126
deba@797
  1127
      return false;
deba@797
  1128
    }
deba@797
  1129
deba@797
  1130
    bool pertinent(const Node& node, const EmbedArc& embed_arc,
deba@797
  1131
                   const MergeRoots& merge_roots) {
deba@797
  1132
      return !merge_roots[node].empty() || embed_arc[node] != INVALID;
deba@797
  1133
    }
deba@797
  1134
deba@797
  1135
    int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
deba@797
  1136
                 AncestorMap& ancestor_map, LowMap& low_map) {
deba@797
  1137
      int low_point;
deba@797
  1138
deba@797
  1139
      Node child = child_lists[node].first;
deba@797
  1140
deba@797
  1141
      if (child != INVALID) {
deba@797
  1142
        low_point = low_map[child];
deba@797
  1143
      } else {
deba@797
  1144
        low_point = order_map[node];
deba@797
  1145
      }
deba@797
  1146
deba@797
  1147
      if (low_point > ancestor_map[node]) {
deba@797
  1148
        low_point = ancestor_map[node];
deba@797
  1149
      }
deba@797
  1150
deba@797
  1151
      return low_point;
deba@797
  1152
    }
deba@797
  1153
deba@797
  1154
    int findComponentRoot(Node root, Node node, ChildLists& child_lists,
deba@797
  1155
                          OrderMap& order_map, OrderList& order_list) {
deba@797
  1156
deba@797
  1157
      int order = order_map[root];
deba@797
  1158
      int norder = order_map[node];
deba@797
  1159
deba@797
  1160
      Node child = child_lists[root].first;
deba@797
  1161
      while (child != INVALID) {
deba@797
  1162
        int corder = order_map[child];
deba@797
  1163
        if (corder > order && corder < norder) {
deba@797
  1164
          order = corder;
deba@797
  1165
        }
deba@797
  1166
        child = child_lists[child].next;
deba@797
  1167
      }
deba@797
  1168
      return order + order_list.size();
deba@797
  1169
    }
deba@797
  1170
deba@797
  1171
    Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data,
deba@797
  1172
                       EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@797
  1173
      Node wnode =_graph.target(node_data[order_map[node]].first);
deba@797
  1174
      while (!pertinent(wnode, embed_arc, merge_roots)) {
deba@797
  1175
        wnode = _graph.target(node_data[order_map[wnode]].first);
deba@797
  1176
      }
deba@797
  1177
      return wnode;
deba@797
  1178
    }
deba@797
  1179
deba@797
  1180
deba@797
  1181
    Node findExternal(Node node, int rorder, OrderMap& order_map,
deba@797
  1182
                      ChildLists& child_lists, AncestorMap& ancestor_map,
deba@797
  1183
                      LowMap& low_map, NodeData& node_data) {
deba@797
  1184
      Node wnode =_graph.target(node_data[order_map[node]].first);
deba@797
  1185
      while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
deba@797
  1186
        wnode = _graph.target(node_data[order_map[wnode]].first);
deba@797
  1187
      }
deba@797
  1188
      return wnode;
deba@797
  1189
    }
deba@797
  1190
deba@797
  1191
    void markCommonPath(Node node, int rorder, Node& wnode, Node& znode,
deba@797
  1192
                        OrderList& order_list, OrderMap& order_map,
deba@797
  1193
                        NodeData& node_data, ArcLists& arc_lists,
deba@797
  1194
                        EmbedArc& embed_arc, MergeRoots& merge_roots,
deba@797
  1195
                        ChildLists& child_lists, AncestorMap& ancestor_map,
deba@797
  1196
                        LowMap& low_map) {
deba@797
  1197
deba@797
  1198
      Node cnode = node;
deba@797
  1199
      Node pred = INVALID;
deba@797
  1200
deba@797
  1201
      while (true) {
deba@797
  1202
deba@797
  1203
        bool pert = pertinent(cnode, embed_arc, merge_roots);
deba@797
  1204
        bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
deba@797
  1205
deba@797
  1206
        if (pert && ext) {
deba@797
  1207
          if (!merge_roots[cnode].empty()) {
deba@797
  1208
            int cn = merge_roots[cnode].back();
deba@797
  1209
deba@797
  1210
            if (low_map[order_list[cn - order_list.size()]] < rorder) {
deba@797
  1211
              Arc arc = node_data[cn].first;
deba@797
  1212
              _kuratowski.set(arc, true);
deba@797
  1213
deba@797
  1214
              pred = cnode;
deba@797
  1215
              cnode = _graph.target(arc);
deba@797
  1216
deba@797
  1217
              continue;
deba@797
  1218
            }
deba@797
  1219
          }
deba@797
  1220
          wnode = znode = cnode;
deba@797
  1221
          return;
deba@797
  1222
deba@797
  1223
        } else if (pert) {
deba@797
  1224
          wnode = cnode;
deba@797
  1225
deba@797
  1226
          while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
deba@797
  1227
            Arc arc = node_data[order_map[cnode]].first;
deba@797
  1228
deba@797
  1229
            if (_graph.target(arc) == pred) {
deba@797
  1230
              arc = arc_lists[arc].next;
deba@797
  1231
            }
deba@797
  1232
            _kuratowski.set(arc, true);
deba@797
  1233
deba@797
  1234
            Node next = _graph.target(arc);
deba@797
  1235
            pred = cnode; cnode = next;
deba@797
  1236
          }
deba@797
  1237
deba@797
  1238
          znode = cnode;
deba@797
  1239
          return;
deba@797
  1240
deba@797
  1241
        } else if (ext) {
deba@797
  1242
          znode = cnode;
deba@797
  1243
deba@797
  1244
          while (!pertinent(cnode, embed_arc, merge_roots)) {
deba@797
  1245
            Arc arc = node_data[order_map[cnode]].first;
deba@797
  1246
deba@797
  1247
            if (_graph.target(arc) == pred) {
deba@797
  1248
              arc = arc_lists[arc].next;
deba@797
  1249
            }
deba@797
  1250
            _kuratowski.set(arc, true);
deba@797
  1251
deba@797
  1252
            Node next = _graph.target(arc);
deba@797
  1253
            pred = cnode; cnode = next;
deba@797
  1254
          }
deba@797
  1255
deba@797
  1256
          wnode = cnode;
deba@797
  1257
          return;
deba@797
  1258
deba@797
  1259
        } else {
deba@797
  1260
          Arc arc = node_data[order_map[cnode]].first;
deba@797
  1261
deba@797
  1262
          if (_graph.target(arc) == pred) {
deba@797
  1263
            arc = arc_lists[arc].next;
deba@797
  1264
          }
deba@797
  1265
          _kuratowski.set(arc, true);
deba@797
  1266
deba@797
  1267
          Node next = _graph.target(arc);
deba@797
  1268
          pred = cnode; cnode = next;
deba@797
  1269
        }
deba@797
  1270
deba@797
  1271
      }
deba@797
  1272
deba@797
  1273
    }
deba@797
  1274
deba@797
  1275
    void orientComponent(Node root, int rn, OrderMap& order_map,
deba@797
  1276
                         PredMap& pred_map, NodeData& node_data,
deba@797
  1277
                         ArcLists& arc_lists, FlipMap& flip_map,
deba@797
  1278
                         TypeMap& type_map) {
deba@797
  1279
      node_data[order_map[root]].first = node_data[rn].first;
deba@797
  1280
      type_map[root] = 1;
deba@797
  1281
deba@797
  1282
      std::vector<Node> st, qu;
deba@797
  1283
deba@797
  1284
      st.push_back(root);
deba@797
  1285
      while (!st.empty()) {
deba@797
  1286
        Node node = st.back();
deba@797
  1287
        st.pop_back();
deba@797
  1288
        qu.push_back(node);
deba@797
  1289
deba@797
  1290
        Arc arc = node_data[order_map[node]].first;
deba@797
  1291
deba@797
  1292
        if (type_map[_graph.target(arc)] == 0) {
deba@797
  1293
          st.push_back(_graph.target(arc));
deba@797
  1294
          type_map[_graph.target(arc)] = 1;
deba@797
  1295
        }
deba@797
  1296
deba@797
  1297
        Arc last = arc, pred = arc;
deba@797
  1298
        arc = arc_lists[arc].next;
deba@797
  1299
        while (arc != last) {
deba@797
  1300
deba@797
  1301
          if (type_map[_graph.target(arc)] == 0) {
deba@797
  1302
            st.push_back(_graph.target(arc));
deba@797
  1303
            type_map[_graph.target(arc)] = 1;
deba@797
  1304
          }
deba@797
  1305
deba@797
  1306
          Arc next = arc_lists[arc].next != pred ?
deba@797
  1307
            arc_lists[arc].next : arc_lists[arc].prev;
deba@797
  1308
          pred = arc; arc = next;
deba@797
  1309
        }
deba@797
  1310
deba@797
  1311
      }
deba@797
  1312
deba@797
  1313
      type_map[root] = 2;
deba@797
  1314
      flip_map[root] = false;
deba@797
  1315
deba@797
  1316
      for (int i = 1; i < int(qu.size()); ++i) {
deba@797
  1317
deba@797
  1318
        Node node = qu[i];
deba@797
  1319
deba@797
  1320
        while (type_map[node] != 2) {
deba@797
  1321
          st.push_back(node);
deba@797
  1322
          type_map[node] = 2;
deba@797
  1323
          node = _graph.source(pred_map[node]);
deba@797
  1324
        }
deba@797
  1325
deba@797
  1326
        bool flip = flip_map[node];
deba@797
  1327
deba@797
  1328
        while (!st.empty()) {
deba@797
  1329
          node = st.back();
deba@797
  1330
          st.pop_back();
deba@797
  1331
deba@797
  1332
          flip_map[node] = flip != flip_map[node];
deba@797
  1333
          flip = flip_map[node];
deba@797
  1334
deba@797
  1335
          if (flip) {
deba@797
  1336
            Arc arc = node_data[order_map[node]].first;
deba@797
  1337
            std::swap(arc_lists[arc].prev, arc_lists[arc].next);
deba@797
  1338
            arc = arc_lists[arc].prev;
deba@797
  1339
            std::swap(arc_lists[arc].prev, arc_lists[arc].next);
deba@797
  1340
            node_data[order_map[node]].first = arc;
deba@797
  1341
          }
deba@797
  1342
        }
deba@797
  1343
      }
deba@797
  1344
deba@797
  1345
      for (int i = 0; i < int(qu.size()); ++i) {
deba@797
  1346
deba@797
  1347
        Arc arc = node_data[order_map[qu[i]]].first;
deba@797
  1348
        Arc last = arc, pred = arc;
deba@797
  1349
deba@797
  1350
        arc = arc_lists[arc].next;
deba@797
  1351
        while (arc != last) {
deba@797
  1352
deba@797
  1353
          if (arc_lists[arc].next == pred) {
deba@797
  1354
            std::swap(arc_lists[arc].next, arc_lists[arc].prev);
deba@797
  1355
          }
deba@797
  1356
          pred = arc; arc = arc_lists[arc].next;
deba@797
  1357
        }
deba@797
  1358
deba@797
  1359
      }
deba@797
  1360
    }
deba@797
  1361
deba@797
  1362
    void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode,
deba@797
  1363
                      OrderMap& order_map, NodeData& node_data,
deba@797
  1364
                      TypeMap& type_map) {
deba@797
  1365
      Node node = _graph.target(node_data[order_map[root]].first);
deba@797
  1366
deba@797
  1367
      while (node != ynode) {
deba@797
  1368
        type_map[node] = HIGHY;
deba@797
  1369
        node = _graph.target(node_data[order_map[node]].first);
deba@797
  1370
      }
deba@797
  1371
deba@797
  1372
      while (node != wnode) {
deba@797
  1373
        type_map[node] = LOWY;
deba@797
  1374
        node = _graph.target(node_data[order_map[node]].first);
deba@797
  1375
      }
deba@797
  1376
deba@797
  1377
      node = _graph.target(node_data[order_map[wnode]].first);
deba@797
  1378
deba@797
  1379
      while (node != xnode) {
deba@797
  1380
        type_map[node] = LOWX;
deba@797
  1381
        node = _graph.target(node_data[order_map[node]].first);
deba@797
  1382
      }
deba@797
  1383
      type_map[node] = LOWX;
deba@797
  1384
deba@797
  1385
      node = _graph.target(node_data[order_map[xnode]].first);
deba@797
  1386
      while (node != root) {
deba@797
  1387
        type_map[node] = HIGHX;
deba@797
  1388
        node = _graph.target(node_data[order_map[node]].first);
deba@797
  1389
      }
deba@797
  1390
deba@797
  1391
      type_map[wnode] = PERTINENT;
deba@797
  1392
      type_map[root] = ROOT;
deba@797
  1393
    }
deba@797
  1394
deba@797
  1395
    void findInternalPath(std::vector<Arc>& ipath,
deba@797
  1396
                          Node wnode, Node root, TypeMap& type_map,
deba@797
  1397
                          OrderMap& order_map, NodeData& node_data,
deba@797
  1398
                          ArcLists& arc_lists) {
deba@797
  1399
      std::vector<Arc> st;
deba@797
  1400
deba@797
  1401
      Node node = wnode;
deba@797
  1402
deba@797
  1403
      while (node != root) {
deba@797
  1404
        Arc arc = arc_lists[node_data[order_map[node]].first].next;
deba@797
  1405
        st.push_back(arc);
deba@797
  1406
        node = _graph.target(arc);
deba@797
  1407
      }
deba@797
  1408
deba@797
  1409
      while (true) {
deba@797
  1410
        Arc arc = st.back();
deba@797
  1411
        if (type_map[_graph.target(arc)] == LOWX ||
deba@797
  1412
            type_map[_graph.target(arc)] == HIGHX) {
deba@797
  1413
          break;
deba@797
  1414
        }
deba@797
  1415
        if (type_map[_graph.target(arc)] == 2) {
deba@797
  1416
          type_map[_graph.target(arc)] = 3;
deba@797
  1417
deba@797
  1418
          arc = arc_lists[_graph.oppositeArc(arc)].next;
deba@797
  1419
          st.push_back(arc);
deba@797
  1420
        } else {
deba@797
  1421
          st.pop_back();
deba@797
  1422
          arc = arc_lists[arc].next;
deba@797
  1423
deba@797
  1424
          while (_graph.oppositeArc(arc) == st.back()) {
deba@797
  1425
            arc = st.back();
deba@797
  1426
            st.pop_back();
deba@797
  1427
            arc = arc_lists[arc].next;
deba@797
  1428
          }
deba@797
  1429
          st.push_back(arc);
deba@797
  1430
        }
deba@797
  1431
      }
deba@797
  1432
deba@797
  1433
      for (int i = 0; i < int(st.size()); ++i) {
deba@797
  1434
        if (type_map[_graph.target(st[i])] != LOWY &&
deba@797
  1435
            type_map[_graph.target(st[i])] != HIGHY) {
deba@797
  1436
          for (; i < int(st.size()); ++i) {
deba@797
  1437
            ipath.push_back(st[i]);
deba@797
  1438
          }
deba@797
  1439
        }
deba@797
  1440
      }
deba@797
  1441
    }
deba@797
  1442
deba@797
  1443
    void setInternalFlags(std::vector<Arc>& ipath, TypeMap& type_map) {
deba@797
  1444
      for (int i = 1; i < int(ipath.size()); ++i) {
deba@797
  1445
        type_map[_graph.source(ipath[i])] = INTERNAL;
deba@797
  1446
      }
deba@797
  1447
    }
deba@797
  1448
deba@797
  1449
    void findPilePath(std::vector<Arc>& ppath,
deba@797
  1450
                      Node root, TypeMap& type_map, OrderMap& order_map,
deba@797
  1451
                      NodeData& node_data, ArcLists& arc_lists) {
deba@797
  1452
      std::vector<Arc> st;
deba@797
  1453
deba@797
  1454
      st.push_back(_graph.oppositeArc(node_data[order_map[root]].first));
deba@797
  1455
      st.push_back(node_data[order_map[root]].first);
deba@797
  1456
deba@797
  1457
      while (st.size() > 1) {
deba@797
  1458
        Arc arc = st.back();
deba@797
  1459
        if (type_map[_graph.target(arc)] == INTERNAL) {
deba@797
  1460
          break;
deba@797
  1461
        }
deba@797
  1462
        if (type_map[_graph.target(arc)] == 3) {
deba@797
  1463
          type_map[_graph.target(arc)] = 4;
deba@797
  1464
deba@797
  1465
          arc = arc_lists[_graph.oppositeArc(arc)].next;
deba@797
  1466
          st.push_back(arc);
deba@797
  1467
        } else {
deba@797
  1468
          st.pop_back();
deba@797
  1469
          arc = arc_lists[arc].next;
deba@797
  1470
deba@797
  1471
          while (!st.empty() && _graph.oppositeArc(arc) == st.back()) {
deba@797
  1472
            arc = st.back();
deba@797
  1473
            st.pop_back();
deba@797
  1474
            arc = arc_lists[arc].next;
deba@797
  1475
          }
deba@797
  1476
          st.push_back(arc);
deba@797
  1477
        }
deba@797
  1478
      }
deba@797
  1479
deba@797
  1480
      for (int i = 1; i < int(st.size()); ++i) {
deba@797
  1481
        ppath.push_back(st[i]);
deba@797
  1482
      }
deba@797
  1483
    }
deba@797
  1484
deba@797
  1485
deba@797
  1486
    int markExternalPath(Node node, OrderMap& order_map,
deba@797
  1487
                         ChildLists& child_lists, PredMap& pred_map,
deba@797
  1488
                         AncestorMap& ancestor_map, LowMap& low_map) {
deba@797
  1489
      int lp = lowPoint(node, order_map, child_lists,
deba@797
  1490
                        ancestor_map, low_map);
deba@797
  1491
deba@797
  1492
      if (ancestor_map[node] != lp) {
deba@797
  1493
        node = child_lists[node].first;
deba@797
  1494
        _kuratowski[pred_map[node]] = true;
deba@797
  1495
deba@797
  1496
        while (ancestor_map[node] != lp) {
deba@797
  1497
          for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797
  1498
            Node tnode = _graph.target(e);
deba@797
  1499
            if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) {
deba@797
  1500
              node = tnode;
deba@797
  1501
              _kuratowski[e] = true;
deba@797
  1502
              break;
deba@797
  1503
            }
deba@797
  1504
          }
deba@797
  1505
        }
deba@797
  1506
      }
deba@797
  1507
deba@797
  1508
      for (OutArcIt e(_graph, node); e != INVALID; ++e) {
deba@797
  1509
        if (order_map[_graph.target(e)] == lp) {
deba@797
  1510
          _kuratowski[e] = true;
deba@797
  1511
          break;
deba@797
  1512
        }
deba@797
  1513
      }
deba@797
  1514
deba@797
  1515
      return lp;
deba@797
  1516
    }
deba@797
  1517
deba@797
  1518
    void markPertinentPath(Node node, OrderMap& order_map,
deba@797
  1519
                           NodeData& node_data, ArcLists& arc_lists,
deba@797
  1520
                           EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@797
  1521
      while (embed_arc[node] == INVALID) {
deba@797
  1522
        int n = merge_roots[node].front();
deba@797
  1523
        Arc arc = node_data[n].first;
deba@797
  1524
deba@797
  1525
        _kuratowski.set(arc, true);
deba@797
  1526
deba@797
  1527
        Node pred = node;
deba@797
  1528
        node = _graph.target(arc);
deba@797
  1529
        while (!pertinent(node, embed_arc, merge_roots)) {
deba@797
  1530
          arc = node_data[order_map[node]].first;
deba@797
  1531
          if (_graph.target(arc) == pred) {
deba@797
  1532
            arc = arc_lists[arc].next;
deba@797
  1533
          }
deba@797
  1534
          _kuratowski.set(arc, true);
deba@797
  1535
          pred = node;
deba@797
  1536
          node = _graph.target(arc);
deba@797
  1537
        }
deba@797
  1538
      }
deba@797
  1539
      _kuratowski.set(embed_arc[node], true);
deba@797
  1540
    }
deba@797
  1541
deba@797
  1542
    void markPredPath(Node node, Node snode, PredMap& pred_map) {
deba@797
  1543
      while (node != snode) {
deba@797
  1544
        _kuratowski.set(pred_map[node], true);
deba@797
  1545
        node = _graph.source(pred_map[node]);
deba@797
  1546
      }
deba@797
  1547
    }
deba@797
  1548
deba@797
  1549
    void markFacePath(Node ynode, Node xnode,
deba@797
  1550
                      OrderMap& order_map, NodeData& node_data) {
deba@797
  1551
      Arc arc = node_data[order_map[ynode]].first;
deba@797
  1552
      Node node = _graph.target(arc);
deba@797
  1553
      _kuratowski.set(arc, true);
deba@797
  1554
deba@797
  1555
      while (node != xnode) {
deba@797
  1556
        arc = node_data[order_map[node]].first;
deba@797
  1557
        _kuratowski.set(arc, true);
deba@797
  1558
        node = _graph.target(arc);
deba@797
  1559
      }
deba@797
  1560
    }
deba@797
  1561
deba@797
  1562
    void markInternalPath(std::vector<Arc>& path) {
deba@797
  1563
      for (int i = 0; i < int(path.size()); ++i) {
deba@797
  1564
        _kuratowski.set(path[i], true);
deba@797
  1565
      }
deba@797
  1566
    }
deba@797
  1567
deba@797
  1568
    void markPilePath(std::vector<Arc>& path) {
deba@797
  1569
      for (int i = 0; i < int(path.size()); ++i) {
deba@797
  1570
        _kuratowski.set(path[i], true);
deba@797
  1571
      }
deba@797
  1572
    }
deba@797
  1573
deba@797
  1574
    void isolateKuratowski(Arc arc, NodeData& node_data,
deba@797
  1575
                           ArcLists& arc_lists, FlipMap& flip_map,
deba@797
  1576
                           OrderMap& order_map, OrderList& order_list,
deba@797
  1577
                           PredMap& pred_map, ChildLists& child_lists,
deba@797
  1578
                           AncestorMap& ancestor_map, LowMap& low_map,
deba@797
  1579
                           EmbedArc& embed_arc, MergeRoots& merge_roots) {
deba@797
  1580
deba@797
  1581
      Node root = _graph.source(arc);
deba@797
  1582
      Node enode = _graph.target(arc);
deba@797
  1583
deba@797
  1584
      int rorder = order_map[root];
deba@797
  1585
deba@797
  1586
      TypeMap type_map(_graph, 0);
deba@797
  1587
deba@797
  1588
      int rn = findComponentRoot(root, enode, child_lists,
deba@797
  1589
                                 order_map, order_list);
deba@797
  1590
deba@797
  1591
      Node xnode = order_list[node_data[rn].next];
deba@797
  1592
      Node ynode = order_list[node_data[rn].prev];
deba@797
  1593
deba@797
  1594
      // Minor-A
deba@797
  1595
      {
deba@797
  1596
        while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
deba@797
  1597
deba@797
  1598
          if (!merge_roots[xnode].empty()) {
deba@797
  1599
            root = xnode;
deba@797
  1600
            rn = merge_roots[xnode].front();
deba@797
  1601
          } else {
deba@797
  1602
            root = ynode;
deba@797
  1603
            rn = merge_roots[ynode].front();
deba@797
  1604
          }
deba@797
  1605
deba@797
  1606
          xnode = order_list[node_data[rn].next];
deba@797
  1607
          ynode = order_list[node_data[rn].prev];
deba@797
  1608
        }
deba@797
  1609
deba@797
  1610
        if (root != _graph.source(arc)) {
deba@797
  1611
          orientComponent(root, rn, order_map, pred_map,
deba@797
  1612
                          node_data, arc_lists, flip_map, type_map);
deba@797
  1613
          markFacePath(root, root, order_map, node_data);
deba@797
  1614
          int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797
  1615
                                     pred_map, ancestor_map, low_map);
deba@797
  1616
          int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797
  1617
                                     pred_map, ancestor_map, low_map);
deba@797
  1618
          markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797
  1619
          Node lwnode = findPertinent(ynode, order_map, node_data,
deba@797
  1620
                                      embed_arc, merge_roots);
deba@797
  1621
deba@797
  1622
          markPertinentPath(lwnode, order_map, node_data, arc_lists,
deba@797
  1623
                            embed_arc, merge_roots);
deba@797
  1624
deba@797
  1625
          return;
deba@797
  1626
        }
deba@797
  1627
      }
deba@797
  1628
deba@797
  1629
      orientComponent(root, rn, order_map, pred_map,
deba@797
  1630
                      node_data, arc_lists, flip_map, type_map);
deba@797
  1631
deba@797
  1632
      Node wnode = findPertinent(ynode, order_map, node_data,
deba@797
  1633
                                 embed_arc, merge_roots);
deba@797
  1634
      setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map);
deba@797
  1635
deba@797
  1636
deba@797
  1637
      //Minor-B
deba@797
  1638
      if (!merge_roots[wnode].empty()) {
deba@797
  1639
        int cn = merge_roots[wnode].back();
deba@797
  1640
        Node rep = order_list[cn - order_list.size()];
deba@797
  1641
        if (low_map[rep] < rorder) {
deba@797
  1642
          markFacePath(root, root, order_map, node_data);
deba@797
  1643
          int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797
  1644
                                     pred_map, ancestor_map, low_map);
deba@797
  1645
          int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797
  1646
                                     pred_map, ancestor_map, low_map);
deba@797
  1647
deba@797
  1648
          Node lwnode, lznode;
deba@797
  1649
          markCommonPath(wnode, rorder, lwnode, lznode, order_list,
deba@797
  1650
                         order_map, node_data, arc_lists, embed_arc,
deba@797
  1651
                         merge_roots, child_lists, ancestor_map, low_map);
deba@797
  1652
deba@797
  1653
          markPertinentPath(lwnode, order_map, node_data, arc_lists,
deba@797
  1654
                            embed_arc, merge_roots);
deba@797
  1655
          int zlp = markExternalPath(lznode, order_map, child_lists,
deba@797
  1656
                                     pred_map, ancestor_map, low_map);
deba@797
  1657
deba@797
  1658
          int minlp = xlp < ylp ? xlp : ylp;
deba@797
  1659
          if (zlp < minlp) minlp = zlp;
deba@797
  1660
deba@797
  1661
          int maxlp = xlp > ylp ? xlp : ylp;
deba@797
  1662
          if (zlp > maxlp) maxlp = zlp;
deba@797
  1663
deba@797
  1664
          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@797
  1665
deba@797
  1666
          return;
deba@797
  1667
        }
deba@797
  1668
      }
deba@797
  1669
deba@797
  1670
      Node pxnode, pynode;
deba@797
  1671
      std::vector<Arc> ipath;
deba@797
  1672
      findInternalPath(ipath, wnode, root, type_map, order_map,
deba@797
  1673
                       node_data, arc_lists);
deba@797
  1674
      setInternalFlags(ipath, type_map);
deba@797
  1675
      pynode = _graph.source(ipath.front());
deba@797
  1676
      pxnode = _graph.target(ipath.back());
deba@797
  1677
deba@797
  1678
      wnode = findPertinent(pynode, order_map, node_data,
deba@797
  1679
                            embed_arc, merge_roots);
deba@797
  1680
deba@797
  1681
      // Minor-C
deba@797
  1682
      {
deba@797
  1683
        if (type_map[_graph.source(ipath.front())] == HIGHY) {
deba@797
  1684
          if (type_map[_graph.target(ipath.back())] == HIGHX) {
deba@797
  1685
            markFacePath(xnode, pxnode, order_map, node_data);
deba@797
  1686
          }
deba@797
  1687
          markFacePath(root, xnode, order_map, node_data);
deba@797
  1688
          markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797
  1689
                            embed_arc, merge_roots);
deba@797
  1690
          markInternalPath(ipath);
deba@797
  1691
          int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797
  1692
                                     pred_map, ancestor_map, low_map);
deba@797
  1693
          int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797
  1694
                                     pred_map, ancestor_map, low_map);
deba@797
  1695
          markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797
  1696
          return;
deba@797
  1697
        }
deba@797
  1698
deba@797
  1699
        if (type_map[_graph.target(ipath.back())] == HIGHX) {
deba@797
  1700
          markFacePath(ynode, root, order_map, node_data);
deba@797
  1701
          markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797
  1702
                            embed_arc, merge_roots);
deba@797
  1703
          markInternalPath(ipath);
deba@797
  1704
          int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797
  1705
                                     pred_map, ancestor_map, low_map);
deba@797
  1706
          int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797
  1707
                                     pred_map, ancestor_map, low_map);
deba@797
  1708
          markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797
  1709
          return;
deba@797
  1710
        }
deba@797
  1711
      }
deba@797
  1712
deba@797
  1713
      std::vector<Arc> ppath;
deba@797
  1714
      findPilePath(ppath, root, type_map, order_map, node_data, arc_lists);
deba@797
  1715
deba@797
  1716
      // Minor-D
deba@797
  1717
      if (!ppath.empty()) {
deba@797
  1718
        markFacePath(ynode, xnode, order_map, node_data);
deba@797
  1719
        markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797
  1720
                          embed_arc, merge_roots);
deba@797
  1721
        markPilePath(ppath);
deba@797
  1722
        markInternalPath(ipath);
deba@797
  1723
        int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797
  1724
                                   pred_map, ancestor_map, low_map);
deba@797
  1725
        int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797
  1726
                                   pred_map, ancestor_map, low_map);
deba@797
  1727
        markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797
  1728
        return;
deba@797
  1729
      }
deba@797
  1730
deba@797
  1731
      // Minor-E*
deba@797
  1732
      {
deba@797
  1733
deba@797
  1734
        if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
deba@797
  1735
          Node znode = findExternal(pynode, rorder, order_map,
deba@797
  1736
                                    child_lists, ancestor_map,
deba@797
  1737
                                    low_map, node_data);
deba@797
  1738
deba@797
  1739
          if (type_map[znode] == LOWY) {
deba@797
  1740
            markFacePath(root, xnode, order_map, node_data);
deba@797
  1741
            markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797
  1742
                              embed_arc, merge_roots);
deba@797
  1743
            markInternalPath(ipath);
deba@797
  1744
            int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797
  1745
                                       pred_map, ancestor_map, low_map);
deba@797
  1746
            int zlp = markExternalPath(znode, order_map, child_lists,
deba@797
  1747
                                       pred_map, ancestor_map, low_map);
deba@797
  1748
            markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map);
deba@797
  1749
          } else {
deba@797
  1750
            markFacePath(ynode, root, order_map, node_data);
deba@797
  1751
            markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797
  1752
                              embed_arc, merge_roots);
deba@797
  1753
            markInternalPath(ipath);
deba@797
  1754
            int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797
  1755
                                       pred_map, ancestor_map, low_map);
deba@797
  1756
            int zlp = markExternalPath(znode, order_map, child_lists,
deba@797
  1757
                                       pred_map, ancestor_map, low_map);
deba@797
  1758
            markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map);
deba@797
  1759
          }
deba@797
  1760
          return;
deba@797
  1761
        }
deba@797
  1762
deba@797
  1763
        int xlp = markExternalPath(xnode, order_map, child_lists,
deba@797
  1764
                                   pred_map, ancestor_map, low_map);
deba@797
  1765
        int ylp = markExternalPath(ynode, order_map, child_lists,
deba@797
  1766
                                   pred_map, ancestor_map, low_map);
deba@797
  1767
        int wlp = markExternalPath(wnode, order_map, child_lists,
deba@797
  1768
                                   pred_map, ancestor_map, low_map);
deba@797
  1769
deba@797
  1770
        if (wlp > xlp && wlp > ylp) {
deba@797
  1771
          markFacePath(root, root, order_map, node_data);
deba@797
  1772
          markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@797
  1773
          return;
deba@797
  1774
        }
deba@797
  1775
deba@797
  1776
        markInternalPath(ipath);
deba@797
  1777
        markPertinentPath(wnode, order_map, node_data, arc_lists,
deba@797
  1778
                          embed_arc, merge_roots);
deba@797
  1779
deba@797
  1780
        if (xlp > ylp && xlp > wlp) {
deba@797
  1781
          markFacePath(root, pynode, order_map, node_data);
deba@797
  1782
          markFacePath(wnode, xnode, order_map, node_data);
deba@797
  1783
          markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map);
deba@797
  1784
          return;
deba@797
  1785
        }
deba@797
  1786
deba@797
  1787
        if (ylp > xlp && ylp > wlp) {
deba@797
  1788
          markFacePath(pxnode, root, order_map, node_data);
deba@797
  1789
          markFacePath(ynode, wnode, order_map, node_data);
deba@797
  1790
          markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map);
deba@797
  1791
          return;
deba@797
  1792
        }
deba@797
  1793
deba@797
  1794
        if (pynode != ynode) {
deba@797
  1795
          markFacePath(pxnode, wnode, order_map, node_data);
deba@797
  1796
deba@797
  1797
          int minlp = xlp < ylp ? xlp : ylp;
deba@797
  1798
          if (wlp < minlp) minlp = wlp;
deba@797
  1799
deba@797
  1800
          int maxlp = xlp > ylp ? xlp : ylp;
deba@797
  1801
          if (wlp > maxlp) maxlp = wlp;
deba@797
  1802
deba@797
  1803
          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@797
  1804
          return;
deba@797
  1805
        }
deba@797
  1806
deba@797
  1807
        if (pxnode != xnode) {
deba@797
  1808
          markFacePath(wnode, pynode, order_map, node_data);
deba@797
  1809
deba@797
  1810
          int minlp = xlp < ylp ? xlp : ylp;
deba@797
  1811
          if (wlp < minlp) minlp = wlp;
deba@797
  1812
deba@797
  1813
          int maxlp = xlp > ylp ? xlp : ylp;
deba@797
  1814
          if (wlp > maxlp) maxlp = wlp;
deba@797
  1815
deba@797
  1816
          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@797
  1817
          return;
deba@797
  1818
        }
deba@797
  1819
deba@797
  1820
        markFacePath(root, root, order_map, node_data);
deba@797
  1821
        int minlp = xlp < ylp ? xlp : ylp;
deba@797
  1822
        if (wlp < minlp) minlp = wlp;
deba@797
  1823
        markPredPath(root, order_list[minlp], pred_map);
deba@797
  1824
        return;
deba@797
  1825
      }
deba@797
  1826
deba@797
  1827
    }
deba@797
  1828
deba@797
  1829
  };
deba@797
  1830
deba@797
  1831
  namespace _planarity_bits {
deba@797
  1832
deba@797
  1833
    template <typename Graph, typename EmbeddingMap>
deba@797
  1834
    void makeConnected(Graph& graph, EmbeddingMap& embedding) {
deba@797
  1835
      DfsVisitor<Graph> null_visitor;
deba@797
  1836
      DfsVisit<Graph, DfsVisitor<Graph> > dfs(graph, null_visitor);
deba@797
  1837
      dfs.init();
deba@797
  1838
deba@797
  1839
      typename Graph::Node u = INVALID;
deba@797
  1840
      for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@797
  1841
        if (!dfs.reached(n)) {
deba@797
  1842
          dfs.addSource(n);
deba@797
  1843
          dfs.start();
deba@797
  1844
          if (u == INVALID) {
deba@797
  1845
            u = n;
deba@797
  1846
          } else {
deba@797
  1847
            typename Graph::Node v = n;
deba@797
  1848
deba@797
  1849
            typename Graph::Arc ue = typename Graph::OutArcIt(graph, u);
deba@797
  1850
            typename Graph::Arc ve = typename Graph::OutArcIt(graph, v);
deba@797
  1851
deba@797
  1852
            typename Graph::Arc e = graph.direct(graph.addEdge(u, v), true);
deba@797
  1853
deba@797
  1854
            if (ue != INVALID) {
deba@797
  1855
              embedding[e] = embedding[ue];
deba@797
  1856
              embedding[ue] = e;
deba@797
  1857
            } else {
deba@797
  1858
              embedding[e] = e;
deba@797
  1859
            }
deba@797
  1860
deba@797
  1861
            if (ve != INVALID) {
deba@797
  1862
              embedding[graph.oppositeArc(e)] = embedding[ve];
deba@797
  1863
              embedding[ve] = graph.oppositeArc(e);
deba@797
  1864
            } else {
deba@797
  1865
              embedding[graph.oppositeArc(e)] = graph.oppositeArc(e);
deba@797
  1866
            }
deba@797
  1867
          }
deba@797
  1868
        }
deba@797
  1869
      }
deba@797
  1870
    }
deba@797
  1871
deba@797
  1872
    template <typename Graph, typename EmbeddingMap>
deba@797
  1873
    void makeBiNodeConnected(Graph& graph, EmbeddingMap& embedding) {
deba@797
  1874
      typename Graph::template ArcMap<bool> processed(graph);
deba@797
  1875
deba@797
  1876
      std::vector<typename Graph::Arc> arcs;
deba@797
  1877
      for (typename Graph::ArcIt e(graph); e != INVALID; ++e) {
deba@797
  1878
        arcs.push_back(e);
deba@797
  1879
      }
deba@797
  1880
deba@797
  1881
      IterableBoolMap<Graph, typename Graph::Node> visited(graph, false);
deba@797
  1882
deba@797
  1883
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@797
  1884
        typename Graph::Arc pp = arcs[i];
deba@797
  1885
        if (processed[pp]) continue;
deba@797
  1886
deba@797
  1887
        typename Graph::Arc e = embedding[graph.oppositeArc(pp)];
deba@797
  1888
        processed[e] = true;
deba@797
  1889
        visited.set(graph.source(e), true);
deba@797
  1890
deba@797
  1891
        typename Graph::Arc p = e, l = e;
deba@797
  1892
        e = embedding[graph.oppositeArc(e)];
deba@797
  1893
deba@797
  1894
        while (e != l) {
deba@797
  1895
          processed[e] = true;
deba@797
  1896
deba@797
  1897
          if (visited[graph.source(e)]) {
deba@797
  1898
deba@797
  1899
            typename Graph::Arc n =
deba@797
  1900
              graph.direct(graph.addEdge(graph.source(p),
deba@797
  1901
                                           graph.target(e)), true);
deba@797
  1902
            embedding[n] = p;
deba@797
  1903
            embedding[graph.oppositeArc(pp)] = n;
deba@797
  1904
deba@797
  1905
            embedding[graph.oppositeArc(n)] =
deba@797
  1906
              embedding[graph.oppositeArc(e)];
deba@797
  1907
            embedding[graph.oppositeArc(e)] =
deba@797
  1908
              graph.oppositeArc(n);
deba@797
  1909
deba@797
  1910
            p = n;
deba@797
  1911
            e = embedding[graph.oppositeArc(n)];
deba@797
  1912
          } else {
deba@797
  1913
            visited.set(graph.source(e), true);
deba@797
  1914
            pp = p;
deba@797
  1915
            p = e;
deba@797
  1916
            e = embedding[graph.oppositeArc(e)];
deba@797
  1917
          }
deba@797
  1918
        }
deba@797
  1919
        visited.setAll(false);
deba@797
  1920
      }
deba@797
  1921
    }
deba@797
  1922
deba@797
  1923
deba@797
  1924
    template <typename Graph, typename EmbeddingMap>
deba@797
  1925
    void makeMaxPlanar(Graph& graph, EmbeddingMap& embedding) {
deba@797
  1926
deba@797
  1927
      typename Graph::template NodeMap<int> degree(graph);
deba@797
  1928
deba@797
  1929
      for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
deba@797
  1930
        degree[n] = countIncEdges(graph, n);
deba@797
  1931
      }
deba@797
  1932
deba@797
  1933
      typename Graph::template ArcMap<bool> processed(graph);
deba@797
  1934
      IterableBoolMap<Graph, typename Graph::Node> visited(graph, false);
deba@797
  1935
deba@797
  1936
      std::vector<typename Graph::Arc> arcs;
deba@797
  1937
      for (typename Graph::ArcIt e(graph); e != INVALID; ++e) {
deba@797
  1938
        arcs.push_back(e);
deba@797
  1939
      }
deba@797
  1940
deba@797
  1941
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@797
  1942
        typename Graph::Arc e = arcs[i];
deba@797
  1943
deba@797
  1944
        if (processed[e]) continue;
deba@797
  1945
        processed[e] = true;
deba@797
  1946
deba@797
  1947
        typename Graph::Arc mine = e;
deba@797
  1948
        int mind = degree[graph.source(e)];
deba@797
  1949
deba@797
  1950
        int face_size = 1;
deba@797
  1951
deba@797
  1952
        typename Graph::Arc l = e;
deba@797
  1953
        e = embedding[graph.oppositeArc(e)];
deba@797
  1954
        while (l != e) {
deba@797
  1955
          processed[e] = true;
deba@797
  1956
deba@797
  1957
          ++face_size;
deba@797
  1958
deba@797
  1959
          if (degree[graph.source(e)] < mind) {
deba@797
  1960
            mine = e;
deba@797
  1961
            mind = degree[graph.source(e)];
deba@797
  1962
          }
deba@797
  1963
deba@797
  1964
          e = embedding[graph.oppositeArc(e)];
deba@797
  1965
        }
deba@797
  1966
deba@797
  1967
        if (face_size < 4) {
deba@797
  1968
          continue;
deba@797
  1969
        }
deba@797
  1970
deba@797
  1971
        typename Graph::Node s = graph.source(mine);
deba@797
  1972
        for (typename Graph::OutArcIt e(graph, s); e != INVALID; ++e) {
deba@797
  1973
          visited.set(graph.target(e), true);
deba@797
  1974
        }
deba@797
  1975
deba@797
  1976
        typename Graph::Arc oppe = INVALID;
deba@797
  1977
deba@797
  1978
        e = embedding[graph.oppositeArc(mine)];
deba@797
  1979
        e = embedding[graph.oppositeArc(e)];
deba@797
  1980
        while (graph.target(e) != s) {
deba@797
  1981
          if (visited[graph.source(e)]) {
deba@797
  1982
            oppe = e;
deba@797
  1983
            break;
deba@797
  1984
          }
deba@797
  1985
          e = embedding[graph.oppositeArc(e)];
deba@797
  1986
        }
deba@797
  1987
        visited.setAll(false);
deba@797
  1988
deba@797
  1989
        if (oppe == INVALID) {
deba@797
  1990
deba@797
  1991
          e = embedding[graph.oppositeArc(mine)];
deba@797
  1992
          typename Graph::Arc pn = mine, p = e;
deba@797
  1993
deba@797
  1994
          e = embedding[graph.oppositeArc(e)];
deba@797
  1995
          while (graph.target(e) != s) {
deba@797
  1996
            typename Graph::Arc n =
deba@797
  1997
              graph.direct(graph.addEdge(s, graph.source(e)), true);
deba@797
  1998
deba@797
  1999
            embedding[n] = pn;
deba@797
  2000
            embedding[graph.oppositeArc(n)] = e;
deba@797
  2001
            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
deba@797
  2002
deba@797
  2003
            pn = n;
deba@797
  2004
deba@797
  2005
            p = e;
deba@797
  2006
            e = embedding[graph.oppositeArc(e)];
deba@797
  2007
          }
deba@797
  2008
deba@797
  2009
          embedding[graph.oppositeArc(e)] = pn;
deba@797
  2010
deba@797
  2011
        } else {
deba@797
  2012
deba@797
  2013
          mine = embedding[graph.oppositeArc(mine)];
deba@797
  2014
          s = graph.source(mine);
deba@797
  2015
          oppe = embedding[graph.oppositeArc(oppe)];
deba@797
  2016
          typename Graph::Node t = graph.source(oppe);
deba@797
  2017
deba@797
  2018
          typename Graph::Arc ce = graph.direct(graph.addEdge(s, t), true);
deba@797
  2019
          embedding[ce] = mine;
deba@797
  2020
          embedding[graph.oppositeArc(ce)] = oppe;
deba@797
  2021
deba@797
  2022
          typename Graph::Arc pn = ce, p = oppe;
deba@797
  2023
          e = embedding[graph.oppositeArc(oppe)];
deba@797
  2024
          while (graph.target(e) != s) {
deba@797
  2025
            typename Graph::Arc n =
deba@797
  2026
              graph.direct(graph.addEdge(s, graph.source(e)), true);
deba@797
  2027
deba@797
  2028
            embedding[n] = pn;
deba@797
  2029
            embedding[graph.oppositeArc(n)] = e;
deba@797
  2030
            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
deba@797
  2031
deba@797
  2032
            pn = n;
deba@797
  2033
deba@797
  2034
            p = e;
deba@797
  2035
            e = embedding[graph.oppositeArc(e)];
deba@797
  2036
deba@797
  2037
          }
deba@797
  2038
          embedding[graph.oppositeArc(e)] = pn;
deba@797
  2039
deba@797
  2040
          pn = graph.oppositeArc(ce), p = mine;
deba@797
  2041
          e = embedding[graph.oppositeArc(mine)];
deba@797
  2042
          while (graph.target(e) != t) {
deba@797
  2043
            typename Graph::Arc n =
deba@797
  2044
              graph.direct(graph.addEdge(t, graph.source(e)), true);
deba@797
  2045
deba@797
  2046
            embedding[n] = pn;
deba@797
  2047
            embedding[graph.oppositeArc(n)] = e;
deba@797
  2048
            embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
deba@797
  2049
deba@797
  2050
            pn = n;
deba@797
  2051
deba@797
  2052
            p = e;
deba@797
  2053
            e = embedding[graph.oppositeArc(e)];
deba@797
  2054
deba@797
  2055
          }
deba@797
  2056
          embedding[graph.oppositeArc(e)] = pn;
deba@797
  2057
        }
deba@797
  2058
      }
deba@797
  2059
    }
deba@797
  2060
deba@797
  2061
  }
deba@797
  2062
deba@797
  2063
  /// \ingroup planar
deba@797
  2064
  ///
deba@797
  2065
  /// \brief Schnyder's planar drawing algorithm
deba@797
  2066
  ///
deba@797
  2067
  /// The planar drawing algorithm calculates positions for the nodes
kpeter@828
  2068
  /// in the plane. These coordinates satisfy that if the edges are
kpeter@828
  2069
  /// represented with straight lines, then they will not intersect
deba@797
  2070
  /// each other.
deba@797
  2071
  ///
kpeter@828
  2072
  /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
kpeter@828
  2073
  /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
deba@797
  2074
  /// The time complexity of the algorithm is O(n).
kpeter@828
  2075
  ///
kpeter@828
  2076
  /// \see PlanarEmbedding
deba@797
  2077
  template <typename Graph>
deba@797
  2078
  class PlanarDrawing {
deba@797
  2079
  public:
deba@797
  2080
deba@797
  2081
    TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@797
  2082
kpeter@828
  2083
    /// \brief The point type for storing coordinates
deba@797
  2084
    typedef dim2::Point<int> Point;
kpeter@828
  2085
    /// \brief The map type for storing the coordinates of the nodes
deba@797
  2086
    typedef typename Graph::template NodeMap<Point> PointMap;
deba@797
  2087
deba@797
  2088
deba@797
  2089
    /// \brief Constructor
deba@797
  2090
    ///
deba@797
  2091
    /// Constructor
kpeter@828
  2092
    /// \pre The graph must be simple, i.e. it should not
kpeter@828
  2093
    /// contain parallel or loop arcs.
deba@797
  2094
    PlanarDrawing(const Graph& graph)
deba@797
  2095
      : _graph(graph), _point_map(graph) {}
deba@797
  2096
deba@797
  2097
  private:
deba@797
  2098
deba@797
  2099
    template <typename AuxGraph, typename AuxEmbeddingMap>
deba@797
  2100
    void drawing(const AuxGraph& graph,
deba@797
  2101
                 const AuxEmbeddingMap& next,
deba@797
  2102
                 PointMap& point_map) {
deba@797
  2103
      TEMPLATE_GRAPH_TYPEDEFS(AuxGraph);
deba@797
  2104
deba@797
  2105
      typename AuxGraph::template ArcMap<Arc> prev(graph);
deba@797
  2106
deba@797
  2107
      for (NodeIt n(graph); n != INVALID; ++n) {
deba@797
  2108
        Arc e = OutArcIt(graph, n);
deba@797
  2109
deba@797
  2110
        Arc p = e, l = e;
deba@797
  2111
deba@797
  2112
        e = next[e];
deba@797
  2113
        while (e != l) {
deba@797
  2114
          prev[e] = p;
deba@797
  2115
          p = e;
deba@797
  2116
          e = next[e];
deba@797
  2117
        }
deba@797
  2118
        prev[e] = p;
deba@797
  2119
      }
deba@797
  2120
deba@797
  2121
      Node anode, bnode, cnode;
deba@797
  2122
deba@797
  2123
      {
deba@797
  2124
        Arc e = ArcIt(graph);
deba@797
  2125
        anode = graph.source(e);
deba@797
  2126
        bnode = graph.target(e);
deba@797
  2127
        cnode = graph.target(next[graph.oppositeArc(e)]);
deba@797
  2128
      }
deba@797
  2129
deba@797
  2130
      IterableBoolMap<AuxGraph, Node> proper(graph, false);
deba@797
  2131
      typename AuxGraph::template NodeMap<int> conn(graph, -1);
deba@797
  2132
deba@797
  2133
      conn[anode] = conn[bnode] = -2;
deba@797
  2134
      {
deba@797
  2135
        for (OutArcIt e(graph, anode); e != INVALID; ++e) {
deba@797
  2136
          Node m = graph.target(e);
deba@797
  2137
          if (conn[m] == -1) {
deba@797
  2138
            conn[m] = 1;
deba@797
  2139
          }
deba@797
  2140
        }
deba@797
  2141
        conn[cnode] = 2;
deba@797
  2142
deba@797
  2143
        for (OutArcIt e(graph, bnode); e != INVALID; ++e) {
deba@797
  2144
          Node m = graph.target(e);
deba@797
  2145
          if (conn[m] == -1) {
deba@797
  2146
            conn[m] = 1;
deba@797
  2147
          } else if (conn[m] != -2) {
deba@797
  2148
            conn[m] += 1;
deba@797
  2149
            Arc pe = graph.oppositeArc(e);
deba@797
  2150
            if (conn[graph.target(next[pe])] == -2) {
deba@797
  2151
              conn[m] -= 1;
deba@797
  2152
            }
deba@797
  2153
            if (conn[graph.target(prev[pe])] == -2) {
deba@797
  2154
              conn[m] -= 1;
deba@797
  2155
            }
deba@797
  2156
deba@797
  2157
            proper.set(m, conn[m] == 1);
deba@797
  2158
          }
deba@797
  2159
        }
deba@797
  2160
      }
deba@797
  2161
deba@797
  2162
deba@797
  2163
      typename AuxGraph::template ArcMap<int> angle(graph, -1);
deba@797
  2164
deba@797
  2165
      while (proper.trueNum() != 0) {
deba@797
  2166
        Node n = typename IterableBoolMap<AuxGraph, Node>::TrueIt(proper);
deba@797
  2167
        proper.set(n, false);
deba@797
  2168
        conn[n] = -2;
deba@797
  2169
deba@797
  2170
        for (OutArcIt e(graph, n); e != INVALID; ++e) {
deba@797
  2171
          Node m = graph.target(e);
deba@797
  2172
          if (conn[m] == -1) {
deba@797
  2173
            conn[m] = 1;
deba@797
  2174
          } else if (conn[m] != -2) {
deba@797
  2175
            conn[m] += 1;
deba@797
  2176
            Arc pe = graph.oppositeArc(e);
deba@797
  2177
            if (conn[graph.target(next[pe])] == -2) {
deba@797
  2178
              conn[m] -= 1;
deba@797
  2179
            }
deba@797
  2180
            if (conn[graph.target(prev[pe])] == -2) {
deba@797
  2181
              conn[m] -= 1;
deba@797
  2182
            }
deba@797
  2183
deba@797
  2184
            proper.set(m, conn[m] == 1);
deba@797
  2185
          }
deba@797
  2186
        }
deba@797
  2187
deba@797
  2188
        {
deba@797
  2189
          Arc e = OutArcIt(graph, n);
deba@797
  2190
          Arc p = e, l = e;
deba@797
  2191
deba@797
  2192
          e = next[e];
deba@797
  2193
          while (e != l) {
deba@797
  2194
deba@797
  2195
            if (conn[graph.target(e)] == -2 && conn[graph.target(p)] == -2) {
deba@797
  2196
              Arc f = e;
deba@797
  2197
              angle[f] = 0;
deba@797
  2198
              f = next[graph.oppositeArc(f)];
deba@797
  2199
              angle[f] = 1;
deba@797
  2200
              f = next[graph.oppositeArc(f)];
deba@797
  2201
              angle[f] = 2;
deba@797
  2202
            }
deba@797
  2203
deba@797
  2204
            p = e;
deba@797
  2205
            e = next[e];
deba@797
  2206
          }
deba@797
  2207
deba@797
  2208
          if (conn[graph.target(e)] == -2 && conn[graph.target(p)] == -2) {
deba@797
  2209
            Arc f = e;
deba@797
  2210
            angle[f] = 0;
deba@797
  2211
            f = next[graph.oppositeArc(f)];
deba@797
  2212
            angle[f] = 1;
deba@797
  2213
            f = next[graph.oppositeArc(f)];
deba@797
  2214
            angle[f] = 2;
deba@797
  2215
          }
deba@797
  2216
        }
deba@797
  2217
      }
deba@797
  2218
deba@797
  2219
      typename AuxGraph::template NodeMap<Node> apred(graph, INVALID);
deba@797
  2220
      typename AuxGraph::template NodeMap<Node> bpred(graph, INVALID);
deba@797
  2221
      typename AuxGraph::template NodeMap<Node> cpred(graph, INVALID);
deba@797
  2222
deba@797
  2223
      typename AuxGraph::template NodeMap<int> apredid(graph, -1);
deba@797
  2224
      typename AuxGraph::template NodeMap<int> bpredid(graph, -1);
deba@797
  2225
      typename AuxGraph::template NodeMap<int> cpredid(graph, -1);
deba@797
  2226
deba@797
  2227
      for (ArcIt e(graph); e != INVALID; ++e) {
deba@797
  2228
        if (angle[e] == angle[next[e]]) {
deba@797
  2229
          switch (angle[e]) {
deba@797
  2230
          case 2:
deba@797
  2231
            apred[graph.target(e)] = graph.source(e);
deba@797
  2232
            apredid[graph.target(e)] = graph.id(graph.source(e));
deba@797
  2233
            break;
deba@797
  2234
          case 1:
deba@797
  2235
            bpred[graph.target(e)] = graph.source(e);
deba@797
  2236
            bpredid[graph.target(e)] = graph.id(graph.source(e));
deba@797
  2237
            break;
deba@797
  2238
          case 0:
deba@797
  2239
            cpred[graph.target(e)] = graph.source(e);
deba@797
  2240
            cpredid[graph.target(e)] = graph.id(graph.source(e));
deba@797
  2241
            break;
deba@797
  2242
          }
deba@797
  2243
        }
deba@797
  2244
      }
deba@797
  2245
deba@797
  2246
      cpred[anode] = INVALID;
deba@797
  2247
      cpred[bnode] = INVALID;
deba@797
  2248
deba@797
  2249
      std::vector<Node> aorder, border, corder;
deba@797
  2250
deba@797
  2251
      {
deba@797
  2252
        typename AuxGraph::template NodeMap<bool> processed(graph, false);
deba@797
  2253
        std::vector<Node> st;
deba@797
  2254
        for (NodeIt n(graph); n != INVALID; ++n) {
deba@797
  2255
          if (!processed[n] && n != bnode && n != cnode) {
deba@797
  2256
            st.push_back(n);
deba@797
  2257
            processed[n] = true;
deba@797
  2258
            Node m = apred[n];
deba@797
  2259
            while (m != INVALID && !processed[m]) {
deba@797
  2260
              st.push_back(m);
deba@797
  2261
              processed[m] = true;
deba@797
  2262
              m = apred[m];
deba@797
  2263
            }
deba@797
  2264
            while (!st.empty()) {
deba@797
  2265
              aorder.push_back(st.back());
deba@797
  2266
              st.pop_back();
deba@797
  2267
            }
deba@797
  2268
          }
deba@797
  2269
        }
deba@797
  2270
      }
deba@797
  2271
deba@797
  2272
      {
deba@797
  2273
        typename AuxGraph::template NodeMap<bool> processed(graph, false);
deba@797
  2274
        std::vector<Node> st;
deba@797
  2275
        for (NodeIt n(graph); n != INVALID; ++n) {
deba@797
  2276
          if (!processed[n] && n != cnode && n != anode) {
deba@797
  2277
            st.push_back(n);
deba@797
  2278
            processed[n] = true;
deba@797
  2279
            Node m = bpred[n];
deba@797
  2280
            while (m != INVALID && !processed[m]) {
deba@797
  2281
              st.push_back(m);
deba@797
  2282
              processed[m] = true;
deba@797
  2283
              m = bpred[m];
deba@797
  2284
            }
deba@797
  2285
            while (!st.empty()) {
deba@797
  2286
              border.push_back(st.back());
deba@797
  2287
              st.pop_back();
deba@797
  2288
            }
deba@797
  2289
          }
deba@797
  2290
        }
deba@797
  2291
      }
deba@797
  2292
deba@797
  2293
      {
deba@797
  2294
        typename AuxGraph::template NodeMap<bool> processed(graph, false);
deba@797
  2295
        std::vector<Node> st;
deba@797
  2296
        for (NodeIt n(graph); n != INVALID; ++n) {
deba@797
  2297
          if (!processed[n] && n != anode && n != bnode) {
deba@797
  2298
            st.push_back(n);
deba@797
  2299
            processed[n] = true;
deba@797
  2300
            Node m = cpred[n];
deba@797
  2301
            while (m != INVALID && !processed[m]) {
deba@797
  2302
              st.push_back(m);
deba@797
  2303
              processed[m] = true;
deba@797
  2304
              m = cpred[m];
deba@797
  2305
            }
deba@797
  2306
            while (!st.empty()) {
deba@797
  2307
              corder.push_back(st.back());
deba@797
  2308
              st.pop_back();
deba@797
  2309
            }
deba@797
  2310
          }
deba@797
  2311
        }
deba@797
  2312
      }
deba@797
  2313
deba@797
  2314
      typename AuxGraph::template NodeMap<int> atree(graph, 0);
deba@797
  2315
      for (int i = aorder.size() - 1; i >= 0; --i) {
deba@797
  2316
        Node n = aorder[i];
deba@797
  2317
        atree[n] = 1;
deba@797
  2318
        for (OutArcIt e(graph, n); e != INVALID; ++e) {
deba@797
  2319
          if (apred[graph.target(e)] == n) {
deba@797
  2320
            atree[n] += atree[graph.target(e)];
deba@797
  2321
          }
deba@797
  2322
        }
deba@797
  2323
      }
deba@797
  2324
deba@797
  2325
      typename AuxGraph::template NodeMap<int> btree(graph, 0);
deba@797
  2326
      for (int i = border.size() - 1; i >= 0; --i) {
deba@797
  2327
        Node n = border[i];
deba@797
  2328
        btree[n] = 1;
deba@797
  2329
        for (OutArcIt e(graph, n); e != INVALID; ++e) {
deba@797
  2330
          if (bpred[graph.target(e)] == n) {
deba@797
  2331
            btree[n] += btree[graph.target(e)];
deba@797
  2332
          }
deba@797
  2333
        }
deba@797
  2334
      }
deba@797
  2335
deba@797
  2336
      typename AuxGraph::template NodeMap<int> apath(graph, 0);
deba@797
  2337
      apath[bnode] = apath[cnode] = 1;
deba@797
  2338
      typename AuxGraph::template NodeMap<int> apath_btree(graph, 0);
deba@797
  2339
      apath_btree[bnode] = btree[bnode];
deba@797
  2340
      for (int i = 1; i < int(aorder.size()); ++i) {
deba@797
  2341
        Node n = aorder[i];
deba@797
  2342
        apath[n] = apath[apred[n]] + 1;
deba@797
  2343
        apath_btree[n] = btree[n] + apath_btree[apred[n]];
deba@797
  2344
      }
deba@797
  2345
deba@797
  2346
      typename AuxGraph::template NodeMap<int> bpath_atree(graph, 0);
deba@797
  2347
      bpath_atree[anode] = atree[anode];
deba@797
  2348
      for (int i = 1; i < int(border.size()); ++i) {
deba@797
  2349
        Node n = border[i];
deba@797
  2350
        bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
deba@797
  2351
      }
deba@797
  2352
deba@797
  2353
      typename AuxGraph::template NodeMap<int> cpath(graph, 0);
deba@797
  2354
      cpath[anode] = cpath[bnode] = 1;
deba@797
  2355
      typename AuxGraph::template NodeMap<int> cpath_atree(graph, 0);
deba@797
  2356
      cpath_atree[anode] = atree[anode];
deba@797
  2357
      typename AuxGraph::template NodeMap<int> cpath_btree(graph, 0);
deba@797
  2358
      cpath_btree[bnode] = btree[bnode];
deba@797
  2359
      for (int i = 1; i < int(corder.size()); ++i) {
deba@797
  2360
        Node n = corder[i];
deba@797
  2361
        cpath[n] = cpath[cpred[n]] + 1;
deba@797
  2362
        cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
deba@797
  2363
        cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
deba@797
  2364
      }
deba@797
  2365
deba@797
  2366
      typename AuxGraph::template NodeMap<int> third(graph);
deba@797
  2367
      for (NodeIt n(graph); n != INVALID; ++n) {
deba@797
  2368
        point_map[n].x =
deba@797
  2369
          bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
deba@797
  2370
        point_map[n].y =
deba@797
  2371
          cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
deba@797
  2372
      }
deba@797
  2373
deba@797
  2374
    }
deba@797
  2375
deba@797
  2376
  public:
deba@797
  2377
kpeter@828
  2378
    /// \brief Calculate the node positions
deba@797
  2379
    ///
kpeter@828
  2380
    /// This function calculates the node positions on the plane.
kpeter@828
  2381
    /// \return \c true if the graph is planar.
deba@797
  2382
    bool run() {
deba@797
  2383
      PlanarEmbedding<Graph> pe(_graph);
deba@797
  2384
      if (!pe.run()) return false;
deba@797
  2385
deba@797
  2386
      run(pe);
deba@797
  2387
      return true;
deba@797
  2388
    }
deba@797
  2389
kpeter@828
  2390
    /// \brief Calculate the node positions according to a
deba@797
  2391
    /// combinatorical embedding
deba@797
  2392
    ///
kpeter@828
  2393
    /// This function calculates the node positions on the plane.
kpeter@828
  2394
    /// The given \c embedding map should contain a valid combinatorical
kpeter@828
  2395
    /// embedding, i.e. a valid cyclic order of the arcs.
kpeter@828
  2396
    /// It can be computed using PlanarEmbedding.
deba@797
  2397
    template <typename EmbeddingMap>
deba@797
  2398
    void run(const EmbeddingMap& embedding) {
deba@797
  2399
      typedef SmartEdgeSet<Graph> AuxGraph;
deba@797
  2400
deba@797
  2401
      if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {
deba@797
  2402
        drawing(_graph, embedding, _point_map);
deba@797
  2403
        return;
deba@797
  2404
      }
deba@797
  2405
deba@797
  2406
      AuxGraph aux_graph(_graph);
deba@797
  2407
      typename AuxGraph::template ArcMap<typename AuxGraph::Arc>
deba@797
  2408
        aux_embedding(aux_graph);
deba@797
  2409
deba@797
  2410
      {
deba@797
  2411
deba@797
  2412
        typename Graph::template EdgeMap<typename AuxGraph::Edge>
deba@797
  2413
          ref(_graph);
deba@797
  2414
deba@797
  2415
        for (EdgeIt e(_graph); e != INVALID; ++e) {
deba@797
  2416
          ref[e] = aux_graph.addEdge(_graph.u(e), _graph.v(e));
deba@797
  2417
        }
deba@797
  2418
deba@797
  2419
        for (EdgeIt e(_graph); e != INVALID; ++e) {
deba@797
  2420
          Arc ee = embedding[_graph.direct(e, true)];
deba@797
  2421
          aux_embedding[aux_graph.direct(ref[e], true)] =
deba@797
  2422
            aux_graph.direct(ref[ee], _graph.direction(ee));
deba@797
  2423
          ee = embedding[_graph.direct(e, false)];
deba@797
  2424
          aux_embedding[aux_graph.direct(ref[e], false)] =
deba@797
  2425
            aux_graph.direct(ref[ee], _graph.direction(ee));
deba@797
  2426
        }
deba@797
  2427
      }
deba@797
  2428
      _planarity_bits::makeConnected(aux_graph, aux_embedding);
deba@797
  2429
      _planarity_bits::makeBiNodeConnected(aux_graph, aux_embedding);
deba@797
  2430
      _planarity_bits::makeMaxPlanar(aux_graph, aux_embedding);
deba@797
  2431
      drawing(aux_graph, aux_embedding, _point_map);
deba@797
  2432
    }
deba@797
  2433
deba@797
  2434
    /// \brief The coordinate of the given node
deba@797
  2435
    ///
kpeter@828
  2436
    /// This function returns the coordinate of the given node.
deba@797
  2437
    Point operator[](const Node& node) const {
deba@797
  2438
      return _point_map[node];
deba@797
  2439
    }
deba@797
  2440
kpeter@828
  2441
    /// \brief Return the grid embedding in a node map
deba@797
  2442
    ///
kpeter@828
  2443
    /// This function returns the grid embedding in a node map of
kpeter@828
  2444
    /// \c dim2::Point<int> coordinates.
deba@797
  2445
    const PointMap& coords() const {
deba@797
  2446
      return _point_map;
deba@797
  2447
    }
deba@797
  2448
deba@797
  2449
  private:
deba@797
  2450
deba@797
  2451
    const Graph& _graph;
deba@797
  2452
    PointMap _point_map;
deba@797
  2453
deba@797
  2454
  };
deba@797
  2455
deba@797
  2456
  namespace _planarity_bits {
deba@797
  2457
deba@797
  2458
    template <typename ColorMap>
deba@797
  2459
    class KempeFilter {
deba@797
  2460
    public:
deba@797
  2461
      typedef typename ColorMap::Key Key;
deba@797
  2462
      typedef bool Value;
deba@797
  2463
deba@797
  2464
      KempeFilter(const ColorMap& color_map,
deba@797
  2465
                  const typename ColorMap::Value& first,
deba@797
  2466
                  const typename ColorMap::Value& second)
deba@797
  2467
        : _color_map(color_map), _first(first), _second(second) {}
deba@797
  2468
deba@797
  2469
      Value operator[](const Key& key) const {
deba@797
  2470
        return _color_map[key] == _first || _color_map[key] == _second;
deba@797
  2471
      }
deba@797
  2472
deba@797
  2473
    private:
deba@797
  2474
      const ColorMap& _color_map;
deba@797
  2475
      typename ColorMap::Value _first, _second;
deba@797
  2476
    };
deba@797
  2477
  }
deba@797
  2478
deba@797
  2479
  /// \ingroup planar
deba@797
  2480
  ///
deba@797
  2481
  /// \brief Coloring planar graphs
deba@797
  2482
  ///
deba@797
  2483
  /// The graph coloring problem is the coloring of the graph nodes
kpeter@828
  2484
  /// so that there are no adjacent nodes with the same color. The
kpeter@828
  2485
  /// planar graphs can always be colored with four colors, which is
kpeter@828
  2486
  /// proved by Appel and Haken. Their proofs provide a quadratic
deba@797
  2487
  /// time algorithm for four coloring, but it could not be used to
kpeter@828
  2488
  /// implement an efficient algorithm. The five and six coloring can be
kpeter@828
  2489
  /// made in linear time, but in this class, the five coloring has
deba@797
  2490
  /// quadratic worst case time complexity. The two coloring (if
deba@797
  2491
  /// possible) is solvable with a graph search algorithm and it is
deba@797
  2492
  /// implemented in \ref bipartitePartitions() function in LEMON. To
kpeter@828
  2493
  /// decide whether a planar graph is three colorable is NP-complete.
deba@797
  2494
  ///
deba@797
  2495
  /// This class contains member functions for calculate colorings
deba@797
  2496
  /// with five and six colors. The six coloring algorithm is a simple
deba@797
  2497
  /// greedy coloring on the backward minimum outgoing order of nodes.
kpeter@828
  2498
  /// This order can be computed by selecting the node with least
kpeter@828
  2499
  /// outgoing arcs to unprocessed nodes in each phase. This order
deba@797
  2500
  /// guarantees that when a node is chosen for coloring it has at
deba@797
  2501
  /// most five already colored adjacents. The five coloring algorithm
deba@797
  2502
  /// use the same method, but if the greedy approach fails to color
deba@797
  2503
  /// with five colors, i.e. the node has five already different
deba@797
  2504
  /// colored neighbours, it swaps the colors in one of the connected
deba@797
  2505
  /// two colored sets with the Kempe recoloring method.
deba@797
  2506
  template <typename Graph>
deba@797
  2507
  class PlanarColoring {
deba@797
  2508
  public:
deba@797
  2509
deba@797
  2510
    TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@797
  2511
kpeter@828
  2512
    /// \brief The map type for storing color indices
deba@797
  2513
    typedef typename Graph::template NodeMap<int> IndexMap;
kpeter@828
  2514
    /// \brief The map type for storing colors
kpeter@828
  2515
    ///
kpeter@828
  2516
    /// The map type for storing colors.
kpeter@828
  2517
    /// \see Palette, Color
deba@797
  2518
    typedef ComposeMap<Palette, IndexMap> ColorMap;
deba@797
  2519
deba@797
  2520
    /// \brief Constructor
deba@797
  2521
    ///
kpeter@828
  2522
    /// Constructor.
kpeter@828
  2523
    /// \pre The graph must be simple, i.e. it should not
kpeter@828
  2524
    /// contain parallel or loop arcs.
deba@797
  2525
    PlanarColoring(const Graph& graph)
deba@797
  2526
      : _graph(graph), _color_map(graph), _palette(0) {
deba@797
  2527
      _palette.add(Color(1,0,0));
deba@797
  2528
      _palette.add(Color(0,1,0));
deba@797
  2529
      _palette.add(Color(0,0,1));
deba@797
  2530
      _palette.add(Color(1,1,0));
deba@797
  2531
      _palette.add(Color(1,0,1));
deba@797
  2532
      _palette.add(Color(0,1,1));
deba@797
  2533
    }
deba@797
  2534
kpeter@828
  2535
    /// \brief Return the node map of color indices
deba@797
  2536
    ///
kpeter@828
  2537
    /// This function returns the node map of color indices. The values are
kpeter@828
  2538
    /// in the range \c [0..4] or \c [0..5] according to the coloring method.
deba@797
  2539
    IndexMap colorIndexMap() const {
deba@797
  2540
      return _color_map;
deba@797
  2541
    }
deba@797
  2542
kpeter@828
  2543
    /// \brief Return the node map of colors
deba@797
  2544
    ///
kpeter@828
  2545
    /// This function returns the node map of colors. The values are among
kpeter@828
  2546
    /// five or six distinct \ref lemon::Color "colors".
deba@797
  2547
    ColorMap colorMap() const {
deba@797
  2548
      return composeMap(_palette, _color_map);
deba@797
  2549
    }
deba@797
  2550
kpeter@828
  2551
    /// \brief Return the color index of the node
deba@797
  2552
    ///
kpeter@828
  2553
    /// This function returns the color index of the given node. The value is
kpeter@828
  2554
    /// in the range \c [0..4] or \c [0..5] according to the coloring method.
deba@797
  2555
    int colorIndex(const Node& node) const {
deba@797
  2556
      return _color_map[node];
deba@797
  2557
    }
deba@797
  2558
kpeter@828
  2559
    /// \brief Return the color of the node
deba@797
  2560
    ///
kpeter@828
  2561
    /// This function returns the color of the given node. The value is among
kpeter@828
  2562
    /// five or six distinct \ref lemon::Color "colors".
deba@797
  2563
    Color color(const Node& node) const {
deba@797
  2564
      return _palette[_color_map[node]];
deba@797
  2565
    }
deba@797
  2566
deba@797
  2567
kpeter@828
  2568
    /// \brief Calculate a coloring with at most six colors
deba@797
  2569
    ///
deba@797
  2570
    /// This function calculates a coloring with at most six colors. The time
deba@797
  2571
    /// complexity of this variant is linear in the size of the graph.
kpeter@828
  2572
    /// \return \c true if the algorithm could color the graph with six colors.
kpeter@828
  2573
    /// If the algorithm fails, then the graph is not planar.
kpeter@828
  2574
    /// \note This function can return \c true if the graph is not
kpeter@828
  2575
    /// planar, but it can be colored with at most six colors.
deba@797
  2576
    bool runSixColoring() {
deba@797
  2577
deba@797
  2578
      typename Graph::template NodeMap<int> heap_index(_graph, -1);
deba@797
  2579
      BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
deba@797
  2580
deba@797
  2581
      for (NodeIt n(_graph); n != INVALID; ++n) {
deba@797
  2582
        _color_map[n] = -2;
deba@797
  2583
        heap.push(n, countOutArcs(_graph, n));
deba@797
  2584
      }
deba@797
  2585
deba@797
  2586
      std::vector<Node> order;
deba@797
  2587
deba@797
  2588
      while (!heap.empty()) {
deba@797
  2589
        Node n = heap.top();
deba@797
  2590
        heap.pop();
deba@797
  2591
        _color_map[n] = -1;
deba@797
  2592
        order.push_back(n);
deba@797
  2593
        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
deba@797
  2594
          Node t = _graph.runningNode(e);
deba@797
  2595
          if (_color_map[t] == -2) {
deba@797
  2596
            heap.decrease(t, heap[t] - 1);
deba@797
  2597
          }
deba@797
  2598
        }
deba@797
  2599
      }
deba@797
  2600
deba@797
  2601
      for (int i = order.size() - 1; i >= 0; --i) {
deba@797
  2602
        std::vector<bool> forbidden(6, false);
deba@797
  2603
        for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {
deba@797
  2604
          Node t = _graph.runningNode(e);
deba@797
  2605
          if (_color_map[t] != -1) {
deba@797
  2606
            forbidden[_color_map[t]] = true;
deba@797
  2607
          }
deba@797
  2608
        }
deba@797
  2609
               for (int k = 0; k < 6; ++k) {
deba@797
  2610
          if (!forbidden[k]) {
deba@797
  2611
            _color_map[order[i]] = k;
deba@797
  2612
            break;
deba@797
  2613
          }
deba@797
  2614
        }
deba@797
  2615
        if (_color_map[order[i]] == -1) {
deba@797
  2616
          return false;
deba@797
  2617
        }
deba@797
  2618
      }
deba@797
  2619
      return true;
deba@797
  2620
    }
deba@797
  2621
deba@797
  2622
  private:
deba@797
  2623
deba@797
  2624
    bool recolor(const Node& u, const Node& v) {
deba@797
  2625
      int ucolor = _color_map[u];
deba@797
  2626
      int vcolor = _color_map[v];
deba@797
  2627
      typedef _planarity_bits::KempeFilter<IndexMap> KempeFilter;
deba@797
  2628
      KempeFilter filter(_color_map, ucolor, vcolor);
deba@797
  2629
deba@797
  2630
      typedef FilterNodes<const Graph, const KempeFilter> KempeGraph;
deba@797
  2631
      KempeGraph kempe_graph(_graph, filter);
deba@797
  2632
deba@797
  2633
      std::vector<Node> comp;
deba@797
  2634
      Bfs<KempeGraph> bfs(kempe_graph);
deba@797
  2635
      bfs.init();
deba@797
  2636
      bfs.addSource(u);
deba@797
  2637
      while (!bfs.emptyQueue()) {
deba@797
  2638
        Node n = bfs.nextNode();
deba@797
  2639
        if (n == v) return false;
deba@797
  2640
        comp.push_back(n);
deba@797
  2641
        bfs.processNextNode();
deba@797
  2642
      }
deba@797
  2643
deba@797
  2644
      int scolor = ucolor + vcolor;
deba@797
  2645
      for (int i = 0; i < static_cast<int>(comp.size()); ++i) {
deba@797
  2646
        _color_map[comp[i]] = scolor - _color_map[comp[i]];
deba@797
  2647
      }
deba@797
  2648
deba@797
  2649
      return true;
deba@797
  2650
    }
deba@797
  2651
deba@797
  2652
    template <typename EmbeddingMap>
deba@797
  2653
    void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) {
deba@797
  2654
      std::vector<Node> nodes;
deba@797
  2655
      nodes.reserve(4);
deba@797
  2656
deba@797
  2657
      for (Arc e = OutArcIt(_graph, node); e != INVALID; e = embedding[e]) {
deba@797
  2658
        Node t = _graph.target(e);
deba@797
  2659
        if (_color_map[t] != -1) {
deba@797
  2660
          nodes.push_back(t);
deba@797
  2661
          if (nodes.size() == 4) break;
deba@797
  2662
        }
deba@797
  2663
      }
deba@797
  2664
deba@797
  2665
      int color = _color_map[nodes[0]];
deba@797
  2666
      if (recolor(nodes[0], nodes[2])) {
deba@797
  2667
        _color_map[node] = color;
deba@797
  2668
      } else {
deba@797
  2669
        color = _color_map[nodes[1]];
deba@797
  2670
        recolor(nodes[1], nodes[3]);
deba@797
  2671
        _color_map[node] = color;
deba@797
  2672
      }
deba@797
  2673
    }
deba@797
  2674
deba@797
  2675
  public:
deba@797
  2676
kpeter@828
  2677
    /// \brief Calculate a coloring with at most five colors
deba@797
  2678
    ///
deba@797
  2679
    /// This function calculates a coloring with at most five
deba@797
  2680
    /// colors. The worst case time complexity of this variant is
deba@797
  2681
    /// quadratic in the size of the graph.
kpeter@828
  2682
    /// \param embedding This map should contain a valid combinatorical
kpeter@828
  2683
    /// embedding, i.e. a valid cyclic order of the arcs.
kpeter@828
  2684
    /// It can be computed using PlanarEmbedding.
deba@797
  2685
    template <typename EmbeddingMap>
deba@797
  2686
    void runFiveColoring(const EmbeddingMap& embedding) {
deba@797
  2687
deba@797
  2688
      typename Graph::template NodeMap<int> heap_index(_graph, -1);
deba@797
  2689
      BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
deba@797
  2690
deba@797
  2691
      for (NodeIt n(_graph); n != INVALID; ++n) {
deba@797
  2692
        _color_map[n] = -2;
deba@797
  2693
        heap.push(n, countOutArcs(_graph, n));
deba@797
  2694
      }
deba@797
  2695
deba@797
  2696
      std::vector<Node> order;
deba@797
  2697
deba@797
  2698
      while (!heap.empty()) {
deba@797
  2699
        Node n = heap.top();
deba@797
  2700
        heap.pop();
deba@797
  2701
        _color_map[n] = -1;
deba@797
  2702
        order.push_back(n);
deba@797
  2703
        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
deba@797
  2704
          Node t = _graph.runningNode(e);
deba@797
  2705
          if (_color_map[t] == -2) {
deba@797
  2706
            heap.decrease(t, heap[t] - 1);
deba@797
  2707
          }
deba@797
  2708
        }
deba@797
  2709
      }
deba@797
  2710
deba@797
  2711
      for (int i = order.size() - 1; i >= 0; --i) {
deba@797
  2712
        std::vector<bool> forbidden(5, false);
deba@797
  2713
        for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {
deba@797
  2714
          Node t = _graph.runningNode(e);
deba@797
  2715
          if (_color_map[t] != -1) {
deba@797
  2716
            forbidden[_color_map[t]] = true;
deba@797
  2717
          }
deba@797
  2718
        }
deba@797
  2719
        for (int k = 0; k < 5; ++k) {
deba@797
  2720
          if (!forbidden[k]) {
deba@797
  2721
            _color_map[order[i]] = k;
deba@797
  2722
            break;
deba@797
  2723
          }
deba@797
  2724
        }
deba@797
  2725
        if (_color_map[order[i]] == -1) {
deba@797
  2726
          kempeRecoloring(order[i], embedding);
deba@797
  2727
        }
deba@797
  2728
      }
deba@797
  2729
    }
deba@797
  2730
kpeter@828
  2731
    /// \brief Calculate a coloring with at most five colors
deba@797
  2732
    ///
deba@797
  2733
    /// This function calculates a coloring with at most five
deba@797
  2734
    /// colors. The worst case time complexity of this variant is
deba@797
  2735
    /// quadratic in the size of the graph.
kpeter@828
  2736
    /// \return \c true if the graph is planar.
deba@797
  2737
    bool runFiveColoring() {
deba@797
  2738
      PlanarEmbedding<Graph> pe(_graph);
deba@797
  2739
      if (!pe.run()) return false;
deba@797
  2740
deba@797
  2741
      runFiveColoring(pe.embeddingMap());
deba@797
  2742
      return true;
deba@797
  2743
    }
deba@797
  2744
deba@797
  2745
  private:
deba@797
  2746
deba@797
  2747
    const Graph& _graph;
deba@797
  2748
    IndexMap _color_map;
deba@797
  2749
    Palette _palette;
deba@797
  2750
  };
deba@797
  2751
deba@797
  2752
}
deba@797
  2753
deba@797
  2754
#endif