1.1 --- a/lemon/planarity.h Wed Sep 09 15:32:03 2009 +0200
1.2 +++ b/lemon/planarity.h Sun Oct 04 10:15:32 2009 +0200
1.3 @@ -137,395 +137,395 @@
1.4 typename Graph::Arc prev, next;
1.5 };
1.6
1.7 + template <typename Graph>
1.8 + class PlanarityChecking {
1.9 + private:
1.10 +
1.11 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.12 +
1.13 + const Graph& _graph;
1.14 +
1.15 + private:
1.16 +
1.17 + typedef typename Graph::template NodeMap<Arc> PredMap;
1.18 +
1.19 + typedef typename Graph::template EdgeMap<bool> TreeMap;
1.20 +
1.21 + typedef typename Graph::template NodeMap<int> OrderMap;
1.22 + typedef std::vector<Node> OrderList;
1.23 +
1.24 + typedef typename Graph::template NodeMap<int> LowMap;
1.25 + typedef typename Graph::template NodeMap<int> AncestorMap;
1.26 +
1.27 + typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
1.28 + typedef std::vector<NodeDataNode> NodeData;
1.29 +
1.30 + typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
1.31 + typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
1.32 +
1.33 + typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
1.34 +
1.35 + typedef typename Graph::template NodeMap<bool> EmbedArc;
1.36 +
1.37 + public:
1.38 +
1.39 + PlanarityChecking(const Graph& graph) : _graph(graph) {}
1.40 +
1.41 + bool run() {
1.42 + typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
1.43 +
1.44 + PredMap pred_map(_graph, INVALID);
1.45 + TreeMap tree_map(_graph, false);
1.46 +
1.47 + OrderMap order_map(_graph, -1);
1.48 + OrderList order_list;
1.49 +
1.50 + AncestorMap ancestor_map(_graph, -1);
1.51 + LowMap low_map(_graph, -1);
1.52 +
1.53 + Visitor visitor(_graph, pred_map, tree_map,
1.54 + order_map, order_list, ancestor_map, low_map);
1.55 + DfsVisit<Graph, Visitor> visit(_graph, visitor);
1.56 + visit.run();
1.57 +
1.58 + ChildLists child_lists(_graph);
1.59 + createChildLists(tree_map, order_map, low_map, child_lists);
1.60 +
1.61 + NodeData node_data(2 * order_list.size());
1.62 +
1.63 + EmbedArc embed_arc(_graph, false);
1.64 +
1.65 + MergeRoots merge_roots(_graph);
1.66 +
1.67 + for (int i = order_list.size() - 1; i >= 0; --i) {
1.68 +
1.69 + Node node = order_list[i];
1.70 +
1.71 + Node source = node;
1.72 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.73 + Node target = _graph.target(e);
1.74 +
1.75 + if (order_map[source] < order_map[target] && tree_map[e]) {
1.76 + initFace(target, node_data, order_map, order_list);
1.77 + }
1.78 + }
1.79 +
1.80 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.81 + Node target = _graph.target(e);
1.82 +
1.83 + if (order_map[source] < order_map[target] && !tree_map[e]) {
1.84 + embed_arc[target] = true;
1.85 + walkUp(target, source, i, pred_map, low_map,
1.86 + order_map, order_list, node_data, merge_roots);
1.87 + }
1.88 + }
1.89 +
1.90 + for (typename MergeRoots::Value::iterator it =
1.91 + merge_roots[node].begin();
1.92 + it != merge_roots[node].end(); ++it) {
1.93 + int rn = *it;
1.94 + walkDown(rn, i, node_data, order_list, child_lists,
1.95 + ancestor_map, low_map, embed_arc, merge_roots);
1.96 + }
1.97 + merge_roots[node].clear();
1.98 +
1.99 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.100 + Node target = _graph.target(e);
1.101 +
1.102 + if (order_map[source] < order_map[target] && !tree_map[e]) {
1.103 + if (embed_arc[target]) {
1.104 + return false;
1.105 + }
1.106 + }
1.107 + }
1.108 + }
1.109 +
1.110 + return true;
1.111 + }
1.112 +
1.113 + private:
1.114 +
1.115 + void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
1.116 + const LowMap& low_map, ChildLists& child_lists) {
1.117 +
1.118 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.119 + Node source = n;
1.120 +
1.121 + std::vector<Node> targets;
1.122 + for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.123 + Node target = _graph.target(e);
1.124 +
1.125 + if (order_map[source] < order_map[target] && tree_map[e]) {
1.126 + targets.push_back(target);
1.127 + }
1.128 + }
1.129 +
1.130 + if (targets.size() == 0) {
1.131 + child_lists[source].first = INVALID;
1.132 + } else if (targets.size() == 1) {
1.133 + child_lists[source].first = targets[0];
1.134 + child_lists[targets[0]].prev = INVALID;
1.135 + child_lists[targets[0]].next = INVALID;
1.136 + } else {
1.137 + radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
1.138 + for (int i = 1; i < int(targets.size()); ++i) {
1.139 + child_lists[targets[i]].prev = targets[i - 1];
1.140 + child_lists[targets[i - 1]].next = targets[i];
1.141 + }
1.142 + child_lists[targets.back()].next = INVALID;
1.143 + child_lists[targets.front()].prev = INVALID;
1.144 + child_lists[source].first = targets.front();
1.145 + }
1.146 + }
1.147 + }
1.148 +
1.149 + void walkUp(const Node& node, Node root, int rorder,
1.150 + const PredMap& pred_map, const LowMap& low_map,
1.151 + const OrderMap& order_map, const OrderList& order_list,
1.152 + NodeData& node_data, MergeRoots& merge_roots) {
1.153 +
1.154 + int na, nb;
1.155 + bool da, db;
1.156 +
1.157 + na = nb = order_map[node];
1.158 + da = true; db = false;
1.159 +
1.160 + while (true) {
1.161 +
1.162 + if (node_data[na].visited == rorder) break;
1.163 + if (node_data[nb].visited == rorder) break;
1.164 +
1.165 + node_data[na].visited = rorder;
1.166 + node_data[nb].visited = rorder;
1.167 +
1.168 + int rn = -1;
1.169 +
1.170 + if (na >= int(order_list.size())) {
1.171 + rn = na;
1.172 + } else if (nb >= int(order_list.size())) {
1.173 + rn = nb;
1.174 + }
1.175 +
1.176 + if (rn == -1) {
1.177 + int nn;
1.178 +
1.179 + nn = da ? node_data[na].prev : node_data[na].next;
1.180 + da = node_data[nn].prev != na;
1.181 + na = nn;
1.182 +
1.183 + nn = db ? node_data[nb].prev : node_data[nb].next;
1.184 + db = node_data[nn].prev != nb;
1.185 + nb = nn;
1.186 +
1.187 + } else {
1.188 +
1.189 + Node rep = order_list[rn - order_list.size()];
1.190 + Node parent = _graph.source(pred_map[rep]);
1.191 +
1.192 + if (low_map[rep] < rorder) {
1.193 + merge_roots[parent].push_back(rn);
1.194 + } else {
1.195 + merge_roots[parent].push_front(rn);
1.196 + }
1.197 +
1.198 + if (parent != root) {
1.199 + na = nb = order_map[parent];
1.200 + da = true; db = false;
1.201 + } else {
1.202 + break;
1.203 + }
1.204 + }
1.205 + }
1.206 + }
1.207 +
1.208 + void walkDown(int rn, int rorder, NodeData& node_data,
1.209 + OrderList& order_list, ChildLists& child_lists,
1.210 + AncestorMap& ancestor_map, LowMap& low_map,
1.211 + EmbedArc& embed_arc, MergeRoots& merge_roots) {
1.212 +
1.213 + std::vector<std::pair<int, bool> > merge_stack;
1.214 +
1.215 + for (int di = 0; di < 2; ++di) {
1.216 + bool rd = di == 0;
1.217 + int pn = rn;
1.218 + int n = rd ? node_data[rn].next : node_data[rn].prev;
1.219 +
1.220 + while (n != rn) {
1.221 +
1.222 + Node node = order_list[n];
1.223 +
1.224 + if (embed_arc[node]) {
1.225 +
1.226 + // Merging components on the critical path
1.227 + while (!merge_stack.empty()) {
1.228 +
1.229 + // Component root
1.230 + int cn = merge_stack.back().first;
1.231 + bool cd = merge_stack.back().second;
1.232 + merge_stack.pop_back();
1.233 +
1.234 + // Parent of component
1.235 + int dn = merge_stack.back().first;
1.236 + bool dd = merge_stack.back().second;
1.237 + merge_stack.pop_back();
1.238 +
1.239 + Node parent = order_list[dn];
1.240 +
1.241 + // Erasing from merge_roots
1.242 + merge_roots[parent].pop_front();
1.243 +
1.244 + Node child = order_list[cn - order_list.size()];
1.245 +
1.246 + // Erasing from child_lists
1.247 + if (child_lists[child].prev != INVALID) {
1.248 + child_lists[child_lists[child].prev].next =
1.249 + child_lists[child].next;
1.250 + } else {
1.251 + child_lists[parent].first = child_lists[child].next;
1.252 + }
1.253 +
1.254 + if (child_lists[child].next != INVALID) {
1.255 + child_lists[child_lists[child].next].prev =
1.256 + child_lists[child].prev;
1.257 + }
1.258 +
1.259 + // Merging external faces
1.260 + {
1.261 + int en = cn;
1.262 + cn = cd ? node_data[cn].prev : node_data[cn].next;
1.263 + cd = node_data[cn].next == en;
1.264 +
1.265 + }
1.266 +
1.267 + if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
1.268 + if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
1.269 +
1.270 + }
1.271 +
1.272 + bool d = pn == node_data[n].prev;
1.273 +
1.274 + if (node_data[n].prev == node_data[n].next &&
1.275 + node_data[n].inverted) {
1.276 + d = !d;
1.277 + }
1.278 +
1.279 + // Embedding arc into external face
1.280 + if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
1.281 + if (d) node_data[n].prev = rn; else node_data[n].next = rn;
1.282 + pn = rn;
1.283 +
1.284 + embed_arc[order_list[n]] = false;
1.285 + }
1.286 +
1.287 + if (!merge_roots[node].empty()) {
1.288 +
1.289 + bool d = pn == node_data[n].prev;
1.290 +
1.291 + merge_stack.push_back(std::make_pair(n, d));
1.292 +
1.293 + int rn = merge_roots[node].front();
1.294 +
1.295 + int xn = node_data[rn].next;
1.296 + Node xnode = order_list[xn];
1.297 +
1.298 + int yn = node_data[rn].prev;
1.299 + Node ynode = order_list[yn];
1.300 +
1.301 + bool rd;
1.302 + if (!external(xnode, rorder, child_lists,
1.303 + ancestor_map, low_map)) {
1.304 + rd = true;
1.305 + } else if (!external(ynode, rorder, child_lists,
1.306 + ancestor_map, low_map)) {
1.307 + rd = false;
1.308 + } else if (pertinent(xnode, embed_arc, merge_roots)) {
1.309 + rd = true;
1.310 + } else {
1.311 + rd = false;
1.312 + }
1.313 +
1.314 + merge_stack.push_back(std::make_pair(rn, rd));
1.315 +
1.316 + pn = rn;
1.317 + n = rd ? xn : yn;
1.318 +
1.319 + } else if (!external(node, rorder, child_lists,
1.320 + ancestor_map, low_map)) {
1.321 + int nn = (node_data[n].next != pn ?
1.322 + node_data[n].next : node_data[n].prev);
1.323 +
1.324 + bool nd = n == node_data[nn].prev;
1.325 +
1.326 + if (nd) node_data[nn].prev = pn;
1.327 + else node_data[nn].next = pn;
1.328 +
1.329 + if (n == node_data[pn].prev) node_data[pn].prev = nn;
1.330 + else node_data[pn].next = nn;
1.331 +
1.332 + node_data[nn].inverted =
1.333 + (node_data[nn].prev == node_data[nn].next && nd != rd);
1.334 +
1.335 + n = nn;
1.336 + }
1.337 + else break;
1.338 +
1.339 + }
1.340 +
1.341 + if (!merge_stack.empty() || n == rn) {
1.342 + break;
1.343 + }
1.344 + }
1.345 + }
1.346 +
1.347 + void initFace(const Node& node, NodeData& node_data,
1.348 + const OrderMap& order_map, const OrderList& order_list) {
1.349 + int n = order_map[node];
1.350 + int rn = n + order_list.size();
1.351 +
1.352 + node_data[n].next = node_data[n].prev = rn;
1.353 + node_data[rn].next = node_data[rn].prev = n;
1.354 +
1.355 + node_data[n].visited = order_list.size();
1.356 + node_data[rn].visited = order_list.size();
1.357 +
1.358 + }
1.359 +
1.360 + bool external(const Node& node, int rorder,
1.361 + ChildLists& child_lists, AncestorMap& ancestor_map,
1.362 + LowMap& low_map) {
1.363 + Node child = child_lists[node].first;
1.364 +
1.365 + if (child != INVALID) {
1.366 + if (low_map[child] < rorder) return true;
1.367 + }
1.368 +
1.369 + if (ancestor_map[node] < rorder) return true;
1.370 +
1.371 + return false;
1.372 + }
1.373 +
1.374 + bool pertinent(const Node& node, const EmbedArc& embed_arc,
1.375 + const MergeRoots& merge_roots) {
1.376 + return !merge_roots[node].empty() || embed_arc[node];
1.377 + }
1.378 +
1.379 + };
1.380 +
1.381 }
1.382
1.383 /// \ingroup planar
1.384 ///
1.385 /// \brief Planarity checking of an undirected simple graph
1.386 ///
1.387 - /// This class implements the Boyer-Myrvold algorithm for planarity
1.388 - /// checking of an undirected graph. This class is a simplified
1.389 + /// This function implements the Boyer-Myrvold algorithm for
1.390 + /// planarity checking of an undirected graph. It is a simplified
1.391 /// version of the PlanarEmbedding algorithm class because neither
1.392 /// the embedding nor the kuratowski subdivisons are not computed.
1.393 - template <typename Graph>
1.394 - class PlanarityChecking {
1.395 - private:
1.396 -
1.397 - TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.398 -
1.399 - const Graph& _graph;
1.400 -
1.401 - private:
1.402 -
1.403 - typedef typename Graph::template NodeMap<Arc> PredMap;
1.404 -
1.405 - typedef typename Graph::template EdgeMap<bool> TreeMap;
1.406 -
1.407 - typedef typename Graph::template NodeMap<int> OrderMap;
1.408 - typedef std::vector<Node> OrderList;
1.409 -
1.410 - typedef typename Graph::template NodeMap<int> LowMap;
1.411 - typedef typename Graph::template NodeMap<int> AncestorMap;
1.412 -
1.413 - typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
1.414 - typedef std::vector<NodeDataNode> NodeData;
1.415 -
1.416 - typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
1.417 - typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
1.418 -
1.419 - typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
1.420 -
1.421 - typedef typename Graph::template NodeMap<bool> EmbedArc;
1.422 -
1.423 - public:
1.424 -
1.425 - /// \brief Constructor
1.426 - ///
1.427 - /// \note The graph should be simple, i.e. parallel and loop arc
1.428 - /// free.
1.429 - PlanarityChecking(const Graph& graph) : _graph(graph) {}
1.430 -
1.431 - /// \brief Runs the algorithm.
1.432 - ///
1.433 - /// Runs the algorithm.
1.434 - /// \return %True when the graph is planar.
1.435 - bool run() {
1.436 - typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
1.437 -
1.438 - PredMap pred_map(_graph, INVALID);
1.439 - TreeMap tree_map(_graph, false);
1.440 -
1.441 - OrderMap order_map(_graph, -1);
1.442 - OrderList order_list;
1.443 -
1.444 - AncestorMap ancestor_map(_graph, -1);
1.445 - LowMap low_map(_graph, -1);
1.446 -
1.447 - Visitor visitor(_graph, pred_map, tree_map,
1.448 - order_map, order_list, ancestor_map, low_map);
1.449 - DfsVisit<Graph, Visitor> visit(_graph, visitor);
1.450 - visit.run();
1.451 -
1.452 - ChildLists child_lists(_graph);
1.453 - createChildLists(tree_map, order_map, low_map, child_lists);
1.454 -
1.455 - NodeData node_data(2 * order_list.size());
1.456 -
1.457 - EmbedArc embed_arc(_graph, false);
1.458 -
1.459 - MergeRoots merge_roots(_graph);
1.460 -
1.461 - for (int i = order_list.size() - 1; i >= 0; --i) {
1.462 -
1.463 - Node node = order_list[i];
1.464 -
1.465 - Node source = node;
1.466 - for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.467 - Node target = _graph.target(e);
1.468 -
1.469 - if (order_map[source] < order_map[target] && tree_map[e]) {
1.470 - initFace(target, node_data, order_map, order_list);
1.471 - }
1.472 - }
1.473 -
1.474 - for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.475 - Node target = _graph.target(e);
1.476 -
1.477 - if (order_map[source] < order_map[target] && !tree_map[e]) {
1.478 - embed_arc[target] = true;
1.479 - walkUp(target, source, i, pred_map, low_map,
1.480 - order_map, order_list, node_data, merge_roots);
1.481 - }
1.482 - }
1.483 -
1.484 - for (typename MergeRoots::Value::iterator it =
1.485 - merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
1.486 - int rn = *it;
1.487 - walkDown(rn, i, node_data, order_list, child_lists,
1.488 - ancestor_map, low_map, embed_arc, merge_roots);
1.489 - }
1.490 - merge_roots[node].clear();
1.491 -
1.492 - for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.493 - Node target = _graph.target(e);
1.494 -
1.495 - if (order_map[source] < order_map[target] && !tree_map[e]) {
1.496 - if (embed_arc[target]) {
1.497 - return false;
1.498 - }
1.499 - }
1.500 - }
1.501 - }
1.502 -
1.503 - return true;
1.504 - }
1.505 -
1.506 - private:
1.507 -
1.508 - void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
1.509 - const LowMap& low_map, ChildLists& child_lists) {
1.510 -
1.511 - for (NodeIt n(_graph); n != INVALID; ++n) {
1.512 - Node source = n;
1.513 -
1.514 - std::vector<Node> targets;
1.515 - for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.516 - Node target = _graph.target(e);
1.517 -
1.518 - if (order_map[source] < order_map[target] && tree_map[e]) {
1.519 - targets.push_back(target);
1.520 - }
1.521 - }
1.522 -
1.523 - if (targets.size() == 0) {
1.524 - child_lists[source].first = INVALID;
1.525 - } else if (targets.size() == 1) {
1.526 - child_lists[source].first = targets[0];
1.527 - child_lists[targets[0]].prev = INVALID;
1.528 - child_lists[targets[0]].next = INVALID;
1.529 - } else {
1.530 - radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
1.531 - for (int i = 1; i < int(targets.size()); ++i) {
1.532 - child_lists[targets[i]].prev = targets[i - 1];
1.533 - child_lists[targets[i - 1]].next = targets[i];
1.534 - }
1.535 - child_lists[targets.back()].next = INVALID;
1.536 - child_lists[targets.front()].prev = INVALID;
1.537 - child_lists[source].first = targets.front();
1.538 - }
1.539 - }
1.540 - }
1.541 -
1.542 - void walkUp(const Node& node, Node root, int rorder,
1.543 - const PredMap& pred_map, const LowMap& low_map,
1.544 - const OrderMap& order_map, const OrderList& order_list,
1.545 - NodeData& node_data, MergeRoots& merge_roots) {
1.546 -
1.547 - int na, nb;
1.548 - bool da, db;
1.549 -
1.550 - na = nb = order_map[node];
1.551 - da = true; db = false;
1.552 -
1.553 - while (true) {
1.554 -
1.555 - if (node_data[na].visited == rorder) break;
1.556 - if (node_data[nb].visited == rorder) break;
1.557 -
1.558 - node_data[na].visited = rorder;
1.559 - node_data[nb].visited = rorder;
1.560 -
1.561 - int rn = -1;
1.562 -
1.563 - if (na >= int(order_list.size())) {
1.564 - rn = na;
1.565 - } else if (nb >= int(order_list.size())) {
1.566 - rn = nb;
1.567 - }
1.568 -
1.569 - if (rn == -1) {
1.570 - int nn;
1.571 -
1.572 - nn = da ? node_data[na].prev : node_data[na].next;
1.573 - da = node_data[nn].prev != na;
1.574 - na = nn;
1.575 -
1.576 - nn = db ? node_data[nb].prev : node_data[nb].next;
1.577 - db = node_data[nn].prev != nb;
1.578 - nb = nn;
1.579 -
1.580 - } else {
1.581 -
1.582 - Node rep = order_list[rn - order_list.size()];
1.583 - Node parent = _graph.source(pred_map[rep]);
1.584 -
1.585 - if (low_map[rep] < rorder) {
1.586 - merge_roots[parent].push_back(rn);
1.587 - } else {
1.588 - merge_roots[parent].push_front(rn);
1.589 - }
1.590 -
1.591 - if (parent != root) {
1.592 - na = nb = order_map[parent];
1.593 - da = true; db = false;
1.594 - } else {
1.595 - break;
1.596 - }
1.597 - }
1.598 - }
1.599 - }
1.600 -
1.601 - void walkDown(int rn, int rorder, NodeData& node_data,
1.602 - OrderList& order_list, ChildLists& child_lists,
1.603 - AncestorMap& ancestor_map, LowMap& low_map,
1.604 - EmbedArc& embed_arc, MergeRoots& merge_roots) {
1.605 -
1.606 - std::vector<std::pair<int, bool> > merge_stack;
1.607 -
1.608 - for (int di = 0; di < 2; ++di) {
1.609 - bool rd = di == 0;
1.610 - int pn = rn;
1.611 - int n = rd ? node_data[rn].next : node_data[rn].prev;
1.612 -
1.613 - while (n != rn) {
1.614 -
1.615 - Node node = order_list[n];
1.616 -
1.617 - if (embed_arc[node]) {
1.618 -
1.619 - // Merging components on the critical path
1.620 - while (!merge_stack.empty()) {
1.621 -
1.622 - // Component root
1.623 - int cn = merge_stack.back().first;
1.624 - bool cd = merge_stack.back().second;
1.625 - merge_stack.pop_back();
1.626 -
1.627 - // Parent of component
1.628 - int dn = merge_stack.back().first;
1.629 - bool dd = merge_stack.back().second;
1.630 - merge_stack.pop_back();
1.631 -
1.632 - Node parent = order_list[dn];
1.633 -
1.634 - // Erasing from merge_roots
1.635 - merge_roots[parent].pop_front();
1.636 -
1.637 - Node child = order_list[cn - order_list.size()];
1.638 -
1.639 - // Erasing from child_lists
1.640 - if (child_lists[child].prev != INVALID) {
1.641 - child_lists[child_lists[child].prev].next =
1.642 - child_lists[child].next;
1.643 - } else {
1.644 - child_lists[parent].first = child_lists[child].next;
1.645 - }
1.646 -
1.647 - if (child_lists[child].next != INVALID) {
1.648 - child_lists[child_lists[child].next].prev =
1.649 - child_lists[child].prev;
1.650 - }
1.651 -
1.652 - // Merging external faces
1.653 - {
1.654 - int en = cn;
1.655 - cn = cd ? node_data[cn].prev : node_data[cn].next;
1.656 - cd = node_data[cn].next == en;
1.657 -
1.658 - }
1.659 -
1.660 - if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
1.661 - if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
1.662 -
1.663 - }
1.664 -
1.665 - bool d = pn == node_data[n].prev;
1.666 -
1.667 - if (node_data[n].prev == node_data[n].next &&
1.668 - node_data[n].inverted) {
1.669 - d = !d;
1.670 - }
1.671 -
1.672 - // Embedding arc into external face
1.673 - if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
1.674 - if (d) node_data[n].prev = rn; else node_data[n].next = rn;
1.675 - pn = rn;
1.676 -
1.677 - embed_arc[order_list[n]] = false;
1.678 - }
1.679 -
1.680 - if (!merge_roots[node].empty()) {
1.681 -
1.682 - bool d = pn == node_data[n].prev;
1.683 -
1.684 - merge_stack.push_back(std::make_pair(n, d));
1.685 -
1.686 - int rn = merge_roots[node].front();
1.687 -
1.688 - int xn = node_data[rn].next;
1.689 - Node xnode = order_list[xn];
1.690 -
1.691 - int yn = node_data[rn].prev;
1.692 - Node ynode = order_list[yn];
1.693 -
1.694 - bool rd;
1.695 - if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
1.696 - rd = true;
1.697 - } else if (!external(ynode, rorder, child_lists,
1.698 - ancestor_map, low_map)) {
1.699 - rd = false;
1.700 - } else if (pertinent(xnode, embed_arc, merge_roots)) {
1.701 - rd = true;
1.702 - } else {
1.703 - rd = false;
1.704 - }
1.705 -
1.706 - merge_stack.push_back(std::make_pair(rn, rd));
1.707 -
1.708 - pn = rn;
1.709 - n = rd ? xn : yn;
1.710 -
1.711 - } else if (!external(node, rorder, child_lists,
1.712 - ancestor_map, low_map)) {
1.713 - int nn = (node_data[n].next != pn ?
1.714 - node_data[n].next : node_data[n].prev);
1.715 -
1.716 - bool nd = n == node_data[nn].prev;
1.717 -
1.718 - if (nd) node_data[nn].prev = pn;
1.719 - else node_data[nn].next = pn;
1.720 -
1.721 - if (n == node_data[pn].prev) node_data[pn].prev = nn;
1.722 - else node_data[pn].next = nn;
1.723 -
1.724 - node_data[nn].inverted =
1.725 - (node_data[nn].prev == node_data[nn].next && nd != rd);
1.726 -
1.727 - n = nn;
1.728 - }
1.729 - else break;
1.730 -
1.731 - }
1.732 -
1.733 - if (!merge_stack.empty() || n == rn) {
1.734 - break;
1.735 - }
1.736 - }
1.737 - }
1.738 -
1.739 - void initFace(const Node& node, NodeData& node_data,
1.740 - const OrderMap& order_map, const OrderList& order_list) {
1.741 - int n = order_map[node];
1.742 - int rn = n + order_list.size();
1.743 -
1.744 - node_data[n].next = node_data[n].prev = rn;
1.745 - node_data[rn].next = node_data[rn].prev = n;
1.746 -
1.747 - node_data[n].visited = order_list.size();
1.748 - node_data[rn].visited = order_list.size();
1.749 -
1.750 - }
1.751 -
1.752 - bool external(const Node& node, int rorder,
1.753 - ChildLists& child_lists, AncestorMap& ancestor_map,
1.754 - LowMap& low_map) {
1.755 - Node child = child_lists[node].first;
1.756 -
1.757 - if (child != INVALID) {
1.758 - if (low_map[child] < rorder) return true;
1.759 - }
1.760 -
1.761 - if (ancestor_map[node] < rorder) return true;
1.762 -
1.763 - return false;
1.764 - }
1.765 -
1.766 - bool pertinent(const Node& node, const EmbedArc& embed_arc,
1.767 - const MergeRoots& merge_roots) {
1.768 - return !merge_roots[node].empty() || embed_arc[node];
1.769 - }
1.770 -
1.771 - };
1.772 + template <typename GR>
1.773 + bool checkPlanarity(const GR& graph) {
1.774 + _planarity_bits::PlanarityChecking<GR> pc(graph);
1.775 + return pc.run();
1.776 + }
1.777
1.778 /// \ingroup planar
1.779 ///
1.780 @@ -712,7 +712,7 @@
1.781 ///
1.782 /// The returned map contains the successor of each arc in the
1.783 /// graph.
1.784 - const EmbeddingMap& embedding() const {
1.785 + const EmbeddingMap& embeddingMap() const {
1.786 return _embedding;
1.787 }
1.788
2.1 --- a/test/planarity_test.cc Wed Sep 09 15:32:03 2009 +0200
2.2 +++ b/test/planarity_test.cc Sun Oct 04 10:15:32 2009 +0200
2.3 @@ -239,15 +239,18 @@
2.4 check(simpleGraph(graph), "Test graphs must be simple");
2.5
2.6 PE pe(graph);
2.7 - if (pe.run()) {
2.8 + bool planar = pe.run();
2.9 + check(checkPlanarity(graph) == planar, "Planarity checking failed");
2.10 +
2.11 + if (planar) {
2.12 checkEmbedding(graph, pe);
2.13
2.14 PlanarDrawing<Graph> pd(graph);
2.15 - pd.run(pe.embedding());
2.16 + pd.run(pe.embeddingMap());
2.17 checkDrawing(graph, pd);
2.18
2.19 PlanarColoring<Graph> pc(graph);
2.20 - pc.runFiveColoring(pe.embedding());
2.21 + pc.runFiveColoring(pe.embeddingMap());
2.22 checkColoring(graph, pc, 5);
2.23
2.24 } else {