void extract_kuratowski_subgraph()

in extra/boost/boost_1_85_0/boost/graph/planar_detail/boyer_myrvold_impl.hpp [1021:1742]


    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 (boost::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 = graph_traits< Graph >::null_vertex();
        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;

        detail::bm_case_t chosen_case = detail::BM_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 (boost::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 (boost::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 = detail::BM_CASE_A;

            for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
                if (lower_face_vertex[*vi])
                    for (boost::tie(oei, oei_end) = out_edges(*vi, g);
                         oei != oei_end; ++oei)
                        if (!outer_face_edge[*oei])
                            goal_edge[*oei] = true;

            for (boost::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 = detail::BM_CASE_B;

            for (boost::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 (boost::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 = detail::BM_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[*boost::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 = detail::BM_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 (boost::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 = detail::BM_CASE_D;
                    break;
                }
                else
                {
                    case_d_edges.clear();
                }
            }
        }

        if (chosen_case != detail::BM_CASE_B
            && chosen_case != detail::BM_CASE_A)
        {

            // Finding z and w.

            for (boost::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 == detail::BM_CASE_E)
            {

                for (boost::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 (boost::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;
            boost::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 == detail::BM_CASE_B)
        {
            is_in_subgraph[dfs_parent_edge[v]] = false;
        }
        else if (chosen_case == detail::BM_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 == detail::BM_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 == detail::BM_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 (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
            if (is_in_subgraph[*ei])
                *o_itr = *ei;
    }