boyer_myrvold_impl.hpp

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

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