1 | /* -*- C++ -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2007 |
---|
6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
8 | * |
---|
9 | * Permission to use, modify and distribute this software is granted |
---|
10 | * provided that this copyright notice appears in all copies. For |
---|
11 | * precise terms see the accompanying LICENSE file. |
---|
12 | * |
---|
13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
14 | * express or implied, and with no claim as to its suitability for any |
---|
15 | * purpose. |
---|
16 | * |
---|
17 | */ |
---|
18 | #ifndef LEMON_PLANARITY_H |
---|
19 | #define LEMON_PLANARITY_H |
---|
20 | |
---|
21 | /// \ingroup graph_prop |
---|
22 | /// \file |
---|
23 | /// \brief Planarity checking, embedding |
---|
24 | |
---|
25 | #include <vector> |
---|
26 | #include <list> |
---|
27 | |
---|
28 | #include <lemon/dfs.h> |
---|
29 | #include <lemon/radix_sort.h> |
---|
30 | #include <lemon/maps.h> |
---|
31 | #include <lemon/path.h> |
---|
32 | |
---|
33 | |
---|
34 | namespace lemon { |
---|
35 | |
---|
36 | namespace _planarity_bits { |
---|
37 | |
---|
38 | template <typename UGraph> |
---|
39 | struct PlanarityVisitor : DfsVisitor<UGraph> { |
---|
40 | |
---|
41 | typedef typename UGraph::Node Node; |
---|
42 | typedef typename UGraph::Edge Edge; |
---|
43 | |
---|
44 | typedef typename UGraph::template NodeMap<Edge> PredMap; |
---|
45 | |
---|
46 | typedef typename UGraph::template UEdgeMap<bool> TreeMap; |
---|
47 | |
---|
48 | typedef typename UGraph::template NodeMap<int> OrderMap; |
---|
49 | typedef std::vector<Node> OrderList; |
---|
50 | |
---|
51 | typedef typename UGraph::template NodeMap<int> LowMap; |
---|
52 | typedef typename UGraph::template NodeMap<int> AncestorMap; |
---|
53 | |
---|
54 | PlanarityVisitor(const UGraph& ugraph, |
---|
55 | PredMap& pred_map, TreeMap& tree_map, |
---|
56 | OrderMap& order_map, OrderList& order_list, |
---|
57 | AncestorMap& ancestor_map, LowMap& low_map) |
---|
58 | : _ugraph(ugraph), _pred_map(pred_map), _tree_map(tree_map), |
---|
59 | _order_map(order_map), _order_list(order_list), |
---|
60 | _ancestor_map(ancestor_map), _low_map(low_map) {} |
---|
61 | |
---|
62 | void reach(const Node& node) { |
---|
63 | _order_map[node] = _order_list.size(); |
---|
64 | _low_map[node] = _order_list.size(); |
---|
65 | _ancestor_map[node] = _order_list.size(); |
---|
66 | _order_list.push_back(node); |
---|
67 | } |
---|
68 | |
---|
69 | void discover(const Edge& edge) { |
---|
70 | Node source = _ugraph.source(edge); |
---|
71 | Node target = _ugraph.target(edge); |
---|
72 | |
---|
73 | _tree_map[edge] = true; |
---|
74 | _pred_map[target] = edge; |
---|
75 | } |
---|
76 | |
---|
77 | void examine(const Edge& edge) { |
---|
78 | Node source = _ugraph.source(edge); |
---|
79 | Node target = _ugraph.target(edge); |
---|
80 | |
---|
81 | if (_order_map[target] < _order_map[source] && !_tree_map[edge]) { |
---|
82 | if (_low_map[source] > _order_map[target]) { |
---|
83 | _low_map[source] = _order_map[target]; |
---|
84 | } |
---|
85 | if (_ancestor_map[source] > _order_map[target]) { |
---|
86 | _ancestor_map[source] = _order_map[target]; |
---|
87 | } |
---|
88 | } |
---|
89 | } |
---|
90 | |
---|
91 | void backtrack(const Edge& edge) { |
---|
92 | Node source = _ugraph.source(edge); |
---|
93 | Node target = _ugraph.target(edge); |
---|
94 | |
---|
95 | if (_low_map[source] > _low_map[target]) { |
---|
96 | _low_map[source] = _low_map[target]; |
---|
97 | } |
---|
98 | } |
---|
99 | |
---|
100 | const UGraph& _ugraph; |
---|
101 | PredMap& _pred_map; |
---|
102 | TreeMap& _tree_map; |
---|
103 | OrderMap& _order_map; |
---|
104 | OrderList& _order_list; |
---|
105 | AncestorMap& _ancestor_map; |
---|
106 | LowMap& _low_map; |
---|
107 | }; |
---|
108 | |
---|
109 | template <typename UGraph, bool embedding = true> |
---|
110 | struct NodeDataNode { |
---|
111 | int prev, next; |
---|
112 | int visited; |
---|
113 | typename UGraph::Edge first; |
---|
114 | bool inverted; |
---|
115 | }; |
---|
116 | |
---|
117 | template <typename UGraph> |
---|
118 | struct NodeDataNode<UGraph, false> { |
---|
119 | int prev, next; |
---|
120 | int visited; |
---|
121 | }; |
---|
122 | |
---|
123 | template <typename UGraph> |
---|
124 | struct ChildListNode { |
---|
125 | typedef typename UGraph::Node Node; |
---|
126 | Node first; |
---|
127 | Node prev, next; |
---|
128 | }; |
---|
129 | |
---|
130 | template <typename UGraph> |
---|
131 | struct EdgeListNode { |
---|
132 | typename UGraph::Edge prev, next; |
---|
133 | }; |
---|
134 | |
---|
135 | } |
---|
136 | |
---|
137 | /// \ingroup graph_prop |
---|
138 | /// |
---|
139 | /// \brief Planarity checking of an undirected simple graph |
---|
140 | /// |
---|
141 | /// This class implements the Boyer-Myrvold algorithm for planar |
---|
142 | /// checking of an undirected graph. This class is a simplified |
---|
143 | /// version of the PlanarEmbedding algorithm class, and it does |
---|
144 | /// provide neither embedding nor kuratowski subdivisons. |
---|
145 | template <typename UGraph> |
---|
146 | class PlanarityChecking { |
---|
147 | private: |
---|
148 | |
---|
149 | UGRAPH_TYPEDEFS(typename UGraph) |
---|
150 | |
---|
151 | const UGraph& _ugraph; |
---|
152 | |
---|
153 | private: |
---|
154 | |
---|
155 | typedef typename UGraph::template NodeMap<Edge> PredMap; |
---|
156 | |
---|
157 | typedef typename UGraph::template UEdgeMap<bool> TreeMap; |
---|
158 | |
---|
159 | typedef typename UGraph::template NodeMap<int> OrderMap; |
---|
160 | typedef std::vector<Node> OrderList; |
---|
161 | |
---|
162 | typedef typename UGraph::template NodeMap<int> LowMap; |
---|
163 | typedef typename UGraph::template NodeMap<int> AncestorMap; |
---|
164 | |
---|
165 | typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode; |
---|
166 | typedef std::vector<NodeDataNode> NodeData; |
---|
167 | |
---|
168 | typedef _planarity_bits::ChildListNode<UGraph> ChildListNode; |
---|
169 | typedef typename UGraph::template NodeMap<ChildListNode> ChildLists; |
---|
170 | |
---|
171 | typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots; |
---|
172 | |
---|
173 | typedef typename UGraph::template NodeMap<bool> EmbedEdge; |
---|
174 | |
---|
175 | public: |
---|
176 | |
---|
177 | /// \brief Constructor |
---|
178 | /// |
---|
179 | /// \warining The graph should be simple, i.e. parallel and loop edge |
---|
180 | /// free. |
---|
181 | PlanarityChecking(const UGraph& ugraph) : _ugraph(ugraph) {} |
---|
182 | |
---|
183 | /// \brief Runs the algorithm. |
---|
184 | /// |
---|
185 | /// Runs the algorithm. |
---|
186 | /// \return %True when the graph is planar. |
---|
187 | bool run() { |
---|
188 | typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor; |
---|
189 | |
---|
190 | PredMap pred_map(_ugraph, INVALID); |
---|
191 | TreeMap tree_map(_ugraph, false); |
---|
192 | |
---|
193 | OrderMap order_map(_ugraph, -1); |
---|
194 | OrderList order_list; |
---|
195 | |
---|
196 | AncestorMap ancestor_map(_ugraph, -1); |
---|
197 | LowMap low_map(_ugraph, -1); |
---|
198 | |
---|
199 | Visitor visitor(_ugraph, pred_map, tree_map, |
---|
200 | order_map, order_list, ancestor_map, low_map); |
---|
201 | DfsVisit<UGraph, Visitor> visit(_ugraph, visitor); |
---|
202 | visit.run(); |
---|
203 | |
---|
204 | ChildLists child_lists(_ugraph); |
---|
205 | createChildLists(tree_map, order_map, low_map, child_lists); |
---|
206 | |
---|
207 | NodeData node_data(2 * order_list.size()); |
---|
208 | |
---|
209 | EmbedEdge embed_edge(_ugraph, false); |
---|
210 | |
---|
211 | MergeRoots merge_roots(_ugraph); |
---|
212 | |
---|
213 | for (int i = order_list.size() - 1; i >= 0; --i) { |
---|
214 | |
---|
215 | Node node = order_list[i]; |
---|
216 | |
---|
217 | Node source = node; |
---|
218 | for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
---|
219 | Node target = _ugraph.target(e); |
---|
220 | |
---|
221 | if (order_map[source] < order_map[target] && tree_map[e]) { |
---|
222 | initFace(target, node_data, order_map, order_list); |
---|
223 | } |
---|
224 | } |
---|
225 | |
---|
226 | for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
---|
227 | Node target = _ugraph.target(e); |
---|
228 | |
---|
229 | if (order_map[source] < order_map[target] && !tree_map[e]) { |
---|
230 | embed_edge[target] = true; |
---|
231 | walkUp(target, source, i, pred_map, low_map, |
---|
232 | order_map, order_list, node_data, merge_roots); |
---|
233 | } |
---|
234 | } |
---|
235 | |
---|
236 | for (typename MergeRoots::Value::iterator it = |
---|
237 | merge_roots[node].begin(); it != merge_roots[node].end(); ++it) { |
---|
238 | int rn = *it; |
---|
239 | walkDown(rn, i, node_data, order_list, child_lists, |
---|
240 | ancestor_map, low_map, embed_edge, merge_roots); |
---|
241 | } |
---|
242 | merge_roots[node].clear(); |
---|
243 | |
---|
244 | for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
---|
245 | Node target = _ugraph.target(e); |
---|
246 | |
---|
247 | if (order_map[source] < order_map[target] && !tree_map[e]) { |
---|
248 | if (embed_edge[target]) { |
---|
249 | return false; |
---|
250 | } |
---|
251 | } |
---|
252 | } |
---|
253 | } |
---|
254 | |
---|
255 | return true; |
---|
256 | } |
---|
257 | |
---|
258 | private: |
---|
259 | |
---|
260 | void createChildLists(const TreeMap& tree_map, const OrderMap& order_map, |
---|
261 | const LowMap& low_map, ChildLists& child_lists) { |
---|
262 | |
---|
263 | for (NodeIt n(_ugraph); n != INVALID; ++n) { |
---|
264 | Node source = n; |
---|
265 | |
---|
266 | std::vector<Node> targets; |
---|
267 | for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) { |
---|
268 | Node target = _ugraph.target(e); |
---|
269 | |
---|
270 | if (order_map[source] < order_map[target] && tree_map[e]) { |
---|
271 | targets.push_back(target); |
---|
272 | } |
---|
273 | } |
---|
274 | |
---|
275 | if (targets.size() == 0) { |
---|
276 | child_lists[source].first = INVALID; |
---|
277 | } else if (targets.size() == 1) { |
---|
278 | child_lists[source].first = targets[0]; |
---|
279 | child_lists[targets[0]].prev = INVALID; |
---|
280 | child_lists[targets[0]].next = INVALID; |
---|
281 | } else { |
---|
282 | radixSort(targets.begin(), targets.end(), mapFunctor(low_map)); |
---|
283 | for (int i = 1; i < int(targets.size()); ++i) { |
---|
284 | child_lists[targets[i]].prev = targets[i - 1]; |
---|
285 | child_lists[targets[i - 1]].next = targets[i]; |
---|
286 | } |
---|
287 | child_lists[targets.back()].next = INVALID; |
---|
288 | child_lists[targets.front()].prev = INVALID; |
---|
289 | child_lists[source].first = targets.front(); |
---|
290 | } |
---|
291 | } |
---|
292 | } |
---|
293 | |
---|
294 | void walkUp(const Node& node, Node root, int rorder, |
---|
295 | const PredMap& pred_map, const LowMap& low_map, |
---|
296 | const OrderMap& order_map, const OrderList& order_list, |
---|
297 | NodeData& node_data, MergeRoots& merge_roots) { |
---|
298 | |
---|
299 | int na, nb; |
---|
300 | bool da, db; |
---|
301 | |
---|
302 | na = nb = order_map[node]; |
---|
303 | da = true; db = false; |
---|
304 | |
---|
305 | while (true) { |
---|
306 | |
---|
307 | if (node_data[na].visited == rorder) break; |
---|
308 | if (node_data[nb].visited == rorder) break; |
---|
309 | |
---|
310 | node_data[na].visited = rorder; |
---|
311 | node_data[nb].visited = rorder; |
---|
312 | |
---|
313 | int rn = -1; |
---|
314 | |
---|
315 | if (na >= int(order_list.size())) { |
---|
316 | rn = na; |
---|
317 | } else if (nb >= int(order_list.size())) { |
---|
318 | rn = nb; |
---|
319 | } |
---|
320 | |
---|
321 | if (rn == -1) { |
---|
322 | int nn; |
---|
323 | |
---|
324 | nn = da ? node_data[na].prev : node_data[na].next; |
---|
325 | da = node_data[nn].prev != na; |
---|
326 | na = nn; |
---|
327 | |
---|
328 | nn = db ? node_data[nb].prev : node_data[nb].next; |
---|
329 | db = node_data[nn].prev != nb; |
---|
330 | nb = nn; |
---|
331 | |
---|
332 | } else { |
---|
333 | |
---|
334 | Node rep = order_list[rn - order_list.size()]; |
---|
335 | Node parent = _ugraph.source(pred_map[rep]); |
---|
336 | |
---|
337 | if (low_map[rep] < rorder) { |
---|
338 | merge_roots[parent].push_back(rn); |
---|
339 | } else { |
---|
340 | merge_roots[parent].push_front(rn); |
---|
341 | } |
---|
342 | |
---|
343 | if (parent != root) { |
---|
344 | na = nb = order_map[parent]; |
---|
345 | da = true; db = false; |
---|
346 | } else { |
---|
347 | break; |
---|
348 | } |
---|
349 | } |
---|
350 | } |
---|
351 | } |
---|
352 | |
---|
353 | void walkDown(int rn, int rorder, NodeData& node_data, |
---|
354 | OrderList& order_list, ChildLists& child_lists, |
---|
355 | AncestorMap& ancestor_map, LowMap& low_map, |
---|
356 | EmbedEdge& embed_edge, MergeRoots& merge_roots) { |
---|
357 | |
---|
358 | std::vector<std::pair<int, bool> > merge_stack; |
---|
359 | |
---|
360 | for (int di = 0; di < 2; ++di) { |
---|
361 | bool rd = di == 0; |
---|
362 | int pn = rn; |
---|
363 | int n = rd ? node_data[rn].next : node_data[rn].prev; |
---|
364 | |
---|
365 | while (n != rn) { |
---|
366 | |
---|
367 | Node node = order_list[n]; |
---|
368 | |
---|
369 | if (embed_edge[node]) { |
---|
370 | |
---|
371 | // Merging components on the critical path |
---|
372 | while (!merge_stack.empty()) { |
---|
373 | |
---|
374 | // Component root |
---|
375 | int cn = merge_stack.back().first; |
---|
376 | bool cd = merge_stack.back().second; |
---|
377 | merge_stack.pop_back(); |
---|
378 | |
---|
379 | // Parent of component |
---|
380 | int dn = merge_stack.back().first; |
---|
381 | bool dd = merge_stack.back().second; |
---|
382 | merge_stack.pop_back(); |
---|
383 | |
---|
384 | Node parent = order_list[dn]; |
---|
385 | |
---|
386 | // Erasing from merge_roots |
---|
387 | merge_roots[parent].pop_front(); |
---|
388 | |
---|
389 | Node child = order_list[cn - order_list.size()]; |
---|
390 | |
---|
391 | // Erasing from child_lists |
---|
392 | if (child_lists[child].prev != INVALID) { |
---|
393 | child_lists[child_lists[child].prev].next = |
---|
394 | child_lists[child].next; |
---|
395 | } else { |
---|
396 | child_lists[parent].first = child_lists[child].next; |
---|
397 | } |
---|
398 | |
---|
399 | if (child_lists[child].next != INVALID) { |
---|
400 | child_lists[child_lists[child].next].prev = |
---|
401 | child_lists[child].prev; |
---|
402 | } |
---|
403 | |
---|
404 | // Merging external faces |
---|
405 | { |
---|
406 | int en = cn; |
---|
407 | cn = cd ? node_data[cn].prev : node_data[cn].next; |
---|
408 | cd = node_data[cn].next == en; |
---|
409 | |
---|
410 | } |
---|
411 | |
---|
412 | if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn; |
---|
413 | if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn; |
---|
414 | |
---|
415 | } |
---|
416 | |
---|
417 | bool d = pn == node_data[n].prev; |
---|
418 | |
---|
419 | if (node_data[n].prev == node_data[n].next && |
---|
420 | node_data[n].inverted) { |
---|
421 | d = !d; |
---|
422 | } |
---|
423 | |
---|
424 | // Embedding edge into external face |
---|
425 | if (rd) node_data[rn].next = n; else node_data[rn].prev = n; |
---|
426 | if (d) node_data[n].prev = rn; else node_data[n].next = rn; |
---|
427 | pn = rn; |
---|
428 | |
---|
429 | embed_edge[order_list[n]] = false; |
---|
430 | } |
---|
431 | |
---|
432 | if (!merge_roots[node].empty()) { |
---|
433 | |
---|
434 | bool d = pn == node_data[n].prev; |
---|
435 | |
---|
436 | merge_stack.push_back(std::make_pair(n, d)); |
---|
437 | |
---|
438 | int rn = merge_roots[node].front(); |
---|
439 | |
---|
440 | int xn = node_data[rn].next; |
---|
441 | Node xnode = order_list[xn]; |
---|
442 | |
---|
443 | int yn = node_data[rn].prev; |
---|
444 | Node ynode = order_list[yn]; |
---|
445 | |
---|
446 | bool rd; |
---|
447 | if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) { |
---|
448 | rd = true; |
---|
449 | } else if (!external(ynode, rorder, child_lists, |
---|
450 | ancestor_map, low_map)) { |
---|
451 | rd = false; |
---|
452 | } else if (pertinent(xnode, embed_edge, merge_roots)) { |
---|
453 | rd = true; |
---|
454 | } else { |
---|
455 | rd = false; |
---|
456 | } |
---|
457 | |
---|
458 | merge_stack.push_back(std::make_pair(rn, rd)); |
---|
459 | |
---|
460 | pn = rn; |
---|
461 | n = rd ? xn : yn; |
---|
462 | |
---|
463 | } else if (!external(node, rorder, child_lists, |
---|
464 | ancestor_map, low_map)) { |
---|
465 | int nn = (node_data[n].next != pn ? |
---|
466 | node_data[n].next : node_data[n].prev); |
---|
467 | |
---|
468 | bool nd = n == node_data[nn].prev; |
---|
469 | |
---|
470 | if (nd) node_data[nn].prev = pn; |
---|
471 | else node_data[nn].next = pn; |
---|
472 | |
---|
473 | if (n == node_data[pn].prev) node_data[pn].prev = nn; |
---|
474 | else node_data[pn].next = nn; |
---|
475 | |
---|
476 | node_data[nn].inverted = |
---|
477 | (node_data[nn].prev == node_data[nn].next && nd != rd); |
---|
478 | |
---|
479 | n = nn; |
---|
480 | } |
---|
481 | else break; |
---|
482 | |
---|
483 | } |
---|
484 | |
---|
485 | if (!merge_stack.empty() || n == rn) { |
---|
486 | break; |
---|
487 | } |
---|
488 | } |
---|
489 | } |
---|
490 | |
---|
491 | void initFace(const Node& node, NodeData& node_data, |
---|
492 | const OrderMap& order_map, const OrderList& order_list) { |
---|
493 | int n = order_map[node]; |
---|
494 | int rn = n + order_list.size(); |
---|
495 | |
---|
496 | node_data[n].next = node_data[n].prev = rn; |
---|
497 | node_data[rn].next = node_data[rn].prev = n; |
---|
498 | |
---|
499 | node_data[n].visited = order_list.size(); |
---|
500 | node_data[rn].visited = order_list.size(); |
---|
501 | |
---|
502 | } |
---|
503 | |
---|
504 | bool external(const Node& node, int rorder, |
---|
505 | ChildLists& child_lists, AncestorMap& ancestor_map, |
---|
506 | LowMap& low_map) { |
---|
507 | Node child = child_lists[node].first; |
---|
508 | |
---|
509 | if (child != INVALID) { |
---|
510 | if (low_map[child] < rorder) return true; |
---|
511 | } |
---|
512 | |
---|
513 | if (ancestor_map[node] < rorder) return true; |
---|
514 | |
---|
515 | return false; |
---|
516 | } |
---|
517 | |
---|
518 | bool pertinent(const Node& node, const EmbedEdge& embed_edge, |
---|
519 | const MergeRoots& merge_roots) { |
---|
520 | return !merge_roots[node].empty() || embed_edge[node]; |
---|
521 | } |
---|
522 | |
---|
523 | }; |
---|
524 | |
---|
525 | /// \ingroup graph_prop |
---|
526 | /// |
---|
527 | /// \brief Planar embedding of an undirected simple graph |
---|
528 | /// |
---|
529 | /// This class implements the Boyer-Myrvold algorithm for planar |
---|
530 | /// embedding of an undirected graph. The planar embeding is an |
---|
531 | /// ordering of the outgoing edges in each node, which is a possible |
---|
532 | /// configuration to draw the graph in the plane. If there is not |
---|
533 | /// such ordering then the graph contains a \f$ K_5 \f$ (full graph |
---|
534 | /// with 5 nodes) or an \f$ K_{3,3} \f$ (complete bipartite graph on |
---|
535 | /// 3 ANode and 3 BNode) subdivision. |
---|
536 | /// |
---|
537 | /// The current implementation calculates an embedding or an |
---|
538 | /// Kuratowski subdivision if the graph is not planar. The running |
---|
539 | /// time of the algorithm is \f$ O(n) \f$. |
---|
540 | template <typename UGraph> |
---|
541 | class PlanarEmbedding { |
---|
542 | private: |
---|
543 | |
---|
544 | UGRAPH_TYPEDEFS(typename UGraph) |
---|
545 | |
---|
546 | const UGraph& _ugraph; |
---|
547 | typename UGraph::template EdgeMap<Edge> _embedding; |
---|
548 | |
---|
549 | typename UGraph::template UEdgeMap<bool> _kuratowski; |
---|
550 | |
---|
551 | private: |
---|
552 | |
---|
553 | typedef typename UGraph::template NodeMap<Edge> PredMap; |
---|
554 | |
---|
555 | typedef typename UGraph::template UEdgeMap<bool> TreeMap; |
---|
556 | |
---|
557 | typedef typename UGraph::template NodeMap<int> OrderMap; |
---|
558 | typedef std::vector<Node> OrderList; |
---|
559 | |
---|
560 | typedef typename UGraph::template NodeMap<int> LowMap; |
---|
561 | typedef typename UGraph::template NodeMap<int> AncestorMap; |
---|
562 | |
---|
563 | typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode; |
---|
564 | typedef std::vector<NodeDataNode> NodeData; |
---|
565 | |
---|
566 | typedef _planarity_bits::ChildListNode<UGraph> ChildListNode; |
---|
567 | typedef typename UGraph::template NodeMap<ChildListNode> ChildLists; |
---|
568 | |
---|
569 | typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots; |
---|
570 | |
---|
571 | typedef typename UGraph::template NodeMap<Edge> EmbedEdge; |
---|
572 | |
---|
573 | typedef _planarity_bits::EdgeListNode<UGraph> EdgeListNode; |
---|
574 | typedef typename UGraph::template EdgeMap<EdgeListNode> EdgeLists; |
---|
575 | |
---|
576 | typedef typename UGraph::template NodeMap<bool> FlipMap; |
---|
577 | |
---|
578 | typedef typename UGraph::template NodeMap<int> TypeMap; |
---|
579 | |
---|
580 | enum IsolatorNodeType { |
---|
581 | HIGHX = 6, LOWX = 7, |
---|
582 | HIGHY = 8, LOWY = 9, |
---|
583 | ROOT = 10, PERTINENT = 11, |
---|
584 | INTERNAL = 12 |
---|
585 | }; |
---|
586 | |
---|
587 | public: |
---|
588 | |
---|
589 | /// \brief Constructor |
---|
590 | /// |
---|
591 | /// \warining The graph should be simple, i.e. parallel and loop edge |
---|
592 | /// free. |
---|
593 | PlanarEmbedding(const UGraph& ugraph) |
---|
594 | : _ugraph(ugraph), _embedding(_ugraph), _kuratowski(ugraph, false) {} |
---|
595 | |
---|
596 | /// \brief Runs the algorithm. |
---|
597 | /// |
---|
598 | /// Runs the algorithm. |
---|
599 | /// \param kuratowski If the parameter is false, then the |
---|
600 | /// algorithm does not calculate the isolate Kuratowski |
---|
601 | /// subdivisions. |
---|
602 | ///\return %True when the graph is planar. |
---|
603 | bool run(bool kuratowski = true) { |
---|
604 | typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor; |
---|
605 | |
---|
606 | PredMap pred_map(_ugraph, INVALID); |
---|
607 | TreeMap tree_map(_ugraph, false); |
---|
608 | |
---|
609 | OrderMap order_map(_ugraph, -1); |
---|
610 | OrderList order_list; |
---|
611 | |
---|
612 | AncestorMap ancestor_map(_ugraph, -1); |
---|
613 | LowMap low_map(_ugraph, -1); |
---|
614 | |
---|
615 | Visitor visitor(_ugraph, pred_map, tree_map, |
---|
616 | order_map, order_list, ancestor_map, low_map); |
---|
617 | DfsVisit<UGraph, Visitor> visit(_ugraph, visitor); |
---|
618 | visit.run(); |
---|
619 | |
---|
620 | ChildLists child_lists(_ugraph); |
---|
621 | createChildLists(tree_map, order_map, low_map, child_lists); |
---|
622 | |
---|
623 | NodeData node_data(2 * order_list.size()); |
---|
624 | |
---|
625 | EmbedEdge embed_edge(_ugraph, INVALID); |
---|
626 | |
---|
627 | MergeRoots merge_roots(_ugraph); |
---|
628 | |
---|
629 | EdgeLists edge_lists(_ugraph); |
---|
630 | |
---|
631 | FlipMap flip_map(_ugraph, false); |
---|
632 | |
---|
633 | for (int i = order_list.size() - 1; i >= 0; --i) { |
---|
634 | |
---|
635 | Node node = order_list[i]; |
---|
636 | |
---|
637 | node_data[i].first = INVALID; |
---|
638 | |
---|
639 | Node source = node; |
---|
640 | for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
---|
641 | Node target = _ugraph.target(e); |
---|
642 | |
---|
643 | if (order_map[source] < order_map[target] && tree_map[e]) { |
---|
644 | initFace(target, edge_lists, node_data, |
---|
645 | pred_map, order_map, order_list); |
---|
646 | } |
---|
647 | } |
---|
648 | |
---|
649 | for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
---|
650 | Node target = _ugraph.target(e); |
---|
651 | |
---|
652 | if (order_map[source] < order_map[target] && !tree_map[e]) { |
---|
653 | embed_edge[target] = e; |
---|
654 | walkUp(target, source, i, pred_map, low_map, |
---|
655 | order_map, order_list, node_data, merge_roots); |
---|
656 | } |
---|
657 | } |
---|
658 | |
---|
659 | for (typename MergeRoots::Value::iterator it = |
---|
660 | merge_roots[node].begin(); it != merge_roots[node].end(); ++it) { |
---|
661 | int rn = *it; |
---|
662 | walkDown(rn, i, node_data, edge_lists, flip_map, order_list, |
---|
663 | child_lists, ancestor_map, low_map, embed_edge, merge_roots); |
---|
664 | } |
---|
665 | merge_roots[node].clear(); |
---|
666 | |
---|
667 | for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
---|
668 | Node target = _ugraph.target(e); |
---|
669 | |
---|
670 | if (order_map[source] < order_map[target] && !tree_map[e]) { |
---|
671 | if (embed_edge[target] != INVALID) { |
---|
672 | if (kuratowski) { |
---|
673 | isolateKuratowski(e, node_data, edge_lists, flip_map, |
---|
674 | order_map, order_list, pred_map, child_lists, |
---|
675 | ancestor_map, low_map, |
---|
676 | embed_edge, merge_roots); |
---|
677 | } |
---|
678 | return false; |
---|
679 | } |
---|
680 | } |
---|
681 | } |
---|
682 | } |
---|
683 | |
---|
684 | for (int i = 0; i < int(order_list.size()); ++i) { |
---|
685 | |
---|
686 | mergeRemainingFaces(order_list[i], node_data, order_list, order_map, |
---|
687 | child_lists, edge_lists); |
---|
688 | storeEmbedding(order_list[i], node_data, order_map, pred_map, |
---|
689 | edge_lists, flip_map); |
---|
690 | } |
---|
691 | |
---|
692 | return true; |
---|
693 | } |
---|
694 | |
---|
695 | /// \brief Gives back the successor of an edge |
---|
696 | /// |
---|
697 | /// Gives back the successor of an edge. This function makes |
---|
698 | /// possible to query the cyclic order of the outgoing edges from |
---|
699 | /// a node. |
---|
700 | Edge next(const Edge& edge) const { |
---|
701 | return _embedding[edge]; |
---|
702 | } |
---|
703 | |
---|
704 | /// \brief Gives back true when the undirected edge is in the |
---|
705 | /// kuratowski subdivision |
---|
706 | /// |
---|
707 | /// Gives back true when the undirected edge is in the kuratowski |
---|
708 | /// subdivision |
---|
709 | bool kuratowski(const UEdge& uedge) { |
---|
710 | return _kuratowski[uedge]; |
---|
711 | } |
---|
712 | |
---|
713 | private: |
---|
714 | |
---|
715 | void createChildLists(const TreeMap& tree_map, const OrderMap& order_map, |
---|
716 | const LowMap& low_map, ChildLists& child_lists) { |
---|
717 | |
---|
718 | for (NodeIt n(_ugraph); n != INVALID; ++n) { |
---|
719 | Node source = n; |
---|
720 | |
---|
721 | std::vector<Node> targets; |
---|
722 | for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) { |
---|
723 | Node target = _ugraph.target(e); |
---|
724 | |
---|
725 | if (order_map[source] < order_map[target] && tree_map[e]) { |
---|
726 | targets.push_back(target); |
---|
727 | } |
---|
728 | } |
---|
729 | |
---|
730 | if (targets.size() == 0) { |
---|
731 | child_lists[source].first = INVALID; |
---|
732 | } else if (targets.size() == 1) { |
---|
733 | child_lists[source].first = targets[0]; |
---|
734 | child_lists[targets[0]].prev = INVALID; |
---|
735 | child_lists[targets[0]].next = INVALID; |
---|
736 | } else { |
---|
737 | radixSort(targets.begin(), targets.end(), mapFunctor(low_map)); |
---|
738 | for (int i = 1; i < int(targets.size()); ++i) { |
---|
739 | child_lists[targets[i]].prev = targets[i - 1]; |
---|
740 | child_lists[targets[i - 1]].next = targets[i]; |
---|
741 | } |
---|
742 | child_lists[targets.back()].next = INVALID; |
---|
743 | child_lists[targets.front()].prev = INVALID; |
---|
744 | child_lists[source].first = targets.front(); |
---|
745 | } |
---|
746 | } |
---|
747 | } |
---|
748 | |
---|
749 | void walkUp(const Node& node, Node root, int rorder, |
---|
750 | const PredMap& pred_map, const LowMap& low_map, |
---|
751 | const OrderMap& order_map, const OrderList& order_list, |
---|
752 | NodeData& node_data, MergeRoots& merge_roots) { |
---|
753 | |
---|
754 | int na, nb; |
---|
755 | bool da, db; |
---|
756 | |
---|
757 | na = nb = order_map[node]; |
---|
758 | da = true; db = false; |
---|
759 | |
---|
760 | while (true) { |
---|
761 | |
---|
762 | if (node_data[na].visited == rorder) break; |
---|
763 | if (node_data[nb].visited == rorder) break; |
---|
764 | |
---|
765 | node_data[na].visited = rorder; |
---|
766 | node_data[nb].visited = rorder; |
---|
767 | |
---|
768 | int rn = -1; |
---|
769 | |
---|
770 | if (na >= int(order_list.size())) { |
---|
771 | rn = na; |
---|
772 | } else if (nb >= int(order_list.size())) { |
---|
773 | rn = nb; |
---|
774 | } |
---|
775 | |
---|
776 | if (rn == -1) { |
---|
777 | int nn; |
---|
778 | |
---|
779 | nn = da ? node_data[na].prev : node_data[na].next; |
---|
780 | da = node_data[nn].prev != na; |
---|
781 | na = nn; |
---|
782 | |
---|
783 | nn = db ? node_data[nb].prev : node_data[nb].next; |
---|
784 | db = node_data[nn].prev != nb; |
---|
785 | nb = nn; |
---|
786 | |
---|
787 | } else { |
---|
788 | |
---|
789 | Node rep = order_list[rn - order_list.size()]; |
---|
790 | Node parent = _ugraph.source(pred_map[rep]); |
---|
791 | |
---|
792 | if (low_map[rep] < rorder) { |
---|
793 | merge_roots[parent].push_back(rn); |
---|
794 | } else { |
---|
795 | merge_roots[parent].push_front(rn); |
---|
796 | } |
---|
797 | |
---|
798 | if (parent != root) { |
---|
799 | na = nb = order_map[parent]; |
---|
800 | da = true; db = false; |
---|
801 | } else { |
---|
802 | break; |
---|
803 | } |
---|
804 | } |
---|
805 | } |
---|
806 | } |
---|
807 | |
---|
808 | void walkDown(int rn, int rorder, NodeData& node_data, |
---|
809 | EdgeLists& edge_lists, FlipMap& flip_map, |
---|
810 | OrderList& order_list, ChildLists& child_lists, |
---|
811 | AncestorMap& ancestor_map, LowMap& low_map, |
---|
812 | EmbedEdge& embed_edge, MergeRoots& merge_roots) { |
---|
813 | |
---|
814 | std::vector<std::pair<int, bool> > merge_stack; |
---|
815 | |
---|
816 | for (int di = 0; di < 2; ++di) { |
---|
817 | bool rd = di == 0; |
---|
818 | int pn = rn; |
---|
819 | int n = rd ? node_data[rn].next : node_data[rn].prev; |
---|
820 | |
---|
821 | while (n != rn) { |
---|
822 | |
---|
823 | Node node = order_list[n]; |
---|
824 | |
---|
825 | if (embed_edge[node] != INVALID) { |
---|
826 | |
---|
827 | // Merging components on the critical path |
---|
828 | while (!merge_stack.empty()) { |
---|
829 | |
---|
830 | // Component root |
---|
831 | int cn = merge_stack.back().first; |
---|
832 | bool cd = merge_stack.back().second; |
---|
833 | merge_stack.pop_back(); |
---|
834 | |
---|
835 | // Parent of component |
---|
836 | int dn = merge_stack.back().first; |
---|
837 | bool dd = merge_stack.back().second; |
---|
838 | merge_stack.pop_back(); |
---|
839 | |
---|
840 | Node parent = order_list[dn]; |
---|
841 | |
---|
842 | // Erasing from merge_roots |
---|
843 | merge_roots[parent].pop_front(); |
---|
844 | |
---|
845 | Node child = order_list[cn - order_list.size()]; |
---|
846 | |
---|
847 | // Erasing from child_lists |
---|
848 | if (child_lists[child].prev != INVALID) { |
---|
849 | child_lists[child_lists[child].prev].next = |
---|
850 | child_lists[child].next; |
---|
851 | } else { |
---|
852 | child_lists[parent].first = child_lists[child].next; |
---|
853 | } |
---|
854 | |
---|
855 | if (child_lists[child].next != INVALID) { |
---|
856 | child_lists[child_lists[child].next].prev = |
---|
857 | child_lists[child].prev; |
---|
858 | } |
---|
859 | |
---|
860 | // Merging edges + flipping |
---|
861 | Edge de = node_data[dn].first; |
---|
862 | Edge ce = node_data[cn].first; |
---|
863 | |
---|
864 | flip_map[order_list[cn - order_list.size()]] = cd != dd; |
---|
865 | if (cd != dd) { |
---|
866 | std::swap(edge_lists[ce].prev, edge_lists[ce].next); |
---|
867 | ce = edge_lists[ce].prev; |
---|
868 | std::swap(edge_lists[ce].prev, edge_lists[ce].next); |
---|
869 | } |
---|
870 | |
---|
871 | { |
---|
872 | Edge dne = edge_lists[de].next; |
---|
873 | Edge cne = edge_lists[ce].next; |
---|
874 | |
---|
875 | edge_lists[de].next = cne; |
---|
876 | edge_lists[ce].next = dne; |
---|
877 | |
---|
878 | edge_lists[dne].prev = ce; |
---|
879 | edge_lists[cne].prev = de; |
---|
880 | } |
---|
881 | |
---|
882 | if (dd) { |
---|
883 | node_data[dn].first = ce; |
---|
884 | } |
---|
885 | |
---|
886 | // Merging external faces |
---|
887 | { |
---|
888 | int en = cn; |
---|
889 | cn = cd ? node_data[cn].prev : node_data[cn].next; |
---|
890 | cd = node_data[cn].next == en; |
---|
891 | |
---|
892 | if (node_data[cn].prev == node_data[cn].next && |
---|
893 | node_data[cn].inverted) { |
---|
894 | cd = !cd; |
---|
895 | } |
---|
896 | } |
---|
897 | |
---|
898 | if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn; |
---|
899 | if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn; |
---|
900 | |
---|
901 | } |
---|
902 | |
---|
903 | bool d = pn == node_data[n].prev; |
---|
904 | |
---|
905 | if (node_data[n].prev == node_data[n].next && |
---|
906 | node_data[n].inverted) { |
---|
907 | d = !d; |
---|
908 | } |
---|
909 | |
---|
910 | // Add new edge |
---|
911 | { |
---|
912 | Edge edge = embed_edge[node]; |
---|
913 | Edge re = node_data[rn].first; |
---|
914 | |
---|
915 | edge_lists[edge_lists[re].next].prev = edge; |
---|
916 | edge_lists[edge].next = edge_lists[re].next; |
---|
917 | edge_lists[edge].prev = re; |
---|
918 | edge_lists[re].next = edge; |
---|
919 | |
---|
920 | if (!rd) { |
---|
921 | node_data[rn].first = edge; |
---|
922 | } |
---|
923 | |
---|
924 | Edge rev = _ugraph.oppositeEdge(edge); |
---|
925 | Edge e = node_data[n].first; |
---|
926 | |
---|
927 | edge_lists[edge_lists[e].next].prev = rev; |
---|
928 | edge_lists[rev].next = edge_lists[e].next; |
---|
929 | edge_lists[rev].prev = e; |
---|
930 | edge_lists[e].next = rev; |
---|
931 | |
---|
932 | if (d) { |
---|
933 | node_data[n].first = rev; |
---|
934 | } |
---|
935 | |
---|
936 | } |
---|
937 | |
---|
938 | // Embedding edge into external face |
---|
939 | if (rd) node_data[rn].next = n; else node_data[rn].prev = n; |
---|
940 | if (d) node_data[n].prev = rn; else node_data[n].next = rn; |
---|
941 | pn = rn; |
---|
942 | |
---|
943 | embed_edge[order_list[n]] = INVALID; |
---|
944 | } |
---|
945 | |
---|
946 | if (!merge_roots[node].empty()) { |
---|
947 | |
---|
948 | bool d = pn == node_data[n].prev; |
---|
949 | if (node_data[n].prev == node_data[n].next && |
---|
950 | node_data[n].inverted) { |
---|
951 | d = !d; |
---|
952 | } |
---|
953 | |
---|
954 | merge_stack.push_back(std::make_pair(n, d)); |
---|
955 | |
---|
956 | int rn = merge_roots[node].front(); |
---|
957 | |
---|
958 | int xn = node_data[rn].next; |
---|
959 | Node xnode = order_list[xn]; |
---|
960 | |
---|
961 | int yn = node_data[rn].prev; |
---|
962 | Node ynode = order_list[yn]; |
---|
963 | |
---|
964 | bool rd; |
---|
965 | if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) { |
---|
966 | rd = true; |
---|
967 | } else if (!external(ynode, rorder, child_lists, |
---|
968 | ancestor_map, low_map)) { |
---|
969 | rd = false; |
---|
970 | } else if (pertinent(xnode, embed_edge, merge_roots)) { |
---|
971 | rd = true; |
---|
972 | } else { |
---|
973 | rd = false; |
---|
974 | } |
---|
975 | |
---|
976 | merge_stack.push_back(std::make_pair(rn, rd)); |
---|
977 | |
---|
978 | pn = rn; |
---|
979 | n = rd ? xn : yn; |
---|
980 | |
---|
981 | } else if (!external(node, rorder, child_lists, |
---|
982 | ancestor_map, low_map)) { |
---|
983 | int nn = (node_data[n].next != pn ? |
---|
984 | node_data[n].next : node_data[n].prev); |
---|
985 | |
---|
986 | bool nd = n == node_data[nn].prev; |
---|
987 | |
---|
988 | if (nd) node_data[nn].prev = pn; |
---|
989 | else node_data[nn].next = pn; |
---|
990 | |
---|
991 | if (n == node_data[pn].prev) node_data[pn].prev = nn; |
---|
992 | else node_data[pn].next = nn; |
---|
993 | |
---|
994 | node_data[nn].inverted = |
---|
995 | (node_data[nn].prev == node_data[nn].next && nd != rd); |
---|
996 | |
---|
997 | n = nn; |
---|
998 | } |
---|
999 | else break; |
---|
1000 | |
---|
1001 | } |
---|
1002 | |
---|
1003 | if (!merge_stack.empty() || n == rn) { |
---|
1004 | break; |
---|
1005 | } |
---|
1006 | } |
---|
1007 | } |
---|
1008 | |
---|
1009 | void initFace(const Node& node, EdgeLists& edge_lists, |
---|
1010 | NodeData& node_data, const PredMap& pred_map, |
---|
1011 | const OrderMap& order_map, const OrderList& order_list) { |
---|
1012 | int n = order_map[node]; |
---|
1013 | int rn = n + order_list.size(); |
---|
1014 | |
---|
1015 | node_data[n].next = node_data[n].prev = rn; |
---|
1016 | node_data[rn].next = node_data[rn].prev = n; |
---|
1017 | |
---|
1018 | node_data[n].visited = order_list.size(); |
---|
1019 | node_data[rn].visited = order_list.size(); |
---|
1020 | |
---|
1021 | node_data[n].inverted = false; |
---|
1022 | node_data[rn].inverted = false; |
---|
1023 | |
---|
1024 | Edge edge = pred_map[node]; |
---|
1025 | Edge rev = _ugraph.oppositeEdge(edge); |
---|
1026 | |
---|
1027 | node_data[rn].first = edge; |
---|
1028 | node_data[n].first = rev; |
---|
1029 | |
---|
1030 | edge_lists[edge].prev = edge; |
---|
1031 | edge_lists[edge].next = edge; |
---|
1032 | |
---|
1033 | edge_lists[rev].prev = rev; |
---|
1034 | edge_lists[rev].next = rev; |
---|
1035 | |
---|
1036 | } |
---|
1037 | |
---|
1038 | void mergeRemainingFaces(const Node& node, NodeData& node_data, |
---|
1039 | OrderList& order_list, OrderMap& order_map, |
---|
1040 | ChildLists& child_lists, EdgeLists& edge_lists) { |
---|
1041 | while (child_lists[node].first != INVALID) { |
---|
1042 | int dd = order_map[node]; |
---|
1043 | Node child = child_lists[node].first; |
---|
1044 | int cd = order_map[child] + order_list.size(); |
---|
1045 | child_lists[node].first = child_lists[child].next; |
---|
1046 | |
---|
1047 | Edge de = node_data[dd].first; |
---|
1048 | Edge ce = node_data[cd].first; |
---|
1049 | |
---|
1050 | if (de != INVALID) { |
---|
1051 | Edge dne = edge_lists[de].next; |
---|
1052 | Edge cne = edge_lists[ce].next; |
---|
1053 | |
---|
1054 | edge_lists[de].next = cne; |
---|
1055 | edge_lists[ce].next = dne; |
---|
1056 | |
---|
1057 | edge_lists[dne].prev = ce; |
---|
1058 | edge_lists[cne].prev = de; |
---|
1059 | } |
---|
1060 | |
---|
1061 | node_data[dd].first = ce; |
---|
1062 | |
---|
1063 | } |
---|
1064 | } |
---|
1065 | |
---|
1066 | void storeEmbedding(const Node& node, NodeData& node_data, |
---|
1067 | OrderMap& order_map, PredMap& pred_map, |
---|
1068 | EdgeLists& edge_lists, FlipMap& flip_map) { |
---|
1069 | |
---|
1070 | if (node_data[order_map[node]].first == INVALID) return; |
---|
1071 | |
---|
1072 | if (pred_map[node] != INVALID) { |
---|
1073 | Node source = _ugraph.source(pred_map[node]); |
---|
1074 | flip_map[node] = flip_map[node] != flip_map[source]; |
---|
1075 | } |
---|
1076 | |
---|
1077 | Edge first = node_data[order_map[node]].first; |
---|
1078 | Edge prev = first; |
---|
1079 | |
---|
1080 | Edge edge = flip_map[node] ? |
---|
1081 | edge_lists[prev].prev : edge_lists[prev].next; |
---|
1082 | |
---|
1083 | _embedding[prev] = edge; |
---|
1084 | |
---|
1085 | while (edge != first) { |
---|
1086 | Edge next = edge_lists[edge].prev == prev ? |
---|
1087 | edge_lists[edge].next : edge_lists[edge].prev; |
---|
1088 | prev = edge; edge = next; |
---|
1089 | _embedding[prev] = edge; |
---|
1090 | } |
---|
1091 | } |
---|
1092 | |
---|
1093 | |
---|
1094 | bool external(const Node& node, int rorder, |
---|
1095 | ChildLists& child_lists, AncestorMap& ancestor_map, |
---|
1096 | LowMap& low_map) { |
---|
1097 | Node child = child_lists[node].first; |
---|
1098 | |
---|
1099 | if (child != INVALID) { |
---|
1100 | if (low_map[child] < rorder) return true; |
---|
1101 | } |
---|
1102 | |
---|
1103 | if (ancestor_map[node] < rorder) return true; |
---|
1104 | |
---|
1105 | return false; |
---|
1106 | } |
---|
1107 | |
---|
1108 | bool pertinent(const Node& node, const EmbedEdge& embed_edge, |
---|
1109 | const MergeRoots& merge_roots) { |
---|
1110 | return !merge_roots[node].empty() || embed_edge[node] != INVALID; |
---|
1111 | } |
---|
1112 | |
---|
1113 | int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists, |
---|
1114 | AncestorMap& ancestor_map, LowMap& low_map) { |
---|
1115 | int low_point; |
---|
1116 | |
---|
1117 | Node child = child_lists[node].first; |
---|
1118 | |
---|
1119 | if (child != INVALID) { |
---|
1120 | low_point = low_map[child]; |
---|
1121 | } else { |
---|
1122 | low_point = order_map[node]; |
---|
1123 | } |
---|
1124 | |
---|
1125 | if (low_point > ancestor_map[node]) { |
---|
1126 | low_point = ancestor_map[node]; |
---|
1127 | } |
---|
1128 | |
---|
1129 | return low_point; |
---|
1130 | } |
---|
1131 | |
---|
1132 | int findComponentRoot(Node root, Node node, ChildLists& child_lists, |
---|
1133 | OrderMap& order_map, OrderList& order_list) { |
---|
1134 | |
---|
1135 | int order = order_map[root]; |
---|
1136 | int norder = order_map[node]; |
---|
1137 | |
---|
1138 | Node child = child_lists[root].first; |
---|
1139 | while (child != INVALID) { |
---|
1140 | int corder = order_map[child]; |
---|
1141 | if (corder > order && corder < norder) { |
---|
1142 | order = corder; |
---|
1143 | } |
---|
1144 | child = child_lists[child].next; |
---|
1145 | } |
---|
1146 | return order + order_list.size(); |
---|
1147 | } |
---|
1148 | |
---|
1149 | Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data, |
---|
1150 | EmbedEdge& embed_edge, MergeRoots& merge_roots) { |
---|
1151 | Node wnode =_ugraph.target(node_data[order_map[node]].first); |
---|
1152 | while (!pertinent(wnode, embed_edge, merge_roots)) { |
---|
1153 | wnode = _ugraph.target(node_data[order_map[wnode]].first); |
---|
1154 | } |
---|
1155 | return wnode; |
---|
1156 | } |
---|
1157 | |
---|
1158 | |
---|
1159 | Node findExternal(Node node, int rorder, OrderMap& order_map, |
---|
1160 | ChildLists& child_lists, AncestorMap& ancestor_map, |
---|
1161 | LowMap& low_map, NodeData& node_data) { |
---|
1162 | Node wnode =_ugraph.target(node_data[order_map[node]].first); |
---|
1163 | while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) { |
---|
1164 | wnode = _ugraph.target(node_data[order_map[wnode]].first); |
---|
1165 | } |
---|
1166 | return wnode; |
---|
1167 | } |
---|
1168 | |
---|
1169 | void markCommonPath(Node node, int rorder, Node& wnode, Node& znode, |
---|
1170 | OrderList& order_list, OrderMap& order_map, |
---|
1171 | NodeData& node_data, EdgeLists& edge_lists, |
---|
1172 | EmbedEdge& embed_edge, MergeRoots& merge_roots, |
---|
1173 | ChildLists& child_lists, AncestorMap& ancestor_map, |
---|
1174 | LowMap& low_map) { |
---|
1175 | |
---|
1176 | Node cnode = node; |
---|
1177 | Node pred = INVALID; |
---|
1178 | |
---|
1179 | while (true) { |
---|
1180 | |
---|
1181 | bool pert = pertinent(cnode, embed_edge, merge_roots); |
---|
1182 | bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map); |
---|
1183 | |
---|
1184 | if (pert && ext) { |
---|
1185 | if (!merge_roots[cnode].empty()) { |
---|
1186 | int cn = merge_roots[cnode].back(); |
---|
1187 | |
---|
1188 | if (low_map[order_list[cn - order_list.size()]] < rorder) { |
---|
1189 | Edge edge = node_data[cn].first; |
---|
1190 | _kuratowski.set(edge, true); |
---|
1191 | |
---|
1192 | pred = cnode; |
---|
1193 | cnode = _ugraph.target(edge); |
---|
1194 | |
---|
1195 | continue; |
---|
1196 | } |
---|
1197 | } |
---|
1198 | wnode = znode = cnode; |
---|
1199 | return; |
---|
1200 | |
---|
1201 | } else if (pert) { |
---|
1202 | wnode = cnode; |
---|
1203 | |
---|
1204 | while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) { |
---|
1205 | Edge edge = node_data[order_map[cnode]].first; |
---|
1206 | |
---|
1207 | if (_ugraph.target(edge) == pred) { |
---|
1208 | edge = edge_lists[edge].next; |
---|
1209 | } |
---|
1210 | _kuratowski.set(edge, true); |
---|
1211 | |
---|
1212 | Node next = _ugraph.target(edge); |
---|
1213 | pred = cnode; cnode = next; |
---|
1214 | } |
---|
1215 | |
---|
1216 | znode = cnode; |
---|
1217 | return; |
---|
1218 | |
---|
1219 | } else if (ext) { |
---|
1220 | znode = cnode; |
---|
1221 | |
---|
1222 | while (!pertinent(cnode, embed_edge, merge_roots)) { |
---|
1223 | Edge edge = node_data[order_map[cnode]].first; |
---|
1224 | |
---|
1225 | if (_ugraph.target(edge) == pred) { |
---|
1226 | edge = edge_lists[edge].next; |
---|
1227 | } |
---|
1228 | _kuratowski.set(edge, true); |
---|
1229 | |
---|
1230 | Node next = _ugraph.target(edge); |
---|
1231 | pred = cnode; cnode = next; |
---|
1232 | } |
---|
1233 | |
---|
1234 | wnode = cnode; |
---|
1235 | return; |
---|
1236 | |
---|
1237 | } else { |
---|
1238 | Edge edge = node_data[order_map[cnode]].first; |
---|
1239 | |
---|
1240 | if (_ugraph.target(edge) == pred) { |
---|
1241 | edge = edge_lists[edge].next; |
---|
1242 | } |
---|
1243 | _kuratowski.set(edge, true); |
---|
1244 | |
---|
1245 | Node next = _ugraph.target(edge); |
---|
1246 | pred = cnode; cnode = next; |
---|
1247 | } |
---|
1248 | |
---|
1249 | } |
---|
1250 | |
---|
1251 | } |
---|
1252 | |
---|
1253 | void orientComponent(Node root, int rn, OrderMap& order_map, |
---|
1254 | PredMap& pred_map, NodeData& node_data, |
---|
1255 | EdgeLists& edge_lists, FlipMap& flip_map, |
---|
1256 | TypeMap& type_map) { |
---|
1257 | node_data[order_map[root]].first = node_data[rn].first; |
---|
1258 | type_map[root] = 1; |
---|
1259 | |
---|
1260 | std::vector<Node> st, qu; |
---|
1261 | |
---|
1262 | st.push_back(root); |
---|
1263 | while (!st.empty()) { |
---|
1264 | Node node = st.back(); |
---|
1265 | st.pop_back(); |
---|
1266 | qu.push_back(node); |
---|
1267 | |
---|
1268 | Edge edge = node_data[order_map[node]].first; |
---|
1269 | |
---|
1270 | if (type_map[_ugraph.target(edge)] == 0) { |
---|
1271 | st.push_back(_ugraph.target(edge)); |
---|
1272 | type_map[_ugraph.target(edge)] = 1; |
---|
1273 | } |
---|
1274 | |
---|
1275 | Edge last = edge, pred = edge; |
---|
1276 | edge = edge_lists[edge].next; |
---|
1277 | while (edge != last) { |
---|
1278 | |
---|
1279 | if (type_map[_ugraph.target(edge)] == 0) { |
---|
1280 | st.push_back(_ugraph.target(edge)); |
---|
1281 | type_map[_ugraph.target(edge)] = 1; |
---|
1282 | } |
---|
1283 | |
---|
1284 | Edge next = edge_lists[edge].next != pred ? |
---|
1285 | edge_lists[edge].next : edge_lists[edge].prev; |
---|
1286 | pred = edge; edge = next; |
---|
1287 | } |
---|
1288 | |
---|
1289 | } |
---|
1290 | |
---|
1291 | type_map[root] = 2; |
---|
1292 | flip_map[root] = false; |
---|
1293 | |
---|
1294 | for (int i = 1; i < int(qu.size()); ++i) { |
---|
1295 | |
---|
1296 | Node node = qu[i]; |
---|
1297 | |
---|
1298 | while (type_map[node] != 2) { |
---|
1299 | st.push_back(node); |
---|
1300 | type_map[node] = 2; |
---|
1301 | node = _ugraph.source(pred_map[node]); |
---|
1302 | } |
---|
1303 | |
---|
1304 | bool flip = flip_map[node]; |
---|
1305 | |
---|
1306 | while (!st.empty()) { |
---|
1307 | node = st.back(); |
---|
1308 | st.pop_back(); |
---|
1309 | |
---|
1310 | flip_map[node] = flip != flip_map[node]; |
---|
1311 | flip = flip_map[node]; |
---|
1312 | |
---|
1313 | if (flip) { |
---|
1314 | Edge edge = node_data[order_map[node]].first; |
---|
1315 | std::swap(edge_lists[edge].prev, edge_lists[edge].next); |
---|
1316 | edge = edge_lists[edge].prev; |
---|
1317 | std::swap(edge_lists[edge].prev, edge_lists[edge].next); |
---|
1318 | node_data[order_map[node]].first = edge; |
---|
1319 | } |
---|
1320 | } |
---|
1321 | } |
---|
1322 | |
---|
1323 | for (int i = 0; i < int(qu.size()); ++i) { |
---|
1324 | |
---|
1325 | Edge edge = node_data[order_map[qu[i]]].first; |
---|
1326 | Edge last = edge, pred = edge; |
---|
1327 | |
---|
1328 | edge = edge_lists[edge].next; |
---|
1329 | while (edge != last) { |
---|
1330 | |
---|
1331 | if (edge_lists[edge].next == pred) { |
---|
1332 | std::swap(edge_lists[edge].next, edge_lists[edge].prev); |
---|
1333 | } |
---|
1334 | pred = edge; edge = edge_lists[edge].next; |
---|
1335 | } |
---|
1336 | |
---|
1337 | } |
---|
1338 | } |
---|
1339 | |
---|
1340 | void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode, |
---|
1341 | OrderMap& order_map, NodeData& node_data, |
---|
1342 | TypeMap& type_map) { |
---|
1343 | Node node = _ugraph.target(node_data[order_map[root]].first); |
---|
1344 | |
---|
1345 | while (node != ynode) { |
---|
1346 | type_map[node] = HIGHY; |
---|
1347 | node = _ugraph.target(node_data[order_map[node]].first); |
---|
1348 | } |
---|
1349 | |
---|
1350 | while (node != wnode) { |
---|
1351 | type_map[node] = LOWY; |
---|
1352 | node = _ugraph.target(node_data[order_map[node]].first); |
---|
1353 | } |
---|
1354 | |
---|
1355 | node = _ugraph.target(node_data[order_map[wnode]].first); |
---|
1356 | |
---|
1357 | while (node != xnode) { |
---|
1358 | type_map[node] = LOWX; |
---|
1359 | node = _ugraph.target(node_data[order_map[node]].first); |
---|
1360 | } |
---|
1361 | type_map[node] = LOWX; |
---|
1362 | |
---|
1363 | node = _ugraph.target(node_data[order_map[xnode]].first); |
---|
1364 | while (node != root) { |
---|
1365 | type_map[node] = HIGHX; |
---|
1366 | node = _ugraph.target(node_data[order_map[node]].first); |
---|
1367 | } |
---|
1368 | |
---|
1369 | type_map[wnode] = PERTINENT; |
---|
1370 | type_map[root] = ROOT; |
---|
1371 | } |
---|
1372 | |
---|
1373 | void findInternalPath(std::vector<Edge>& ipath, |
---|
1374 | Node wnode, Node root, TypeMap& type_map, |
---|
1375 | OrderMap& order_map, NodeData& node_data, |
---|
1376 | EdgeLists& edge_lists) { |
---|
1377 | std::vector<Edge> st; |
---|
1378 | |
---|
1379 | Node node = wnode; |
---|
1380 | |
---|
1381 | while (node != root) { |
---|
1382 | Edge edge = edge_lists[node_data[order_map[node]].first].next; |
---|
1383 | st.push_back(edge); |
---|
1384 | node = _ugraph.target(edge); |
---|
1385 | } |
---|
1386 | |
---|
1387 | while (true) { |
---|
1388 | Edge edge = st.back(); |
---|
1389 | if (type_map[_ugraph.target(edge)] == LOWX || |
---|
1390 | type_map[_ugraph.target(edge)] == HIGHX) { |
---|
1391 | break; |
---|
1392 | } |
---|
1393 | if (type_map[_ugraph.target(edge)] == 2) { |
---|
1394 | type_map[_ugraph.target(edge)] = 3; |
---|
1395 | |
---|
1396 | edge = edge_lists[_ugraph.oppositeEdge(edge)].next; |
---|
1397 | st.push_back(edge); |
---|
1398 | } else { |
---|
1399 | st.pop_back(); |
---|
1400 | edge = edge_lists[edge].next; |
---|
1401 | |
---|
1402 | while (_ugraph.oppositeEdge(edge) == st.back()) { |
---|
1403 | edge = st.back(); |
---|
1404 | st.pop_back(); |
---|
1405 | edge = edge_lists[edge].next; |
---|
1406 | } |
---|
1407 | st.push_back(edge); |
---|
1408 | } |
---|
1409 | } |
---|
1410 | |
---|
1411 | for (int i = 0; i < int(st.size()); ++i) { |
---|
1412 | if (type_map[_ugraph.target(st[i])] != LOWY && |
---|
1413 | type_map[_ugraph.target(st[i])] != HIGHY) { |
---|
1414 | for (; i < int(st.size()); ++i) { |
---|
1415 | ipath.push_back(st[i]); |
---|
1416 | } |
---|
1417 | } |
---|
1418 | } |
---|
1419 | } |
---|
1420 | |
---|
1421 | void setInternalFlags(std::vector<Edge>& ipath, TypeMap& type_map) { |
---|
1422 | for (int i = 1; i < int(ipath.size()); ++i) { |
---|
1423 | type_map[_ugraph.source(ipath[i])] = INTERNAL; |
---|
1424 | } |
---|
1425 | } |
---|
1426 | |
---|
1427 | void findPilePath(std::vector<Edge>& ppath, |
---|
1428 | Node root, TypeMap& type_map, OrderMap& order_map, |
---|
1429 | NodeData& node_data, EdgeLists& edge_lists) { |
---|
1430 | std::vector<Edge> st; |
---|
1431 | |
---|
1432 | st.push_back(_ugraph.oppositeEdge(node_data[order_map[root]].first)); |
---|
1433 | st.push_back(node_data[order_map[root]].first); |
---|
1434 | |
---|
1435 | while (st.size() > 1) { |
---|
1436 | Edge edge = st.back(); |
---|
1437 | if (type_map[_ugraph.target(edge)] == INTERNAL) { |
---|
1438 | break; |
---|
1439 | } |
---|
1440 | if (type_map[_ugraph.target(edge)] == 3) { |
---|
1441 | type_map[_ugraph.target(edge)] = 4; |
---|
1442 | |
---|
1443 | edge = edge_lists[_ugraph.oppositeEdge(edge)].next; |
---|
1444 | st.push_back(edge); |
---|
1445 | } else { |
---|
1446 | st.pop_back(); |
---|
1447 | edge = edge_lists[edge].next; |
---|
1448 | |
---|
1449 | while (!st.empty() && _ugraph.oppositeEdge(edge) == st.back()) { |
---|
1450 | edge = st.back(); |
---|
1451 | st.pop_back(); |
---|
1452 | edge = edge_lists[edge].next; |
---|
1453 | } |
---|
1454 | st.push_back(edge); |
---|
1455 | } |
---|
1456 | } |
---|
1457 | |
---|
1458 | for (int i = 1; i < int(st.size()); ++i) { |
---|
1459 | ppath.push_back(st[i]); |
---|
1460 | } |
---|
1461 | } |
---|
1462 | |
---|
1463 | |
---|
1464 | int markExternalPath(Node node, OrderMap& order_map, |
---|
1465 | ChildLists& child_lists, PredMap& pred_map, |
---|
1466 | AncestorMap& ancestor_map, LowMap& low_map) { |
---|
1467 | int lp = lowPoint(node, order_map, child_lists, |
---|
1468 | ancestor_map, low_map); |
---|
1469 | |
---|
1470 | if (ancestor_map[node] != lp) { |
---|
1471 | node = child_lists[node].first; |
---|
1472 | _kuratowski[pred_map[node]] = true; |
---|
1473 | |
---|
1474 | while (ancestor_map[node] != lp) { |
---|
1475 | for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
---|
1476 | Node tnode = _ugraph.target(e); |
---|
1477 | if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) { |
---|
1478 | node = tnode; |
---|
1479 | _kuratowski[e] = true; |
---|
1480 | break; |
---|
1481 | } |
---|
1482 | } |
---|
1483 | } |
---|
1484 | } |
---|
1485 | |
---|
1486 | for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
---|
1487 | if (order_map[_ugraph.target(e)] == lp) { |
---|
1488 | _kuratowski[e] = true; |
---|
1489 | break; |
---|
1490 | } |
---|
1491 | } |
---|
1492 | |
---|
1493 | return lp; |
---|
1494 | } |
---|
1495 | |
---|
1496 | void markPertinentPath(Node node, OrderMap& order_map, |
---|
1497 | NodeData& node_data, EdgeLists& edge_lists, |
---|
1498 | EmbedEdge& embed_edge, MergeRoots& merge_roots) { |
---|
1499 | while (embed_edge[node] == INVALID) { |
---|
1500 | int n = merge_roots[node].front(); |
---|
1501 | Edge edge = node_data[n].first; |
---|
1502 | |
---|
1503 | _kuratowski.set(edge, true); |
---|
1504 | |
---|
1505 | Node pred = node; |
---|
1506 | node = _ugraph.target(edge); |
---|
1507 | while (!pertinent(node, embed_edge, merge_roots)) { |
---|
1508 | edge = node_data[order_map[node]].first; |
---|
1509 | if (_ugraph.target(edge) == pred) { |
---|
1510 | edge = edge_lists[edge].next; |
---|
1511 | } |
---|
1512 | _kuratowski.set(edge, true); |
---|
1513 | pred = node; |
---|
1514 | node = _ugraph.target(edge); |
---|
1515 | } |
---|
1516 | } |
---|
1517 | _kuratowski.set(embed_edge[node], true); |
---|
1518 | } |
---|
1519 | |
---|
1520 | void markPredPath(Node node, Node snode, PredMap& pred_map) { |
---|
1521 | while (node != snode) { |
---|
1522 | _kuratowski.set(pred_map[node], true); |
---|
1523 | node = _ugraph.source(pred_map[node]); |
---|
1524 | } |
---|
1525 | } |
---|
1526 | |
---|
1527 | void markFacePath(Node ynode, Node xnode, |
---|
1528 | OrderMap& order_map, NodeData& node_data) { |
---|
1529 | Edge edge = node_data[order_map[ynode]].first; |
---|
1530 | Node node = _ugraph.target(edge); |
---|
1531 | _kuratowski.set(edge, true); |
---|
1532 | |
---|
1533 | while (node != xnode) { |
---|
1534 | edge = node_data[order_map[node]].first; |
---|
1535 | _kuratowski.set(edge, true); |
---|
1536 | node = _ugraph.target(edge); |
---|
1537 | } |
---|
1538 | } |
---|
1539 | |
---|
1540 | void markInternalPath(std::vector<Edge>& path) { |
---|
1541 | for (int i = 0; i < int(path.size()); ++i) { |
---|
1542 | _kuratowski.set(path[i], true); |
---|
1543 | } |
---|
1544 | } |
---|
1545 | |
---|
1546 | void markPilePath(std::vector<Edge>& path) { |
---|
1547 | for (int i = 0; i < int(path.size()); ++i) { |
---|
1548 | _kuratowski.set(path[i], true); |
---|
1549 | } |
---|
1550 | } |
---|
1551 | |
---|
1552 | void isolateKuratowski(Edge edge, NodeData& node_data, |
---|
1553 | EdgeLists& edge_lists, FlipMap& flip_map, |
---|
1554 | OrderMap& order_map, OrderList& order_list, |
---|
1555 | PredMap& pred_map, ChildLists& child_lists, |
---|
1556 | AncestorMap& ancestor_map, LowMap& low_map, |
---|
1557 | EmbedEdge& embed_edge, MergeRoots& merge_roots) { |
---|
1558 | |
---|
1559 | Node root = _ugraph.source(edge); |
---|
1560 | Node enode = _ugraph.target(edge); |
---|
1561 | |
---|
1562 | int rorder = order_map[root]; |
---|
1563 | |
---|
1564 | TypeMap type_map(_ugraph, 0); |
---|
1565 | |
---|
1566 | int rn = findComponentRoot(root, enode, child_lists, |
---|
1567 | order_map, order_list); |
---|
1568 | |
---|
1569 | Node xnode = order_list[node_data[rn].next]; |
---|
1570 | Node ynode = order_list[node_data[rn].prev]; |
---|
1571 | |
---|
1572 | // Minor-A |
---|
1573 | { |
---|
1574 | while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) { |
---|
1575 | |
---|
1576 | if (!merge_roots[xnode].empty()) { |
---|
1577 | root = xnode; |
---|
1578 | rn = merge_roots[xnode].front(); |
---|
1579 | } else { |
---|
1580 | root = ynode; |
---|
1581 | rn = merge_roots[ynode].front(); |
---|
1582 | } |
---|
1583 | |
---|
1584 | xnode = order_list[node_data[rn].next]; |
---|
1585 | ynode = order_list[node_data[rn].prev]; |
---|
1586 | } |
---|
1587 | |
---|
1588 | if (root != _ugraph.source(edge)) { |
---|
1589 | orientComponent(root, rn, order_map, pred_map, |
---|
1590 | node_data, edge_lists, flip_map, type_map); |
---|
1591 | markFacePath(root, root, order_map, node_data); |
---|
1592 | int xlp = markExternalPath(xnode, order_map, child_lists, |
---|
1593 | pred_map, ancestor_map, low_map); |
---|
1594 | int ylp = markExternalPath(ynode, order_map, child_lists, |
---|
1595 | pred_map, ancestor_map, low_map); |
---|
1596 | markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); |
---|
1597 | Node lwnode = findPertinent(ynode, order_map, node_data, |
---|
1598 | embed_edge, merge_roots); |
---|
1599 | |
---|
1600 | markPertinentPath(lwnode, order_map, node_data, edge_lists, |
---|
1601 | embed_edge, merge_roots); |
---|
1602 | |
---|
1603 | return; |
---|
1604 | } |
---|
1605 | } |
---|
1606 | |
---|
1607 | orientComponent(root, rn, order_map, pred_map, |
---|
1608 | node_data, edge_lists, flip_map, type_map); |
---|
1609 | |
---|
1610 | Node wnode = findPertinent(ynode, order_map, node_data, |
---|
1611 | embed_edge, merge_roots); |
---|
1612 | setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map); |
---|
1613 | |
---|
1614 | |
---|
1615 | //Minor-B |
---|
1616 | if (!merge_roots[wnode].empty()) { |
---|
1617 | int cn = merge_roots[wnode].back(); |
---|
1618 | Node rep = order_list[cn - order_list.size()]; |
---|
1619 | if (low_map[rep] < rorder) { |
---|
1620 | markFacePath(root, root, order_map, node_data); |
---|
1621 | int xlp = markExternalPath(xnode, order_map, child_lists, |
---|
1622 | pred_map, ancestor_map, low_map); |
---|
1623 | int ylp = markExternalPath(ynode, order_map, child_lists, |
---|
1624 | pred_map, ancestor_map, low_map); |
---|
1625 | |
---|
1626 | Node lwnode, lznode; |
---|
1627 | markCommonPath(wnode, rorder, lwnode, lznode, order_list, |
---|
1628 | order_map, node_data, edge_lists, embed_edge, |
---|
1629 | merge_roots, child_lists, ancestor_map, low_map); |
---|
1630 | |
---|
1631 | markPertinentPath(lwnode, order_map, node_data, edge_lists, |
---|
1632 | embed_edge, merge_roots); |
---|
1633 | int zlp = markExternalPath(lznode, order_map, child_lists, |
---|
1634 | pred_map, ancestor_map, low_map); |
---|
1635 | |
---|
1636 | int minlp = xlp < ylp ? xlp : ylp; |
---|
1637 | if (zlp < minlp) minlp = zlp; |
---|
1638 | |
---|
1639 | int maxlp = xlp > ylp ? xlp : ylp; |
---|
1640 | if (zlp > maxlp) maxlp = zlp; |
---|
1641 | |
---|
1642 | markPredPath(order_list[maxlp], order_list[minlp], pred_map); |
---|
1643 | |
---|
1644 | return; |
---|
1645 | } |
---|
1646 | } |
---|
1647 | |
---|
1648 | Node pxnode, pynode; |
---|
1649 | std::vector<Edge> ipath; |
---|
1650 | findInternalPath(ipath, wnode, root, type_map, order_map, |
---|
1651 | node_data, edge_lists); |
---|
1652 | setInternalFlags(ipath, type_map); |
---|
1653 | pynode = _ugraph.source(ipath.front()); |
---|
1654 | pxnode = _ugraph.target(ipath.back()); |
---|
1655 | |
---|
1656 | wnode = findPertinent(pynode, order_map, node_data, |
---|
1657 | embed_edge, merge_roots); |
---|
1658 | |
---|
1659 | // Minor-C |
---|
1660 | { |
---|
1661 | if (type_map[_ugraph.source(ipath.front())] == HIGHY) { |
---|
1662 | if (type_map[_ugraph.target(ipath.back())] == HIGHX) { |
---|
1663 | markFacePath(xnode, pxnode, order_map, node_data); |
---|
1664 | } |
---|
1665 | markFacePath(root, xnode, order_map, node_data); |
---|
1666 | markPertinentPath(wnode, order_map, node_data, edge_lists, |
---|
1667 | embed_edge, merge_roots); |
---|
1668 | markInternalPath(ipath); |
---|
1669 | int xlp = markExternalPath(xnode, order_map, child_lists, |
---|
1670 | pred_map, ancestor_map, low_map); |
---|
1671 | int ylp = markExternalPath(ynode, order_map, child_lists, |
---|
1672 | pred_map, ancestor_map, low_map); |
---|
1673 | markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); |
---|
1674 | return; |
---|
1675 | } |
---|
1676 | |
---|
1677 | if (type_map[_ugraph.target(ipath.back())] == HIGHX) { |
---|
1678 | markFacePath(ynode, root, order_map, node_data); |
---|
1679 | markPertinentPath(wnode, order_map, node_data, edge_lists, |
---|
1680 | embed_edge, merge_roots); |
---|
1681 | markInternalPath(ipath); |
---|
1682 | int xlp = markExternalPath(xnode, order_map, child_lists, |
---|
1683 | pred_map, ancestor_map, low_map); |
---|
1684 | int ylp = markExternalPath(ynode, order_map, child_lists, |
---|
1685 | pred_map, ancestor_map, low_map); |
---|
1686 | markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); |
---|
1687 | return; |
---|
1688 | } |
---|
1689 | } |
---|
1690 | |
---|
1691 | std::vector<Edge> ppath; |
---|
1692 | findPilePath(ppath, root, type_map, order_map, node_data, edge_lists); |
---|
1693 | |
---|
1694 | // Minor-D |
---|
1695 | if (!ppath.empty()) { |
---|
1696 | markFacePath(ynode, xnode, order_map, node_data); |
---|
1697 | markPertinentPath(wnode, order_map, node_data, edge_lists, |
---|
1698 | embed_edge, merge_roots); |
---|
1699 | markPilePath(ppath); |
---|
1700 | markInternalPath(ipath); |
---|
1701 | int xlp = markExternalPath(xnode, order_map, child_lists, |
---|
1702 | pred_map, ancestor_map, low_map); |
---|
1703 | int ylp = markExternalPath(ynode, order_map, child_lists, |
---|
1704 | pred_map, ancestor_map, low_map); |
---|
1705 | markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); |
---|
1706 | return; |
---|
1707 | } |
---|
1708 | |
---|
1709 | // Minor-E* |
---|
1710 | { |
---|
1711 | |
---|
1712 | if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) { |
---|
1713 | Node znode = findExternal(pynode, rorder, order_map, |
---|
1714 | child_lists, ancestor_map, |
---|
1715 | low_map, node_data); |
---|
1716 | |
---|
1717 | if (type_map[znode] == LOWY) { |
---|
1718 | markFacePath(root, xnode, order_map, node_data); |
---|
1719 | markPertinentPath(wnode, order_map, node_data, edge_lists, |
---|
1720 | embed_edge, merge_roots); |
---|
1721 | markInternalPath(ipath); |
---|
1722 | int xlp = markExternalPath(xnode, order_map, child_lists, |
---|
1723 | pred_map, ancestor_map, low_map); |
---|
1724 | int zlp = markExternalPath(znode, order_map, child_lists, |
---|
1725 | pred_map, ancestor_map, low_map); |
---|
1726 | markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map); |
---|
1727 | } else { |
---|
1728 | markFacePath(ynode, root, order_map, node_data); |
---|
1729 | markPertinentPath(wnode, order_map, node_data, edge_lists, |
---|
1730 | embed_edge, merge_roots); |
---|
1731 | markInternalPath(ipath); |
---|
1732 | int ylp = markExternalPath(ynode, order_map, child_lists, |
---|
1733 | pred_map, ancestor_map, low_map); |
---|
1734 | int zlp = markExternalPath(znode, order_map, child_lists, |
---|
1735 | pred_map, ancestor_map, low_map); |
---|
1736 | markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map); |
---|
1737 | } |
---|
1738 | return; |
---|
1739 | } |
---|
1740 | |
---|
1741 | int xlp = markExternalPath(xnode, order_map, child_lists, |
---|
1742 | pred_map, ancestor_map, low_map); |
---|
1743 | int ylp = markExternalPath(ynode, order_map, child_lists, |
---|
1744 | pred_map, ancestor_map, low_map); |
---|
1745 | int wlp = markExternalPath(wnode, order_map, child_lists, |
---|
1746 | pred_map, ancestor_map, low_map); |
---|
1747 | |
---|
1748 | if (wlp > xlp && wlp > ylp) { |
---|
1749 | markFacePath(root, root, order_map, node_data); |
---|
1750 | markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map); |
---|
1751 | return; |
---|
1752 | } |
---|
1753 | |
---|
1754 | markInternalPath(ipath); |
---|
1755 | markPertinentPath(wnode, order_map, node_data, edge_lists, |
---|
1756 | embed_edge, merge_roots); |
---|
1757 | |
---|
1758 | if (xlp > ylp && xlp > wlp) { |
---|
1759 | markFacePath(root, pynode, order_map, node_data); |
---|
1760 | markFacePath(wnode, xnode, order_map, node_data); |
---|
1761 | markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map); |
---|
1762 | return; |
---|
1763 | } |
---|
1764 | |
---|
1765 | if (ylp > xlp && ylp > wlp) { |
---|
1766 | markFacePath(pxnode, root, order_map, node_data); |
---|
1767 | markFacePath(ynode, wnode, order_map, node_data); |
---|
1768 | markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map); |
---|
1769 | return; |
---|
1770 | } |
---|
1771 | |
---|
1772 | if (pynode != ynode) { |
---|
1773 | markFacePath(pxnode, wnode, order_map, node_data); |
---|
1774 | |
---|
1775 | int minlp = xlp < ylp ? xlp : ylp; |
---|
1776 | if (wlp < minlp) minlp = wlp; |
---|
1777 | |
---|
1778 | int maxlp = xlp > ylp ? xlp : ylp; |
---|
1779 | if (wlp > maxlp) maxlp = wlp; |
---|
1780 | |
---|
1781 | markPredPath(order_list[maxlp], order_list[minlp], pred_map); |
---|
1782 | return; |
---|
1783 | } |
---|
1784 | |
---|
1785 | if (pxnode != xnode) { |
---|
1786 | markFacePath(wnode, pynode, order_map, node_data); |
---|
1787 | |
---|
1788 | int minlp = xlp < ylp ? xlp : ylp; |
---|
1789 | if (wlp < minlp) minlp = wlp; |
---|
1790 | |
---|
1791 | int maxlp = xlp > ylp ? xlp : ylp; |
---|
1792 | if (wlp > maxlp) maxlp = wlp; |
---|
1793 | |
---|
1794 | markPredPath(order_list[maxlp], order_list[minlp], pred_map); |
---|
1795 | return; |
---|
1796 | } |
---|
1797 | |
---|
1798 | markFacePath(root, root, order_map, node_data); |
---|
1799 | int minlp = xlp < ylp ? xlp : ylp; |
---|
1800 | if (wlp < minlp) minlp = wlp; |
---|
1801 | markPredPath(root, order_list[minlp], pred_map); |
---|
1802 | return; |
---|
1803 | } |
---|
1804 | |
---|
1805 | } |
---|
1806 | |
---|
1807 | }; |
---|
1808 | |
---|
1809 | } |
---|
1810 | |
---|
1811 | #endif |
---|