Я использую Boost Graph Library для хранения неориентированного графа с double
граничные веса и double
веса вершин. В нескольких местах моего кода мне нужно применить алгоритм Дейкстры для поиска кратчайших путей. Это работало довольно хорошо, пока я не решил, что хочу временно переопределить сохраненные веса ребер своими собственными весами (только временно, веса графиков не должны изменяться). Мой код в основном выглядит так:
// Initial typedefs
typedef boost::property<boost::edge_weight_t, double> edge_weight_t;
typedef boost::property<boost::vertex_discover_time_t, double> vertex_weight_t;
typedef boost::adjacency_list<boost::vecS,
boost::vecS,
boost::undirectedS,
vertex_weight_t,
edge_weight_t> graph_t;
// In a function, where graph is a const reference of type graph_t
std::vector<double> pathLengths( boost::num_vertices( graph ) );
boost::property_map<graph_t, boost::edge_weight_t>::type weightMap;
boost::graph_traits<graph_t>::edge_iterator e_it, e_it_end;
for( boost::tie( e_it, e_it_end ) = boost::edges( graph );
e_it != e_it_end;
++e_it )
{
weightMap[ *e_it ] = 1.0;
}
boost::dijkstra_shortest_paths( graph,
boost::vertex( vertex, graph ),
boost::distance_map( &pathLengths[0] ).weight_map( weightMap ) );
Хотя graph
это постоянная ссылка в приведенном выше коде вес ребра графа будет изменено после этого. Что я делаю неправильно? Или, более конкретно, как я могу временно переопределить веса ребер в взвешенном графике?
Очевидно, я мог бы просто сохранить текущие веса ребер, заменить их моими весами и затем изменить их обратно. Тем не менее, я убежден, что я Я виноват, и я не хочу игнорировать эту проблему.
Я считаю, что у меня была та же проблема — я хотел временно (для конкретного запуска алгоритма поиска) изменить вес ребер, не изменяя сам график постоянно. После некоторых поисков я нашел это, что позволяет зарегистрировать функтор, который используется для генерации весов. Это используется в качестве параметра weight_map:
http://www.boost.org/doc/libs/1_51_0/boost/property_map/function_property_map.hpp
Других решений пока нет …