Использование связанных свойств в качестве карты весов в dijkstra_shortest_paths

Возможно, это глупый вопрос, но я пытаюсь использовать dijkstra_shortest_paths BGL и, в частности, использовать поле моего связанного свойства Edge в качестве карты весов. Мои попытки в настоящее время привели к десяткам страниц ошибок компилятора, поэтому я надеюсь, что кто-то знает, как мне помочь. Вот как выглядит мой код:

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. В частности, я хотел бы знать, что нужно для повышения вуду, чтобы соответствовать такому вызову:

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?

таким образом, карта весов каким-то образом свяжет конкретное ребро моего графика с соответствующим полем length в свойстве. Я уверен, что есть простой способ сделать это, но документация по BGL для меня невероятно непрозрачна. Если подскажете, где в документации описан пример, тоже буду очень рад.

Заранее спасибо!


c++ boost-graph
person Carlos Scheidegger    schedule 20.08.2010    source источник

Ответы (3)


arrow_upward
11
arrow_downward

Если кого-то это волнует, похоже, сработала версия вызова с именованным параметром, а именно:

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

Это есть в документации, здесь. Однако я до сих пор не знаю, как использовать версию вызова с «неименованным параметром».

person Carlos Scheidegger    schedule 20.08.2010

arrow_upward
6
arrow_downward

Хорошо, я просто потратил слишком много времени на эту проблему. Вот решение для потомков:

/**
 * @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) );
person user1661473    schedule 11.09.2012

arrow_upward
6
arrow_downward

Каким бы мощным ни был BGL, к сожалению, по моему честному мнению, его не очень легко использовать. Чтобы заставить это работать, потребовалось немало проб и ошибок, но вот рабочая версия, скомпилированная с помощью Boost 1.53.0 [мы хотим использовать алгоритм Дейкстры для переменной 'rate' в __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>()) );

    ...
}

Я искренне надеюсь, что это поможет! Моя попытка здесь состояла в том, чтобы показать, как получить доступ ко всем основным «функциям», доступным для алгоритма.

person user2587407    schedule 16.07.2013