1.1 --- a/lemon/planarity.h Fri Oct 19 15:21:07 2007 +0000
1.2 +++ b/lemon/planarity.h Fri Oct 19 16:24:31 2007 +0000
1.3 @@ -18,7 +18,7 @@
1.4 #ifndef LEMON_PLANARITY_H
1.5 #define LEMON_PLANARITY_H
1.6
1.7 -/// \ingroup graph_prop
1.8 +/// \ingroup planar
1.9 /// \file
1.10 /// \brief Planarity checking, embedding
1.11
1.12 @@ -29,6 +29,8 @@
1.13 #include <lemon/radix_sort.h>
1.14 #include <lemon/maps.h>
1.15 #include <lemon/path.h>
1.16 +#include <lemon/iterable_maps.h>
1.17 +#include <lemon/edge_set.h>
1.18
1.19
1.20 namespace lemon {
1.21 @@ -134,11 +136,11 @@
1.22
1.23 }
1.24
1.25 - /// \ingroup graph_prop
1.26 + /// \ingroup planar
1.27 ///
1.28 /// \brief Planarity checking of an undirected simple graph
1.29 ///
1.30 - /// This class implements the Boyer-Myrvold algorithm for planar
1.31 + /// This class implements the Boyer-Myrvold algorithm for planarity
1.32 /// checking of an undirected graph. This class is a simplified
1.33 /// version of the PlanarEmbedding algorithm class, and it does
1.34 /// provide neither embedding nor kuratowski subdivisons.
1.35 @@ -146,7 +148,7 @@
1.36 class PlanarityChecking {
1.37 private:
1.38
1.39 - UGRAPH_TYPEDEFS(typename UGraph)
1.40 + UGRAPH_TYPEDEFS(typename UGraph);
1.41
1.42 const UGraph& _ugraph;
1.43
1.44 @@ -522,7 +524,7 @@
1.45
1.46 };
1.47
1.48 - /// \ingroup graph_prop
1.49 + /// \ingroup planar
1.50 ///
1.51 /// \brief Planar embedding of an undirected simple graph
1.52 ///
1.53 @@ -541,7 +543,7 @@
1.54 class PlanarEmbedding {
1.55 private:
1.56
1.57 - UGRAPH_TYPEDEFS(typename UGraph)
1.58 + UGRAPH_TYPEDEFS(typename UGraph);
1.59
1.60 const UGraph& _ugraph;
1.61 typename UGraph::template EdgeMap<Edge> _embedding;
1.62 @@ -586,6 +588,9 @@
1.63
1.64 public:
1.65
1.66 + /// \brief The map for store of embedding
1.67 + typedef typename UGraph::template EdgeMap<Edge> EmbeddingMap;
1.68 +
1.69 /// \brief Constructor
1.70 ///
1.71 /// \warining The graph should be simple, i.e. parallel and loop edge
1.72 @@ -701,6 +706,14 @@
1.73 return _embedding[edge];
1.74 }
1.75
1.76 + /// \brief Gives back the calculated embedding map
1.77 + ///
1.78 + /// The returned map contains the successor of each edge in the
1.79 + /// graph.
1.80 + const EmbeddingMap& embedding() const {
1.81 + return _embedding;
1.82 + }
1.83 +
1.84 /// \brief Gives back true when the undirected edge is in the
1.85 /// kuratowski subdivision
1.86 ///
1.87 @@ -1806,6 +1819,623 @@
1.88
1.89 };
1.90
1.91 + namespace _planarity_bits {
1.92 +
1.93 + template <typename UGraph, typename EmbeddingMap>
1.94 + void makeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
1.95 + DfsVisitor<UGraph> null_visitor;
1.96 + DfsVisit<UGraph, DfsVisitor<UGraph> > dfs(ugraph, null_visitor);
1.97 + dfs.init();
1.98 +
1.99 + typename UGraph::Node u = INVALID;
1.100 + for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
1.101 + if (!dfs.reached(n)) {
1.102 + dfs.addSource(n);
1.103 + dfs.start();
1.104 + if (u == INVALID) {
1.105 + u = n;
1.106 + } else {
1.107 + typename UGraph::Node v = n;
1.108 +
1.109 + typename UGraph::Edge ue = typename UGraph::OutEdgeIt(ugraph, u);
1.110 + typename UGraph::Edge ve = typename UGraph::OutEdgeIt(ugraph, v);
1.111 +
1.112 + typename UGraph::Edge e = ugraph.direct(ugraph.addEdge(u, v), true);
1.113 +
1.114 + if (ue != INVALID) {
1.115 + embedding[e] = embedding[ue];
1.116 + embedding[ue] = e;
1.117 + } else {
1.118 + embedding[e] = e;
1.119 + }
1.120 +
1.121 + if (ve != INVALID) {
1.122 + embedding[ugraph.oppositeEdge(e)] = embedding[ve];
1.123 + embedding[ve] = ugraph.oppositeEdge(e);
1.124 + } else {
1.125 + embedding[ugraph.oppositeEdge(e)] = ugraph.oppositeEdge(e);
1.126 + }
1.127 + }
1.128 + }
1.129 + }
1.130 + }
1.131 +
1.132 + template <typename UGraph, typename EmbeddingMap>
1.133 + void makeBiNodeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
1.134 + typename UGraph::template EdgeMap<bool> processed(ugraph);
1.135 +
1.136 + std::vector<typename UGraph::Edge> edges;
1.137 + for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
1.138 + edges.push_back(e);
1.139 + }
1.140 +
1.141 + IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
1.142 +
1.143 + for (int i = 0; i < int(edges.size()); ++i) {
1.144 + typename UGraph::Edge pp = edges[i];
1.145 + if (processed[pp]) continue;
1.146 +
1.147 + typename UGraph::Edge e = embedding[ugraph.oppositeEdge(pp)];
1.148 + processed[e] = true;
1.149 + visited.set(ugraph.source(e), true);
1.150 +
1.151 + typename UGraph::Edge p = e, l = e;
1.152 + e = embedding[ugraph.oppositeEdge(e)];
1.153 +
1.154 + while (e != l) {
1.155 + processed[e] = true;
1.156 +
1.157 + if (visited[ugraph.source(e)]) {
1.158 +
1.159 + typename UGraph::Edge n =
1.160 + ugraph.direct(ugraph.addEdge(ugraph.source(p),
1.161 + ugraph.target(e)), true);
1.162 + embedding[n] = p;
1.163 + embedding[ugraph.oppositeEdge(pp)] = n;
1.164 +
1.165 + embedding[ugraph.oppositeEdge(n)] =
1.166 + embedding[ugraph.oppositeEdge(e)];
1.167 + embedding[ugraph.oppositeEdge(e)] =
1.168 + ugraph.oppositeEdge(n);
1.169 +
1.170 + p = n;
1.171 + e = embedding[ugraph.oppositeEdge(n)];
1.172 + } else {
1.173 + visited.set(ugraph.source(e), true);
1.174 + pp = p;
1.175 + p = e;
1.176 + e = embedding[ugraph.oppositeEdge(e)];
1.177 + }
1.178 + }
1.179 + visited.setAll(false);
1.180 + }
1.181 + }
1.182 +
1.183 +
1.184 + template <typename UGraph, typename EmbeddingMap>
1.185 + void makeMaxPlanar(UGraph& ugraph, EmbeddingMap& embedding) {
1.186 +
1.187 + typename UGraph::template NodeMap<int> degree(ugraph);
1.188 +
1.189 + for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
1.190 + degree[n] = countIncEdges(ugraph, n);
1.191 + }
1.192 +
1.193 + typename UGraph::template EdgeMap<bool> processed(ugraph);
1.194 + IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
1.195 +
1.196 + std::vector<typename UGraph::Edge> edges;
1.197 + for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
1.198 + edges.push_back(e);
1.199 + }
1.200 +
1.201 + for (int i = 0; i < int(edges.size()); ++i) {
1.202 + typename UGraph::Edge e = edges[i];
1.203 +
1.204 + if (processed[e]) continue;
1.205 + processed[e] = true;
1.206 +
1.207 + typename UGraph::Edge mine = e;
1.208 + int mind = degree[ugraph.source(e)];
1.209 +
1.210 + int face_size = 1;
1.211 +
1.212 + typename UGraph::Edge l = e;
1.213 + e = embedding[ugraph.oppositeEdge(e)];
1.214 + while (l != e) {
1.215 + processed[e] = true;
1.216 +
1.217 + ++face_size;
1.218 +
1.219 + if (degree[ugraph.source(e)] < mind) {
1.220 + mine = e;
1.221 + mind = degree[ugraph.source(e)];
1.222 + }
1.223 +
1.224 + e = embedding[ugraph.oppositeEdge(e)];
1.225 + }
1.226 +
1.227 + if (face_size < 4) {
1.228 + continue;
1.229 + }
1.230 +
1.231 + typename UGraph::Node s = ugraph.source(mine);
1.232 + for (typename UGraph::OutEdgeIt e(ugraph, s); e != INVALID; ++e) {
1.233 + visited.set(ugraph.target(e), true);
1.234 + }
1.235 +
1.236 + typename UGraph::Edge oppe = INVALID;
1.237 +
1.238 + e = embedding[ugraph.oppositeEdge(mine)];
1.239 + e = embedding[ugraph.oppositeEdge(e)];
1.240 + while (ugraph.target(e) != s) {
1.241 + if (visited[ugraph.source(e)]) {
1.242 + oppe = e;
1.243 + break;
1.244 + }
1.245 + e = embedding[ugraph.oppositeEdge(e)];
1.246 + }
1.247 + visited.setAll(false);
1.248 +
1.249 + if (oppe == INVALID) {
1.250 +
1.251 + e = embedding[ugraph.oppositeEdge(mine)];
1.252 + typename UGraph::Edge pn = mine, p = e;
1.253 +
1.254 + e = embedding[ugraph.oppositeEdge(e)];
1.255 + while (ugraph.target(e) != s) {
1.256 + typename UGraph::Edge n =
1.257 + ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
1.258 +
1.259 + embedding[n] = pn;
1.260 + embedding[ugraph.oppositeEdge(n)] = e;
1.261 + embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
1.262 +
1.263 + pn = n;
1.264 +
1.265 + p = e;
1.266 + e = embedding[ugraph.oppositeEdge(e)];
1.267 + }
1.268 +
1.269 + embedding[ugraph.oppositeEdge(e)] = pn;
1.270 +
1.271 + } else {
1.272 +
1.273 + mine = embedding[ugraph.oppositeEdge(mine)];
1.274 + s = ugraph.source(mine);
1.275 + oppe = embedding[ugraph.oppositeEdge(oppe)];
1.276 + typename UGraph::Node t = ugraph.source(oppe);
1.277 +
1.278 + typename UGraph::Edge ce = ugraph.direct(ugraph.addEdge(s, t), true);
1.279 + embedding[ce] = mine;
1.280 + embedding[ugraph.oppositeEdge(ce)] = oppe;
1.281 +
1.282 + typename UGraph::Edge pn = ce, p = oppe;
1.283 + e = embedding[ugraph.oppositeEdge(oppe)];
1.284 + while (ugraph.target(e) != s) {
1.285 + typename UGraph::Edge n =
1.286 + ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
1.287 +
1.288 + embedding[n] = pn;
1.289 + embedding[ugraph.oppositeEdge(n)] = e;
1.290 + embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
1.291 +
1.292 + pn = n;
1.293 +
1.294 + p = e;
1.295 + e = embedding[ugraph.oppositeEdge(e)];
1.296 +
1.297 + }
1.298 + embedding[ugraph.oppositeEdge(e)] = pn;
1.299 +
1.300 + pn = ugraph.oppositeEdge(ce), p = mine;
1.301 + e = embedding[ugraph.oppositeEdge(mine)];
1.302 + while (ugraph.target(e) != t) {
1.303 + typename UGraph::Edge n =
1.304 + ugraph.direct(ugraph.addEdge(t, ugraph.source(e)), true);
1.305 +
1.306 + embedding[n] = pn;
1.307 + embedding[ugraph.oppositeEdge(n)] = e;
1.308 + embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
1.309 +
1.310 + pn = n;
1.311 +
1.312 + p = e;
1.313 + e = embedding[ugraph.oppositeEdge(e)];
1.314 +
1.315 + }
1.316 + embedding[ugraph.oppositeEdge(e)] = pn;
1.317 + }
1.318 + }
1.319 + }
1.320 +
1.321 + }
1.322 +
1.323 + /// \brief Schnyder's planar drawing algorithms
1.324 + ///
1.325 + /// The planar drawing algorithm calculates location for each node
1.326 + /// in the plane, which coordinates satisfies that if each edge is
1.327 + /// represented with a straight line then the edges will not
1.328 + /// intersect each other.
1.329 + ///
1.330 + /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
1.331 + /// ie. each node will be located in the \c [0,n-2]x[0,n-2] square.
1.332 + /// The time complexity of the algorithm is O(n).
1.333 + template <typename UGraph>
1.334 + class PlanarDrawing {
1.335 + public:
1.336 +
1.337 + UGRAPH_TYPEDEFS(typename UGraph);
1.338 +
1.339 + /// \brief The point type for store coordinates
1.340 + typedef dim2::Point<int> Point;
1.341 + /// \brief The map type for store coordinates
1.342 + typedef typename UGraph::template NodeMap<Point> PointMap;
1.343 +
1.344 +
1.345 + /// \brief Constructor
1.346 + ///
1.347 + /// Constructor
1.348 + /// \pre The ugraph should be simple, ie. loop and parallel edge free.
1.349 + PlanarDrawing(const UGraph& ugraph)
1.350 + : _ugraph(ugraph), _point_map(ugraph) {}
1.351 +
1.352 + private:
1.353 +
1.354 + template <typename AuxUGraph, typename AuxEmbeddingMap>
1.355 + void drawing(const AuxUGraph& ugraph,
1.356 + const AuxEmbeddingMap& next,
1.357 + PointMap& point_map) {
1.358 + UGRAPH_TYPEDEFS(typename AuxUGraph);
1.359 +
1.360 + typename AuxUGraph::template EdgeMap<Edge> prev(ugraph);
1.361 +
1.362 + for (NodeIt n(ugraph); n != INVALID; ++n) {
1.363 + Edge e = OutEdgeIt(ugraph, n);
1.364 +
1.365 + Edge p = e, l = e;
1.366 +
1.367 + e = next[e];
1.368 + while (e != l) {
1.369 + prev[e] = p;
1.370 + p = e;
1.371 + e = next[e];
1.372 + }
1.373 + prev[e] = p;
1.374 + }
1.375 +
1.376 + Node anode, bnode, cnode;
1.377 +
1.378 + {
1.379 + Edge e = EdgeIt(ugraph);
1.380 + anode = ugraph.source(e);
1.381 + bnode = ugraph.target(e);
1.382 + cnode = ugraph.target(next[ugraph.oppositeEdge(e)]);
1.383 + }
1.384 +
1.385 + IterableBoolMap<AuxUGraph, Node> proper(ugraph, false);
1.386 + typename AuxUGraph::template NodeMap<int> conn(ugraph, -1);
1.387 +
1.388 + conn[anode] = conn[bnode] = -2;
1.389 + {
1.390 + for (OutEdgeIt e(ugraph, anode); e != INVALID; ++e) {
1.391 + Node m = ugraph.target(e);
1.392 + if (conn[m] == -1) {
1.393 + conn[m] = 1;
1.394 + }
1.395 + }
1.396 + conn[cnode] = 2;
1.397 +
1.398 + for (OutEdgeIt e(ugraph, bnode); e != INVALID; ++e) {
1.399 + Node m = ugraph.target(e);
1.400 + if (conn[m] == -1) {
1.401 + conn[m] = 1;
1.402 + } else if (conn[m] != -2) {
1.403 + conn[m] += 1;
1.404 + Edge pe = ugraph.oppositeEdge(e);
1.405 + if (conn[ugraph.target(next[pe])] == -2) {
1.406 + conn[m] -= 1;
1.407 + }
1.408 + if (conn[ugraph.target(prev[pe])] == -2) {
1.409 + conn[m] -= 1;
1.410 + }
1.411 +
1.412 + proper.set(m, conn[m] == 1);
1.413 + }
1.414 + }
1.415 + }
1.416 +
1.417 +
1.418 + typename AuxUGraph::template EdgeMap<int> angle(ugraph, -1);
1.419 +
1.420 + while (proper.trueNum() != 0) {
1.421 + Node n = typename IterableBoolMap<AuxUGraph, Node>::TrueIt(proper);
1.422 + proper.set(n, false);
1.423 + conn[n] = -2;
1.424 +
1.425 + for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
1.426 + Node m = ugraph.target(e);
1.427 + if (conn[m] == -1) {
1.428 + conn[m] = 1;
1.429 + } else if (conn[m] != -2) {
1.430 + conn[m] += 1;
1.431 + Edge pe = ugraph.oppositeEdge(e);
1.432 + if (conn[ugraph.target(next[pe])] == -2) {
1.433 + conn[m] -= 1;
1.434 + }
1.435 + if (conn[ugraph.target(prev[pe])] == -2) {
1.436 + conn[m] -= 1;
1.437 + }
1.438 +
1.439 + proper.set(m, conn[m] == 1);
1.440 + }
1.441 + }
1.442 +
1.443 + {
1.444 + Edge e = OutEdgeIt(ugraph, n);
1.445 + Edge p = e, l = e;
1.446 +
1.447 + e = next[e];
1.448 + while (e != l) {
1.449 +
1.450 + if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
1.451 + Edge f = e;
1.452 + angle[f] = 0;
1.453 + f = next[ugraph.oppositeEdge(f)];
1.454 + angle[f] = 1;
1.455 + f = next[ugraph.oppositeEdge(f)];
1.456 + angle[f] = 2;
1.457 + }
1.458 +
1.459 + p = e;
1.460 + e = next[e];
1.461 + }
1.462 +
1.463 + if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
1.464 + Edge f = e;
1.465 + angle[f] = 0;
1.466 + f = next[ugraph.oppositeEdge(f)];
1.467 + angle[f] = 1;
1.468 + f = next[ugraph.oppositeEdge(f)];
1.469 + angle[f] = 2;
1.470 + }
1.471 + }
1.472 + }
1.473 +
1.474 + typename AuxUGraph::template NodeMap<Node> apred(ugraph, INVALID);
1.475 + typename AuxUGraph::template NodeMap<Node> bpred(ugraph, INVALID);
1.476 + typename AuxUGraph::template NodeMap<Node> cpred(ugraph, INVALID);
1.477 +
1.478 + typename AuxUGraph::template NodeMap<int> apredid(ugraph, -1);
1.479 + typename AuxUGraph::template NodeMap<int> bpredid(ugraph, -1);
1.480 + typename AuxUGraph::template NodeMap<int> cpredid(ugraph, -1);
1.481 +
1.482 + for (EdgeIt e(ugraph); e != INVALID; ++e) {
1.483 + if (angle[e] == angle[next[e]]) {
1.484 + switch (angle[e]) {
1.485 + case 2:
1.486 + apred[ugraph.target(e)] = ugraph.source(e);
1.487 + apredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
1.488 + break;
1.489 + case 1:
1.490 + bpred[ugraph.target(e)] = ugraph.source(e);
1.491 + bpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
1.492 + break;
1.493 + case 0:
1.494 + cpred[ugraph.target(e)] = ugraph.source(e);
1.495 + cpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
1.496 + break;
1.497 + }
1.498 + }
1.499 + }
1.500 +
1.501 + cpred[anode] = INVALID;
1.502 + cpred[bnode] = INVALID;
1.503 +
1.504 + std::vector<Node> aorder, border, corder;
1.505 +
1.506 + {
1.507 + typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
1.508 + std::vector<Node> st;
1.509 + for (NodeIt n(ugraph); n != INVALID; ++n) {
1.510 + if (!processed[n] && n != bnode && n != cnode) {
1.511 + st.push_back(n);
1.512 + processed[n] = true;
1.513 + Node m = apred[n];
1.514 + while (m != INVALID && !processed[m]) {
1.515 + st.push_back(m);
1.516 + processed[m] = true;
1.517 + m = apred[m];
1.518 + }
1.519 + while (!st.empty()) {
1.520 + aorder.push_back(st.back());
1.521 + st.pop_back();
1.522 + }
1.523 + }
1.524 + }
1.525 + }
1.526 +
1.527 + {
1.528 + typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
1.529 + std::vector<Node> st;
1.530 + for (NodeIt n(ugraph); n != INVALID; ++n) {
1.531 + if (!processed[n] && n != cnode && n != anode) {
1.532 + st.push_back(n);
1.533 + processed[n] = true;
1.534 + Node m = bpred[n];
1.535 + while (m != INVALID && !processed[m]) {
1.536 + st.push_back(m);
1.537 + processed[m] = true;
1.538 + m = bpred[m];
1.539 + }
1.540 + while (!st.empty()) {
1.541 + border.push_back(st.back());
1.542 + st.pop_back();
1.543 + }
1.544 + }
1.545 + }
1.546 + }
1.547 +
1.548 + {
1.549 + typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
1.550 + std::vector<Node> st;
1.551 + for (NodeIt n(ugraph); n != INVALID; ++n) {
1.552 + if (!processed[n] && n != anode && n != bnode) {
1.553 + st.push_back(n);
1.554 + processed[n] = true;
1.555 + Node m = cpred[n];
1.556 + while (m != INVALID && !processed[m]) {
1.557 + st.push_back(m);
1.558 + processed[m] = true;
1.559 + m = cpred[m];
1.560 + }
1.561 + while (!st.empty()) {
1.562 + corder.push_back(st.back());
1.563 + st.pop_back();
1.564 + }
1.565 + }
1.566 + }
1.567 + }
1.568 +
1.569 + typename AuxUGraph::template NodeMap<int> atree(ugraph, 0);
1.570 + for (int i = aorder.size() - 1; i >= 0; --i) {
1.571 + Node n = aorder[i];
1.572 + atree[n] = 1;
1.573 + for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
1.574 + if (apred[ugraph.target(e)] == n) {
1.575 + atree[n] += atree[ugraph.target(e)];
1.576 + }
1.577 + }
1.578 + }
1.579 +
1.580 + typename AuxUGraph::template NodeMap<int> btree(ugraph, 0);
1.581 + for (int i = border.size() - 1; i >= 0; --i) {
1.582 + Node n = border[i];
1.583 + btree[n] = 1;
1.584 + for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
1.585 + if (bpred[ugraph.target(e)] == n) {
1.586 + btree[n] += btree[ugraph.target(e)];
1.587 + }
1.588 + }
1.589 + }
1.590 +
1.591 + typename AuxUGraph::template NodeMap<int> apath(ugraph, 0);
1.592 + apath[bnode] = apath[cnode] = 1;
1.593 + typename AuxUGraph::template NodeMap<int> apath_btree(ugraph, 0);
1.594 + apath_btree[bnode] = btree[bnode];
1.595 + for (int i = 1; i < int(aorder.size()); ++i) {
1.596 + Node n = aorder[i];
1.597 + apath[n] = apath[apred[n]] + 1;
1.598 + apath_btree[n] = btree[n] + apath_btree[apred[n]];
1.599 + }
1.600 +
1.601 + typename AuxUGraph::template NodeMap<int> bpath_atree(ugraph, 0);
1.602 + bpath_atree[anode] = atree[anode];
1.603 + for (int i = 1; i < int(border.size()); ++i) {
1.604 + Node n = border[i];
1.605 + bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
1.606 + }
1.607 +
1.608 + typename AuxUGraph::template NodeMap<int> cpath(ugraph, 0);
1.609 + cpath[anode] = cpath[bnode] = 1;
1.610 + typename AuxUGraph::template NodeMap<int> cpath_atree(ugraph, 0);
1.611 + cpath_atree[anode] = atree[anode];
1.612 + typename AuxUGraph::template NodeMap<int> cpath_btree(ugraph, 0);
1.613 + cpath_btree[bnode] = btree[bnode];
1.614 + for (int i = 1; i < int(corder.size()); ++i) {
1.615 + Node n = corder[i];
1.616 + cpath[n] = cpath[cpred[n]] + 1;
1.617 + cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
1.618 + cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
1.619 + }
1.620 +
1.621 + typename AuxUGraph::template NodeMap<int> third(ugraph);
1.622 + for (NodeIt n(ugraph); n != INVALID; ++n) {
1.623 + point_map[n].x =
1.624 + bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
1.625 + point_map[n].y =
1.626 + cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
1.627 + }
1.628 +
1.629 + }
1.630 +
1.631 + public:
1.632 +
1.633 + /// \brief Calculates the node locations
1.634 + ///
1.635 + /// This function calculates the node locations.
1.636 + bool run() {
1.637 + PlanarEmbedding<UGraph> pe(_ugraph);
1.638 + if (!pe.run()) return false;
1.639 +
1.640 + run(pe);
1.641 + return true;
1.642 + }
1.643 +
1.644 + /// \brief Calculates the node locations according to a
1.645 + /// combinatorical embedding
1.646 + ///
1.647 + /// This function calculates the node locations. The \c embedding
1.648 + /// parameter should contain a valid combinatorical embedding, ie.
1.649 + /// a valid cyclic order of the edges.
1.650 + template <typename EmbeddingMap>
1.651 + void run(const EmbeddingMap& embedding) {
1.652 + typedef SmartUEdgeSet<UGraph> AuxUGraph;
1.653 +
1.654 + if (3 * countNodes(_ugraph) - 6 == countUEdges(_ugraph)) {
1.655 + drawing(_ugraph, embedding, _point_map);
1.656 + return;
1.657 + }
1.658 +
1.659 + AuxUGraph aux_ugraph(_ugraph);
1.660 + typename AuxUGraph::template EdgeMap<typename AuxUGraph::Edge>
1.661 + aux_embedding(aux_ugraph);
1.662 +
1.663 + {
1.664 +
1.665 + typename UGraph::template UEdgeMap<typename AuxUGraph::UEdge>
1.666 + ref(_ugraph);
1.667 +
1.668 + for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
1.669 + ref[e] = aux_ugraph.addEdge(_ugraph.source(e), _ugraph.target(e));
1.670 + }
1.671 +
1.672 + for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
1.673 + Edge ee = embedding[_ugraph.direct(e, true)];
1.674 + aux_embedding[aux_ugraph.direct(ref[e], true)] =
1.675 + aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
1.676 + ee = embedding[_ugraph.direct(e, false)];
1.677 + aux_embedding[aux_ugraph.direct(ref[e], false)] =
1.678 + aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
1.679 + }
1.680 + }
1.681 + _planarity_bits::makeConnected(aux_ugraph, aux_embedding);
1.682 + _planarity_bits::makeBiNodeConnected(aux_ugraph, aux_embedding);
1.683 + _planarity_bits::makeMaxPlanar(aux_ugraph, aux_embedding);
1.684 + drawing(aux_ugraph, aux_embedding, _point_map);
1.685 + }
1.686 +
1.687 + /// \brief The coordinate of the given node
1.688 + ///
1.689 + /// The coordinate of the given node.
1.690 + Point operator[](const Node& node) {
1.691 + return _point_map[node];
1.692 + }
1.693 +
1.694 + /// \brief Returns the grid embedding in a \e NodeMap.
1.695 + ///
1.696 + /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
1.697 + const PointMap& coords() const {
1.698 + return _point_map;
1.699 + }
1.700 +
1.701 + private:
1.702 +
1.703 + const UGraph& _ugraph;
1.704 + PointMap _point_map;
1.705 +
1.706 + };
1.707 +
1.708 }
1.709
1.710 #endif