[Graph] Occasional crash when removing a vertex

From: Anne van de Graaf (A.vandeGraaf_at_[hidden])
Date: 2021-11-29 12:43:54

Hello all,

When I remove a vertex from a graph, I occasionally experience a crash (on a system running Red Hat Enterprise Linux 8.5). I have been able to replicate the behavior with the following test program:

#include <boost/graph/adjacency_list.hpp>

int main()
{
    using MyGraph = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS>;
    using MyVertexDescriptor = boost::graph_traits<MyGraph>::vertex_descriptor;
    using MyVertexDescriptorVec = std::vector<MyVertexDescriptor>;

    MyGraph g;
    MyVertexDescriptorVec vertices{ boost::add_vertex( g ),
                                    boost::add_vertex( g ),
                                    boost::add_vertex( g ) };

    boost::add_edge( vertices[0], vertices[1], g );
    boost::add_edge( vertices[1], vertices[2], g );

    boost::clear_vertex( vertices[0], g );
    boost::remove_vertex( vertices[0], g );

    return 0;
}

Also on a Windows platform, I observe similar behavior. When I build the above code with Microsoft Visual Studio 2019 (MSVC 14.27.29110) and run it with a debugger, a debug assertion is triggered ("cannot increment value-initialized map/set iterator"). In both cases (on Linux and Windows platforms), the debugger reveals that the problem is at line 2071 of boost/graph/detail/adjacency_list.hpp. For clarity, I have copied the involved template function below:

template < class EdgeList, class vertex_descriptor >
inline void reindex_edge_list(
    EdgeList& el, vertex_descriptor u, boost::disallow_parallel_edge_tag)
{
    for (typename EdgeList::iterator ei = el.begin(); ei != el.end(); ++ei) // line 2071: increment operator fails
    {
        if (ei->get_target() > u)
        {
            typename EdgeList::value_type ce = *ei;
            el.erase(ce);
            --ce.get_target();
            el.insert(ce);
        }
    }
}

While I was searching for a proper place to post my question, I found the following issue at GitHub (which was opened on July 1 of this year): https://github.com/boostorg/graph/issues/268. This appears to be the exact same issue. So last week, I added a comment saying that I am facing the exact same problem. Unfortunately, so far no one has responded yet. To me, it seems that the problem is well-understood. Also, some have proposed a bug fix to resolve the issue (including a pull request). Nevertheless, no progress has been made over the past months. So I was just wondering what is the best way to proceed if we want to fix the issue in Boost itself? Is there anything that I can do (apart from starting this thread) to help in resolving the issue? Any feedback is greatly appreciated.

Kind regards,
Anne van de Graaf