1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/planarity.h Sun Aug 11 15:28:12 2013 +0200
1.3 @@ -0,0 +1,2754 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2010
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_PLANARITY_H
1.23 +#define LEMON_PLANARITY_H
1.24 +
1.25 +/// \ingroup planar
1.26 +/// \file
1.27 +/// \brief Planarity checking, embedding, drawing and coloring
1.28 +
1.29 +#include <vector>
1.30 +#include <list>
1.31 +
1.32 +#include <lemon/dfs.h>
1.33 +#include <lemon/bfs.h>
1.34 +#include <lemon/radix_sort.h>
1.35 +#include <lemon/maps.h>
1.36 +#include <lemon/path.h>
1.37 +#include <lemon/bucket_heap.h>
1.38 +#include <lemon/adaptors.h>
1.39 +#include <lemon/edge_set.h>
1.40 +#include <lemon/color.h>
1.41 +#include <lemon/dim2.h>
1.42 +
1.43 +namespace lemon {
1.44 +
1.45 + namespace _planarity_bits {
1.46 +
1.47 + template <typename Graph>
1.48 + struct PlanarityVisitor : DfsVisitor<Graph> {
1.49 +
1.50 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.51 +
1.52 + typedef typename Graph::template NodeMap<Arc> PredMap;
1.53 +
1.54 + typedef typename Graph::template EdgeMap<bool> TreeMap;
1.55 +
1.56 + typedef typename Graph::template NodeMap<int> OrderMap;
1.57 + typedef std::vector<Node> OrderList;
1.58 +
1.59 + typedef typename Graph::template NodeMap<int> LowMap;
1.60 + typedef typename Graph::template NodeMap<int> AncestorMap;
1.61 +
1.62 + PlanarityVisitor(const Graph& graph,
1.63 + PredMap& pred_map, TreeMap& tree_map,
1.64 + OrderMap& order_map, OrderList& order_list,
1.65 + AncestorMap& ancestor_map, LowMap& low_map)
1.66 + : _graph(graph), _pred_map(pred_map), _tree_map(tree_map),
1.67 + _order_map(order_map), _order_list(order_list),
1.68 + _ancestor_map(ancestor_map), _low_map(low_map) {}
1.69 +
1.70 + void reach(const Node& node) {
1.71 + _order_map[node] = _order_list.size();
1.72 + _low_map[node] = _order_list.size();
1.73 + _ancestor_map[node] = _order_list.size();
1.74 + _order_list.push_back(node);
1.75 + }
1.76 +
1.77 + void discover(const Arc& arc) {
1.78 + Node target = _graph.target(arc);
1.79 +
1.80 + _tree_map[arc] = true;
1.81 + _pred_map[target] = arc;
1.82 + }
1.83 +
1.84 + void examine(const Arc& arc) {
1.85 + Node source = _graph.source(arc);
1.86 + Node target = _graph.target(arc);
1.87 +
1.88 + if (_order_map[target] < _order_map[source] && !_tree_map[arc]) {
1.89 + if (_low_map[source] > _order_map[target]) {
1.90 + _low_map[source] = _order_map[target];
1.91 + }
1.92 + if (_ancestor_map[source] > _order_map[target]) {
1.93 + _ancestor_map[source] = _order_map[target];
1.94 + }
1.95 + }
1.96 + }
1.97 +
1.98 + void backtrack(const Arc& arc) {
1.99 + Node source = _graph.source(arc);
1.100 + Node target = _graph.target(arc);
1.101 +
1.102 + if (_low_map[source] > _low_map[target]) {
1.103 + _low_map[source] = _low_map[target];
1.104 + }
1.105 + }
1.106 +
1.107 + const Graph& _graph;
1.108 + PredMap& _pred_map;
1.109 + TreeMap& _tree_map;
1.110 + OrderMap& _order_map;
1.111 + OrderList& _order_list;
1.112 + AncestorMap& _ancestor_map;
1.113 + LowMap& _low_map;
1.114 + };
1.115 +
1.116 + template <typename Graph, bool embedding = true>
1.117 + struct NodeDataNode {
1.118 + int prev, next;
1.119 + int visited;
1.120 + typename Graph::Arc first;
1.121 + bool inverted;
1.122 + };
1.123 +
1.124 + template <typename Graph>
1.125 + struct NodeDataNode<Graph, false> {
1.126 + int prev, next;
1.127 + int visited;
1.128 + };
1.129 +
1.130 + template <typename Graph>
1.131 + struct ChildListNode {
1.132 + typedef typename Graph::Node Node;
1.133 + Node first;
1.134 + Node prev, next;
1.135 + };
1.136 +
1.137 + template <typename Graph>
1.138 + struct ArcListNode {
1.139 + typename Graph::Arc prev, next;
1.140 + };
1.141 +
1.142 + template <typename Graph>
1.143 + class PlanarityChecking {
1.144 + private:
1.145 +
1.146 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.147 +
1.148 + const Graph& _graph;
1.149 +
1.150 + private:
1.151 +
1.152 + typedef typename Graph::template NodeMap<Arc> PredMap;
1.153 +
1.154 + typedef typename Graph::template EdgeMap<bool> TreeMap;
1.155 +
1.156 + typedef typename Graph::template NodeMap<int> OrderMap;
1.157 + typedef std::vector<Node> OrderList;
1.158 +
1.159 + typedef typename Graph::template NodeMap<int> LowMap;
1.160 + typedef typename Graph::template NodeMap<int> AncestorMap;
1.161 +
1.162 + typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
1.163 + typedef std::vector<NodeDataNode> NodeData;
1.164 +
1.165 + typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
1.166 + typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
1.167 +
1.168 + typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
1.169 +
1.170 + typedef typename Graph::template NodeMap<bool> EmbedArc;
1.171 +
1.172 + public:
1.173 +
1.174 + PlanarityChecking(const Graph& graph) : _graph(graph) {}
1.175 +
1.176 + bool run() {
1.177 + typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
1.178 +
1.179 + PredMap pred_map(_graph, INVALID);
1.180 + TreeMap tree_map(_graph, false);
1.181 +
1.182 + OrderMap order_map(_graph, -1);
1.183 + OrderList order_list;
1.184 +
1.185 + AncestorMap ancestor_map(_graph, -1);
1.186 + LowMap low_map(_graph, -1);
1.187 +
1.188 + Visitor visitor(_graph, pred_map, tree_map,
1.189 + order_map, order_list, ancestor_map, low_map);
1.190 + DfsVisit<Graph, Visitor> visit(_graph, visitor);
1.191 + visit.run();
1.192 +
1.193 + ChildLists child_lists(_graph);
1.194 + createChildLists(tree_map, order_map, low_map, child_lists);
1.195 +
1.196 + NodeData node_data(2 * order_list.size());
1.197 +
1.198 + EmbedArc embed_arc(_graph, false);
1.199 +
1.200 + MergeRoots merge_roots(_graph);
1.201 +
1.202 + for (int i = order_list.size() - 1; i >= 0; --i) {
1.203 +
1.204 + Node node = order_list[i];
1.205 +
1.206 + Node source = node;
1.207 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.208 + Node target = _graph.target(e);
1.209 +
1.210 + if (order_map[source] < order_map[target] && tree_map[e]) {
1.211 + initFace(target, node_data, order_map, order_list);
1.212 + }
1.213 + }
1.214 +
1.215 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.216 + Node target = _graph.target(e);
1.217 +
1.218 + if (order_map[source] < order_map[target] && !tree_map[e]) {
1.219 + embed_arc[target] = true;
1.220 + walkUp(target, source, i, pred_map, low_map,
1.221 + order_map, order_list, node_data, merge_roots);
1.222 + }
1.223 + }
1.224 +
1.225 + for (typename MergeRoots::Value::iterator it =
1.226 + merge_roots[node].begin();
1.227 + it != merge_roots[node].end(); ++it) {
1.228 + int rn = *it;
1.229 + walkDown(rn, i, node_data, order_list, child_lists,
1.230 + ancestor_map, low_map, embed_arc, merge_roots);
1.231 + }
1.232 + merge_roots[node].clear();
1.233 +
1.234 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.235 + Node target = _graph.target(e);
1.236 +
1.237 + if (order_map[source] < order_map[target] && !tree_map[e]) {
1.238 + if (embed_arc[target]) {
1.239 + return false;
1.240 + }
1.241 + }
1.242 + }
1.243 + }
1.244 +
1.245 + return true;
1.246 + }
1.247 +
1.248 + private:
1.249 +
1.250 + void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
1.251 + const LowMap& low_map, ChildLists& child_lists) {
1.252 +
1.253 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.254 + Node source = n;
1.255 +
1.256 + std::vector<Node> targets;
1.257 + for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.258 + Node target = _graph.target(e);
1.259 +
1.260 + if (order_map[source] < order_map[target] && tree_map[e]) {
1.261 + targets.push_back(target);
1.262 + }
1.263 + }
1.264 +
1.265 + if (targets.size() == 0) {
1.266 + child_lists[source].first = INVALID;
1.267 + } else if (targets.size() == 1) {
1.268 + child_lists[source].first = targets[0];
1.269 + child_lists[targets[0]].prev = INVALID;
1.270 + child_lists[targets[0]].next = INVALID;
1.271 + } else {
1.272 + radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
1.273 + for (int i = 1; i < int(targets.size()); ++i) {
1.274 + child_lists[targets[i]].prev = targets[i - 1];
1.275 + child_lists[targets[i - 1]].next = targets[i];
1.276 + }
1.277 + child_lists[targets.back()].next = INVALID;
1.278 + child_lists[targets.front()].prev = INVALID;
1.279 + child_lists[source].first = targets.front();
1.280 + }
1.281 + }
1.282 + }
1.283 +
1.284 + void walkUp(const Node& node, Node root, int rorder,
1.285 + const PredMap& pred_map, const LowMap& low_map,
1.286 + const OrderMap& order_map, const OrderList& order_list,
1.287 + NodeData& node_data, MergeRoots& merge_roots) {
1.288 +
1.289 + int na, nb;
1.290 + bool da, db;
1.291 +
1.292 + na = nb = order_map[node];
1.293 + da = true; db = false;
1.294 +
1.295 + while (true) {
1.296 +
1.297 + if (node_data[na].visited == rorder) break;
1.298 + if (node_data[nb].visited == rorder) break;
1.299 +
1.300 + node_data[na].visited = rorder;
1.301 + node_data[nb].visited = rorder;
1.302 +
1.303 + int rn = -1;
1.304 +
1.305 + if (na >= int(order_list.size())) {
1.306 + rn = na;
1.307 + } else if (nb >= int(order_list.size())) {
1.308 + rn = nb;
1.309 + }
1.310 +
1.311 + if (rn == -1) {
1.312 + int nn;
1.313 +
1.314 + nn = da ? node_data[na].prev : node_data[na].next;
1.315 + da = node_data[nn].prev != na;
1.316 + na = nn;
1.317 +
1.318 + nn = db ? node_data[nb].prev : node_data[nb].next;
1.319 + db = node_data[nn].prev != nb;
1.320 + nb = nn;
1.321 +
1.322 + } else {
1.323 +
1.324 + Node rep = order_list[rn - order_list.size()];
1.325 + Node parent = _graph.source(pred_map[rep]);
1.326 +
1.327 + if (low_map[rep] < rorder) {
1.328 + merge_roots[parent].push_back(rn);
1.329 + } else {
1.330 + merge_roots[parent].push_front(rn);
1.331 + }
1.332 +
1.333 + if (parent != root) {
1.334 + na = nb = order_map[parent];
1.335 + da = true; db = false;
1.336 + } else {
1.337 + break;
1.338 + }
1.339 + }
1.340 + }
1.341 + }
1.342 +
1.343 + void walkDown(int rn, int rorder, NodeData& node_data,
1.344 + OrderList& order_list, ChildLists& child_lists,
1.345 + AncestorMap& ancestor_map, LowMap& low_map,
1.346 + EmbedArc& embed_arc, MergeRoots& merge_roots) {
1.347 +
1.348 + std::vector<std::pair<int, bool> > merge_stack;
1.349 +
1.350 + for (int di = 0; di < 2; ++di) {
1.351 + bool rd = di == 0;
1.352 + int pn = rn;
1.353 + int n = rd ? node_data[rn].next : node_data[rn].prev;
1.354 +
1.355 + while (n != rn) {
1.356 +
1.357 + Node node = order_list[n];
1.358 +
1.359 + if (embed_arc[node]) {
1.360 +
1.361 + // Merging components on the critical path
1.362 + while (!merge_stack.empty()) {
1.363 +
1.364 + // Component root
1.365 + int cn = merge_stack.back().first;
1.366 + bool cd = merge_stack.back().second;
1.367 + merge_stack.pop_back();
1.368 +
1.369 + // Parent of component
1.370 + int dn = merge_stack.back().first;
1.371 + bool dd = merge_stack.back().second;
1.372 + merge_stack.pop_back();
1.373 +
1.374 + Node parent = order_list[dn];
1.375 +
1.376 + // Erasing from merge_roots
1.377 + merge_roots[parent].pop_front();
1.378 +
1.379 + Node child = order_list[cn - order_list.size()];
1.380 +
1.381 + // Erasing from child_lists
1.382 + if (child_lists[child].prev != INVALID) {
1.383 + child_lists[child_lists[child].prev].next =
1.384 + child_lists[child].next;
1.385 + } else {
1.386 + child_lists[parent].first = child_lists[child].next;
1.387 + }
1.388 +
1.389 + if (child_lists[child].next != INVALID) {
1.390 + child_lists[child_lists[child].next].prev =
1.391 + child_lists[child].prev;
1.392 + }
1.393 +
1.394 + // Merging external faces
1.395 + {
1.396 + int en = cn;
1.397 + cn = cd ? node_data[cn].prev : node_data[cn].next;
1.398 + cd = node_data[cn].next == en;
1.399 +
1.400 + }
1.401 +
1.402 + if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
1.403 + if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
1.404 +
1.405 + }
1.406 +
1.407 + bool d = pn == node_data[n].prev;
1.408 +
1.409 + if (node_data[n].prev == node_data[n].next &&
1.410 + node_data[n].inverted) {
1.411 + d = !d;
1.412 + }
1.413 +
1.414 + // Embedding arc into external face
1.415 + if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
1.416 + if (d) node_data[n].prev = rn; else node_data[n].next = rn;
1.417 + pn = rn;
1.418 +
1.419 + embed_arc[order_list[n]] = false;
1.420 + }
1.421 +
1.422 + if (!merge_roots[node].empty()) {
1.423 +
1.424 + bool d = pn == node_data[n].prev;
1.425 +
1.426 + merge_stack.push_back(std::make_pair(n, d));
1.427 +
1.428 + int rn = merge_roots[node].front();
1.429 +
1.430 + int xn = node_data[rn].next;
1.431 + Node xnode = order_list[xn];
1.432 +
1.433 + int yn = node_data[rn].prev;
1.434 + Node ynode = order_list[yn];
1.435 +
1.436 + bool rd;
1.437 + if (!external(xnode, rorder, child_lists,
1.438 + ancestor_map, low_map)) {
1.439 + rd = true;
1.440 + } else if (!external(ynode, rorder, child_lists,
1.441 + ancestor_map, low_map)) {
1.442 + rd = false;
1.443 + } else if (pertinent(xnode, embed_arc, merge_roots)) {
1.444 + rd = true;
1.445 + } else {
1.446 + rd = false;
1.447 + }
1.448 +
1.449 + merge_stack.push_back(std::make_pair(rn, rd));
1.450 +
1.451 + pn = rn;
1.452 + n = rd ? xn : yn;
1.453 +
1.454 + } else if (!external(node, rorder, child_lists,
1.455 + ancestor_map, low_map)) {
1.456 + int nn = (node_data[n].next != pn ?
1.457 + node_data[n].next : node_data[n].prev);
1.458 +
1.459 + bool nd = n == node_data[nn].prev;
1.460 +
1.461 + if (nd) node_data[nn].prev = pn;
1.462 + else node_data[nn].next = pn;
1.463 +
1.464 + if (n == node_data[pn].prev) node_data[pn].prev = nn;
1.465 + else node_data[pn].next = nn;
1.466 +
1.467 + node_data[nn].inverted =
1.468 + (node_data[nn].prev == node_data[nn].next && nd != rd);
1.469 +
1.470 + n = nn;
1.471 + }
1.472 + else break;
1.473 +
1.474 + }
1.475 +
1.476 + if (!merge_stack.empty() || n == rn) {
1.477 + break;
1.478 + }
1.479 + }
1.480 + }
1.481 +
1.482 + void initFace(const Node& node, NodeData& node_data,
1.483 + const OrderMap& order_map, const OrderList& order_list) {
1.484 + int n = order_map[node];
1.485 + int rn = n + order_list.size();
1.486 +
1.487 + node_data[n].next = node_data[n].prev = rn;
1.488 + node_data[rn].next = node_data[rn].prev = n;
1.489 +
1.490 + node_data[n].visited = order_list.size();
1.491 + node_data[rn].visited = order_list.size();
1.492 +
1.493 + }
1.494 +
1.495 + bool external(const Node& node, int rorder,
1.496 + ChildLists& child_lists, AncestorMap& ancestor_map,
1.497 + LowMap& low_map) {
1.498 + Node child = child_lists[node].first;
1.499 +
1.500 + if (child != INVALID) {
1.501 + if (low_map[child] < rorder) return true;
1.502 + }
1.503 +
1.504 + if (ancestor_map[node] < rorder) return true;
1.505 +
1.506 + return false;
1.507 + }
1.508 +
1.509 + bool pertinent(const Node& node, const EmbedArc& embed_arc,
1.510 + const MergeRoots& merge_roots) {
1.511 + return !merge_roots[node].empty() || embed_arc[node];
1.512 + }
1.513 +
1.514 + };
1.515 +
1.516 + }
1.517 +
1.518 + /// \ingroup planar
1.519 + ///
1.520 + /// \brief Planarity checking of an undirected simple graph
1.521 + ///
1.522 + /// This function implements the Boyer-Myrvold algorithm for
1.523 + /// planarity checking of an undirected simple graph. It is a simplified
1.524 + /// version of the PlanarEmbedding algorithm class because neither
1.525 + /// the embedding nor the Kuratowski subdivisons are computed.
1.526 + template <typename GR>
1.527 + bool checkPlanarity(const GR& graph) {
1.528 + _planarity_bits::PlanarityChecking<GR> pc(graph);
1.529 + return pc.run();
1.530 + }
1.531 +
1.532 + /// \ingroup planar
1.533 + ///
1.534 + /// \brief Planar embedding of an undirected simple graph
1.535 + ///
1.536 + /// This class implements the Boyer-Myrvold algorithm for planar
1.537 + /// embedding of an undirected simple graph. The planar embedding is an
1.538 + /// ordering of the outgoing edges of the nodes, which is a possible
1.539 + /// configuration to draw the graph in the plane. If there is not
1.540 + /// such ordering then the graph contains a K<sub>5</sub> (full graph
1.541 + /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
1.542 + /// 3 Red and 3 Blue nodes) subdivision.
1.543 + ///
1.544 + /// The current implementation calculates either an embedding or a
1.545 + /// Kuratowski subdivision. The running time of the algorithm is O(n).
1.546 + ///
1.547 + /// \see PlanarDrawing, checkPlanarity()
1.548 + template <typename Graph>
1.549 + class PlanarEmbedding {
1.550 + private:
1.551 +
1.552 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.553 +
1.554 + const Graph& _graph;
1.555 + typename Graph::template ArcMap<Arc> _embedding;
1.556 +
1.557 + typename Graph::template EdgeMap<bool> _kuratowski;
1.558 +
1.559 + private:
1.560 +
1.561 + typedef typename Graph::template NodeMap<Arc> PredMap;
1.562 +
1.563 + typedef typename Graph::template EdgeMap<bool> TreeMap;
1.564 +
1.565 + typedef typename Graph::template NodeMap<int> OrderMap;
1.566 + typedef std::vector<Node> OrderList;
1.567 +
1.568 + typedef typename Graph::template NodeMap<int> LowMap;
1.569 + typedef typename Graph::template NodeMap<int> AncestorMap;
1.570 +
1.571 + typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode;
1.572 + typedef std::vector<NodeDataNode> NodeData;
1.573 +
1.574 + typedef _planarity_bits::ChildListNode<Graph> ChildListNode;
1.575 + typedef typename Graph::template NodeMap<ChildListNode> ChildLists;
1.576 +
1.577 + typedef typename Graph::template NodeMap<std::list<int> > MergeRoots;
1.578 +
1.579 + typedef typename Graph::template NodeMap<Arc> EmbedArc;
1.580 +
1.581 + typedef _planarity_bits::ArcListNode<Graph> ArcListNode;
1.582 + typedef typename Graph::template ArcMap<ArcListNode> ArcLists;
1.583 +
1.584 + typedef typename Graph::template NodeMap<bool> FlipMap;
1.585 +
1.586 + typedef typename Graph::template NodeMap<int> TypeMap;
1.587 +
1.588 + enum IsolatorNodeType {
1.589 + HIGHX = 6, LOWX = 7,
1.590 + HIGHY = 8, LOWY = 9,
1.591 + ROOT = 10, PERTINENT = 11,
1.592 + INTERNAL = 12
1.593 + };
1.594 +
1.595 + public:
1.596 +
1.597 + /// \brief The map type for storing the embedding
1.598 + ///
1.599 + /// The map type for storing the embedding.
1.600 + /// \see embeddingMap()
1.601 + typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
1.602 +
1.603 + /// \brief Constructor
1.604 + ///
1.605 + /// Constructor.
1.606 + /// \pre The graph must be simple, i.e. it should not
1.607 + /// contain parallel or loop arcs.
1.608 + PlanarEmbedding(const Graph& graph)
1.609 + : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
1.610 +
1.611 + /// \brief Run the algorithm.
1.612 + ///
1.613 + /// This function runs the algorithm.
1.614 + /// \param kuratowski If this parameter is set to \c false, then the
1.615 + /// algorithm does not compute a Kuratowski subdivision.
1.616 + /// \return \c true if the graph is planar.
1.617 + bool run(bool kuratowski = true) {
1.618 + typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
1.619 +
1.620 + PredMap pred_map(_graph, INVALID);
1.621 + TreeMap tree_map(_graph, false);
1.622 +
1.623 + OrderMap order_map(_graph, -1);
1.624 + OrderList order_list;
1.625 +
1.626 + AncestorMap ancestor_map(_graph, -1);
1.627 + LowMap low_map(_graph, -1);
1.628 +
1.629 + Visitor visitor(_graph, pred_map, tree_map,
1.630 + order_map, order_list, ancestor_map, low_map);
1.631 + DfsVisit<Graph, Visitor> visit(_graph, visitor);
1.632 + visit.run();
1.633 +
1.634 + ChildLists child_lists(_graph);
1.635 + createChildLists(tree_map, order_map, low_map, child_lists);
1.636 +
1.637 + NodeData node_data(2 * order_list.size());
1.638 +
1.639 + EmbedArc embed_arc(_graph, INVALID);
1.640 +
1.641 + MergeRoots merge_roots(_graph);
1.642 +
1.643 + ArcLists arc_lists(_graph);
1.644 +
1.645 + FlipMap flip_map(_graph, false);
1.646 +
1.647 + for (int i = order_list.size() - 1; i >= 0; --i) {
1.648 +
1.649 + Node node = order_list[i];
1.650 +
1.651 + node_data[i].first = INVALID;
1.652 +
1.653 + Node source = node;
1.654 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.655 + Node target = _graph.target(e);
1.656 +
1.657 + if (order_map[source] < order_map[target] && tree_map[e]) {
1.658 + initFace(target, arc_lists, node_data,
1.659 + pred_map, order_map, order_list);
1.660 + }
1.661 + }
1.662 +
1.663 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.664 + Node target = _graph.target(e);
1.665 +
1.666 + if (order_map[source] < order_map[target] && !tree_map[e]) {
1.667 + embed_arc[target] = e;
1.668 + walkUp(target, source, i, pred_map, low_map,
1.669 + order_map, order_list, node_data, merge_roots);
1.670 + }
1.671 + }
1.672 +
1.673 + for (typename MergeRoots::Value::iterator it =
1.674 + merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
1.675 + int rn = *it;
1.676 + walkDown(rn, i, node_data, arc_lists, flip_map, order_list,
1.677 + child_lists, ancestor_map, low_map, embed_arc, merge_roots);
1.678 + }
1.679 + merge_roots[node].clear();
1.680 +
1.681 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.682 + Node target = _graph.target(e);
1.683 +
1.684 + if (order_map[source] < order_map[target] && !tree_map[e]) {
1.685 + if (embed_arc[target] != INVALID) {
1.686 + if (kuratowski) {
1.687 + isolateKuratowski(e, node_data, arc_lists, flip_map,
1.688 + order_map, order_list, pred_map, child_lists,
1.689 + ancestor_map, low_map,
1.690 + embed_arc, merge_roots);
1.691 + }
1.692 + return false;
1.693 + }
1.694 + }
1.695 + }
1.696 + }
1.697 +
1.698 + for (int i = 0; i < int(order_list.size()); ++i) {
1.699 +
1.700 + mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
1.701 + child_lists, arc_lists);
1.702 + storeEmbedding(order_list[i], node_data, order_map, pred_map,
1.703 + arc_lists, flip_map);
1.704 + }
1.705 +
1.706 + return true;
1.707 + }
1.708 +
1.709 + /// \brief Give back the successor of an arc
1.710 + ///
1.711 + /// This function gives back the successor of an arc. It makes
1.712 + /// possible to query the cyclic order of the outgoing arcs from
1.713 + /// a node.
1.714 + Arc next(const Arc& arc) const {
1.715 + return _embedding[arc];
1.716 + }
1.717 +
1.718 + /// \brief Give back the calculated embedding map
1.719 + ///
1.720 + /// This function gives back the calculated embedding map, which
1.721 + /// contains the successor of each arc in the cyclic order of the
1.722 + /// outgoing arcs of its source node.
1.723 + const EmbeddingMap& embeddingMap() const {
1.724 + return _embedding;
1.725 + }
1.726 +
1.727 + /// \brief Give back \c true if the given edge is in the Kuratowski
1.728 + /// subdivision
1.729 + ///
1.730 + /// This function gives back \c true if the given edge is in the found
1.731 + /// Kuratowski subdivision.
1.732 + /// \pre The \c run() function must be called with \c true parameter
1.733 + /// before using this function.
1.734 + bool kuratowski(const Edge& edge) const {
1.735 + return _kuratowski[edge];
1.736 + }
1.737 +
1.738 + private:
1.739 +
1.740 + void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
1.741 + const LowMap& low_map, ChildLists& child_lists) {
1.742 +
1.743 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.744 + Node source = n;
1.745 +
1.746 + std::vector<Node> targets;
1.747 + for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.748 + Node target = _graph.target(e);
1.749 +
1.750 + if (order_map[source] < order_map[target] && tree_map[e]) {
1.751 + targets.push_back(target);
1.752 + }
1.753 + }
1.754 +
1.755 + if (targets.size() == 0) {
1.756 + child_lists[source].first = INVALID;
1.757 + } else if (targets.size() == 1) {
1.758 + child_lists[source].first = targets[0];
1.759 + child_lists[targets[0]].prev = INVALID;
1.760 + child_lists[targets[0]].next = INVALID;
1.761 + } else {
1.762 + radixSort(targets.begin(), targets.end(), mapToFunctor(low_map));
1.763 + for (int i = 1; i < int(targets.size()); ++i) {
1.764 + child_lists[targets[i]].prev = targets[i - 1];
1.765 + child_lists[targets[i - 1]].next = targets[i];
1.766 + }
1.767 + child_lists[targets.back()].next = INVALID;
1.768 + child_lists[targets.front()].prev = INVALID;
1.769 + child_lists[source].first = targets.front();
1.770 + }
1.771 + }
1.772 + }
1.773 +
1.774 + void walkUp(const Node& node, Node root, int rorder,
1.775 + const PredMap& pred_map, const LowMap& low_map,
1.776 + const OrderMap& order_map, const OrderList& order_list,
1.777 + NodeData& node_data, MergeRoots& merge_roots) {
1.778 +
1.779 + int na, nb;
1.780 + bool da, db;
1.781 +
1.782 + na = nb = order_map[node];
1.783 + da = true; db = false;
1.784 +
1.785 + while (true) {
1.786 +
1.787 + if (node_data[na].visited == rorder) break;
1.788 + if (node_data[nb].visited == rorder) break;
1.789 +
1.790 + node_data[na].visited = rorder;
1.791 + node_data[nb].visited = rorder;
1.792 +
1.793 + int rn = -1;
1.794 +
1.795 + if (na >= int(order_list.size())) {
1.796 + rn = na;
1.797 + } else if (nb >= int(order_list.size())) {
1.798 + rn = nb;
1.799 + }
1.800 +
1.801 + if (rn == -1) {
1.802 + int nn;
1.803 +
1.804 + nn = da ? node_data[na].prev : node_data[na].next;
1.805 + da = node_data[nn].prev != na;
1.806 + na = nn;
1.807 +
1.808 + nn = db ? node_data[nb].prev : node_data[nb].next;
1.809 + db = node_data[nn].prev != nb;
1.810 + nb = nn;
1.811 +
1.812 + } else {
1.813 +
1.814 + Node rep = order_list[rn - order_list.size()];
1.815 + Node parent = _graph.source(pred_map[rep]);
1.816 +
1.817 + if (low_map[rep] < rorder) {
1.818 + merge_roots[parent].push_back(rn);
1.819 + } else {
1.820 + merge_roots[parent].push_front(rn);
1.821 + }
1.822 +
1.823 + if (parent != root) {
1.824 + na = nb = order_map[parent];
1.825 + da = true; db = false;
1.826 + } else {
1.827 + break;
1.828 + }
1.829 + }
1.830 + }
1.831 + }
1.832 +
1.833 + void walkDown(int rn, int rorder, NodeData& node_data,
1.834 + ArcLists& arc_lists, FlipMap& flip_map,
1.835 + OrderList& order_list, ChildLists& child_lists,
1.836 + AncestorMap& ancestor_map, LowMap& low_map,
1.837 + EmbedArc& embed_arc, MergeRoots& merge_roots) {
1.838 +
1.839 + std::vector<std::pair<int, bool> > merge_stack;
1.840 +
1.841 + for (int di = 0; di < 2; ++di) {
1.842 + bool rd = di == 0;
1.843 + int pn = rn;
1.844 + int n = rd ? node_data[rn].next : node_data[rn].prev;
1.845 +
1.846 + while (n != rn) {
1.847 +
1.848 + Node node = order_list[n];
1.849 +
1.850 + if (embed_arc[node] != INVALID) {
1.851 +
1.852 + // Merging components on the critical path
1.853 + while (!merge_stack.empty()) {
1.854 +
1.855 + // Component root
1.856 + int cn = merge_stack.back().first;
1.857 + bool cd = merge_stack.back().second;
1.858 + merge_stack.pop_back();
1.859 +
1.860 + // Parent of component
1.861 + int dn = merge_stack.back().first;
1.862 + bool dd = merge_stack.back().second;
1.863 + merge_stack.pop_back();
1.864 +
1.865 + Node parent = order_list[dn];
1.866 +
1.867 + // Erasing from merge_roots
1.868 + merge_roots[parent].pop_front();
1.869 +
1.870 + Node child = order_list[cn - order_list.size()];
1.871 +
1.872 + // Erasing from child_lists
1.873 + if (child_lists[child].prev != INVALID) {
1.874 + child_lists[child_lists[child].prev].next =
1.875 + child_lists[child].next;
1.876 + } else {
1.877 + child_lists[parent].first = child_lists[child].next;
1.878 + }
1.879 +
1.880 + if (child_lists[child].next != INVALID) {
1.881 + child_lists[child_lists[child].next].prev =
1.882 + child_lists[child].prev;
1.883 + }
1.884 +
1.885 + // Merging arcs + flipping
1.886 + Arc de = node_data[dn].first;
1.887 + Arc ce = node_data[cn].first;
1.888 +
1.889 + flip_map[order_list[cn - order_list.size()]] = cd != dd;
1.890 + if (cd != dd) {
1.891 + std::swap(arc_lists[ce].prev, arc_lists[ce].next);
1.892 + ce = arc_lists[ce].prev;
1.893 + std::swap(arc_lists[ce].prev, arc_lists[ce].next);
1.894 + }
1.895 +
1.896 + {
1.897 + Arc dne = arc_lists[de].next;
1.898 + Arc cne = arc_lists[ce].next;
1.899 +
1.900 + arc_lists[de].next = cne;
1.901 + arc_lists[ce].next = dne;
1.902 +
1.903 + arc_lists[dne].prev = ce;
1.904 + arc_lists[cne].prev = de;
1.905 + }
1.906 +
1.907 + if (dd) {
1.908 + node_data[dn].first = ce;
1.909 + }
1.910 +
1.911 + // Merging external faces
1.912 + {
1.913 + int en = cn;
1.914 + cn = cd ? node_data[cn].prev : node_data[cn].next;
1.915 + cd = node_data[cn].next == en;
1.916 +
1.917 + if (node_data[cn].prev == node_data[cn].next &&
1.918 + node_data[cn].inverted) {
1.919 + cd = !cd;
1.920 + }
1.921 + }
1.922 +
1.923 + if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
1.924 + if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
1.925 +
1.926 + }
1.927 +
1.928 + bool d = pn == node_data[n].prev;
1.929 +
1.930 + if (node_data[n].prev == node_data[n].next &&
1.931 + node_data[n].inverted) {
1.932 + d = !d;
1.933 + }
1.934 +
1.935 + // Add new arc
1.936 + {
1.937 + Arc arc = embed_arc[node];
1.938 + Arc re = node_data[rn].first;
1.939 +
1.940 + arc_lists[arc_lists[re].next].prev = arc;
1.941 + arc_lists[arc].next = arc_lists[re].next;
1.942 + arc_lists[arc].prev = re;
1.943 + arc_lists[re].next = arc;
1.944 +
1.945 + if (!rd) {
1.946 + node_data[rn].first = arc;
1.947 + }
1.948 +
1.949 + Arc rev = _graph.oppositeArc(arc);
1.950 + Arc e = node_data[n].first;
1.951 +
1.952 + arc_lists[arc_lists[e].next].prev = rev;
1.953 + arc_lists[rev].next = arc_lists[e].next;
1.954 + arc_lists[rev].prev = e;
1.955 + arc_lists[e].next = rev;
1.956 +
1.957 + if (d) {
1.958 + node_data[n].first = rev;
1.959 + }
1.960 +
1.961 + }
1.962 +
1.963 + // Embedding arc into external face
1.964 + if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
1.965 + if (d) node_data[n].prev = rn; else node_data[n].next = rn;
1.966 + pn = rn;
1.967 +
1.968 + embed_arc[order_list[n]] = INVALID;
1.969 + }
1.970 +
1.971 + if (!merge_roots[node].empty()) {
1.972 +
1.973 + bool d = pn == node_data[n].prev;
1.974 + if (node_data[n].prev == node_data[n].next &&
1.975 + node_data[n].inverted) {
1.976 + d = !d;
1.977 + }
1.978 +
1.979 + merge_stack.push_back(std::make_pair(n, d));
1.980 +
1.981 + int rn = merge_roots[node].front();
1.982 +
1.983 + int xn = node_data[rn].next;
1.984 + Node xnode = order_list[xn];
1.985 +
1.986 + int yn = node_data[rn].prev;
1.987 + Node ynode = order_list[yn];
1.988 +
1.989 + bool rd;
1.990 + if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
1.991 + rd = true;
1.992 + } else if (!external(ynode, rorder, child_lists,
1.993 + ancestor_map, low_map)) {
1.994 + rd = false;
1.995 + } else if (pertinent(xnode, embed_arc, merge_roots)) {
1.996 + rd = true;
1.997 + } else {
1.998 + rd = false;
1.999 + }
1.1000 +
1.1001 + merge_stack.push_back(std::make_pair(rn, rd));
1.1002 +
1.1003 + pn = rn;
1.1004 + n = rd ? xn : yn;
1.1005 +
1.1006 + } else if (!external(node, rorder, child_lists,
1.1007 + ancestor_map, low_map)) {
1.1008 + int nn = (node_data[n].next != pn ?
1.1009 + node_data[n].next : node_data[n].prev);
1.1010 +
1.1011 + bool nd = n == node_data[nn].prev;
1.1012 +
1.1013 + if (nd) node_data[nn].prev = pn;
1.1014 + else node_data[nn].next = pn;
1.1015 +
1.1016 + if (n == node_data[pn].prev) node_data[pn].prev = nn;
1.1017 + else node_data[pn].next = nn;
1.1018 +
1.1019 + node_data[nn].inverted =
1.1020 + (node_data[nn].prev == node_data[nn].next && nd != rd);
1.1021 +
1.1022 + n = nn;
1.1023 + }
1.1024 + else break;
1.1025 +
1.1026 + }
1.1027 +
1.1028 + if (!merge_stack.empty() || n == rn) {
1.1029 + break;
1.1030 + }
1.1031 + }
1.1032 + }
1.1033 +
1.1034 + void initFace(const Node& node, ArcLists& arc_lists,
1.1035 + NodeData& node_data, const PredMap& pred_map,
1.1036 + const OrderMap& order_map, const OrderList& order_list) {
1.1037 + int n = order_map[node];
1.1038 + int rn = n + order_list.size();
1.1039 +
1.1040 + node_data[n].next = node_data[n].prev = rn;
1.1041 + node_data[rn].next = node_data[rn].prev = n;
1.1042 +
1.1043 + node_data[n].visited = order_list.size();
1.1044 + node_data[rn].visited = order_list.size();
1.1045 +
1.1046 + node_data[n].inverted = false;
1.1047 + node_data[rn].inverted = false;
1.1048 +
1.1049 + Arc arc = pred_map[node];
1.1050 + Arc rev = _graph.oppositeArc(arc);
1.1051 +
1.1052 + node_data[rn].first = arc;
1.1053 + node_data[n].first = rev;
1.1054 +
1.1055 + arc_lists[arc].prev = arc;
1.1056 + arc_lists[arc].next = arc;
1.1057 +
1.1058 + arc_lists[rev].prev = rev;
1.1059 + arc_lists[rev].next = rev;
1.1060 +
1.1061 + }
1.1062 +
1.1063 + void mergeRemainingFaces(const Node& node, NodeData& node_data,
1.1064 + OrderList& order_list, OrderMap& order_map,
1.1065 + ChildLists& child_lists, ArcLists& arc_lists) {
1.1066 + while (child_lists[node].first != INVALID) {
1.1067 + int dd = order_map[node];
1.1068 + Node child = child_lists[node].first;
1.1069 + int cd = order_map[child] + order_list.size();
1.1070 + child_lists[node].first = child_lists[child].next;
1.1071 +
1.1072 + Arc de = node_data[dd].first;
1.1073 + Arc ce = node_data[cd].first;
1.1074 +
1.1075 + if (de != INVALID) {
1.1076 + Arc dne = arc_lists[de].next;
1.1077 + Arc cne = arc_lists[ce].next;
1.1078 +
1.1079 + arc_lists[de].next = cne;
1.1080 + arc_lists[ce].next = dne;
1.1081 +
1.1082 + arc_lists[dne].prev = ce;
1.1083 + arc_lists[cne].prev = de;
1.1084 + }
1.1085 +
1.1086 + node_data[dd].first = ce;
1.1087 +
1.1088 + }
1.1089 + }
1.1090 +
1.1091 + void storeEmbedding(const Node& node, NodeData& node_data,
1.1092 + OrderMap& order_map, PredMap& pred_map,
1.1093 + ArcLists& arc_lists, FlipMap& flip_map) {
1.1094 +
1.1095 + if (node_data[order_map[node]].first == INVALID) return;
1.1096 +
1.1097 + if (pred_map[node] != INVALID) {
1.1098 + Node source = _graph.source(pred_map[node]);
1.1099 + flip_map[node] = flip_map[node] != flip_map[source];
1.1100 + }
1.1101 +
1.1102 + Arc first = node_data[order_map[node]].first;
1.1103 + Arc prev = first;
1.1104 +
1.1105 + Arc arc = flip_map[node] ?
1.1106 + arc_lists[prev].prev : arc_lists[prev].next;
1.1107 +
1.1108 + _embedding[prev] = arc;
1.1109 +
1.1110 + while (arc != first) {
1.1111 + Arc next = arc_lists[arc].prev == prev ?
1.1112 + arc_lists[arc].next : arc_lists[arc].prev;
1.1113 + prev = arc; arc = next;
1.1114 + _embedding[prev] = arc;
1.1115 + }
1.1116 + }
1.1117 +
1.1118 +
1.1119 + bool external(const Node& node, int rorder,
1.1120 + ChildLists& child_lists, AncestorMap& ancestor_map,
1.1121 + LowMap& low_map) {
1.1122 + Node child = child_lists[node].first;
1.1123 +
1.1124 + if (child != INVALID) {
1.1125 + if (low_map[child] < rorder) return true;
1.1126 + }
1.1127 +
1.1128 + if (ancestor_map[node] < rorder) return true;
1.1129 +
1.1130 + return false;
1.1131 + }
1.1132 +
1.1133 + bool pertinent(const Node& node, const EmbedArc& embed_arc,
1.1134 + const MergeRoots& merge_roots) {
1.1135 + return !merge_roots[node].empty() || embed_arc[node] != INVALID;
1.1136 + }
1.1137 +
1.1138 + int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
1.1139 + AncestorMap& ancestor_map, LowMap& low_map) {
1.1140 + int low_point;
1.1141 +
1.1142 + Node child = child_lists[node].first;
1.1143 +
1.1144 + if (child != INVALID) {
1.1145 + low_point = low_map[child];
1.1146 + } else {
1.1147 + low_point = order_map[node];
1.1148 + }
1.1149 +
1.1150 + if (low_point > ancestor_map[node]) {
1.1151 + low_point = ancestor_map[node];
1.1152 + }
1.1153 +
1.1154 + return low_point;
1.1155 + }
1.1156 +
1.1157 + int findComponentRoot(Node root, Node node, ChildLists& child_lists,
1.1158 + OrderMap& order_map, OrderList& order_list) {
1.1159 +
1.1160 + int order = order_map[root];
1.1161 + int norder = order_map[node];
1.1162 +
1.1163 + Node child = child_lists[root].first;
1.1164 + while (child != INVALID) {
1.1165 + int corder = order_map[child];
1.1166 + if (corder > order && corder < norder) {
1.1167 + order = corder;
1.1168 + }
1.1169 + child = child_lists[child].next;
1.1170 + }
1.1171 + return order + order_list.size();
1.1172 + }
1.1173 +
1.1174 + Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data,
1.1175 + EmbedArc& embed_arc, MergeRoots& merge_roots) {
1.1176 + Node wnode =_graph.target(node_data[order_map[node]].first);
1.1177 + while (!pertinent(wnode, embed_arc, merge_roots)) {
1.1178 + wnode = _graph.target(node_data[order_map[wnode]].first);
1.1179 + }
1.1180 + return wnode;
1.1181 + }
1.1182 +
1.1183 +
1.1184 + Node findExternal(Node node, int rorder, OrderMap& order_map,
1.1185 + ChildLists& child_lists, AncestorMap& ancestor_map,
1.1186 + LowMap& low_map, NodeData& node_data) {
1.1187 + Node wnode =_graph.target(node_data[order_map[node]].first);
1.1188 + while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
1.1189 + wnode = _graph.target(node_data[order_map[wnode]].first);
1.1190 + }
1.1191 + return wnode;
1.1192 + }
1.1193 +
1.1194 + void markCommonPath(Node node, int rorder, Node& wnode, Node& znode,
1.1195 + OrderList& order_list, OrderMap& order_map,
1.1196 + NodeData& node_data, ArcLists& arc_lists,
1.1197 + EmbedArc& embed_arc, MergeRoots& merge_roots,
1.1198 + ChildLists& child_lists, AncestorMap& ancestor_map,
1.1199 + LowMap& low_map) {
1.1200 +
1.1201 + Node cnode = node;
1.1202 + Node pred = INVALID;
1.1203 +
1.1204 + while (true) {
1.1205 +
1.1206 + bool pert = pertinent(cnode, embed_arc, merge_roots);
1.1207 + bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
1.1208 +
1.1209 + if (pert && ext) {
1.1210 + if (!merge_roots[cnode].empty()) {
1.1211 + int cn = merge_roots[cnode].back();
1.1212 +
1.1213 + if (low_map[order_list[cn - order_list.size()]] < rorder) {
1.1214 + Arc arc = node_data[cn].first;
1.1215 + _kuratowski.set(arc, true);
1.1216 +
1.1217 + pred = cnode;
1.1218 + cnode = _graph.target(arc);
1.1219 +
1.1220 + continue;
1.1221 + }
1.1222 + }
1.1223 + wnode = znode = cnode;
1.1224 + return;
1.1225 +
1.1226 + } else if (pert) {
1.1227 + wnode = cnode;
1.1228 +
1.1229 + while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
1.1230 + Arc arc = node_data[order_map[cnode]].first;
1.1231 +
1.1232 + if (_graph.target(arc) == pred) {
1.1233 + arc = arc_lists[arc].next;
1.1234 + }
1.1235 + _kuratowski.set(arc, true);
1.1236 +
1.1237 + Node next = _graph.target(arc);
1.1238 + pred = cnode; cnode = next;
1.1239 + }
1.1240 +
1.1241 + znode = cnode;
1.1242 + return;
1.1243 +
1.1244 + } else if (ext) {
1.1245 + znode = cnode;
1.1246 +
1.1247 + while (!pertinent(cnode, embed_arc, merge_roots)) {
1.1248 + Arc arc = node_data[order_map[cnode]].first;
1.1249 +
1.1250 + if (_graph.target(arc) == pred) {
1.1251 + arc = arc_lists[arc].next;
1.1252 + }
1.1253 + _kuratowski.set(arc, true);
1.1254 +
1.1255 + Node next = _graph.target(arc);
1.1256 + pred = cnode; cnode = next;
1.1257 + }
1.1258 +
1.1259 + wnode = cnode;
1.1260 + return;
1.1261 +
1.1262 + } else {
1.1263 + Arc arc = node_data[order_map[cnode]].first;
1.1264 +
1.1265 + if (_graph.target(arc) == pred) {
1.1266 + arc = arc_lists[arc].next;
1.1267 + }
1.1268 + _kuratowski.set(arc, true);
1.1269 +
1.1270 + Node next = _graph.target(arc);
1.1271 + pred = cnode; cnode = next;
1.1272 + }
1.1273 +
1.1274 + }
1.1275 +
1.1276 + }
1.1277 +
1.1278 + void orientComponent(Node root, int rn, OrderMap& order_map,
1.1279 + PredMap& pred_map, NodeData& node_data,
1.1280 + ArcLists& arc_lists, FlipMap& flip_map,
1.1281 + TypeMap& type_map) {
1.1282 + node_data[order_map[root]].first = node_data[rn].first;
1.1283 + type_map[root] = 1;
1.1284 +
1.1285 + std::vector<Node> st, qu;
1.1286 +
1.1287 + st.push_back(root);
1.1288 + while (!st.empty()) {
1.1289 + Node node = st.back();
1.1290 + st.pop_back();
1.1291 + qu.push_back(node);
1.1292 +
1.1293 + Arc arc = node_data[order_map[node]].first;
1.1294 +
1.1295 + if (type_map[_graph.target(arc)] == 0) {
1.1296 + st.push_back(_graph.target(arc));
1.1297 + type_map[_graph.target(arc)] = 1;
1.1298 + }
1.1299 +
1.1300 + Arc last = arc, pred = arc;
1.1301 + arc = arc_lists[arc].next;
1.1302 + while (arc != last) {
1.1303 +
1.1304 + if (type_map[_graph.target(arc)] == 0) {
1.1305 + st.push_back(_graph.target(arc));
1.1306 + type_map[_graph.target(arc)] = 1;
1.1307 + }
1.1308 +
1.1309 + Arc next = arc_lists[arc].next != pred ?
1.1310 + arc_lists[arc].next : arc_lists[arc].prev;
1.1311 + pred = arc; arc = next;
1.1312 + }
1.1313 +
1.1314 + }
1.1315 +
1.1316 + type_map[root] = 2;
1.1317 + flip_map[root] = false;
1.1318 +
1.1319 + for (int i = 1; i < int(qu.size()); ++i) {
1.1320 +
1.1321 + Node node = qu[i];
1.1322 +
1.1323 + while (type_map[node] != 2) {
1.1324 + st.push_back(node);
1.1325 + type_map[node] = 2;
1.1326 + node = _graph.source(pred_map[node]);
1.1327 + }
1.1328 +
1.1329 + bool flip = flip_map[node];
1.1330 +
1.1331 + while (!st.empty()) {
1.1332 + node = st.back();
1.1333 + st.pop_back();
1.1334 +
1.1335 + flip_map[node] = flip != flip_map[node];
1.1336 + flip = flip_map[node];
1.1337 +
1.1338 + if (flip) {
1.1339 + Arc arc = node_data[order_map[node]].first;
1.1340 + std::swap(arc_lists[arc].prev, arc_lists[arc].next);
1.1341 + arc = arc_lists[arc].prev;
1.1342 + std::swap(arc_lists[arc].prev, arc_lists[arc].next);
1.1343 + node_data[order_map[node]].first = arc;
1.1344 + }
1.1345 + }
1.1346 + }
1.1347 +
1.1348 + for (int i = 0; i < int(qu.size()); ++i) {
1.1349 +
1.1350 + Arc arc = node_data[order_map[qu[i]]].first;
1.1351 + Arc last = arc, pred = arc;
1.1352 +
1.1353 + arc = arc_lists[arc].next;
1.1354 + while (arc != last) {
1.1355 +
1.1356 + if (arc_lists[arc].next == pred) {
1.1357 + std::swap(arc_lists[arc].next, arc_lists[arc].prev);
1.1358 + }
1.1359 + pred = arc; arc = arc_lists[arc].next;
1.1360 + }
1.1361 +
1.1362 + }
1.1363 + }
1.1364 +
1.1365 + void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode,
1.1366 + OrderMap& order_map, NodeData& node_data,
1.1367 + TypeMap& type_map) {
1.1368 + Node node = _graph.target(node_data[order_map[root]].first);
1.1369 +
1.1370 + while (node != ynode) {
1.1371 + type_map[node] = HIGHY;
1.1372 + node = _graph.target(node_data[order_map[node]].first);
1.1373 + }
1.1374 +
1.1375 + while (node != wnode) {
1.1376 + type_map[node] = LOWY;
1.1377 + node = _graph.target(node_data[order_map[node]].first);
1.1378 + }
1.1379 +
1.1380 + node = _graph.target(node_data[order_map[wnode]].first);
1.1381 +
1.1382 + while (node != xnode) {
1.1383 + type_map[node] = LOWX;
1.1384 + node = _graph.target(node_data[order_map[node]].first);
1.1385 + }
1.1386 + type_map[node] = LOWX;
1.1387 +
1.1388 + node = _graph.target(node_data[order_map[xnode]].first);
1.1389 + while (node != root) {
1.1390 + type_map[node] = HIGHX;
1.1391 + node = _graph.target(node_data[order_map[node]].first);
1.1392 + }
1.1393 +
1.1394 + type_map[wnode] = PERTINENT;
1.1395 + type_map[root] = ROOT;
1.1396 + }
1.1397 +
1.1398 + void findInternalPath(std::vector<Arc>& ipath,
1.1399 + Node wnode, Node root, TypeMap& type_map,
1.1400 + OrderMap& order_map, NodeData& node_data,
1.1401 + ArcLists& arc_lists) {
1.1402 + std::vector<Arc> st;
1.1403 +
1.1404 + Node node = wnode;
1.1405 +
1.1406 + while (node != root) {
1.1407 + Arc arc = arc_lists[node_data[order_map[node]].first].next;
1.1408 + st.push_back(arc);
1.1409 + node = _graph.target(arc);
1.1410 + }
1.1411 +
1.1412 + while (true) {
1.1413 + Arc arc = st.back();
1.1414 + if (type_map[_graph.target(arc)] == LOWX ||
1.1415 + type_map[_graph.target(arc)] == HIGHX) {
1.1416 + break;
1.1417 + }
1.1418 + if (type_map[_graph.target(arc)] == 2) {
1.1419 + type_map[_graph.target(arc)] = 3;
1.1420 +
1.1421 + arc = arc_lists[_graph.oppositeArc(arc)].next;
1.1422 + st.push_back(arc);
1.1423 + } else {
1.1424 + st.pop_back();
1.1425 + arc = arc_lists[arc].next;
1.1426 +
1.1427 + while (_graph.oppositeArc(arc) == st.back()) {
1.1428 + arc = st.back();
1.1429 + st.pop_back();
1.1430 + arc = arc_lists[arc].next;
1.1431 + }
1.1432 + st.push_back(arc);
1.1433 + }
1.1434 + }
1.1435 +
1.1436 + for (int i = 0; i < int(st.size()); ++i) {
1.1437 + if (type_map[_graph.target(st[i])] != LOWY &&
1.1438 + type_map[_graph.target(st[i])] != HIGHY) {
1.1439 + for (; i < int(st.size()); ++i) {
1.1440 + ipath.push_back(st[i]);
1.1441 + }
1.1442 + }
1.1443 + }
1.1444 + }
1.1445 +
1.1446 + void setInternalFlags(std::vector<Arc>& ipath, TypeMap& type_map) {
1.1447 + for (int i = 1; i < int(ipath.size()); ++i) {
1.1448 + type_map[_graph.source(ipath[i])] = INTERNAL;
1.1449 + }
1.1450 + }
1.1451 +
1.1452 + void findPilePath(std::vector<Arc>& ppath,
1.1453 + Node root, TypeMap& type_map, OrderMap& order_map,
1.1454 + NodeData& node_data, ArcLists& arc_lists) {
1.1455 + std::vector<Arc> st;
1.1456 +
1.1457 + st.push_back(_graph.oppositeArc(node_data[order_map[root]].first));
1.1458 + st.push_back(node_data[order_map[root]].first);
1.1459 +
1.1460 + while (st.size() > 1) {
1.1461 + Arc arc = st.back();
1.1462 + if (type_map[_graph.target(arc)] == INTERNAL) {
1.1463 + break;
1.1464 + }
1.1465 + if (type_map[_graph.target(arc)] == 3) {
1.1466 + type_map[_graph.target(arc)] = 4;
1.1467 +
1.1468 + arc = arc_lists[_graph.oppositeArc(arc)].next;
1.1469 + st.push_back(arc);
1.1470 + } else {
1.1471 + st.pop_back();
1.1472 + arc = arc_lists[arc].next;
1.1473 +
1.1474 + while (!st.empty() && _graph.oppositeArc(arc) == st.back()) {
1.1475 + arc = st.back();
1.1476 + st.pop_back();
1.1477 + arc = arc_lists[arc].next;
1.1478 + }
1.1479 + st.push_back(arc);
1.1480 + }
1.1481 + }
1.1482 +
1.1483 + for (int i = 1; i < int(st.size()); ++i) {
1.1484 + ppath.push_back(st[i]);
1.1485 + }
1.1486 + }
1.1487 +
1.1488 +
1.1489 + int markExternalPath(Node node, OrderMap& order_map,
1.1490 + ChildLists& child_lists, PredMap& pred_map,
1.1491 + AncestorMap& ancestor_map, LowMap& low_map) {
1.1492 + int lp = lowPoint(node, order_map, child_lists,
1.1493 + ancestor_map, low_map);
1.1494 +
1.1495 + if (ancestor_map[node] != lp) {
1.1496 + node = child_lists[node].first;
1.1497 + _kuratowski[pred_map[node]] = true;
1.1498 +
1.1499 + while (ancestor_map[node] != lp) {
1.1500 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.1501 + Node tnode = _graph.target(e);
1.1502 + if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) {
1.1503 + node = tnode;
1.1504 + _kuratowski[e] = true;
1.1505 + break;
1.1506 + }
1.1507 + }
1.1508 + }
1.1509 + }
1.1510 +
1.1511 + for (OutArcIt e(_graph, node); e != INVALID; ++e) {
1.1512 + if (order_map[_graph.target(e)] == lp) {
1.1513 + _kuratowski[e] = true;
1.1514 + break;
1.1515 + }
1.1516 + }
1.1517 +
1.1518 + return lp;
1.1519 + }
1.1520 +
1.1521 + void markPertinentPath(Node node, OrderMap& order_map,
1.1522 + NodeData& node_data, ArcLists& arc_lists,
1.1523 + EmbedArc& embed_arc, MergeRoots& merge_roots) {
1.1524 + while (embed_arc[node] == INVALID) {
1.1525 + int n = merge_roots[node].front();
1.1526 + Arc arc = node_data[n].first;
1.1527 +
1.1528 + _kuratowski.set(arc, true);
1.1529 +
1.1530 + Node pred = node;
1.1531 + node = _graph.target(arc);
1.1532 + while (!pertinent(node, embed_arc, merge_roots)) {
1.1533 + arc = node_data[order_map[node]].first;
1.1534 + if (_graph.target(arc) == pred) {
1.1535 + arc = arc_lists[arc].next;
1.1536 + }
1.1537 + _kuratowski.set(arc, true);
1.1538 + pred = node;
1.1539 + node = _graph.target(arc);
1.1540 + }
1.1541 + }
1.1542 + _kuratowski.set(embed_arc[node], true);
1.1543 + }
1.1544 +
1.1545 + void markPredPath(Node node, Node snode, PredMap& pred_map) {
1.1546 + while (node != snode) {
1.1547 + _kuratowski.set(pred_map[node], true);
1.1548 + node = _graph.source(pred_map[node]);
1.1549 + }
1.1550 + }
1.1551 +
1.1552 + void markFacePath(Node ynode, Node xnode,
1.1553 + OrderMap& order_map, NodeData& node_data) {
1.1554 + Arc arc = node_data[order_map[ynode]].first;
1.1555 + Node node = _graph.target(arc);
1.1556 + _kuratowski.set(arc, true);
1.1557 +
1.1558 + while (node != xnode) {
1.1559 + arc = node_data[order_map[node]].first;
1.1560 + _kuratowski.set(arc, true);
1.1561 + node = _graph.target(arc);
1.1562 + }
1.1563 + }
1.1564 +
1.1565 + void markInternalPath(std::vector<Arc>& path) {
1.1566 + for (int i = 0; i < int(path.size()); ++i) {
1.1567 + _kuratowski.set(path[i], true);
1.1568 + }
1.1569 + }
1.1570 +
1.1571 + void markPilePath(std::vector<Arc>& path) {
1.1572 + for (int i = 0; i < int(path.size()); ++i) {
1.1573 + _kuratowski.set(path[i], true);
1.1574 + }
1.1575 + }
1.1576 +
1.1577 + void isolateKuratowski(Arc arc, NodeData& node_data,
1.1578 + ArcLists& arc_lists, FlipMap& flip_map,
1.1579 + OrderMap& order_map, OrderList& order_list,
1.1580 + PredMap& pred_map, ChildLists& child_lists,
1.1581 + AncestorMap& ancestor_map, LowMap& low_map,
1.1582 + EmbedArc& embed_arc, MergeRoots& merge_roots) {
1.1583 +
1.1584 + Node root = _graph.source(arc);
1.1585 + Node enode = _graph.target(arc);
1.1586 +
1.1587 + int rorder = order_map[root];
1.1588 +
1.1589 + TypeMap type_map(_graph, 0);
1.1590 +
1.1591 + int rn = findComponentRoot(root, enode, child_lists,
1.1592 + order_map, order_list);
1.1593 +
1.1594 + Node xnode = order_list[node_data[rn].next];
1.1595 + Node ynode = order_list[node_data[rn].prev];
1.1596 +
1.1597 + // Minor-A
1.1598 + {
1.1599 + while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
1.1600 +
1.1601 + if (!merge_roots[xnode].empty()) {
1.1602 + root = xnode;
1.1603 + rn = merge_roots[xnode].front();
1.1604 + } else {
1.1605 + root = ynode;
1.1606 + rn = merge_roots[ynode].front();
1.1607 + }
1.1608 +
1.1609 + xnode = order_list[node_data[rn].next];
1.1610 + ynode = order_list[node_data[rn].prev];
1.1611 + }
1.1612 +
1.1613 + if (root != _graph.source(arc)) {
1.1614 + orientComponent(root, rn, order_map, pred_map,
1.1615 + node_data, arc_lists, flip_map, type_map);
1.1616 + markFacePath(root, root, order_map, node_data);
1.1617 + int xlp = markExternalPath(xnode, order_map, child_lists,
1.1618 + pred_map, ancestor_map, low_map);
1.1619 + int ylp = markExternalPath(ynode, order_map, child_lists,
1.1620 + pred_map, ancestor_map, low_map);
1.1621 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1.1622 + Node lwnode = findPertinent(ynode, order_map, node_data,
1.1623 + embed_arc, merge_roots);
1.1624 +
1.1625 + markPertinentPath(lwnode, order_map, node_data, arc_lists,
1.1626 + embed_arc, merge_roots);
1.1627 +
1.1628 + return;
1.1629 + }
1.1630 + }
1.1631 +
1.1632 + orientComponent(root, rn, order_map, pred_map,
1.1633 + node_data, arc_lists, flip_map, type_map);
1.1634 +
1.1635 + Node wnode = findPertinent(ynode, order_map, node_data,
1.1636 + embed_arc, merge_roots);
1.1637 + setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map);
1.1638 +
1.1639 +
1.1640 + //Minor-B
1.1641 + if (!merge_roots[wnode].empty()) {
1.1642 + int cn = merge_roots[wnode].back();
1.1643 + Node rep = order_list[cn - order_list.size()];
1.1644 + if (low_map[rep] < rorder) {
1.1645 + markFacePath(root, root, order_map, node_data);
1.1646 + int xlp = markExternalPath(xnode, order_map, child_lists,
1.1647 + pred_map, ancestor_map, low_map);
1.1648 + int ylp = markExternalPath(ynode, order_map, child_lists,
1.1649 + pred_map, ancestor_map, low_map);
1.1650 +
1.1651 + Node lwnode, lznode;
1.1652 + markCommonPath(wnode, rorder, lwnode, lznode, order_list,
1.1653 + order_map, node_data, arc_lists, embed_arc,
1.1654 + merge_roots, child_lists, ancestor_map, low_map);
1.1655 +
1.1656 + markPertinentPath(lwnode, order_map, node_data, arc_lists,
1.1657 + embed_arc, merge_roots);
1.1658 + int zlp = markExternalPath(lznode, order_map, child_lists,
1.1659 + pred_map, ancestor_map, low_map);
1.1660 +
1.1661 + int minlp = xlp < ylp ? xlp : ylp;
1.1662 + if (zlp < minlp) minlp = zlp;
1.1663 +
1.1664 + int maxlp = xlp > ylp ? xlp : ylp;
1.1665 + if (zlp > maxlp) maxlp = zlp;
1.1666 +
1.1667 + markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1.1668 +
1.1669 + return;
1.1670 + }
1.1671 + }
1.1672 +
1.1673 + Node pxnode, pynode;
1.1674 + std::vector<Arc> ipath;
1.1675 + findInternalPath(ipath, wnode, root, type_map, order_map,
1.1676 + node_data, arc_lists);
1.1677 + setInternalFlags(ipath, type_map);
1.1678 + pynode = _graph.source(ipath.front());
1.1679 + pxnode = _graph.target(ipath.back());
1.1680 +
1.1681 + wnode = findPertinent(pynode, order_map, node_data,
1.1682 + embed_arc, merge_roots);
1.1683 +
1.1684 + // Minor-C
1.1685 + {
1.1686 + if (type_map[_graph.source(ipath.front())] == HIGHY) {
1.1687 + if (type_map[_graph.target(ipath.back())] == HIGHX) {
1.1688 + markFacePath(xnode, pxnode, order_map, node_data);
1.1689 + }
1.1690 + markFacePath(root, xnode, order_map, node_data);
1.1691 + markPertinentPath(wnode, order_map, node_data, arc_lists,
1.1692 + embed_arc, merge_roots);
1.1693 + markInternalPath(ipath);
1.1694 + int xlp = markExternalPath(xnode, order_map, child_lists,
1.1695 + pred_map, ancestor_map, low_map);
1.1696 + int ylp = markExternalPath(ynode, order_map, child_lists,
1.1697 + pred_map, ancestor_map, low_map);
1.1698 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1.1699 + return;
1.1700 + }
1.1701 +
1.1702 + if (type_map[_graph.target(ipath.back())] == HIGHX) {
1.1703 + markFacePath(ynode, root, order_map, node_data);
1.1704 + markPertinentPath(wnode, order_map, node_data, arc_lists,
1.1705 + embed_arc, merge_roots);
1.1706 + markInternalPath(ipath);
1.1707 + int xlp = markExternalPath(xnode, order_map, child_lists,
1.1708 + pred_map, ancestor_map, low_map);
1.1709 + int ylp = markExternalPath(ynode, order_map, child_lists,
1.1710 + pred_map, ancestor_map, low_map);
1.1711 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1.1712 + return;
1.1713 + }
1.1714 + }
1.1715 +
1.1716 + std::vector<Arc> ppath;
1.1717 + findPilePath(ppath, root, type_map, order_map, node_data, arc_lists);
1.1718 +
1.1719 + // Minor-D
1.1720 + if (!ppath.empty()) {
1.1721 + markFacePath(ynode, xnode, order_map, node_data);
1.1722 + markPertinentPath(wnode, order_map, node_data, arc_lists,
1.1723 + embed_arc, merge_roots);
1.1724 + markPilePath(ppath);
1.1725 + markInternalPath(ipath);
1.1726 + int xlp = markExternalPath(xnode, order_map, child_lists,
1.1727 + pred_map, ancestor_map, low_map);
1.1728 + int ylp = markExternalPath(ynode, order_map, child_lists,
1.1729 + pred_map, ancestor_map, low_map);
1.1730 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1.1731 + return;
1.1732 + }
1.1733 +
1.1734 + // Minor-E*
1.1735 + {
1.1736 +
1.1737 + if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
1.1738 + Node znode = findExternal(pynode, rorder, order_map,
1.1739 + child_lists, ancestor_map,
1.1740 + low_map, node_data);
1.1741 +
1.1742 + if (type_map[znode] == LOWY) {
1.1743 + markFacePath(root, xnode, order_map, node_data);
1.1744 + markPertinentPath(wnode, order_map, node_data, arc_lists,
1.1745 + embed_arc, merge_roots);
1.1746 + markInternalPath(ipath);
1.1747 + int xlp = markExternalPath(xnode, order_map, child_lists,
1.1748 + pred_map, ancestor_map, low_map);
1.1749 + int zlp = markExternalPath(znode, order_map, child_lists,
1.1750 + pred_map, ancestor_map, low_map);
1.1751 + markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map);
1.1752 + } else {
1.1753 + markFacePath(ynode, root, order_map, node_data);
1.1754 + markPertinentPath(wnode, order_map, node_data, arc_lists,
1.1755 + embed_arc, merge_roots);
1.1756 + markInternalPath(ipath);
1.1757 + int ylp = markExternalPath(ynode, order_map, child_lists,
1.1758 + pred_map, ancestor_map, low_map);
1.1759 + int zlp = markExternalPath(znode, order_map, child_lists,
1.1760 + pred_map, ancestor_map, low_map);
1.1761 + markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map);
1.1762 + }
1.1763 + return;
1.1764 + }
1.1765 +
1.1766 + int xlp = markExternalPath(xnode, order_map, child_lists,
1.1767 + pred_map, ancestor_map, low_map);
1.1768 + int ylp = markExternalPath(ynode, order_map, child_lists,
1.1769 + pred_map, ancestor_map, low_map);
1.1770 + int wlp = markExternalPath(wnode, order_map, child_lists,
1.1771 + pred_map, ancestor_map, low_map);
1.1772 +
1.1773 + if (wlp > xlp && wlp > ylp) {
1.1774 + markFacePath(root, root, order_map, node_data);
1.1775 + markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1.1776 + return;
1.1777 + }
1.1778 +
1.1779 + markInternalPath(ipath);
1.1780 + markPertinentPath(wnode, order_map, node_data, arc_lists,
1.1781 + embed_arc, merge_roots);
1.1782 +
1.1783 + if (xlp > ylp && xlp > wlp) {
1.1784 + markFacePath(root, pynode, order_map, node_data);
1.1785 + markFacePath(wnode, xnode, order_map, node_data);
1.1786 + markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map);
1.1787 + return;
1.1788 + }
1.1789 +
1.1790 + if (ylp > xlp && ylp > wlp) {
1.1791 + markFacePath(pxnode, root, order_map, node_data);
1.1792 + markFacePath(ynode, wnode, order_map, node_data);
1.1793 + markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map);
1.1794 + return;
1.1795 + }
1.1796 +
1.1797 + if (pynode != ynode) {
1.1798 + markFacePath(pxnode, wnode, order_map, node_data);
1.1799 +
1.1800 + int minlp = xlp < ylp ? xlp : ylp;
1.1801 + if (wlp < minlp) minlp = wlp;
1.1802 +
1.1803 + int maxlp = xlp > ylp ? xlp : ylp;
1.1804 + if (wlp > maxlp) maxlp = wlp;
1.1805 +
1.1806 + markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1.1807 + return;
1.1808 + }
1.1809 +
1.1810 + if (pxnode != xnode) {
1.1811 + markFacePath(wnode, pynode, order_map, node_data);
1.1812 +
1.1813 + int minlp = xlp < ylp ? xlp : ylp;
1.1814 + if (wlp < minlp) minlp = wlp;
1.1815 +
1.1816 + int maxlp = xlp > ylp ? xlp : ylp;
1.1817 + if (wlp > maxlp) maxlp = wlp;
1.1818 +
1.1819 + markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1.1820 + return;
1.1821 + }
1.1822 +
1.1823 + markFacePath(root, root, order_map, node_data);
1.1824 + int minlp = xlp < ylp ? xlp : ylp;
1.1825 + if (wlp < minlp) minlp = wlp;
1.1826 + markPredPath(root, order_list[minlp], pred_map);
1.1827 + return;
1.1828 + }
1.1829 +
1.1830 + }
1.1831 +
1.1832 + };
1.1833 +
1.1834 + namespace _planarity_bits {
1.1835 +
1.1836 + template <typename Graph, typename EmbeddingMap>
1.1837 + void makeConnected(Graph& graph, EmbeddingMap& embedding) {
1.1838 + DfsVisitor<Graph> null_visitor;
1.1839 + DfsVisit<Graph, DfsVisitor<Graph> > dfs(graph, null_visitor);
1.1840 + dfs.init();
1.1841 +
1.1842 + typename Graph::Node u = INVALID;
1.1843 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.1844 + if (!dfs.reached(n)) {
1.1845 + dfs.addSource(n);
1.1846 + dfs.start();
1.1847 + if (u == INVALID) {
1.1848 + u = n;
1.1849 + } else {
1.1850 + typename Graph::Node v = n;
1.1851 +
1.1852 + typename Graph::Arc ue = typename Graph::OutArcIt(graph, u);
1.1853 + typename Graph::Arc ve = typename Graph::OutArcIt(graph, v);
1.1854 +
1.1855 + typename Graph::Arc e = graph.direct(graph.addEdge(u, v), true);
1.1856 +
1.1857 + if (ue != INVALID) {
1.1858 + embedding[e] = embedding[ue];
1.1859 + embedding[ue] = e;
1.1860 + } else {
1.1861 + embedding[e] = e;
1.1862 + }
1.1863 +
1.1864 + if (ve != INVALID) {
1.1865 + embedding[graph.oppositeArc(e)] = embedding[ve];
1.1866 + embedding[ve] = graph.oppositeArc(e);
1.1867 + } else {
1.1868 + embedding[graph.oppositeArc(e)] = graph.oppositeArc(e);
1.1869 + }
1.1870 + }
1.1871 + }
1.1872 + }
1.1873 + }
1.1874 +
1.1875 + template <typename Graph, typename EmbeddingMap>
1.1876 + void makeBiNodeConnected(Graph& graph, EmbeddingMap& embedding) {
1.1877 + typename Graph::template ArcMap<bool> processed(graph);
1.1878 +
1.1879 + std::vector<typename Graph::Arc> arcs;
1.1880 + for (typename Graph::ArcIt e(graph); e != INVALID; ++e) {
1.1881 + arcs.push_back(e);
1.1882 + }
1.1883 +
1.1884 + IterableBoolMap<Graph, typename Graph::Node> visited(graph, false);
1.1885 +
1.1886 + for (int i = 0; i < int(arcs.size()); ++i) {
1.1887 + typename Graph::Arc pp = arcs[i];
1.1888 + if (processed[pp]) continue;
1.1889 +
1.1890 + typename Graph::Arc e = embedding[graph.oppositeArc(pp)];
1.1891 + processed[e] = true;
1.1892 + visited.set(graph.source(e), true);
1.1893 +
1.1894 + typename Graph::Arc p = e, l = e;
1.1895 + e = embedding[graph.oppositeArc(e)];
1.1896 +
1.1897 + while (e != l) {
1.1898 + processed[e] = true;
1.1899 +
1.1900 + if (visited[graph.source(e)]) {
1.1901 +
1.1902 + typename Graph::Arc n =
1.1903 + graph.direct(graph.addEdge(graph.source(p),
1.1904 + graph.target(e)), true);
1.1905 + embedding[n] = p;
1.1906 + embedding[graph.oppositeArc(pp)] = n;
1.1907 +
1.1908 + embedding[graph.oppositeArc(n)] =
1.1909 + embedding[graph.oppositeArc(e)];
1.1910 + embedding[graph.oppositeArc(e)] =
1.1911 + graph.oppositeArc(n);
1.1912 +
1.1913 + p = n;
1.1914 + e = embedding[graph.oppositeArc(n)];
1.1915 + } else {
1.1916 + visited.set(graph.source(e), true);
1.1917 + pp = p;
1.1918 + p = e;
1.1919 + e = embedding[graph.oppositeArc(e)];
1.1920 + }
1.1921 + }
1.1922 + visited.setAll(false);
1.1923 + }
1.1924 + }
1.1925 +
1.1926 +
1.1927 + template <typename Graph, typename EmbeddingMap>
1.1928 + void makeMaxPlanar(Graph& graph, EmbeddingMap& embedding) {
1.1929 +
1.1930 + typename Graph::template NodeMap<int> degree(graph);
1.1931 +
1.1932 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
1.1933 + degree[n] = countIncEdges(graph, n);
1.1934 + }
1.1935 +
1.1936 + typename Graph::template ArcMap<bool> processed(graph);
1.1937 + IterableBoolMap<Graph, typename Graph::Node> visited(graph, false);
1.1938 +
1.1939 + std::vector<typename Graph::Arc> arcs;
1.1940 + for (typename Graph::ArcIt e(graph); e != INVALID; ++e) {
1.1941 + arcs.push_back(e);
1.1942 + }
1.1943 +
1.1944 + for (int i = 0; i < int(arcs.size()); ++i) {
1.1945 + typename Graph::Arc e = arcs[i];
1.1946 +
1.1947 + if (processed[e]) continue;
1.1948 + processed[e] = true;
1.1949 +
1.1950 + typename Graph::Arc mine = e;
1.1951 + int mind = degree[graph.source(e)];
1.1952 +
1.1953 + int face_size = 1;
1.1954 +
1.1955 + typename Graph::Arc l = e;
1.1956 + e = embedding[graph.oppositeArc(e)];
1.1957 + while (l != e) {
1.1958 + processed[e] = true;
1.1959 +
1.1960 + ++face_size;
1.1961 +
1.1962 + if (degree[graph.source(e)] < mind) {
1.1963 + mine = e;
1.1964 + mind = degree[graph.source(e)];
1.1965 + }
1.1966 +
1.1967 + e = embedding[graph.oppositeArc(e)];
1.1968 + }
1.1969 +
1.1970 + if (face_size < 4) {
1.1971 + continue;
1.1972 + }
1.1973 +
1.1974 + typename Graph::Node s = graph.source(mine);
1.1975 + for (typename Graph::OutArcIt e(graph, s); e != INVALID; ++e) {
1.1976 + visited.set(graph.target(e), true);
1.1977 + }
1.1978 +
1.1979 + typename Graph::Arc oppe = INVALID;
1.1980 +
1.1981 + e = embedding[graph.oppositeArc(mine)];
1.1982 + e = embedding[graph.oppositeArc(e)];
1.1983 + while (graph.target(e) != s) {
1.1984 + if (visited[graph.source(e)]) {
1.1985 + oppe = e;
1.1986 + break;
1.1987 + }
1.1988 + e = embedding[graph.oppositeArc(e)];
1.1989 + }
1.1990 + visited.setAll(false);
1.1991 +
1.1992 + if (oppe == INVALID) {
1.1993 +
1.1994 + e = embedding[graph.oppositeArc(mine)];
1.1995 + typename Graph::Arc pn = mine, p = e;
1.1996 +
1.1997 + e = embedding[graph.oppositeArc(e)];
1.1998 + while (graph.target(e) != s) {
1.1999 + typename Graph::Arc n =
1.2000 + graph.direct(graph.addEdge(s, graph.source(e)), true);
1.2001 +
1.2002 + embedding[n] = pn;
1.2003 + embedding[graph.oppositeArc(n)] = e;
1.2004 + embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
1.2005 +
1.2006 + pn = n;
1.2007 +
1.2008 + p = e;
1.2009 + e = embedding[graph.oppositeArc(e)];
1.2010 + }
1.2011 +
1.2012 + embedding[graph.oppositeArc(e)] = pn;
1.2013 +
1.2014 + } else {
1.2015 +
1.2016 + mine = embedding[graph.oppositeArc(mine)];
1.2017 + s = graph.source(mine);
1.2018 + oppe = embedding[graph.oppositeArc(oppe)];
1.2019 + typename Graph::Node t = graph.source(oppe);
1.2020 +
1.2021 + typename Graph::Arc ce = graph.direct(graph.addEdge(s, t), true);
1.2022 + embedding[ce] = mine;
1.2023 + embedding[graph.oppositeArc(ce)] = oppe;
1.2024 +
1.2025 + typename Graph::Arc pn = ce, p = oppe;
1.2026 + e = embedding[graph.oppositeArc(oppe)];
1.2027 + while (graph.target(e) != s) {
1.2028 + typename Graph::Arc n =
1.2029 + graph.direct(graph.addEdge(s, graph.source(e)), true);
1.2030 +
1.2031 + embedding[n] = pn;
1.2032 + embedding[graph.oppositeArc(n)] = e;
1.2033 + embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
1.2034 +
1.2035 + pn = n;
1.2036 +
1.2037 + p = e;
1.2038 + e = embedding[graph.oppositeArc(e)];
1.2039 +
1.2040 + }
1.2041 + embedding[graph.oppositeArc(e)] = pn;
1.2042 +
1.2043 + pn = graph.oppositeArc(ce), p = mine;
1.2044 + e = embedding[graph.oppositeArc(mine)];
1.2045 + while (graph.target(e) != t) {
1.2046 + typename Graph::Arc n =
1.2047 + graph.direct(graph.addEdge(t, graph.source(e)), true);
1.2048 +
1.2049 + embedding[n] = pn;
1.2050 + embedding[graph.oppositeArc(n)] = e;
1.2051 + embedding[graph.oppositeArc(p)] = graph.oppositeArc(n);
1.2052 +
1.2053 + pn = n;
1.2054 +
1.2055 + p = e;
1.2056 + e = embedding[graph.oppositeArc(e)];
1.2057 +
1.2058 + }
1.2059 + embedding[graph.oppositeArc(e)] = pn;
1.2060 + }
1.2061 + }
1.2062 + }
1.2063 +
1.2064 + }
1.2065 +
1.2066 + /// \ingroup planar
1.2067 + ///
1.2068 + /// \brief Schnyder's planar drawing algorithm
1.2069 + ///
1.2070 + /// The planar drawing algorithm calculates positions for the nodes
1.2071 + /// in the plane. These coordinates satisfy that if the edges are
1.2072 + /// represented with straight lines, then they will not intersect
1.2073 + /// each other.
1.2074 + ///
1.2075 + /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
1.2076 + /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
1.2077 + /// The time complexity of the algorithm is O(n).
1.2078 + ///
1.2079 + /// \see PlanarEmbedding
1.2080 + template <typename Graph>
1.2081 + class PlanarDrawing {
1.2082 + public:
1.2083 +
1.2084 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.2085 +
1.2086 + /// \brief The point type for storing coordinates
1.2087 + typedef dim2::Point<int> Point;
1.2088 + /// \brief The map type for storing the coordinates of the nodes
1.2089 + typedef typename Graph::template NodeMap<Point> PointMap;
1.2090 +
1.2091 +
1.2092 + /// \brief Constructor
1.2093 + ///
1.2094 + /// Constructor
1.2095 + /// \pre The graph must be simple, i.e. it should not
1.2096 + /// contain parallel or loop arcs.
1.2097 + PlanarDrawing(const Graph& graph)
1.2098 + : _graph(graph), _point_map(graph) {}
1.2099 +
1.2100 + private:
1.2101 +
1.2102 + template <typename AuxGraph, typename AuxEmbeddingMap>
1.2103 + void drawing(const AuxGraph& graph,
1.2104 + const AuxEmbeddingMap& next,
1.2105 + PointMap& point_map) {
1.2106 + TEMPLATE_GRAPH_TYPEDEFS(AuxGraph);
1.2107 +
1.2108 + typename AuxGraph::template ArcMap<Arc> prev(graph);
1.2109 +
1.2110 + for (NodeIt n(graph); n != INVALID; ++n) {
1.2111 + Arc e = OutArcIt(graph, n);
1.2112 +
1.2113 + Arc p = e, l = e;
1.2114 +
1.2115 + e = next[e];
1.2116 + while (e != l) {
1.2117 + prev[e] = p;
1.2118 + p = e;
1.2119 + e = next[e];
1.2120 + }
1.2121 + prev[e] = p;
1.2122 + }
1.2123 +
1.2124 + Node anode, bnode, cnode;
1.2125 +
1.2126 + {
1.2127 + Arc e = ArcIt(graph);
1.2128 + anode = graph.source(e);
1.2129 + bnode = graph.target(e);
1.2130 + cnode = graph.target(next[graph.oppositeArc(e)]);
1.2131 + }
1.2132 +
1.2133 + IterableBoolMap<AuxGraph, Node> proper(graph, false);
1.2134 + typename AuxGraph::template NodeMap<int> conn(graph, -1);
1.2135 +
1.2136 + conn[anode] = conn[bnode] = -2;
1.2137 + {
1.2138 + for (OutArcIt e(graph, anode); e != INVALID; ++e) {
1.2139 + Node m = graph.target(e);
1.2140 + if (conn[m] == -1) {
1.2141 + conn[m] = 1;
1.2142 + }
1.2143 + }
1.2144 + conn[cnode] = 2;
1.2145 +
1.2146 + for (OutArcIt e(graph, bnode); e != INVALID; ++e) {
1.2147 + Node m = graph.target(e);
1.2148 + if (conn[m] == -1) {
1.2149 + conn[m] = 1;
1.2150 + } else if (conn[m] != -2) {
1.2151 + conn[m] += 1;
1.2152 + Arc pe = graph.oppositeArc(e);
1.2153 + if (conn[graph.target(next[pe])] == -2) {
1.2154 + conn[m] -= 1;
1.2155 + }
1.2156 + if (conn[graph.target(prev[pe])] == -2) {
1.2157 + conn[m] -= 1;
1.2158 + }
1.2159 +
1.2160 + proper.set(m, conn[m] == 1);
1.2161 + }
1.2162 + }
1.2163 + }
1.2164 +
1.2165 +
1.2166 + typename AuxGraph::template ArcMap<int> angle(graph, -1);
1.2167 +
1.2168 + while (proper.trueNum() != 0) {
1.2169 + Node n = typename IterableBoolMap<AuxGraph, Node>::TrueIt(proper);
1.2170 + proper.set(n, false);
1.2171 + conn[n] = -2;
1.2172 +
1.2173 + for (OutArcIt e(graph, n); e != INVALID; ++e) {
1.2174 + Node m = graph.target(e);
1.2175 + if (conn[m] == -1) {
1.2176 + conn[m] = 1;
1.2177 + } else if (conn[m] != -2) {
1.2178 + conn[m] += 1;
1.2179 + Arc pe = graph.oppositeArc(e);
1.2180 + if (conn[graph.target(next[pe])] == -2) {
1.2181 + conn[m] -= 1;
1.2182 + }
1.2183 + if (conn[graph.target(prev[pe])] == -2) {
1.2184 + conn[m] -= 1;
1.2185 + }
1.2186 +
1.2187 + proper.set(m, conn[m] == 1);
1.2188 + }
1.2189 + }
1.2190 +
1.2191 + {
1.2192 + Arc e = OutArcIt(graph, n);
1.2193 + Arc p = e, l = e;
1.2194 +
1.2195 + e = next[e];
1.2196 + while (e != l) {
1.2197 +
1.2198 + if (conn[graph.target(e)] == -2 && conn[graph.target(p)] == -2) {
1.2199 + Arc f = e;
1.2200 + angle[f] = 0;
1.2201 + f = next[graph.oppositeArc(f)];
1.2202 + angle[f] = 1;
1.2203 + f = next[graph.oppositeArc(f)];
1.2204 + angle[f] = 2;
1.2205 + }
1.2206 +
1.2207 + p = e;
1.2208 + e = next[e];
1.2209 + }
1.2210 +
1.2211 + if (conn[graph.target(e)] == -2 && conn[graph.target(p)] == -2) {
1.2212 + Arc f = e;
1.2213 + angle[f] = 0;
1.2214 + f = next[graph.oppositeArc(f)];
1.2215 + angle[f] = 1;
1.2216 + f = next[graph.oppositeArc(f)];
1.2217 + angle[f] = 2;
1.2218 + }
1.2219 + }
1.2220 + }
1.2221 +
1.2222 + typename AuxGraph::template NodeMap<Node> apred(graph, INVALID);
1.2223 + typename AuxGraph::template NodeMap<Node> bpred(graph, INVALID);
1.2224 + typename AuxGraph::template NodeMap<Node> cpred(graph, INVALID);
1.2225 +
1.2226 + typename AuxGraph::template NodeMap<int> apredid(graph, -1);
1.2227 + typename AuxGraph::template NodeMap<int> bpredid(graph, -1);
1.2228 + typename AuxGraph::template NodeMap<int> cpredid(graph, -1);
1.2229 +
1.2230 + for (ArcIt e(graph); e != INVALID; ++e) {
1.2231 + if (angle[e] == angle[next[e]]) {
1.2232 + switch (angle[e]) {
1.2233 + case 2:
1.2234 + apred[graph.target(e)] = graph.source(e);
1.2235 + apredid[graph.target(e)] = graph.id(graph.source(e));
1.2236 + break;
1.2237 + case 1:
1.2238 + bpred[graph.target(e)] = graph.source(e);
1.2239 + bpredid[graph.target(e)] = graph.id(graph.source(e));
1.2240 + break;
1.2241 + case 0:
1.2242 + cpred[graph.target(e)] = graph.source(e);
1.2243 + cpredid[graph.target(e)] = graph.id(graph.source(e));
1.2244 + break;
1.2245 + }
1.2246 + }
1.2247 + }
1.2248 +
1.2249 + cpred[anode] = INVALID;
1.2250 + cpred[bnode] = INVALID;
1.2251 +
1.2252 + std::vector<Node> aorder, border, corder;
1.2253 +
1.2254 + {
1.2255 + typename AuxGraph::template NodeMap<bool> processed(graph, false);
1.2256 + std::vector<Node> st;
1.2257 + for (NodeIt n(graph); n != INVALID; ++n) {
1.2258 + if (!processed[n] && n != bnode && n != cnode) {
1.2259 + st.push_back(n);
1.2260 + processed[n] = true;
1.2261 + Node m = apred[n];
1.2262 + while (m != INVALID && !processed[m]) {
1.2263 + st.push_back(m);
1.2264 + processed[m] = true;
1.2265 + m = apred[m];
1.2266 + }
1.2267 + while (!st.empty()) {
1.2268 + aorder.push_back(st.back());
1.2269 + st.pop_back();
1.2270 + }
1.2271 + }
1.2272 + }
1.2273 + }
1.2274 +
1.2275 + {
1.2276 + typename AuxGraph::template NodeMap<bool> processed(graph, false);
1.2277 + std::vector<Node> st;
1.2278 + for (NodeIt n(graph); n != INVALID; ++n) {
1.2279 + if (!processed[n] && n != cnode && n != anode) {
1.2280 + st.push_back(n);
1.2281 + processed[n] = true;
1.2282 + Node m = bpred[n];
1.2283 + while (m != INVALID && !processed[m]) {
1.2284 + st.push_back(m);
1.2285 + processed[m] = true;
1.2286 + m = bpred[m];
1.2287 + }
1.2288 + while (!st.empty()) {
1.2289 + border.push_back(st.back());
1.2290 + st.pop_back();
1.2291 + }
1.2292 + }
1.2293 + }
1.2294 + }
1.2295 +
1.2296 + {
1.2297 + typename AuxGraph::template NodeMap<bool> processed(graph, false);
1.2298 + std::vector<Node> st;
1.2299 + for (NodeIt n(graph); n != INVALID; ++n) {
1.2300 + if (!processed[n] && n != anode && n != bnode) {
1.2301 + st.push_back(n);
1.2302 + processed[n] = true;
1.2303 + Node m = cpred[n];
1.2304 + while (m != INVALID && !processed[m]) {
1.2305 + st.push_back(m);
1.2306 + processed[m] = true;
1.2307 + m = cpred[m];
1.2308 + }
1.2309 + while (!st.empty()) {
1.2310 + corder.push_back(st.back());
1.2311 + st.pop_back();
1.2312 + }
1.2313 + }
1.2314 + }
1.2315 + }
1.2316 +
1.2317 + typename AuxGraph::template NodeMap<int> atree(graph, 0);
1.2318 + for (int i = aorder.size() - 1; i >= 0; --i) {
1.2319 + Node n = aorder[i];
1.2320 + atree[n] = 1;
1.2321 + for (OutArcIt e(graph, n); e != INVALID; ++e) {
1.2322 + if (apred[graph.target(e)] == n) {
1.2323 + atree[n] += atree[graph.target(e)];
1.2324 + }
1.2325 + }
1.2326 + }
1.2327 +
1.2328 + typename AuxGraph::template NodeMap<int> btree(graph, 0);
1.2329 + for (int i = border.size() - 1; i >= 0; --i) {
1.2330 + Node n = border[i];
1.2331 + btree[n] = 1;
1.2332 + for (OutArcIt e(graph, n); e != INVALID; ++e) {
1.2333 + if (bpred[graph.target(e)] == n) {
1.2334 + btree[n] += btree[graph.target(e)];
1.2335 + }
1.2336 + }
1.2337 + }
1.2338 +
1.2339 + typename AuxGraph::template NodeMap<int> apath(graph, 0);
1.2340 + apath[bnode] = apath[cnode] = 1;
1.2341 + typename AuxGraph::template NodeMap<int> apath_btree(graph, 0);
1.2342 + apath_btree[bnode] = btree[bnode];
1.2343 + for (int i = 1; i < int(aorder.size()); ++i) {
1.2344 + Node n = aorder[i];
1.2345 + apath[n] = apath[apred[n]] + 1;
1.2346 + apath_btree[n] = btree[n] + apath_btree[apred[n]];
1.2347 + }
1.2348 +
1.2349 + typename AuxGraph::template NodeMap<int> bpath_atree(graph, 0);
1.2350 + bpath_atree[anode] = atree[anode];
1.2351 + for (int i = 1; i < int(border.size()); ++i) {
1.2352 + Node n = border[i];
1.2353 + bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
1.2354 + }
1.2355 +
1.2356 + typename AuxGraph::template NodeMap<int> cpath(graph, 0);
1.2357 + cpath[anode] = cpath[bnode] = 1;
1.2358 + typename AuxGraph::template NodeMap<int> cpath_atree(graph, 0);
1.2359 + cpath_atree[anode] = atree[anode];
1.2360 + typename AuxGraph::template NodeMap<int> cpath_btree(graph, 0);
1.2361 + cpath_btree[bnode] = btree[bnode];
1.2362 + for (int i = 1; i < int(corder.size()); ++i) {
1.2363 + Node n = corder[i];
1.2364 + cpath[n] = cpath[cpred[n]] + 1;
1.2365 + cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
1.2366 + cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
1.2367 + }
1.2368 +
1.2369 + typename AuxGraph::template NodeMap<int> third(graph);
1.2370 + for (NodeIt n(graph); n != INVALID; ++n) {
1.2371 + point_map[n].x =
1.2372 + bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
1.2373 + point_map[n].y =
1.2374 + cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
1.2375 + }
1.2376 +
1.2377 + }
1.2378 +
1.2379 + public:
1.2380 +
1.2381 + /// \brief Calculate the node positions
1.2382 + ///
1.2383 + /// This function calculates the node positions on the plane.
1.2384 + /// \return \c true if the graph is planar.
1.2385 + bool run() {
1.2386 + PlanarEmbedding<Graph> pe(_graph);
1.2387 + if (!pe.run()) return false;
1.2388 +
1.2389 + run(pe);
1.2390 + return true;
1.2391 + }
1.2392 +
1.2393 + /// \brief Calculate the node positions according to a
1.2394 + /// combinatorical embedding
1.2395 + ///
1.2396 + /// This function calculates the node positions on the plane.
1.2397 + /// The given \c embedding map should contain a valid combinatorical
1.2398 + /// embedding, i.e. a valid cyclic order of the arcs.
1.2399 + /// It can be computed using PlanarEmbedding.
1.2400 + template <typename EmbeddingMap>
1.2401 + void run(const EmbeddingMap& embedding) {
1.2402 + typedef SmartEdgeSet<Graph> AuxGraph;
1.2403 +
1.2404 + if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {
1.2405 + drawing(_graph, embedding, _point_map);
1.2406 + return;
1.2407 + }
1.2408 +
1.2409 + AuxGraph aux_graph(_graph);
1.2410 + typename AuxGraph::template ArcMap<typename AuxGraph::Arc>
1.2411 + aux_embedding(aux_graph);
1.2412 +
1.2413 + {
1.2414 +
1.2415 + typename Graph::template EdgeMap<typename AuxGraph::Edge>
1.2416 + ref(_graph);
1.2417 +
1.2418 + for (EdgeIt e(_graph); e != INVALID; ++e) {
1.2419 + ref[e] = aux_graph.addEdge(_graph.u(e), _graph.v(e));
1.2420 + }
1.2421 +
1.2422 + for (EdgeIt e(_graph); e != INVALID; ++e) {
1.2423 + Arc ee = embedding[_graph.direct(e, true)];
1.2424 + aux_embedding[aux_graph.direct(ref[e], true)] =
1.2425 + aux_graph.direct(ref[ee], _graph.direction(ee));
1.2426 + ee = embedding[_graph.direct(e, false)];
1.2427 + aux_embedding[aux_graph.direct(ref[e], false)] =
1.2428 + aux_graph.direct(ref[ee], _graph.direction(ee));
1.2429 + }
1.2430 + }
1.2431 + _planarity_bits::makeConnected(aux_graph, aux_embedding);
1.2432 + _planarity_bits::makeBiNodeConnected(aux_graph, aux_embedding);
1.2433 + _planarity_bits::makeMaxPlanar(aux_graph, aux_embedding);
1.2434 + drawing(aux_graph, aux_embedding, _point_map);
1.2435 + }
1.2436 +
1.2437 + /// \brief The coordinate of the given node
1.2438 + ///
1.2439 + /// This function returns the coordinate of the given node.
1.2440 + Point operator[](const Node& node) const {
1.2441 + return _point_map[node];
1.2442 + }
1.2443 +
1.2444 + /// \brief Return the grid embedding in a node map
1.2445 + ///
1.2446 + /// This function returns the grid embedding in a node map of
1.2447 + /// \c dim2::Point<int> coordinates.
1.2448 + const PointMap& coords() const {
1.2449 + return _point_map;
1.2450 + }
1.2451 +
1.2452 + private:
1.2453 +
1.2454 + const Graph& _graph;
1.2455 + PointMap _point_map;
1.2456 +
1.2457 + };
1.2458 +
1.2459 + namespace _planarity_bits {
1.2460 +
1.2461 + template <typename ColorMap>
1.2462 + class KempeFilter {
1.2463 + public:
1.2464 + typedef typename ColorMap::Key Key;
1.2465 + typedef bool Value;
1.2466 +
1.2467 + KempeFilter(const ColorMap& color_map,
1.2468 + const typename ColorMap::Value& first,
1.2469 + const typename ColorMap::Value& second)
1.2470 + : _color_map(color_map), _first(first), _second(second) {}
1.2471 +
1.2472 + Value operator[](const Key& key) const {
1.2473 + return _color_map[key] == _first || _color_map[key] == _second;
1.2474 + }
1.2475 +
1.2476 + private:
1.2477 + const ColorMap& _color_map;
1.2478 + typename ColorMap::Value _first, _second;
1.2479 + };
1.2480 + }
1.2481 +
1.2482 + /// \ingroup planar
1.2483 + ///
1.2484 + /// \brief Coloring planar graphs
1.2485 + ///
1.2486 + /// The graph coloring problem is the coloring of the graph nodes
1.2487 + /// so that there are no adjacent nodes with the same color. The
1.2488 + /// planar graphs can always be colored with four colors, which is
1.2489 + /// proved by Appel and Haken. Their proofs provide a quadratic
1.2490 + /// time algorithm for four coloring, but it could not be used to
1.2491 + /// implement an efficient algorithm. The five and six coloring can be
1.2492 + /// made in linear time, but in this class, the five coloring has
1.2493 + /// quadratic worst case time complexity. The two coloring (if
1.2494 + /// possible) is solvable with a graph search algorithm and it is
1.2495 + /// implemented in \ref bipartitePartitions() function in LEMON. To
1.2496 + /// decide whether a planar graph is three colorable is NP-complete.
1.2497 + ///
1.2498 + /// This class contains member functions for calculate colorings
1.2499 + /// with five and six colors. The six coloring algorithm is a simple
1.2500 + /// greedy coloring on the backward minimum outgoing order of nodes.
1.2501 + /// This order can be computed by selecting the node with least
1.2502 + /// outgoing arcs to unprocessed nodes in each phase. This order
1.2503 + /// guarantees that when a node is chosen for coloring it has at
1.2504 + /// most five already colored adjacents. The five coloring algorithm
1.2505 + /// use the same method, but if the greedy approach fails to color
1.2506 + /// with five colors, i.e. the node has five already different
1.2507 + /// colored neighbours, it swaps the colors in one of the connected
1.2508 + /// two colored sets with the Kempe recoloring method.
1.2509 + template <typename Graph>
1.2510 + class PlanarColoring {
1.2511 + public:
1.2512 +
1.2513 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.2514 +
1.2515 + /// \brief The map type for storing color indices
1.2516 + typedef typename Graph::template NodeMap<int> IndexMap;
1.2517 + /// \brief The map type for storing colors
1.2518 + ///
1.2519 + /// The map type for storing colors.
1.2520 + /// \see Palette, Color
1.2521 + typedef ComposeMap<Palette, IndexMap> ColorMap;
1.2522 +
1.2523 + /// \brief Constructor
1.2524 + ///
1.2525 + /// Constructor.
1.2526 + /// \pre The graph must be simple, i.e. it should not
1.2527 + /// contain parallel or loop arcs.
1.2528 + PlanarColoring(const Graph& graph)
1.2529 + : _graph(graph), _color_map(graph), _palette(0) {
1.2530 + _palette.add(Color(1,0,0));
1.2531 + _palette.add(Color(0,1,0));
1.2532 + _palette.add(Color(0,0,1));
1.2533 + _palette.add(Color(1,1,0));
1.2534 + _palette.add(Color(1,0,1));
1.2535 + _palette.add(Color(0,1,1));
1.2536 + }
1.2537 +
1.2538 + /// \brief Return the node map of color indices
1.2539 + ///
1.2540 + /// This function returns the node map of color indices. The values are
1.2541 + /// in the range \c [0..4] or \c [0..5] according to the coloring method.
1.2542 + IndexMap colorIndexMap() const {
1.2543 + return _color_map;
1.2544 + }
1.2545 +
1.2546 + /// \brief Return the node map of colors
1.2547 + ///
1.2548 + /// This function returns the node map of colors. The values are among
1.2549 + /// five or six distinct \ref lemon::Color "colors".
1.2550 + ColorMap colorMap() const {
1.2551 + return composeMap(_palette, _color_map);
1.2552 + }
1.2553 +
1.2554 + /// \brief Return the color index of the node
1.2555 + ///
1.2556 + /// This function returns the color index of the given node. The value is
1.2557 + /// in the range \c [0..4] or \c [0..5] according to the coloring method.
1.2558 + int colorIndex(const Node& node) const {
1.2559 + return _color_map[node];
1.2560 + }
1.2561 +
1.2562 + /// \brief Return the color of the node
1.2563 + ///
1.2564 + /// This function returns the color of the given node. The value is among
1.2565 + /// five or six distinct \ref lemon::Color "colors".
1.2566 + Color color(const Node& node) const {
1.2567 + return _palette[_color_map[node]];
1.2568 + }
1.2569 +
1.2570 +
1.2571 + /// \brief Calculate a coloring with at most six colors
1.2572 + ///
1.2573 + /// This function calculates a coloring with at most six colors. The time
1.2574 + /// complexity of this variant is linear in the size of the graph.
1.2575 + /// \return \c true if the algorithm could color the graph with six colors.
1.2576 + /// If the algorithm fails, then the graph is not planar.
1.2577 + /// \note This function can return \c true if the graph is not
1.2578 + /// planar, but it can be colored with at most six colors.
1.2579 + bool runSixColoring() {
1.2580 +
1.2581 + typename Graph::template NodeMap<int> heap_index(_graph, -1);
1.2582 + BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
1.2583 +
1.2584 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.2585 + _color_map[n] = -2;
1.2586 + heap.push(n, countOutArcs(_graph, n));
1.2587 + }
1.2588 +
1.2589 + std::vector<Node> order;
1.2590 +
1.2591 + while (!heap.empty()) {
1.2592 + Node n = heap.top();
1.2593 + heap.pop();
1.2594 + _color_map[n] = -1;
1.2595 + order.push_back(n);
1.2596 + for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.2597 + Node t = _graph.runningNode(e);
1.2598 + if (_color_map[t] == -2) {
1.2599 + heap.decrease(t, heap[t] - 1);
1.2600 + }
1.2601 + }
1.2602 + }
1.2603 +
1.2604 + for (int i = order.size() - 1; i >= 0; --i) {
1.2605 + std::vector<bool> forbidden(6, false);
1.2606 + for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {
1.2607 + Node t = _graph.runningNode(e);
1.2608 + if (_color_map[t] != -1) {
1.2609 + forbidden[_color_map[t]] = true;
1.2610 + }
1.2611 + }
1.2612 + for (int k = 0; k < 6; ++k) {
1.2613 + if (!forbidden[k]) {
1.2614 + _color_map[order[i]] = k;
1.2615 + break;
1.2616 + }
1.2617 + }
1.2618 + if (_color_map[order[i]] == -1) {
1.2619 + return false;
1.2620 + }
1.2621 + }
1.2622 + return true;
1.2623 + }
1.2624 +
1.2625 + private:
1.2626 +
1.2627 + bool recolor(const Node& u, const Node& v) {
1.2628 + int ucolor = _color_map[u];
1.2629 + int vcolor = _color_map[v];
1.2630 + typedef _planarity_bits::KempeFilter<IndexMap> KempeFilter;
1.2631 + KempeFilter filter(_color_map, ucolor, vcolor);
1.2632 +
1.2633 + typedef FilterNodes<const Graph, const KempeFilter> KempeGraph;
1.2634 + KempeGraph kempe_graph(_graph, filter);
1.2635 +
1.2636 + std::vector<Node> comp;
1.2637 + Bfs<KempeGraph> bfs(kempe_graph);
1.2638 + bfs.init();
1.2639 + bfs.addSource(u);
1.2640 + while (!bfs.emptyQueue()) {
1.2641 + Node n = bfs.nextNode();
1.2642 + if (n == v) return false;
1.2643 + comp.push_back(n);
1.2644 + bfs.processNextNode();
1.2645 + }
1.2646 +
1.2647 + int scolor = ucolor + vcolor;
1.2648 + for (int i = 0; i < static_cast<int>(comp.size()); ++i) {
1.2649 + _color_map[comp[i]] = scolor - _color_map[comp[i]];
1.2650 + }
1.2651 +
1.2652 + return true;
1.2653 + }
1.2654 +
1.2655 + template <typename EmbeddingMap>
1.2656 + void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) {
1.2657 + std::vector<Node> nodes;
1.2658 + nodes.reserve(4);
1.2659 +
1.2660 + for (Arc e = OutArcIt(_graph, node); e != INVALID; e = embedding[e]) {
1.2661 + Node t = _graph.target(e);
1.2662 + if (_color_map[t] != -1) {
1.2663 + nodes.push_back(t);
1.2664 + if (nodes.size() == 4) break;
1.2665 + }
1.2666 + }
1.2667 +
1.2668 + int color = _color_map[nodes[0]];
1.2669 + if (recolor(nodes[0], nodes[2])) {
1.2670 + _color_map[node] = color;
1.2671 + } else {
1.2672 + color = _color_map[nodes[1]];
1.2673 + recolor(nodes[1], nodes[3]);
1.2674 + _color_map[node] = color;
1.2675 + }
1.2676 + }
1.2677 +
1.2678 + public:
1.2679 +
1.2680 + /// \brief Calculate a coloring with at most five colors
1.2681 + ///
1.2682 + /// This function calculates a coloring with at most five
1.2683 + /// colors. The worst case time complexity of this variant is
1.2684 + /// quadratic in the size of the graph.
1.2685 + /// \param embedding This map should contain a valid combinatorical
1.2686 + /// embedding, i.e. a valid cyclic order of the arcs.
1.2687 + /// It can be computed using PlanarEmbedding.
1.2688 + template <typename EmbeddingMap>
1.2689 + void runFiveColoring(const EmbeddingMap& embedding) {
1.2690 +
1.2691 + typename Graph::template NodeMap<int> heap_index(_graph, -1);
1.2692 + BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
1.2693 +
1.2694 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.2695 + _color_map[n] = -2;
1.2696 + heap.push(n, countOutArcs(_graph, n));
1.2697 + }
1.2698 +
1.2699 + std::vector<Node> order;
1.2700 +
1.2701 + while (!heap.empty()) {
1.2702 + Node n = heap.top();
1.2703 + heap.pop();
1.2704 + _color_map[n] = -1;
1.2705 + order.push_back(n);
1.2706 + for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.2707 + Node t = _graph.runningNode(e);
1.2708 + if (_color_map[t] == -2) {
1.2709 + heap.decrease(t, heap[t] - 1);
1.2710 + }
1.2711 + }
1.2712 + }
1.2713 +
1.2714 + for (int i = order.size() - 1; i >= 0; --i) {
1.2715 + std::vector<bool> forbidden(5, false);
1.2716 + for (OutArcIt e(_graph, order[i]); e != INVALID; ++e) {
1.2717 + Node t = _graph.runningNode(e);
1.2718 + if (_color_map[t] != -1) {
1.2719 + forbidden[_color_map[t]] = true;
1.2720 + }
1.2721 + }
1.2722 + for (int k = 0; k < 5; ++k) {
1.2723 + if (!forbidden[k]) {
1.2724 + _color_map[order[i]] = k;
1.2725 + break;
1.2726 + }
1.2727 + }
1.2728 + if (_color_map[order[i]] == -1) {
1.2729 + kempeRecoloring(order[i], embedding);
1.2730 + }
1.2731 + }
1.2732 + }
1.2733 +
1.2734 + /// \brief Calculate a coloring with at most five colors
1.2735 + ///
1.2736 + /// This function calculates a coloring with at most five
1.2737 + /// colors. The worst case time complexity of this variant is
1.2738 + /// quadratic in the size of the graph.
1.2739 + /// \return \c true if the graph is planar.
1.2740 + bool runFiveColoring() {
1.2741 + PlanarEmbedding<Graph> pe(_graph);
1.2742 + if (!pe.run()) return false;
1.2743 +
1.2744 + runFiveColoring(pe.embeddingMap());
1.2745 + return true;
1.2746 + }
1.2747 +
1.2748 + private:
1.2749 +
1.2750 + const Graph& _graph;
1.2751 + IndexMap _color_map;
1.2752 + Palette _palette;
1.2753 + };
1.2754 +
1.2755 +}
1.2756 +
1.2757 +#endif