boyer_myrvold_impl.hpp - Hosted on DriveHQ Cloud IT Platform

//=======================================================================
// Copyright (c) Aaron Windsor 2007
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef __BOYER_MYRVOLD_IMPL_HPP__
#define __BOYER_MYRVOLD_IMPL_HPP__

#include <vector>
#include <list>
#include <boost/utility.hpp>   //for boost::next
#include <boost/config.hpp>    //for std::min macros
#include <boost/shared_ptr.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/planar_detail/face_handles.hpp>
#include <boost/graph/planar_detail/face_iterators.hpp>
#include <boost/graph/planar_detail/bucket_sort.hpp>



namespace boost
{

  template<typename LowPointMap, typename DFSParentMap,
           typename DFSNumberMap, typename LeastAncestorMap,
           typename DFSParentEdgeMap, typename SizeType>
  struct planar_dfs_visitor : public dfs_visitor<>
  {
    planar_dfs_visitor(LowPointMap lpm, DFSParentMap dfs_p, 
                       DFSNumberMap dfs_n, LeastAncestorMap lam,
                       DFSParentEdgeMap dfs_edge) 
      : low(lpm),
        parent(dfs_p),
        df_number(dfs_n),
        least_ancestor(lam),
        df_edge(dfs_edge),
        count(0) 
    {}
    
    
    template <typename Vertex, typename Graph>
    void start_vertex(const Vertex& u, Graph&)
    {
      put(parent, u, u);
      put(least_ancestor, u, count);
    }
    
    
    template <typename Vertex, typename Graph>
    void discover_vertex(const Vertex& u, Graph&)
    {
      put(low, u, count);
      put(df_number, u, count);
      ++count;
    }
    
    template <typename Edge, typename Graph>
    void tree_edge(const Edge& e, Graph& g)
    {
      typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
      vertex_t s(source(e,g));
      vertex_t t(target(e,g));

      put(parent, t, s);
      put(df_edge, t, e);
      put(least_ancestor, t, get(df_number, s));
    }
    
    template <typename Edge, typename Graph>
    void back_edge(const Edge& e, Graph& g)
    {
      typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
      typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
      
      vertex_t s(source(e,g));
      vertex_t t(target(e,g));
      BOOST_USING_STD_MIN();

      if ( t != get(parent, s) ) {
        v_size_t s_low_df_number = get(low, s);
        v_size_t t_df_number = get(df_number, t);
        v_size_t s_least_ancestor_df_number = get(least_ancestor, s);

        put(low, s, 
            min BOOST_PREVENT_MACRO_SUBSTITUTION(s_low_df_number,
                                                 t_df_number)
            );
        
        put(least_ancestor, s, 
            min BOOST_PREVENT_MACRO_SUBSTITUTION(s_least_ancestor_df_number, 
                                                 t_df_number
                                                 )
            );

      }
    }
    
    template <typename Vertex, typename Graph>
    void finish_vertex(const Vertex& u, Graph& g)
    {
      typedef typename graph_traits<Graph>::vertices_size_type v_size_t;

      Vertex u_parent = get(parent, u);
      v_size_t u_parent_lowpoint = get(low, u_parent);
      v_size_t u_lowpoint = get(low, u);
      BOOST_USING_STD_MIN();

      if (u_parent != u)
        {
          put(low, u_parent, 
              min BOOST_PREVENT_MACRO_SUBSTITUTION(u_lowpoint, 
                                                   u_parent_lowpoint
                                                   )
              );
        }
    }
    
    LowPointMap low;
    DFSParentMap parent;
    DFSNumberMap df_number;
    LeastAncestorMap least_ancestor;
    DFSParentEdgeMap df_edge;
    SizeType count;
    
  };






  template <typename Graph,
            typename VertexIndexMap,
            typename StoreOldHandlesPolicy = graph::detail::store_old_handles,
            typename StoreEmbeddingPolicy = graph::detail::recursive_lazy_list
            >
  class boyer_myrvold_impl
  {

    typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
    typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
    typedef typename graph_traits<Graph>::out_edge_iterator 
        out_edge_iterator_t;
    typedef graph::detail::face_handle
        <Graph, StoreOldHandlesPolicy, StoreEmbeddingPolicy> face_handle_t;
    typedef std::vector<vertex_t> vertex_vector_t;
    typedef std::vector<edge_t> edge_vector_t;
    typedef std::list<vertex_t> vertex_list_t;
    typedef std::list< face_handle_t > face_handle_list_t;
    typedef boost::shared_ptr< face_handle_list_t > face_handle_list_ptr_t;
    typedef boost::shared_ptr< vertex_list_t > vertex_list_ptr_t;
    typedef boost::tuple<vertex_t, bool, bool> merge_stack_frame_t;
    typedef std::vector<merge_stack_frame_t> merge_stack_t;

    template <typename T>
    struct map_vertex_to_
    {
      typedef iterator_property_map
          <typename std::vector<T>::iterator, VertexIndexMap> type;
    };

    typedef typename map_vertex_to_<v_size_t>::type vertex_to_v_size_map_t;
    typedef typename map_vertex_to_<vertex_t>::type vertex_to_vertex_map_t;
    typedef typename map_vertex_to_<edge_t>::type vertex_to_edge_map_t;
    typedef typename map_vertex_to_<vertex_list_ptr_t>::type 
        vertex_to_vertex_list_ptr_map_t;
    typedef typename map_vertex_to_< edge_vector_t >::type 
        vertex_to_edge_vector_map_t;
    typedef typename map_vertex_to_<bool>::type vertex_to_bool_map_t;
    typedef typename map_vertex_to_<face_handle_t>::type 
        vertex_to_face_handle_map_t;
    typedef typename map_vertex_to_<face_handle_list_ptr_t>::type 
        vertex_to_face_handle_list_ptr_map_t;
    typedef typename map_vertex_to_<typename vertex_list_t::iterator>::type 
        vertex_to_separated_node_map_t;

    template <typename BicompSideToTraverse = single_side,
              typename VisitorType = lead_visitor,
              typename Time = current_iteration>
    struct face_vertex_iterator
    {
      typedef face_iterator<Graph, 
                            vertex_to_face_handle_map_t, 
                            vertex_t, 
                            BicompSideToTraverse, 
                            VisitorType,
                            Time>
      type;
    };

    template <typename BicompSideToTraverse = single_side,
              typename Time = current_iteration>
    struct face_edge_iterator
    {
      typedef face_iterator<Graph,
                            vertex_to_face_handle_map_t,
                            edge_t,
                            BicompSideToTraverse,
                            lead_visitor,
                            Time>
      type;
    };



  public:

 

    boyer_myrvold_impl(const Graph& arg_g, VertexIndexMap arg_vm):
      g(arg_g),
      vm(arg_vm),

      low_point_vector(num_vertices(g)),
      dfs_parent_vector(num_vertices(g)),
      dfs_number_vector(num_vertices(g)),
      least_ancestor_vector(num_vertices(g)),
      pertinent_roots_vector(num_vertices(g)),
      backedge_flag_vector(num_vertices(g), num_vertices(g) + 1),
      visited_vector(num_vertices(g), num_vertices(g) + 1),
      face_handles_vector(num_vertices(g)),
      dfs_child_handles_vector(num_vertices(g)),
      separated_dfs_child_list_vector(num_vertices(g)),
      separated_node_in_parent_list_vector(num_vertices(g)),
      canonical_dfs_child_vector(num_vertices(g)),
      flipped_vector(num_vertices(g), false),
      backedges_vector(num_vertices(g)),
      dfs_parent_edge_vector(num_vertices(g)),
                        
      vertices_by_dfs_num(num_vertices(g)),

      low_point(low_point_vector.begin(), vm),
      dfs_parent(dfs_parent_vector.begin(), vm),
      dfs_number(dfs_number_vector.begin(), vm),
      least_ancestor(least_ancestor_vector.begin(), vm),
      pertinent_roots(pertinent_roots_vector.begin(), vm),
      backedge_flag(backedge_flag_vector.begin(), vm),
      visited(visited_vector.begin(), vm),
      face_handles(face_handles_vector.begin(), vm),
      dfs_child_handles(dfs_child_handles_vector.begin(), vm),
      separated_dfs_child_list(separated_dfs_child_list_vector.begin(), vm),
      separated_node_in_parent_list
          (separated_node_in_parent_list_vector.begin(), vm),
      canonical_dfs_child(canonical_dfs_child_vector.begin(), vm),
      flipped(flipped_vector.begin(), vm),
      backedges(backedges_vector.begin(), vm),
      dfs_parent_edge(dfs_parent_edge_vector.begin(), vm)

    {

      planar_dfs_visitor
        <vertex_to_v_size_map_t, vertex_to_vertex_map_t,
        vertex_to_v_size_map_t, vertex_to_v_size_map_t,
        vertex_to_edge_map_t, v_size_t> vis
        (low_point, dfs_parent, dfs_number, least_ancestor, dfs_parent_edge);

      // Perform a depth-first search to find each vertex's low point, least
      // ancestor, and dfs tree information
      depth_first_search(g, visitor(vis).vertex_index_map(vm));

      // Sort vertices by their lowpoint - need this later in the constructor
      vertex_vector_t vertices_by_lowpoint(num_vertices(g));
      std::copy( vertices(g).first, vertices(g).second, 
                 vertices_by_lowpoint.begin()
                 );
      bucket_sort(vertices_by_lowpoint.begin(), 
                  vertices_by_lowpoint.end(), 
                  low_point,
                  num_vertices(g)
                  );

      // Sort vertices by their dfs number - need this to iterate by reverse 
      // DFS number in the main loop.
      std::copy( vertices(g).first, vertices(g).second, 
                 vertices_by_dfs_num.begin()
                 );
      bucket_sort(vertices_by_dfs_num.begin(), 
                  vertices_by_dfs_num.end(), 
                  dfs_number,
                  num_vertices(g)
                  );

      // Initialize face handles. A face handle is an abstraction that serves 
      // two uses in our implementation - it allows us to efficiently move 
      // along the outer face of embedded bicomps in a partially embedded 
      // graph, and it provides storage for the planar embedding. Face 
      // handles are implemented by a sequence of edges and are associated 
      // with a particular vertex - the sequence of edges represents the 
      // current embedding of edges around that vertex, and the first and 
      // last edges in the sequence represent the pair of edges on the outer 
      // face that are adjacent to the associated vertex. This lets us embed 
      // edges in the graph by just pushing them on the front or back of the 
      // sequence of edges held by the face handles.
      // 
      // Our algorithm starts with a DFS tree of edges (where every vertex is
      // an articulation point and every edge is a singleton bicomp) and 
      // repeatedly merges bicomps by embedding additional edges. Note that 
      // any bicomp at any point in the algorithm can be associated with a 
      // unique edge connecting the vertex of that bicomp with the lowest DFS
      // number (which we refer to as the "root" of the bicomp) with its DFS 
      // child in the bicomp: the existence of two such edges would contradict
      // the properties of a DFS tree. We refer to the DFS child of the root 
      // of a bicomp as the "canonical DFS child" of the bicomp. Note that a 
      // vertex can be the root of more than one bicomp.
      //
      // We move around the external faces of a bicomp using a few property 
      // maps, which we'll initialize presently:
      //
      // - face_handles: maps a vertex to a face handle that can be used to 
      //   move "up" a bicomp. For a vertex that isn't an articulation point, 
      //   this holds the face handles that can be used to move around that 
      //   vertex's unique bicomp. For a vertex that is an articulation point,
      //   this holds the face handles associated with the unique bicomp that 
      //   the vertex is NOT the root of. These handles can therefore be used 
      //   to move from any point on the outer face of the tree of bicomps 
      //   around the current outer face towards the root of the DFS tree.
      //
      // - dfs_child_handles: these are used to hold face handles for 
      //   vertices that are articulation points - dfs_child_handles[v] holds
      //   the face handles corresponding to vertex u in the bicomp with root
      //   u and canonical DFS child v.
      //
      // - canonical_dfs_child: this property map allows one to determine the
      //   canonical DFS child of a bicomp while traversing the outer face.
      //   This property map is only valid when applied to one of the two 
      //   vertices adjacent to the root of the bicomp on the outer face. To
      //   be more precise, if v is the canonical DFS child of a bicomp,
      //   canonical_dfs_child[dfs_child_handles[v].first_vertex()] == v and 
      //   canonical_dfs_child[dfs_child_handles[v].second_vertex()] == v.
      //
      // - pertinent_roots: given a vertex v, pertinent_roots[v] contains a
      //   list of face handles pointing to the top of bicomps that need to
      //   be visited by the current walkdown traversal (since they lead to
      //   backedges that need to be embedded). These lists are populated by
      //   the walkup and consumed by the walkdown.

      vertex_iterator_t vi, vi_end;
      for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
        {
          vertex_t v(*vi);
          vertex_t parent = dfs_parent[v];

          if (parent != v)
            {
              edge_t parent_edge = dfs_parent_edge[v];
              add_to_embedded_edges(parent_edge, StoreOldHandlesPolicy());
              face_handles[v] = face_handle_t(v, parent_edge, g);
              dfs_child_handles[v] = face_handle_t(parent, parent_edge, g);
            }
          else
            {
              face_handles[v] = face_handle_t(v);
              dfs_child_handles[v] = face_handle_t(parent);
            }

          canonical_dfs_child[v] = v;
          pertinent_roots[v] = face_handle_list_ptr_t(new face_handle_list_t); 
          separated_dfs_child_list[v] = vertex_list_ptr_t(new vertex_list_t);

        }

      // We need to create a list of not-yet-merged depth-first children for
      // each vertex that will be updated as bicomps get merged. We sort each 
      // list by ascending lowpoint, which allows the externally_active 
      // function to run in constant time, and we keep a pointer to each 
      // vertex's representation in its parent's list, which allows merging 
      //in constant time.

      for(typename vertex_vector_t::iterator itr = 
            vertices_by_lowpoint.begin();
          itr != vertices_by_lowpoint.end(); ++itr)
        {
          vertex_t v(*itr);
          vertex_t parent(dfs_parent[v]);
          if (v != parent)
            {
              separated_node_in_parent_list[v] =
                separated_dfs_child_list[parent]->insert
                (separated_dfs_child_list[parent]->end(), v);
            }
        }    

      // The merge stack holds path information during a walkdown iteration
      merge_stack.reserve(num_vertices(g));

    }






    bool is_planar()
    {

      // This is the main algorithm: starting with a DFS tree of embedded 
      // edges (which, since it's a tree, is planar), iterate through all 
      // vertices by reverse DFS number, attempting to embed all backedges
      // connecting the current vertex to vertices with higher DFS numbers.
      // 
      // The walkup is a procedure that examines all such backedges and sets
      // up the required data structures so that they can be searched by the
      // walkdown in linear time. The walkdown does the actual work of
      // embedding edges and flipping bicomps, and can identify when it has
      // come across a kuratowski subgraph.
      //
      // store_old_face_handles caches face handles from the previous
      // iteration - this is used only for the kuratowski subgraph isolation,
      // and is therefore dispatched based on the StoreOldHandlesPolicy.
      //
      // clean_up_embedding does some clean-up and fills in values that have
      // to be computed lazily during the actual execution of the algorithm
      // (for instance, whether or not a bicomp is flipped in the final
      // embedding). It's dispatched on the the StoreEmbeddingPolicy, since
      // it's not needed if an embedding isn't desired.

      typename vertex_vector_t::reverse_iterator vi, vi_end;

      vi_end = vertices_by_dfs_num.rend();
      for(vi = vertices_by_dfs_num.rbegin(); vi != vi_end; ++vi)
        {

          store_old_face_handles(StoreOldHandlesPolicy());

          vertex_t v(*vi);
          
          walkup(v);

          if (!walkdown(v))
            return false;

        }

      clean_up_embedding(StoreEmbeddingPolicy());

      return true;
      
    }






  private:





    void walkup(vertex_t v)
    {

      // The point of the walkup is to follow all backedges from v to 
      // vertices with higher DFS numbers, and update pertinent_roots
      // for the bicomp roots on the path from backedge endpoints up
      // to v. This will set the stage for the walkdown to efficiently
      // traverse the graph of bicomps down from v.

      typedef typename face_vertex_iterator<both_sides>::type walkup_iterator_t;
      
      out_edge_iterator_t oi, oi_end;
      for(tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi)
        {
          edge_t e(*oi);
          vertex_t e_source(source(e,g));
          vertex_t e_target(target(e,g));

          if (e_source == e_target)
            {
              self_loops.push_back(e);
              continue;
            }

          vertex_t w(e_source == v ? e_target : e_source);

          //continue if not a back edge or already embedded
          if (dfs_number[w] < dfs_number[v] || e == dfs_parent_edge[w])
            continue;

          backedges[w].push_back(e);

          v_size_t timestamp = dfs_number[v];         
          backedge_flag[w] = timestamp;

          walkup_iterator_t walkup_itr(w, face_handles);
          walkup_iterator_t walkup_end;
          vertex_t lead_vertex = w;

          while (true)
            {
              
              // Move to the root of the current bicomp or the first visited
              // vertex on the bicomp by going up each side in parallel
              
              while(walkup_itr != walkup_end && 
                    visited[*walkup_itr] != timestamp
                    )
                {
                  lead_vertex = *walkup_itr;
                  visited[lead_vertex] = timestamp;
                  ++walkup_itr;
                }

              // If we've found the root of a bicomp through a path we haven't
              // seen before, update pertinent_roots with a handle to the
              // current bicomp. Otherwise, we've just seen a path we've been 
              // up before, so break out of the main while loop.
              
              if (walkup_itr == walkup_end)
                {
                  vertex_t dfs_child = canonical_dfs_child[lead_vertex];
                  vertex_t parent = dfs_parent[dfs_child];

                  visited[dfs_child_handles[dfs_child].first_vertex()] 
                    = timestamp;
                  visited[dfs_child_handles[dfs_child].second_vertex()] 
                    = timestamp;

                  if (low_point[dfs_child] < dfs_number[v] || 
                      least_ancestor[dfs_child] < dfs_number[v]
                      )
                    {
                      pertinent_roots[parent]->push_back
                        (dfs_child_handles[dfs_child]);
                    }
                  else
                    {
                      pertinent_roots[parent]->push_front
                        (dfs_child_handles[dfs_child]);
                    }

                  if (parent != v && visited[parent] != timestamp)
                    {
                      walkup_itr = walkup_iterator_t(parent, face_handles);
                      lead_vertex = parent;
                    }
                  else
                    break;
                }
              else
                break;
            }

        }      
      
    }
    






    bool walkdown(vertex_t v)
    {
      // This procedure is where all of the action is - pertinent_roots
      // has already been set up by the walkup, so we just need to move
      // down bicomps from v until we find vertices that have been
      // labeled as backedge endpoints. Once we find such a vertex, we
      // embed the corresponding edge and glue together the bicomps on
      // the path connecting the two vertices in the edge. This may
      // involve flipping bicomps along the way.

      vertex_t w; //the other endpoint of the edge we're embedding

      while (!pertinent_roots[v]->empty())
        {
          
          face_handle_t root_face_handle = pertinent_roots[v]->front();
          face_handle_t curr_face_handle = root_face_handle;
          pertinent_roots[v]->pop_front();      

          merge_stack.clear();

          while(true)
            {

              typename face_vertex_iterator<>::type 
                first_face_itr, second_face_itr, face_end;
              vertex_t first_side_vertex 
                = graph_traits<Graph>::null_vertex();
              vertex_t second_side_vertex;
              vertex_t first_tail, second_tail;

              first_tail = second_tail = curr_face_handle.get_anchor();
              first_face_itr = typename face_vertex_iterator<>::type
                (curr_face_handle, face_handles, first_side());
              second_face_itr = typename face_vertex_iterator<>::type
                (curr_face_handle, face_handles, second_side());

              for(; first_face_itr != face_end; ++first_face_itr)
                {
                  vertex_t face_vertex(*first_face_itr);
                  if (pertinent(face_vertex, v) || 
                      externally_active(face_vertex, v)
                      )
                    {
                      first_side_vertex = face_vertex;
                      second_side_vertex = face_vertex;
                      break;
                    }
                  first_tail = face_vertex;
                }

              if (first_side_vertex == graph_traits<Graph>::null_vertex() || 
                  first_side_vertex == curr_face_handle.get_anchor()
                  )
                break;

              for(;second_face_itr != face_end; ++second_face_itr)
                {
                  vertex_t face_vertex(*second_face_itr);
                  if (pertinent(face_vertex, v) || 
                      externally_active(face_vertex, v)
                      )
                    {
                      second_side_vertex = face_vertex;
                      break;
                    }
                  second_tail = face_vertex;
                }

              vertex_t chosen;
              bool chose_first_upper_path;
              if (internally_active(first_side_vertex, v))
                {
                  chosen = first_side_vertex;
                  chose_first_upper_path = true;
                }
              else if (internally_active(second_side_vertex, v))
                {
                  chosen = second_side_vertex;
                  chose_first_upper_path = false;
                }
              else if (pertinent(first_side_vertex, v))
                {
                  chosen = first_side_vertex;
                  chose_first_upper_path = true;
                }
              else if (pertinent(second_side_vertex, v))
                {
                  chosen = second_side_vertex;
                  chose_first_upper_path = false;
                }
              else 
                {

                  // If there's a pertinent vertex on the lower face 
                  // between the first_face_itr and the second_face_itr, 
                  // this graph isn't planar.
                  for(; 
                      *first_face_itr != second_side_vertex; 
                      ++first_face_itr
                      )
                    {
                      vertex_t p(*first_face_itr);
                      if (pertinent(p,v))
                        {
                          //Found a Kuratowski subgraph
                          kuratowski_v = v;
                          kuratowski_x = first_side_vertex;
                          kuratowski_y = second_side_vertex;
                          return false;
                        }
                    }
                  
                  // Otherwise, the fact that we didn't find a pertinent 
                  // vertex on this face is fine - we should set the 
                  // short-circuit edges and break out of this loop to 
                  // start looking at a different pertinent root.
                                    
                  if (first_side_vertex == second_side_vertex)
                    {
                      if (first_tail != v)
                        {
                          vertex_t first 
                            = face_handles[first_tail].first_vertex();
                          vertex_t second 
                            = face_handles[first_tail].second_vertex();
                          tie(first_side_vertex, first_tail) 
                            = make_tuple(first_tail, 
                                         first == first_side_vertex ? 
                                         second : first
                                         );
                        }
                      else if (second_tail != v)
                        {
                          vertex_t first 
                            = face_handles[second_tail].first_vertex();
                          vertex_t second 
                            = face_handles[second_tail].second_vertex();
                          tie(second_side_vertex, second_tail) 
                            = make_tuple(second_tail,
                                         first == second_side_vertex ? 
                                         second : first);
                        }
                      else
                        break;
                    }
                  
                  canonical_dfs_child[first_side_vertex] 
                    = canonical_dfs_child[root_face_handle.first_vertex()];
                  canonical_dfs_child[second_side_vertex] 
                    = canonical_dfs_child[root_face_handle.second_vertex()];
                  root_face_handle.set_first_vertex(first_side_vertex);
                  root_face_handle.set_second_vertex(second_side_vertex);

                  if (face_handles[first_side_vertex].first_vertex() == 
                      first_tail
                      )
                    face_handles[first_side_vertex].set_first_vertex(v);
                  else
                    face_handles[first_side_vertex].set_second_vertex(v);

                  if (face_handles[second_side_vertex].first_vertex() == 
                      second_tail
                      )
                    face_handles[second_side_vertex].set_first_vertex(v);
                  else
                    face_handles[second_side_vertex].set_second_vertex(v);
                    
                  break;
                  
                }


              // When we unwind the stack, we need to know which direction 
              // we came down from on the top face handle
              
              bool chose_first_lower_path = 
                (chose_first_upper_path && 
                 face_handles[chosen].first_vertex() == first_tail) 
                ||
                (!chose_first_upper_path && 
                 face_handles[chosen].first_vertex() == second_tail);

              //If there's a backedge at the chosen vertex, embed it now
              if (backedge_flag[chosen] == dfs_number[v])
                {
                  w = chosen;
                  
                  backedge_flag[chosen] = num_vertices(g) + 1;
                  add_to_merge_points(chosen, StoreOldHandlesPolicy());
                  
                  typename edge_vector_t::iterator ei, ei_end;
                  ei_end = backedges[chosen].end();
                  for(ei = backedges[chosen].begin(); ei != ei_end; ++ei)
                    {
                      edge_t e(*ei);
                      add_to_embedded_edges(e, StoreOldHandlesPolicy());

                      if (chose_first_lower_path)
                        face_handles[chosen].push_first(e, g);
                      else
                        face_handles[chosen].push_second(e, g);
                    }

                }
              else
                {
                  merge_stack.push_back(make_tuple
                     (chosen, chose_first_upper_path, chose_first_lower_path)
                                        );
                  curr_face_handle = *pertinent_roots[chosen]->begin();
                  continue;
                }

              //Unwind the merge stack to the root, merging all bicomps
      
              bool bottom_path_follows_first;
              bool top_path_follows_first;
              bool next_bottom_follows_first = chose_first_upper_path;
              face_handle_t top_handle, bottom_handle;

              vertex_t merge_point = chosen;

              while(!merge_stack.empty())
                {

                  bottom_path_follows_first = next_bottom_follows_first;
                  tie(merge_point, 
                      next_bottom_follows_first, 
                      top_path_follows_first
                      ) = merge_stack.back();
                  merge_stack.pop_back();

                  face_handle_t top_handle(face_handles[merge_point]);
                  face_handle_t bottom_handle
                    (*pertinent_roots[merge_point]->begin());
                  
                  vertex_t bottom_dfs_child = canonical_dfs_child
                    [pertinent_roots[merge_point]->begin()->first_vertex()];

                  remove_vertex_from_separated_dfs_child_list(
                       canonical_dfs_child
                       [pertinent_roots[merge_point]->begin()->first_vertex()]
                       );

                  pertinent_roots[merge_point]->pop_front();

                  add_to_merge_points(top_handle.get_anchor(), 
                                      StoreOldHandlesPolicy()
                                      );
                  
                  if (top_path_follows_first && bottom_path_follows_first)
                    {
                      bottom_handle.flip();
                      top_handle.glue_first_to_second(bottom_handle);
                    }          
                  else if (!top_path_follows_first && 
                           bottom_path_follows_first
                           )
                    {
                      flipped[bottom_dfs_child] = true;
                      top_handle.glue_second_to_first(bottom_handle);
                    }
                  else if (top_path_follows_first && 
                           !bottom_path_follows_first
                           )
                    {
                      flipped[bottom_dfs_child] = true;
                      top_handle.glue_first_to_second(bottom_handle);
                    }
                  else //!top_path_follows_first && !bottom_path_follows_first
                    {
                      bottom_handle.flip();
                      top_handle.glue_second_to_first(bottom_handle);
                    }

                }

              //Finally, embed all edges (v,w) at their upper end points
              canonical_dfs_child[w] 
                = canonical_dfs_child[root_face_handle.first_vertex()];
              
              add_to_merge_points(root_face_handle.get_anchor(), 
                                  StoreOldHandlesPolicy()
                                  );
              
              typename edge_vector_t::iterator ei, ei_end;
              ei_end = backedges[chosen].end();
              for(ei = backedges[chosen].begin(); ei != ei_end; ++ei)
                {              
                  if (next_bottom_follows_first)
                    root_face_handle.push_first(*ei, g);
                  else
                    root_face_handle.push_second(*ei, g);
                }

              backedges[chosen].clear();
              curr_face_handle = root_face_handle;

            }//while(true)
          
        }//while(!pertinent_roots[v]->empty())

      return true;

    }






    void store_old_face_handles(graph::detail::no_old_handles) {}

    void store_old_face_handles(graph::detail::store_old_handles)
    {
      for(typename std::vector<vertex_t>::iterator mp_itr 
            = current_merge_points.begin();
          mp_itr != current_merge_points.end(); ++mp_itr)
        {
          face_handles[*mp_itr].store_old_face_handles();
        }
      current_merge_points.clear();
    }          


    void add_to_merge_points(vertex_t v, graph::detail::no_old_handles) {}

    void add_to_merge_points(vertex_t v, graph::detail::store_old_handles)
    {
      current_merge_points.push_back(v);
    }

    
    void add_to_embedded_edges(edge_t e, graph::detail::no_old_handles) {}

    void add_to_embedded_edges(edge_t e, graph::detail::store_old_handles)
    {
      embedded_edges.push_back(e);
    }




    void clean_up_embedding(graph::detail::no_embedding) {}

    void clean_up_embedding(graph::detail::store_embedding)
    {

      // If the graph isn't biconnected, we'll still have entries
      // in the separated_dfs_child_list for some vertices. Since
      // these represent articulation points, we can obtain a
      // planar embedding no matter what order we embed them in.

      vertex_iterator_t xi, xi_end;
      for(tie(xi,xi_end) = vertices(g); xi != xi_end; ++xi)
        {
          if (!separated_dfs_child_list[*xi]->empty())
            {
              typename vertex_list_t::iterator yi, yi_end;
              yi_end = separated_dfs_child_list[*xi]->end();
              for(yi = separated_dfs_child_list[*xi]->begin(); 
                  yi != yi_end; ++yi
                  )
                {
                  dfs_child_handles[*yi].flip();
                  face_handles[*xi].glue_first_to_second
                    (dfs_child_handles[*yi]);
                }
            }
        }      

      // Up until this point, we've flipped bicomps lazily by setting
      // flipped[v] to true if the bicomp rooted at v was flipped (the
      // lazy aspect of this flip is that all descendents of that vertex
      // need to have their orientations reversed as well). Now, we
      // traverse the DFS tree by DFS number and perform the actual
      // flipping as needed

      typedef typename vertex_vector_t::iterator vertex_vector_itr_t;
      vertex_vector_itr_t vi_end = vertices_by_dfs_num.end();
      for(vertex_vector_itr_t vi = vertices_by_dfs_num.begin(); 
          vi != vi_end; ++vi
          )
        {
          vertex_t v(*vi);
          bool v_flipped = flipped[v];
          bool p_flipped = flipped[dfs_parent[v]];
          if (v_flipped && !p_flipped)
            {
              face_handles[v].flip();
            }
          else if (p_flipped && !v_flipped)
            {
              face_handles[v].flip();
              flipped[v] = true;
            }
          else
            {
              flipped[v] = false;
            }
        }

      // If there are any self-loops in the graph, they were flagged
      // during the walkup, and we should add them to the embedding now.
      // Adding a self loop anywhere in the embedding could never 
      // invalidate the embedding, but they would complicate the traversal
      // if they were added during the walkup/walkdown.

      typename edge_vector_t::iterator ei, ei_end;
      ei_end = self_loops.end();
      for(ei = self_loops.begin(); ei != ei_end; ++ei)
        {
          edge_t e(*ei);
          face_handles[source(e,g)].push_second(e,g);
        }
      
    }




    
    bool pertinent(vertex_t w, vertex_t v)
    {
      // w is pertinent with respect to v if there is a backedge (v,w) or if
      // w is the root of a bicomp that contains a pertinent vertex.

      return backedge_flag[w] == dfs_number[v] || !pertinent_roots[w]->empty();
    }
    


    bool externally_active(vertex_t w, vertex_t v)
    {
      // Let a be any proper depth-first search ancestor of v. w is externally
      // active with respect to v if there exists a backedge (a,w) or a 
      // backedge (a,w_0) for some w_0 in a descendent bicomp of w.

      v_size_t dfs_number_of_v = dfs_number[v];
      return (least_ancestor[w] < dfs_number_of_v) ||
        (!separated_dfs_child_list[w]->empty() &&
         low_point[separated_dfs_child_list[w]->front()] < dfs_number_of_v); 
   }
    

      
    bool internally_active(vertex_t w, vertex_t v)
    {
      return pertinent(w,v) && !externally_active(w,v);
    }    
      



    void remove_vertex_from_separated_dfs_child_list(vertex_t v)
    {
      typename vertex_list_t::iterator to_delete 
        = separated_node_in_parent_list[v];
      garbage.splice(garbage.end(), 
                     *separated_dfs_child_list[dfs_parent[v]], 
                     to_delete, 
                     next(to_delete)
                     );
    }




    
    // End of the implementation of the basic Boyer-Myrvold Algorithm. The rest
    // of the code below implements the isolation of a Kuratowski subgraph in 
    // the case that the input graph is not planar. This is by far the most
    // complicated part of the implementation.




  public:




    template <typename EdgeToBoolPropertyMap, typename EdgeContainer>
    vertex_t kuratowski_walkup(vertex_t v, 
                               EdgeToBoolPropertyMap forbidden_edge,
                               EdgeToBoolPropertyMap goal_edge,
                               EdgeToBoolPropertyMap is_embedded,
                               EdgeContainer& path_edges
                               )
    {
      vertex_t current_endpoint;
      bool seen_goal_edge = false;
      out_edge_iterator_t oi, oi_end;
      
      for(tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi)
        forbidden_edge[*oi] = true;
      
      for(tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi)
        {
          path_edges.clear();
          
          edge_t e(*oi);
          current_endpoint = target(*oi,g) == v ? 
            source(*oi,g) : target(*oi,g);
          
          if (dfs_number[current_endpoint] < dfs_number[v] || 
              is_embedded[e] ||
              v == current_endpoint //self-loop
              )
            {
              //Not a backedge
              continue;
            }
          
          path_edges.push_back(e);
          if (goal_edge[e])
            {
              return current_endpoint;
            }

          typedef typename face_edge_iterator<>::type walkup_itr_t;
          
          walkup_itr_t 
            walkup_itr(current_endpoint, face_handles, first_side());
          walkup_itr_t walkup_end;
          
          seen_goal_edge = false;
          
          while (true)
            {      
              
              if (walkup_itr != walkup_end && forbidden_edge[*walkup_itr])
                break;
              
              while(walkup_itr != walkup_end && 
                    !goal_edge[*walkup_itr] && 
                    !forbidden_edge[*walkup_itr]
                    )
                {
                  edge_t f(*walkup_itr);
                  forbidden_edge[f] = true;
                  path_edges.push_back(f);
                  current_endpoint = 
                    source(f, g) == current_endpoint ? 
                    target(f, g) : 
                    source(f,g);
                  ++walkup_itr;
                }

              if (walkup_itr != walkup_end && goal_edge[*walkup_itr])
                {
                  path_edges.push_back(*walkup_itr);
                  seen_goal_edge = true;
                  break;
                }

              walkup_itr 
                = walkup_itr_t(current_endpoint, face_handles, first_side());
              
            }
          
          if (seen_goal_edge)
            break;
          
        }

      if (seen_goal_edge)
        return current_endpoint;
      else
        return graph_traits<Graph>::null_vertex();

    }








    template <typename OutputIterator, typename EdgeIndexMap>
    void extract_kuratowski_subgraph(OutputIterator o_itr, EdgeIndexMap em)
    {

      // If the main algorithm has failed to embed one of the back-edges from
      // a vertex v, we can use the current state of the algorithm to isolate
      // a Kuratowksi subgraph. The isolation process breaks down into five
      // cases, A - E. The general configuration of all five cases is shown in
      //                  figure 1. There is a vertex v from which the planar
      //         v        embedding process could not proceed. This means that
      //         |        there exists some bicomp containing three vertices
      //       -----      x,y, and z as shown such that x and y are externally
      //      |     |     active with respect to v (which means that there are
      //      x     y     two vertices x_0 and y_0 such that (1) both x_0 and  
      //      |     |     y_0 are proper depth-first search ancestors of v and 
      //       --z--      (2) there are two disjoint paths, one connecting x 
      //                  and x_0 and one connecting y and y_0, both consisting
      //       fig. 1     entirely of unembedded edges). Furthermore, there
      //                  exists a vertex z_0 such that z is a depth-first
      // search ancestor of z_0 and (v,z_0) is an unembedded back-edge from v.
      // x,y and z all exist on the same bicomp, which consists entirely of
      // embedded edges. The five subcases break down as follows, and are
      // handled by the algorithm logically in the order A-E: First, if v is
      // not on the same bicomp as x,y, and z, a K_3_3 can be isolated - this
      // is case A. So, we'll assume that v is on the same bicomp as x,y, and
      // z. If z_0 is on a different bicomp than x,y, and z, a K_3_3 can also
      // be isolated - this is a case B - so we'll assume from now on that v
      // is on the same bicomp as x, y, and z=z_0. In this case, one can use
      // properties of the Boyer-Myrvold algorithm to show the existence of an
      // "x-y path" connecting some vertex on the "left side" of the x,y,z
      // bicomp with some vertex on the "right side" of the bicomp (where the
      // left and right are split by a line drawn through v and z.If either of 
      // the endpoints of the x-y path is above x or y on the bicomp, a K_3_3 
      // can be isolated - this is a case C. Otherwise, both endpoints are at 
      // or below x and y on the bicomp. If there is a vertex alpha on the x-y 
      // path such that alpha is not x or y and there's a path from alpha to v
      // that's disjoint from any of the edges on the bicomp and the x-y path,
      // a K_3_3 can be isolated - this is a case D. Otherwise, properties of
      // the Boyer-Myrvold algorithm can be used to show that another vertex
      // w exists on the lower half of the bicomp such that w is externally
      // active with respect to v. w can then be used to isolate a K_5 - this
      // is the configuration of case E.

      vertex_iterator_t vi, vi_end;
      edge_iterator_t ei, ei_end;
      out_edge_iterator_t oei, oei_end;
      typename std::vector<edge_t>::iterator xi, xi_end;

      // Clear the short-circuit edges - these are needed for the planar 
      // testing/embedding algorithm to run in linear time, but they'll 
      // complicate the kuratowski subgraph isolation
      for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
        {
          face_handles[*vi].reset_vertex_cache();
          dfs_child_handles[*vi].reset_vertex_cache();
        }

      vertex_t v = kuratowski_v;
      vertex_t x = kuratowski_x;
      vertex_t y = kuratowski_y;

      typedef iterator_property_map
        <typename std::vector<bool>::iterator, EdgeIndexMap>
        edge_to_bool_map_t;

      std::vector<bool> is_in_subgraph_vector(num_edges(g), false);
      edge_to_bool_map_t is_in_subgraph(is_in_subgraph_vector.begin(), em);

      std::vector<bool> is_embedded_vector(num_edges(g), false);
      edge_to_bool_map_t is_embedded(is_embedded_vector.begin(), em);

      typename std::vector<edge_t>::iterator embedded_itr, embedded_end;
      embedded_end = embedded_edges.end();
      for(embedded_itr = embedded_edges.begin(); 
          embedded_itr != embedded_end; ++embedded_itr
          )
        is_embedded[*embedded_itr] = true;

      // upper_face_vertex is true for x,y, and all vertices above x and y in 
      // the bicomp
      std::vector<bool> upper_face_vertex_vector(num_vertices(g), false);
      vertex_to_bool_map_t upper_face_vertex
        (upper_face_vertex_vector.begin(), vm);

      std::vector<bool> lower_face_vertex_vector(num_vertices(g), false);
      vertex_to_bool_map_t lower_face_vertex
        (lower_face_vertex_vector.begin(), vm);

      // These next few variable declarations are all things that we need
      // to find.
      vertex_t z; 
      vertex_t bicomp_root;
      vertex_t w = graph_traits<Graph>::null_vertex();
      face_handle_t w_handle;
      face_handle_t v_dfchild_handle;
      vertex_t first_x_y_path_endpoint = graph_traits<Graph>::null_vertex();
      vertex_t second_x_y_path_endpoint = graph_traits<Graph>::null_vertex();
      vertex_t w_ancestor = v;

      enum case_t{NO_CASE_CHOSEN, CASE_A, CASE_B, CASE_C, CASE_D, CASE_E};
      case_t chosen_case = NO_CASE_CHOSEN;

      std::vector<edge_t> x_external_path;
      std::vector<edge_t> y_external_path;
      std::vector<edge_t> case_d_edges;

      std::vector<edge_t> z_v_path;
      std::vector<edge_t> w_path;

      //first, use a walkup to find a path from V that starts with a
      //backedge from V, then goes up until it hits either X or Y
      //(but doesn't find X or Y as the root of a bicomp)

      typename face_vertex_iterator<>::type 
        x_upper_itr(x, face_handles, first_side());
      typename face_vertex_iterator<>::type 
        x_lower_itr(x, face_handles, second_side());
      typename face_vertex_iterator<>::type face_itr, face_end;

      // Don't know which path from x is the upper or lower path - 
      // we'll find out here
      for(face_itr = x_upper_itr; face_itr != face_end; ++face_itr)
        {
          if (*face_itr == y)
            {
              std::swap(x_upper_itr, x_lower_itr);
              break;
            }
        }

      upper_face_vertex[x] = true;

      vertex_t current_vertex = x;
      vertex_t previous_vertex;
      for(face_itr = x_upper_itr; face_itr != face_end; ++face_itr)
        {
          previous_vertex = current_vertex;
          current_vertex = *face_itr;
          upper_face_vertex[current_vertex] = true;
        }

      v_dfchild_handle 
        = dfs_child_handles[canonical_dfs_child[previous_vertex]];
      
      for(face_itr = x_lower_itr; *face_itr != y; ++face_itr)
        {
          vertex_t current_vertex(*face_itr);
          lower_face_vertex[current_vertex] = true;

          typename face_handle_list_t::iterator roots_itr, roots_end;

          if (w == graph_traits<Graph>::null_vertex()) //haven't found a w yet
            {
              roots_end = pertinent_roots[current_vertex]->end();
              for(roots_itr = pertinent_roots[current_vertex]->begin(); 
                  roots_itr != roots_end; ++roots_itr
                  )
                {
                  if (low_point[canonical_dfs_child[roots_itr->first_vertex()]]
                      < dfs_number[v]
                      )
                    {
                      w = current_vertex;
                      w_handle = *roots_itr;
                      break;
                    }
                }
            }

        }

      for(; face_itr != face_end; ++face_itr)
        {
          vertex_t current_vertex(*face_itr);
          upper_face_vertex[current_vertex] = true;
          bicomp_root = current_vertex;
        }

      typedef typename face_edge_iterator<>::type walkup_itr_t;

      std::vector<bool> outer_face_edge_vector(num_edges(g), false);
      edge_to_bool_map_t outer_face_edge(outer_face_edge_vector.begin(), em);

      walkup_itr_t walkup_end;
      for(walkup_itr_t walkup_itr(x, face_handles, first_side()); 
          walkup_itr != walkup_end; ++walkup_itr
          )
        {
          outer_face_edge[*walkup_itr] = true;
          is_in_subgraph[*walkup_itr] = true;
        }

      for(walkup_itr_t walkup_itr(x, face_handles, second_side()); 
          walkup_itr != walkup_end; ++walkup_itr
          )
        {
          outer_face_edge[*walkup_itr] = true;
          is_in_subgraph[*walkup_itr] = true;
        }

      std::vector<bool> forbidden_edge_vector(num_edges(g), false);
      edge_to_bool_map_t forbidden_edge(forbidden_edge_vector.begin(), em);

      std::vector<bool> goal_edge_vector(num_edges(g), false);
      edge_to_bool_map_t goal_edge(goal_edge_vector.begin(), em);


      //Find external path to x and to y

      for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        {
          edge_t e(*ei);
          goal_edge[e] 
            = !outer_face_edge[e] && (source(e,g) == x || target(e,g) == x);
          forbidden_edge[*ei] = outer_face_edge[*ei];
        }

      vertex_t x_ancestor = v;
      vertex_t x_endpoint = graph_traits<Graph>::null_vertex();
      
      while(x_endpoint == graph_traits<Graph>::null_vertex())
        { 
          x_ancestor = dfs_parent[x_ancestor];
          x_endpoint = kuratowski_walkup(x_ancestor, 
                                         forbidden_edge, 
                                         goal_edge,
                                         is_embedded,
                                         x_external_path
                                         );
          
        }            


      for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        {
          edge_t e(*ei);
          goal_edge[e] 
            = !outer_face_edge[e] && (source(e,g) == y || target(e,g) == y);
          forbidden_edge[*ei] = outer_face_edge[*ei];
        }

      vertex_t y_ancestor = v;
      vertex_t y_endpoint = graph_traits<Graph>::null_vertex();
      
      while(y_endpoint == graph_traits<Graph>::null_vertex())
        { 
          y_ancestor = dfs_parent[y_ancestor];
          y_endpoint = kuratowski_walkup(y_ancestor, 
                                         forbidden_edge, 
                                         goal_edge,
                                         is_embedded,
                                         y_external_path
                                         );
          
        }            
      

      vertex_t parent, child;
      
      //If v isn't on the same bicomp as x and y, it's a case A
      if (bicomp_root != v)
        {
          chosen_case = CASE_A;

          for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
            if (lower_face_vertex[*vi])
              for(tie(oei,oei_end) = out_edges(*vi,g); oei != oei_end; ++oei)
                if(!outer_face_edge[*oei])
                  goal_edge[*oei] = true;
          
          for(tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
            forbidden_edge[*ei] = outer_face_edge[*ei];
          
          z = kuratowski_walkup
            (v, forbidden_edge, goal_edge, is_embedded, z_v_path);
          
        }
      else if (w != graph_traits<Graph>::null_vertex())
        {
          chosen_case = CASE_B;

          for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
            {
              edge_t e(*ei);
              goal_edge[e] = false;
              forbidden_edge[e] = outer_face_edge[e];
            }
          
          goal_edge[w_handle.first_edge()] = true;
          goal_edge[w_handle.second_edge()] = true;

          z = kuratowski_walkup(v,
                                forbidden_edge, 
                                goal_edge,
                                is_embedded,
                                z_v_path
                                );
              

          for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
            {
              forbidden_edge[*ei] = outer_face_edge[*ei];
            }

          typename std::vector<edge_t>::iterator pi, pi_end;
          pi_end = z_v_path.end();
          for(pi = z_v_path.begin(); pi != pi_end; ++pi)
            {
              goal_edge[*pi] = true;
            }
          
          w_ancestor = v;
          vertex_t w_endpoint = graph_traits<Graph>::null_vertex();
          
          while(w_endpoint == graph_traits<Graph>::null_vertex())
            { 
              w_ancestor = dfs_parent[w_ancestor];
              w_endpoint = kuratowski_walkup(w_ancestor, 
                                             forbidden_edge, 
                                             goal_edge,
                                             is_embedded,
                                             w_path
                                             );
              
            }            
          
          // We really want both the w walkup and the z walkup to finish on 
          // exactly the same edge, but for convenience (since we don't have 
          // control over which side of a bicomp a walkup moves up) we've 
          // defined the walkup to either end at w_handle.first_edge() or 
          // w_handle.second_edge(). If both walkups ended at different edges, 
          // we'll do a little surgery on the w walkup path to make it follow 
          // the other side of the final bicomp.

          if ((w_path.back() == w_handle.first_edge() && 
               z_v_path.back() == w_handle.second_edge()) 
              ||
              (w_path.back() == w_handle.second_edge() && 
               z_v_path.back() == w_handle.first_edge())
              )
            {
              walkup_itr_t wi, wi_end;
              edge_t final_edge = w_path.back();
              vertex_t anchor 
                = source(final_edge, g) == w_handle.get_anchor() ? 
                target(final_edge, g) : source(final_edge, g);
              if (face_handles[anchor].first_edge() == final_edge)
                wi = walkup_itr_t(anchor, face_handles, second_side());
              else
                wi = walkup_itr_t(anchor, face_handles, first_side());

              w_path.pop_back();

              for(; wi != wi_end; ++wi)
                {
                  edge_t e(*wi);
                  if (w_path.back() == e)
                    w_path.pop_back();
                  else
                    w_path.push_back(e);
                }
            }

          
        }
      else 
        {

          //We need to find a valid z, since the x-y path re-defines the lower
          //face, and the z we found earlier may now be on the upper face.

          chosen_case = CASE_E;


          // The z we've used so far is just an externally active vertex on the
          // lower face path, but may not be the z we need for a case C, D, or
          // E subgraph. the z we need now is any externally active vertex on 
          // the lower face path with both old_face_handles edges on the outer
          // face. Since we know an x-y path exists, such a z must also exist.

          //TODO: find this z in the first place.

          //find the new z

          for(face_itr = x_lower_itr; *face_itr != y; ++face_itr)
            {
              vertex_t possible_z(*face_itr);
              if (pertinent(possible_z,v) && 
                  outer_face_edge[face_handles[possible_z].old_first_edge()] &&
                  outer_face_edge[face_handles[possible_z].old_second_edge()]
                  )
                {
                  z = possible_z;
                  break;
                }
            }

          //find x-y path, and a w if one exists.

          if (externally_active(z,v))
            w = z;
          

          typedef typename face_edge_iterator
            <single_side, previous_iteration>::type old_face_iterator_t; 

          old_face_iterator_t 
            first_old_face_itr(z, face_handles, first_side());
          old_face_iterator_t 
            second_old_face_itr(z, face_handles, second_side());
          old_face_iterator_t old_face_itr, old_face_end;

          std::vector<old_face_iterator_t> old_face_iterators;
          old_face_iterators.push_back(first_old_face_itr);
          old_face_iterators.push_back(second_old_face_itr);

          std::vector<bool> x_y_path_vertex_vector(num_vertices(g), false);
          vertex_to_bool_map_t x_y_path_vertex
            (x_y_path_vertex_vector.begin(), vm);

          typename std::vector<old_face_iterator_t>::iterator 
            of_itr, of_itr_end;
          of_itr_end = old_face_iterators.end(); 
          for(of_itr = old_face_iterators.begin(); 
              of_itr != of_itr_end; ++of_itr
              )
            {

              old_face_itr = *of_itr;

              vertex_t previous_vertex;
              bool seen_x_or_y = false;
              vertex_t current_vertex = z;
              for(; old_face_itr != old_face_end; ++old_face_itr)
                {
                  edge_t e(*old_face_itr);
                  previous_vertex = current_vertex;
                  current_vertex = source(e,g) == current_vertex ? 
                    target(e,g) : source(e,g);
                  
                  if (current_vertex == x || current_vertex == y)
                    seen_x_or_y = true;

                  if (w == graph_traits<Graph>::null_vertex() && 
                      externally_active(current_vertex,v) &&
                      outer_face_edge[e] &&
                      outer_face_edge[*next(old_face_itr)] &&
                      !seen_x_or_y
                      )
                    {
                      w = current_vertex;
                    }
                  
                  if (!outer_face_edge[e])
                    {
                      if (!upper_face_vertex[current_vertex] && 
                          !lower_face_vertex[current_vertex]
                          )
                        {
                          x_y_path_vertex[current_vertex] = true;
                        }

                      is_in_subgraph[e] = true;
                      if (upper_face_vertex[source(e,g)] || 
                          lower_face_vertex[source(e,g)]
                          )
                        {
                          if (first_x_y_path_endpoint == 
                              graph_traits<Graph>::null_vertex()
                              )
                            first_x_y_path_endpoint = source(e,g);
                          else
                            second_x_y_path_endpoint = source(e,g);
                        }
                      if (upper_face_vertex[target(e,g)] || 
                          lower_face_vertex[target(e,g)]
                          )
                        {
                          if (first_x_y_path_endpoint == 
                              graph_traits<Graph>::null_vertex()
                              )
                            first_x_y_path_endpoint = target(e,g);
                          else
                            second_x_y_path_endpoint = target(e,g);
                        }


                    }
                  else if (previous_vertex == x || previous_vertex == y)
                    {
                      chosen_case = CASE_C;
                    }
              
                }

            }

          // Look for a case D - one of v's embedded edges will connect to the 
          // x-y path along an inner face path.

          //First, get a list of all of v's embedded child edges

          out_edge_iterator_t v_edge_itr, v_edge_end;
          for(tie(v_edge_itr,v_edge_end) = out_edges(v,g); 
              v_edge_itr != v_edge_end; ++v_edge_itr
              )
            {
              edge_t embedded_edge(*v_edge_itr);
             
              if (!is_embedded[embedded_edge] || 
                  embedded_edge == dfs_parent_edge[v]
                  )
                continue;

              case_d_edges.push_back(embedded_edge);

              vertex_t current_vertex 
                = source(embedded_edge,g) == v ? 
                target(embedded_edge,g) : source(embedded_edge,g);

              typename face_edge_iterator<>::type 
                internal_face_itr, internal_face_end;
              if (face_handles[current_vertex].first_vertex() == v)
                {
                  internal_face_itr = typename face_edge_iterator<>::type
                    (current_vertex, face_handles, second_side());
                }
              else
                {
                  internal_face_itr = typename face_edge_iterator<>::type
                    (current_vertex, face_handles, first_side());
                }

              while(internal_face_itr != internal_face_end &&
                    !outer_face_edge[*internal_face_itr] && 
                    !x_y_path_vertex[current_vertex]
                    )
                {
                  edge_t e(*internal_face_itr);
                  case_d_edges.push_back(e);
                  current_vertex = 
                    source(e,g) == current_vertex ? target(e,g) : source(e,g);
                  ++internal_face_itr;
                }

              if (x_y_path_vertex[current_vertex])
                {
                  chosen_case = CASE_D;
                  break;
                }
              else
                {
                  case_d_edges.clear();
                }

            }
          

        }




      if (chosen_case != CASE_B && chosen_case != CASE_A)
        {

          //Finding z and w.

          for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
            {
              edge_t e(*ei);
              goal_edge[e] = !outer_face_edge[e] && 
                (source(e,g) == z || target(e,g) == z);
              forbidden_edge[e] = outer_face_edge[e];
            }

          kuratowski_walkup(v,
                            forbidden_edge, 
                            goal_edge,
                            is_embedded,
                            z_v_path
                            );
              
          if (chosen_case == CASE_E)
            {

              for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
                {
                  forbidden_edge[*ei] = outer_face_edge[*ei];
                  goal_edge[*ei] = !outer_face_edge[*ei] && 
                    (source(*ei,g) == w || target(*ei,g) == w);
                }

              for(tie(oei, oei_end) = out_edges(w,g); oei != oei_end; ++oei)
                {
                  if (!outer_face_edge[*oei])
                    goal_edge[*oei] = true;
                }

              typename std::vector<edge_t>::iterator pi, pi_end;
              pi_end = z_v_path.end();
              for(pi = z_v_path.begin(); pi != pi_end; ++pi)
                {
                  goal_edge[*pi] = true;
                }
          
              w_ancestor = v;
              vertex_t w_endpoint = graph_traits<Graph>::null_vertex();
          
              while(w_endpoint == graph_traits<Graph>::null_vertex())
                { 
                  w_ancestor = dfs_parent[w_ancestor];
                  w_endpoint = kuratowski_walkup(w_ancestor, 
                                                 forbidden_edge, 
                                                 goal_edge,
                                                 is_embedded,
                                                 w_path
                                                 );
                  
                }            
 
            }


        }


      //We're done isolating the Kuratowski subgraph at this point -
      //but there's still some cleaning up to do.

      //Update is_in_subgraph with the paths we just found

      xi_end = x_external_path.end();
      for(xi = x_external_path.begin(); xi != xi_end; ++xi)
        is_in_subgraph[*xi] = true;

      xi_end = y_external_path.end();
      for(xi = y_external_path.begin(); xi != xi_end; ++xi)
        is_in_subgraph[*xi] = true;

      xi_end = z_v_path.end();
      for(xi = z_v_path.begin(); xi != xi_end; ++xi)
        is_in_subgraph[*xi] = true;

      xi_end = case_d_edges.end();
      for(xi = case_d_edges.begin(); xi != xi_end; ++xi)
        is_in_subgraph[*xi] = true;

      xi_end = w_path.end();
      for(xi = w_path.begin(); xi != xi_end; ++xi)
        is_in_subgraph[*xi] = true;
      
      child = bicomp_root;
      parent = dfs_parent[child];
      while(child != parent)
        {
          is_in_subgraph[dfs_parent_edge[child]] = true;
          tie(parent, child) = std::make_pair( dfs_parent[parent], parent );
        }




      // At this point, we've already isolated the Kuratowski subgraph and 
      // collected all of the edges that compose it in the is_in_subgraph 
      // property map. But we want the verification of such a subgraph to be 
      // a deterministic process, and we can simplify the function 
      // is_kuratowski_subgraph by cleaning up some edges here.

      if (chosen_case == CASE_B)
        {
          is_in_subgraph[dfs_parent_edge[v]] = false;
        }
      else if (chosen_case == CASE_C)
        {
          // In a case C subgraph, at least one of the x-y path endpoints
          // (call it alpha) is above either x or y on the outer face. The
          // other endpoint may be attached at x or y OR above OR below. In
          // any of these three cases, we can form a K_3_3 by removing the 
          // edge attached to v on the outer face that is NOT on the path to 
          // alpha.

          typename face_vertex_iterator<single_side, follow_visitor>::type 
            face_itr, face_end;
          if (face_handles[v_dfchild_handle.first_vertex()].first_edge() == 
              v_dfchild_handle.first_edge()
              )
            {
              face_itr = typename face_vertex_iterator
                <single_side, follow_visitor>::type
                (v_dfchild_handle.first_vertex(), face_handles, second_side());
            }
          else
            {
              face_itr = typename face_vertex_iterator
                <single_side, follow_visitor>::type
                (v_dfchild_handle.first_vertex(), face_handles, first_side());
            }

          for(; true; ++face_itr)
            {
              vertex_t current_vertex(*face_itr);
              if (current_vertex == x || current_vertex == y)
                {
                  is_in_subgraph[v_dfchild_handle.first_edge()] = false;
                  break;
                }
              else if (current_vertex == first_x_y_path_endpoint ||
                       current_vertex == second_x_y_path_endpoint)
                {
                  is_in_subgraph[v_dfchild_handle.second_edge()] = false;
                  break;
                }
            }
          
        }
      else if (chosen_case == CASE_D)
        {
          // Need to remove both of the edges adjacent to v on the outer face.
          // remove the connecting edges from v to bicomp, then
          // is_kuratowski_subgraph will shrink vertices of degree 1 
          // automatically...

          is_in_subgraph[v_dfchild_handle.first_edge()] = false;
          is_in_subgraph[v_dfchild_handle.second_edge()] = false;

        }
      else if (chosen_case == CASE_E)
        {
          // Similarly to case C, if the endpoints of the x-y path are both 
          // below x and y, we should remove an edge to allow the subgraph to 
          // contract to a K_3_3.


          if ((first_x_y_path_endpoint != x && first_x_y_path_endpoint != y) ||
              (second_x_y_path_endpoint != x && second_x_y_path_endpoint != y)
              )
            {
              is_in_subgraph[dfs_parent_edge[v]] = false;              

              vertex_t deletion_endpoint, other_endpoint;
              if (lower_face_vertex[first_x_y_path_endpoint])
                {
                  deletion_endpoint = second_x_y_path_endpoint;
                  other_endpoint = first_x_y_path_endpoint;
                }
              else
                {                
                  deletion_endpoint = first_x_y_path_endpoint;
                  other_endpoint = second_x_y_path_endpoint;
                }

              typename face_edge_iterator<>::type face_itr, face_end;
              
              bool found_other_endpoint = false;
              for(face_itr = typename face_edge_iterator<>::type
                    (deletion_endpoint, face_handles, first_side());
                  face_itr != face_end; ++face_itr
                  )
                {
                  edge_t e(*face_itr);
                  if (source(e,g) == other_endpoint || 
                      target(e,g) == other_endpoint
                      )
                    {
                      found_other_endpoint = true;
                      break;
                    }
                }

              if (found_other_endpoint)
                {
                  is_in_subgraph[face_handles[deletion_endpoint].first_edge()] 
                    = false;
                }
              else
                {
                  is_in_subgraph[face_handles[deletion_endpoint].second_edge()]
                    = false;
                }
            }
          
        }


      for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        if (is_in_subgraph[*ei])
          *o_itr = *ei;
      
    }



    template<typename EdgePermutation>
    void make_edge_permutation(EdgePermutation perm)
    {
      vertex_iterator_t vi, vi_end;
      for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
        {
          vertex_t v(*vi);
          perm[v].clear();
          face_handles[v].get_list(std::back_inserter(perm[v]));
        }
    }


  private:

    const Graph& g;
    VertexIndexMap vm;

    vertex_t kuratowski_v;
    vertex_t kuratowski_x;
    vertex_t kuratowski_y;
    
    vertex_list_t garbage; // we delete items from linked lists by 
                           // splicing them into garbage

    //only need these two for kuratowski subgraph isolation
    std::vector<vertex_t> current_merge_points;
    std::vector<edge_t> embedded_edges;
    
    //property map storage
    std::vector<v_size_t> low_point_vector;
    std::vector<vertex_t> dfs_parent_vector;
    std::vector<v_size_t> dfs_number_vector;
    std::vector<v_size_t> least_ancestor_vector;
    std::vector<face_handle_list_ptr_t> pertinent_roots_vector;
    std::vector<v_size_t> backedge_flag_vector;
    std::vector<v_size_t> visited_vector;
    std::vector< face_handle_t > face_handles_vector;
    std::vector< face_handle_t > dfs_child_handles_vector;
    std::vector< vertex_list_ptr_t > separated_dfs_child_list_vector;
    std::vector< typename vertex_list_t::iterator > 
        separated_node_in_parent_list_vector;
    std::vector<vertex_t> canonical_dfs_child_vector;
    std::vector<bool> flipped_vector;
    std::vector<edge_vector_t> backedges_vector;
    edge_vector_t self_loops;
    std::vector<edge_t> dfs_parent_edge_vector;
    vertex_vector_t vertices_by_dfs_num;

    //property maps
    vertex_to_v_size_map_t low_point;
    vertex_to_vertex_map_t dfs_parent;
    vertex_to_v_size_map_t dfs_number;
    vertex_to_v_size_map_t least_ancestor;
    vertex_to_face_handle_list_ptr_map_t pertinent_roots;
    vertex_to_v_size_map_t backedge_flag;
    vertex_to_v_size_map_t visited;
    vertex_to_face_handle_map_t face_handles;         
    vertex_to_face_handle_map_t dfs_child_handles;
    vertex_to_vertex_list_ptr_map_t separated_dfs_child_list;
    vertex_to_separated_node_map_t separated_node_in_parent_list;
    vertex_to_vertex_map_t canonical_dfs_child;      
    vertex_to_bool_map_t flipped;
    vertex_to_edge_vector_map_t backedges;
    vertex_to_edge_map_t dfs_parent_edge; //only need for kuratowski

    merge_stack_t merge_stack;
    
  };
  
      
} //namespace boost

#endif //__BOYER_MYRVOLD_IMPL_HPP__
boyer_myrvold_impl.hpp
Page URL
File URL
Prev 2/5 Next
Download ( 73 KB )
Leading Cloud Surveillance, recording and storage service. IP camera remote viewing, live streaming, broadcasting
Leading Enterprise Cloud IT Service. Cloud File Server, Drive Mapping, FTP Hosting, Online Storage
Note: The DriveHQ service banners will NOT be displayed if the file owner is a paid member.
Comments
Total ratings: 0 Average rating:
Not Rated
Would you like to comment?

Join DriveHQ for a free account, or Logon if you are already a member.