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