Demonstration of Boost O(1) remove_edge() in class derived from "edge_index_update_visitor"

o1_edge_visitor.cpp

//=======================================================================
// Copyright 2024
// Author: Hermann Stamm-Wilbrandt
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <iostream>
#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/planar_detail/add_edge_visitors.hpp>

using namespace boost;

template < typename EdgeIndexMap, typename Graph > struct o1_edge_visitor
    : edge_index_update_visitor< EdgeIndexMap >
{
    typedef
        typename property_traits< EdgeIndexMap >::value_type edge_index_value_t;
    typedef
        typename graph_traits< Graph >::out_edge_iterator out_edge_iterator;
    typedef
        typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
    typedef
        typename graph_traits< Graph >::edge_descriptor edge_descriptor;
    typedef
        edge_index_update_visitor< EdgeIndexMap > edge_index_update_visitor_t;

    o1_edge_visitor(
        EdgeIndexMap em, edge_index_value_t next_index_available, Graph)
    : edge_index_update_visitor_t::edge_index_update_visitor(
        em, next_index_available),
      m_em(em)
    {
    }

    explicit o1_edge_visitor(Graph g)
    : o1_edge_visitor(get(edge_index, g), num_edges(g), g)
    {
    }

    void visit_vertex_pair(vertex_descriptor u, vertex_descriptor v, Graph& g)
    {
        edge_index_update_visitor_t::visit_vertex_pair(u, v, g);

        storage.push_back(
            std::make_pair(
                --(out_edges(u, g).second),     // std::prev() hangs
                --(out_edges(v, g).second)));
    }

    // O(1)
    void visit_edge(edge_descriptor e, Graph& g)
    {
        auto it_to_front = [](out_edge_iterator it, Graph& g)
        {
            auto &L = g.impl().out_edge_list(it.m_src);
            L.splice(L.begin(), L, it.base());
        };

        it_to_front(storage[m_em[e]].first, g);
        it_to_front(storage[m_em[e]].second, g);
        boost::remove_edge(e, g);
    }

 private:
    EdgeIndexMap m_em;
    std::vector< std::pair< out_edge_iterator, out_edge_iterator > > storage;
};

int main(int, char*[]) {
    typedef undirected_graph<> ugraph;
    typedef ugraph::vertex_descriptor vertex_descriptor;
    typedef ugraph::edge_descriptor edge_descriptor;
    typedef boost::property_map< ugraph, boost::edge_index_t >::type
        EdgeIndexMap;

    int n = 5;
    ugraph U;
    o1_edge_visitor< EdgeIndexMap, ugraph > vis(U);
    std::vector< vertex_descriptor > V(n);

    for (int i = 0; i < n; ++i)  { V[i] = add_vertex(U); }
    std::cout << num_vertices(U) << std::endl;

    vis.visit_vertex_pair(V[0], V[1], U);
    vis.visit_vertex_pair(V[1], V[2], U);
    vis.visit_vertex_pair(V[2], V[3], U);
    vis.visit_vertex_pair(V[3], V[0], U);
    vis.visit_vertex_pair(V[0], V[2], U);

    print_graph(U);
    std::cout << num_edges(U) << std::endl;

    edge_descriptor e = *(--edges(U).second);
    vis.visit_edge(e, U);

    print_graph(U);
    std::cout << num_edges(U) << std::endl;

    return 0;
}

For discussion in this pull request comment:
boostorg/graph#387 (comment)