将 listS 用于顶点和边列表时无法调用 boost::clear_vertex

Question

我正在编写一个程序，该程序使用 boost 图形库来解决旅行商问题，使用具有最小生成树启发式的 A* 搜索。我对 boost::graph 比较陌生在我的启发式 class 中，我计算了所有尚未访问的顶点的最小生成树。我通过维护一个来跟踪访问了哪些顶点每次调用启发式时，我都会从中删除当前顶点及其所有边的原始图的副本。但是，当我去调用 boost::clear_vertex(u, subGraph) 其中 u 是 vertex_descriptor 并且 subGraph 是我从中减去顶点的原始图的副本时，我得到一个调试断言失败说明：

list erase iterator outside range.

经过一些调试后，我发现最终错误出现在 STL <list> 的第 1383 行，由于某种原因，以下条件为假：

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

这是我的启发式 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;
};

以下是一些相关的类型定义：

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

我真的很感激有人为我澄清为什么会这样。另外，我的启发式 class 的想法可能是完全愚蠢的，所以如果你认为我应该尝试一些其他的方法来获得最小生成树启发式而不是继续搞乱这个，我当然愿意展望。如果我的启发式是愚蠢的，我真的很感激一些关于还能做什么的建议。我的升级版本是 boost_1_67_0，我使用的是 MS Visual Studio 2017.

Answer 1

您运行进入了 MSVC 的迭代器调试检查。这很好，否则你可能不知道它并且你的程序会有（沉默？）Undefined Behaviour.

现在让我看一下代码。

这看起来很可疑：

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

这带有隐含的假设，即 u 至少有一个出边。这可能是真的，但你真的应该检查一下。

进一步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.

也许初始化该颜色图是个好主意。我不知道这是否适用于您的代码，因为您没有包含相关代码 ()。

所以我改变了：

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

不，还是一样的错误。现在通读代码。

... 20 分钟后。啊哈。您正在将图表复制到 subGraph。但是，您还传递了一个参数 u。这怎么可能是正确的？顶点 u 很可能 而不是 来自 subGraph。这可能是另一个错误来源。

让我们也解决这个问题：

msth(msth.vertex(2));

有了新成员访问器：

vertex_descriptor vertex(std::size_t n) const {
    return boost::vertex(n, 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

很明显，您在图外有一个顶点 u。与 "destabilizing" 无关（这不是它的工作方式。迭代器有时会失效，但不会因此变得不稳定：如果不小心，您可能会调用未定义的行为）。

至少，在传递有效 u 时，UbSan 和 ASan 不会在这里抱怨，这是一个好兆头。很可能您的编译器的调试迭代器也不会抱怨。

现在，请注意：

listS 不会 而不是 使 remove 上的任何其他迭代器无效（这也在 Iterator invalidation rules 中）。很明显，只是删除了那个。
m_goal 遇到与 u 相同的问题：它很难来自正确的图表，因为您正在复制整个图表
即使 remove 仅使该特定顶点描述符无效，您似乎正试图在 A* 搜索的回调中执行此操作。这可能会破坏该算法假定的不变量（我没有检查文档，但你应该检查！同样，这是因为你没有显示 A* 相关代码）。
关于 Weight 是否是 double，您的代码似乎仍然存在问题。（为什么是static_cast？）

最终结果

这是我最后得到的，包括各种清理。

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));
}

版画

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

将 listS 用于顶点和边列表时无法调用 boost::clear_vertex

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

c++

boost

a-star

boost-graph

最终结果