更改 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 };

更改 discover_vertex 访问者中图表的权重

Changing weights of graph in discover_vertex visitor

boost

boost-graph

visitor-pattern