Найти все достижимые вершины в графе Boost BGL, используя BFS - PullRequest
Новая
       41

Найти все достижимые вершины в графе Boost BGL, используя BFS

0 голосов
/ 20 декабря 2018

Я построил график ускоренного BGL: 

using vertex_t = std::variant<node_t, specialNode_t>; // structs
using edge_t = std::variant<TerminalType>;            // enum

using Graph_t = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    vertex_t,
    edge_t>;

Graph_t myGraph;

, и я пытаюсь найти (собрать) все вершины, доступные из определенной начальной точки (вершины), отсортированные по их расстоянию.Это означает, что я хотел бы создать список всех вершин, достижимых из определенной начальной вершины, где «более близкие» вершины хранятся ранее в списке / векторе.Поэтому мне (кажется, мне) нужна BFS.

К сожалению, я не смог выяснить, как это сделать без ошибки компиляции: 

boost::queue<vertex_t> Q;
boost::default_bfs_visitor vis; // Will do my collecting visitor later...

auto indexmap = boost::get(boost::vertex_index, myGraph);
auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);

boost::breadth_first_visit(myGraph, start, std::ref(Q), vis, colormap);

это приводит к следующим ошибкам: 

Error   C2039   'push': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
Error   C2039   'empty': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
Error   C2039   'top': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
Error   C2039   'pop': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'
Error   C2039   'push': is not a member of 'std::reference_wrapper<boost::queue<ListSim::vertex_t,std::deque<_Tp,std::allocator<_Ty>>>>'

Мои вопросы:

  1. Может кто-нибудь пролить свет на мою ошибку?Или, может быть, указатель на пример?
  2. Возможно, есть лучший (с точки зрения эффективности) или иной подход к достижению этой цели?

(хотя я об использовании «connected_components»)сначала ... но он использует DFS, которая не может соответствовать критериям расстояния / сортировки, которые у меня есть).

1 Ответ

0 голосов
/ 20 декабря 2018

В документах говорится, что буфер должен быть очередью vertex_descriptors.Вы случайно объявили, что он имеет vertex_t (комплект свойств вершины) в качестве типа значения.

Исправьте это: 

using vertex_descriptor = boost::graph_traits<Graph_t>::vertex_descriptor;

boost::queue<vertex_descriptor> Q;

И он компилируется:

Live On Coliru 

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <variant>
#include <queue>

struct node_t {
};
struct specialNode_t {
};
enum class TerminalType {
};

using vertex_t = std::variant<node_t, specialNode_t>; // structs
using edge_t = std::variant<TerminalType>;            // enum

using Graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, vertex_t, edge_t>;

int main() {
    Graph_t myGraph(5);
    boost::default_bfs_visitor vis; // Will do my collecting visitor later...

    auto indexmap = boost::get(boost::vertex_index, myGraph);
    auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);

    using vertex_descriptor = boost::graph_traits<Graph_t>::vertex_descriptor;

    boost::queue<vertex_descriptor> Q;
    boost::breadth_first_visit(myGraph, 0, Q, vis, colormap);
}
...