COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/planarity.h @ 2480:eecaeab41472

Last change on this file since 2480:eecaeab41472 was 2480:eecaeab41472, checked in by Balazs Dezso, 12 years ago

Planarity checking and embedding

File size: 48.6 KB
Line 
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
34namespace 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    /// \param kuratowski If the parameter is false, then the
187    /// algorithm does not calculate the isolate Kuratowski
188    /// subdivisions.
189    /// \return %True when the graph is planar.
190    bool run(bool kuratowski = true) {
191      typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
192
193      PredMap pred_map(_ugraph, INVALID);
194      TreeMap tree_map(_ugraph, false);
195
196      OrderMap order_map(_ugraph, -1);
197      OrderList order_list;
198
199      AncestorMap ancestor_map(_ugraph, -1);
200      LowMap low_map(_ugraph, -1);
201
202      Visitor visitor(_ugraph, pred_map, tree_map,
203                      order_map, order_list, ancestor_map, low_map);
204      DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
205      visit.run();
206
207      ChildLists child_lists(_ugraph);
208      createChildLists(tree_map, order_map, low_map, child_lists);
209
210      NodeData node_data(2 * order_list.size());
211     
212      EmbedEdge embed_edge(_ugraph, false);
213
214      MergeRoots merge_roots(_ugraph);
215     
216      for (int i = order_list.size() - 1; i >= 0; --i) {
217
218        Node node = order_list[i];
219
220        Node source = node;
221        for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
222          Node target = _ugraph.target(e);
223         
224          if (order_map[source] < order_map[target] && tree_map[e]) {
225            initFace(target, node_data, pred_map, order_map, order_list);
226          }
227        }
228       
229        for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
230          Node target = _ugraph.target(e);
231         
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);
236          }
237        }
238
239        for (typename MergeRoots::Value::iterator it =
240               merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
241          int rn = *it;
242          walkDown(rn, i, node_data, order_list, child_lists,
243                   ancestor_map, low_map, embed_edge, merge_roots);
244        }
245        merge_roots[node].clear();
246       
247        for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
248          Node target = _ugraph.target(e);
249         
250          if (order_map[source] < order_map[target] && !tree_map[e]) {
251            if (embed_edge[target]) {
252              return false;
253            }
254          }
255        }
256      }
257
258      return true;
259    }
260   
261  private:
262
263    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
264                          const LowMap& low_map, ChildLists& child_lists) {
265
266      for (NodeIt n(_ugraph); n != INVALID; ++n) {
267        Node source = n;
268       
269        std::vector<Node> targets; 
270        for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
271          Node target = _ugraph.target(e);
272
273          if (order_map[source] < order_map[target] && tree_map[e]) {
274            targets.push_back(target);
275          }
276        }       
277
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;
284        } else {
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];
289          }
290          child_lists[targets.back()].next = INVALID;
291          child_lists[targets.front()].prev = INVALID;
292          child_lists[source].first = targets.front();
293        }
294      }
295    }
296
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) {
301
302      int na, nb;
303      bool da, db;
304     
305      na = nb = order_map[node];
306      da = true; db = false;
307     
308      while (true) {
309       
310        if (node_data[na].visited == rorder) break;
311        if (node_data[nb].visited == rorder) break;
312
313        node_data[na].visited = rorder;
314        node_data[nb].visited = rorder;
315
316        int rn = -1;
317
318        if (na >= int(order_list.size())) {
319          rn = na;
320        } else if (nb >= int(order_list.size())) {
321          rn = nb;
322        }
323
324        if (rn == -1) {
325          int nn;
326         
327          nn = da ? node_data[na].prev : node_data[na].next;
328          da = node_data[nn].prev != na;
329          na = nn;
330         
331          nn = db ? node_data[nb].prev : node_data[nb].next;
332          db = node_data[nn].prev != nb;
333          nb = nn;
334
335        } else {
336
337          Node rep = order_list[rn - order_list.size()];
338          Node parent = _ugraph.source(pred_map[rep]);
339
340          if (low_map[rep] < rorder) {
341            merge_roots[parent].push_back(rn);
342          } else {
343            merge_roots[parent].push_front(rn);
344          }
345         
346          if (parent != root) { 
347            na = nb = order_map[parent];
348            da = true; db = false;
349          } else {
350            break;
351          }
352        }       
353      }
354    }
355
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) {
360
361      std::vector<std::pair<int, bool> > merge_stack;
362
363      for (int di = 0; di < 2; ++di) {
364        bool rd = di == 0;
365        int pn = rn;
366        int n = rd ? node_data[rn].next : node_data[rn].prev;
367       
368        while (n != rn) {
369         
370          Node node = order_list[n];
371         
372          if (embed_edge[node]) {
373
374            // Merging components on the critical path
375            while (!merge_stack.empty()) {
376
377              // Component root
378              int cn = merge_stack.back().first;
379              bool cd = merge_stack.back().second;
380              merge_stack.pop_back();
381
382              // Parent of component
383              int dn = merge_stack.back().first;
384              bool dd = merge_stack.back().second;
385              merge_stack.pop_back();
386
387              Node parent = order_list[dn];
388
389              // Erasing from merge_roots
390              merge_roots[parent].pop_front();
391             
392              Node child = order_list[cn - order_list.size()];
393
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;
398              } else {
399                child_lists[parent].first = child_lists[child].next;
400              }
401             
402              if (child_lists[child].next != INVALID) {
403                child_lists[child_lists[child].next].prev =
404                  child_lists[child].prev;
405              }
406             
407              // Merging external faces
408              {
409                int en = cn;
410                cn = cd ? node_data[cn].prev : node_data[cn].next;
411                cd = node_data[cn].next == en;
412
413              }
414
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;
417
418            }
419
420            bool d = pn == node_data[n].prev;
421
422            if (node_data[n].prev == node_data[n].next &&
423                node_data[n].inverted) {
424              d = !d;
425            }
426
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;
430            pn = rn;
431
432            embed_edge[order_list[n]] = false;
433          }
434
435          if (!merge_roots[node].empty()) {
436
437            bool d = pn == node_data[n].prev;
438
439            merge_stack.push_back(std::make_pair(n, d));
440
441            int rn = merge_roots[node].front();
442           
443            int xn = node_data[rn].next;
444            Node xnode = order_list[xn];
445           
446            int yn = node_data[rn].prev;
447            Node ynode = order_list[yn];
448           
449            bool rd;
450            if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
451              rd = true;
452            } else if (!external(ynode, rorder, child_lists,
453                                 ancestor_map, low_map)) {
454              rd = false;
455            } else if (pertinent(xnode, embed_edge, merge_roots)) {
456              rd = true;
457            } else {
458              rd = false;
459            }
460           
461            merge_stack.push_back(std::make_pair(rn, rd));
462           
463            pn = rn;
464            n = rd ? xn : yn;         
465                   
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);
470
471            bool nd = n == node_data[nn].prev;
472
473            if (nd) node_data[nn].prev = pn;
474            else node_data[nn].next = pn;
475
476            if (n == node_data[pn].prev) node_data[pn].prev = nn;
477            else node_data[pn].next = nn;
478
479            node_data[nn].inverted =
480              (node_data[nn].prev == node_data[nn].next && nd != rd);
481
482            n = nn;
483          }
484          else break;
485         
486        }
487
488        if (!merge_stack.empty() || n == rn) {
489          break;
490        }
491      }
492    }
493
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();
499     
500      node_data[n].next = node_data[n].prev = rn;
501      node_data[rn].next = node_data[rn].prev = n;
502     
503      node_data[n].visited = order_list.size();
504      node_data[rn].visited = order_list.size();
505     
506    }
507
508    bool external(const Node& node, int rorder,
509                  ChildLists& child_lists, AncestorMap& ancestor_map,
510                  LowMap& low_map) {
511      Node child = child_lists[node].first;
512
513      if (child != INVALID) {
514        if (low_map[child] < rorder) return true;
515      }
516
517      if (ancestor_map[node] < rorder) return true;
518
519      return false;
520    }
521
522    bool pertinent(const Node& node, const EmbedEdge& embed_edge,
523                   const MergeRoots& merge_roots) {
524      return !merge_roots[node].empty() || embed_edge[node];
525    }
526
527  };
528
529  /// \ingroup graph_prop
530  ///
531  /// \brief Planar embedding of an undirected simple graph
532  ///
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.
540  ///
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 {
546  private:
547   
548    UGRAPH_TYPEDEFS(typename UGraph)
549     
550    const UGraph& _ugraph;
551    typename UGraph::template EdgeMap<Edge> _embedding;
552
553    typename UGraph::template UEdgeMap<bool> _kuratowski;
554
555  private:
556
557    typedef typename UGraph::template NodeMap<Edge> PredMap;
558   
559    typedef typename UGraph::template UEdgeMap<bool> TreeMap;
560
561    typedef typename UGraph::template NodeMap<int> OrderMap;
562    typedef std::vector<Node> OrderList;
563
564    typedef typename UGraph::template NodeMap<int> LowMap;
565    typedef typename UGraph::template NodeMap<int> AncestorMap;
566
567    typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
568    typedef std::vector<NodeDataNode> NodeData;
569   
570    typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
571    typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
572
573    typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
574 
575    typedef typename UGraph::template NodeMap<Edge> EmbedEdge;
576
577    typedef _planarity_bits::EdgeListNode<UGraph> EdgeListNode;
578    typedef typename UGraph::template EdgeMap<EdgeListNode> EdgeLists;
579
580    typedef typename UGraph::template NodeMap<bool> FlipMap;
581
582    typedef typename UGraph::template NodeMap<int> TypeMap;
583
584    enum IsolatorNodeType {
585      HIGHX = 6, LOWX = 7,
586      HIGHY = 8, LOWY = 9,
587      ROOT = 10, PERTINENT = 11,
588      INTERNAL = 12
589    };
590
591  public:
592
593    /// \brief Constructor
594    ///
595    /// \warining The graph should be simple, i.e. parallel and loop edge
596    /// free.
597    PlanarEmbedding(const UGraph& ugraph)
598      : _ugraph(ugraph), _embedding(_ugraph), _kuratowski(ugraph, false) {}
599
600    /// \brief Runs the algorithm.
601    ///
602    /// Runs the algorithm. 
603    /// \param kuratowski If the parameter is false, then the
604    /// algorithm does not calculate the isolate Kuratowski
605    /// subdivisions.
606    ///\return %True when the graph is planar.
607    bool run(bool kuratowski = true) {
608      typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
609
610      PredMap pred_map(_ugraph, INVALID);
611      TreeMap tree_map(_ugraph, false);
612
613      OrderMap order_map(_ugraph, -1);
614      OrderList order_list;
615
616      AncestorMap ancestor_map(_ugraph, -1);
617      LowMap low_map(_ugraph, -1);
618
619      Visitor visitor(_ugraph, pred_map, tree_map,
620                      order_map, order_list, ancestor_map, low_map);
621      DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
622      visit.run();
623
624      ChildLists child_lists(_ugraph);
625      createChildLists(tree_map, order_map, low_map, child_lists);
626
627      NodeData node_data(2 * order_list.size());
628     
629      EmbedEdge embed_edge(_ugraph, INVALID);
630
631      MergeRoots merge_roots(_ugraph);
632
633      EdgeLists edge_lists(_ugraph);
634
635      FlipMap flip_map(_ugraph, false);
636
637      for (int i = order_list.size() - 1; i >= 0; --i) {
638
639        Node node = order_list[i];
640
641        node_data[i].first = INVALID;
642       
643        Node source = node;
644        for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
645          Node target = _ugraph.target(e);
646         
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);
650          }
651        }
652       
653        for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
654          Node target = _ugraph.target(e);
655         
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);
660          }
661        }
662
663        for (typename MergeRoots::Value::iterator it =
664               merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
665          int rn = *it;
666          walkDown(rn, i, node_data, edge_lists, flip_map, order_list,
667                   child_lists, ancestor_map, low_map, embed_edge, merge_roots);
668        }
669        merge_roots[node].clear();
670       
671        for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
672          Node target = _ugraph.target(e);
673         
674          if (order_map[source] < order_map[target] && !tree_map[e]) {
675            if (embed_edge[target] != INVALID) {
676              if (kuratowski) {
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);
681              }
682              return false;
683            }
684          }
685        }
686      }
687
688      for (int i = 0; i < int(order_list.size()); ++i) {
689
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);
694      }
695
696      return true;
697    }
698
699    /// \brief Gives back the successor of an edge
700    ///
701    /// Gives back the successor of an edge. This function makes
702    /// possible to query the cyclic order of the outgoing edges from
703    /// a node.
704    Edge next(const Edge& edge) const {
705      return _embedding[edge];
706    }
707
708    /// \brief Gives back true when the undirected edge is in the
709    /// kuratowski subdivision
710    ///
711    /// Gives back true when the undirected edge is in the kuratowski
712    /// subdivision
713    bool kuratowski(const UEdge& uedge) {
714      return _kuratowski[uedge];
715    }
716
717  private:
718
719    void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
720                          const LowMap& low_map, ChildLists& child_lists) {
721
722      for (NodeIt n(_ugraph); n != INVALID; ++n) {
723        Node source = n;
724       
725        std::vector<Node> targets; 
726        for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
727          Node target = _ugraph.target(e);
728
729          if (order_map[source] < order_map[target] && tree_map[e]) {
730            targets.push_back(target);
731          }
732        }       
733
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;
740        } else {
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];
745          }
746          child_lists[targets.back()].next = INVALID;
747          child_lists[targets.front()].prev = INVALID;
748          child_lists[source].first = targets.front();
749        }
750      }
751    }
752
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) {
757
758      int na, nb;
759      bool da, db;
760     
761      na = nb = order_map[node];
762      da = true; db = false;
763     
764      while (true) {
765       
766        if (node_data[na].visited == rorder) break;
767        if (node_data[nb].visited == rorder) break;
768
769        node_data[na].visited = rorder;
770        node_data[nb].visited = rorder;
771
772        int rn = -1;
773
774        if (na >= int(order_list.size())) {
775          rn = na;
776        } else if (nb >= int(order_list.size())) {
777          rn = nb;
778        }
779
780        if (rn == -1) {
781          int nn;
782         
783          nn = da ? node_data[na].prev : node_data[na].next;
784          da = node_data[nn].prev != na;
785          na = nn;
786         
787          nn = db ? node_data[nb].prev : node_data[nb].next;
788          db = node_data[nn].prev != nb;
789          nb = nn;
790
791        } else {
792
793          Node rep = order_list[rn - order_list.size()];
794          Node parent = _ugraph.source(pred_map[rep]);
795
796          if (low_map[rep] < rorder) {
797            merge_roots[parent].push_back(rn);
798          } else {
799            merge_roots[parent].push_front(rn);
800          }
801         
802          if (parent != root) { 
803            na = nb = order_map[parent];
804            da = true; db = false;
805          } else {
806            break;
807          }
808        }       
809      }
810    }
811
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) {
817
818      std::vector<std::pair<int, bool> > merge_stack;
819
820      for (int di = 0; di < 2; ++di) {
821        bool rd = di == 0;
822        int pn = rn;
823        int n = rd ? node_data[rn].next : node_data[rn].prev;
824       
825        while (n != rn) {
826         
827          Node node = order_list[n];
828         
829          if (embed_edge[node] != INVALID) {
830
831            // Merging components on the critical path
832            while (!merge_stack.empty()) {
833
834              // Component root
835              int cn = merge_stack.back().first;
836              bool cd = merge_stack.back().second;
837              merge_stack.pop_back();
838
839              // Parent of component
840              int dn = merge_stack.back().first;
841              bool dd = merge_stack.back().second;
842              merge_stack.pop_back();
843
844              Node parent = order_list[dn];
845
846              // Erasing from merge_roots
847              merge_roots[parent].pop_front();
848             
849              Node child = order_list[cn - order_list.size()];
850
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;
855              } else {
856                child_lists[parent].first = child_lists[child].next;
857              }
858             
859              if (child_lists[child].next != INVALID) {
860                child_lists[child_lists[child].next].prev =
861                  child_lists[child].prev;
862              }
863
864              // Merging edges + flipping
865              Edge de = node_data[dn].first;
866              Edge ce = node_data[cn].first;
867
868              flip_map[order_list[cn - order_list.size()]] = cd != dd;
869              if (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);
873              }
874
875              {
876                Edge dne = edge_lists[de].next;
877                Edge cne = edge_lists[ce].next;
878
879                edge_lists[de].next = cne;
880                edge_lists[ce].next = dne;
881             
882                edge_lists[dne].prev = ce;
883                edge_lists[cne].prev = de;
884              }
885                     
886              if (dd) {
887                node_data[dn].first = ce;
888              }
889             
890              // Merging external faces
891              {
892                int en = cn;
893                cn = cd ? node_data[cn].prev : node_data[cn].next;
894                cd = node_data[cn].next == en;
895
896                if (node_data[cn].prev == node_data[cn].next &&
897                    node_data[cn].inverted) {
898                  cd = !cd;
899                }
900              }
901
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;
904
905            }
906
907            bool d = pn == node_data[n].prev;
908
909            if (node_data[n].prev == node_data[n].next &&
910                node_data[n].inverted) {
911              d = !d;
912            }
913
914            // Add new edge
915            {
916              Edge edge = embed_edge[node];
917              Edge re = node_data[rn].first;
918
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;
923
924              if (!rd) {
925                node_data[rn].first = edge;
926              }
927
928              Edge rev = _ugraph.oppositeEdge(edge);
929              Edge e = node_data[n].first;
930
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;
935
936              if (d) {
937                node_data[n].first = rev;
938              }
939             
940            }
941
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;
945            pn = rn;
946
947            embed_edge[order_list[n]] = INVALID;
948          }
949
950          if (!merge_roots[node].empty()) {
951
952            bool d = pn == node_data[n].prev;
953            if (node_data[n].prev == node_data[n].next &&
954                node_data[n].inverted) {
955              d = !d;
956            }
957
958            merge_stack.push_back(std::make_pair(n, d));
959
960            int rn = merge_roots[node].front();
961           
962            int xn = node_data[rn].next;
963            Node xnode = order_list[xn];
964           
965            int yn = node_data[rn].prev;
966            Node ynode = order_list[yn];
967           
968            bool rd;
969            if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
970              rd = true;
971            } else if (!external(ynode, rorder, child_lists,
972                                 ancestor_map, low_map)) {
973              rd = false;
974            } else if (pertinent(xnode, embed_edge, merge_roots)) {
975              rd = true;
976            } else {
977              rd = false;
978            }
979           
980            merge_stack.push_back(std::make_pair(rn, rd));
981           
982            pn = rn;
983            n = rd ? xn : yn;         
984                   
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);
989
990            bool nd = n == node_data[nn].prev;
991
992            if (nd) node_data[nn].prev = pn;
993            else node_data[nn].next = pn;
994
995            if (n == node_data[pn].prev) node_data[pn].prev = nn;
996            else node_data[pn].next = nn;
997
998            node_data[nn].inverted =
999              (node_data[nn].prev == node_data[nn].next && nd != rd);
1000
1001            n = nn;
1002          }
1003          else break;
1004         
1005        }
1006
1007        if (!merge_stack.empty() || n == rn) {
1008          break;
1009        }
1010      }
1011    }
1012
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();
1018     
1019      node_data[n].next = node_data[n].prev = rn;
1020      node_data[rn].next = node_data[rn].prev = n;
1021     
1022      node_data[n].visited = order_list.size();
1023      node_data[rn].visited = order_list.size();
1024
1025      node_data[n].inverted = false;
1026      node_data[rn].inverted = false;
1027
1028      Edge edge = pred_map[node];
1029      Edge rev = _ugraph.oppositeEdge(edge);
1030
1031      node_data[rn].first = edge;
1032      node_data[n].first = rev;
1033
1034      edge_lists[edge].prev = edge;
1035      edge_lists[edge].next = edge;
1036
1037      edge_lists[rev].prev = rev;
1038      edge_lists[rev].next = rev;
1039
1040    }
1041
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;
1050
1051        Edge de = node_data[dd].first;
1052        Edge ce = node_data[cd].first;
1053
1054        if (de != INVALID) {
1055          Edge dne = edge_lists[de].next;
1056          Edge cne = edge_lists[ce].next;
1057         
1058          edge_lists[de].next = cne;
1059          edge_lists[ce].next = dne;
1060         
1061          edge_lists[dne].prev = ce;
1062          edge_lists[cne].prev = de;
1063        }
1064       
1065        node_data[dd].first = ce;
1066
1067      }
1068    }
1069
1070    void storeEmbedding(const Node& node, NodeData& node_data,
1071                        OrderMap& order_map, PredMap& pred_map,
1072                        EdgeLists& edge_lists, FlipMap& flip_map) {
1073
1074      if (node_data[order_map[node]].first == INVALID) return;
1075
1076      if (pred_map[node] != INVALID) {
1077        Node source = _ugraph.source(pred_map[node]);
1078        flip_map[node] = flip_map[node] != flip_map[source];
1079      }
1080     
1081      Edge first = node_data[order_map[node]].first;
1082      Edge prev = first;
1083
1084      Edge edge = flip_map[node] ?
1085        edge_lists[prev].prev : edge_lists[prev].next;
1086
1087      _embedding[prev] = edge;
1088     
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;
1094      }
1095    }
1096
1097
1098    bool external(const Node& node, int rorder,
1099                  ChildLists& child_lists, AncestorMap& ancestor_map,
1100                  LowMap& low_map) {
1101      Node child = child_lists[node].first;
1102
1103      if (child != INVALID) {
1104        if (low_map[child] < rorder) return true;
1105      }
1106
1107      if (ancestor_map[node] < rorder) return true;
1108
1109      return false;
1110    }
1111
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;
1115    }
1116
1117    int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
1118                 AncestorMap& ancestor_map, LowMap& low_map) {
1119      int low_point;
1120
1121      Node child = child_lists[node].first;
1122
1123      if (child != INVALID) {
1124        low_point = low_map[child];
1125      } else {
1126        low_point = order_map[node];
1127      }
1128
1129      if (low_point > ancestor_map[node]) {
1130        low_point = ancestor_map[node];
1131      }
1132
1133      return low_point;
1134    }
1135
1136    int findComponentRoot(Node root, Node node, ChildLists& child_lists,
1137                          OrderMap& order_map, OrderList& order_list) {
1138
1139      int order = order_map[root];
1140      int norder = order_map[node];
1141
1142      Node child = child_lists[root].first;
1143      while (child != INVALID) {
1144        int corder = order_map[child];
1145        if (corder > order && corder < norder) {
1146          order = corder;
1147        }
1148        child = child_lists[child].next;
1149      }
1150      return order + order_list.size();
1151    }
1152
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);
1158      }
1159      return wnode;
1160    }
1161
1162
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);
1169      }
1170      return wnode;
1171    }
1172
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,
1178                        LowMap& low_map) {
1179     
1180      Node cnode = node;
1181      Node pred = INVALID;
1182     
1183      while (true) {
1184
1185        bool pert = pertinent(cnode, embed_edge, merge_roots);
1186        bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
1187
1188        if (pert && ext) {
1189          if (!merge_roots[cnode].empty()) {
1190            int cn = merge_roots[cnode].back();
1191           
1192            if (low_map[order_list[cn - order_list.size()]] < rorder) {
1193              Edge edge = node_data[cn].first;
1194              _kuratowski.set(edge, true);
1195             
1196              pred = cnode;
1197              cnode = _ugraph.target(edge);
1198           
1199              continue;
1200            }
1201          }
1202          wnode = znode = cnode;
1203          return;
1204
1205        } else if (pert) {
1206          wnode = cnode;
1207         
1208          while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
1209            Edge edge = node_data[order_map[cnode]].first;
1210         
1211            if (_ugraph.target(edge) == pred) {
1212              edge = edge_lists[edge].next;
1213            }
1214            _kuratowski.set(edge, true);
1215           
1216            Node next = _ugraph.target(edge);
1217            pred = cnode; cnode = next;
1218          }
1219         
1220          znode = cnode;
1221          return;
1222
1223        } else if (ext) {
1224          znode = cnode;
1225         
1226          while (!pertinent(cnode, embed_edge, merge_roots)) {
1227            Edge edge = node_data[order_map[cnode]].first;
1228         
1229            if (_ugraph.target(edge) == pred) {
1230              edge = edge_lists[edge].next;
1231            }
1232            _kuratowski.set(edge, true);
1233           
1234            Node next = _ugraph.target(edge);
1235            pred = cnode; cnode = next;
1236          }
1237         
1238          wnode = cnode;
1239          return;
1240         
1241        } else {
1242          Edge edge = node_data[order_map[cnode]].first;
1243         
1244          if (_ugraph.target(edge) == pred) {
1245            edge = edge_lists[edge].next;
1246          }
1247          _kuratowski.set(edge, true);
1248
1249          Node next = _ugraph.target(edge);
1250          pred = cnode; cnode = next;
1251        }
1252       
1253      }
1254
1255    }
1256
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;
1262      type_map[root] = 1;
1263
1264      std::vector<Node> st, qu;
1265
1266      st.push_back(root);
1267      while (!st.empty()) {
1268        Node node = st.back();
1269        st.pop_back();
1270        qu.push_back(node);
1271       
1272        Edge edge = node_data[order_map[node]].first;
1273       
1274        if (type_map[_ugraph.target(edge)] == 0) {
1275          st.push_back(_ugraph.target(edge));
1276          type_map[_ugraph.target(edge)] = 1;
1277        }
1278       
1279        Edge last = edge, pred = edge;
1280        edge = edge_lists[edge].next;
1281        while (edge != last) {
1282
1283          if (type_map[_ugraph.target(edge)] == 0) {
1284            st.push_back(_ugraph.target(edge));
1285            type_map[_ugraph.target(edge)] = 1;
1286          }
1287         
1288          Edge next = edge_lists[edge].next != pred ?
1289            edge_lists[edge].next : edge_lists[edge].prev;
1290          pred = edge; edge = next;
1291        }
1292
1293      }
1294
1295      type_map[root] = 2;
1296      flip_map[root] = false;
1297
1298      for (int i = 1; i < int(qu.size()); ++i) {
1299
1300        Node node = qu[i];
1301
1302        while (type_map[node] != 2) {
1303          st.push_back(node);
1304          type_map[node] = 2;
1305          node = _ugraph.source(pred_map[node]);
1306        }
1307
1308        bool flip = flip_map[node];
1309
1310        while (!st.empty()) {
1311          node = st.back();
1312          st.pop_back();
1313         
1314          flip_map[node] = flip != flip_map[node];
1315          flip = flip_map[node];
1316
1317          if (flip) {
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;
1323          }
1324        }
1325      }
1326
1327      for (int i = 0; i < int(qu.size()); ++i) {
1328
1329        Edge edge = node_data[order_map[qu[i]]].first;
1330        Edge last = edge, pred = edge;
1331
1332        edge = edge_lists[edge].next;
1333        while (edge != last) {
1334
1335          if (edge_lists[edge].next == pred) {
1336            std::swap(edge_lists[edge].next, edge_lists[edge].prev);
1337          }
1338          pred = edge; edge = edge_lists[edge].next;
1339        }
1340       
1341      }
1342    }
1343
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);
1348
1349      while (node != ynode) {
1350        type_map[node] = HIGHY;
1351        node = _ugraph.target(node_data[order_map[node]].first);
1352      }
1353
1354      while (node != wnode) {
1355        type_map[node] = LOWY;
1356        node = _ugraph.target(node_data[order_map[node]].first);
1357      }
1358     
1359      node = _ugraph.target(node_data[order_map[wnode]].first);
1360     
1361      while (node != xnode) {
1362        type_map[node] = LOWX;
1363        node = _ugraph.target(node_data[order_map[node]].first);
1364      }
1365      type_map[node] = LOWX;
1366
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);
1371      }
1372
1373      type_map[wnode] = PERTINENT;
1374      type_map[root] = ROOT;
1375    }
1376
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;
1382
1383      Node node = wnode;
1384     
1385      while (node != root) {
1386        Edge edge = edge_lists[node_data[order_map[node]].first].next;
1387        st.push_back(edge);
1388        node = _ugraph.target(edge);
1389      }
1390     
1391      while (true) {
1392        Edge edge = st.back();
1393        if (type_map[_ugraph.target(edge)] == LOWX ||
1394            type_map[_ugraph.target(edge)] == HIGHX) {
1395          break;
1396        }
1397        if (type_map[_ugraph.target(edge)] == 2) {
1398          type_map[_ugraph.target(edge)] = 3;
1399         
1400          edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
1401          st.push_back(edge);
1402        } else {
1403          st.pop_back();
1404          edge = edge_lists[edge].next;
1405         
1406          while (_ugraph.oppositeEdge(edge) == st.back()) {
1407            edge = st.back();
1408            st.pop_back();
1409            edge = edge_lists[edge].next;
1410          }
1411          st.push_back(edge);
1412        }
1413      }
1414     
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]);
1420          }
1421        }
1422      }
1423    }
1424
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;
1428      }
1429    }
1430
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;
1435
1436      st.push_back(_ugraph.oppositeEdge(node_data[order_map[root]].first));
1437      st.push_back(node_data[order_map[root]].first);
1438     
1439      while (st.size() > 1) {
1440        Edge edge = st.back();
1441        if (type_map[_ugraph.target(edge)] == INTERNAL) {
1442          break;
1443        }
1444        if (type_map[_ugraph.target(edge)] == 3) {
1445          type_map[_ugraph.target(edge)] = 4;
1446         
1447          edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
1448          st.push_back(edge);
1449        } else {
1450          st.pop_back();
1451          edge = edge_lists[edge].next;
1452         
1453          while (!st.empty() && _ugraph.oppositeEdge(edge) == st.back()) {
1454            edge = st.back();
1455            st.pop_back();
1456            edge = edge_lists[edge].next;
1457          }
1458          st.push_back(edge);
1459        }
1460      }
1461     
1462      for (int i = 1; i < int(st.size()); ++i) {
1463        ppath.push_back(st[i]);
1464      }
1465    }
1466
1467
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);
1473     
1474      if (ancestor_map[node] != lp) {
1475        node = child_lists[node].first;
1476        _kuratowski[pred_map[node]] = true;
1477
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) {
1482              node = tnode;
1483              _kuratowski[e] = true;
1484              break;
1485            }
1486          }
1487        }
1488      }
1489
1490      for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
1491        if (order_map[_ugraph.target(e)] == lp) {
1492          _kuratowski[e] = true;
1493          break;
1494        }
1495      }
1496     
1497      return lp;
1498    }
1499
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;
1506
1507        _kuratowski.set(edge, true);
1508       
1509        Node pred = node;
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;
1515          }
1516          _kuratowski.set(edge, true);
1517          pred = node;
1518          node = _ugraph.target(edge);
1519        }
1520      }
1521      _kuratowski.set(embed_edge[node], true);
1522    }
1523
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]);
1528      }
1529    }
1530
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);
1536       
1537      while (node != xnode) {
1538        edge = node_data[order_map[node]].first;
1539        _kuratowski.set(edge, true);
1540        node = _ugraph.target(edge);
1541      }
1542    }
1543
1544    void markInternalPath(std::vector<Edge>& path) {
1545      for (int i = 0; i < int(path.size()); ++i) {
1546        _kuratowski.set(path[i], true);
1547      }
1548    }
1549
1550    void markPilePath(std::vector<Edge>& path) {
1551      for (int i = 0; i < int(path.size()); ++i) {
1552        _kuratowski.set(path[i], true);
1553      }
1554    }
1555
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) {
1562
1563      Node root = _ugraph.source(edge);
1564      Node enode = _ugraph.target(edge);
1565
1566      int rorder = order_map[root];
1567
1568      TypeMap type_map(_ugraph, 0);
1569
1570      int rn = findComponentRoot(root, enode, child_lists,
1571                                 order_map, order_list);
1572
1573      Node xnode = order_list[node_data[rn].next];
1574      Node ynode = order_list[node_data[rn].prev];
1575
1576      // Minor-A
1577      {
1578        while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
1579         
1580          if (!merge_roots[xnode].empty()) {
1581            root = xnode;
1582            rn = merge_roots[xnode].front();
1583          } else {
1584            root = ynode;
1585            rn = merge_roots[ynode].front();
1586          }
1587         
1588          xnode = order_list[node_data[rn].next];
1589          ynode = order_list[node_data[rn].prev];
1590        }
1591       
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);
1603         
1604          markPertinentPath(lwnode, order_map, node_data, edge_lists,
1605                            embed_edge, merge_roots);
1606         
1607          return;
1608        }
1609      }
1610     
1611      orientComponent(root, rn, order_map, pred_map,
1612                      node_data, edge_lists, flip_map, type_map);
1613
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);
1617
1618     
1619      //Minor-B
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);
1629
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);
1634                 
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);
1639
1640          int minlp = xlp < ylp ? xlp : ylp;
1641          if (zlp < minlp) minlp = zlp;
1642
1643          int maxlp = xlp > ylp ? xlp : ylp;
1644          if (zlp > maxlp) maxlp = zlp;
1645         
1646          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1647         
1648          return;
1649        }
1650      }
1651
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());
1659
1660      wnode = findPertinent(pynode, order_map, node_data,
1661                            embed_edge, merge_roots);
1662     
1663      // Minor-C
1664      {
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);
1668          }
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);
1678          return;
1679        }
1680
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);
1691          return;
1692        }
1693      }
1694
1695      std::vector<Edge> ppath;
1696      findPilePath(ppath, root, type_map, order_map, node_data, edge_lists);
1697     
1698      // Minor-D
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);
1710        return;
1711      }
1712
1713      // Minor-E*
1714      {
1715
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);
1720         
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);
1731          } else {
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);
1741          }
1742          return;
1743        }
1744
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);
1751
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);
1755          return;
1756        }
1757
1758        markInternalPath(ipath);
1759        markPertinentPath(wnode, order_map, node_data, edge_lists,
1760                          embed_edge, merge_roots);
1761
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);
1766          return;
1767        }
1768
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);
1773          return;
1774        }
1775
1776        if (pynode != ynode) {
1777          markFacePath(pxnode, wnode, order_map, node_data);
1778
1779          int minlp = xlp < ylp ? xlp : ylp;
1780          if (wlp < minlp) minlp = wlp;
1781
1782          int maxlp = xlp > ylp ? xlp : ylp;
1783          if (wlp > maxlp) maxlp = wlp;
1784         
1785          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1786          return;
1787        }
1788
1789        if (pxnode != xnode) {
1790          markFacePath(wnode, pynode, order_map, node_data);
1791
1792          int minlp = xlp < ylp ? xlp : ylp;
1793          if (wlp < minlp) minlp = wlp;
1794
1795          int maxlp = xlp > ylp ? xlp : ylp;
1796          if (wlp > maxlp) maxlp = wlp;
1797         
1798          markPredPath(order_list[maxlp], order_list[minlp], pred_map);
1799          return;
1800        }
1801
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);
1806        return;
1807      }
1808     
1809    }
1810
1811  };
1812
1813}
1814
1815#endif
Note: See TracBrowser for help on using the repository browser.