1.1 --- a/lemon/Makefile.am Fri Sep 28 12:42:14 2007 +0000
1.2 +++ b/lemon/Makefile.am Sun Sep 30 19:14:33 2007 +0000
1.3 @@ -99,6 +99,7 @@
1.4 lemon/network_simplex.h \
1.5 lemon/path.h \
1.6 lemon/path_utils.h \
1.7 + lemon/planarity.h \
1.8 lemon/polynomial.h \
1.9 lemon/preflow.h \
1.10 lemon/prim.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/planarity.h Sun Sep 30 19:14:33 2007 +0000
2.3 @@ -0,0 +1,1815 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2007
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +#ifndef LEMON_PLANARITY_H
2.22 +#define LEMON_PLANARITY_H
2.23 +
2.24 +/// \ingroup graph_prop
2.25 +/// \file
2.26 +/// \brief Planarity checking, embedding
2.27 +
2.28 +#include <vector>
2.29 +#include <list>
2.30 +
2.31 +#include <lemon/dfs.h>
2.32 +#include <lemon/radix_sort.h>
2.33 +#include <lemon/maps.h>
2.34 +#include <lemon/path.h>
2.35 +
2.36 +
2.37 +namespace lemon {
2.38 +
2.39 + namespace _planarity_bits {
2.40 +
2.41 + template <typename UGraph>
2.42 + struct PlanarityVisitor : DfsVisitor<UGraph> {
2.43 +
2.44 + typedef typename UGraph::Node Node;
2.45 + typedef typename UGraph::Edge Edge;
2.46 +
2.47 + typedef typename UGraph::template NodeMap<Edge> PredMap;
2.48 +
2.49 + typedef typename UGraph::template UEdgeMap<bool> TreeMap;
2.50 +
2.51 + typedef typename UGraph::template NodeMap<int> OrderMap;
2.52 + typedef std::vector<Node> OrderList;
2.53 +
2.54 + typedef typename UGraph::template NodeMap<int> LowMap;
2.55 + typedef typename UGraph::template NodeMap<int> AncestorMap;
2.56 +
2.57 + PlanarityVisitor(const UGraph& ugraph,
2.58 + PredMap& pred_map, TreeMap& tree_map,
2.59 + OrderMap& order_map, OrderList& order_list,
2.60 + AncestorMap& ancestor_map, LowMap& low_map)
2.61 + : _ugraph(ugraph), _pred_map(pred_map), _tree_map(tree_map),
2.62 + _order_map(order_map), _order_list(order_list),
2.63 + _ancestor_map(ancestor_map), _low_map(low_map) {}
2.64 +
2.65 + void reach(const Node& node) {
2.66 + _order_map[node] = _order_list.size();
2.67 + _low_map[node] = _order_list.size();
2.68 + _ancestor_map[node] = _order_list.size();
2.69 + _order_list.push_back(node);
2.70 + }
2.71 +
2.72 + void discover(const Edge& edge) {
2.73 + Node source = _ugraph.source(edge);
2.74 + Node target = _ugraph.target(edge);
2.75 +
2.76 + _tree_map[edge] = true;
2.77 + _pred_map[target] = edge;
2.78 + }
2.79 +
2.80 + void examine(const Edge& edge) {
2.81 + Node source = _ugraph.source(edge);
2.82 + Node target = _ugraph.target(edge);
2.83 +
2.84 + if (_order_map[target] < _order_map[source] && !_tree_map[edge]) {
2.85 + if (_low_map[source] > _order_map[target]) {
2.86 + _low_map[source] = _order_map[target];
2.87 + }
2.88 + if (_ancestor_map[source] > _order_map[target]) {
2.89 + _ancestor_map[source] = _order_map[target];
2.90 + }
2.91 + }
2.92 + }
2.93 +
2.94 + void backtrack(const Edge& edge) {
2.95 + Node source = _ugraph.source(edge);
2.96 + Node target = _ugraph.target(edge);
2.97 +
2.98 + if (_low_map[source] > _low_map[target]) {
2.99 + _low_map[source] = _low_map[target];
2.100 + }
2.101 + }
2.102 +
2.103 + const UGraph& _ugraph;
2.104 + PredMap& _pred_map;
2.105 + TreeMap& _tree_map;
2.106 + OrderMap& _order_map;
2.107 + OrderList& _order_list;
2.108 + AncestorMap& _ancestor_map;
2.109 + LowMap& _low_map;
2.110 + };
2.111 +
2.112 + template <typename UGraph, bool embedding = true>
2.113 + struct NodeDataNode {
2.114 + int prev, next;
2.115 + int visited;
2.116 + typename UGraph::Edge first;
2.117 + bool inverted;
2.118 + };
2.119 +
2.120 + template <typename UGraph>
2.121 + struct NodeDataNode<UGraph, false> {
2.122 + int prev, next;
2.123 + int visited;
2.124 + };
2.125 +
2.126 + template <typename UGraph>
2.127 + struct ChildListNode {
2.128 + typedef typename UGraph::Node Node;
2.129 + Node first;
2.130 + Node prev, next;
2.131 + };
2.132 +
2.133 + template <typename UGraph>
2.134 + struct EdgeListNode {
2.135 + typename UGraph::Edge prev, next;
2.136 + };
2.137 +
2.138 + }
2.139 +
2.140 + /// \ingroup graph_prop
2.141 + ///
2.142 + /// \brief Planarity checking of an undirected simple graph
2.143 + ///
2.144 + /// This class implements the Boyer-Myrvold algorithm for planar
2.145 + /// checking of an undirected graph. This class is a simplified
2.146 + /// version of the PlanarEmbedding algorithm class, and it does
2.147 + /// provide neither embedding nor kuratowski subdivisons.
2.148 + template <typename UGraph>
2.149 + class PlanarityChecking {
2.150 + private:
2.151 +
2.152 + UGRAPH_TYPEDEFS(typename UGraph)
2.153 +
2.154 + const UGraph& _ugraph;
2.155 +
2.156 + private:
2.157 +
2.158 + typedef typename UGraph::template NodeMap<Edge> PredMap;
2.159 +
2.160 + typedef typename UGraph::template UEdgeMap<bool> TreeMap;
2.161 +
2.162 + typedef typename UGraph::template NodeMap<int> OrderMap;
2.163 + typedef std::vector<Node> OrderList;
2.164 +
2.165 + typedef typename UGraph::template NodeMap<int> LowMap;
2.166 + typedef typename UGraph::template NodeMap<int> AncestorMap;
2.167 +
2.168 + typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
2.169 + typedef std::vector<NodeDataNode> NodeData;
2.170 +
2.171 + typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
2.172 + typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
2.173 +
2.174 + typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
2.175 +
2.176 + typedef typename UGraph::template NodeMap<bool> EmbedEdge;
2.177 +
2.178 + public:
2.179 +
2.180 + /// \brief Constructor
2.181 + ///
2.182 + /// \warining The graph should be simple, i.e. parallel and loop edge
2.183 + /// free.
2.184 + PlanarityChecking(const UGraph& ugraph) : _ugraph(ugraph) {}
2.185 +
2.186 + /// \brief Runs the algorithm.
2.187 + ///
2.188 + /// Runs the algorithm.
2.189 + /// \param kuratowski If the parameter is false, then the
2.190 + /// algorithm does not calculate the isolate Kuratowski
2.191 + /// subdivisions.
2.192 + /// \return %True when the graph is planar.
2.193 + bool run(bool kuratowski = true) {
2.194 + typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
2.195 +
2.196 + PredMap pred_map(_ugraph, INVALID);
2.197 + TreeMap tree_map(_ugraph, false);
2.198 +
2.199 + OrderMap order_map(_ugraph, -1);
2.200 + OrderList order_list;
2.201 +
2.202 + AncestorMap ancestor_map(_ugraph, -1);
2.203 + LowMap low_map(_ugraph, -1);
2.204 +
2.205 + Visitor visitor(_ugraph, pred_map, tree_map,
2.206 + order_map, order_list, ancestor_map, low_map);
2.207 + DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
2.208 + visit.run();
2.209 +
2.210 + ChildLists child_lists(_ugraph);
2.211 + createChildLists(tree_map, order_map, low_map, child_lists);
2.212 +
2.213 + NodeData node_data(2 * order_list.size());
2.214 +
2.215 + EmbedEdge embed_edge(_ugraph, false);
2.216 +
2.217 + MergeRoots merge_roots(_ugraph);
2.218 +
2.219 + for (int i = order_list.size() - 1; i >= 0; --i) {
2.220 +
2.221 + Node node = order_list[i];
2.222 +
2.223 + Node source = node;
2.224 + for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
2.225 + Node target = _ugraph.target(e);
2.226 +
2.227 + if (order_map[source] < order_map[target] && tree_map[e]) {
2.228 + initFace(target, node_data, pred_map, order_map, order_list);
2.229 + }
2.230 + }
2.231 +
2.232 + for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
2.233 + Node target = _ugraph.target(e);
2.234 +
2.235 + if (order_map[source] < order_map[target] && !tree_map[e]) {
2.236 + embed_edge[target] = true;
2.237 + walkUp(target, source, i, pred_map, low_map,
2.238 + order_map, order_list, node_data, merge_roots);
2.239 + }
2.240 + }
2.241 +
2.242 + for (typename MergeRoots::Value::iterator it =
2.243 + merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
2.244 + int rn = *it;
2.245 + walkDown(rn, i, node_data, order_list, child_lists,
2.246 + ancestor_map, low_map, embed_edge, merge_roots);
2.247 + }
2.248 + merge_roots[node].clear();
2.249 +
2.250 + for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
2.251 + Node target = _ugraph.target(e);
2.252 +
2.253 + if (order_map[source] < order_map[target] && !tree_map[e]) {
2.254 + if (embed_edge[target]) {
2.255 + return false;
2.256 + }
2.257 + }
2.258 + }
2.259 + }
2.260 +
2.261 + return true;
2.262 + }
2.263 +
2.264 + private:
2.265 +
2.266 + void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
2.267 + const LowMap& low_map, ChildLists& child_lists) {
2.268 +
2.269 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
2.270 + Node source = n;
2.271 +
2.272 + std::vector<Node> targets;
2.273 + for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
2.274 + Node target = _ugraph.target(e);
2.275 +
2.276 + if (order_map[source] < order_map[target] && tree_map[e]) {
2.277 + targets.push_back(target);
2.278 + }
2.279 + }
2.280 +
2.281 + if (targets.size() == 0) {
2.282 + child_lists[source].first = INVALID;
2.283 + } else if (targets.size() == 1) {
2.284 + child_lists[source].first = targets[0];
2.285 + child_lists[targets[0]].prev = INVALID;
2.286 + child_lists[targets[0]].next = INVALID;
2.287 + } else {
2.288 + radixSort(targets.begin(), targets.end(), mapFunctor(low_map));
2.289 + for (int i = 1; i < int(targets.size()); ++i) {
2.290 + child_lists[targets[i]].prev = targets[i - 1];
2.291 + child_lists[targets[i - 1]].next = targets[i];
2.292 + }
2.293 + child_lists[targets.back()].next = INVALID;
2.294 + child_lists[targets.front()].prev = INVALID;
2.295 + child_lists[source].first = targets.front();
2.296 + }
2.297 + }
2.298 + }
2.299 +
2.300 + void walkUp(const Node& node, Node root, int rorder,
2.301 + const PredMap& pred_map, const LowMap& low_map,
2.302 + const OrderMap& order_map, const OrderList& order_list,
2.303 + NodeData& node_data, MergeRoots& merge_roots) {
2.304 +
2.305 + int na, nb;
2.306 + bool da, db;
2.307 +
2.308 + na = nb = order_map[node];
2.309 + da = true; db = false;
2.310 +
2.311 + while (true) {
2.312 +
2.313 + if (node_data[na].visited == rorder) break;
2.314 + if (node_data[nb].visited == rorder) break;
2.315 +
2.316 + node_data[na].visited = rorder;
2.317 + node_data[nb].visited = rorder;
2.318 +
2.319 + int rn = -1;
2.320 +
2.321 + if (na >= int(order_list.size())) {
2.322 + rn = na;
2.323 + } else if (nb >= int(order_list.size())) {
2.324 + rn = nb;
2.325 + }
2.326 +
2.327 + if (rn == -1) {
2.328 + int nn;
2.329 +
2.330 + nn = da ? node_data[na].prev : node_data[na].next;
2.331 + da = node_data[nn].prev != na;
2.332 + na = nn;
2.333 +
2.334 + nn = db ? node_data[nb].prev : node_data[nb].next;
2.335 + db = node_data[nn].prev != nb;
2.336 + nb = nn;
2.337 +
2.338 + } else {
2.339 +
2.340 + Node rep = order_list[rn - order_list.size()];
2.341 + Node parent = _ugraph.source(pred_map[rep]);
2.342 +
2.343 + if (low_map[rep] < rorder) {
2.344 + merge_roots[parent].push_back(rn);
2.345 + } else {
2.346 + merge_roots[parent].push_front(rn);
2.347 + }
2.348 +
2.349 + if (parent != root) {
2.350 + na = nb = order_map[parent];
2.351 + da = true; db = false;
2.352 + } else {
2.353 + break;
2.354 + }
2.355 + }
2.356 + }
2.357 + }
2.358 +
2.359 + void walkDown(int rn, int rorder, NodeData& node_data,
2.360 + OrderList& order_list, ChildLists& child_lists,
2.361 + AncestorMap& ancestor_map, LowMap& low_map,
2.362 + EmbedEdge& embed_edge, MergeRoots& merge_roots) {
2.363 +
2.364 + std::vector<std::pair<int, bool> > merge_stack;
2.365 +
2.366 + for (int di = 0; di < 2; ++di) {
2.367 + bool rd = di == 0;
2.368 + int pn = rn;
2.369 + int n = rd ? node_data[rn].next : node_data[rn].prev;
2.370 +
2.371 + while (n != rn) {
2.372 +
2.373 + Node node = order_list[n];
2.374 +
2.375 + if (embed_edge[node]) {
2.376 +
2.377 + // Merging components on the critical path
2.378 + while (!merge_stack.empty()) {
2.379 +
2.380 + // Component root
2.381 + int cn = merge_stack.back().first;
2.382 + bool cd = merge_stack.back().second;
2.383 + merge_stack.pop_back();
2.384 +
2.385 + // Parent of component
2.386 + int dn = merge_stack.back().first;
2.387 + bool dd = merge_stack.back().second;
2.388 + merge_stack.pop_back();
2.389 +
2.390 + Node parent = order_list[dn];
2.391 +
2.392 + // Erasing from merge_roots
2.393 + merge_roots[parent].pop_front();
2.394 +
2.395 + Node child = order_list[cn - order_list.size()];
2.396 +
2.397 + // Erasing from child_lists
2.398 + if (child_lists[child].prev != INVALID) {
2.399 + child_lists[child_lists[child].prev].next =
2.400 + child_lists[child].next;
2.401 + } else {
2.402 + child_lists[parent].first = child_lists[child].next;
2.403 + }
2.404 +
2.405 + if (child_lists[child].next != INVALID) {
2.406 + child_lists[child_lists[child].next].prev =
2.407 + child_lists[child].prev;
2.408 + }
2.409 +
2.410 + // Merging external faces
2.411 + {
2.412 + int en = cn;
2.413 + cn = cd ? node_data[cn].prev : node_data[cn].next;
2.414 + cd = node_data[cn].next == en;
2.415 +
2.416 + }
2.417 +
2.418 + if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
2.419 + if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
2.420 +
2.421 + }
2.422 +
2.423 + bool d = pn == node_data[n].prev;
2.424 +
2.425 + if (node_data[n].prev == node_data[n].next &&
2.426 + node_data[n].inverted) {
2.427 + d = !d;
2.428 + }
2.429 +
2.430 + // Embedding edge into external face
2.431 + if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
2.432 + if (d) node_data[n].prev = rn; else node_data[n].next = rn;
2.433 + pn = rn;
2.434 +
2.435 + embed_edge[order_list[n]] = false;
2.436 + }
2.437 +
2.438 + if (!merge_roots[node].empty()) {
2.439 +
2.440 + bool d = pn == node_data[n].prev;
2.441 +
2.442 + merge_stack.push_back(std::make_pair(n, d));
2.443 +
2.444 + int rn = merge_roots[node].front();
2.445 +
2.446 + int xn = node_data[rn].next;
2.447 + Node xnode = order_list[xn];
2.448 +
2.449 + int yn = node_data[rn].prev;
2.450 + Node ynode = order_list[yn];
2.451 +
2.452 + bool rd;
2.453 + if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
2.454 + rd = true;
2.455 + } else if (!external(ynode, rorder, child_lists,
2.456 + ancestor_map, low_map)) {
2.457 + rd = false;
2.458 + } else if (pertinent(xnode, embed_edge, merge_roots)) {
2.459 + rd = true;
2.460 + } else {
2.461 + rd = false;
2.462 + }
2.463 +
2.464 + merge_stack.push_back(std::make_pair(rn, rd));
2.465 +
2.466 + pn = rn;
2.467 + n = rd ? xn : yn;
2.468 +
2.469 + } else if (!external(node, rorder, child_lists,
2.470 + ancestor_map, low_map)) {
2.471 + int nn = (node_data[n].next != pn ?
2.472 + node_data[n].next : node_data[n].prev);
2.473 +
2.474 + bool nd = n == node_data[nn].prev;
2.475 +
2.476 + if (nd) node_data[nn].prev = pn;
2.477 + else node_data[nn].next = pn;
2.478 +
2.479 + if (n == node_data[pn].prev) node_data[pn].prev = nn;
2.480 + else node_data[pn].next = nn;
2.481 +
2.482 + node_data[nn].inverted =
2.483 + (node_data[nn].prev == node_data[nn].next && nd != rd);
2.484 +
2.485 + n = nn;
2.486 + }
2.487 + else break;
2.488 +
2.489 + }
2.490 +
2.491 + if (!merge_stack.empty() || n == rn) {
2.492 + break;
2.493 + }
2.494 + }
2.495 + }
2.496 +
2.497 + void initFace(const Node& node, NodeData& node_data,
2.498 + const PredMap& pred_map, const OrderMap& order_map,
2.499 + const OrderList& order_list) {
2.500 + int n = order_map[node];
2.501 + int rn = n + order_list.size();
2.502 +
2.503 + node_data[n].next = node_data[n].prev = rn;
2.504 + node_data[rn].next = node_data[rn].prev = n;
2.505 +
2.506 + node_data[n].visited = order_list.size();
2.507 + node_data[rn].visited = order_list.size();
2.508 +
2.509 + }
2.510 +
2.511 + bool external(const Node& node, int rorder,
2.512 + ChildLists& child_lists, AncestorMap& ancestor_map,
2.513 + LowMap& low_map) {
2.514 + Node child = child_lists[node].first;
2.515 +
2.516 + if (child != INVALID) {
2.517 + if (low_map[child] < rorder) return true;
2.518 + }
2.519 +
2.520 + if (ancestor_map[node] < rorder) return true;
2.521 +
2.522 + return false;
2.523 + }
2.524 +
2.525 + bool pertinent(const Node& node, const EmbedEdge& embed_edge,
2.526 + const MergeRoots& merge_roots) {
2.527 + return !merge_roots[node].empty() || embed_edge[node];
2.528 + }
2.529 +
2.530 + };
2.531 +
2.532 + /// \ingroup graph_prop
2.533 + ///
2.534 + /// \brief Planar embedding of an undirected simple graph
2.535 + ///
2.536 + /// This class implements the Boyer-Myrvold algorithm for planar
2.537 + /// embedding of an undirected graph. The planar embeding is an
2.538 + /// ordering of the outgoing edges in each node, which is a possible
2.539 + /// configuration to draw the graph in the plane. If there is not
2.540 + /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
2.541 + /// with 5 nodes) or an \f$ K_{3,3} \f$ (complete bipartite graph on
2.542 + /// 3 ANode and 3 BNode) subdivision.
2.543 + ///
2.544 + /// The current implementation calculates an embedding or an
2.545 + /// Kuratowski subdivision if the graph is not planar. The running
2.546 + /// time of the algorithm is \f$ O(n) \f$.
2.547 + template <typename UGraph>
2.548 + class PlanarEmbedding {
2.549 + private:
2.550 +
2.551 + UGRAPH_TYPEDEFS(typename UGraph)
2.552 +
2.553 + const UGraph& _ugraph;
2.554 + typename UGraph::template EdgeMap<Edge> _embedding;
2.555 +
2.556 + typename UGraph::template UEdgeMap<bool> _kuratowski;
2.557 +
2.558 + private:
2.559 +
2.560 + typedef typename UGraph::template NodeMap<Edge> PredMap;
2.561 +
2.562 + typedef typename UGraph::template UEdgeMap<bool> TreeMap;
2.563 +
2.564 + typedef typename UGraph::template NodeMap<int> OrderMap;
2.565 + typedef std::vector<Node> OrderList;
2.566 +
2.567 + typedef typename UGraph::template NodeMap<int> LowMap;
2.568 + typedef typename UGraph::template NodeMap<int> AncestorMap;
2.569 +
2.570 + typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
2.571 + typedef std::vector<NodeDataNode> NodeData;
2.572 +
2.573 + typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
2.574 + typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
2.575 +
2.576 + typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
2.577 +
2.578 + typedef typename UGraph::template NodeMap<Edge> EmbedEdge;
2.579 +
2.580 + typedef _planarity_bits::EdgeListNode<UGraph> EdgeListNode;
2.581 + typedef typename UGraph::template EdgeMap<EdgeListNode> EdgeLists;
2.582 +
2.583 + typedef typename UGraph::template NodeMap<bool> FlipMap;
2.584 +
2.585 + typedef typename UGraph::template NodeMap<int> TypeMap;
2.586 +
2.587 + enum IsolatorNodeType {
2.588 + HIGHX = 6, LOWX = 7,
2.589 + HIGHY = 8, LOWY = 9,
2.590 + ROOT = 10, PERTINENT = 11,
2.591 + INTERNAL = 12
2.592 + };
2.593 +
2.594 + public:
2.595 +
2.596 + /// \brief Constructor
2.597 + ///
2.598 + /// \warining The graph should be simple, i.e. parallel and loop edge
2.599 + /// free.
2.600 + PlanarEmbedding(const UGraph& ugraph)
2.601 + : _ugraph(ugraph), _embedding(_ugraph), _kuratowski(ugraph, false) {}
2.602 +
2.603 + /// \brief Runs the algorithm.
2.604 + ///
2.605 + /// Runs the algorithm.
2.606 + /// \param kuratowski If the parameter is false, then the
2.607 + /// algorithm does not calculate the isolate Kuratowski
2.608 + /// subdivisions.
2.609 + ///\return %True when the graph is planar.
2.610 + bool run(bool kuratowski = true) {
2.611 + typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
2.612 +
2.613 + PredMap pred_map(_ugraph, INVALID);
2.614 + TreeMap tree_map(_ugraph, false);
2.615 +
2.616 + OrderMap order_map(_ugraph, -1);
2.617 + OrderList order_list;
2.618 +
2.619 + AncestorMap ancestor_map(_ugraph, -1);
2.620 + LowMap low_map(_ugraph, -1);
2.621 +
2.622 + Visitor visitor(_ugraph, pred_map, tree_map,
2.623 + order_map, order_list, ancestor_map, low_map);
2.624 + DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
2.625 + visit.run();
2.626 +
2.627 + ChildLists child_lists(_ugraph);
2.628 + createChildLists(tree_map, order_map, low_map, child_lists);
2.629 +
2.630 + NodeData node_data(2 * order_list.size());
2.631 +
2.632 + EmbedEdge embed_edge(_ugraph, INVALID);
2.633 +
2.634 + MergeRoots merge_roots(_ugraph);
2.635 +
2.636 + EdgeLists edge_lists(_ugraph);
2.637 +
2.638 + FlipMap flip_map(_ugraph, false);
2.639 +
2.640 + for (int i = order_list.size() - 1; i >= 0; --i) {
2.641 +
2.642 + Node node = order_list[i];
2.643 +
2.644 + node_data[i].first = INVALID;
2.645 +
2.646 + Node source = node;
2.647 + for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
2.648 + Node target = _ugraph.target(e);
2.649 +
2.650 + if (order_map[source] < order_map[target] && tree_map[e]) {
2.651 + initFace(target, edge_lists, node_data,
2.652 + pred_map, order_map, order_list);
2.653 + }
2.654 + }
2.655 +
2.656 + for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
2.657 + Node target = _ugraph.target(e);
2.658 +
2.659 + if (order_map[source] < order_map[target] && !tree_map[e]) {
2.660 + embed_edge[target] = e;
2.661 + walkUp(target, source, i, pred_map, low_map,
2.662 + order_map, order_list, node_data, merge_roots);
2.663 + }
2.664 + }
2.665 +
2.666 + for (typename MergeRoots::Value::iterator it =
2.667 + merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
2.668 + int rn = *it;
2.669 + walkDown(rn, i, node_data, edge_lists, flip_map, order_list,
2.670 + child_lists, ancestor_map, low_map, embed_edge, merge_roots);
2.671 + }
2.672 + merge_roots[node].clear();
2.673 +
2.674 + for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
2.675 + Node target = _ugraph.target(e);
2.676 +
2.677 + if (order_map[source] < order_map[target] && !tree_map[e]) {
2.678 + if (embed_edge[target] != INVALID) {
2.679 + if (kuratowski) {
2.680 + isolateKuratowski(e, node_data, edge_lists, flip_map,
2.681 + order_map, order_list, pred_map, child_lists,
2.682 + ancestor_map, low_map,
2.683 + embed_edge, merge_roots);
2.684 + }
2.685 + return false;
2.686 + }
2.687 + }
2.688 + }
2.689 + }
2.690 +
2.691 + for (int i = 0; i < int(order_list.size()); ++i) {
2.692 +
2.693 + mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
2.694 + child_lists, edge_lists);
2.695 + storeEmbedding(order_list[i], node_data, order_map, pred_map,
2.696 + edge_lists, flip_map);
2.697 + }
2.698 +
2.699 + return true;
2.700 + }
2.701 +
2.702 + /// \brief Gives back the successor of an edge
2.703 + ///
2.704 + /// Gives back the successor of an edge. This function makes
2.705 + /// possible to query the cyclic order of the outgoing edges from
2.706 + /// a node.
2.707 + Edge next(const Edge& edge) const {
2.708 + return _embedding[edge];
2.709 + }
2.710 +
2.711 + /// \brief Gives back true when the undirected edge is in the
2.712 + /// kuratowski subdivision
2.713 + ///
2.714 + /// Gives back true when the undirected edge is in the kuratowski
2.715 + /// subdivision
2.716 + bool kuratowski(const UEdge& uedge) {
2.717 + return _kuratowski[uedge];
2.718 + }
2.719 +
2.720 + private:
2.721 +
2.722 + void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
2.723 + const LowMap& low_map, ChildLists& child_lists) {
2.724 +
2.725 + for (NodeIt n(_ugraph); n != INVALID; ++n) {
2.726 + Node source = n;
2.727 +
2.728 + std::vector<Node> targets;
2.729 + for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
2.730 + Node target = _ugraph.target(e);
2.731 +
2.732 + if (order_map[source] < order_map[target] && tree_map[e]) {
2.733 + targets.push_back(target);
2.734 + }
2.735 + }
2.736 +
2.737 + if (targets.size() == 0) {
2.738 + child_lists[source].first = INVALID;
2.739 + } else if (targets.size() == 1) {
2.740 + child_lists[source].first = targets[0];
2.741 + child_lists[targets[0]].prev = INVALID;
2.742 + child_lists[targets[0]].next = INVALID;
2.743 + } else {
2.744 + radixSort(targets.begin(), targets.end(), mapFunctor(low_map));
2.745 + for (int i = 1; i < int(targets.size()); ++i) {
2.746 + child_lists[targets[i]].prev = targets[i - 1];
2.747 + child_lists[targets[i - 1]].next = targets[i];
2.748 + }
2.749 + child_lists[targets.back()].next = INVALID;
2.750 + child_lists[targets.front()].prev = INVALID;
2.751 + child_lists[source].first = targets.front();
2.752 + }
2.753 + }
2.754 + }
2.755 +
2.756 + void walkUp(const Node& node, Node root, int rorder,
2.757 + const PredMap& pred_map, const LowMap& low_map,
2.758 + const OrderMap& order_map, const OrderList& order_list,
2.759 + NodeData& node_data, MergeRoots& merge_roots) {
2.760 +
2.761 + int na, nb;
2.762 + bool da, db;
2.763 +
2.764 + na = nb = order_map[node];
2.765 + da = true; db = false;
2.766 +
2.767 + while (true) {
2.768 +
2.769 + if (node_data[na].visited == rorder) break;
2.770 + if (node_data[nb].visited == rorder) break;
2.771 +
2.772 + node_data[na].visited = rorder;
2.773 + node_data[nb].visited = rorder;
2.774 +
2.775 + int rn = -1;
2.776 +
2.777 + if (na >= int(order_list.size())) {
2.778 + rn = na;
2.779 + } else if (nb >= int(order_list.size())) {
2.780 + rn = nb;
2.781 + }
2.782 +
2.783 + if (rn == -1) {
2.784 + int nn;
2.785 +
2.786 + nn = da ? node_data[na].prev : node_data[na].next;
2.787 + da = node_data[nn].prev != na;
2.788 + na = nn;
2.789 +
2.790 + nn = db ? node_data[nb].prev : node_data[nb].next;
2.791 + db = node_data[nn].prev != nb;
2.792 + nb = nn;
2.793 +
2.794 + } else {
2.795 +
2.796 + Node rep = order_list[rn - order_list.size()];
2.797 + Node parent = _ugraph.source(pred_map[rep]);
2.798 +
2.799 + if (low_map[rep] < rorder) {
2.800 + merge_roots[parent].push_back(rn);
2.801 + } else {
2.802 + merge_roots[parent].push_front(rn);
2.803 + }
2.804 +
2.805 + if (parent != root) {
2.806 + na = nb = order_map[parent];
2.807 + da = true; db = false;
2.808 + } else {
2.809 + break;
2.810 + }
2.811 + }
2.812 + }
2.813 + }
2.814 +
2.815 + void walkDown(int rn, int rorder, NodeData& node_data,
2.816 + EdgeLists& edge_lists, FlipMap& flip_map,
2.817 + OrderList& order_list, ChildLists& child_lists,
2.818 + AncestorMap& ancestor_map, LowMap& low_map,
2.819 + EmbedEdge& embed_edge, MergeRoots& merge_roots) {
2.820 +
2.821 + std::vector<std::pair<int, bool> > merge_stack;
2.822 +
2.823 + for (int di = 0; di < 2; ++di) {
2.824 + bool rd = di == 0;
2.825 + int pn = rn;
2.826 + int n = rd ? node_data[rn].next : node_data[rn].prev;
2.827 +
2.828 + while (n != rn) {
2.829 +
2.830 + Node node = order_list[n];
2.831 +
2.832 + if (embed_edge[node] != INVALID) {
2.833 +
2.834 + // Merging components on the critical path
2.835 + while (!merge_stack.empty()) {
2.836 +
2.837 + // Component root
2.838 + int cn = merge_stack.back().first;
2.839 + bool cd = merge_stack.back().second;
2.840 + merge_stack.pop_back();
2.841 +
2.842 + // Parent of component
2.843 + int dn = merge_stack.back().first;
2.844 + bool dd = merge_stack.back().second;
2.845 + merge_stack.pop_back();
2.846 +
2.847 + Node parent = order_list[dn];
2.848 +
2.849 + // Erasing from merge_roots
2.850 + merge_roots[parent].pop_front();
2.851 +
2.852 + Node child = order_list[cn - order_list.size()];
2.853 +
2.854 + // Erasing from child_lists
2.855 + if (child_lists[child].prev != INVALID) {
2.856 + child_lists[child_lists[child].prev].next =
2.857 + child_lists[child].next;
2.858 + } else {
2.859 + child_lists[parent].first = child_lists[child].next;
2.860 + }
2.861 +
2.862 + if (child_lists[child].next != INVALID) {
2.863 + child_lists[child_lists[child].next].prev =
2.864 + child_lists[child].prev;
2.865 + }
2.866 +
2.867 + // Merging edges + flipping
2.868 + Edge de = node_data[dn].first;
2.869 + Edge ce = node_data[cn].first;
2.870 +
2.871 + flip_map[order_list[cn - order_list.size()]] = cd != dd;
2.872 + if (cd != dd) {
2.873 + std::swap(edge_lists[ce].prev, edge_lists[ce].next);
2.874 + ce = edge_lists[ce].prev;
2.875 + std::swap(edge_lists[ce].prev, edge_lists[ce].next);
2.876 + }
2.877 +
2.878 + {
2.879 + Edge dne = edge_lists[de].next;
2.880 + Edge cne = edge_lists[ce].next;
2.881 +
2.882 + edge_lists[de].next = cne;
2.883 + edge_lists[ce].next = dne;
2.884 +
2.885 + edge_lists[dne].prev = ce;
2.886 + edge_lists[cne].prev = de;
2.887 + }
2.888 +
2.889 + if (dd) {
2.890 + node_data[dn].first = ce;
2.891 + }
2.892 +
2.893 + // Merging external faces
2.894 + {
2.895 + int en = cn;
2.896 + cn = cd ? node_data[cn].prev : node_data[cn].next;
2.897 + cd = node_data[cn].next == en;
2.898 +
2.899 + if (node_data[cn].prev == node_data[cn].next &&
2.900 + node_data[cn].inverted) {
2.901 + cd = !cd;
2.902 + }
2.903 + }
2.904 +
2.905 + if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
2.906 + if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
2.907 +
2.908 + }
2.909 +
2.910 + bool d = pn == node_data[n].prev;
2.911 +
2.912 + if (node_data[n].prev == node_data[n].next &&
2.913 + node_data[n].inverted) {
2.914 + d = !d;
2.915 + }
2.916 +
2.917 + // Add new edge
2.918 + {
2.919 + Edge edge = embed_edge[node];
2.920 + Edge re = node_data[rn].first;
2.921 +
2.922 + edge_lists[edge_lists[re].next].prev = edge;
2.923 + edge_lists[edge].next = edge_lists[re].next;
2.924 + edge_lists[edge].prev = re;
2.925 + edge_lists[re].next = edge;
2.926 +
2.927 + if (!rd) {
2.928 + node_data[rn].first = edge;
2.929 + }
2.930 +
2.931 + Edge rev = _ugraph.oppositeEdge(edge);
2.932 + Edge e = node_data[n].first;
2.933 +
2.934 + edge_lists[edge_lists[e].next].prev = rev;
2.935 + edge_lists[rev].next = edge_lists[e].next;
2.936 + edge_lists[rev].prev = e;
2.937 + edge_lists[e].next = rev;
2.938 +
2.939 + if (d) {
2.940 + node_data[n].first = rev;
2.941 + }
2.942 +
2.943 + }
2.944 +
2.945 + // Embedding edge into external face
2.946 + if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
2.947 + if (d) node_data[n].prev = rn; else node_data[n].next = rn;
2.948 + pn = rn;
2.949 +
2.950 + embed_edge[order_list[n]] = INVALID;
2.951 + }
2.952 +
2.953 + if (!merge_roots[node].empty()) {
2.954 +
2.955 + bool d = pn == node_data[n].prev;
2.956 + if (node_data[n].prev == node_data[n].next &&
2.957 + node_data[n].inverted) {
2.958 + d = !d;
2.959 + }
2.960 +
2.961 + merge_stack.push_back(std::make_pair(n, d));
2.962 +
2.963 + int rn = merge_roots[node].front();
2.964 +
2.965 + int xn = node_data[rn].next;
2.966 + Node xnode = order_list[xn];
2.967 +
2.968 + int yn = node_data[rn].prev;
2.969 + Node ynode = order_list[yn];
2.970 +
2.971 + bool rd;
2.972 + if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
2.973 + rd = true;
2.974 + } else if (!external(ynode, rorder, child_lists,
2.975 + ancestor_map, low_map)) {
2.976 + rd = false;
2.977 + } else if (pertinent(xnode, embed_edge, merge_roots)) {
2.978 + rd = true;
2.979 + } else {
2.980 + rd = false;
2.981 + }
2.982 +
2.983 + merge_stack.push_back(std::make_pair(rn, rd));
2.984 +
2.985 + pn = rn;
2.986 + n = rd ? xn : yn;
2.987 +
2.988 + } else if (!external(node, rorder, child_lists,
2.989 + ancestor_map, low_map)) {
2.990 + int nn = (node_data[n].next != pn ?
2.991 + node_data[n].next : node_data[n].prev);
2.992 +
2.993 + bool nd = n == node_data[nn].prev;
2.994 +
2.995 + if (nd) node_data[nn].prev = pn;
2.996 + else node_data[nn].next = pn;
2.997 +
2.998 + if (n == node_data[pn].prev) node_data[pn].prev = nn;
2.999 + else node_data[pn].next = nn;
2.1000 +
2.1001 + node_data[nn].inverted =
2.1002 + (node_data[nn].prev == node_data[nn].next && nd != rd);
2.1003 +
2.1004 + n = nn;
2.1005 + }
2.1006 + else break;
2.1007 +
2.1008 + }
2.1009 +
2.1010 + if (!merge_stack.empty() || n == rn) {
2.1011 + break;
2.1012 + }
2.1013 + }
2.1014 + }
2.1015 +
2.1016 + void initFace(const Node& node, EdgeLists& edge_lists,
2.1017 + NodeData& node_data, const PredMap& pred_map,
2.1018 + const OrderMap& order_map, const OrderList& order_list) {
2.1019 + int n = order_map[node];
2.1020 + int rn = n + order_list.size();
2.1021 +
2.1022 + node_data[n].next = node_data[n].prev = rn;
2.1023 + node_data[rn].next = node_data[rn].prev = n;
2.1024 +
2.1025 + node_data[n].visited = order_list.size();
2.1026 + node_data[rn].visited = order_list.size();
2.1027 +
2.1028 + node_data[n].inverted = false;
2.1029 + node_data[rn].inverted = false;
2.1030 +
2.1031 + Edge edge = pred_map[node];
2.1032 + Edge rev = _ugraph.oppositeEdge(edge);
2.1033 +
2.1034 + node_data[rn].first = edge;
2.1035 + node_data[n].first = rev;
2.1036 +
2.1037 + edge_lists[edge].prev = edge;
2.1038 + edge_lists[edge].next = edge;
2.1039 +
2.1040 + edge_lists[rev].prev = rev;
2.1041 + edge_lists[rev].next = rev;
2.1042 +
2.1043 + }
2.1044 +
2.1045 + void mergeRemainingFaces(const Node& node, NodeData& node_data,
2.1046 + OrderList& order_list, OrderMap& order_map,
2.1047 + ChildLists& child_lists, EdgeLists& edge_lists) {
2.1048 + while (child_lists[node].first != INVALID) {
2.1049 + int dd = order_map[node];
2.1050 + Node child = child_lists[node].first;
2.1051 + int cd = order_map[child] + order_list.size();
2.1052 + child_lists[node].first = child_lists[child].next;
2.1053 +
2.1054 + Edge de = node_data[dd].first;
2.1055 + Edge ce = node_data[cd].first;
2.1056 +
2.1057 + if (de != INVALID) {
2.1058 + Edge dne = edge_lists[de].next;
2.1059 + Edge cne = edge_lists[ce].next;
2.1060 +
2.1061 + edge_lists[de].next = cne;
2.1062 + edge_lists[ce].next = dne;
2.1063 +
2.1064 + edge_lists[dne].prev = ce;
2.1065 + edge_lists[cne].prev = de;
2.1066 + }
2.1067 +
2.1068 + node_data[dd].first = ce;
2.1069 +
2.1070 + }
2.1071 + }
2.1072 +
2.1073 + void storeEmbedding(const Node& node, NodeData& node_data,
2.1074 + OrderMap& order_map, PredMap& pred_map,
2.1075 + EdgeLists& edge_lists, FlipMap& flip_map) {
2.1076 +
2.1077 + if (node_data[order_map[node]].first == INVALID) return;
2.1078 +
2.1079 + if (pred_map[node] != INVALID) {
2.1080 + Node source = _ugraph.source(pred_map[node]);
2.1081 + flip_map[node] = flip_map[node] != flip_map[source];
2.1082 + }
2.1083 +
2.1084 + Edge first = node_data[order_map[node]].first;
2.1085 + Edge prev = first;
2.1086 +
2.1087 + Edge edge = flip_map[node] ?
2.1088 + edge_lists[prev].prev : edge_lists[prev].next;
2.1089 +
2.1090 + _embedding[prev] = edge;
2.1091 +
2.1092 + while (edge != first) {
2.1093 + Edge next = edge_lists[edge].prev == prev ?
2.1094 + edge_lists[edge].next : edge_lists[edge].prev;
2.1095 + prev = edge; edge = next;
2.1096 + _embedding[prev] = edge;
2.1097 + }
2.1098 + }
2.1099 +
2.1100 +
2.1101 + bool external(const Node& node, int rorder,
2.1102 + ChildLists& child_lists, AncestorMap& ancestor_map,
2.1103 + LowMap& low_map) {
2.1104 + Node child = child_lists[node].first;
2.1105 +
2.1106 + if (child != INVALID) {
2.1107 + if (low_map[child] < rorder) return true;
2.1108 + }
2.1109 +
2.1110 + if (ancestor_map[node] < rorder) return true;
2.1111 +
2.1112 + return false;
2.1113 + }
2.1114 +
2.1115 + bool pertinent(const Node& node, const EmbedEdge& embed_edge,
2.1116 + const MergeRoots& merge_roots) {
2.1117 + return !merge_roots[node].empty() || embed_edge[node] != INVALID;
2.1118 + }
2.1119 +
2.1120 + int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
2.1121 + AncestorMap& ancestor_map, LowMap& low_map) {
2.1122 + int low_point;
2.1123 +
2.1124 + Node child = child_lists[node].first;
2.1125 +
2.1126 + if (child != INVALID) {
2.1127 + low_point = low_map[child];
2.1128 + } else {
2.1129 + low_point = order_map[node];
2.1130 + }
2.1131 +
2.1132 + if (low_point > ancestor_map[node]) {
2.1133 + low_point = ancestor_map[node];
2.1134 + }
2.1135 +
2.1136 + return low_point;
2.1137 + }
2.1138 +
2.1139 + int findComponentRoot(Node root, Node node, ChildLists& child_lists,
2.1140 + OrderMap& order_map, OrderList& order_list) {
2.1141 +
2.1142 + int order = order_map[root];
2.1143 + int norder = order_map[node];
2.1144 +
2.1145 + Node child = child_lists[root].first;
2.1146 + while (child != INVALID) {
2.1147 + int corder = order_map[child];
2.1148 + if (corder > order && corder < norder) {
2.1149 + order = corder;
2.1150 + }
2.1151 + child = child_lists[child].next;
2.1152 + }
2.1153 + return order + order_list.size();
2.1154 + }
2.1155 +
2.1156 + Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data,
2.1157 + EmbedEdge& embed_edge, MergeRoots& merge_roots) {
2.1158 + Node wnode =_ugraph.target(node_data[order_map[node]].first);
2.1159 + while (!pertinent(wnode, embed_edge, merge_roots)) {
2.1160 + wnode = _ugraph.target(node_data[order_map[wnode]].first);
2.1161 + }
2.1162 + return wnode;
2.1163 + }
2.1164 +
2.1165 +
2.1166 + Node findExternal(Node node, int rorder, OrderMap& order_map,
2.1167 + ChildLists& child_lists, AncestorMap& ancestor_map,
2.1168 + LowMap& low_map, NodeData& node_data) {
2.1169 + Node wnode =_ugraph.target(node_data[order_map[node]].first);
2.1170 + while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
2.1171 + wnode = _ugraph.target(node_data[order_map[wnode]].first);
2.1172 + }
2.1173 + return wnode;
2.1174 + }
2.1175 +
2.1176 + void markCommonPath(Node node, int rorder, Node& wnode, Node& znode,
2.1177 + OrderList& order_list, OrderMap& order_map,
2.1178 + NodeData& node_data, EdgeLists& edge_lists,
2.1179 + EmbedEdge& embed_edge, MergeRoots& merge_roots,
2.1180 + ChildLists& child_lists, AncestorMap& ancestor_map,
2.1181 + LowMap& low_map) {
2.1182 +
2.1183 + Node cnode = node;
2.1184 + Node pred = INVALID;
2.1185 +
2.1186 + while (true) {
2.1187 +
2.1188 + bool pert = pertinent(cnode, embed_edge, merge_roots);
2.1189 + bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
2.1190 +
2.1191 + if (pert && ext) {
2.1192 + if (!merge_roots[cnode].empty()) {
2.1193 + int cn = merge_roots[cnode].back();
2.1194 +
2.1195 + if (low_map[order_list[cn - order_list.size()]] < rorder) {
2.1196 + Edge edge = node_data[cn].first;
2.1197 + _kuratowski.set(edge, true);
2.1198 +
2.1199 + pred = cnode;
2.1200 + cnode = _ugraph.target(edge);
2.1201 +
2.1202 + continue;
2.1203 + }
2.1204 + }
2.1205 + wnode = znode = cnode;
2.1206 + return;
2.1207 +
2.1208 + } else if (pert) {
2.1209 + wnode = cnode;
2.1210 +
2.1211 + while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
2.1212 + Edge edge = node_data[order_map[cnode]].first;
2.1213 +
2.1214 + if (_ugraph.target(edge) == pred) {
2.1215 + edge = edge_lists[edge].next;
2.1216 + }
2.1217 + _kuratowski.set(edge, true);
2.1218 +
2.1219 + Node next = _ugraph.target(edge);
2.1220 + pred = cnode; cnode = next;
2.1221 + }
2.1222 +
2.1223 + znode = cnode;
2.1224 + return;
2.1225 +
2.1226 + } else if (ext) {
2.1227 + znode = cnode;
2.1228 +
2.1229 + while (!pertinent(cnode, embed_edge, merge_roots)) {
2.1230 + Edge edge = node_data[order_map[cnode]].first;
2.1231 +
2.1232 + if (_ugraph.target(edge) == pred) {
2.1233 + edge = edge_lists[edge].next;
2.1234 + }
2.1235 + _kuratowski.set(edge, true);
2.1236 +
2.1237 + Node next = _ugraph.target(edge);
2.1238 + pred = cnode; cnode = next;
2.1239 + }
2.1240 +
2.1241 + wnode = cnode;
2.1242 + return;
2.1243 +
2.1244 + } else {
2.1245 + Edge edge = node_data[order_map[cnode]].first;
2.1246 +
2.1247 + if (_ugraph.target(edge) == pred) {
2.1248 + edge = edge_lists[edge].next;
2.1249 + }
2.1250 + _kuratowski.set(edge, true);
2.1251 +
2.1252 + Node next = _ugraph.target(edge);
2.1253 + pred = cnode; cnode = next;
2.1254 + }
2.1255 +
2.1256 + }
2.1257 +
2.1258 + }
2.1259 +
2.1260 + void orientComponent(Node root, int rn, OrderMap& order_map,
2.1261 + PredMap& pred_map, NodeData& node_data,
2.1262 + EdgeLists& edge_lists, FlipMap& flip_map,
2.1263 + TypeMap& type_map) {
2.1264 + node_data[order_map[root]].first = node_data[rn].first;
2.1265 + type_map[root] = 1;
2.1266 +
2.1267 + std::vector<Node> st, qu;
2.1268 +
2.1269 + st.push_back(root);
2.1270 + while (!st.empty()) {
2.1271 + Node node = st.back();
2.1272 + st.pop_back();
2.1273 + qu.push_back(node);
2.1274 +
2.1275 + Edge edge = node_data[order_map[node]].first;
2.1276 +
2.1277 + if (type_map[_ugraph.target(edge)] == 0) {
2.1278 + st.push_back(_ugraph.target(edge));
2.1279 + type_map[_ugraph.target(edge)] = 1;
2.1280 + }
2.1281 +
2.1282 + Edge last = edge, pred = edge;
2.1283 + edge = edge_lists[edge].next;
2.1284 + while (edge != last) {
2.1285 +
2.1286 + if (type_map[_ugraph.target(edge)] == 0) {
2.1287 + st.push_back(_ugraph.target(edge));
2.1288 + type_map[_ugraph.target(edge)] = 1;
2.1289 + }
2.1290 +
2.1291 + Edge next = edge_lists[edge].next != pred ?
2.1292 + edge_lists[edge].next : edge_lists[edge].prev;
2.1293 + pred = edge; edge = next;
2.1294 + }
2.1295 +
2.1296 + }
2.1297 +
2.1298 + type_map[root] = 2;
2.1299 + flip_map[root] = false;
2.1300 +
2.1301 + for (int i = 1; i < int(qu.size()); ++i) {
2.1302 +
2.1303 + Node node = qu[i];
2.1304 +
2.1305 + while (type_map[node] != 2) {
2.1306 + st.push_back(node);
2.1307 + type_map[node] = 2;
2.1308 + node = _ugraph.source(pred_map[node]);
2.1309 + }
2.1310 +
2.1311 + bool flip = flip_map[node];
2.1312 +
2.1313 + while (!st.empty()) {
2.1314 + node = st.back();
2.1315 + st.pop_back();
2.1316 +
2.1317 + flip_map[node] = flip != flip_map[node];
2.1318 + flip = flip_map[node];
2.1319 +
2.1320 + if (flip) {
2.1321 + Edge edge = node_data[order_map[node]].first;
2.1322 + std::swap(edge_lists[edge].prev, edge_lists[edge].next);
2.1323 + edge = edge_lists[edge].prev;
2.1324 + std::swap(edge_lists[edge].prev, edge_lists[edge].next);
2.1325 + node_data[order_map[node]].first = edge;
2.1326 + }
2.1327 + }
2.1328 + }
2.1329 +
2.1330 + for (int i = 0; i < int(qu.size()); ++i) {
2.1331 +
2.1332 + Edge edge = node_data[order_map[qu[i]]].first;
2.1333 + Edge last = edge, pred = edge;
2.1334 +
2.1335 + edge = edge_lists[edge].next;
2.1336 + while (edge != last) {
2.1337 +
2.1338 + if (edge_lists[edge].next == pred) {
2.1339 + std::swap(edge_lists[edge].next, edge_lists[edge].prev);
2.1340 + }
2.1341 + pred = edge; edge = edge_lists[edge].next;
2.1342 + }
2.1343 +
2.1344 + }
2.1345 + }
2.1346 +
2.1347 + void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode,
2.1348 + OrderMap& order_map, NodeData& node_data,
2.1349 + TypeMap& type_map) {
2.1350 + Node node = _ugraph.target(node_data[order_map[root]].first);
2.1351 +
2.1352 + while (node != ynode) {
2.1353 + type_map[node] = HIGHY;
2.1354 + node = _ugraph.target(node_data[order_map[node]].first);
2.1355 + }
2.1356 +
2.1357 + while (node != wnode) {
2.1358 + type_map[node] = LOWY;
2.1359 + node = _ugraph.target(node_data[order_map[node]].first);
2.1360 + }
2.1361 +
2.1362 + node = _ugraph.target(node_data[order_map[wnode]].first);
2.1363 +
2.1364 + while (node != xnode) {
2.1365 + type_map[node] = LOWX;
2.1366 + node = _ugraph.target(node_data[order_map[node]].first);
2.1367 + }
2.1368 + type_map[node] = LOWX;
2.1369 +
2.1370 + node = _ugraph.target(node_data[order_map[xnode]].first);
2.1371 + while (node != root) {
2.1372 + type_map[node] = HIGHX;
2.1373 + node = _ugraph.target(node_data[order_map[node]].first);
2.1374 + }
2.1375 +
2.1376 + type_map[wnode] = PERTINENT;
2.1377 + type_map[root] = ROOT;
2.1378 + }
2.1379 +
2.1380 + void findInternalPath(std::vector<Edge>& ipath,
2.1381 + Node wnode, Node root, TypeMap& type_map,
2.1382 + OrderMap& order_map, NodeData& node_data,
2.1383 + EdgeLists& edge_lists) {
2.1384 + std::vector<Edge> st;
2.1385 +
2.1386 + Node node = wnode;
2.1387 +
2.1388 + while (node != root) {
2.1389 + Edge edge = edge_lists[node_data[order_map[node]].first].next;
2.1390 + st.push_back(edge);
2.1391 + node = _ugraph.target(edge);
2.1392 + }
2.1393 +
2.1394 + while (true) {
2.1395 + Edge edge = st.back();
2.1396 + if (type_map[_ugraph.target(edge)] == LOWX ||
2.1397 + type_map[_ugraph.target(edge)] == HIGHX) {
2.1398 + break;
2.1399 + }
2.1400 + if (type_map[_ugraph.target(edge)] == 2) {
2.1401 + type_map[_ugraph.target(edge)] = 3;
2.1402 +
2.1403 + edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
2.1404 + st.push_back(edge);
2.1405 + } else {
2.1406 + st.pop_back();
2.1407 + edge = edge_lists[edge].next;
2.1408 +
2.1409 + while (_ugraph.oppositeEdge(edge) == st.back()) {
2.1410 + edge = st.back();
2.1411 + st.pop_back();
2.1412 + edge = edge_lists[edge].next;
2.1413 + }
2.1414 + st.push_back(edge);
2.1415 + }
2.1416 + }
2.1417 +
2.1418 + for (int i = 0; i < int(st.size()); ++i) {
2.1419 + if (type_map[_ugraph.target(st[i])] != LOWY &&
2.1420 + type_map[_ugraph.target(st[i])] != HIGHY) {
2.1421 + for (; i < int(st.size()); ++i) {
2.1422 + ipath.push_back(st[i]);
2.1423 + }
2.1424 + }
2.1425 + }
2.1426 + }
2.1427 +
2.1428 + void setInternalFlags(std::vector<Edge>& ipath, TypeMap& type_map) {
2.1429 + for (int i = 1; i < int(ipath.size()); ++i) {
2.1430 + type_map[_ugraph.source(ipath[i])] = INTERNAL;
2.1431 + }
2.1432 + }
2.1433 +
2.1434 + void findPilePath(std::vector<Edge>& ppath,
2.1435 + Node root, TypeMap& type_map, OrderMap& order_map,
2.1436 + NodeData& node_data, EdgeLists& edge_lists) {
2.1437 + std::vector<Edge> st;
2.1438 +
2.1439 + st.push_back(_ugraph.oppositeEdge(node_data[order_map[root]].first));
2.1440 + st.push_back(node_data[order_map[root]].first);
2.1441 +
2.1442 + while (st.size() > 1) {
2.1443 + Edge edge = st.back();
2.1444 + if (type_map[_ugraph.target(edge)] == INTERNAL) {
2.1445 + break;
2.1446 + }
2.1447 + if (type_map[_ugraph.target(edge)] == 3) {
2.1448 + type_map[_ugraph.target(edge)] = 4;
2.1449 +
2.1450 + edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
2.1451 + st.push_back(edge);
2.1452 + } else {
2.1453 + st.pop_back();
2.1454 + edge = edge_lists[edge].next;
2.1455 +
2.1456 + while (!st.empty() && _ugraph.oppositeEdge(edge) == st.back()) {
2.1457 + edge = st.back();
2.1458 + st.pop_back();
2.1459 + edge = edge_lists[edge].next;
2.1460 + }
2.1461 + st.push_back(edge);
2.1462 + }
2.1463 + }
2.1464 +
2.1465 + for (int i = 1; i < int(st.size()); ++i) {
2.1466 + ppath.push_back(st[i]);
2.1467 + }
2.1468 + }
2.1469 +
2.1470 +
2.1471 + int markExternalPath(Node node, OrderMap& order_map,
2.1472 + ChildLists& child_lists, PredMap& pred_map,
2.1473 + AncestorMap& ancestor_map, LowMap& low_map) {
2.1474 + int lp = lowPoint(node, order_map, child_lists,
2.1475 + ancestor_map, low_map);
2.1476 +
2.1477 + if (ancestor_map[node] != lp) {
2.1478 + node = child_lists[node].first;
2.1479 + _kuratowski[pred_map[node]] = true;
2.1480 +
2.1481 + while (ancestor_map[node] != lp) {
2.1482 + for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
2.1483 + Node tnode = _ugraph.target(e);
2.1484 + if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) {
2.1485 + node = tnode;
2.1486 + _kuratowski[e] = true;
2.1487 + break;
2.1488 + }
2.1489 + }
2.1490 + }
2.1491 + }
2.1492 +
2.1493 + for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
2.1494 + if (order_map[_ugraph.target(e)] == lp) {
2.1495 + _kuratowski[e] = true;
2.1496 + break;
2.1497 + }
2.1498 + }
2.1499 +
2.1500 + return lp;
2.1501 + }
2.1502 +
2.1503 + void markPertinentPath(Node node, OrderMap& order_map,
2.1504 + NodeData& node_data, EdgeLists& edge_lists,
2.1505 + EmbedEdge& embed_edge, MergeRoots& merge_roots) {
2.1506 + while (embed_edge[node] == INVALID) {
2.1507 + int n = merge_roots[node].front();
2.1508 + Edge edge = node_data[n].first;
2.1509 +
2.1510 + _kuratowski.set(edge, true);
2.1511 +
2.1512 + Node pred = node;
2.1513 + node = _ugraph.target(edge);
2.1514 + while (!pertinent(node, embed_edge, merge_roots)) {
2.1515 + edge = node_data[order_map[node]].first;
2.1516 + if (_ugraph.target(edge) == pred) {
2.1517 + edge = edge_lists[edge].next;
2.1518 + }
2.1519 + _kuratowski.set(edge, true);
2.1520 + pred = node;
2.1521 + node = _ugraph.target(edge);
2.1522 + }
2.1523 + }
2.1524 + _kuratowski.set(embed_edge[node], true);
2.1525 + }
2.1526 +
2.1527 + void markPredPath(Node node, Node snode, PredMap& pred_map) {
2.1528 + while (node != snode) {
2.1529 + _kuratowski.set(pred_map[node], true);
2.1530 + node = _ugraph.source(pred_map[node]);
2.1531 + }
2.1532 + }
2.1533 +
2.1534 + void markFacePath(Node ynode, Node xnode,
2.1535 + OrderMap& order_map, NodeData& node_data) {
2.1536 + Edge edge = node_data[order_map[ynode]].first;
2.1537 + Node node = _ugraph.target(edge);
2.1538 + _kuratowski.set(edge, true);
2.1539 +
2.1540 + while (node != xnode) {
2.1541 + edge = node_data[order_map[node]].first;
2.1542 + _kuratowski.set(edge, true);
2.1543 + node = _ugraph.target(edge);
2.1544 + }
2.1545 + }
2.1546 +
2.1547 + void markInternalPath(std::vector<Edge>& path) {
2.1548 + for (int i = 0; i < int(path.size()); ++i) {
2.1549 + _kuratowski.set(path[i], true);
2.1550 + }
2.1551 + }
2.1552 +
2.1553 + void markPilePath(std::vector<Edge>& path) {
2.1554 + for (int i = 0; i < int(path.size()); ++i) {
2.1555 + _kuratowski.set(path[i], true);
2.1556 + }
2.1557 + }
2.1558 +
2.1559 + void isolateKuratowski(Edge edge, NodeData& node_data,
2.1560 + EdgeLists& edge_lists, FlipMap& flip_map,
2.1561 + OrderMap& order_map, OrderList& order_list,
2.1562 + PredMap& pred_map, ChildLists& child_lists,
2.1563 + AncestorMap& ancestor_map, LowMap& low_map,
2.1564 + EmbedEdge& embed_edge, MergeRoots& merge_roots) {
2.1565 +
2.1566 + Node root = _ugraph.source(edge);
2.1567 + Node enode = _ugraph.target(edge);
2.1568 +
2.1569 + int rorder = order_map[root];
2.1570 +
2.1571 + TypeMap type_map(_ugraph, 0);
2.1572 +
2.1573 + int rn = findComponentRoot(root, enode, child_lists,
2.1574 + order_map, order_list);
2.1575 +
2.1576 + Node xnode = order_list[node_data[rn].next];
2.1577 + Node ynode = order_list[node_data[rn].prev];
2.1578 +
2.1579 + // Minor-A
2.1580 + {
2.1581 + while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
2.1582 +
2.1583 + if (!merge_roots[xnode].empty()) {
2.1584 + root = xnode;
2.1585 + rn = merge_roots[xnode].front();
2.1586 + } else {
2.1587 + root = ynode;
2.1588 + rn = merge_roots[ynode].front();
2.1589 + }
2.1590 +
2.1591 + xnode = order_list[node_data[rn].next];
2.1592 + ynode = order_list[node_data[rn].prev];
2.1593 + }
2.1594 +
2.1595 + if (root != _ugraph.source(edge)) {
2.1596 + orientComponent(root, rn, order_map, pred_map,
2.1597 + node_data, edge_lists, flip_map, type_map);
2.1598 + markFacePath(root, root, order_map, node_data);
2.1599 + int xlp = markExternalPath(xnode, order_map, child_lists,
2.1600 + pred_map, ancestor_map, low_map);
2.1601 + int ylp = markExternalPath(ynode, order_map, child_lists,
2.1602 + pred_map, ancestor_map, low_map);
2.1603 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
2.1604 + Node lwnode = findPertinent(ynode, order_map, node_data,
2.1605 + embed_edge, merge_roots);
2.1606 +
2.1607 + markPertinentPath(lwnode, order_map, node_data, edge_lists,
2.1608 + embed_edge, merge_roots);
2.1609 +
2.1610 + return;
2.1611 + }
2.1612 + }
2.1613 +
2.1614 + orientComponent(root, rn, order_map, pred_map,
2.1615 + node_data, edge_lists, flip_map, type_map);
2.1616 +
2.1617 + Node wnode = findPertinent(ynode, order_map, node_data,
2.1618 + embed_edge, merge_roots);
2.1619 + setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map);
2.1620 +
2.1621 +
2.1622 + //Minor-B
2.1623 + if (!merge_roots[wnode].empty()) {
2.1624 + int cn = merge_roots[wnode].back();
2.1625 + Node rep = order_list[cn - order_list.size()];
2.1626 + if (low_map[rep] < rorder) {
2.1627 + markFacePath(root, root, order_map, node_data);
2.1628 + int xlp = markExternalPath(xnode, order_map, child_lists,
2.1629 + pred_map, ancestor_map, low_map);
2.1630 + int ylp = markExternalPath(ynode, order_map, child_lists,
2.1631 + pred_map, ancestor_map, low_map);
2.1632 +
2.1633 + Node lwnode, lznode;
2.1634 + markCommonPath(wnode, rorder, lwnode, lznode, order_list,
2.1635 + order_map, node_data, edge_lists, embed_edge,
2.1636 + merge_roots, child_lists, ancestor_map, low_map);
2.1637 +
2.1638 + markPertinentPath(lwnode, order_map, node_data, edge_lists,
2.1639 + embed_edge, merge_roots);
2.1640 + int zlp = markExternalPath(lznode, order_map, child_lists,
2.1641 + pred_map, ancestor_map, low_map);
2.1642 +
2.1643 + int minlp = xlp < ylp ? xlp : ylp;
2.1644 + if (zlp < minlp) minlp = zlp;
2.1645 +
2.1646 + int maxlp = xlp > ylp ? xlp : ylp;
2.1647 + if (zlp > maxlp) maxlp = zlp;
2.1648 +
2.1649 + markPredPath(order_list[maxlp], order_list[minlp], pred_map);
2.1650 +
2.1651 + return;
2.1652 + }
2.1653 + }
2.1654 +
2.1655 + Node pxnode, pynode;
2.1656 + std::vector<Edge> ipath;
2.1657 + findInternalPath(ipath, wnode, root, type_map, order_map,
2.1658 + node_data, edge_lists);
2.1659 + setInternalFlags(ipath, type_map);
2.1660 + pynode = _ugraph.source(ipath.front());
2.1661 + pxnode = _ugraph.target(ipath.back());
2.1662 +
2.1663 + wnode = findPertinent(pynode, order_map, node_data,
2.1664 + embed_edge, merge_roots);
2.1665 +
2.1666 + // Minor-C
2.1667 + {
2.1668 + if (type_map[_ugraph.source(ipath.front())] == HIGHY) {
2.1669 + if (type_map[_ugraph.target(ipath.back())] == HIGHX) {
2.1670 + markFacePath(xnode, pxnode, order_map, node_data);
2.1671 + }
2.1672 + markFacePath(root, xnode, order_map, node_data);
2.1673 + markPertinentPath(wnode, order_map, node_data, edge_lists,
2.1674 + embed_edge, merge_roots);
2.1675 + markInternalPath(ipath);
2.1676 + int xlp = markExternalPath(xnode, order_map, child_lists,
2.1677 + pred_map, ancestor_map, low_map);
2.1678 + int ylp = markExternalPath(ynode, order_map, child_lists,
2.1679 + pred_map, ancestor_map, low_map);
2.1680 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
2.1681 + return;
2.1682 + }
2.1683 +
2.1684 + if (type_map[_ugraph.target(ipath.back())] == HIGHX) {
2.1685 + markFacePath(ynode, root, order_map, node_data);
2.1686 + markPertinentPath(wnode, order_map, node_data, edge_lists,
2.1687 + embed_edge, merge_roots);
2.1688 + markInternalPath(ipath);
2.1689 + int xlp = markExternalPath(xnode, order_map, child_lists,
2.1690 + pred_map, ancestor_map, low_map);
2.1691 + int ylp = markExternalPath(ynode, order_map, child_lists,
2.1692 + pred_map, ancestor_map, low_map);
2.1693 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
2.1694 + return;
2.1695 + }
2.1696 + }
2.1697 +
2.1698 + std::vector<Edge> ppath;
2.1699 + findPilePath(ppath, root, type_map, order_map, node_data, edge_lists);
2.1700 +
2.1701 + // Minor-D
2.1702 + if (!ppath.empty()) {
2.1703 + markFacePath(ynode, xnode, order_map, node_data);
2.1704 + markPertinentPath(wnode, order_map, node_data, edge_lists,
2.1705 + embed_edge, merge_roots);
2.1706 + markPilePath(ppath);
2.1707 + markInternalPath(ipath);
2.1708 + int xlp = markExternalPath(xnode, order_map, child_lists,
2.1709 + pred_map, ancestor_map, low_map);
2.1710 + int ylp = markExternalPath(ynode, order_map, child_lists,
2.1711 + pred_map, ancestor_map, low_map);
2.1712 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
2.1713 + return;
2.1714 + }
2.1715 +
2.1716 + // Minor-E*
2.1717 + {
2.1718 +
2.1719 + if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
2.1720 + Node znode = findExternal(pynode, rorder, order_map,
2.1721 + child_lists, ancestor_map,
2.1722 + low_map, node_data);
2.1723 +
2.1724 + if (type_map[znode] == LOWY) {
2.1725 + markFacePath(root, xnode, order_map, node_data);
2.1726 + markPertinentPath(wnode, order_map, node_data, edge_lists,
2.1727 + embed_edge, merge_roots);
2.1728 + markInternalPath(ipath);
2.1729 + int xlp = markExternalPath(xnode, order_map, child_lists,
2.1730 + pred_map, ancestor_map, low_map);
2.1731 + int zlp = markExternalPath(znode, order_map, child_lists,
2.1732 + pred_map, ancestor_map, low_map);
2.1733 + markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map);
2.1734 + } else {
2.1735 + markFacePath(ynode, root, order_map, node_data);
2.1736 + markPertinentPath(wnode, order_map, node_data, edge_lists,
2.1737 + embed_edge, merge_roots);
2.1738 + markInternalPath(ipath);
2.1739 + int ylp = markExternalPath(ynode, order_map, child_lists,
2.1740 + pred_map, ancestor_map, low_map);
2.1741 + int zlp = markExternalPath(znode, order_map, child_lists,
2.1742 + pred_map, ancestor_map, low_map);
2.1743 + markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map);
2.1744 + }
2.1745 + return;
2.1746 + }
2.1747 +
2.1748 + int xlp = markExternalPath(xnode, order_map, child_lists,
2.1749 + pred_map, ancestor_map, low_map);
2.1750 + int ylp = markExternalPath(ynode, order_map, child_lists,
2.1751 + pred_map, ancestor_map, low_map);
2.1752 + int wlp = markExternalPath(wnode, order_map, child_lists,
2.1753 + pred_map, ancestor_map, low_map);
2.1754 +
2.1755 + if (wlp > xlp && wlp > ylp) {
2.1756 + markFacePath(root, root, order_map, node_data);
2.1757 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
2.1758 + return;
2.1759 + }
2.1760 +
2.1761 + markInternalPath(ipath);
2.1762 + markPertinentPath(wnode, order_map, node_data, edge_lists,
2.1763 + embed_edge, merge_roots);
2.1764 +
2.1765 + if (xlp > ylp && xlp > wlp) {
2.1766 + markFacePath(root, pynode, order_map, node_data);
2.1767 + markFacePath(wnode, xnode, order_map, node_data);
2.1768 + markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map);
2.1769 + return;
2.1770 + }
2.1771 +
2.1772 + if (ylp > xlp && ylp > wlp) {
2.1773 + markFacePath(pxnode, root, order_map, node_data);
2.1774 + markFacePath(ynode, wnode, order_map, node_data);
2.1775 + markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map);
2.1776 + return;
2.1777 + }
2.1778 +
2.1779 + if (pynode != ynode) {
2.1780 + markFacePath(pxnode, wnode, order_map, node_data);
2.1781 +
2.1782 + int minlp = xlp < ylp ? xlp : ylp;
2.1783 + if (wlp < minlp) minlp = wlp;
2.1784 +
2.1785 + int maxlp = xlp > ylp ? xlp : ylp;
2.1786 + if (wlp > maxlp) maxlp = wlp;
2.1787 +
2.1788 + markPredPath(order_list[maxlp], order_list[minlp], pred_map);
2.1789 + return;
2.1790 + }
2.1791 +
2.1792 + if (pxnode != xnode) {
2.1793 + markFacePath(wnode, pynode, order_map, node_data);
2.1794 +
2.1795 + int minlp = xlp < ylp ? xlp : ylp;
2.1796 + if (wlp < minlp) minlp = wlp;
2.1797 +
2.1798 + int maxlp = xlp > ylp ? xlp : ylp;
2.1799 + if (wlp > maxlp) maxlp = wlp;
2.1800 +
2.1801 + markPredPath(order_list[maxlp], order_list[minlp], pred_map);
2.1802 + return;
2.1803 + }
2.1804 +
2.1805 + markFacePath(root, root, order_map, node_data);
2.1806 + int minlp = xlp < ylp ? xlp : ylp;
2.1807 + if (wlp < minlp) minlp = wlp;
2.1808 + markPredPath(root, order_list[minlp], pred_map);
2.1809 + return;
2.1810 + }
2.1811 +
2.1812 + }
2.1813 +
2.1814 + };
2.1815 +
2.1816 +}
2.1817 +
2.1818 +#endif