CODEWITHSUNDEEP
boostboost-graphvisitor-pattern
evolved
evolved

Reputation: 2210

Changing weights of graph in discover_vertex visitor

Is it possible to change the weights of a graph while an algorithm (dijkstra in this case) is running?

In the following code I get a compiler error:

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

Without the reference I am working on a copy of the graph which is not what I want. Instead I would like to change the weights on the graph directly.

Here is the call to Dijkstra shortes path algorithm:

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

For vertices and edges I use bundled properties:

struct tVertex
{
    int id;
};

struct tEdge
{
    double weight;
};

And the definition of the graph

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

Upvotes: 3

Views: 253

Answers (1)

sehe
sehe

Reputation: 393467

Changing the weight is dangerous, depending on the algorithm. You could violate some invariants of the algorithm, making the behaviour undefined (like, maybe it will never terminate).

But if you know what you're doing, just keep a pointer-to-mutable-graph in the visitor:

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

...

And instantiate it with the address:

WeightVisitor sWeightVisitor { &g };

Upvotes: 1

Related Questions