Изменение веса графа в посетителе Discover_vertex - PullRequest
Новая
       21

Изменение веса графа в посетителе Discover_vertex

0 голосов
/ 04 февраля 2019

Можно ли изменить вес графика во время работы алгоритма (в данном случае dijkstra)?

В следующем коде я получаю ошибку компилятора:

'g': вы не можете присвоить переменной, которая является константой 

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

Без ссылки я работаю над копией графика, которая не является тем, что я хочу.Вместо этого я бы хотел изменить весовые коэффициенты непосредственно на графике.

Вот вызов алгоритма сокращения путей Дейкстры: 

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;

1 Ответ

0 голосов
/ 04 февраля 2019

Изменение веса опасно, в зависимости от алгоритма.Вы можете нарушить некоторые инварианты алгоритма, сделав поведение неопределенным (например, возможно, оно никогда не прекратится).

Но если вы знаете, что делаете, просто сохраните указатель на изменяемый граф впосетитель: 

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

...

И создайте его экземпляр по адресу: 

WeightVisitor sWeightVisitor { &g };
...