boyer_myrvold_impl.hpp

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

          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);