3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
18 #ifndef LEMON_PLANARITY_H
19 #define LEMON_PLANARITY_H
21 /// \ingroup graph_prop
23 /// \brief Planarity checking, embedding
28 #include <lemon/dfs.h>
29 #include <lemon/radix_sort.h>
30 #include <lemon/maps.h>
31 #include <lemon/path.h>
36 namespace _planarity_bits {
38 template <typename UGraph>
39 struct PlanarityVisitor : DfsVisitor<UGraph> {
41 typedef typename UGraph::Node Node;
42 typedef typename UGraph::Edge Edge;
44 typedef typename UGraph::template NodeMap<Edge> PredMap;
46 typedef typename UGraph::template UEdgeMap<bool> TreeMap;
48 typedef typename UGraph::template NodeMap<int> OrderMap;
49 typedef std::vector<Node> OrderList;
51 typedef typename UGraph::template NodeMap<int> LowMap;
52 typedef typename UGraph::template NodeMap<int> AncestorMap;
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) {}
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);
69 void discover(const Edge& edge) {
70 Node source = _ugraph.source(edge);
71 Node target = _ugraph.target(edge);
73 _tree_map[edge] = true;
74 _pred_map[target] = edge;
77 void examine(const Edge& edge) {
78 Node source = _ugraph.source(edge);
79 Node target = _ugraph.target(edge);
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];
85 if (_ancestor_map[source] > _order_map[target]) {
86 _ancestor_map[source] = _order_map[target];
91 void backtrack(const Edge& edge) {
92 Node source = _ugraph.source(edge);
93 Node target = _ugraph.target(edge);
95 if (_low_map[source] > _low_map[target]) {
96 _low_map[source] = _low_map[target];
100 const UGraph& _ugraph;
103 OrderMap& _order_map;
104 OrderList& _order_list;
105 AncestorMap& _ancestor_map;
109 template <typename UGraph, bool embedding = true>
110 struct NodeDataNode {
113 typename UGraph::Edge first;
117 template <typename UGraph>
118 struct NodeDataNode<UGraph, false> {
123 template <typename UGraph>
124 struct ChildListNode {
125 typedef typename UGraph::Node Node;
130 template <typename UGraph>
131 struct EdgeListNode {
132 typename UGraph::Edge prev, next;
137 /// \ingroup graph_prop
139 /// \brief Planarity checking of an undirected simple graph
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 {
149 UGRAPH_TYPEDEFS(typename UGraph)
151 const UGraph& _ugraph;
155 typedef typename UGraph::template NodeMap<Edge> PredMap;
157 typedef typename UGraph::template UEdgeMap<bool> TreeMap;
159 typedef typename UGraph::template NodeMap<int> OrderMap;
160 typedef std::vector<Node> OrderList;
162 typedef typename UGraph::template NodeMap<int> LowMap;
163 typedef typename UGraph::template NodeMap<int> AncestorMap;
165 typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
166 typedef std::vector<NodeDataNode> NodeData;
168 typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
169 typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
171 typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
173 typedef typename UGraph::template NodeMap<bool> EmbedEdge;
177 /// \brief Constructor
179 /// \warining The graph should be simple, i.e. parallel and loop edge
181 PlanarityChecking(const UGraph& ugraph) : _ugraph(ugraph) {}
183 /// \brief Runs the algorithm.
185 /// Runs the algorithm.
186 /// \param kuratowski If the parameter is false, then the
187 /// algorithm does not calculate the isolate Kuratowski
189 /// \return %True when the graph is planar.
190 bool run(bool kuratowski = true) {
191 typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
193 PredMap pred_map(_ugraph, INVALID);
194 TreeMap tree_map(_ugraph, false);
196 OrderMap order_map(_ugraph, -1);
197 OrderList order_list;
199 AncestorMap ancestor_map(_ugraph, -1);
200 LowMap low_map(_ugraph, -1);
202 Visitor visitor(_ugraph, pred_map, tree_map,
203 order_map, order_list, ancestor_map, low_map);
204 DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
207 ChildLists child_lists(_ugraph);
208 createChildLists(tree_map, order_map, low_map, child_lists);
210 NodeData node_data(2 * order_list.size());
212 EmbedEdge embed_edge(_ugraph, false);
214 MergeRoots merge_roots(_ugraph);
216 for (int i = order_list.size() - 1; i >= 0; --i) {
218 Node node = order_list[i];
221 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
222 Node target = _ugraph.target(e);
224 if (order_map[source] < order_map[target] && tree_map[e]) {
225 initFace(target, node_data, pred_map, order_map, order_list);
229 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
230 Node target = _ugraph.target(e);
232 if (order_map[source] < order_map[target] && !tree_map[e]) {
233 embed_edge[target] = true;
234 walkUp(target, source, i, pred_map, low_map,
235 order_map, order_list, node_data, merge_roots);
239 for (typename MergeRoots::Value::iterator it =
240 merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
242 walkDown(rn, i, node_data, order_list, child_lists,
243 ancestor_map, low_map, embed_edge, merge_roots);
245 merge_roots[node].clear();
247 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
248 Node target = _ugraph.target(e);
250 if (order_map[source] < order_map[target] && !tree_map[e]) {
251 if (embed_edge[target]) {
263 void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
264 const LowMap& low_map, ChildLists& child_lists) {
266 for (NodeIt n(_ugraph); n != INVALID; ++n) {
269 std::vector<Node> targets;
270 for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
271 Node target = _ugraph.target(e);
273 if (order_map[source] < order_map[target] && tree_map[e]) {
274 targets.push_back(target);
278 if (targets.size() == 0) {
279 child_lists[source].first = INVALID;
280 } else if (targets.size() == 1) {
281 child_lists[source].first = targets[0];
282 child_lists[targets[0]].prev = INVALID;
283 child_lists[targets[0]].next = INVALID;
285 radixSort(targets.begin(), targets.end(), mapFunctor(low_map));
286 for (int i = 1; i < int(targets.size()); ++i) {
287 child_lists[targets[i]].prev = targets[i - 1];
288 child_lists[targets[i - 1]].next = targets[i];
290 child_lists[targets.back()].next = INVALID;
291 child_lists[targets.front()].prev = INVALID;
292 child_lists[source].first = targets.front();
297 void walkUp(const Node& node, Node root, int rorder,
298 const PredMap& pred_map, const LowMap& low_map,
299 const OrderMap& order_map, const OrderList& order_list,
300 NodeData& node_data, MergeRoots& merge_roots) {
305 na = nb = order_map[node];
306 da = true; db = false;
310 if (node_data[na].visited == rorder) break;
311 if (node_data[nb].visited == rorder) break;
313 node_data[na].visited = rorder;
314 node_data[nb].visited = rorder;
318 if (na >= int(order_list.size())) {
320 } else if (nb >= int(order_list.size())) {
327 nn = da ? node_data[na].prev : node_data[na].next;
328 da = node_data[nn].prev != na;
331 nn = db ? node_data[nb].prev : node_data[nb].next;
332 db = node_data[nn].prev != nb;
337 Node rep = order_list[rn - order_list.size()];
338 Node parent = _ugraph.source(pred_map[rep]);
340 if (low_map[rep] < rorder) {
341 merge_roots[parent].push_back(rn);
343 merge_roots[parent].push_front(rn);
346 if (parent != root) {
347 na = nb = order_map[parent];
348 da = true; db = false;
356 void walkDown(int rn, int rorder, NodeData& node_data,
357 OrderList& order_list, ChildLists& child_lists,
358 AncestorMap& ancestor_map, LowMap& low_map,
359 EmbedEdge& embed_edge, MergeRoots& merge_roots) {
361 std::vector<std::pair<int, bool> > merge_stack;
363 for (int di = 0; di < 2; ++di) {
366 int n = rd ? node_data[rn].next : node_data[rn].prev;
370 Node node = order_list[n];
372 if (embed_edge[node]) {
374 // Merging components on the critical path
375 while (!merge_stack.empty()) {
378 int cn = merge_stack.back().first;
379 bool cd = merge_stack.back().second;
380 merge_stack.pop_back();
382 // Parent of component
383 int dn = merge_stack.back().first;
384 bool dd = merge_stack.back().second;
385 merge_stack.pop_back();
387 Node parent = order_list[dn];
389 // Erasing from merge_roots
390 merge_roots[parent].pop_front();
392 Node child = order_list[cn - order_list.size()];
394 // Erasing from child_lists
395 if (child_lists[child].prev != INVALID) {
396 child_lists[child_lists[child].prev].next =
397 child_lists[child].next;
399 child_lists[parent].first = child_lists[child].next;
402 if (child_lists[child].next != INVALID) {
403 child_lists[child_lists[child].next].prev =
404 child_lists[child].prev;
407 // Merging external faces
410 cn = cd ? node_data[cn].prev : node_data[cn].next;
411 cd = node_data[cn].next == en;
415 if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
416 if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
420 bool d = pn == node_data[n].prev;
422 if (node_data[n].prev == node_data[n].next &&
423 node_data[n].inverted) {
427 // Embedding edge into external face
428 if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
429 if (d) node_data[n].prev = rn; else node_data[n].next = rn;
432 embed_edge[order_list[n]] = false;
435 if (!merge_roots[node].empty()) {
437 bool d = pn == node_data[n].prev;
439 merge_stack.push_back(std::make_pair(n, d));
441 int rn = merge_roots[node].front();
443 int xn = node_data[rn].next;
444 Node xnode = order_list[xn];
446 int yn = node_data[rn].prev;
447 Node ynode = order_list[yn];
450 if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
452 } else if (!external(ynode, rorder, child_lists,
453 ancestor_map, low_map)) {
455 } else if (pertinent(xnode, embed_edge, merge_roots)) {
461 merge_stack.push_back(std::make_pair(rn, rd));
466 } else if (!external(node, rorder, child_lists,
467 ancestor_map, low_map)) {
468 int nn = (node_data[n].next != pn ?
469 node_data[n].next : node_data[n].prev);
471 bool nd = n == node_data[nn].prev;
473 if (nd) node_data[nn].prev = pn;
474 else node_data[nn].next = pn;
476 if (n == node_data[pn].prev) node_data[pn].prev = nn;
477 else node_data[pn].next = nn;
479 node_data[nn].inverted =
480 (node_data[nn].prev == node_data[nn].next && nd != rd);
488 if (!merge_stack.empty() || n == rn) {
494 void initFace(const Node& node, NodeData& node_data,
495 const PredMap& pred_map, const OrderMap& order_map,
496 const OrderList& order_list) {
497 int n = order_map[node];
498 int rn = n + order_list.size();
500 node_data[n].next = node_data[n].prev = rn;
501 node_data[rn].next = node_data[rn].prev = n;
503 node_data[n].visited = order_list.size();
504 node_data[rn].visited = order_list.size();
508 bool external(const Node& node, int rorder,
509 ChildLists& child_lists, AncestorMap& ancestor_map,
511 Node child = child_lists[node].first;
513 if (child != INVALID) {
514 if (low_map[child] < rorder) return true;
517 if (ancestor_map[node] < rorder) return true;
522 bool pertinent(const Node& node, const EmbedEdge& embed_edge,
523 const MergeRoots& merge_roots) {
524 return !merge_roots[node].empty() || embed_edge[node];
529 /// \ingroup graph_prop
531 /// \brief Planar embedding of an undirected simple graph
533 /// This class implements the Boyer-Myrvold algorithm for planar
534 /// embedding of an undirected graph. The planar embeding is an
535 /// ordering of the outgoing edges in each node, which is a possible
536 /// configuration to draw the graph in the plane. If there is not
537 /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
538 /// with 5 nodes) or an \f$ K_{3,3} \f$ (complete bipartite graph on
539 /// 3 ANode and 3 BNode) subdivision.
541 /// The current implementation calculates an embedding or an
542 /// Kuratowski subdivision if the graph is not planar. The running
543 /// time of the algorithm is \f$ O(n) \f$.
544 template <typename UGraph>
545 class PlanarEmbedding {
548 UGRAPH_TYPEDEFS(typename UGraph)
550 const UGraph& _ugraph;
551 typename UGraph::template EdgeMap<Edge> _embedding;
553 typename UGraph::template UEdgeMap<bool> _kuratowski;
557 typedef typename UGraph::template NodeMap<Edge> PredMap;
559 typedef typename UGraph::template UEdgeMap<bool> TreeMap;
561 typedef typename UGraph::template NodeMap<int> OrderMap;
562 typedef std::vector<Node> OrderList;
564 typedef typename UGraph::template NodeMap<int> LowMap;
565 typedef typename UGraph::template NodeMap<int> AncestorMap;
567 typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
568 typedef std::vector<NodeDataNode> NodeData;
570 typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
571 typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
573 typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
575 typedef typename UGraph::template NodeMap<Edge> EmbedEdge;
577 typedef _planarity_bits::EdgeListNode<UGraph> EdgeListNode;
578 typedef typename UGraph::template EdgeMap<EdgeListNode> EdgeLists;
580 typedef typename UGraph::template NodeMap<bool> FlipMap;
582 typedef typename UGraph::template NodeMap<int> TypeMap;
584 enum IsolatorNodeType {
587 ROOT = 10, PERTINENT = 11,
593 /// \brief Constructor
595 /// \warining The graph should be simple, i.e. parallel and loop edge
597 PlanarEmbedding(const UGraph& ugraph)
598 : _ugraph(ugraph), _embedding(_ugraph), _kuratowski(ugraph, false) {}
600 /// \brief Runs the algorithm.
602 /// Runs the algorithm.
603 /// \param kuratowski If the parameter is false, then the
604 /// algorithm does not calculate the isolate Kuratowski
606 ///\return %True when the graph is planar.
607 bool run(bool kuratowski = true) {
608 typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
610 PredMap pred_map(_ugraph, INVALID);
611 TreeMap tree_map(_ugraph, false);
613 OrderMap order_map(_ugraph, -1);
614 OrderList order_list;
616 AncestorMap ancestor_map(_ugraph, -1);
617 LowMap low_map(_ugraph, -1);
619 Visitor visitor(_ugraph, pred_map, tree_map,
620 order_map, order_list, ancestor_map, low_map);
621 DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
624 ChildLists child_lists(_ugraph);
625 createChildLists(tree_map, order_map, low_map, child_lists);
627 NodeData node_data(2 * order_list.size());
629 EmbedEdge embed_edge(_ugraph, INVALID);
631 MergeRoots merge_roots(_ugraph);
633 EdgeLists edge_lists(_ugraph);
635 FlipMap flip_map(_ugraph, false);
637 for (int i = order_list.size() - 1; i >= 0; --i) {
639 Node node = order_list[i];
641 node_data[i].first = INVALID;
644 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
645 Node target = _ugraph.target(e);
647 if (order_map[source] < order_map[target] && tree_map[e]) {
648 initFace(target, edge_lists, node_data,
649 pred_map, order_map, order_list);
653 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
654 Node target = _ugraph.target(e);
656 if (order_map[source] < order_map[target] && !tree_map[e]) {
657 embed_edge[target] = e;
658 walkUp(target, source, i, pred_map, low_map,
659 order_map, order_list, node_data, merge_roots);
663 for (typename MergeRoots::Value::iterator it =
664 merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
666 walkDown(rn, i, node_data, edge_lists, flip_map, order_list,
667 child_lists, ancestor_map, low_map, embed_edge, merge_roots);
669 merge_roots[node].clear();
671 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
672 Node target = _ugraph.target(e);
674 if (order_map[source] < order_map[target] && !tree_map[e]) {
675 if (embed_edge[target] != INVALID) {
677 isolateKuratowski(e, node_data, edge_lists, flip_map,
678 order_map, order_list, pred_map, child_lists,
679 ancestor_map, low_map,
680 embed_edge, merge_roots);
688 for (int i = 0; i < int(order_list.size()); ++i) {
690 mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
691 child_lists, edge_lists);
692 storeEmbedding(order_list[i], node_data, order_map, pred_map,
693 edge_lists, flip_map);
699 /// \brief Gives back the successor of an edge
701 /// Gives back the successor of an edge. This function makes
702 /// possible to query the cyclic order of the outgoing edges from
704 Edge next(const Edge& edge) const {
705 return _embedding[edge];
708 /// \brief Gives back true when the undirected edge is in the
709 /// kuratowski subdivision
711 /// Gives back true when the undirected edge is in the kuratowski
713 bool kuratowski(const UEdge& uedge) {
714 return _kuratowski[uedge];
719 void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
720 const LowMap& low_map, ChildLists& child_lists) {
722 for (NodeIt n(_ugraph); n != INVALID; ++n) {
725 std::vector<Node> targets;
726 for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
727 Node target = _ugraph.target(e);
729 if (order_map[source] < order_map[target] && tree_map[e]) {
730 targets.push_back(target);
734 if (targets.size() == 0) {
735 child_lists[source].first = INVALID;
736 } else if (targets.size() == 1) {
737 child_lists[source].first = targets[0];
738 child_lists[targets[0]].prev = INVALID;
739 child_lists[targets[0]].next = INVALID;
741 radixSort(targets.begin(), targets.end(), mapFunctor(low_map));
742 for (int i = 1; i < int(targets.size()); ++i) {
743 child_lists[targets[i]].prev = targets[i - 1];
744 child_lists[targets[i - 1]].next = targets[i];
746 child_lists[targets.back()].next = INVALID;
747 child_lists[targets.front()].prev = INVALID;
748 child_lists[source].first = targets.front();
753 void walkUp(const Node& node, Node root, int rorder,
754 const PredMap& pred_map, const LowMap& low_map,
755 const OrderMap& order_map, const OrderList& order_list,
756 NodeData& node_data, MergeRoots& merge_roots) {
761 na = nb = order_map[node];
762 da = true; db = false;
766 if (node_data[na].visited == rorder) break;
767 if (node_data[nb].visited == rorder) break;
769 node_data[na].visited = rorder;
770 node_data[nb].visited = rorder;
774 if (na >= int(order_list.size())) {
776 } else if (nb >= int(order_list.size())) {
783 nn = da ? node_data[na].prev : node_data[na].next;
784 da = node_data[nn].prev != na;
787 nn = db ? node_data[nb].prev : node_data[nb].next;
788 db = node_data[nn].prev != nb;
793 Node rep = order_list[rn - order_list.size()];
794 Node parent = _ugraph.source(pred_map[rep]);
796 if (low_map[rep] < rorder) {
797 merge_roots[parent].push_back(rn);
799 merge_roots[parent].push_front(rn);
802 if (parent != root) {
803 na = nb = order_map[parent];
804 da = true; db = false;
812 void walkDown(int rn, int rorder, NodeData& node_data,
813 EdgeLists& edge_lists, FlipMap& flip_map,
814 OrderList& order_list, ChildLists& child_lists,
815 AncestorMap& ancestor_map, LowMap& low_map,
816 EmbedEdge& embed_edge, MergeRoots& merge_roots) {
818 std::vector<std::pair<int, bool> > merge_stack;
820 for (int di = 0; di < 2; ++di) {
823 int n = rd ? node_data[rn].next : node_data[rn].prev;
827 Node node = order_list[n];
829 if (embed_edge[node] != INVALID) {
831 // Merging components on the critical path
832 while (!merge_stack.empty()) {
835 int cn = merge_stack.back().first;
836 bool cd = merge_stack.back().second;
837 merge_stack.pop_back();
839 // Parent of component
840 int dn = merge_stack.back().first;
841 bool dd = merge_stack.back().second;
842 merge_stack.pop_back();
844 Node parent = order_list[dn];
846 // Erasing from merge_roots
847 merge_roots[parent].pop_front();
849 Node child = order_list[cn - order_list.size()];
851 // Erasing from child_lists
852 if (child_lists[child].prev != INVALID) {
853 child_lists[child_lists[child].prev].next =
854 child_lists[child].next;
856 child_lists[parent].first = child_lists[child].next;
859 if (child_lists[child].next != INVALID) {
860 child_lists[child_lists[child].next].prev =
861 child_lists[child].prev;
864 // Merging edges + flipping
865 Edge de = node_data[dn].first;
866 Edge ce = node_data[cn].first;
868 flip_map[order_list[cn - order_list.size()]] = cd != dd;
870 std::swap(edge_lists[ce].prev, edge_lists[ce].next);
871 ce = edge_lists[ce].prev;
872 std::swap(edge_lists[ce].prev, edge_lists[ce].next);
876 Edge dne = edge_lists[de].next;
877 Edge cne = edge_lists[ce].next;
879 edge_lists[de].next = cne;
880 edge_lists[ce].next = dne;
882 edge_lists[dne].prev = ce;
883 edge_lists[cne].prev = de;
887 node_data[dn].first = ce;
890 // Merging external faces
893 cn = cd ? node_data[cn].prev : node_data[cn].next;
894 cd = node_data[cn].next == en;
896 if (node_data[cn].prev == node_data[cn].next &&
897 node_data[cn].inverted) {
902 if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
903 if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
907 bool d = pn == node_data[n].prev;
909 if (node_data[n].prev == node_data[n].next &&
910 node_data[n].inverted) {
916 Edge edge = embed_edge[node];
917 Edge re = node_data[rn].first;
919 edge_lists[edge_lists[re].next].prev = edge;
920 edge_lists[edge].next = edge_lists[re].next;
921 edge_lists[edge].prev = re;
922 edge_lists[re].next = edge;
925 node_data[rn].first = edge;
928 Edge rev = _ugraph.oppositeEdge(edge);
929 Edge e = node_data[n].first;
931 edge_lists[edge_lists[e].next].prev = rev;
932 edge_lists[rev].next = edge_lists[e].next;
933 edge_lists[rev].prev = e;
934 edge_lists[e].next = rev;
937 node_data[n].first = rev;
942 // Embedding edge into external face
943 if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
944 if (d) node_data[n].prev = rn; else node_data[n].next = rn;
947 embed_edge[order_list[n]] = INVALID;
950 if (!merge_roots[node].empty()) {
952 bool d = pn == node_data[n].prev;
953 if (node_data[n].prev == node_data[n].next &&
954 node_data[n].inverted) {
958 merge_stack.push_back(std::make_pair(n, d));
960 int rn = merge_roots[node].front();
962 int xn = node_data[rn].next;
963 Node xnode = order_list[xn];
965 int yn = node_data[rn].prev;
966 Node ynode = order_list[yn];
969 if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
971 } else if (!external(ynode, rorder, child_lists,
972 ancestor_map, low_map)) {
974 } else if (pertinent(xnode, embed_edge, merge_roots)) {
980 merge_stack.push_back(std::make_pair(rn, rd));
985 } else if (!external(node, rorder, child_lists,
986 ancestor_map, low_map)) {
987 int nn = (node_data[n].next != pn ?
988 node_data[n].next : node_data[n].prev);
990 bool nd = n == node_data[nn].prev;
992 if (nd) node_data[nn].prev = pn;
993 else node_data[nn].next = pn;
995 if (n == node_data[pn].prev) node_data[pn].prev = nn;
996 else node_data[pn].next = nn;
998 node_data[nn].inverted =
999 (node_data[nn].prev == node_data[nn].next && nd != rd);
1007 if (!merge_stack.empty() || n == rn) {
1013 void initFace(const Node& node, EdgeLists& edge_lists,
1014 NodeData& node_data, const PredMap& pred_map,
1015 const OrderMap& order_map, const OrderList& order_list) {
1016 int n = order_map[node];
1017 int rn = n + order_list.size();
1019 node_data[n].next = node_data[n].prev = rn;
1020 node_data[rn].next = node_data[rn].prev = n;
1022 node_data[n].visited = order_list.size();
1023 node_data[rn].visited = order_list.size();
1025 node_data[n].inverted = false;
1026 node_data[rn].inverted = false;
1028 Edge edge = pred_map[node];
1029 Edge rev = _ugraph.oppositeEdge(edge);
1031 node_data[rn].first = edge;
1032 node_data[n].first = rev;
1034 edge_lists[edge].prev = edge;
1035 edge_lists[edge].next = edge;
1037 edge_lists[rev].prev = rev;
1038 edge_lists[rev].next = rev;
1042 void mergeRemainingFaces(const Node& node, NodeData& node_data,
1043 OrderList& order_list, OrderMap& order_map,
1044 ChildLists& child_lists, EdgeLists& edge_lists) {
1045 while (child_lists[node].first != INVALID) {
1046 int dd = order_map[node];
1047 Node child = child_lists[node].first;
1048 int cd = order_map[child] + order_list.size();
1049 child_lists[node].first = child_lists[child].next;
1051 Edge de = node_data[dd].first;
1052 Edge ce = node_data[cd].first;
1054 if (de != INVALID) {
1055 Edge dne = edge_lists[de].next;
1056 Edge cne = edge_lists[ce].next;
1058 edge_lists[de].next = cne;
1059 edge_lists[ce].next = dne;
1061 edge_lists[dne].prev = ce;
1062 edge_lists[cne].prev = de;
1065 node_data[dd].first = ce;
1070 void storeEmbedding(const Node& node, NodeData& node_data,
1071 OrderMap& order_map, PredMap& pred_map,
1072 EdgeLists& edge_lists, FlipMap& flip_map) {
1074 if (node_data[order_map[node]].first == INVALID) return;
1076 if (pred_map[node] != INVALID) {
1077 Node source = _ugraph.source(pred_map[node]);
1078 flip_map[node] = flip_map[node] != flip_map[source];
1081 Edge first = node_data[order_map[node]].first;
1084 Edge edge = flip_map[node] ?
1085 edge_lists[prev].prev : edge_lists[prev].next;
1087 _embedding[prev] = edge;
1089 while (edge != first) {
1090 Edge next = edge_lists[edge].prev == prev ?
1091 edge_lists[edge].next : edge_lists[edge].prev;
1092 prev = edge; edge = next;
1093 _embedding[prev] = edge;
1098 bool external(const Node& node, int rorder,
1099 ChildLists& child_lists, AncestorMap& ancestor_map,
1101 Node child = child_lists[node].first;
1103 if (child != INVALID) {
1104 if (low_map[child] < rorder) return true;
1107 if (ancestor_map[node] < rorder) return true;
1112 bool pertinent(const Node& node, const EmbedEdge& embed_edge,
1113 const MergeRoots& merge_roots) {
1114 return !merge_roots[node].empty() || embed_edge[node] != INVALID;
1117 int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
1118 AncestorMap& ancestor_map, LowMap& low_map) {
1121 Node child = child_lists[node].first;
1123 if (child != INVALID) {
1124 low_point = low_map[child];
1126 low_point = order_map[node];
1129 if (low_point > ancestor_map[node]) {
1130 low_point = ancestor_map[node];
1136 int findComponentRoot(Node root, Node node, ChildLists& child_lists,
1137 OrderMap& order_map, OrderList& order_list) {
1139 int order = order_map[root];
1140 int norder = order_map[node];
1142 Node child = child_lists[root].first;
1143 while (child != INVALID) {
1144 int corder = order_map[child];
1145 if (corder > order && corder < norder) {
1148 child = child_lists[child].next;
1150 return order + order_list.size();
1153 Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data,
1154 EmbedEdge& embed_edge, MergeRoots& merge_roots) {
1155 Node wnode =_ugraph.target(node_data[order_map[node]].first);
1156 while (!pertinent(wnode, embed_edge, merge_roots)) {
1157 wnode = _ugraph.target(node_data[order_map[wnode]].first);
1163 Node findExternal(Node node, int rorder, OrderMap& order_map,
1164 ChildLists& child_lists, AncestorMap& ancestor_map,
1165 LowMap& low_map, NodeData& node_data) {
1166 Node wnode =_ugraph.target(node_data[order_map[node]].first);
1167 while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
1168 wnode = _ugraph.target(node_data[order_map[wnode]].first);
1173 void markCommonPath(Node node, int rorder, Node& wnode, Node& znode,
1174 OrderList& order_list, OrderMap& order_map,
1175 NodeData& node_data, EdgeLists& edge_lists,
1176 EmbedEdge& embed_edge, MergeRoots& merge_roots,
1177 ChildLists& child_lists, AncestorMap& ancestor_map,
1181 Node pred = INVALID;
1185 bool pert = pertinent(cnode, embed_edge, merge_roots);
1186 bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
1189 if (!merge_roots[cnode].empty()) {
1190 int cn = merge_roots[cnode].back();
1192 if (low_map[order_list[cn - order_list.size()]] < rorder) {
1193 Edge edge = node_data[cn].first;
1194 _kuratowski.set(edge, true);
1197 cnode = _ugraph.target(edge);
1202 wnode = znode = cnode;
1208 while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
1209 Edge edge = node_data[order_map[cnode]].first;
1211 if (_ugraph.target(edge) == pred) {
1212 edge = edge_lists[edge].next;
1214 _kuratowski.set(edge, true);
1216 Node next = _ugraph.target(edge);
1217 pred = cnode; cnode = next;
1226 while (!pertinent(cnode, embed_edge, merge_roots)) {
1227 Edge edge = node_data[order_map[cnode]].first;
1229 if (_ugraph.target(edge) == pred) {
1230 edge = edge_lists[edge].next;
1232 _kuratowski.set(edge, true);
1234 Node next = _ugraph.target(edge);
1235 pred = cnode; cnode = next;
1242 Edge edge = node_data[order_map[cnode]].first;
1244 if (_ugraph.target(edge) == pred) {
1245 edge = edge_lists[edge].next;
1247 _kuratowski.set(edge, true);
1249 Node next = _ugraph.target(edge);
1250 pred = cnode; cnode = next;
1257 void orientComponent(Node root, int rn, OrderMap& order_map,
1258 PredMap& pred_map, NodeData& node_data,
1259 EdgeLists& edge_lists, FlipMap& flip_map,
1260 TypeMap& type_map) {
1261 node_data[order_map[root]].first = node_data[rn].first;
1264 std::vector<Node> st, qu;
1267 while (!st.empty()) {
1268 Node node = st.back();
1272 Edge edge = node_data[order_map[node]].first;
1274 if (type_map[_ugraph.target(edge)] == 0) {
1275 st.push_back(_ugraph.target(edge));
1276 type_map[_ugraph.target(edge)] = 1;
1279 Edge last = edge, pred = edge;
1280 edge = edge_lists[edge].next;
1281 while (edge != last) {
1283 if (type_map[_ugraph.target(edge)] == 0) {
1284 st.push_back(_ugraph.target(edge));
1285 type_map[_ugraph.target(edge)] = 1;
1288 Edge next = edge_lists[edge].next != pred ?
1289 edge_lists[edge].next : edge_lists[edge].prev;
1290 pred = edge; edge = next;
1296 flip_map[root] = false;
1298 for (int i = 1; i < int(qu.size()); ++i) {
1302 while (type_map[node] != 2) {
1305 node = _ugraph.source(pred_map[node]);
1308 bool flip = flip_map[node];
1310 while (!st.empty()) {
1314 flip_map[node] = flip != flip_map[node];
1315 flip = flip_map[node];
1318 Edge edge = node_data[order_map[node]].first;
1319 std::swap(edge_lists[edge].prev, edge_lists[edge].next);
1320 edge = edge_lists[edge].prev;
1321 std::swap(edge_lists[edge].prev, edge_lists[edge].next);
1322 node_data[order_map[node]].first = edge;
1327 for (int i = 0; i < int(qu.size()); ++i) {
1329 Edge edge = node_data[order_map[qu[i]]].first;
1330 Edge last = edge, pred = edge;
1332 edge = edge_lists[edge].next;
1333 while (edge != last) {
1335 if (edge_lists[edge].next == pred) {
1336 std::swap(edge_lists[edge].next, edge_lists[edge].prev);
1338 pred = edge; edge = edge_lists[edge].next;
1344 void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode,
1345 OrderMap& order_map, NodeData& node_data,
1346 TypeMap& type_map) {
1347 Node node = _ugraph.target(node_data[order_map[root]].first);
1349 while (node != ynode) {
1350 type_map[node] = HIGHY;
1351 node = _ugraph.target(node_data[order_map[node]].first);
1354 while (node != wnode) {
1355 type_map[node] = LOWY;
1356 node = _ugraph.target(node_data[order_map[node]].first);
1359 node = _ugraph.target(node_data[order_map[wnode]].first);
1361 while (node != xnode) {
1362 type_map[node] = LOWX;
1363 node = _ugraph.target(node_data[order_map[node]].first);
1365 type_map[node] = LOWX;
1367 node = _ugraph.target(node_data[order_map[xnode]].first);
1368 while (node != root) {
1369 type_map[node] = HIGHX;
1370 node = _ugraph.target(node_data[order_map[node]].first);
1373 type_map[wnode] = PERTINENT;
1374 type_map[root] = ROOT;
1377 void findInternalPath(std::vector<Edge>& ipath,
1378 Node wnode, Node root, TypeMap& type_map,
1379 OrderMap& order_map, NodeData& node_data,
1380 EdgeLists& edge_lists) {
1381 std::vector<Edge> st;
1385 while (node != root) {
1386 Edge edge = edge_lists[node_data[order_map[node]].first].next;
1388 node = _ugraph.target(edge);
1392 Edge edge = st.back();
1393 if (type_map[_ugraph.target(edge)] == LOWX ||
1394 type_map[_ugraph.target(edge)] == HIGHX) {
1397 if (type_map[_ugraph.target(edge)] == 2) {
1398 type_map[_ugraph.target(edge)] = 3;
1400 edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
1404 edge = edge_lists[edge].next;
1406 while (_ugraph.oppositeEdge(edge) == st.back()) {
1409 edge = edge_lists[edge].next;
1415 for (int i = 0; i < int(st.size()); ++i) {
1416 if (type_map[_ugraph.target(st[i])] != LOWY &&
1417 type_map[_ugraph.target(st[i])] != HIGHY) {
1418 for (; i < int(st.size()); ++i) {
1419 ipath.push_back(st[i]);
1425 void setInternalFlags(std::vector<Edge>& ipath, TypeMap& type_map) {
1426 for (int i = 1; i < int(ipath.size()); ++i) {
1427 type_map[_ugraph.source(ipath[i])] = INTERNAL;
1431 void findPilePath(std::vector<Edge>& ppath,
1432 Node root, TypeMap& type_map, OrderMap& order_map,
1433 NodeData& node_data, EdgeLists& edge_lists) {
1434 std::vector<Edge> st;
1436 st.push_back(_ugraph.oppositeEdge(node_data[order_map[root]].first));
1437 st.push_back(node_data[order_map[root]].first);
1439 while (st.size() > 1) {
1440 Edge edge = st.back();
1441 if (type_map[_ugraph.target(edge)] == INTERNAL) {
1444 if (type_map[_ugraph.target(edge)] == 3) {
1445 type_map[_ugraph.target(edge)] = 4;
1447 edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
1451 edge = edge_lists[edge].next;
1453 while (!st.empty() && _ugraph.oppositeEdge(edge) == st.back()) {
1456 edge = edge_lists[edge].next;
1462 for (int i = 1; i < int(st.size()); ++i) {
1463 ppath.push_back(st[i]);
1468 int markExternalPath(Node node, OrderMap& order_map,
1469 ChildLists& child_lists, PredMap& pred_map,
1470 AncestorMap& ancestor_map, LowMap& low_map) {
1471 int lp = lowPoint(node, order_map, child_lists,
1472 ancestor_map, low_map);
1474 if (ancestor_map[node] != lp) {
1475 node = child_lists[node].first;
1476 _kuratowski[pred_map[node]] = true;
1478 while (ancestor_map[node] != lp) {
1479 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
1480 Node tnode = _ugraph.target(e);
1481 if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) {
1483 _kuratowski[e] = true;
1490 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
1491 if (order_map[_ugraph.target(e)] == lp) {
1492 _kuratowski[e] = true;
1500 void markPertinentPath(Node node, OrderMap& order_map,
1501 NodeData& node_data, EdgeLists& edge_lists,
1502 EmbedEdge& embed_edge, MergeRoots& merge_roots) {
1503 while (embed_edge[node] == INVALID) {
1504 int n = merge_roots[node].front();
1505 Edge edge = node_data[n].first;
1507 _kuratowski.set(edge, true);
1510 node = _ugraph.target(edge);
1511 while (!pertinent(node, embed_edge, merge_roots)) {
1512 edge = node_data[order_map[node]].first;
1513 if (_ugraph.target(edge) == pred) {
1514 edge = edge_lists[edge].next;
1516 _kuratowski.set(edge, true);
1518 node = _ugraph.target(edge);
1521 _kuratowski.set(embed_edge[node], true);
1524 void markPredPath(Node node, Node snode, PredMap& pred_map) {
1525 while (node != snode) {
1526 _kuratowski.set(pred_map[node], true);
1527 node = _ugraph.source(pred_map[node]);
1531 void markFacePath(Node ynode, Node xnode,
1532 OrderMap& order_map, NodeData& node_data) {
1533 Edge edge = node_data[order_map[ynode]].first;
1534 Node node = _ugraph.target(edge);
1535 _kuratowski.set(edge, true);
1537 while (node != xnode) {
1538 edge = node_data[order_map[node]].first;
1539 _kuratowski.set(edge, true);
1540 node = _ugraph.target(edge);
1544 void markInternalPath(std::vector<Edge>& path) {
1545 for (int i = 0; i < int(path.size()); ++i) {
1546 _kuratowski.set(path[i], true);
1550 void markPilePath(std::vector<Edge>& path) {
1551 for (int i = 0; i < int(path.size()); ++i) {
1552 _kuratowski.set(path[i], true);
1556 void isolateKuratowski(Edge edge, NodeData& node_data,
1557 EdgeLists& edge_lists, FlipMap& flip_map,
1558 OrderMap& order_map, OrderList& order_list,
1559 PredMap& pred_map, ChildLists& child_lists,
1560 AncestorMap& ancestor_map, LowMap& low_map,
1561 EmbedEdge& embed_edge, MergeRoots& merge_roots) {
1563 Node root = _ugraph.source(edge);
1564 Node enode = _ugraph.target(edge);
1566 int rorder = order_map[root];
1568 TypeMap type_map(_ugraph, 0);
1570 int rn = findComponentRoot(root, enode, child_lists,
1571 order_map, order_list);
1573 Node xnode = order_list[node_data[rn].next];
1574 Node ynode = order_list[node_data[rn].prev];
1578 while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
1580 if (!merge_roots[xnode].empty()) {
1582 rn = merge_roots[xnode].front();
1585 rn = merge_roots[ynode].front();
1588 xnode = order_list[node_data[rn].next];
1589 ynode = order_list[node_data[rn].prev];
1592 if (root != _ugraph.source(edge)) {
1593 orientComponent(root, rn, order_map, pred_map,
1594 node_data, edge_lists, flip_map, type_map);
1595 markFacePath(root, root, order_map, node_data);
1596 int xlp = markExternalPath(xnode, order_map, child_lists,
1597 pred_map, ancestor_map, low_map);
1598 int ylp = markExternalPath(ynode, order_map, child_lists,
1599 pred_map, ancestor_map, low_map);
1600 markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1601 Node lwnode = findPertinent(ynode, order_map, node_data,
1602 embed_edge, merge_roots);
1604 markPertinentPath(lwnode, order_map, node_data, edge_lists,
1605 embed_edge, merge_roots);
1611 orientComponent(root, rn, order_map, pred_map,
1612 node_data, edge_lists, flip_map, type_map);
1614 Node wnode = findPertinent(ynode, order_map, node_data,
1615 embed_edge, merge_roots);
1616 setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map);
1620 if (!merge_roots[wnode].empty()) {
1621 int cn = merge_roots[wnode].back();
1622 Node rep = order_list[cn - order_list.size()];
1623 if (low_map[rep] < rorder) {
1624 markFacePath(root, root, order_map, node_data);
1625 int xlp = markExternalPath(xnode, order_map, child_lists,
1626 pred_map, ancestor_map, low_map);
1627 int ylp = markExternalPath(ynode, order_map, child_lists,
1628 pred_map, ancestor_map, low_map);
1630 Node lwnode, lznode;
1631 markCommonPath(wnode, rorder, lwnode, lznode, order_list,
1632 order_map, node_data, edge_lists, embed_edge,
1633 merge_roots, child_lists, ancestor_map, low_map);
1635 markPertinentPath(lwnode, order_map, node_data, edge_lists,
1636 embed_edge, merge_roots);
1637 int zlp = markExternalPath(lznode, order_map, child_lists,
1638 pred_map, ancestor_map, low_map);
1640 int minlp = xlp < ylp ? xlp : ylp;
1641 if (zlp < minlp) minlp = zlp;
1643 int maxlp = xlp > ylp ? xlp : ylp;
1644 if (zlp > maxlp) maxlp = zlp;
1646 markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1652 Node pxnode, pynode;
1653 std::vector<Edge> ipath;
1654 findInternalPath(ipath, wnode, root, type_map, order_map,
1655 node_data, edge_lists);
1656 setInternalFlags(ipath, type_map);
1657 pynode = _ugraph.source(ipath.front());
1658 pxnode = _ugraph.target(ipath.back());
1660 wnode = findPertinent(pynode, order_map, node_data,
1661 embed_edge, merge_roots);
1665 if (type_map[_ugraph.source(ipath.front())] == HIGHY) {
1666 if (type_map[_ugraph.target(ipath.back())] == HIGHX) {
1667 markFacePath(xnode, pxnode, order_map, node_data);
1669 markFacePath(root, xnode, order_map, node_data);
1670 markPertinentPath(wnode, order_map, node_data, edge_lists,
1671 embed_edge, merge_roots);
1672 markInternalPath(ipath);
1673 int xlp = markExternalPath(xnode, order_map, child_lists,
1674 pred_map, ancestor_map, low_map);
1675 int ylp = markExternalPath(ynode, order_map, child_lists,
1676 pred_map, ancestor_map, low_map);
1677 markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1681 if (type_map[_ugraph.target(ipath.back())] == HIGHX) {
1682 markFacePath(ynode, root, order_map, node_data);
1683 markPertinentPath(wnode, order_map, node_data, edge_lists,
1684 embed_edge, merge_roots);
1685 markInternalPath(ipath);
1686 int xlp = markExternalPath(xnode, order_map, child_lists,
1687 pred_map, ancestor_map, low_map);
1688 int ylp = markExternalPath(ynode, order_map, child_lists,
1689 pred_map, ancestor_map, low_map);
1690 markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1695 std::vector<Edge> ppath;
1696 findPilePath(ppath, root, type_map, order_map, node_data, edge_lists);
1699 if (!ppath.empty()) {
1700 markFacePath(ynode, xnode, order_map, node_data);
1701 markPertinentPath(wnode, order_map, node_data, edge_lists,
1702 embed_edge, merge_roots);
1703 markPilePath(ppath);
1704 markInternalPath(ipath);
1705 int xlp = markExternalPath(xnode, order_map, child_lists,
1706 pred_map, ancestor_map, low_map);
1707 int ylp = markExternalPath(ynode, order_map, child_lists,
1708 pred_map, ancestor_map, low_map);
1709 markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1716 if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
1717 Node znode = findExternal(pynode, rorder, order_map,
1718 child_lists, ancestor_map,
1719 low_map, node_data);
1721 if (type_map[znode] == LOWY) {
1722 markFacePath(root, xnode, order_map, node_data);
1723 markPertinentPath(wnode, order_map, node_data, edge_lists,
1724 embed_edge, merge_roots);
1725 markInternalPath(ipath);
1726 int xlp = markExternalPath(xnode, order_map, child_lists,
1727 pred_map, ancestor_map, low_map);
1728 int zlp = markExternalPath(znode, order_map, child_lists,
1729 pred_map, ancestor_map, low_map);
1730 markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map);
1732 markFacePath(ynode, root, order_map, node_data);
1733 markPertinentPath(wnode, order_map, node_data, edge_lists,
1734 embed_edge, merge_roots);
1735 markInternalPath(ipath);
1736 int ylp = markExternalPath(ynode, order_map, child_lists,
1737 pred_map, ancestor_map, low_map);
1738 int zlp = markExternalPath(znode, order_map, child_lists,
1739 pred_map, ancestor_map, low_map);
1740 markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map);
1745 int xlp = markExternalPath(xnode, order_map, child_lists,
1746 pred_map, ancestor_map, low_map);
1747 int ylp = markExternalPath(ynode, order_map, child_lists,
1748 pred_map, ancestor_map, low_map);
1749 int wlp = markExternalPath(wnode, order_map, child_lists,
1750 pred_map, ancestor_map, low_map);
1752 if (wlp > xlp && wlp > ylp) {
1753 markFacePath(root, root, order_map, node_data);
1754 markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
1758 markInternalPath(ipath);
1759 markPertinentPath(wnode, order_map, node_data, edge_lists,
1760 embed_edge, merge_roots);
1762 if (xlp > ylp && xlp > wlp) {
1763 markFacePath(root, pynode, order_map, node_data);
1764 markFacePath(wnode, xnode, order_map, node_data);
1765 markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map);
1769 if (ylp > xlp && ylp > wlp) {
1770 markFacePath(pxnode, root, order_map, node_data);
1771 markFacePath(ynode, wnode, order_map, node_data);
1772 markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map);
1776 if (pynode != ynode) {
1777 markFacePath(pxnode, wnode, order_map, node_data);
1779 int minlp = xlp < ylp ? xlp : ylp;
1780 if (wlp < minlp) minlp = wlp;
1782 int maxlp = xlp > ylp ? xlp : ylp;
1783 if (wlp > maxlp) maxlp = wlp;
1785 markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1789 if (pxnode != xnode) {
1790 markFacePath(wnode, pynode, order_map, node_data);
1792 int minlp = xlp < ylp ? xlp : ylp;
1793 if (wlp < minlp) minlp = wlp;
1795 int maxlp = xlp > ylp ? xlp : ylp;
1796 if (wlp > maxlp) maxlp = wlp;
1798 markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1802 markFacePath(root, root, order_map, node_data);
1803 int minlp = xlp < ylp ? xlp : ylp;
1804 if (wlp < minlp) minlp = wlp;
1805 markPredPath(root, order_list[minlp], pred_map);