boyer_myrvold_impl.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

                  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