COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/planarity.h @ 2481:ddb851e1481a

Last change on this file since 2481:ddb851e1481a was 2481:ddb851e1481a, checked in by Balazs Dezso, 17 years ago

Avoiding warnings

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