Используя комплексные свойства в качестве весовой карты в Dijkstra_shortest_paths
-
29-09-2019 - |
Вопрос
Возможно, это глупый вопрос, но я пытаюсь использовать BGL dijkstra_shortest_paths
, и, в частности, использовать поле моего края комплексного свойства в качестве весовой карты. Мои попытки в настоящее время привели к десяткам страниц ошибок компилятора, поэтому я надеюсь, что кто -то знает, как мне помочь. По сути, это мой код:
struct GraphEdge {
float length;
// other cruft
};
struct GraphVertex {
...
};
typedef boost::adjacency_list
<boost::vecS, boost::vecS, boost::directedS,
GraphVertex, GraphEdge> GraphType;
Я могу заполнить график без каких -либо проблем, однако, когда дело доходит до звонка dijkstra_shortest_paths
, У меня проблемы. Я хотел бы использовать length
поле. В частности, я хотел бы знать, что такое необходимое для Boost Voodoo, чтобы подходить к такому вызову:
GraphType m_graph;
vector<int> predecessor(num_vertices(m_graph));
vector<float> distances(num_vertices(m_graph), 0.0f);
vector<int> vertex_index_map(num_vertices(m_graph));
for (size_t i=0; i<vertex_index_map.size(); ++i) {
vertex_index_map[i] = i;
}
dijkstra_shortest_paths(m_graph, vertex_from, predecessor, distances,
weightmap, vertex_index_map,
std::less<float>(), closed_plus<float>(),
(std::numeric_limits<float>::max)(), 0.0f,
default_dijkstra_visitor());
// How do I write the right version of weightmap here?
Такова, что WeightMap каким -то образом связывает определенный край моего графика с соответствующим length
Поле в собственности. Я уверен, что есть простой способ сделать это, но документация для BGL для меня невероятно непрозрачна. Если вы можете сказать мне, где в документации описан пример, я также был бы очень счастлив.
Заранее спасибо!
Решение
В случае, если кто -то заботится об этом, использование именованной версии вызова, похоже, сработала следующим образом:
dijkstra_shortest_paths(m_graph, vertex_from,
weight_map(get(&TrafficGraphEdge::length, m_graph))
.distance_map(make_iterator_property_map(distances.begin(),
get(vertex_index, m_graph))));
Это в документации, здесь. Анкет Однако я до сих пор не знаю, как использовать версию «Параметр без названия».
Другие советы
Хорошо, я просто потратил слишком много времени на эту проблему. Вот решение для потомства:
/**
* @brief Example concerning bundled properties.
* @author Pierre-Andre Noel
* @date September 10 2012
*/
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
/// The type of the field we are interested in.
typedef int interesting_type;
/// The struct whose elements will be bundled in each vertex.
struct bundled_in_vertex_type
{
/// Something interesting.
interesting_type something;
};
int main()
{
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, bundled_in_vertex_type > graph_type;
typedef graph_type::vertex_descriptor vertex_descriptor_type;
/// Create a graph of two vertices.
graph_type g(2);
/// Name the two nodes.
const vertex_descriptor_type v1(*boost::vertices(g).first), v2(*(++boost::vertices(g).first));
// Store some stuff in the two nodes, the "easy" way.
g[v1].something = interesting_type(42);
g[v2].something = interesting_type(999);
// Now what you came here for.
/// An handle providing direct access to the field "something".
boost::property_map< graph_type, interesting_type bundled_in_vertex_type::* >::type handle_to_something( boost::get(&bundled_in_vertex_type::something, g) );
// You can now use "handle_to_something" for whatever deed you are interested in.
// Just checking that it works.
std::cout << "Vertex v1's ""something"" field is: " << handle_to_something[v1] << std::endl;
std::cout << "Vertex v2's ""something"" field is: " << handle_to_something[v2] << std::endl;
// Thank you and have a nice day.
return 0;
}
Серьезно, эта библиотека великолепна, но документация окончательно не хватает. Это должно быть тривиальным вопросом.
РЕДАКТИРОВАТЬ
Если вы используете C ++ 11, то вы можете предпочесть следующую альтернативу.
auto handle_to_something( boost::get(&bundled_in_vertex_type::something, g) );
К сожалению, каким бы мощным BGL он не очень легко использовать в моем честном мнении. Получение этого потребовало некоторую значительную пробную версию и ошибку, но вот рабочая версия, составленная с Boost 1.53.0 [мы хотим использовать алгоритм Dijkstra на переменной «скорости» в __edge_data]:
struct __edge_data
{
double rate;
double edge_thickness;
size_t colour;
};
struct __vertex_data
{
size_t colour;
size_t shape_code;
string name;
};
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, __vertex_data, __edge_data> DIgraph;
typedef boost::graph_traits<DIgraph>::vertex_descriptor vertexx;
typedef boost::graph_traits<DIgraph>::vertex_iterator vertexx_iter;
typedef boost::graph_traits<DIgraph>::edge_descriptor edgee;
// functor
template<typename T>
struct combine_min : public std::binary_function<T, T, T>
{
T const operator()(const T& a, const T& b) const
{
return b < a ? (b) : (a);
}
};
// functor
template<typename T>
struct compare_less_than : public std::binary_function<T, T, bool>
{
bool const operator()(const T& a, const T& b) const
{
return a < b;
}
};
void graph_analysis()
{
...
std::vector<vertexx> parents(num_vertices(G));
std::vector<double> distances(num_vertices(G));
auto p_map = boost::make_iterator_property_map(&parents[0], boost::get(boost::vertex_index, G));
auto d_map = boost::make_iterator_property_map(&distances[0], boost::get(boost::vertex_index, G));
auto w_map = boost::get(&__edge_data::rate_rate, G); // <=== THIS IS THE TRICK!!!
auto n_map = boost::get(&__vertex_data::name, G);
boost::dijkstra_shortest_paths(G, start_vertex_vector,
boost::weight_map(w_map).
predecessor_map(p_map).
distance_map(d_map).
distance_combine(combine_min<double>()).
distance_compare(compare_less_than<double>()) );
...
}
Я искренне надеюсь, что это поможет! Моя попытка заключалась в том, чтобы показать, как получить доступ ко всем основным «функциям», доступным для алгоритма.