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