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