Unable to call boost::clear_vertex while using listS for the vertex and edge lists

Question

I am writing a program which uses the boost graph library to solve the Travelling Salesman problem using A* search with a minimum spanning tree heuristic. I am rather new to boost::graph In my heuristic class, I calculate the minimum spanning tree of all the vertices yet unvisited. I keep track of which vertices have been visited by maintaining a copy of the original graph from which I remove the current vertex and all its edges on each call to the heuristic. However, when I go to call boost::clear_vertex(u, subGraph) where u is a vertex_descriptor and subGraph is the copy of the original graph from which I am subtracting vertices, I get a debug assertion failure stating:

list erase iterator outside range.

After doing some debugging, I found that ultimately the error is generated on line 1383 of STL <list> where for some reason the following condition is false:

_Where._Getcont() != _STD addressof(this->_Get_data()).

Here is my Heuristic class:

class MST_Heuristic : public astar_heuristic<MyGraphType, double>
{
public:
    MST_Heuristic(vertex_descriptor goal, MyGraphType g)
        : m_goal(goal), subGraph(g), firstRun(true) {}
    double operator () (vertex_descriptor u)
    {
        double MSTDist = 0.0;
        double startDist = numeric_limits<double>::infinity();
        int minEdgeWeight = subGraph[*out_edges(u, subGraph).first].weight;         // initialize minEdgeWeight to weight of first out edge

        if (firstRun)
        {
            IndexMap mapIndex;
            associative_property_map<IndexMap> vertexIndices(mapIndex);
            int j = 0;
            for (auto v = vertices(subGraph).first; v != vertices(subGraph).second; v++)
            {
                put(vertexIndices, *v, j++);
            }

            dijkstra_shortest_paths(subGraph, u, get(&VertexData::pred, subGraph),  // calculate the shortest path from the start for each vertex
                get(&VertexData::dist2, subGraph), get(&EdgeData::weight, subGraph),
                vertexIndices, less<double>(), plus<double>(),
                numeric_limits<double>::infinity(), 0, do_nothing_dijkstra_visitor(),
                get(&VertexData::color, subGraph));
        }
        for (auto ed : make_iterator_range(out_edges(u, subGraph)))
        {
            minEdgeWeight = min(subGraph[ed].weight, minEdgeWeight);                // find distance from nearest unvisited vertex to the current vertex
        }
        clear_vertex(u, subGraph);
        remove_vertex(u, subGraph);
        // Problem here; The problem has to do with removing vertices/edges and destabilizing the graph, thereby making it impossible to iterate through the graph

        IndexMap mapIndex;
        associative_property_map<IndexMap> vertexIndices(mapIndex);
        int j = 0;
        for (auto v = vertices(subGraph).first; v != vertices(subGraph).second; v++)
        {
            put(vertexIndices, *v, j++);
        }

        prim_minimum_spanning_tree(subGraph, *vertices(subGraph).first,             // calculate the minimum spanning tree
            get(&VertexData::pred, subGraph), get(&VertexData::dist, subGraph),
            get(&EdgeData::weight, subGraph), vertexIndices,
            do_nothing_dijkstra_visitor());

        for (auto vd : make_iterator_range(vertices(subGraph)))                     // estimate distance to travel all the unvisited vertices
        {
            MSTDist += subGraph[vd].dist;
            startDist = min(startDist, subGraph[vd].dist2);
        }

        firstRun = false;
        return static_cast<double>(minEdgeWeight) + MSTDist + startDist;            // return the result of the heuristic function
    }
private:
    vertex_descriptor m_goal;
    MyGraphType subGraph;
    bool firstRun;
};

Here are some relevant typedefs:

typedef adjacency_list_traits<listS, listS, undirectedS> GraphTraits;               // to simplify the next definition

typedef GraphTraits::vertex_descriptor vertex_descriptor;                           // vertex descriptor for the graph

typedef GraphTraits::edge_descriptor edge_descriptor;                               // edge descriptor for the graph

typedef std::map<vertex_descriptor, size_t>IndexMap;                                // type used for the vertex index property map

typedef adjacency_list<listS, listS, undirectedS,VertexData, EdgeData> MyGraphType; // graph type

I would really appreciate someone clearing up for me why this is happening. Also, it could be that my idea for a heuristic class is totally stupid, so if you think I should just try some other approach for a Minimum Spanning Tree heuristic rather than keep messing with this, I am certainly open to the prospect. If my heuristic is idiotic, I would really appreciate some suggestion as to what else to do. My boost version is boost_1_67_0 and I am using MS Visual Studio 2017.

Answer 1

You're running into iterator debugging checks from MSVC. That's GOOD because otherwise you might not know about it and your program would have (silent?) Undefined Behaviour.

Now let me look at the code.

This looks suspect:

double minEdgeWeight =
    subGraph[*out_edges(u, subGraph).first].weight; // initialize minEdgeWeight to weight of first out edge

This carries the implicit assumption that u has at least one outgoing edge. this may be true but you should really check it.

Further inspection with UbSan:

/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:82:30: runtime error: load of value 3200171710, which is not a valid value for type 'boost::default_color_type'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:82:30 in 
/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:83:13: runtime error: load of value 3200171710, which is not a valid value for type 'ColorValue' (aka 'boost::default_color_type')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:83:13 in 
/home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:87:15: runtime error: load of value 3200171710, which is not a valid value for type 'ColorValue' (aka 'boost::default_color_type')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sehe/custom/boost_1_67_0/boost/graph/breadth_first_search.hpp:87:15 in 
sotest: /home/sehe/custom/boost_1_67_0/boost/graph/two_bit_color_map.hpp:86: void boost::put(const two_bit_color_map<IndexMap> &, typename property_traits<IndexMap>::key_type, boost::two_bit_color_type) [IndexMap = boost::associative_property_map<std::map<void *, unsigned long, std::less<void *>, std::allocator<std::pair<void *const, unsigned long> > > >]: Assertion `(std::size_t)i < pm.n' failed.

Maybe it's a good idea to initialize that color map. I have no clue whether this applies to your code because you didn't include the relevant code (again).

So I change that:

struct VertexData {
    vertex_descriptor pred;
    double dist = 0, dist2 = 0;
    boost::default_color_type color = {};
};

Nope, still same error. Reading through the code now.

... 20 minutes later. Aha. You'r copying the graph into subGraph. However, you're also passing in a parameter u. How could that be correct? The vertex u will, most likely not be from subGraph. This is probably another source of error.

Let's fix this too:

msth(msth.vertex(2));

With a new member accessor:

vertex_descriptor vertex(std::size_t n) const {
    return boost::vertex(n, subGraph);
}

Reaching your comment

    // Problem here; The problem has to do with removing vertices/edges and destabilizing the graph, thereby making
    // it impossible to iterate through the graph

It becomes pretty obvious that you had a vertex u from outside the graph. Nothing about "destabilizing" (that's not how it works. Iterators get invalidated sometimes, but nothing becomes unstable because of it: you might just invoke undefined behaviour if you're not careful).

At least, when passing a valid u UbSan and ASan aren't complaining here, which is a good sign. Most likely your compiler's Debug Iterators won't be complaining either.

Now, take note:

• listS does not invalidate any other iterators on remove (that's also in Iterator invalidation rules). Only, obviously, the one removed.

• m_goal suffers from the same problem as u: it can hardly be from the right graph since you're copying the whole graph

• Even though remove only invalidates that particular vertex descriptor, it seems you are trying to do this inside a callback for A* search. That might well break the invariants assumed by that algorithm (I haven't checked the documentation, but you should! Again, this is because you don't show the A* related code).

• Your code still seems torn on whether Weight is, or is not, a double. (Why the static_cast?)

---

End Result

This is what I got in the end, various cleanups included.

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iomanip>
#include <numeric>

typedef boost::adjacency_list_traits<boost::listS, boost::listS, boost::undirectedS>
    GraphTraits;                                          // to simplify the next definition
typedef GraphTraits::vertex_descriptor vertex_descriptor; // vertex descriptor for the graph
typedef GraphTraits::edge_descriptor edge_descriptor;     // edge descriptor for the graph
typedef double Weight;

struct VertexData {
    std::string name;
    VertexData(std::string name = "") : name(std::move(name)) {}
    //
    vertex_descriptor pred {};
    Weight dist = 0, dist2 = 0;
    boost::default_color_type color = {};

    friend std::ostream& operator<<(std::ostream &os, VertexData const &vd) {
        return os << "{name:" << std::quoted(vd.name) << "}";
    }
};

struct EdgeData {
    Weight weight = 1;
};

typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, VertexData, EdgeData>
    MyGraphType; // graph type

class MST_Heuristic : public boost::astar_heuristic<MyGraphType, Weight> {
    struct do_nothing_dijkstra_visitor : boost::default_dijkstra_visitor {};

    auto make_index() const {
        std::map<vertex_descriptor, size_t> m;
        size_t n=0;
        for (auto vd : boost::make_iterator_range(vertices(subGraph)))
            m[vd] = n++;
        return m;
    }
  public:
    MST_Heuristic(MyGraphType g) : subGraph(g), firstRun(true) {}

    Weight operator()(vertex_descriptor u) {

        if (firstRun) {
            auto idx = make_index();
            dijkstra_shortest_paths(
                subGraph, u,
                get(&VertexData::pred, subGraph), // calculate the shortest path from the start for each vertex
                get(&VertexData::dist2, subGraph),
                get(&EdgeData::weight, subGraph),
                boost::make_assoc_property_map(idx), std::less<Weight>(),
                std::plus<Weight>(), std::numeric_limits<Weight>::infinity(), 0, do_nothing_dijkstra_visitor(),
                get(&VertexData::color, subGraph));
        }

        Weight minEdgeWeight = std::numeric_limits<Weight>::max(); // initialize minEdgeWeight to weight of first out edge
        for (auto ed : make_iterator_range(out_edges(u, subGraph))) {
            minEdgeWeight = std::min(subGraph[ed].weight, minEdgeWeight); // find distance from nearest unvisited vertex to the current vertex
        }

        clear_vertex(u, subGraph);
        remove_vertex(u, subGraph);

        {
            auto idx = make_index();
            prim_minimum_spanning_tree(subGraph, vertex(0), // calculate the minimum spanning tree
                                       get(&VertexData::pred, subGraph), get(&VertexData::dist, subGraph),
                                       get(&EdgeData::weight, subGraph), boost::make_assoc_property_map(idx),
                                       do_nothing_dijkstra_visitor());
        }

        //// combine
        Weight MSTDist = 0.0;
        Weight startDist = std::numeric_limits<Weight>::infinity();

        for (auto vd : boost::make_iterator_range(vertices(subGraph))) // estimate distance to travel all the unvisited vertices
        {
            MSTDist += subGraph[vd].dist;
            startDist = std::min(startDist, subGraph[vd].dist2);
        }

        firstRun = false;
        return minEdgeWeight + MSTDist + startDist; // return the result of the heuristic function
    }

    vertex_descriptor vertex(std::size_t n) const {
        return boost::vertex(n, subGraph);
    }

  private:

    MyGraphType subGraph;
    bool firstRun;
};

int main() {
    MyGraphType g;

    auto v1 = add_vertex({"one"}, g);
    auto v2 = add_vertex({"two"}, g);
    auto v3 = add_vertex({"three"}, g);
    auto v4 = add_vertex({"four"}, g);
    auto v5 = add_vertex({"five"}, g);

    add_edge(v1, v2, g);
    add_edge(v2, v3, g);
    add_edge(v3, v4, g);
    add_edge(v4, v5, g);

    print_graph(g, get(&VertexData::name, g));

    MST_Heuristic msth(g);
    msth(msth.vertex(2));
}

Prints

one <--> two 
two <--> one three 
three <--> two four 
four <--> three five 
five <--> four