sPhenix code displayed by LXR master/​JETSCAPE/​external_packages/​gtl/​src/​planarity.cpp	Source navigation Diff markup Identifier search General search
	Version: master Revert   Change

File indexing completed on 2025-08-03 08:19:40

 /* This software is distributed under the GNU Lesser General Public License */
 //==========================================================================
 //
 //   planarity.cpp 
 //
 //==========================================================================
 // $Id: planarity.cpp,v 1.28 2008/02/03 18:12:07 chris Exp $
 
 #include <GTL/planarity.h>
 #include <GTL/pq_tree.h>
 #include <GTL/biconnectivity.h>
 #include <GTL/debug.h>
 
 #include <iostream>
 #include <cstdio>
 #include <fstream>
 #include <sstream>
 
 #ifdef __GTL_MSVCC
 #   ifdef _Debug
 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
 #   error SEARCH NOT ENABLED
 #   endif
 #   define new DEBUG_NEW
 #   undef THIS_FILE
     static char THIS_FILE[] = __FILE__;
 #   endif   // _DEBUG
 #endif  // __GTL_MSVCC
 
 __GTL_BEGIN_NAMESPACE
 
 //--------------------------------------------------------------------------
 //   Planarity Test
 //--------------------------------------------------------------------------
 
 
 planarity::planarity() : 
     algorithm (), emp (false), kup (false), bip (true) 
 {
 #ifdef _DEBUG  
     GTL_debug::init_debug();
 #endif
 };  
 
 planarity::~planarity()
 {
 #ifdef _DEBUG  
     GTL_debug::close_debug();
 #endif
 };  
 
 
 int planarity::check (graph& G) 
 {
     return algorithm::GTL_OK;
 }
 
 bool planarity::run_on_biconnected (graph& G, planar_embedding& em)
 {
 
     if (G.number_of_edges() == 0) return algorithm::GTL_OK;
     
     st_number st_;
     
     //
     // The graph may have self loops. Make sure that we 
     // choose a normal edge for st.
     //
 
     graph::edge_iterator 
     edge_it = G.edges_begin(), 
     edge_end = G.edges_end();
 
     edge st;
 
     while (edge_it != edge_end) {
     if ((*edge_it).source() != (*edge_it).target()) {
         st = *edge_it;
         break;
     }
     ++edge_it;
     }
 
     //
     // G has only selfloops
     //
 
     if (st == edge()) {
     if (emp) {
         em.init (G);
         edge_it = G.edges_begin();
         edge_end = G.edges_end();
     
         for (;edge_it != edge_end; ++edge_it) {
         em.self.push_back (*edge_it);
         }
     }
 
     return algorithm::GTL_OK;
     }
 
     st_.st_edge (st);
     st_.s_node (st.source());
     int res = st_.check(G);
     assert (res == algorithm::GTL_OK);
     res = st_.run(G);
     assert (res == algorithm::GTL_OK);
     int size = G.number_of_nodes();
 
     if (emp) {
     em.init (G);
     }
     
     list<pq_leaf*> neighbors;
     st_number::iterator st_it = st_.begin();
     node curr = *st_it;
     node::out_edges_iterator o_it = curr.out_edges_begin();
     node::out_edges_iterator o_end = curr.out_edges_end();
     node::in_edges_iterator i_it = curr.in_edges_begin();
     node::in_edges_iterator i_end = curr.in_edges_end();
     list<edge> self_loops;
     node opp;
     node_map<int> visited_from (G, 0);
     pq_leaf* tmp_leaf;
     vector< list<pq_leaf*> > leaves (size);
     
     for (; o_it != o_end; ++o_it) {
     opp = curr.opposite (*o_it);
 
     if (opp != curr) {
         if (visited_from[opp] == st_[curr] && emp) {
         em.multi.push_back (*o_it);
         } else {
         visited_from[opp] = st_[curr];
         tmp_leaf = new pq_leaf (st_[opp], st_[curr], *o_it, opp);
         leaves[st_[opp]-1].push_back (tmp_leaf);
         neighbors.push_back (tmp_leaf);
         }
 
     } else if (emp) {
         em.self.push_back (*o_it);
     }
     }
     
     for (; i_it != i_end; ++i_it) {
     opp = curr.opposite (*i_it);
 
     if (opp != curr) {
         if (visited_from[opp] == st_[curr] && emp) {
         em.multi.push_back (*i_it);
         } else {
         visited_from[opp] = st_[curr];
         tmp_leaf = new pq_leaf (st_[opp], st_[curr], *i_it, opp);
         leaves[st_[opp]-1].push_back (tmp_leaf);
         neighbors.push_back (tmp_leaf);
         }
     } 
     }
 
     node_map<list<direction_indicator> > dirs;
 
     //
     // There is a problem with node/edge maps of iterators with Visual C++
     // which I donīt fully understand at the moment. Fortunatly the init for the 
     // maps below is only needed to allocate memory, which is done anyway, when
     // values are assigned to it.
     //
 
 #ifndef __GTL_MSVCC
     dirs.init (G);
 #endif
     pq_tree PQ (st_[curr], curr, neighbors);
     neighbors.erase (neighbors.begin(), neighbors.end());
     ++st_it;
     curr = *st_it;
     
     while (st_[curr] < size) {
         
 #ifdef _DEBUG
     char filename[10] = "out";
     char buffer[12];
 #ifdef __GTL_MSVCC
     _snprintf (buffer, 12, "%s%d.gml", filename, st_[curr]);
 #else 
     snprintf (buffer, 12, "%s%d.gml", filename, st_[curr]);
 #endif
     ofstream os (buffer, ios::out | ios::trunc);
     os << PQ << endl;
     os.close();
     bool ret_flag = PQ.integrity_check();
     assert(ret_flag);
 #endif
         
     if (!PQ.reduce (leaves[st_[curr]-1])) {
 #ifdef _DEBUG
         os.open ("fail.gml", ios::out | ios::trunc);
         os << PQ << endl;
         os.close ();
 #endif          
         if (kup) {
         examine_obstruction (G, st_, curr, 
             PQ.get_fail(), PQ.is_fail_root(), em, dirs, &PQ);
         }
 
         PQ.reset();
         return false;
     }
 
     
     //
     // It seems to be not very comfortable to use in and out iterators to
     // go through the adjacency of a node. For graphs without selfloops this
     // could be replaced by using adj_iterator, but if there are selfloops 
     // they will occur in both the list of outgoing and the one of incoming 
     // edges, and thus two times in the adjacency.
     //
 
     o_it = curr.out_edges_begin();
     o_end = curr.out_edges_end();
     i_it = curr.in_edges_begin();
     i_end = curr.in_edges_end();
         
     for (; o_it != o_end; ++o_it) {
         opp = curr.opposite (*o_it);
             
         if (st_[opp] > st_[curr]) {
         if (visited_from[opp] == st_[curr] && emp) {
             em.multi.push_back (*o_it);
         } else {
             visited_from[opp] = st_[curr];
             tmp_leaf = new pq_leaf (st_[opp], st_[curr], *o_it, opp);
             leaves[st_[opp]-1].push_back (tmp_leaf);
             neighbors.push_back (tmp_leaf);
         }
 
         } else if (st_[opp] == st_[curr] && emp) {
         em.self.push_back (*o_it);
         }
     }
     
     for (; i_it != i_end; ++i_it) {
         opp = curr.opposite (*i_it);
             
         if (st_[opp] > st_[curr]) {
         if (visited_from[opp] == st_[curr] && emp) {
             em.multi.push_back (*i_it);
         } else {
             visited_from[opp] = st_[curr];
             tmp_leaf = new pq_leaf (st_[opp], st_[curr], *i_it, opp);
             leaves[st_[opp]-1].push_back (tmp_leaf);
             neighbors.push_back (tmp_leaf);
         }
         }
     }
         
     if (emp) {
         PQ.replace_pert (st_[curr], curr, neighbors, &em, &(dirs[curr]));
 #ifdef _DEBUG
         GTL_debug::os() << "Embedding of " << st_[curr] << ":: ";
         planar_embedding::iterator adit, adend;
         for (adit = em.adj_edges_begin (curr), adend = em.adj_edges_end (curr); adit != adend; ++adit) {
         GTL_debug::os() << "[" << st_[curr.opposite (*adit)] << "]";
         }
         GTL_debug::os() << endl;
         GTL_debug::os() << "Direction Indicators for: " << st_[curr] << ":: ";
         list<direction_indicator>::iterator dit, dend;
 
         for (dit = dirs[curr].begin(), dend = dirs[curr].end(); dit != dend; ++dit) {
         GTL_debug::os() << "[";
         if ((*dit).direction)
             GTL_debug::os() << ">> " << (*dit).id << " >>";
         else 
             GTL_debug::os() << "<< " << (*dit).id << " <<";
         GTL_debug::os() << "]";
         }
         GTL_debug::os() << endl;
 #endif
 
     } else {
         PQ.replace_pert (st_[curr], curr, neighbors);       
     }
 
     PQ.reset();
 
 
     neighbors.erase (neighbors.begin(), neighbors.end());
     ++st_it;
     curr = *st_it;
     }
     
     if (emp) {
     PQ.get_frontier (em, dirs[curr]);
     
 
     //
     // get self_loops for last node
     //
 
     o_it = curr.out_edges_begin();
     o_end = curr.out_edges_end();
     
     for (; o_it != o_end; ++o_it) {
         if ((*o_it).target() == (*o_it).source()) {
         em.self.push_back (*o_it);
         }
     }
     
     //
     // some adjcacency list of the embedding obtained so far have to be
     // turned.
     // 
 
     correct_embedding(em, st_, dirs);
         
     node_map<int> mark;
     mark.init (G, 0);   
     node_map<symlist<edge>::iterator > upward_begin;
     upward_begin.init (G);
     node tmp;
     
     forall_nodes (tmp, G) {
         upward_begin[tmp] = em.adjacency(tmp).begin();
     } 
 
     extend_embedding(curr, em, mark, upward_begin);
     }
 
     return true;
 }
 
 
 int planarity::run (graph& G) 
 {      
     bool directed = false;
     
     if (G.is_directed()) {
     G.make_undirected();
     directed = true;
     }
     
     biconnectivity biconn;
     
     if (bip) {
     biconn.make_biconnected (true);
     } else {
     biconn.store_components (true);
     }
 
     biconn.check (G);
     biconn.run (G);
     
     if (emp) {
     embedding.init (G);
     }
 
     planar_embedding em;
 
     if (!biconn.is_biconnected() && !bip) {
     biconnectivity::component_iterator c_it, c_end;
 
     for (c_it = biconn.components_begin(), c_end = biconn.components_end(); 
     c_it != c_end; ++c_it) {
         
         switch_to_component (G, c_it);
         
 #ifdef _DEBUG
         GTL_debug::os() << "Component is: " << endl;
         GTL_debug::os() << G << endl;
 #endif
         if (!run_on_biconnected (G, em)) {
         if (directed) {
             G.make_directed();
         }
         
         G.restore_graph();
         planar = false;
         return algorithm::GTL_OK;
         }
      
         if (emp) {
         add_to_embedding (G, em);
         }
     }
     
     G.restore_graph();
 
     } else {
 
     //
     // G is already biconnected
     //
     
     GTL_debug::debug_message ("graph is biconnected\n");
 
     if (!run_on_biconnected (G, embedding)) {
         if (directed) {
         G.make_directed();
         }
         
         planar = false;
         return algorithm::GTL_OK;
     }   
     }
 
     if (bip) {
     list<edge>::iterator it, end;
     it = biconn.additional_begin();
     end = biconn.additional_end();
     
     for (; it != end; ++it) {
 
         if (emp) {
         node s = (*it).source();
         node t = (*it).target();
         embedding.adj[s].erase (embedding.s_pos[*it]);
         embedding.adj[t].erase (embedding.t_pos[*it]);
         }
 
         G.del_edge (*it);
     }
     }
 
     if (directed) {
     G.make_directed();
     }
 
     planar = true;
     return algorithm::GTL_OK;
 }
 
 void planarity::add_to_embedding (graph& G, planar_embedding& em) 
 {
     node n;
     forall_nodes (n, G) {
     planar_embedding::iterator it = em.adj_edges_begin (n);
     planar_embedding::iterator end = em.adj_edges_end (n);
         
     for (; it != end; ++it) {
         embedding.pos (n, *it) = em.pos (n, *it);
     }
         
     embedding.adjacency(n).splice (
         embedding.adj_edges_end (n),
         em.adj_edges_begin (n),
         em.adj_edges_end (n));
     }
 
     embedding.self.splice (
     embedding.self.end(), 
     em.self, em.self.begin(), em.self.end());
     embedding.multi.splice (
     embedding.multi.end(), 
     em.multi, em.multi.begin(), em.multi.end());
 }
 
 
 void planarity::reset () 
 {
     ob_edges.erase (ob_edges.begin(), ob_edges.end());
     ob_nodes.erase (ob_nodes.begin(), ob_nodes.end());
 }
 
 
 void planarity::correct_embedding (
     planar_embedding& em, 
     st_number& st_, 
     node_map<list<direction_indicator> >& dirs) 
 {
     st_number::reverse_iterator it = st_.rbegin();
     st_number::reverse_iterator end = st_.rend();
     bool* turn = new bool[st_[*it]];
     
     for (int i = 0; i < st_[*it]; ++i) {
     turn[i] = false;
     } 
     
     while (it != end) {
     node curr = *it;
         
     if (turn[st_[curr] - 1]) {
         em.adjacency(curr).reverse();
     } 
         
     list<direction_indicator>::iterator d_it = dirs[curr].begin();
         
     while (!dirs[curr].empty()) {
             
         if ((*d_it).direction && turn[st_[curr] - 1] || 
         !(*d_it).direction && !turn[st_[curr] - 1]) {
         turn[(*d_it).id - 1] = true;
         }
         
         d_it = dirs[curr].erase (d_it);
     }
         
     ++it;
     }
     
     delete[] turn;
 }
 
 
 void planarity::extend_embedding (  
     node n, 
     planar_embedding& em, 
     node_map<int>& mark,
     node_map<symlist<edge>::iterator >& upward_begin)
 {
     mark[n] = 1;
     
     symlist<edge>::iterator it = upward_begin[n];
     symlist<edge>::iterator end = em.adjacency(n).end();
     node other;
 
     for (; it != end; ++it) {
     em.pos (n, *it) = it;
     other = n.opposite (*it);
     em.pos (other, *it) = em.push_front (other, *it);
 
     if (mark[other] == 0) {
         extend_embedding (other, em, mark, upward_begin);
     }
     }
 }
 
 void planarity::switch_to_component (graph& G, 
                      biconnectivity::component_iterator c_it)
 {
     //
     // hide all nodes 
     //
 
     list<node> dummy;
     G.induced_subgraph (dummy);
 
     //
     // Restore nodes in this component.
     // 
 
     list<node>::iterator it = (*c_it).first.begin();
     list<node>::iterator end = (*c_it).first.end();
 
     for (; it != end; ++it) {
     G.restore_node (*it);
     }
 
     //
     // Restore edges in this component.
     //
 
     list<edge>::iterator e_it = (*c_it).second.begin();
     list<edge>::iterator e_end = (*c_it).second.end();
   
     for (; e_it != e_end; ++e_it) {
     G.restore_edge (*e_it);
     }
 }
 
 void planarity::examine_obstruction (graph& G, 
                      st_number& st_, 
                      node act, 
                      pq_node* fail, 
                      bool is_root,
                      planar_embedding& em,
                      node_map<list<direction_indicator> >& dirs,
                      pq_tree* PQ)
 {
     node_map<int> used (G, 0);
     node_map<edge> to_father (G);
 
     //
     // Create a dfs-tree of the so called bush form. This is basically a normal dfs 
     // applied to the induced subgraph of G consisting only of the nodes with st_number 
     // 1, ..., st_[act] - 1. The only difference is that edges are always directed from 
     // the lower numbered vertex to higher numbered one.
     //
 
     dfs_bushform (st_.s_node(), used, st_, st_[act], to_father);
 
     if (fail->kind() == pq_node::Q_NODE) {
 
     //
     // In case the reduction failed at a Q-Node we need to know the edges that 
     // form the boundary of the biconnected component, which this Q-Node represents.
     // These can easily be obtained from the embedding we got so far.
     //
 
     q_node* q_fail = fail->Q();
 
     pq_tree::sons_iterator s_it = q_fail->sons.begin();
     pq_tree::sons_iterator s_end = q_fail->sons.end();
     node greatest = fail->n;
 
     while (s_it != s_end)  {
         if ((*s_it)->kind() == pq_node::DIR) {
         direction_indicator* dir = (*s_it)->D();
         pq_tree::sons_iterator tmp = s_it;
         
         if (++tmp == ++(dir->pos)) {
             dir->direction = true;
         } else {
             dir->direction = false;
         }
 
         dirs[act].push_back (*dir);
 
         //
         // chris 2/3/2008:
         //
         // To avoid a memory leak, it is not sufficient to erase it from the
         // PQ-tree (-node). The direction indicator object also has to be
         // deleted. Since it is then not a member of the pertinent subtree any
         // more, it must not be cleared by PQ->reset(). The instance in the
         // dirs node map is a clone!
         //
 
         // s_it = q_fail->sons.erase (s_it);
         s_it = PQ->remove_dir_ind(q_fail, s_it);
         } else {
         if (st_[(*s_it)->up] > st_[greatest]) {
             greatest = (*s_it)->up;
         }
 
         ++s_it;
         }
     }
     
     correct_embedding (em, st_, dirs);
     node_map<int> mark;
     mark.init (G, 0);   
     node_map<symlist<edge>::iterator > upward_begin;
     upward_begin.init (G);
     node tmp;
 
     em.adjacency(fail->n).erase (
         em.adjacency(fail->n).begin(), 
         em.adjacency(fail->n).end());
 
     forall_nodes (tmp, G) {
         upward_begin[tmp] = em.adjacency(tmp).begin();
     }
 
     //
     // chris 2/3/2008:
     //
     // With the code of MR 11/27/2001 the component of the failing Q-node is not found
     // correctly.
     //
 
     extend_embedding(greatest, em, mark, upward_begin);
     
     /*
     //
     // MR 11/27/2001:
     //
     // This is important! We restricted building the embedding to the nodes in
     // the biconnected component which the Q-node fail refers to. But the st-number 
     // obtained for the whole graph restricted to these nodes will not be a st-numbering 
     // for this biconnected component. 
     //
 
     st_number::reverse_iterator st_it, st_end;
 
     for (st_it = st_.rbegin(), st_end = st_.rend();
          st_it != st_end;
          ++st_it) 
     {
         if (mark[*st_it] == 0) {
         extend_embedding (*st_it, em, mark, upward_begin);
         }
     }
     */
 #ifdef _DEBUG
     GTL_debug::os() << "Embedding so far (st_numbered): " << endl;
     em.write_st (GTL_debug::os(), st_);
 #endif 
 
     attachment_cycle (fail->n, em);
 
     if (!q_fail->pert_cons) {
 
         //
         // the reduction failed because there was more than one block 
         // of pertinent children. The reduction in this case assures that 
         // pert_begin and pert_end lie in different blocks and that 
         // --pert_end is empty and lies between these two blocks.
         //
         // This is one of the two cases that may apply when the reduction 
         // fails already in bubble up. The reduction takes care of this.
         //
 
         GTL_debug::debug_message ("CASE C (non consecutive pertinent children)\n");
         pq_tree::sons_iterator tmp = q_fail->pert_begin;
         pq_leaf* leaves[3];
         node nodes[3];
         leaves[0] = search_full_leaf (*tmp);
         nodes[0] = (*tmp)->up;
 
         tmp = q_fail->pert_end;
         leaves[2] = search_full_leaf (*tmp);
         nodes[2] = (*tmp)->up;
         
         --tmp;
         while ((*tmp)->kind() == pq_node::DIR) {
         --tmp;
         }
 
         leaves[1] = search_empty_leaf (*tmp);
         nodes[1] = (*tmp)->up;
         
         case_C (nodes, leaves, st_, to_father, G, q_fail);
 
     } else if (!(*(q_fail->pert_end))->is_endmost && !is_root) {
 
         GTL_debug::debug_message ("CASE D (non-root q-node with both endmost sons empty)\n");
         pq_tree::sons_iterator tmp = q_fail->sons.begin();
         pq_leaf* leaves[3];
         node nodes[3];
         leaves[0] = search_empty_leaf (*tmp);
         nodes[0] = (*tmp)->up;
 
         tmp = --(q_fail->sons.end());
         leaves[2] = search_empty_leaf (*tmp);
         nodes[2] = (*tmp)->up;
         
         tmp = q_fail->pert_begin;
         leaves[1] = search_full_leaf (*tmp);
         nodes[1] = (*tmp)->up;
 
         case_D (nodes, leaves, st_, to_father, G, q_fail);         
 
     } else if (q_fail->partial_count == 1) {
         if (q_fail->partial_pos[0] == q_fail->pert_end) {       
         GTL_debug::debug_message ("CASE D (non-root q-node with partial child at end of pertinent children\n");
         pq_tree::sons_iterator tmp = q_fail->sons.begin();
         pq_leaf* leaves[3];
         node nodes[3];
         leaves[0] = search_empty_leaf (*tmp);
         nodes[0] = (*tmp)->up;
         
         tmp = q_fail->pert_end;
         leaves[2] = search_empty_leaf (*tmp);
         nodes[2] = (*tmp)->up;
         
         tmp = q_fail->pert_begin;
         leaves[1] = search_full_leaf (*tmp);
         nodes[1] = (*tmp)->up;
         
         case_D (nodes, leaves, st_, to_father, G, q_fail);      
         } else {
         GTL_debug::debug_message ("CASE C (q-node with partial children surrounded by pertinent children)\n");
         pq_tree::sons_iterator tmp = q_fail->pert_begin;
         pq_leaf* leaves[3];
         node nodes[3];
         leaves[0] = search_full_leaf (*tmp);
         nodes[0] = (*tmp)->up;
         
         tmp = q_fail->pert_end;
         leaves[2] = search_full_leaf (*tmp);
         nodes[2] = (*tmp)->up;
         
         tmp = q_fail->partial_pos[0];
         leaves[1] = search_empty_leaf (*tmp);
         nodes[1] = (*tmp)->up;
         
         
         case_C (nodes, leaves, st_, to_father, G, q_fail);
         }
         
     } else if ((q_fail->partial_pos[0] == q_fail->pert_begin ||
             q_fail->partial_pos[0] == q_fail->pert_end) && 
            (q_fail->partial_pos[1] == q_fail->pert_begin ||
             q_fail->partial_pos[1] == q_fail->pert_end)) {
 
         if (++(q_fail->sons.begin()) == --(q_fail->sons.end())) {
 
         //
         // q_node with two children, which are both partial.
         //
 
         pq_tree::sons_iterator tmp = q_fail->sons.begin();
         pq_leaf* leaves[4];
         node nodes[2];
         leaves[0] = search_empty_leaf (*tmp);
         nodes[0] = (*tmp)->up;
         leaves[1] = search_full_leaf (*tmp);
         
         ++tmp;
         leaves[2] = search_empty_leaf (*tmp);
         nodes[1] = (*tmp)->up;
         leaves[3] = search_full_leaf (*tmp);
 
         case_E (nodes, leaves, st_, to_father, G, q_fail);      
 
         } else if (q_fail->partial_count == 2) {
         GTL_debug::debug_message ("CASE D (non-root q_node with first and last pertinent children partial)\n");
 
         //
         // sons.begin() is empty, pert_begin is partial, pert_end is partial
         //
 
         pq_tree::sons_iterator tmp = q_fail->sons.begin();
         pq_leaf* leaves[3];
         node nodes[3];
         leaves[0] = search_empty_leaf (*tmp);
         nodes[0] = (*tmp)->up;
         
         tmp = q_fail->pert_end;
         leaves[2] = search_empty_leaf (*tmp);
         nodes[2] = (*tmp)->up;
         
         tmp = q_fail->pert_begin;
 
         if (tmp == q_fail->sons.begin()) {
             ++tmp;
         }
 
         leaves[1] = search_full_leaf (*tmp);
         nodes[1] = (*tmp)->up;
         
         case_D (nodes, leaves, st_, to_father, G, q_fail);      
 
         } else {
         GTL_debug::debug_message ("CASE C (q_node with at least three partial children)\n");
 
         //
         // There must be at least one other partial child among the pertinent.
         //
         
         pq_tree::sons_iterator tmp = q_fail->pert_begin;
         pq_leaf* leaves[3];
         node nodes[3];
         leaves[0] = search_full_leaf (*tmp);
         nodes[0] = (*tmp)->up;
         
         tmp = q_fail->pert_end;
         leaves[2] = search_full_leaf (*tmp);
         nodes[2] = (*tmp)->up;
         
         tmp = q_fail->partial_pos[2];
         leaves[1] = search_empty_leaf (*tmp);
         nodes[1] = (*tmp)->up;
                 
         case_C (nodes, leaves, st_, to_father, G, q_fail);
         }
 
     } else {
         
         //
         // At least one partial son is in between the pertinent sons.
         //
 
         GTL_debug::debug_message ("CASE C (q_node with at least two partial children, at least one surrounded by pertinent)\n");
         pq_tree::sons_iterator tmp = q_fail->pert_begin;
         pq_leaf* leaves[3];
         node nodes[3];
         leaves[0] = search_full_leaf (*tmp);
         nodes[0] = (*tmp)->up;
         
         tmp = q_fail->pert_end;
         leaves[2] = search_full_leaf (*tmp);
         nodes[2] = (*tmp)->up;
         
         tmp = q_fail->partial_pos[0];
         
         if (tmp == q_fail->pert_begin || tmp == q_fail->pert_end) {
         tmp = q_fail->partial_pos[1];
         }
         
         leaves[1] = search_empty_leaf (*tmp);
         nodes[1] = (*tmp)->up;
         
         case_C (nodes, leaves, st_, to_father, G, q_fail);
     }
 
     } else {
 
     //
     // pert_root is a P-Node ==> at least two partial children.
     //
 
     p_node* p_fail = fail->P();
 
     if (p_fail->partial_count == 2) {
         GTL_debug::debug_message ("CASE B (non-root p-node with two partial children)\n");
         case_B (p_fail, act, st_, to_father, G);
     
     } else {
 
         //
         // We have at least three partial children 
         //
 
         GTL_debug::debug_message ("CASE A (p-node with at least three partial children)\n");
         case_A (p_fail, act, st_, to_father, G);
     }   
     }   
 }
 
 
 
 void planarity::case_A (p_node* p_fail,
             node act,
             st_number& st_, 
             node_map<edge> to_father, 
             graph& G)
 {
     node art = p_fail->n;
     ob_nodes.push_back (art);
     ob_nodes.push_back (act);
     node_map<int> mark (G, 0);
     mark[art] = 1;
     pq_leaf* empty[3];
     pq_tree::sons_iterator part_pos = p_fail->partial_sons.begin();
     int i;
     
     for (i = 0; i < 3; ++i) {
     q_node* q_part = (*part_pos)->Q();
     empty[i] = run_through_partial (q_part, mark, to_father, art);
     ++part_pos;
     }
     
     node t_node = st_.s_node().opposite (st_.st_edge());
     mark[t_node] = 1;
     node tmp[3];
     
     for (i = 0; i < 3; ++i) {
     tmp[i] = up_until_marked (empty[i]->n, mark, st_);
     }
     
     assert (tmp[0] == t_node);
     node tmp_node;
     
     //
     // The three paths found meet at the nodes tmp[1] and tmp[2]; the one
     // one with the higher st_number is the one we are looking for. Since the
     // first path always ends at t and it may happen that the paths meet below 
     // t, we might have to delete some of the edges found in the first path.
     //
     
     if (st_[tmp[1]] < st_[tmp[2]]) {
     tmp_node = tmp[2];
     ob_nodes.push_back (tmp[1]);
     } else {
     tmp_node = tmp[1];
     ob_nodes.push_back (tmp[2]);
     }
     
     
     if (tmp_node != t_node) {
     list<edge>::iterator it, end;
     int max_st = st_[tmp_node];
     
     it = ob_edges.begin();
     end = ob_edges.end();
     
     while (it != end) {
         edge cur = *it;
         
         if (st_[cur.source()] > max_st || st_[cur.target()] > max_st) {
         it = ob_edges.erase (it);
         } else {
         ++it;
         }
     }
     }
 }
 
 
 
 void planarity::case_B (p_node* p_fail,
             node act,
             st_number& st_, 
             node_map<edge> to_father, 
             graph& G)
 {
     //
     // P-Node, which is not the root of the pertinent subtree, but has 
     // two partial children. 
     // 
 
     node art = p_fail->n;
     ob_nodes.push_back (art);
     ob_nodes.push_back (act);
     node_map<int> mark (G, 0);
     node_map<int> below (G, 0);
     mark[art] = 1;
     
     //
     // mark edges leading to full leaves from full sons.
     //
     
     pq_tree::sons_iterator it, end;
     for (it = p_fail->full_sons.begin(), end = p_fail->full_sons.end(); it != end; ++it) {
     mark_all_neighbors_of_leaves (*it, below);
     }
     
     //
     // search paths from one full and one empty leaf to the articulation point 
     // in TBk. mark edges leading to full leaves from pertinent sons of part.
     //
     
     pq_tree::sons_iterator part_pos = p_fail->partial_sons.begin();
     q_node* q_part = (*part_pos)->Q();
     pq_leaf* empty1 = run_through_partial (q_part, mark, to_father, art);
     
     for (it = q_part->pert_begin, end = ++(q_part->pert_end); it != end; ++it) {
     mark_all_neighbors_of_leaves (*it, below);
     }
     
     //
     // search paths from one full and one empty leaf to the articulation point 
     // in TBk. mark edges leading to full leaves from pertinent sons of part.
     //
     
     ++part_pos;
     q_part = (*part_pos)->Q();
     pq_leaf* empty2 = run_through_partial (q_part, mark, to_father, art);
 
     
     for (it = q_part->pert_begin, end = ++(q_part->pert_end); it != end; ++it) {
     mark_all_neighbors_of_leaves (*it, below);
     }
 
     //
     // now that all the adjacent edges of act, that lead to art in TBk have been
     // marked search an unmarked adj. edge of act, 
     //
     
     node::adj_edges_iterator a_it, a_end;
     
     for (a_it = act.adj_edges_begin(), a_end = act.adj_edges_end(); a_it != a_end; ++a_it) {
     if (below[act.opposite (*a_it)] == 0 && st_[act.opposite (*a_it)] < st_[act]) {
         break;
     }
     }
     
     assert (a_it != a_end);
     mark[st_.s_node()] = 1;
     mark[art] = 0;
     node tmp = up_until_marked (art, mark, to_father);
     assert (tmp == st_.s_node());
     tmp = up_until_marked (act.opposite (*a_it), mark, to_father);
     assert(tmp != art);
     ob_nodes.push_back (tmp);
     ob_edges.push_back (*a_it);
     ob_edges.push_back (st_.st_edge());
     
     //
     // search from empty1 and empty2 to t.
     //
     
     node t_node = st_.s_node().opposite (st_.st_edge());
     mark[t_node] = 1;
     tmp = up_until_marked (empty1->n, mark, st_);
     assert (tmp == t_node); 
     tmp = up_until_marked (empty2->n, mark, st_);
     ob_nodes.push_back (tmp);
 }
 
 
 void planarity::case_C (node* nodes,
             pq_leaf** leaves,
             st_number& st_, 
             node_map<edge> to_father, 
             graph& G,
             q_node* q_fail) 
 {
     int i;
     node_map<int> mark (G, 0);
     node y_0 = q_fail->n;
 
     for (i = 0; i < 3; ++i) {
     mark[nodes[i]] = 1;    
     edge tmp_edge = leaves[i]->e;
     node tmp_node = leaves[i]->n;
     ob_edges.push_back (tmp_edge);
     tmp_node = up_until_marked (tmp_node.opposite (tmp_edge), mark, to_father);
     assert (tmp_node == nodes[i]);
     ob_nodes.push_back (nodes[i]);
     }
 
     ob_nodes.push_back (y_0);
     mark[st_.s_node()] = 1;
     node tmp = up_until_marked (y_0, mark, to_father);    
     assert (tmp == st_.s_node ());
 
     ob_nodes.push_back (leaves[2]->n);
     ob_edges.push_back (st_.st_edge());
     
     node t_node = st_.s_node().opposite (st_.st_edge());
     mark[t_node] = 1;
     tmp = up_until_marked (leaves[1]->n, mark, st_);
     assert (tmp == t_node); 
     tmp = up_until_marked (leaves[2]->n, mark, st_);
     ob_nodes.push_back (tmp);
 }
 
 
 void planarity::case_D (node* nodes,
             pq_leaf** leaves,
             st_number& st_, 
             node_map<edge> to_father, 
             graph& G,
             q_node* q_fail) 
 {
     //
     // Mark all edges from leaves leading to this component.
     //
     
     node y_0 = q_fail->n;
     pq_tree::sons_iterator it, end;
     node_map<int> below (G, 0);
     node act = leaves[1]->n;
        
     for (it = q_fail->sons.begin(), end = q_fail->sons.end(); it != end; ++it) {
     mark_all_neighbors_of_leaves (*it, below);
     }
     
     node::adj_edges_iterator a_it, a_end;
     
     for (a_it = act.adj_edges_begin(), a_end = act.adj_edges_end(); a_it != a_end; ++a_it) {
     if (below[act.opposite (*a_it)] == 0 && st_[act.opposite (*a_it)] < st_[act]) {
         break;
     }
     }
     
 
     //
     // Since q_fail can't be the root of the pertinent subtree, there must 
     // be at least one edge from act not leading to the component described by 
     // q_fail.
     //
     
     assert (a_it != a_end);
 
     int i;
     node_map<int> mark (G, 0);
 
     for (i = 0; i < 3; ++i) {
     mark[nodes[i]] = 1;    
     edge tmp_edge = leaves[i]->e;
     node tmp_node = leaves[i]->n;
     ob_edges.push_back (tmp_edge);
     tmp_node = up_until_marked (tmp_node.opposite (tmp_edge), mark, to_father);
     assert (tmp_node == nodes[i]);
     ob_nodes.push_back (nodes[i]);
     }
 
     ob_nodes.push_back (y_0);
     mark[st_.s_node()] = 1; 
     node tmp = up_until_marked (y_0, mark, to_father);    
     assert (tmp == st_.s_node ());
     ob_edges.push_back (*a_it);
     tmp = up_until_marked (act.opposite (*a_it), mark, to_father);
 
 
     //
     // The paths from y_0 and from act meet in tmp. If tmp != s_node we have 
     // to delete some edges.
     //
 
     if (tmp != st_.s_node()) {
     list<edge>::iterator it, end;
     int min_st = st_[tmp];
     it = ob_edges.begin();
     end = ob_edges.end();
     
     while (it != end) {
         edge cur = *it;
         
         if (st_[cur.source()] < min_st || st_[cur.target()] < min_st) {
         it = ob_edges.erase (it);
         } else {
         ++it;
         }
     }
     }
 
     ob_nodes.push_back (act);
 
     node t_node = st_.s_node().opposite (st_.st_edge());
     mark[t_node] = 1;
     node tmp_nodes[3];
     
     for (i = 0; i < 3; ++i) {
     tmp_nodes[i] = up_until_marked (leaves[i]->n, mark, st_);
     }
     
     assert (tmp_nodes[0] == t_node);
     
     //
     // The three paths found meet at the nodes tmp[1] and tmp[2]; the one
     // one with the higher st_number is the one we are looking for. Since the
     // first path always ends at t and it may happen that the paths meet below 
     // t, we might have to delete some of the edges found in the first path.
     //
     
     if (st_[tmp_nodes[1]] < st_[tmp_nodes[2]]) {
     tmp = tmp_nodes[2];
     ob_nodes.push_back (tmp_nodes[1]);
     } else {
     tmp = tmp_nodes[1];
     ob_nodes.push_back (tmp_nodes[2]);
     }
     
     
     if (tmp != t_node) {
     list<edge>::iterator it, end;
     int max_st = st_[tmp];
     it = ob_edges.begin();
     end = ob_edges.end();
     
     while (it != end) {
         edge cur = *it;
         
         if (st_[cur.source()] > max_st || st_[cur.target()] > max_st) {
         it = ob_edges.erase (it);
         } else {
         ++it;
         }
     }   
     }
 }
 
 
 void planarity::case_E (node* nodes,
             pq_leaf** leaves,
             st_number& st_, 
             node_map<edge> to_father, 
             graph& G,
             q_node* q_fail) 
 {
 
     //
     // Mark all edges from the act node leading to this component.
     //
     
     node y_0 = q_fail->n;
     pq_tree::sons_iterator it, end;
     node_map<int> below (G, 0);
     node act = leaves[1]->n;
     
     for (it = q_fail->pert_begin, end = ++(q_fail->pert_end); it != end; ++it) {
     mark_all_neighbors_of_leaves (*it, below);
     }
     
     node::adj_edges_iterator a_it, a_end;
     
     for (a_it = act.adj_edges_begin(), a_end = act.adj_edges_end(); a_it != a_end; ++a_it) {
     if (below[act.opposite (*a_it)] == 0 && st_[act.opposite (*a_it)] < st_[act]) {
         break;
     }
     }
     
 
     //
     // Since q_fail can't be the root of the pertinent subtree, there must 
     // be at least one edge from act not leading to the component described by 
     // q_fail.
     //
     
     assert (a_it != a_end);
     
     //
     // The list ob_edges at the moment contains the boundary. we need to know the paths 
     // from y_0 to nodes[0] ( = y_1), from nodes[0] to nodes[1] ( = y_2 ) and from nodes[1]
     // back to y_0, because some of them will be eventually deleted later.
     //
 
     list<edge>::iterator paths_begin[3];
     list<edge>::iterator l_it, l_end;
     node next = y_0;
 
     for (l_it = ob_edges.begin(), l_end = ob_edges.end(); l_it != l_end; ++l_it) {
     next = next.opposite (*l_it);
 
     if (next == nodes[1]) {
         node tmp = nodes[1];
         nodes[1] = nodes[0];
         nodes[0] = tmp;
         pq_leaf* tmp_leaf = leaves[2];
         leaves[2] = leaves[0];
         leaves[0] = tmp_leaf;
         tmp_leaf = leaves[3];
         leaves[3] = leaves[1];
         leaves[1] = tmp_leaf;
 
         paths_begin[0] = l_it;
         ++paths_begin[0];
         break;
     } else if (next == nodes[0]) {
         paths_begin[0] = l_it;
         ++paths_begin[0];
         break;
     }
     }
 
     assert (l_it != l_end);
     ++l_it;
     assert (l_it != l_end);
 
     for (; l_it != l_end; ++l_it) {
     next = next.opposite (*l_it);
 
     if (next == nodes[1]) {
         paths_begin[1] = l_it;
         ++paths_begin[1];
         break;
     }
     }
 
     assert (l_it != l_end);
 
     paths_begin[2] = --l_end;
 
     node y[3];
     int i;
     node_map<int> mark (G, 0);
     list<edge> from_act[3];
     list<edge>::iterator pos;
 
     for (i = 0; i < 2; ++i) {
     mark[nodes[i]] = 1;    
     edge tmp_edge = leaves[2 * i]->e;
     node tmp_node = leaves[2 * i]->n;
     ob_edges.push_back (tmp_edge);
     tmp_node = up_until_marked (tmp_node.opposite (tmp_edge), mark, to_father);
     assert (tmp_node == nodes[i]);
     tmp_edge = leaves[2 * i + 1]->e;
     tmp_node = leaves[2 * i + 1]->n;
     pos = ob_edges.insert (ob_edges.end(), tmp_edge);
     y[i + 1] = up_until_marked (tmp_node.opposite (tmp_edge), mark, to_father);
     from_act[i + 1].splice (from_act[i + 1].begin(), ob_edges, pos, ob_edges.end());
     }
 
     mark[st_.s_node()] = 1; 
     node tmp = up_until_marked (y_0, mark, to_father);    
     assert (tmp == st_.s_node ());
     pos = ob_edges.insert (ob_edges.end(), *a_it);
     y[0] = up_until_marked (act.opposite (*a_it), mark, to_father);
     from_act[0].splice (from_act[0].begin(), ob_edges, pos, ob_edges.end());
 
     node t_node = st_.s_node().opposite (st_.st_edge());
     mark[t_node] = 1;
     node tmp_nodes[3];
     node_map<int> from_where (G, 0);
 
     for (i = 0; i < 2; ++i) {
     pos = --(ob_edges.end());
     tmp_nodes[i] = up_until_marked (leaves[2 * i]->n, mark, st_);
     for (l_it = ++pos, l_end = ob_edges.end(); l_it != l_end; ++l_it) {
         from_where[(*l_it).source()] = i + 1;
         from_where[(*l_it).target()] = i + 1;
     }
     }
     
     assert (tmp_nodes[0] == t_node);
 
     if (y_0 != y[0]) {
     ob_nodes.push_back (y_0);
     ob_nodes.push_back (y[0]);
     ob_nodes.push_back (y[1]);
     ob_nodes.push_back (y[2]);
     ob_nodes.push_back (act);
     ob_nodes.push_back (tmp_nodes[1]);
 
     l_it = paths_begin[0];
     l_end = paths_begin[1];
     ob_edges.erase (l_it, l_end);
 
     for (i = 0; i < 3; ++i) {
         ob_edges.splice (ob_edges.end(), from_act[i], from_act[i].begin(), from_act[i].end());
     }
 
     GTL_debug::debug_message ("CASE E(i)\n");
 
     } else if (nodes[0] != y[1]) {
     ob_nodes.push_back (y_0);
     ob_nodes.push_back (y[1]);
     ob_nodes.push_back (nodes[0]);
     ob_nodes.push_back (y[2]);
     ob_nodes.push_back (act);
     ob_nodes.push_back (tmp_nodes[1]);
     l_it = paths_begin[1];
     l_end = paths_begin[2];
     ++l_end;
     ob_edges.erase (l_it, l_end);
 
     for (i = 0; i < 3; ++i) {
         ob_edges.splice (ob_edges.end(), from_act[i], from_act[i].begin(), from_act[i].end());
     }
 
     GTL_debug::debug_message ("CASE E(ii)\n");
 
     } else if (nodes[1] != y[2]) {
     ob_nodes.push_back (y_0);
     ob_nodes.push_back (y[1]);
     ob_nodes.push_back (nodes[1]);
     ob_nodes.push_back (y[2]);
     ob_nodes.push_back (act);
     ob_nodes.push_back (tmp_nodes[1]);
     l_it = ob_edges.begin();
     l_end = paths_begin[0];
     ob_edges.erase (l_it, l_end);
 
     for (i = 0; i < 3; ++i) {
         ob_edges.splice (ob_edges.end(), from_act[i], from_act[i].begin(), from_act[i].end());
     }
 
     GTL_debug::debug_message ("CASE E(ii)\n");
 
     } else {
     tmp_nodes[2] = up_until_marked (leaves[1]->n, mark, st_);
     ob_nodes.push_back (y_0);
     ob_nodes.push_back (y[1]);
     ob_nodes.push_back (tmp_nodes[1]);
     ob_nodes.push_back (y[2]);
     ob_nodes.push_back (act);
     
     if (st_[tmp_nodes[1]] < st_[tmp_nodes[2]]) {
         ob_nodes.push_back (tmp_nodes[2]);
         l_it = paths_begin[0];
         l_end = paths_begin[1];
         ob_edges.erase (l_it, l_end);
         
         for (i = 1; i < 3; ++i) {
         ob_edges.splice (ob_edges.end(), from_act[i], from_act[i].begin(), from_act[i].end());
         }
 
         GTL_debug::debug_message ("CASE E(iii) (1)\n");
 
     } else if (st_[tmp_nodes[1]] > st_[tmp_nodes[2]]) {
         edge last_edge = *(--(ob_edges.end()));
         ob_nodes.push_back (tmp_nodes[2]);
         ob_edges.splice (ob_edges.end(), from_act[0], from_act[0].begin(), from_act[0].end());
         int from;
 
         if (from_where[last_edge.source()] > 0) {
         from = from_where[last_edge.source()];
         } else {
         from = from_where[last_edge.target()];
         }
         
         assert (from > 0);
 
         if (from == 1) {
         ob_edges.splice (ob_edges.end(), from_act[2], from_act[2].begin(), from_act[2].end());
 
         l_it = paths_begin[1];
         l_end = paths_begin[2];
         ++l_end;
         ob_edges.erase (l_it, l_end);
 
         } else {
         ob_edges.splice (ob_edges.end(), from_act[1], from_act[1].begin(), from_act[1].end());
 
         l_it = ob_edges.begin();
         l_end = paths_begin[0];
         ob_edges.erase (l_it, l_end);
         }
 
         GTL_debug::debug_message ("CASE E(iii) (2)\n");
 
     } else {
         for (i = 0; i < 3; ++i) {
         ob_edges.splice (ob_edges.end(), from_act[i], from_act[i].begin(), from_act[i].end());
         }
 
         GTL_debug::debug_message ("CASE E(iii) (3)\n");
     }
     }   
 
     ob_edges.push_back (st_.st_edge());
 }       
 
 
 pq_leaf* planarity::search_full_leaf (pq_node* n) 
 {
     switch (n->kind()) {
     case pq_node::LEAF:
     return n->L();   
     
     case pq_node::P_NODE:
     case pq_node::Q_NODE:
     return search_full_leaf (*(--(n->sons.end())));
 
     default:
     assert (false);
     return 0;
     }
 }
 
 
 pq_leaf* planarity::search_empty_leaf (pq_node* n) 
 {
     switch (n->kind()) {
     case pq_node::LEAF:
     return n->L();   
     
     case pq_node::Q_NODE:
     case pq_node::P_NODE:
     return search_empty_leaf (*(n->sons.begin()));
     
     default:
     assert (false);
     return 0;
     }
 }
 
 
 
 void planarity::mark_all_neighbors_of_leaves (pq_node* act, node_map<int>& mark)
 {
     if (act->kind() == pq_node::LEAF) {
         mark[((pq_leaf*)act)->e.opposite(((pq_leaf*)act)->n)] = 1;
     } else {
         pq_tree::sons_iterator it, end;
 
         for (it = act->sons.begin(), end = act->sons.end(); it != end; ++it) {
             mark_all_neighbors_of_leaves (*it, mark);
         }
     }
 }
 
 
 pq_leaf* planarity::run_through_partial (q_node* part, node_map<int>& mark, node_map<edge>& to_father, node v) 
 {
     pq_leaf* tmp = search_full_leaf (part);
     edge tmp_edge = tmp->e;
     node tmp_node = tmp->n;
     ob_edges.push_back (tmp_edge);
     tmp_node = up_until_marked (tmp_node.opposite (tmp_edge), mark, to_father);
 
     tmp = search_empty_leaf (part);
     tmp_node = tmp->n;
     tmp_edge = tmp->e;
     ob_edges.push_back (tmp_edge);
     tmp_node = up_until_marked (tmp_node.opposite (tmp_edge), mark, to_father);
     assert (tmp_node != v);
     ob_nodes.push_back (tmp_node);
     
     return tmp->L();
 }
 
 
 node planarity::up_until_marked (node act, node_map<int>& mark, node_map<edge>& to_father) 
 {
     while (mark[act] == 0) {
     mark[act] = 1;
     edge next = to_father[act];
     ob_edges.push_back (next);
     act = act.opposite (next);
     }
 
     return act;
 }
 
 node planarity::up_until_marked (node act, node_map<int>& mark, st_number& st_) 
 {
     while (mark[act] == 0) {
     mark[act] = 1;
     node opp;
     node::adj_edges_iterator it, end;
 
     for (it = act.adj_edges_begin(), end = act.adj_edges_end(); it != end; ++it) {
         opp = act.opposite (*it);
         if (st_[opp] > st_[act]) {
         break;
         }
     }
 
     assert (it != end);
     ob_edges.push_back (*it);
     act = opp;
     }
 
     return act;
 }
 
 void planarity::attachment_cycle (node start, planar_embedding& em) 
 {
     edge act = em.adjacency(start).front();
     node next = start.opposite (act);
     ob_edges.push_back (act);
 
     while (next != start) {
     act = em.cyclic_next (next, act);
     next = next.opposite (act);
     ob_edges.push_back (act);
     }
 }
 
 
 void planarity::dfs_bushform (node n, 
                   node_map<int>& used, 
                   st_number& st_, 
                   int stop, 
                   node_map<edge>& to_father) 
 {    
     used[n] = 1;
     node::adj_edges_iterator it, end;
     
     for (it = n.adj_edges_begin(), end = n.adj_edges_end(); it != end; ++it) {
     edge act = *it;
     node other = n.opposite(act);
     
     if (used[other] == 0 && st_[other] < stop) {
         to_father[other] = *it;
         dfs_bushform (other, used, st_, stop, to_father);
     }
     }
 }
 
 #ifdef _DEBUG
 
 void planarity::write_node(ostream& os, int id, int label, int mark) {
     os << "node [\n" << "id " << id << endl;
     os << "label \"" << label << "\"\n";
     os << "graphics [\n" << "x 100\n" << "y 100 \n";
     if (mark == 1) {
         os << "outline \"#ff0000\"\n";
     }
     os << "]\n";    
     os << "]" << endl;    
 }
 #endif
 
 #ifdef _DEBUG
 void planarity::write_bushform(graph& G, st_number& st_, int k, const char* name, const node_map<int>& mark,
                                const node_map<edge>& to_father) 
 {
     // create the bushform Bk for the k where the test failed 
     st_number::iterator st_it, st_end; 
     int id = 0;
     node_map<int> ids (G);
     ofstream os (name, ios::out | ios::trunc);
 
     os << "graph [\n" << "directed 1" << endl;
     
     for (st_it = st_.begin(), st_end = st_.end(); st_it != st_end && st_[*st_it] <= k; ++st_it) {
         write_node(os, id, st_[*st_it], mark[*st_it]);
         ids[*st_it] = id;
         id++;
     }
 
     for (st_it = st_.begin(), st_end = st_.end(); st_it != st_end && st_[*st_it] <= k; ++st_it) {
         node::adj_edges_iterator ait, aend;
         
         for (ait = (*st_it).adj_edges_begin(), aend = (*st_it).adj_edges_end(); ait != aend; ait++) {
             node other = (*ait).opposite(*st_it);
             int other_id;
             if (st_[*st_it] < st_[other]) {
                 if(st_[other] > k) {
                     write_node(os, id, st_[other], mark[other]);
                     other_id = id;
                     id++;
                 } else {
                     other_id = ids[other];
                 }
 
                 os << "edge [\n" << "source " << ids[*st_it] << "\ntarget " << other_id << endl;
                 if (*ait == to_father[*st_it] || *ait == to_father[other]) {
                     os << "graphics [\n" << "fill \"#0000ff\"" << endl;
                     os << "width 4.0\n]" << endl;
                 } 
                 os << "\n]" << endl;
             }
         }
     }
 
     os << "]" << endl;
 }
 
 #endif
 
 __GTL_END_NAMESPACE
 
 //--------------------------------------------------------------------------
 //   end of file
 //--------------------------------------------------------------------------

This page was automatically generated by the 2.3.7 LXR engine. The LXR team