boost - 在 discover_vertex 访问者中改变图的权重

Question

是否可以在算法(在本例中为 dijkstra)运行时更改图的权重？

在下面的代码中我得到一个编译器错误:

'g' : you cannot assign to a variable that is const

struct WeightVisitor : public boost::default_dijkstra_visitor
{
    template <typename Vertex, typename Graph> void
        discover_vertex(Vertex v, Graph & g)
    {
        /// Get parent
        Vertex parentVertex = boost::in_edges(v, g).first->m_source;

        typedef typename boost::graph_traits< Graph >::edge_descriptor edge_t;
        edge_t edgeDescriptor;

        std::pair<edge_t, bool> ed = boost::edge(parentVertex, v, g);
        if (tTrue == ed.second)
        {
            edgeDescriptor = ed.first;

            //put(&EdgeValueType::weight, tree, edgeDescriptor, i_wtNewWeight);
            g[edgeDescriptor].weight = rand() % 100;
            std::cout << "TimeStamp: " << g[edgeDescriptor].weight << std::endl;
        }
        else
        {
            std::cout << "Warning: No edge between input vertices" << std::endl;
        }
    }
};

在没有引用的情况下，我正在处理图表的副本，这不是我想要的。相反，我想直接更改图表上的权重。

这里是对 Dijkstra 最短路径算法的调用:

boost::dijkstra_shortest_paths(g, root,
        boost::weight_map(boost::get(&tEdge::weight, g))
        .distance_map(boost::make_iterator_property_map(distances.begin(), boost::get(boost::vertex_index, g)))
        .predecessor_map(boost::make_iterator_property_map(predecessors.begin(), boost::get(boost::vertex_index, g)))
        .visitor(sWeightVisitor)
    );

对于顶点和边，我使用捆绑属性:

struct tVertex
{
    int id;
};

struct tEdge
{
    double weight;
};

以及图的定义

typedef boost::adjacency_list<
        boost::mapS,
        boost::vecS,
        boost::bidirectionalS,
        tVertex, tEdge>
        graph_t;

Answer 1

改变权重是危险的，这取决于算法。您可能会违反算法的某些不变量，使行为不确定(例如，它可能永远不会终止)。

但是如果您知道自己在做什么，只需在访问者中保留一个指向可变图的指针:

struct WeightVisitor : public boost::default_dijkstra_visitor
{
    graph_t* _graph;

...

并用地址实例化它:

WeightVisitor sWeightVisitor { &g };