deba@2480: /* -*- C++ -*-
deba@2480:  *
deba@2480:  * This file is a part of LEMON, a generic C++ optimization library
deba@2480:  *
deba@2480:  * Copyright (C) 2003-2007
deba@2480:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2480:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2480:  *
deba@2480:  * Permission to use, modify and distribute this software is granted
deba@2480:  * provided that this copyright notice appears in all copies. For
deba@2480:  * precise terms see the accompanying LICENSE file.
deba@2480:  *
deba@2480:  * This software is provided "AS IS" with no warranty of any kind,
deba@2480:  * express or implied, and with no claim as to its suitability for any
deba@2480:  * purpose.
deba@2480:  *
deba@2480:  */
deba@2480: #ifndef LEMON_PLANARITY_H
deba@2480: #define LEMON_PLANARITY_H
deba@2480: 
deba@2499: /// \ingroup planar
deba@2480: /// \file
deba@2480: /// \brief Planarity checking, embedding
deba@2480: 
deba@2480: #include <vector>
deba@2480: #include <list>
deba@2480: 
deba@2480: #include <lemon/dfs.h>
deba@2480: #include <lemon/radix_sort.h>
deba@2480: #include <lemon/maps.h>
deba@2480: #include <lemon/path.h>
deba@2499: #include <lemon/iterable_maps.h>
deba@2499: #include <lemon/edge_set.h>
deba@2480: 
deba@2480: 
deba@2480: namespace lemon {
deba@2480: 
deba@2480:   namespace _planarity_bits {
deba@2480: 
deba@2480:     template <typename UGraph>
deba@2480:     struct PlanarityVisitor : DfsVisitor<UGraph> {
deba@2480: 
deba@2480:       typedef typename UGraph::Node Node;
deba@2480:       typedef typename UGraph::Edge Edge;
deba@2480: 
deba@2480:       typedef typename UGraph::template NodeMap<Edge> PredMap;
deba@2480: 
deba@2480:       typedef typename UGraph::template UEdgeMap<bool> TreeMap;
deba@2480: 
deba@2480:       typedef typename UGraph::template NodeMap<int> OrderMap;
deba@2480:       typedef std::vector<Node> OrderList;
deba@2480: 
deba@2480:       typedef typename UGraph::template NodeMap<int> LowMap;
deba@2480:       typedef typename UGraph::template NodeMap<int> AncestorMap;
deba@2480: 
deba@2480:       PlanarityVisitor(const UGraph& ugraph,
deba@2480: 		       PredMap& pred_map, TreeMap& tree_map,
deba@2480: 		       OrderMap& order_map, OrderList& order_list,
deba@2480: 		       AncestorMap& ancestor_map, LowMap& low_map)
deba@2480: 	: _ugraph(ugraph), _pred_map(pred_map), _tree_map(tree_map),
deba@2480: 	  _order_map(order_map), _order_list(order_list),
deba@2480: 	  _ancestor_map(ancestor_map), _low_map(low_map) {}
deba@2480:       
deba@2480:       void reach(const Node& node) {
deba@2480: 	_order_map[node] = _order_list.size();
deba@2480: 	_low_map[node] = _order_list.size();
deba@2480: 	_ancestor_map[node] = _order_list.size();
deba@2480: 	_order_list.push_back(node);
deba@2480:       }
deba@2480: 
deba@2480:       void discover(const Edge& edge) {
deba@2480: 	Node source = _ugraph.source(edge);
deba@2480: 	Node target = _ugraph.target(edge);
deba@2480: 
deba@2480: 	_tree_map[edge] = true;
deba@2480: 	_pred_map[target] = edge;
deba@2480:       }
deba@2480: 
deba@2480:       void examine(const Edge& edge) {
deba@2480: 	Node source = _ugraph.source(edge);
deba@2480: 	Node target = _ugraph.target(edge);
deba@2480: 	
deba@2480: 	if (_order_map[target] < _order_map[source] && !_tree_map[edge]) {
deba@2480: 	  if (_low_map[source] > _order_map[target]) {
deba@2480: 	    _low_map[source] = _order_map[target];
deba@2480: 	  }
deba@2480: 	  if (_ancestor_map[source] > _order_map[target]) {
deba@2480: 	    _ancestor_map[source] = _order_map[target];
deba@2480: 	  }
deba@2480: 	}
deba@2480:       }
deba@2480: 
deba@2480:       void backtrack(const Edge& edge) {
deba@2480: 	Node source = _ugraph.source(edge);
deba@2480: 	Node target = _ugraph.target(edge);
deba@2480: 
deba@2480: 	if (_low_map[source] > _low_map[target]) {
deba@2480: 	  _low_map[source] = _low_map[target];
deba@2480: 	}
deba@2480:       }
deba@2480: 
deba@2480:       const UGraph& _ugraph;
deba@2480:       PredMap& _pred_map;
deba@2480:       TreeMap& _tree_map;
deba@2480:       OrderMap& _order_map;
deba@2480:       OrderList& _order_list;
deba@2480:       AncestorMap& _ancestor_map;
deba@2480:       LowMap& _low_map;
deba@2480:     };
deba@2480: 
deba@2480:     template <typename UGraph, bool embedding = true>
deba@2480:     struct NodeDataNode {
deba@2480:       int prev, next;
deba@2480:       int visited;
deba@2480:       typename UGraph::Edge first;
deba@2480:       bool inverted;
deba@2480:     };
deba@2480: 
deba@2480:     template <typename UGraph>
deba@2480:     struct NodeDataNode<UGraph, false> {
deba@2480:       int prev, next;
deba@2480:       int visited;
deba@2480:     };
deba@2480: 
deba@2480:     template <typename UGraph>
deba@2480:     struct ChildListNode {
deba@2480:       typedef typename UGraph::Node Node;
deba@2480:       Node first;
deba@2480:       Node prev, next;
deba@2480:     };
deba@2480: 
deba@2480:     template <typename UGraph>
deba@2480:     struct EdgeListNode {
deba@2480:       typename UGraph::Edge prev, next;
deba@2480:     };
deba@2480: 
deba@2480:   }
deba@2480: 
deba@2499:   /// \ingroup planar
deba@2480:   ///
deba@2480:   /// \brief Planarity checking of an undirected simple graph
deba@2480:   ///
deba@2499:   /// This class implements the Boyer-Myrvold algorithm for planarity
deba@2480:   /// checking of an undirected graph. This class is a simplified
deba@2480:   /// version of the PlanarEmbedding algorithm class, and it does
deba@2480:   /// provide neither embedding nor kuratowski subdivisons.
deba@2480:   template <typename UGraph>
deba@2480:   class PlanarityChecking {
deba@2480:   private:
deba@2480:     
deba@2499:     UGRAPH_TYPEDEFS(typename UGraph);
deba@2480:       
deba@2480:     const UGraph& _ugraph;
deba@2480: 
deba@2480:   private:
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<Edge> PredMap;
deba@2480:     
deba@2480:     typedef typename UGraph::template UEdgeMap<bool> TreeMap;
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<int> OrderMap;
deba@2480:     typedef std::vector<Node> OrderList;
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<int> LowMap;
deba@2480:     typedef typename UGraph::template NodeMap<int> AncestorMap;
deba@2480: 
deba@2480:     typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
deba@2480:     typedef std::vector<NodeDataNode> NodeData;
deba@2480:     
deba@2480:     typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
deba@2480:     typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
deba@2480:  
deba@2480:     typedef typename UGraph::template NodeMap<bool> EmbedEdge;
deba@2480: 
deba@2480:   public:
deba@2480: 
deba@2480:     /// \brief Constructor
deba@2480:     ///
deba@2480:     /// \warining The graph should be simple, i.e. parallel and loop edge
deba@2480:     /// free.
deba@2480:     PlanarityChecking(const UGraph& ugraph) : _ugraph(ugraph) {}
deba@2480: 
deba@2480:     /// \brief Runs the algorithm.
deba@2480:     ///
deba@2480:     /// Runs the algorithm.  
deba@2480:     /// \return %True when the graph is planar.
deba@2481:     bool run() {
deba@2480:       typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
deba@2480: 
deba@2480:       PredMap pred_map(_ugraph, INVALID);
deba@2480:       TreeMap tree_map(_ugraph, false);
deba@2480: 
deba@2480:       OrderMap order_map(_ugraph, -1);
deba@2480:       OrderList order_list;
deba@2480: 
deba@2480:       AncestorMap ancestor_map(_ugraph, -1);
deba@2480:       LowMap low_map(_ugraph, -1);
deba@2480: 
deba@2480:       Visitor visitor(_ugraph, pred_map, tree_map,
deba@2480: 		      order_map, order_list, ancestor_map, low_map);
deba@2480:       DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
deba@2480:       visit.run();
deba@2480: 
deba@2480:       ChildLists child_lists(_ugraph);
deba@2480:       createChildLists(tree_map, order_map, low_map, child_lists);
deba@2480: 
deba@2480:       NodeData node_data(2 * order_list.size());
deba@2480:       
deba@2480:       EmbedEdge embed_edge(_ugraph, false);
deba@2480: 
deba@2480:       MergeRoots merge_roots(_ugraph);
deba@2480:       
deba@2480:       for (int i = order_list.size() - 1; i >= 0; --i) {
deba@2480: 
deba@2480: 	Node node = order_list[i];
deba@2480: 
deba@2480: 	Node source = node;
deba@2480: 	for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
deba@2480: 	  Node target = _ugraph.target(e);
deba@2480: 	  
deba@2480: 	  if (order_map[source] < order_map[target] && tree_map[e]) {
deba@2481: 	    initFace(target, node_data, order_map, order_list);
deba@2480: 	  }
deba@2480: 	}
deba@2480: 	
deba@2480: 	for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
deba@2480: 	  Node target = _ugraph.target(e);
deba@2480: 	  
deba@2480: 	  if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@2480: 	    embed_edge[target] = true;
deba@2480: 	    walkUp(target, source, i, pred_map, low_map,
deba@2480: 		   order_map, order_list, node_data, merge_roots);
deba@2480: 	  }
deba@2480: 	}
deba@2480: 
deba@2480: 	for (typename MergeRoots::Value::iterator it = 
deba@2480: 	       merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
deba@2480: 	  int rn = *it;
deba@2480: 	  walkDown(rn, i, node_data, order_list, child_lists, 
deba@2480: 		   ancestor_map, low_map, embed_edge, merge_roots);
deba@2480: 	}
deba@2480: 	merge_roots[node].clear();
deba@2480: 	
deba@2480: 	for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
deba@2480: 	  Node target = _ugraph.target(e);
deba@2480: 	  
deba@2480: 	  if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@2480: 	    if (embed_edge[target]) {
deba@2480: 	      return false;
deba@2480: 	    }
deba@2480: 	  }
deba@2480: 	}
deba@2480:       }
deba@2480: 
deba@2480:       return true;
deba@2480:     }
deba@2480:     
deba@2480:   private:
deba@2480: 
deba@2480:     void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
deba@2480: 			  const LowMap& low_map, ChildLists& child_lists) {
deba@2480: 
deba@2480:       for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2480: 	Node source = n;
deba@2480: 	
deba@2480: 	std::vector<Node> targets;  
deba@2480: 	for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
deba@2480: 	  Node target = _ugraph.target(e);
deba@2480: 
deba@2480: 	  if (order_map[source] < order_map[target] && tree_map[e]) {
deba@2480: 	    targets.push_back(target);
deba@2480: 	  }
deba@2480: 	}	
deba@2480: 
deba@2480: 	if (targets.size() == 0) {
deba@2480: 	  child_lists[source].first = INVALID;
deba@2480: 	} else if (targets.size() == 1) {
deba@2480: 	  child_lists[source].first = targets[0];
deba@2480: 	  child_lists[targets[0]].prev = INVALID;
deba@2480: 	  child_lists[targets[0]].next = INVALID;
deba@2480: 	} else {
deba@2480: 	  radixSort(targets.begin(), targets.end(), mapFunctor(low_map));
deba@2480: 	  for (int i = 1; i < int(targets.size()); ++i) {
deba@2480: 	    child_lists[targets[i]].prev = targets[i - 1];
deba@2480: 	    child_lists[targets[i - 1]].next = targets[i];
deba@2480: 	  }
deba@2480: 	  child_lists[targets.back()].next = INVALID; 
deba@2480: 	  child_lists[targets.front()].prev = INVALID;
deba@2480: 	  child_lists[source].first = targets.front();
deba@2480: 	}
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void walkUp(const Node& node, Node root, int rorder,
deba@2480: 		const PredMap& pred_map, const LowMap& low_map,
deba@2480: 		const OrderMap& order_map, const OrderList& order_list,
deba@2480: 		NodeData& node_data, MergeRoots& merge_roots) {
deba@2480: 
deba@2480:       int na, nb;
deba@2480:       bool da, db;
deba@2480:       
deba@2480:       na = nb = order_map[node];
deba@2480:       da = true; db = false;
deba@2480:       
deba@2480:       while (true) {
deba@2480: 	
deba@2480: 	if (node_data[na].visited == rorder) break;
deba@2480: 	if (node_data[nb].visited == rorder) break;
deba@2480: 
deba@2480: 	node_data[na].visited = rorder;
deba@2480: 	node_data[nb].visited = rorder;
deba@2480: 
deba@2480: 	int rn = -1;
deba@2480: 
deba@2480: 	if (na >= int(order_list.size())) {
deba@2480: 	  rn = na;
deba@2480: 	} else if (nb >= int(order_list.size())) {
deba@2480: 	  rn = nb;
deba@2480: 	}
deba@2480: 
deba@2480: 	if (rn == -1) {
deba@2480: 	  int nn;
deba@2480: 	  
deba@2480: 	  nn = da ? node_data[na].prev : node_data[na].next;
deba@2480: 	  da = node_data[nn].prev != na;
deba@2480: 	  na = nn;
deba@2480: 	  
deba@2480: 	  nn = db ? node_data[nb].prev : node_data[nb].next;
deba@2480: 	  db = node_data[nn].prev != nb;
deba@2480: 	  nb = nn;
deba@2480: 
deba@2480: 	} else {
deba@2480: 
deba@2480: 	  Node rep = order_list[rn - order_list.size()];
deba@2480: 	  Node parent = _ugraph.source(pred_map[rep]);
deba@2480: 
deba@2480: 	  if (low_map[rep] < rorder) {
deba@2480: 	    merge_roots[parent].push_back(rn);
deba@2480: 	  } else {
deba@2480: 	    merge_roots[parent].push_front(rn);
deba@2480: 	  }
deba@2480: 	  
deba@2480: 	  if (parent != root) {  
deba@2480: 	    na = nb = order_map[parent];
deba@2480: 	    da = true; db = false;
deba@2480: 	  } else {
deba@2480: 	    break;
deba@2480: 	  }
deba@2480: 	}	
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void walkDown(int rn, int rorder, NodeData& node_data,
deba@2480: 		  OrderList& order_list, ChildLists& child_lists,
deba@2480: 		  AncestorMap& ancestor_map, LowMap& low_map,
deba@2480: 		  EmbedEdge& embed_edge, MergeRoots& merge_roots) {
deba@2480: 
deba@2480:       std::vector<std::pair<int, bool> > merge_stack;
deba@2480: 
deba@2480:       for (int di = 0; di < 2; ++di) {
deba@2480: 	bool rd = di == 0;
deba@2480: 	int pn = rn;
deba@2480: 	int n = rd ? node_data[rn].next : node_data[rn].prev;
deba@2480: 	
deba@2480: 	while (n != rn) {
deba@2480: 	  
deba@2480: 	  Node node = order_list[n];
deba@2480: 	  
deba@2480: 	  if (embed_edge[node]) {
deba@2480: 
deba@2480: 	    // Merging components on the critical path
deba@2480: 	    while (!merge_stack.empty()) {
deba@2480: 
deba@2480: 	      // Component root
deba@2480: 	      int cn = merge_stack.back().first;
deba@2480: 	      bool cd = merge_stack.back().second;
deba@2480: 	      merge_stack.pop_back();
deba@2480: 
deba@2480: 	      // Parent of component
deba@2480: 	      int dn = merge_stack.back().first;
deba@2480: 	      bool dd = merge_stack.back().second;
deba@2480: 	      merge_stack.pop_back();
deba@2480: 
deba@2480: 	      Node parent = order_list[dn];
deba@2480: 
deba@2480: 	      // Erasing from merge_roots
deba@2480: 	      merge_roots[parent].pop_front();
deba@2480: 	      
deba@2480: 	      Node child = order_list[cn - order_list.size()];
deba@2480: 
deba@2480: 	      // Erasing from child_lists
deba@2480: 	      if (child_lists[child].prev != INVALID) {
deba@2480: 		child_lists[child_lists[child].prev].next =
deba@2480: 		  child_lists[child].next;
deba@2480: 	      } else {
deba@2480: 		child_lists[parent].first = child_lists[child].next;
deba@2480: 	      }
deba@2480: 	      
deba@2480: 	      if (child_lists[child].next != INVALID) {
deba@2480: 		child_lists[child_lists[child].next].prev =
deba@2480: 		  child_lists[child].prev;
deba@2480: 	      }
deba@2480: 	      
deba@2480: 	      // Merging external faces
deba@2480: 	      {
deba@2480: 		int en = cn;
deba@2480: 		cn = cd ? node_data[cn].prev : node_data[cn].next;
deba@2480: 		cd = node_data[cn].next == en;
deba@2480: 
deba@2480: 	      }
deba@2480: 
deba@2480: 	      if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
deba@2480: 	      if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
deba@2480: 
deba@2480: 	    }
deba@2480: 
deba@2480: 	    bool d = pn == node_data[n].prev;
deba@2480: 
deba@2480: 	    if (node_data[n].prev == node_data[n].next && 
deba@2480: 		node_data[n].inverted) {
deba@2480: 	      d = !d;
deba@2480: 	    }
deba@2480: 
deba@2480: 	    // Embedding edge into external face
deba@2480: 	    if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
deba@2480: 	    if (d) node_data[n].prev = rn; else node_data[n].next = rn;
deba@2480: 	    pn = rn;
deba@2480: 
deba@2480: 	    embed_edge[order_list[n]] = false;
deba@2480: 	  }
deba@2480: 
deba@2480: 	  if (!merge_roots[node].empty()) {
deba@2480: 
deba@2480: 	    bool d = pn == node_data[n].prev;
deba@2480: 
deba@2480: 	    merge_stack.push_back(std::make_pair(n, d));
deba@2480: 
deba@2480: 	    int rn = merge_roots[node].front();
deba@2480: 	    
deba@2480: 	    int xn = node_data[rn].next;
deba@2480: 	    Node xnode = order_list[xn];
deba@2480: 	    
deba@2480: 	    int yn = node_data[rn].prev;
deba@2480: 	    Node ynode = order_list[yn];
deba@2480: 	    
deba@2480: 	    bool rd;
deba@2480: 	    if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
deba@2480: 	      rd = true;
deba@2480: 	    } else if (!external(ynode, rorder, child_lists, 
deba@2480: 				 ancestor_map, low_map)) {
deba@2480: 	      rd = false;
deba@2480: 	    } else if (pertinent(xnode, embed_edge, merge_roots)) {
deba@2480: 	      rd = true;
deba@2480: 	    } else {
deba@2480: 	      rd = false;
deba@2480: 	    }
deba@2480: 	    
deba@2480: 	    merge_stack.push_back(std::make_pair(rn, rd));
deba@2480: 	    
deba@2480: 	    pn = rn;
deba@2480: 	    n = rd ? xn : yn;	      
deba@2480: 	    	    
deba@2480: 	  } else if (!external(node, rorder, child_lists,
deba@2480: 			       ancestor_map, low_map)) {
deba@2480: 	    int nn = (node_data[n].next != pn ? 
deba@2480: 		      node_data[n].next : node_data[n].prev);
deba@2480: 
deba@2480: 	    bool nd = n == node_data[nn].prev;
deba@2480: 
deba@2480: 	    if (nd) node_data[nn].prev = pn;
deba@2480: 	    else node_data[nn].next = pn; 
deba@2480: 
deba@2480: 	    if (n == node_data[pn].prev) node_data[pn].prev = nn;
deba@2480: 	    else node_data[pn].next = nn;
deba@2480: 
deba@2480: 	    node_data[nn].inverted = 
deba@2480: 	      (node_data[nn].prev == node_data[nn].next && nd != rd);
deba@2480: 
deba@2480: 	    n = nn;
deba@2480: 	  }
deba@2480: 	  else break;
deba@2480: 	  
deba@2480: 	}
deba@2480: 
deba@2480: 	if (!merge_stack.empty() || n == rn) {
deba@2480: 	  break;
deba@2480: 	}
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void initFace(const Node& node, NodeData& node_data, 
deba@2481: 		  const OrderMap& order_map, const OrderList& order_list) {
deba@2480:       int n = order_map[node];
deba@2480:       int rn = n + order_list.size();
deba@2480:       
deba@2480:       node_data[n].next = node_data[n].prev = rn;
deba@2480:       node_data[rn].next = node_data[rn].prev = n;
deba@2480:       
deba@2480:       node_data[n].visited = order_list.size();
deba@2480:       node_data[rn].visited = order_list.size();
deba@2480:       
deba@2480:     }
deba@2480: 
deba@2480:     bool external(const Node& node, int rorder,
deba@2480: 		  ChildLists& child_lists, AncestorMap& ancestor_map, 
deba@2480: 		  LowMap& low_map) {
deba@2480:       Node child = child_lists[node].first;
deba@2480: 
deba@2480:       if (child != INVALID) {
deba@2480: 	if (low_map[child] < rorder) return true;
deba@2480:       }
deba@2480: 
deba@2480:       if (ancestor_map[node] < rorder) return true;
deba@2480: 
deba@2480:       return false;
deba@2480:     }
deba@2480: 
deba@2480:     bool pertinent(const Node& node, const EmbedEdge& embed_edge,
deba@2480: 		   const MergeRoots& merge_roots) {
deba@2480:       return !merge_roots[node].empty() || embed_edge[node];
deba@2480:     }
deba@2480: 
deba@2480:   };
deba@2480: 
deba@2499:   /// \ingroup planar
deba@2480:   ///
deba@2480:   /// \brief Planar embedding of an undirected simple graph
deba@2480:   ///
deba@2480:   /// This class implements the Boyer-Myrvold algorithm for planar
deba@2480:   /// embedding of an undirected graph. The planar embeding is an
deba@2480:   /// ordering of the outgoing edges in each node, which is a possible
deba@2480:   /// configuration to draw the graph in the plane. If there is not
deba@2480:   /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
deba@2480:   /// with 5 nodes) or an \f$ K_{3,3} \f$ (complete bipartite graph on
deba@2480:   /// 3 ANode and 3 BNode) subdivision.
deba@2480:   ///
deba@2480:   /// The current implementation calculates an embedding or an
deba@2480:   /// Kuratowski subdivision if the graph is not planar. The running
deba@2480:   /// time of the algorithm is \f$ O(n) \f$.
deba@2480:   template <typename UGraph>
deba@2480:   class PlanarEmbedding {
deba@2480:   private:
deba@2480:     
deba@2499:     UGRAPH_TYPEDEFS(typename UGraph);
deba@2480:       
deba@2480:     const UGraph& _ugraph;
deba@2480:     typename UGraph::template EdgeMap<Edge> _embedding;
deba@2480: 
deba@2480:     typename UGraph::template UEdgeMap<bool> _kuratowski;
deba@2480: 
deba@2480:   private:
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<Edge> PredMap;
deba@2480:     
deba@2480:     typedef typename UGraph::template UEdgeMap<bool> TreeMap;
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<int> OrderMap;
deba@2480:     typedef std::vector<Node> OrderList;
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<int> LowMap;
deba@2480:     typedef typename UGraph::template NodeMap<int> AncestorMap;
deba@2480: 
deba@2480:     typedef _planarity_bits::NodeDataNode<UGraph> NodeDataNode;
deba@2480:     typedef std::vector<NodeDataNode> NodeData;
deba@2480:     
deba@2480:     typedef _planarity_bits::ChildListNode<UGraph> ChildListNode;
deba@2480:     typedef typename UGraph::template NodeMap<ChildListNode> ChildLists;
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<std::list<int> > MergeRoots;
deba@2480:  
deba@2480:     typedef typename UGraph::template NodeMap<Edge> EmbedEdge;
deba@2480: 
deba@2480:     typedef _planarity_bits::EdgeListNode<UGraph> EdgeListNode;
deba@2480:     typedef typename UGraph::template EdgeMap<EdgeListNode> EdgeLists;
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<bool> FlipMap;
deba@2480: 
deba@2480:     typedef typename UGraph::template NodeMap<int> TypeMap;
deba@2480: 
deba@2480:     enum IsolatorNodeType {
deba@2480:       HIGHX = 6, LOWX = 7,
deba@2480:       HIGHY = 8, LOWY = 9,
deba@2480:       ROOT = 10, PERTINENT = 11,
deba@2480:       INTERNAL = 12
deba@2480:     };
deba@2480: 
deba@2480:   public:
deba@2480: 
deba@2499:     /// \brief The map for store of embedding
deba@2499:     typedef typename UGraph::template EdgeMap<Edge> EmbeddingMap;
deba@2499: 
deba@2480:     /// \brief Constructor
deba@2480:     ///
deba@2480:     /// \warining The graph should be simple, i.e. parallel and loop edge
deba@2480:     /// free.
deba@2480:     PlanarEmbedding(const UGraph& ugraph)
deba@2480:       : _ugraph(ugraph), _embedding(_ugraph), _kuratowski(ugraph, false) {}
deba@2480: 
deba@2480:     /// \brief Runs the algorithm.
deba@2480:     ///
deba@2480:     /// Runs the algorithm.  
deba@2480:     /// \param kuratowski If the parameter is false, then the
deba@2480:     /// algorithm does not calculate the isolate Kuratowski
deba@2480:     /// subdivisions.
deba@2480:     ///\return %True when the graph is planar.
deba@2480:     bool run(bool kuratowski = true) {
deba@2480:       typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor;
deba@2480: 
deba@2480:       PredMap pred_map(_ugraph, INVALID);
deba@2480:       TreeMap tree_map(_ugraph, false);
deba@2480: 
deba@2480:       OrderMap order_map(_ugraph, -1);
deba@2480:       OrderList order_list;
deba@2480: 
deba@2480:       AncestorMap ancestor_map(_ugraph, -1);
deba@2480:       LowMap low_map(_ugraph, -1);
deba@2480: 
deba@2480:       Visitor visitor(_ugraph, pred_map, tree_map,
deba@2480: 		      order_map, order_list, ancestor_map, low_map);
deba@2480:       DfsVisit<UGraph, Visitor> visit(_ugraph, visitor);
deba@2480:       visit.run();
deba@2480: 
deba@2480:       ChildLists child_lists(_ugraph);
deba@2480:       createChildLists(tree_map, order_map, low_map, child_lists);
deba@2480: 
deba@2480:       NodeData node_data(2 * order_list.size());
deba@2480:       
deba@2480:       EmbedEdge embed_edge(_ugraph, INVALID);
deba@2480: 
deba@2480:       MergeRoots merge_roots(_ugraph);
deba@2480: 
deba@2480:       EdgeLists edge_lists(_ugraph);
deba@2480: 
deba@2480:       FlipMap flip_map(_ugraph, false);
deba@2480: 
deba@2480:       for (int i = order_list.size() - 1; i >= 0; --i) {
deba@2480: 
deba@2480: 	Node node = order_list[i];
deba@2480: 
deba@2480: 	node_data[i].first = INVALID;
deba@2480: 	
deba@2480: 	Node source = node;
deba@2480: 	for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
deba@2480: 	  Node target = _ugraph.target(e);
deba@2480: 	  
deba@2480: 	  if (order_map[source] < order_map[target] && tree_map[e]) {
deba@2480: 	    initFace(target, edge_lists, node_data,
deba@2480: 		      pred_map, order_map, order_list);
deba@2480: 	  }
deba@2480: 	}
deba@2480: 	
deba@2480: 	for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
deba@2480: 	  Node target = _ugraph.target(e);
deba@2480: 	  
deba@2480: 	  if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@2480: 	    embed_edge[target] = e;
deba@2480: 	    walkUp(target, source, i, pred_map, low_map,
deba@2480: 		   order_map, order_list, node_data, merge_roots);
deba@2480: 	  }
deba@2480: 	}
deba@2480: 
deba@2480: 	for (typename MergeRoots::Value::iterator it = 
deba@2480: 	       merge_roots[node].begin(); it != merge_roots[node].end(); ++it) {
deba@2480: 	  int rn = *it;
deba@2480: 	  walkDown(rn, i, node_data, edge_lists, flip_map, order_list, 
deba@2480: 		   child_lists, ancestor_map, low_map, embed_edge, merge_roots);
deba@2480: 	}
deba@2480: 	merge_roots[node].clear();
deba@2480: 	
deba@2480: 	for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
deba@2480: 	  Node target = _ugraph.target(e);
deba@2480: 	  
deba@2480: 	  if (order_map[source] < order_map[target] && !tree_map[e]) {
deba@2480: 	    if (embed_edge[target] != INVALID) {
deba@2480: 	      if (kuratowski) {
deba@2480: 		isolateKuratowski(e, node_data, edge_lists, flip_map,
deba@2480: 				  order_map, order_list, pred_map, child_lists,
deba@2480: 				  ancestor_map, low_map, 
deba@2480: 				  embed_edge, merge_roots);
deba@2480: 	      }
deba@2480: 	      return false;
deba@2480: 	    }
deba@2480: 	  }
deba@2480: 	}
deba@2480:       }
deba@2480: 
deba@2480:       for (int i = 0; i < int(order_list.size()); ++i) {
deba@2480: 
deba@2480: 	mergeRemainingFaces(order_list[i], node_data, order_list, order_map,
deba@2480: 			    child_lists, edge_lists);
deba@2480: 	storeEmbedding(order_list[i], node_data, order_map, pred_map,
deba@2480: 		       edge_lists, flip_map);
deba@2480:       }
deba@2480: 
deba@2480:       return true;
deba@2480:     }
deba@2480: 
deba@2480:     /// \brief Gives back the successor of an edge
deba@2480:     ///
deba@2480:     /// Gives back the successor of an edge. This function makes
deba@2480:     /// possible to query the cyclic order of the outgoing edges from
deba@2480:     /// a node.
deba@2480:     Edge next(const Edge& edge) const {
deba@2480:       return _embedding[edge];
deba@2480:     }
deba@2480: 
deba@2499:     /// \brief Gives back the calculated embedding map
deba@2499:     ///
deba@2499:     /// The returned map contains the successor of each edge in the
deba@2499:     /// graph.
deba@2499:     const EmbeddingMap& embedding() const {
deba@2499:       return _embedding;
deba@2499:     }
deba@2499: 
deba@2480:     /// \brief Gives back true when the undirected edge is in the
deba@2480:     /// kuratowski subdivision
deba@2480:     ///
deba@2480:     /// Gives back true when the undirected edge is in the kuratowski
deba@2480:     /// subdivision
deba@2480:     bool kuratowski(const UEdge& uedge) {
deba@2480:       return _kuratowski[uedge];
deba@2480:     }
deba@2480: 
deba@2480:   private:
deba@2480: 
deba@2480:     void createChildLists(const TreeMap& tree_map, const OrderMap& order_map,
deba@2480: 			  const LowMap& low_map, ChildLists& child_lists) {
deba@2480: 
deba@2480:       for (NodeIt n(_ugraph); n != INVALID; ++n) {
deba@2480: 	Node source = n;
deba@2480: 	
deba@2480: 	std::vector<Node> targets;  
deba@2480: 	for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) {
deba@2480: 	  Node target = _ugraph.target(e);
deba@2480: 
deba@2480: 	  if (order_map[source] < order_map[target] && tree_map[e]) {
deba@2480: 	    targets.push_back(target);
deba@2480: 	  }
deba@2480: 	}	
deba@2480: 
deba@2480: 	if (targets.size() == 0) {
deba@2480: 	  child_lists[source].first = INVALID;
deba@2480: 	} else if (targets.size() == 1) {
deba@2480: 	  child_lists[source].first = targets[0];
deba@2480: 	  child_lists[targets[0]].prev = INVALID;
deba@2480: 	  child_lists[targets[0]].next = INVALID;
deba@2480: 	} else {
deba@2480: 	  radixSort(targets.begin(), targets.end(), mapFunctor(low_map));
deba@2480: 	  for (int i = 1; i < int(targets.size()); ++i) {
deba@2480: 	    child_lists[targets[i]].prev = targets[i - 1];
deba@2480: 	    child_lists[targets[i - 1]].next = targets[i];
deba@2480: 	  }
deba@2480: 	  child_lists[targets.back()].next = INVALID; 
deba@2480: 	  child_lists[targets.front()].prev = INVALID;
deba@2480: 	  child_lists[source].first = targets.front();
deba@2480: 	}
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void walkUp(const Node& node, Node root, int rorder,
deba@2480: 		const PredMap& pred_map, const LowMap& low_map,
deba@2480: 		const OrderMap& order_map, const OrderList& order_list,
deba@2480: 		NodeData& node_data, MergeRoots& merge_roots) {
deba@2480: 
deba@2480:       int na, nb;
deba@2480:       bool da, db;
deba@2480:       
deba@2480:       na = nb = order_map[node];
deba@2480:       da = true; db = false;
deba@2480:       
deba@2480:       while (true) {
deba@2480: 	
deba@2480: 	if (node_data[na].visited == rorder) break;
deba@2480: 	if (node_data[nb].visited == rorder) break;
deba@2480: 
deba@2480: 	node_data[na].visited = rorder;
deba@2480: 	node_data[nb].visited = rorder;
deba@2480: 
deba@2480: 	int rn = -1;
deba@2480: 
deba@2480: 	if (na >= int(order_list.size())) {
deba@2480: 	  rn = na;
deba@2480: 	} else if (nb >= int(order_list.size())) {
deba@2480: 	  rn = nb;
deba@2480: 	}
deba@2480: 
deba@2480: 	if (rn == -1) {
deba@2480: 	  int nn;
deba@2480: 	  
deba@2480: 	  nn = da ? node_data[na].prev : node_data[na].next;
deba@2480: 	  da = node_data[nn].prev != na;
deba@2480: 	  na = nn;
deba@2480: 	  
deba@2480: 	  nn = db ? node_data[nb].prev : node_data[nb].next;
deba@2480: 	  db = node_data[nn].prev != nb;
deba@2480: 	  nb = nn;
deba@2480: 
deba@2480: 	} else {
deba@2480: 
deba@2480: 	  Node rep = order_list[rn - order_list.size()];
deba@2480: 	  Node parent = _ugraph.source(pred_map[rep]);
deba@2480: 
deba@2480: 	  if (low_map[rep] < rorder) {
deba@2480: 	    merge_roots[parent].push_back(rn);
deba@2480: 	  } else {
deba@2480: 	    merge_roots[parent].push_front(rn);
deba@2480: 	  }
deba@2480: 	  
deba@2480: 	  if (parent != root) {  
deba@2480: 	    na = nb = order_map[parent];
deba@2480: 	    da = true; db = false;
deba@2480: 	  } else {
deba@2480: 	    break;
deba@2480: 	  }
deba@2480: 	}	
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void walkDown(int rn, int rorder, NodeData& node_data,
deba@2480: 		  EdgeLists& edge_lists, FlipMap& flip_map, 
deba@2480: 		  OrderList& order_list, ChildLists& child_lists,
deba@2480: 		  AncestorMap& ancestor_map, LowMap& low_map,
deba@2480: 		  EmbedEdge& embed_edge, MergeRoots& merge_roots) {
deba@2480: 
deba@2480:       std::vector<std::pair<int, bool> > merge_stack;
deba@2480: 
deba@2480:       for (int di = 0; di < 2; ++di) {
deba@2480: 	bool rd = di == 0;
deba@2480: 	int pn = rn;
deba@2480: 	int n = rd ? node_data[rn].next : node_data[rn].prev;
deba@2480: 	
deba@2480: 	while (n != rn) {
deba@2480: 	  
deba@2480: 	  Node node = order_list[n];
deba@2480: 	  
deba@2480: 	  if (embed_edge[node] != INVALID) {
deba@2480: 
deba@2480: 	    // Merging components on the critical path
deba@2480: 	    while (!merge_stack.empty()) {
deba@2480: 
deba@2480: 	      // Component root
deba@2480: 	      int cn = merge_stack.back().first;
deba@2480: 	      bool cd = merge_stack.back().second;
deba@2480: 	      merge_stack.pop_back();
deba@2480: 
deba@2480: 	      // Parent of component
deba@2480: 	      int dn = merge_stack.back().first;
deba@2480: 	      bool dd = merge_stack.back().second;
deba@2480: 	      merge_stack.pop_back();
deba@2480: 
deba@2480: 	      Node parent = order_list[dn];
deba@2480: 
deba@2480: 	      // Erasing from merge_roots
deba@2480: 	      merge_roots[parent].pop_front();
deba@2480: 	      
deba@2480: 	      Node child = order_list[cn - order_list.size()];
deba@2480: 
deba@2480: 	      // Erasing from child_lists
deba@2480: 	      if (child_lists[child].prev != INVALID) {
deba@2480: 		child_lists[child_lists[child].prev].next =
deba@2480: 		  child_lists[child].next;
deba@2480: 	      } else {
deba@2480: 		child_lists[parent].first = child_lists[child].next;
deba@2480: 	      }
deba@2480: 	      
deba@2480: 	      if (child_lists[child].next != INVALID) {
deba@2480: 		child_lists[child_lists[child].next].prev =
deba@2480: 		  child_lists[child].prev;
deba@2480: 	      }
deba@2480: 
deba@2480: 	      // Merging edges + flipping
deba@2480: 	      Edge de = node_data[dn].first;
deba@2480: 	      Edge ce = node_data[cn].first;
deba@2480: 
deba@2480: 	      flip_map[order_list[cn - order_list.size()]] = cd != dd;
deba@2480: 	      if (cd != dd) {
deba@2480: 		std::swap(edge_lists[ce].prev, edge_lists[ce].next);
deba@2480: 		ce = edge_lists[ce].prev;
deba@2480: 		std::swap(edge_lists[ce].prev, edge_lists[ce].next);
deba@2480: 	      }
deba@2480: 
deba@2480: 	      {
deba@2480: 		Edge dne = edge_lists[de].next; 
deba@2480: 		Edge cne = edge_lists[ce].next; 
deba@2480: 
deba@2480: 		edge_lists[de].next = cne;
deba@2480: 		edge_lists[ce].next = dne;
deba@2480: 	      
deba@2480: 		edge_lists[dne].prev = ce;
deba@2480: 		edge_lists[cne].prev = de;
deba@2480: 	      }
deba@2480: 	      	      
deba@2480: 	      if (dd) {
deba@2480: 		node_data[dn].first = ce;
deba@2480: 	      }
deba@2480: 	      
deba@2480: 	      // Merging external faces
deba@2480: 	      {
deba@2480: 		int en = cn;
deba@2480: 		cn = cd ? node_data[cn].prev : node_data[cn].next;
deba@2480: 		cd = node_data[cn].next == en;
deba@2480: 
deba@2480:  		if (node_data[cn].prev == node_data[cn].next && 
deba@2480: 		    node_data[cn].inverted) {
deba@2480:  		  cd = !cd;
deba@2480:  		}
deba@2480: 	      }
deba@2480: 
deba@2480: 	      if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn;
deba@2480: 	      if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn;
deba@2480: 
deba@2480: 	    }
deba@2480: 
deba@2480: 	    bool d = pn == node_data[n].prev;
deba@2480: 
deba@2480: 	    if (node_data[n].prev == node_data[n].next && 
deba@2480: 		node_data[n].inverted) {
deba@2480: 	      d = !d;
deba@2480: 	    }
deba@2480: 
deba@2480: 	    // Add new edge
deba@2480: 	    {
deba@2480: 	      Edge edge = embed_edge[node];
deba@2480: 	      Edge re = node_data[rn].first;
deba@2480: 
deba@2480: 	      edge_lists[edge_lists[re].next].prev = edge;
deba@2480: 	      edge_lists[edge].next = edge_lists[re].next;
deba@2480: 	      edge_lists[edge].prev = re;
deba@2480: 	      edge_lists[re].next = edge;
deba@2480: 
deba@2480: 	      if (!rd) {
deba@2480: 		node_data[rn].first = edge;
deba@2480: 	      }
deba@2480: 
deba@2480: 	      Edge rev = _ugraph.oppositeEdge(edge);
deba@2480: 	      Edge e = node_data[n].first;
deba@2480: 
deba@2480: 	      edge_lists[edge_lists[e].next].prev = rev;
deba@2480: 	      edge_lists[rev].next = edge_lists[e].next;
deba@2480: 	      edge_lists[rev].prev = e;
deba@2480: 	      edge_lists[e].next = rev;
deba@2480: 
deba@2480: 	      if (d) {
deba@2480: 		node_data[n].first = rev;
deba@2480: 	      }
deba@2480: 	      
deba@2480: 	    }
deba@2480: 
deba@2480: 	    // Embedding edge into external face
deba@2480: 	    if (rd) node_data[rn].next = n; else node_data[rn].prev = n;
deba@2480: 	    if (d) node_data[n].prev = rn; else node_data[n].next = rn;
deba@2480: 	    pn = rn;
deba@2480: 
deba@2480: 	    embed_edge[order_list[n]] = INVALID;
deba@2480: 	  }
deba@2480: 
deba@2480: 	  if (!merge_roots[node].empty()) {
deba@2480: 
deba@2480: 	    bool d = pn == node_data[n].prev;
deba@2480: 	    if (node_data[n].prev == node_data[n].next && 
deba@2480: 		node_data[n].inverted) {
deba@2480: 	      d = !d;
deba@2480: 	    }
deba@2480: 
deba@2480: 	    merge_stack.push_back(std::make_pair(n, d));
deba@2480: 
deba@2480: 	    int rn = merge_roots[node].front();
deba@2480: 	    
deba@2480: 	    int xn = node_data[rn].next;
deba@2480: 	    Node xnode = order_list[xn];
deba@2480: 	    
deba@2480: 	    int yn = node_data[rn].prev;
deba@2480: 	    Node ynode = order_list[yn];
deba@2480: 	    
deba@2480: 	    bool rd;
deba@2480: 	    if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) {
deba@2480: 	      rd = true;
deba@2480: 	    } else if (!external(ynode, rorder, child_lists, 
deba@2480: 				 ancestor_map, low_map)) {
deba@2480: 	      rd = false;
deba@2480: 	    } else if (pertinent(xnode, embed_edge, merge_roots)) {
deba@2480: 	      rd = true;
deba@2480: 	    } else {
deba@2480: 	      rd = false;
deba@2480: 	    }
deba@2480: 	    
deba@2480: 	    merge_stack.push_back(std::make_pair(rn, rd));
deba@2480: 	    
deba@2480: 	    pn = rn;
deba@2480: 	    n = rd ? xn : yn;	      
deba@2480: 	    	    
deba@2480: 	  } else if (!external(node, rorder, child_lists,
deba@2480: 			       ancestor_map, low_map)) {
deba@2480: 	    int nn = (node_data[n].next != pn ? 
deba@2480: 		      node_data[n].next : node_data[n].prev);
deba@2480: 
deba@2480: 	    bool nd = n == node_data[nn].prev;
deba@2480: 
deba@2480: 	    if (nd) node_data[nn].prev = pn;
deba@2480: 	    else node_data[nn].next = pn; 
deba@2480: 
deba@2480: 	    if (n == node_data[pn].prev) node_data[pn].prev = nn;
deba@2480: 	    else node_data[pn].next = nn;
deba@2480: 
deba@2480: 	    node_data[nn].inverted = 
deba@2480: 	      (node_data[nn].prev == node_data[nn].next && nd != rd);
deba@2480: 
deba@2480: 	    n = nn;
deba@2480: 	  }
deba@2480: 	  else break;
deba@2480: 	  
deba@2480: 	}
deba@2480: 
deba@2480: 	if (!merge_stack.empty() || n == rn) {
deba@2480: 	  break;
deba@2480: 	}
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void initFace(const Node& node, EdgeLists& edge_lists,
deba@2480: 		   NodeData& node_data, const PredMap& pred_map,
deba@2480: 		   const OrderMap& order_map, const OrderList& order_list) {
deba@2480:       int n = order_map[node];
deba@2480:       int rn = n + order_list.size();
deba@2480:       
deba@2480:       node_data[n].next = node_data[n].prev = rn;
deba@2480:       node_data[rn].next = node_data[rn].prev = n;
deba@2480:       
deba@2480:       node_data[n].visited = order_list.size();
deba@2480:       node_data[rn].visited = order_list.size();
deba@2480: 
deba@2480:       node_data[n].inverted = false;
deba@2480:       node_data[rn].inverted = false;
deba@2480: 
deba@2480:       Edge edge = pred_map[node];
deba@2480:       Edge rev = _ugraph.oppositeEdge(edge);
deba@2480: 
deba@2480:       node_data[rn].first = edge;
deba@2480:       node_data[n].first = rev;
deba@2480: 
deba@2480:       edge_lists[edge].prev = edge;
deba@2480:       edge_lists[edge].next = edge;
deba@2480: 
deba@2480:       edge_lists[rev].prev = rev;
deba@2480:       edge_lists[rev].next = rev;
deba@2480: 
deba@2480:     }
deba@2480: 
deba@2480:     void mergeRemainingFaces(const Node& node, NodeData& node_data,
deba@2480: 			     OrderList& order_list, OrderMap& order_map,
deba@2480: 			     ChildLists& child_lists, EdgeLists& edge_lists) {
deba@2480:       while (child_lists[node].first != INVALID) {
deba@2480: 	int dd = order_map[node];
deba@2480: 	Node child = child_lists[node].first; 
deba@2480: 	int cd = order_map[child] + order_list.size();
deba@2480: 	child_lists[node].first = child_lists[child].next;
deba@2480: 
deba@2480: 	Edge de = node_data[dd].first;
deba@2480: 	Edge ce = node_data[cd].first;
deba@2480: 
deba@2480: 	if (de != INVALID) {
deba@2480: 	  Edge dne = edge_lists[de].next; 
deba@2480: 	  Edge cne = edge_lists[ce].next; 
deba@2480: 	  
deba@2480: 	  edge_lists[de].next = cne;
deba@2480: 	  edge_lists[ce].next = dne;
deba@2480: 	  
deba@2480: 	  edge_lists[dne].prev = ce;
deba@2480: 	  edge_lists[cne].prev = de;
deba@2480: 	}
deba@2480: 	
deba@2480: 	node_data[dd].first = ce;
deba@2480: 
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void storeEmbedding(const Node& node, NodeData& node_data,
deba@2480: 			OrderMap& order_map, PredMap& pred_map,
deba@2480: 			EdgeLists& edge_lists, FlipMap& flip_map) {
deba@2480: 
deba@2480:       if (node_data[order_map[node]].first == INVALID) return;
deba@2480: 
deba@2480:       if (pred_map[node] != INVALID) {
deba@2480: 	Node source = _ugraph.source(pred_map[node]);
deba@2480: 	flip_map[node] = flip_map[node] != flip_map[source];
deba@2480:       }
deba@2480:       
deba@2480:       Edge first = node_data[order_map[node]].first;
deba@2480:       Edge prev = first;
deba@2480: 
deba@2480:       Edge edge = flip_map[node] ?
deba@2480: 	edge_lists[prev].prev : edge_lists[prev].next;
deba@2480: 
deba@2480:       _embedding[prev] = edge;
deba@2480:       
deba@2480:       while (edge != first) {
deba@2480: 	Edge next = edge_lists[edge].prev == prev ?
deba@2480: 	  edge_lists[edge].next : edge_lists[edge].prev;
deba@2480: 	prev = edge; edge = next;
deba@2480: 	_embedding[prev] = edge;
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480: 
deba@2480:     bool external(const Node& node, int rorder,
deba@2480: 		  ChildLists& child_lists, AncestorMap& ancestor_map, 
deba@2480: 		  LowMap& low_map) {
deba@2480:       Node child = child_lists[node].first;
deba@2480: 
deba@2480:       if (child != INVALID) {
deba@2480: 	if (low_map[child] < rorder) return true;
deba@2480:       }
deba@2480: 
deba@2480:       if (ancestor_map[node] < rorder) return true;
deba@2480: 
deba@2480:       return false;
deba@2480:     }
deba@2480: 
deba@2480:     bool pertinent(const Node& node, const EmbedEdge& embed_edge,
deba@2480: 		   const MergeRoots& merge_roots) {
deba@2480:       return !merge_roots[node].empty() || embed_edge[node] != INVALID;
deba@2480:     }
deba@2480: 
deba@2480:     int lowPoint(const Node& node, OrderMap& order_map, ChildLists& child_lists,
deba@2480: 		 AncestorMap& ancestor_map, LowMap& low_map) {
deba@2480:       int low_point;
deba@2480: 
deba@2480:       Node child = child_lists[node].first;
deba@2480: 
deba@2480:       if (child != INVALID) {
deba@2480: 	low_point = low_map[child];
deba@2480:       } else {
deba@2480: 	low_point = order_map[node];
deba@2480:       }
deba@2480: 
deba@2480:       if (low_point > ancestor_map[node]) {
deba@2480: 	low_point = ancestor_map[node];
deba@2480:       }
deba@2480: 
deba@2480:       return low_point;
deba@2480:     }
deba@2480: 
deba@2480:     int findComponentRoot(Node root, Node node, ChildLists& child_lists, 
deba@2480: 			  OrderMap& order_map, OrderList& order_list) {
deba@2480: 
deba@2480:       int order = order_map[root];
deba@2480:       int norder = order_map[node];
deba@2480: 
deba@2480:       Node child = child_lists[root].first;
deba@2480:       while (child != INVALID) {
deba@2480: 	int corder = order_map[child];
deba@2480: 	if (corder > order && corder < norder) {
deba@2480: 	  order = corder;
deba@2480: 	}
deba@2480: 	child = child_lists[child].next;
deba@2480:       }
deba@2480:       return order + order_list.size();
deba@2480:     }
deba@2480: 
deba@2480:     Node findPertinent(Node node, OrderMap& order_map, NodeData& node_data,
deba@2480: 		       EmbedEdge& embed_edge, MergeRoots& merge_roots) {
deba@2480:       Node wnode =_ugraph.target(node_data[order_map[node]].first);
deba@2480:       while (!pertinent(wnode, embed_edge, merge_roots)) {
deba@2480: 	wnode = _ugraph.target(node_data[order_map[wnode]].first);
deba@2480:       }
deba@2480:       return wnode;
deba@2480:     }
deba@2480: 
deba@2480: 
deba@2480:     Node findExternal(Node node, int rorder, OrderMap& order_map, 
deba@2480: 		      ChildLists& child_lists, AncestorMap& ancestor_map,
deba@2480: 		      LowMap& low_map, NodeData& node_data) {
deba@2480:       Node wnode =_ugraph.target(node_data[order_map[node]].first);
deba@2480:       while (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
deba@2480: 	wnode = _ugraph.target(node_data[order_map[wnode]].first);
deba@2480:       }
deba@2480:       return wnode;
deba@2480:     }
deba@2480: 
deba@2480:     void markCommonPath(Node node, int rorder, Node& wnode, Node& znode, 
deba@2480: 			OrderList& order_list, OrderMap& order_map, 
deba@2480: 			NodeData& node_data, EdgeLists& edge_lists, 
deba@2480: 			EmbedEdge& embed_edge, MergeRoots& merge_roots, 
deba@2480: 			ChildLists& child_lists, AncestorMap& ancestor_map, 
deba@2480: 			LowMap& low_map) {
deba@2480:       
deba@2480:       Node cnode = node;
deba@2480:       Node pred = INVALID;
deba@2480:       
deba@2480:       while (true) {
deba@2480: 
deba@2480: 	bool pert = pertinent(cnode, embed_edge, merge_roots);
deba@2480: 	bool ext = external(cnode, rorder, child_lists, ancestor_map, low_map);
deba@2480: 
deba@2480: 	if (pert && ext) {
deba@2480: 	  if (!merge_roots[cnode].empty()) {
deba@2480: 	    int cn = merge_roots[cnode].back();
deba@2480: 	    
deba@2480: 	    if (low_map[order_list[cn - order_list.size()]] < rorder) {
deba@2480: 	      Edge edge = node_data[cn].first;
deba@2480: 	      _kuratowski.set(edge, true);
deba@2480: 	      
deba@2480: 	      pred = cnode;
deba@2480: 	      cnode = _ugraph.target(edge);
deba@2480: 	    
deba@2480: 	      continue;
deba@2480: 	    }
deba@2480: 	  }
deba@2480: 	  wnode = znode = cnode;
deba@2480: 	  return;
deba@2480: 
deba@2480: 	} else if (pert) {
deba@2480: 	  wnode = cnode;
deba@2480: 	  
deba@2480: 	  while (!external(cnode, rorder, child_lists, ancestor_map, low_map)) {
deba@2480: 	    Edge edge = node_data[order_map[cnode]].first;
deba@2480: 	  
deba@2480: 	    if (_ugraph.target(edge) == pred) {
deba@2480: 	      edge = edge_lists[edge].next;
deba@2480: 	    }
deba@2480: 	    _kuratowski.set(edge, true);
deba@2480: 	    
deba@2480: 	    Node next = _ugraph.target(edge);
deba@2480: 	    pred = cnode; cnode = next;
deba@2480: 	  }
deba@2480: 	  
deba@2480: 	  znode = cnode;
deba@2480: 	  return;
deba@2480: 
deba@2480: 	} else if (ext) {
deba@2480: 	  znode = cnode;
deba@2480: 	  
deba@2480: 	  while (!pertinent(cnode, embed_edge, merge_roots)) {
deba@2480: 	    Edge edge = node_data[order_map[cnode]].first;
deba@2480: 	  
deba@2480: 	    if (_ugraph.target(edge) == pred) {
deba@2480: 	      edge = edge_lists[edge].next;
deba@2480: 	    }
deba@2480: 	    _kuratowski.set(edge, true);
deba@2480: 	    
deba@2480: 	    Node next = _ugraph.target(edge);
deba@2480: 	    pred = cnode; cnode = next;
deba@2480: 	  }
deba@2480: 	  
deba@2480: 	  wnode = cnode;
deba@2480: 	  return;
deba@2480: 	  
deba@2480: 	} else {
deba@2480: 	  Edge edge = node_data[order_map[cnode]].first;
deba@2480: 	  
deba@2480: 	  if (_ugraph.target(edge) == pred) {
deba@2480: 	    edge = edge_lists[edge].next;
deba@2480: 	  }
deba@2480: 	  _kuratowski.set(edge, true);
deba@2480: 
deba@2480: 	  Node next = _ugraph.target(edge);
deba@2480: 	  pred = cnode; cnode = next;
deba@2480: 	}
deba@2480: 	
deba@2480:       }
deba@2480: 
deba@2480:     }
deba@2480: 
deba@2480:     void orientComponent(Node root, int rn, OrderMap& order_map,
deba@2480: 			 PredMap& pred_map, NodeData& node_data, 
deba@2480: 			 EdgeLists& edge_lists, FlipMap& flip_map, 
deba@2480: 			 TypeMap& type_map) {
deba@2480:       node_data[order_map[root]].first = node_data[rn].first;
deba@2480:       type_map[root] = 1;
deba@2480: 
deba@2480:       std::vector<Node> st, qu;
deba@2480: 
deba@2480:       st.push_back(root);
deba@2480:       while (!st.empty()) {
deba@2480: 	Node node = st.back();
deba@2480: 	st.pop_back();
deba@2480: 	qu.push_back(node);
deba@2480: 	
deba@2480: 	Edge edge = node_data[order_map[node]].first;
deba@2480: 	
deba@2480: 	if (type_map[_ugraph.target(edge)] == 0) {
deba@2480: 	  st.push_back(_ugraph.target(edge));
deba@2480: 	  type_map[_ugraph.target(edge)] = 1;
deba@2480: 	} 
deba@2480: 	
deba@2480: 	Edge last = edge, pred = edge;
deba@2480: 	edge = edge_lists[edge].next;
deba@2480: 	while (edge != last) {
deba@2480: 
deba@2480: 	  if (type_map[_ugraph.target(edge)] == 0) {
deba@2480: 	    st.push_back(_ugraph.target(edge));
deba@2480: 	    type_map[_ugraph.target(edge)] = 1;
deba@2480: 	  } 
deba@2480: 	  
deba@2480: 	  Edge next = edge_lists[edge].next != pred ? 
deba@2480: 	    edge_lists[edge].next : edge_lists[edge].prev;
deba@2480: 	  pred = edge; edge = next;
deba@2480: 	}
deba@2480: 
deba@2480:       }
deba@2480: 
deba@2480:       type_map[root] = 2;
deba@2480:       flip_map[root] = false;
deba@2480: 
deba@2480:       for (int i = 1; i < int(qu.size()); ++i) {
deba@2480: 
deba@2480: 	Node node = qu[i];
deba@2480: 
deba@2480: 	while (type_map[node] != 2) {
deba@2480: 	  st.push_back(node);
deba@2480: 	  type_map[node] = 2;
deba@2480: 	  node = _ugraph.source(pred_map[node]);
deba@2480: 	}
deba@2480: 
deba@2480: 	bool flip = flip_map[node];
deba@2480: 
deba@2480: 	while (!st.empty()) {
deba@2480: 	  node = st.back();
deba@2480: 	  st.pop_back();
deba@2480: 	  
deba@2480: 	  flip_map[node] = flip != flip_map[node];
deba@2480: 	  flip = flip_map[node];
deba@2480: 
deba@2480: 	  if (flip) {
deba@2480: 	    Edge edge = node_data[order_map[node]].first;
deba@2480: 	    std::swap(edge_lists[edge].prev, edge_lists[edge].next);
deba@2480: 	    edge = edge_lists[edge].prev;
deba@2480: 	    std::swap(edge_lists[edge].prev, edge_lists[edge].next);
deba@2480: 	    node_data[order_map[node]].first = edge;
deba@2480: 	  }
deba@2480: 	}
deba@2480:       }
deba@2480: 
deba@2480:       for (int i = 0; i < int(qu.size()); ++i) {
deba@2480: 
deba@2480: 	Edge edge = node_data[order_map[qu[i]]].first;
deba@2480: 	Edge last = edge, pred = edge;
deba@2480: 
deba@2480: 	edge = edge_lists[edge].next;
deba@2480: 	while (edge != last) {
deba@2480: 
deba@2480: 	  if (edge_lists[edge].next == pred) {
deba@2480: 	    std::swap(edge_lists[edge].next, edge_lists[edge].prev);
deba@2480: 	  } 
deba@2480: 	  pred = edge; edge = edge_lists[edge].next;
deba@2480: 	}
deba@2480: 	
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void setFaceFlags(Node root, Node wnode, Node ynode, Node xnode,
deba@2480: 		      OrderMap& order_map, NodeData& node_data, 
deba@2480: 		      TypeMap& type_map) {
deba@2480:       Node node = _ugraph.target(node_data[order_map[root]].first);
deba@2480: 
deba@2480:       while (node != ynode) {
deba@2480: 	type_map[node] = HIGHY;
deba@2480: 	node = _ugraph.target(node_data[order_map[node]].first);
deba@2480:       }
deba@2480: 
deba@2480:       while (node != wnode) {
deba@2480: 	type_map[node] = LOWY;
deba@2480: 	node = _ugraph.target(node_data[order_map[node]].first);
deba@2480:       }
deba@2480:       
deba@2480:       node = _ugraph.target(node_data[order_map[wnode]].first);
deba@2480:       
deba@2480:       while (node != xnode) {
deba@2480: 	type_map[node] = LOWX;
deba@2480: 	node = _ugraph.target(node_data[order_map[node]].first);
deba@2480:       }
deba@2480:       type_map[node] = LOWX;
deba@2480: 
deba@2480:       node = _ugraph.target(node_data[order_map[xnode]].first);
deba@2480:       while (node != root) {
deba@2480: 	type_map[node] = HIGHX;
deba@2480: 	node = _ugraph.target(node_data[order_map[node]].first);
deba@2480:       }
deba@2480: 
deba@2480:       type_map[wnode] = PERTINENT;
deba@2480:       type_map[root] = ROOT;
deba@2480:     }
deba@2480: 
deba@2480:     void findInternalPath(std::vector<Edge>& ipath,
deba@2480: 			  Node wnode, Node root, TypeMap& type_map, 
deba@2480: 			  OrderMap& order_map, NodeData& node_data, 
deba@2480: 			  EdgeLists& edge_lists) {
deba@2480:       std::vector<Edge> st;
deba@2480: 
deba@2480:       Node node = wnode;
deba@2480:       
deba@2480:       while (node != root) {
deba@2480: 	Edge edge = edge_lists[node_data[order_map[node]].first].next;
deba@2480: 	st.push_back(edge);
deba@2480: 	node = _ugraph.target(edge);
deba@2480:       }
deba@2480:       
deba@2480:       while (true) {
deba@2480: 	Edge edge = st.back();
deba@2480: 	if (type_map[_ugraph.target(edge)] == LOWX ||
deba@2480: 	    type_map[_ugraph.target(edge)] == HIGHX) {
deba@2480: 	  break;
deba@2480: 	}
deba@2480: 	if (type_map[_ugraph.target(edge)] == 2) {
deba@2480: 	  type_map[_ugraph.target(edge)] = 3;
deba@2480: 	  
deba@2480: 	  edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
deba@2480: 	  st.push_back(edge);
deba@2480: 	} else {
deba@2480: 	  st.pop_back();
deba@2480: 	  edge = edge_lists[edge].next;
deba@2480: 	  
deba@2480: 	  while (_ugraph.oppositeEdge(edge) == st.back()) {
deba@2480: 	    edge = st.back();
deba@2480: 	    st.pop_back();
deba@2480: 	    edge = edge_lists[edge].next;
deba@2480: 	  }
deba@2480: 	  st.push_back(edge);
deba@2480: 	}
deba@2480:       }
deba@2480:       
deba@2480:       for (int i = 0; i < int(st.size()); ++i) {
deba@2480: 	if (type_map[_ugraph.target(st[i])] != LOWY &&
deba@2480: 	    type_map[_ugraph.target(st[i])] != HIGHY) {
deba@2480: 	  for (; i < int(st.size()); ++i) {
deba@2480: 	    ipath.push_back(st[i]);
deba@2480: 	  }
deba@2480: 	}
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void setInternalFlags(std::vector<Edge>& ipath, TypeMap& type_map) {
deba@2480:       for (int i = 1; i < int(ipath.size()); ++i) {
deba@2480: 	type_map[_ugraph.source(ipath[i])] = INTERNAL;
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void findPilePath(std::vector<Edge>& ppath,
deba@2480: 		      Node root, TypeMap& type_map, OrderMap& order_map, 
deba@2480: 		      NodeData& node_data, EdgeLists& edge_lists) {
deba@2480:       std::vector<Edge> st;
deba@2480: 
deba@2480:       st.push_back(_ugraph.oppositeEdge(node_data[order_map[root]].first));
deba@2480:       st.push_back(node_data[order_map[root]].first);
deba@2480:       
deba@2480:       while (st.size() > 1) {
deba@2480: 	Edge edge = st.back();
deba@2480: 	if (type_map[_ugraph.target(edge)] == INTERNAL) {
deba@2480: 	  break;
deba@2480: 	}
deba@2480: 	if (type_map[_ugraph.target(edge)] == 3) {
deba@2480: 	  type_map[_ugraph.target(edge)] = 4;
deba@2480: 	  
deba@2480: 	  edge = edge_lists[_ugraph.oppositeEdge(edge)].next;
deba@2480: 	  st.push_back(edge);
deba@2480: 	} else {
deba@2480: 	  st.pop_back();
deba@2480: 	  edge = edge_lists[edge].next;
deba@2480: 	  
deba@2480: 	  while (!st.empty() && _ugraph.oppositeEdge(edge) == st.back()) {
deba@2480: 	    edge = st.back();
deba@2480: 	    st.pop_back();
deba@2480: 	    edge = edge_lists[edge].next;
deba@2480: 	  }
deba@2480: 	  st.push_back(edge);
deba@2480: 	}
deba@2480:       }
deba@2480:       
deba@2480:       for (int i = 1; i < int(st.size()); ++i) {
deba@2480: 	ppath.push_back(st[i]);
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480: 
deba@2480:     int markExternalPath(Node node, OrderMap& order_map,
deba@2480: 			 ChildLists& child_lists, PredMap& pred_map,
deba@2480: 			 AncestorMap& ancestor_map, LowMap& low_map) {
deba@2480:       int lp = lowPoint(node, order_map, child_lists,
deba@2480: 			ancestor_map, low_map);
deba@2480:       
deba@2480:       if (ancestor_map[node] != lp) {
deba@2480: 	node = child_lists[node].first;
deba@2480: 	_kuratowski[pred_map[node]] = true;
deba@2480: 
deba@2480: 	while (ancestor_map[node] != lp) {
deba@2480: 	  for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
deba@2480: 	    Node tnode = _ugraph.target(e); 
deba@2480: 	    if (order_map[tnode] > order_map[node] && low_map[tnode] == lp) {
deba@2480: 	      node = tnode;
deba@2480: 	      _kuratowski[e] = true;
deba@2480: 	      break;
deba@2480: 	    }
deba@2480: 	  }
deba@2480: 	}
deba@2480:       }
deba@2480: 
deba@2480:       for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) {
deba@2480: 	if (order_map[_ugraph.target(e)] == lp) {
deba@2480: 	  _kuratowski[e] = true;
deba@2480: 	  break;
deba@2480: 	}
deba@2480:       }
deba@2480:       
deba@2480:       return lp;
deba@2480:     }
deba@2480: 
deba@2480:     void markPertinentPath(Node node, OrderMap& order_map, 
deba@2480: 			   NodeData& node_data, EdgeLists& edge_lists,
deba@2480: 			   EmbedEdge& embed_edge, MergeRoots& merge_roots) {
deba@2480:       while (embed_edge[node] == INVALID) {
deba@2480: 	int n = merge_roots[node].front();
deba@2480: 	Edge edge = node_data[n].first;
deba@2480: 
deba@2480: 	_kuratowski.set(edge, true);
deba@2480: 	
deba@2480: 	Node pred = node;
deba@2480: 	node = _ugraph.target(edge);
deba@2480: 	while (!pertinent(node, embed_edge, merge_roots)) {
deba@2480: 	  edge = node_data[order_map[node]].first;
deba@2480: 	  if (_ugraph.target(edge) == pred) {
deba@2480: 	    edge = edge_lists[edge].next;
deba@2480: 	  }
deba@2480: 	  _kuratowski.set(edge, true);
deba@2480: 	  pred = node;
deba@2480: 	  node = _ugraph.target(edge);
deba@2480: 	}
deba@2480:       }
deba@2480:       _kuratowski.set(embed_edge[node], true);
deba@2480:     } 
deba@2480: 
deba@2480:     void markPredPath(Node node, Node snode, PredMap& pred_map) {
deba@2480:       while (node != snode) {
deba@2480: 	_kuratowski.set(pred_map[node], true);
deba@2480: 	node = _ugraph.source(pred_map[node]);
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void markFacePath(Node ynode, Node xnode, 
deba@2480: 		      OrderMap& order_map, NodeData& node_data) {
deba@2480:       Edge edge = node_data[order_map[ynode]].first;
deba@2480:       Node node = _ugraph.target(edge);
deba@2480:       _kuratowski.set(edge, true);
deba@2480: 	
deba@2480:       while (node != xnode) {
deba@2480: 	edge = node_data[order_map[node]].first;
deba@2480: 	_kuratowski.set(edge, true);
deba@2480: 	node = _ugraph.target(edge);
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void markInternalPath(std::vector<Edge>& path) {
deba@2480:       for (int i = 0; i < int(path.size()); ++i) {
deba@2480: 	_kuratowski.set(path[i], true);
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void markPilePath(std::vector<Edge>& path) {
deba@2480:       for (int i = 0; i < int(path.size()); ++i) {
deba@2480: 	_kuratowski.set(path[i], true);
deba@2480:       }
deba@2480:     }
deba@2480: 
deba@2480:     void isolateKuratowski(Edge edge, NodeData& node_data, 
deba@2480: 			   EdgeLists& edge_lists, FlipMap& flip_map,
deba@2480: 			   OrderMap& order_map, OrderList& order_list, 
deba@2480: 			   PredMap& pred_map, ChildLists& child_lists,
deba@2480: 			   AncestorMap& ancestor_map, LowMap& low_map, 
deba@2480: 			   EmbedEdge& embed_edge, MergeRoots& merge_roots) {
deba@2480: 
deba@2480:       Node root = _ugraph.source(edge);
deba@2480:       Node enode = _ugraph.target(edge);
deba@2480: 
deba@2480:       int rorder = order_map[root];
deba@2480: 
deba@2480:       TypeMap type_map(_ugraph, 0);
deba@2480: 
deba@2480:       int rn = findComponentRoot(root, enode, child_lists, 
deba@2480: 				 order_map, order_list);
deba@2480: 
deba@2480:       Node xnode = order_list[node_data[rn].next];
deba@2480:       Node ynode = order_list[node_data[rn].prev];
deba@2480: 
deba@2480:       // Minor-A
deba@2480:       {
deba@2480: 	while (!merge_roots[xnode].empty() || !merge_roots[ynode].empty()) {
deba@2480: 	  
deba@2480: 	  if (!merge_roots[xnode].empty()) {
deba@2480: 	    root = xnode;
deba@2480: 	    rn = merge_roots[xnode].front();
deba@2480: 	  } else {
deba@2480: 	    root = ynode;
deba@2480: 	    rn = merge_roots[ynode].front();
deba@2480: 	  }
deba@2480: 	  
deba@2480: 	  xnode = order_list[node_data[rn].next];
deba@2480: 	  ynode = order_list[node_data[rn].prev];
deba@2480: 	}
deba@2480: 	
deba@2480: 	if (root != _ugraph.source(edge)) {
deba@2480: 	  orientComponent(root, rn, order_map, pred_map, 
deba@2480: 			  node_data, edge_lists, flip_map, type_map);
deba@2480: 	  markFacePath(root, root, order_map, node_data);
deba@2480: 	  int xlp = markExternalPath(xnode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 	  int ylp = markExternalPath(ynode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 	  markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@2480: 	  Node lwnode = findPertinent(ynode, order_map, node_data,
deba@2480: 				     embed_edge, merge_roots);
deba@2480: 	  
deba@2480: 	  markPertinentPath(lwnode, order_map, node_data, edge_lists,
deba@2480: 			    embed_edge, merge_roots);
deba@2480: 	  
deba@2480: 	  return;
deba@2480: 	}
deba@2480:       }
deba@2480:       
deba@2480:       orientComponent(root, rn, order_map, pred_map, 
deba@2480: 		      node_data, edge_lists, flip_map, type_map);
deba@2480: 
deba@2480:       Node wnode = findPertinent(ynode, order_map, node_data,
deba@2480: 				 embed_edge, merge_roots);
deba@2480:       setFaceFlags(root, wnode, ynode, xnode, order_map, node_data, type_map);
deba@2480: 
deba@2480:       
deba@2480:       //Minor-B
deba@2480:       if (!merge_roots[wnode].empty()) {
deba@2480: 	int cn = merge_roots[wnode].back();
deba@2480: 	Node rep = order_list[cn - order_list.size()];
deba@2480: 	if (low_map[rep] < rorder) {
deba@2480: 	  markFacePath(root, root, order_map, node_data);
deba@2480: 	  int xlp = markExternalPath(xnode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 	  int ylp = markExternalPath(ynode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 
deba@2480: 	  Node lwnode, lznode;
deba@2480: 	  markCommonPath(wnode, rorder, lwnode, lznode, order_list, 
deba@2480: 			 order_map, node_data, edge_lists, embed_edge, 
deba@2480: 			 merge_roots, child_lists, ancestor_map, low_map);
deba@2480: 	  	  
deba@2480: 	  markPertinentPath(lwnode, order_map, node_data, edge_lists,
deba@2480: 			    embed_edge, merge_roots);
deba@2480: 	  int zlp = markExternalPath(lznode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 
deba@2480: 	  int minlp = xlp < ylp ? xlp : ylp;
deba@2480: 	  if (zlp < minlp) minlp = zlp;
deba@2480: 
deba@2480: 	  int maxlp = xlp > ylp ? xlp : ylp;
deba@2480: 	  if (zlp > maxlp) maxlp = zlp;
deba@2480: 	  
deba@2480: 	  markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@2480: 	  
deba@2480: 	  return;
deba@2480: 	}
deba@2480:       }
deba@2480: 
deba@2480:       Node pxnode, pynode;
deba@2480:       std::vector<Edge> ipath;
deba@2480:       findInternalPath(ipath, wnode, root, type_map, order_map,
deba@2480: 		       node_data, edge_lists);
deba@2480:       setInternalFlags(ipath, type_map);
deba@2480:       pynode = _ugraph.source(ipath.front());
deba@2480:       pxnode = _ugraph.target(ipath.back());
deba@2480: 
deba@2480:       wnode = findPertinent(pynode, order_map, node_data,
deba@2480: 			    embed_edge, merge_roots);
deba@2480:       
deba@2480:       // Minor-C
deba@2480:       {
deba@2480: 	if (type_map[_ugraph.source(ipath.front())] == HIGHY) {
deba@2480: 	  if (type_map[_ugraph.target(ipath.back())] == HIGHX) {
deba@2480: 	    markFacePath(xnode, pxnode, order_map, node_data);
deba@2480: 	  }
deba@2480: 	  markFacePath(root, xnode, order_map, node_data);
deba@2480: 	  markPertinentPath(wnode, order_map, node_data, edge_lists,
deba@2480: 			    embed_edge, merge_roots);
deba@2480: 	  markInternalPath(ipath);
deba@2480: 	  int xlp = markExternalPath(xnode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 	  int ylp = markExternalPath(ynode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 	  markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@2480: 	  return;
deba@2480: 	}
deba@2480: 
deba@2480: 	if (type_map[_ugraph.target(ipath.back())] == HIGHX) {
deba@2480: 	  markFacePath(ynode, root, order_map, node_data);
deba@2480: 	  markPertinentPath(wnode, order_map, node_data, edge_lists,
deba@2480: 			    embed_edge, merge_roots);
deba@2480: 	  markInternalPath(ipath);
deba@2480: 	  int xlp = markExternalPath(xnode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 	  int ylp = markExternalPath(ynode, order_map, child_lists, 
deba@2480: 				     pred_map, ancestor_map, low_map);
deba@2480: 	  markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@2480: 	  return;
deba@2480: 	}
deba@2480:       }
deba@2480: 
deba@2480:       std::vector<Edge> ppath;
deba@2480:       findPilePath(ppath, root, type_map, order_map, node_data, edge_lists);
deba@2480:       
deba@2480:       // Minor-D
deba@2480:       if (!ppath.empty()) {
deba@2480: 	markFacePath(ynode, xnode, order_map, node_data);
deba@2480: 	markPertinentPath(wnode, order_map, node_data, edge_lists,
deba@2480: 			  embed_edge, merge_roots);
deba@2480: 	markPilePath(ppath);
deba@2480: 	markInternalPath(ipath);
deba@2480: 	int xlp = markExternalPath(xnode, order_map, child_lists, 
deba@2480: 				   pred_map, ancestor_map, low_map);
deba@2480: 	int ylp = markExternalPath(ynode, order_map, child_lists, 
deba@2480: 				   pred_map, ancestor_map, low_map);
deba@2480: 	markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@2480: 	return;
deba@2480:       }
deba@2480: 
deba@2480:       // Minor-E*
deba@2480:       {
deba@2480: 
deba@2480: 	if (!external(wnode, rorder, child_lists, ancestor_map, low_map)) {
deba@2480: 	  Node znode = findExternal(pynode, rorder, order_map, 
deba@2480: 				    child_lists, ancestor_map,
deba@2480: 				    low_map, node_data);
deba@2480: 	  
deba@2480: 	  if (type_map[znode] == LOWY) {
deba@2480: 	    markFacePath(root, xnode, order_map, node_data);
deba@2480: 	    markPertinentPath(wnode, order_map, node_data, edge_lists,
deba@2480: 			      embed_edge, merge_roots);
deba@2480: 	    markInternalPath(ipath);
deba@2480: 	    int xlp = markExternalPath(xnode, order_map, child_lists, 
deba@2480: 				       pred_map, ancestor_map, low_map);
deba@2480: 	    int zlp = markExternalPath(znode, order_map, child_lists, 
deba@2480: 				       pred_map, ancestor_map, low_map);
deba@2480: 	    markPredPath(root, order_list[xlp < zlp ? xlp : zlp], pred_map);
deba@2480: 	  } else {
deba@2480: 	    markFacePath(ynode, root, order_map, node_data);
deba@2480: 	    markPertinentPath(wnode, order_map, node_data, edge_lists,
deba@2480: 			      embed_edge, merge_roots);
deba@2480: 	    markInternalPath(ipath);
deba@2480: 	    int ylp = markExternalPath(ynode, order_map, child_lists, 
deba@2480: 				       pred_map, ancestor_map, low_map);
deba@2480: 	    int zlp = markExternalPath(znode, order_map, child_lists, 
deba@2480: 				       pred_map, ancestor_map, low_map);
deba@2480: 	    markPredPath(root, order_list[ylp < zlp ? ylp : zlp], pred_map);
deba@2480: 	  }
deba@2480: 	  return;
deba@2480: 	}
deba@2480: 
deba@2480: 	int xlp = markExternalPath(xnode, order_map, child_lists, 
deba@2480: 				   pred_map, ancestor_map, low_map);
deba@2480: 	int ylp = markExternalPath(ynode, order_map, child_lists, 
deba@2480: 				   pred_map, ancestor_map, low_map);
deba@2480: 	int wlp = markExternalPath(wnode, order_map, child_lists, 
deba@2480: 				   pred_map, ancestor_map, low_map);
deba@2480: 
deba@2480: 	if (wlp > xlp && wlp > ylp) {
deba@2480: 	  markFacePath(root, root, order_map, node_data);
deba@2480: 	  markPredPath(root, order_list[xlp < ylp ? xlp : ylp], pred_map);
deba@2480: 	  return;
deba@2480: 	}
deba@2480: 
deba@2480: 	markInternalPath(ipath);
deba@2480: 	markPertinentPath(wnode, order_map, node_data, edge_lists,
deba@2480: 			  embed_edge, merge_roots);
deba@2480: 
deba@2480: 	if (xlp > ylp && xlp > wlp) {
deba@2480: 	  markFacePath(root, pynode, order_map, node_data);
deba@2480: 	  markFacePath(wnode, xnode, order_map, node_data);
deba@2480: 	  markPredPath(root, order_list[ylp < wlp ? ylp : wlp], pred_map);
deba@2480: 	  return;
deba@2480: 	}
deba@2480: 
deba@2480: 	if (ylp > xlp && ylp > wlp) {
deba@2480: 	  markFacePath(pxnode, root, order_map, node_data);
deba@2480: 	  markFacePath(ynode, wnode, order_map, node_data);
deba@2480: 	  markPredPath(root, order_list[xlp < wlp ? xlp : wlp], pred_map);
deba@2480: 	  return;
deba@2480: 	}
deba@2480: 
deba@2480: 	if (pynode != ynode) {
deba@2480: 	  markFacePath(pxnode, wnode, order_map, node_data);
deba@2480: 
deba@2480: 	  int minlp = xlp < ylp ? xlp : ylp;
deba@2480: 	  if (wlp < minlp) minlp = wlp;
deba@2480: 
deba@2480: 	  int maxlp = xlp > ylp ? xlp : ylp;
deba@2480: 	  if (wlp > maxlp) maxlp = wlp;
deba@2480: 	  
deba@2480: 	  markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@2480: 	  return;
deba@2480: 	}
deba@2480: 
deba@2480: 	if (pxnode != xnode) {
deba@2480: 	  markFacePath(wnode, pynode, order_map, node_data);
deba@2480: 
deba@2480: 	  int minlp = xlp < ylp ? xlp : ylp;
deba@2480: 	  if (wlp < minlp) minlp = wlp;
deba@2480: 
deba@2480: 	  int maxlp = xlp > ylp ? xlp : ylp;
deba@2480: 	  if (wlp > maxlp) maxlp = wlp;
deba@2480: 	  
deba@2480: 	  markPredPath(order_list[maxlp], order_list[minlp], pred_map);
deba@2480: 	  return;
deba@2480: 	}
deba@2480: 
deba@2480: 	markFacePath(root, root, order_map, node_data);
deba@2480: 	int minlp = xlp < ylp ? xlp : ylp;
deba@2480: 	if (wlp < minlp) minlp = wlp;
deba@2480: 	markPredPath(root, order_list[minlp], pred_map);
deba@2480: 	return;
deba@2480:       }
deba@2480:       
deba@2480:     }
deba@2480: 
deba@2480:   };
deba@2480: 
deba@2499:   namespace _planarity_bits {
deba@2499: 
deba@2499:     template <typename UGraph, typename EmbeddingMap>
deba@2499:     void makeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
deba@2499:       DfsVisitor<UGraph> null_visitor;
deba@2499:       DfsVisit<UGraph, DfsVisitor<UGraph> > dfs(ugraph, null_visitor);
deba@2499:       dfs.init();
deba@2499: 
deba@2499:       typename UGraph::Node u = INVALID;
deba@2499:       for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
deba@2499: 	if (!dfs.reached(n)) {
deba@2499: 	  dfs.addSource(n);
deba@2499: 	  dfs.start();
deba@2499: 	  if (u == INVALID) {
deba@2499: 	    u = n;
deba@2499: 	  } else {
deba@2499: 	    typename UGraph::Node v = n;
deba@2499: 	    
deba@2499: 	    typename UGraph::Edge ue = typename UGraph::OutEdgeIt(ugraph, u);
deba@2499: 	    typename UGraph::Edge ve = typename UGraph::OutEdgeIt(ugraph, v);
deba@2499: 
deba@2499: 	    typename UGraph::Edge e = ugraph.direct(ugraph.addEdge(u, v), true);
deba@2499: 	    
deba@2499: 	    if (ue != INVALID) {
deba@2499: 	      embedding[e] = embedding[ue];
deba@2499: 	      embedding[ue] = e;
deba@2499: 	    } else {
deba@2499: 	      embedding[e] = e;
deba@2499: 	    }
deba@2499: 
deba@2499: 	    if (ve != INVALID) {
deba@2499: 	      embedding[ugraph.oppositeEdge(e)] = embedding[ve];
deba@2499: 	      embedding[ve] = ugraph.oppositeEdge(e);
deba@2499: 	    } else {
deba@2499: 	      embedding[ugraph.oppositeEdge(e)] = ugraph.oppositeEdge(e);
deba@2499: 	    }
deba@2499: 	  }
deba@2499: 	}
deba@2499:       }
deba@2499:     }
deba@2499: 
deba@2499:     template <typename UGraph, typename EmbeddingMap>
deba@2499:     void makeBiNodeConnected(UGraph& ugraph, EmbeddingMap& embedding) {
deba@2499:       typename UGraph::template EdgeMap<bool> processed(ugraph);
deba@2499: 
deba@2499:       std::vector<typename UGraph::Edge> edges;
deba@2499:       for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
deba@2499: 	edges.push_back(e);
deba@2499:       }
deba@2499: 
deba@2499:       IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
deba@2499:       
deba@2499:       for (int i = 0; i < int(edges.size()); ++i) {
deba@2499: 	typename UGraph::Edge pp = edges[i];
deba@2499: 	if (processed[pp]) continue;
deba@2499: 
deba@2499: 	typename UGraph::Edge e = embedding[ugraph.oppositeEdge(pp)];
deba@2499: 	processed[e] = true;
deba@2499: 	visited.set(ugraph.source(e), true);
deba@2499: 	
deba@2499: 	typename UGraph::Edge p = e, l = e;
deba@2499: 	e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	
deba@2499: 	while (e != l) {
deba@2499: 	  processed[e] = true;
deba@2499: 
deba@2499: 	  if (visited[ugraph.source(e)]) {
deba@2499: 	    
deba@2499: 	    typename UGraph::Edge n = 
deba@2499: 	      ugraph.direct(ugraph.addEdge(ugraph.source(p), 
deba@2499: 					   ugraph.target(e)), true);
deba@2499: 	    embedding[n] = p;
deba@2499: 	    embedding[ugraph.oppositeEdge(pp)] = n;
deba@2499: 
deba@2499: 	    embedding[ugraph.oppositeEdge(n)] = 
deba@2499: 	      embedding[ugraph.oppositeEdge(e)];
deba@2499: 	    embedding[ugraph.oppositeEdge(e)] = 
deba@2499: 	      ugraph.oppositeEdge(n);
deba@2499: 	    
deba@2499: 	    p = n;
deba@2499: 	    e = embedding[ugraph.oppositeEdge(n)];
deba@2499: 	  } else {
deba@2499: 	    visited.set(ugraph.source(e), true);
deba@2499: 	    pp = p;
deba@2499: 	    p = e;
deba@2499: 	    e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	  }
deba@2499: 	}
deba@2499: 	visited.setAll(false);
deba@2499:       }
deba@2499:     }
deba@2499:     
deba@2499:     
deba@2499:     template <typename UGraph, typename EmbeddingMap>
deba@2499:     void makeMaxPlanar(UGraph& ugraph, EmbeddingMap& embedding) {
deba@2499:       
deba@2499:       typename UGraph::template NodeMap<int> degree(ugraph);
deba@2499: 
deba@2499:       for (typename UGraph::NodeIt n(ugraph); n != INVALID; ++n) {
deba@2499: 	degree[n] = countIncEdges(ugraph, n);
deba@2499:       }
deba@2499: 
deba@2499:       typename UGraph::template EdgeMap<bool> processed(ugraph);
deba@2499:       IterableBoolMap<UGraph, typename UGraph::Node> visited(ugraph, false);
deba@2499: 
deba@2499:       std::vector<typename UGraph::Edge> edges;
deba@2499:       for (typename UGraph::EdgeIt e(ugraph); e != INVALID; ++e) {
deba@2499: 	edges.push_back(e);
deba@2499:       }
deba@2499: 
deba@2499:       for (int i = 0; i < int(edges.size()); ++i) {
deba@2499: 	typename UGraph::Edge e = edges[i];
deba@2499: 
deba@2499: 	if (processed[e]) continue;
deba@2499: 	processed[e] = true;
deba@2499: 
deba@2499: 	typename UGraph::Edge mine = e;
deba@2499: 	int mind = degree[ugraph.source(e)];
deba@2499: 
deba@2499: 	int face_size = 1;	
deba@2499: 
deba@2499: 	typename UGraph::Edge l = e;
deba@2499: 	e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	while (l != e) {
deba@2499: 	  processed[e] = true;
deba@2499: 
deba@2499: 	  ++face_size;
deba@2499: 
deba@2499: 	  if (degree[ugraph.source(e)] < mind) {
deba@2499: 	    mine = e;
deba@2499: 	    mind = degree[ugraph.source(e)];
deba@2499: 	  }
deba@2499: 	  
deba@2499: 	  e = embedding[ugraph.oppositeEdge(e)];	  
deba@2499: 	}
deba@2499: 	
deba@2499: 	if (face_size < 4) {
deba@2499: 	  continue;
deba@2499: 	}
deba@2499: 
deba@2499: 	typename UGraph::Node s = ugraph.source(mine);
deba@2499: 	for (typename UGraph::OutEdgeIt e(ugraph, s); e != INVALID; ++e) {
deba@2499: 	  visited.set(ugraph.target(e), true); 
deba@2499: 	}
deba@2499: 
deba@2499: 	typename UGraph::Edge oppe = INVALID;
deba@2499: 
deba@2499: 	e = embedding[ugraph.oppositeEdge(mine)];
deba@2499: 	e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	while (ugraph.target(e) != s) {
deba@2499: 	  if (visited[ugraph.source(e)]) {
deba@2499: 	    oppe = e;
deba@2499: 	    break;
deba@2499: 	  }
deba@2499: 	  e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	}
deba@2499: 	visited.setAll(false);
deba@2499: 	
deba@2499: 	if (oppe == INVALID) {
deba@2499: 
deba@2499: 	  e = embedding[ugraph.oppositeEdge(mine)];
deba@2499: 	  typename UGraph::Edge pn = mine, p = e;
deba@2499: 
deba@2499: 	  e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	  while (ugraph.target(e) != s) {
deba@2499: 	    typename UGraph::Edge n = 
deba@2499: 	      ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
deba@2499: 
deba@2499: 	    embedding[n] = pn;
deba@2499: 	    embedding[ugraph.oppositeEdge(n)] = e;
deba@2499: 	    embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
deba@2499: 
deba@2499: 	    pn = n;
deba@2499: 	    
deba@2499: 	    p = e;
deba@2499: 	    e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	  }
deba@2499: 
deba@2499: 	  embedding[ugraph.oppositeEdge(e)] = pn;
deba@2499: 
deba@2499: 	} else {
deba@2499: 
deba@2499: 	  mine = embedding[ugraph.oppositeEdge(mine)];
deba@2499: 	  s = ugraph.source(mine);
deba@2499: 	  oppe = embedding[ugraph.oppositeEdge(oppe)];
deba@2499: 	  typename UGraph::Node t = ugraph.source(oppe);
deba@2499: 	  
deba@2499: 	  typename UGraph::Edge ce = ugraph.direct(ugraph.addEdge(s, t), true);
deba@2499: 	  embedding[ce] = mine;
deba@2499: 	  embedding[ugraph.oppositeEdge(ce)] = oppe;
deba@2499: 
deba@2499: 	  typename UGraph::Edge pn = ce, p = oppe;	  
deba@2499: 	  e = embedding[ugraph.oppositeEdge(oppe)];
deba@2499: 	  while (ugraph.target(e) != s) {
deba@2499: 	    typename UGraph::Edge n = 
deba@2499: 	      ugraph.direct(ugraph.addEdge(s, ugraph.source(e)), true);
deba@2499: 
deba@2499: 	    embedding[n] = pn;
deba@2499: 	    embedding[ugraph.oppositeEdge(n)] = e;
deba@2499: 	    embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
deba@2499: 
deba@2499: 	    pn = n;
deba@2499: 	    
deba@2499: 	    p = e;
deba@2499: 	    e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	    
deba@2499: 	  }
deba@2499: 	  embedding[ugraph.oppositeEdge(e)] = pn;
deba@2499: 
deba@2499: 	  pn = ugraph.oppositeEdge(ce), p = mine;	  
deba@2499: 	  e = embedding[ugraph.oppositeEdge(mine)];
deba@2499: 	  while (ugraph.target(e) != t) {
deba@2499: 	    typename UGraph::Edge n = 
deba@2499: 	      ugraph.direct(ugraph.addEdge(t, ugraph.source(e)), true);
deba@2499: 
deba@2499: 	    embedding[n] = pn;
deba@2499: 	    embedding[ugraph.oppositeEdge(n)] = e;
deba@2499: 	    embedding[ugraph.oppositeEdge(p)] = ugraph.oppositeEdge(n);
deba@2499: 
deba@2499: 	    pn = n;
deba@2499: 	    
deba@2499: 	    p = e;
deba@2499: 	    e = embedding[ugraph.oppositeEdge(e)];
deba@2499: 	    
deba@2499: 	  }
deba@2499: 	  embedding[ugraph.oppositeEdge(e)] = pn;
deba@2499: 	}
deba@2499:       }
deba@2499:     }
deba@2499: 
deba@2499:   }
deba@2499: 
deba@2499:   /// \brief Schnyder's planar drawing algorithms
deba@2499:   ///
deba@2499:   /// The planar drawing algorithm calculates location for each node
deba@2499:   /// in the plane, which coordinates satisfies that if each edge is
deba@2499:   /// represented with a straight line then the edges will not
deba@2499:   /// intersect each other.
deba@2499:   ///
deba@2499:   /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
deba@2499:   /// ie. each node will be located in the \c [0,n-2]x[0,n-2] square.
deba@2499:   /// The time complexity of the algorithm is O(n).
deba@2499:   template <typename UGraph>
deba@2499:   class PlanarDrawing {
deba@2499:   public:
deba@2499: 
deba@2499:     UGRAPH_TYPEDEFS(typename UGraph);
deba@2499: 
deba@2499:     /// \brief The point type for store coordinates
deba@2499:     typedef dim2::Point<int> Point;
deba@2499:     /// \brief The map type for store coordinates
deba@2499:     typedef typename UGraph::template NodeMap<Point> PointMap;
deba@2499: 
deba@2499: 
deba@2499:     /// \brief Constructor
deba@2499:     ///
deba@2499:     /// Constructor
deba@2499:     /// \pre The ugraph should be simple, ie. loop and parallel edge free. 
deba@2499:     PlanarDrawing(const UGraph& ugraph)
deba@2499:       : _ugraph(ugraph), _point_map(ugraph) {}
deba@2499: 
deba@2499:   private:
deba@2499: 
deba@2499:     template <typename AuxUGraph, typename AuxEmbeddingMap>
deba@2499:     void drawing(const AuxUGraph& ugraph, 
deba@2499: 		 const AuxEmbeddingMap& next, 
deba@2499: 		 PointMap& point_map) {
deba@2499:       UGRAPH_TYPEDEFS(typename AuxUGraph);
deba@2499: 
deba@2499:       typename AuxUGraph::template EdgeMap<Edge> prev(ugraph);
deba@2499: 
deba@2499:       for (NodeIt n(ugraph); n != INVALID; ++n) {
deba@2499: 	Edge e = OutEdgeIt(ugraph, n);
deba@2499: 	
deba@2499: 	Edge p = e, l = e;
deba@2499: 	
deba@2499: 	e = next[e];
deba@2499: 	while (e != l) {
deba@2499: 	  prev[e] = p;
deba@2499: 	  p = e;
deba@2499: 	  e = next[e];
deba@2499: 	}
deba@2499: 	prev[e] = p;
deba@2499:       }
deba@2499: 
deba@2499:       Node anode, bnode, cnode;
deba@2499: 
deba@2499:       {
deba@2499: 	Edge e = EdgeIt(ugraph);
deba@2499: 	anode = ugraph.source(e);
deba@2499: 	bnode = ugraph.target(e);
deba@2499: 	cnode = ugraph.target(next[ugraph.oppositeEdge(e)]);
deba@2499:       }
deba@2499:       
deba@2499:       IterableBoolMap<AuxUGraph, Node> proper(ugraph, false);
deba@2499:       typename AuxUGraph::template NodeMap<int> conn(ugraph, -1);
deba@2499: 
deba@2499:       conn[anode] = conn[bnode] = -2;      
deba@2499:       {
deba@2499: 	for (OutEdgeIt e(ugraph, anode); e != INVALID; ++e) {
deba@2499: 	  Node m = ugraph.target(e);
deba@2499: 	  if (conn[m] == -1) {
deba@2499: 	    conn[m] = 1;
deba@2499: 	  }
deba@2499: 	}
deba@2499: 	conn[cnode] = 2;
deba@2499: 
deba@2499: 	for (OutEdgeIt e(ugraph, bnode); e != INVALID; ++e) {
deba@2499: 	  Node m = ugraph.target(e);
deba@2499: 	  if (conn[m] == -1) {
deba@2499: 	    conn[m] = 1;
deba@2499: 	  } else if (conn[m] != -2) {
deba@2499: 	    conn[m] += 1;	    
deba@2499: 	    Edge pe = ugraph.oppositeEdge(e);
deba@2499: 	    if (conn[ugraph.target(next[pe])] == -2) {
deba@2499: 	      conn[m] -= 1;
deba@2499: 	    }
deba@2499: 	    if (conn[ugraph.target(prev[pe])] == -2) {
deba@2499: 	      conn[m] -= 1;
deba@2499: 	    }
deba@2499: 
deba@2499: 	    proper.set(m, conn[m] == 1);
deba@2499: 	  }
deba@2499: 	}
deba@2499:       }
deba@2499:       
deba@2499: 
deba@2499:       typename AuxUGraph::template EdgeMap<int> angle(ugraph, -1);
deba@2499: 
deba@2499:       while (proper.trueNum() != 0) {
deba@2499: 	Node n = typename IterableBoolMap<AuxUGraph, Node>::TrueIt(proper);
deba@2499: 	proper.set(n, false);
deba@2499: 	conn[n] = -2;
deba@2499: 
deba@2499: 	for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
deba@2499: 	  Node m = ugraph.target(e);
deba@2499: 	  if (conn[m] == -1) {
deba@2499: 	    conn[m] = 1;
deba@2499: 	  } else if (conn[m] != -2) {
deba@2499: 	    conn[m] += 1;	    
deba@2499: 	    Edge pe = ugraph.oppositeEdge(e);
deba@2499: 	    if (conn[ugraph.target(next[pe])] == -2) {
deba@2499: 	      conn[m] -= 1;
deba@2499: 	    }
deba@2499: 	    if (conn[ugraph.target(prev[pe])] == -2) {
deba@2499: 	      conn[m] -= 1;
deba@2499: 	    }
deba@2499: 
deba@2499: 	    proper.set(m, conn[m] == 1);
deba@2499: 	  }
deba@2499: 	}
deba@2499: 
deba@2499: 	{
deba@2499: 	  Edge e = OutEdgeIt(ugraph, n);
deba@2499: 	  Edge p = e, l = e;
deba@2499: 	  
deba@2499: 	  e = next[e];
deba@2499: 	  while (e != l) {
deba@2499: 	    
deba@2499: 	    if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
deba@2499: 	      Edge f = e;
deba@2499: 	      angle[f] = 0;
deba@2499: 	      f = next[ugraph.oppositeEdge(f)];
deba@2499: 	      angle[f] = 1;
deba@2499: 	      f = next[ugraph.oppositeEdge(f)];
deba@2499: 	      angle[f] = 2;
deba@2499: 	    }
deba@2499: 	    
deba@2499: 	    p = e;
deba@2499: 	    e = next[e];
deba@2499: 	  }
deba@2499: 	  
deba@2499: 	  if (conn[ugraph.target(e)] == -2 && conn[ugraph.target(p)] == -2) {
deba@2499: 	    Edge f = e;
deba@2499: 	    angle[f] = 0;
deba@2499: 	    f = next[ugraph.oppositeEdge(f)];
deba@2499: 	    angle[f] = 1;
deba@2499: 	    f = next[ugraph.oppositeEdge(f)];
deba@2499: 	    angle[f] = 2;
deba@2499: 	  }
deba@2499: 	}
deba@2499:       }
deba@2499: 
deba@2499:       typename AuxUGraph::template NodeMap<Node> apred(ugraph, INVALID);
deba@2499:       typename AuxUGraph::template NodeMap<Node> bpred(ugraph, INVALID);
deba@2499:       typename AuxUGraph::template NodeMap<Node> cpred(ugraph, INVALID);
deba@2499: 
deba@2499:       typename AuxUGraph::template NodeMap<int> apredid(ugraph, -1);
deba@2499:       typename AuxUGraph::template NodeMap<int> bpredid(ugraph, -1);
deba@2499:       typename AuxUGraph::template NodeMap<int> cpredid(ugraph, -1);
deba@2499: 
deba@2499:       for (EdgeIt e(ugraph); e != INVALID; ++e) {
deba@2499: 	if (angle[e] == angle[next[e]]) {
deba@2499: 	  switch (angle[e]) {
deba@2499: 	  case 2:
deba@2499: 	    apred[ugraph.target(e)] = ugraph.source(e);
deba@2499: 	    apredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
deba@2499: 	    break;
deba@2499: 	  case 1:
deba@2499: 	    bpred[ugraph.target(e)] = ugraph.source(e);
deba@2499: 	    bpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
deba@2499: 	    break;
deba@2499: 	  case 0:
deba@2499: 	    cpred[ugraph.target(e)] = ugraph.source(e);
deba@2499: 	    cpredid[ugraph.target(e)] = ugraph.id(ugraph.source(e));
deba@2499: 	    break;
deba@2499: 	  }
deba@2499: 	}
deba@2499:       }
deba@2499: 
deba@2499:       cpred[anode] = INVALID;
deba@2499:       cpred[bnode] = INVALID;
deba@2499: 
deba@2499:       std::vector<Node> aorder, border, corder; 
deba@2499: 
deba@2499:       {
deba@2499: 	typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
deba@2499: 	std::vector<Node> st;
deba@2499: 	for (NodeIt n(ugraph); n != INVALID; ++n) {
deba@2499: 	  if (!processed[n] && n != bnode && n != cnode) {
deba@2499: 	    st.push_back(n);
deba@2499: 	    processed[n] = true;
deba@2499: 	    Node m = apred[n];
deba@2499: 	    while (m != INVALID && !processed[m]) {
deba@2499: 	      st.push_back(m);
deba@2499: 	      processed[m] = true;
deba@2499: 	      m = apred[m];
deba@2499: 	    }
deba@2499: 	    while (!st.empty()) {
deba@2499: 	      aorder.push_back(st.back());
deba@2499: 	      st.pop_back();
deba@2499: 	    }
deba@2499: 	  }
deba@2499: 	}
deba@2499:       }
deba@2499: 
deba@2499:       {
deba@2499: 	typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
deba@2499: 	std::vector<Node> st;
deba@2499: 	for (NodeIt n(ugraph); n != INVALID; ++n) {
deba@2499: 	  if (!processed[n] && n != cnode && n != anode) {
deba@2499: 	    st.push_back(n);
deba@2499: 	    processed[n] = true;
deba@2499: 	    Node m = bpred[n];
deba@2499: 	    while (m != INVALID && !processed[m]) {
deba@2499: 	      st.push_back(m);
deba@2499: 	      processed[m] = true;
deba@2499: 	      m = bpred[m];
deba@2499: 	    }
deba@2499: 	    while (!st.empty()) {
deba@2499: 	      border.push_back(st.back());
deba@2499: 	      st.pop_back();
deba@2499: 	    }
deba@2499: 	  }
deba@2499: 	}
deba@2499:       }
deba@2499: 
deba@2499:       {
deba@2499: 	typename AuxUGraph::template NodeMap<bool> processed(ugraph, false);
deba@2499: 	std::vector<Node> st;
deba@2499: 	for (NodeIt n(ugraph); n != INVALID; ++n) {
deba@2499: 	  if (!processed[n] && n != anode && n != bnode) {
deba@2499: 	    st.push_back(n);
deba@2499: 	    processed[n] = true;
deba@2499: 	    Node m = cpred[n];
deba@2499: 	    while (m != INVALID && !processed[m]) {
deba@2499: 	      st.push_back(m);
deba@2499: 	      processed[m] = true;
deba@2499: 	      m = cpred[m];
deba@2499: 	    }
deba@2499: 	    while (!st.empty()) {
deba@2499: 	      corder.push_back(st.back());
deba@2499: 	      st.pop_back();
deba@2499: 	    }
deba@2499: 	  }
deba@2499: 	}
deba@2499:       }
deba@2499: 
deba@2499:       typename AuxUGraph::template NodeMap<int> atree(ugraph, 0);
deba@2499:       for (int i = aorder.size() - 1; i >= 0; --i) {
deba@2499: 	Node n = aorder[i];
deba@2499: 	atree[n] = 1;
deba@2499: 	for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
deba@2499: 	  if (apred[ugraph.target(e)] == n) {
deba@2499: 	    atree[n] += atree[ugraph.target(e)];
deba@2499: 	  }
deba@2499: 	} 
deba@2499:       }
deba@2499: 
deba@2499:       typename AuxUGraph::template NodeMap<int> btree(ugraph, 0);
deba@2499:       for (int i = border.size() - 1; i >= 0; --i) {
deba@2499: 	Node n = border[i];
deba@2499: 	btree[n] = 1;
deba@2499: 	for (OutEdgeIt e(ugraph, n); e != INVALID; ++e) {
deba@2499: 	  if (bpred[ugraph.target(e)] == n) {
deba@2499: 	    btree[n] += btree[ugraph.target(e)];
deba@2499: 	  }
deba@2499: 	} 
deba@2499:       }
deba@2499:       
deba@2499:       typename AuxUGraph::template NodeMap<int> apath(ugraph, 0);
deba@2499:       apath[bnode] = apath[cnode] = 1;
deba@2499:       typename AuxUGraph::template NodeMap<int> apath_btree(ugraph, 0);
deba@2499:       apath_btree[bnode] = btree[bnode];
deba@2499:       for (int i = 1; i < int(aorder.size()); ++i) {
deba@2499: 	Node n = aorder[i];
deba@2499: 	apath[n] = apath[apred[n]] + 1;
deba@2499: 	apath_btree[n] = btree[n] + apath_btree[apred[n]];
deba@2499:       }
deba@2499: 
deba@2499:       typename AuxUGraph::template NodeMap<int> bpath_atree(ugraph, 0);
deba@2499:       bpath_atree[anode] = atree[anode];
deba@2499:       for (int i = 1; i < int(border.size()); ++i) {
deba@2499: 	Node n = border[i];
deba@2499: 	bpath_atree[n] = atree[n] + bpath_atree[bpred[n]];
deba@2499:       }
deba@2499: 
deba@2499:       typename AuxUGraph::template NodeMap<int> cpath(ugraph, 0);
deba@2499:       cpath[anode] = cpath[bnode] = 1;
deba@2499:       typename AuxUGraph::template NodeMap<int> cpath_atree(ugraph, 0);
deba@2499:       cpath_atree[anode] = atree[anode];
deba@2499:       typename AuxUGraph::template NodeMap<int> cpath_btree(ugraph, 0);
deba@2499:       cpath_btree[bnode] = btree[bnode];
deba@2499:       for (int i = 1; i < int(corder.size()); ++i) {
deba@2499: 	Node n = corder[i];
deba@2499: 	cpath[n] = cpath[cpred[n]] + 1;
deba@2499: 	cpath_atree[n] = atree[n] + cpath_atree[cpred[n]];
deba@2499: 	cpath_btree[n] = btree[n] + cpath_btree[cpred[n]];
deba@2499:       }
deba@2499: 
deba@2499:       typename AuxUGraph::template NodeMap<int> third(ugraph);
deba@2499:       for (NodeIt n(ugraph); n != INVALID; ++n) {
deba@2499: 	point_map[n].x = 
deba@2499: 	  bpath_atree[n] + cpath_atree[n] - atree[n] - cpath[n] + 1;
deba@2499: 	point_map[n].y = 
deba@2499: 	  cpath_btree[n] + apath_btree[n] - btree[n] - apath[n] + 1;
deba@2499:       }
deba@2499:       
deba@2499:     }
deba@2499: 
deba@2499:   public:
deba@2499: 
deba@2499:     /// \brief Calculates the node locations
deba@2499:     ///
deba@2499:     /// This function calculates the node locations.
deba@2499:     bool run() {
deba@2499:       PlanarEmbedding<UGraph> pe(_ugraph);
deba@2499:       if (!pe.run()) return false;
deba@2499:       
deba@2499:       run(pe);
deba@2499:       return true;
deba@2499:     }
deba@2499: 
deba@2499:     /// \brief Calculates the node locations according to a
deba@2499:     /// combinatorical embedding
deba@2499:     ///
deba@2499:     /// This function calculates the node locations. The \c embedding
deba@2499:     /// parameter should contain a valid combinatorical embedding, ie.
deba@2499:     /// a valid cyclic order of the edges.
deba@2499:     template <typename EmbeddingMap>
deba@2499:     void run(const EmbeddingMap& embedding) {
deba@2499:       typedef SmartUEdgeSet<UGraph> AuxUGraph; 
deba@2499: 
deba@2499:       if (3 * countNodes(_ugraph) - 6 == countUEdges(_ugraph)) {
deba@2499: 	drawing(_ugraph, embedding, _point_map);
deba@2499: 	return;
deba@2499:       }
deba@2499: 
deba@2499:       AuxUGraph aux_ugraph(_ugraph);
deba@2499:       typename AuxUGraph::template EdgeMap<typename AuxUGraph::Edge> 
deba@2499: 	aux_embedding(aux_ugraph);
deba@2499: 
deba@2499:       {
deba@2499: 
deba@2499: 	typename UGraph::template UEdgeMap<typename AuxUGraph::UEdge> 
deba@2499: 	  ref(_ugraph);
deba@2499: 	
deba@2499: 	for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
deba@2499: 	  ref[e] = aux_ugraph.addEdge(_ugraph.source(e), _ugraph.target(e));
deba@2499: 	}
deba@2499: 
deba@2499: 	for (UEdgeIt e(_ugraph); e != INVALID; ++e) {
deba@2499: 	  Edge ee = embedding[_ugraph.direct(e, true)];
deba@2499: 	  aux_embedding[aux_ugraph.direct(ref[e], true)] = 
deba@2499: 	    aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
deba@2499: 	  ee = embedding[_ugraph.direct(e, false)];
deba@2499: 	  aux_embedding[aux_ugraph.direct(ref[e], false)] = 
deba@2499: 	    aux_ugraph.direct(ref[ee], _ugraph.direction(ee));
deba@2499: 	}
deba@2499:       }
deba@2499:       _planarity_bits::makeConnected(aux_ugraph, aux_embedding);
deba@2499:       _planarity_bits::makeBiNodeConnected(aux_ugraph, aux_embedding);
deba@2499:       _planarity_bits::makeMaxPlanar(aux_ugraph, aux_embedding);
deba@2499:       drawing(aux_ugraph, aux_embedding, _point_map);
deba@2499:     }
deba@2499: 
deba@2499:     /// \brief The coordinate of the given node
deba@2499:     ///
deba@2499:     /// The coordinate of the given node.
deba@2499:     Point operator[](const Node& node) {
deba@2499:       return _point_map[node];
deba@2499:     }
deba@2499: 
deba@2499:     /// \brief Returns the grid embedding in a \e NodeMap.
deba@2499:     ///
deba@2499:     /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
deba@2499:     const PointMap& coords() const {
deba@2499:       return _point_map;
deba@2499:     }
deba@2499: 
deba@2499:   private:
deba@2499:     
deba@2499:     const UGraph& _ugraph;
deba@2499:     PointMap _point_map;
deba@2499:     
deba@2499:   };
deba@2499: 
deba@2480: }
deba@2480: 
deba@2480: #endif