boyer_myrvold_impl.hpp

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

              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_