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