[Graph] Attempt to resolve open issue

From: Anne van de Graaf (A.vandeGraaf_at_[hidden])
Date: 2021-12-03 08:36:53

Hello all,

I am trying to get an open issue in Boost.Graph resolved. Since I haven't received any response at the corresponding GitHub page nor from the Boost Users mailing list (where I posted the below message last Monday), I am reaching out to you. My aim is to get in touch with the maintainer(s) of Boost.Graph in order to discuss what is the preferred/most efficient way to fix the issue. Since this is my first post to this mailing list, please accept my apologies if you feel this is not the right way to get in touch with the maintainers. In that case, I would appreciate it very much if you could kindly explain what I should have done instead. Please find below a copy of my message that I sent last Monday to the Boost Users mailing list. Thank you very much for your attention and any replies.

Original message:
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 <vector>
#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