Why edge properties can't be changed within visitor in BGL?

Question

I want to change edge weight when examine an edge, but it tells

error: assignment of member ‘EdgeProperty::weight’ in read-only object g[e].weight = 1/g[e].residual_capacity;

If there is a way to change edge properties within a function of a custom visitor? Thanks.

struct EdgeProperty{
float weight;
float capacity;
float residual_capacity;
};
class custom_dijkstra_visitor : public boost::default_dijkstra_visitor
{
public:
    template < typename Edge, typename Graph >
    void examine_edge(Edge e, Graph const & g)
    {
        g[e].weight = 1/g[e].residual_capacity;
    }
};

`examine_edge()` takes `g` as a `const` reference parameter, so I would be surprised if any assignment statement with `g` on the LHS would compile. Try changing it to a non-const reference parameter. — j_random_hacker, Jan 17 '18 at 15:06

score 2 · Accepted Answer · answered Jan 17 '18 at 16:08

2

Finally I solved it by storing a Graph pointer in the visitor.

Note though that presumably you pass the visitor to an algorithm. That algorithm has its own invariants. If you change the weights, e.g. dijkstra_shortest_paths may not terminate at all, or yield incorrect (suboptimal) results.

If you want to change the weight according to the results of a previous algorithm and the algorithm uses (depends on) the weights, the safest course of action would be to store the "updated" weights in a separate map, and appy the changes afterwards.

answered Jan 17 '18 at 16:08

sehe

374,641
47
450
633

Your idea is reasonable, but it needs to run `dijkstra_shortest_paths()` two times. Other properties e.g `residual_capacity` can't be changed either while they do not affect `dijkstra_shortest_paths()` at all. – 井上由一 Jan 18 '18 at 01:44
That's not true is it, you can change whatever you want outside the parameter passed to the visitor, as you pointed out (and I responded to that). It's just a cautionary note. If you know what you're doing (i.e. read the actual algorithm pseudo code in the docs) you're free to do whatever convenes you. That's the spirit of C++. No barriers. – sehe Jan 18 '18 at 02:22
In my answer I specifically talk about data "the algorithm _uses_ (depends on)". So not about `residual_capacity`. There may be many ways in which it is safe to change weights (e.g. before first use, or only increasing in weight, from what I remember the algorithm doing). – sehe Jan 18 '18 at 02:23
Finally, you don't need to run the algorithm twice, since in such a weird situation you apparently don't want the algorithm to run, but you just want to update weights. That doesn't need to be done in the algorithm. – sehe Jan 18 '18 at 02:25
1

Now, ***summarizing*** are you simply saying your weight is a function and it is too expensive to calculate ahead of time for any nodes (that might not be visited)? Because in that case, why not **ask** that, because the answer is `make_transform_value_property_map` (see e.g. [Weight map as a function in Boost Graph](https://stackoverflow.com/questions/33103659/weight-map-as-function-in-boost-graph-dijkstra-algorithm/33104513#33104513) and [many others](https://stackoverflow.com/search?q=user%3A85371+make_transform_value_property_map)) – sehe Jan 18 '18 at 02:28
1

Yes, you are right, my `weight` is a function. **Weight map as a function in Boost Graph** is exactly what I want. Thank you. – 井上由一 Jan 18 '18 at 07:48
@井上由一 Cheers and welcome to StackOverflow. Please consider [upvoting helpful answers](https://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work) :) – sehe Jan 18 '18 at 08:20

score 1 · Answer 2 · answered Jan 17 '18 at 15:56

Finally I solved it by storing a Graph pointer in the visitor.

class custom_dijkstra_visitor : public boost::default_dijkstra_visitor
{
public:
    template < typename Edge, typename Graph >
    void examine_edge(Edge e, Graph & g)
    {
        (*gg)[e].weight = 1/(*gg)[e].residual_capacity;
    }
    Graph* gg = nullptr;
};

Why edge properties can't be changed within visitor in BGL?

2 Answers2