найти компоненты связности отфильтрованного графа

Как я могу вычислить связанные компоненты отфильтрованного графа с помощью BGL? Я создал рабочий фильтр, который проверяет настраиваемое свойство вершины под названием «живой» и возвращает только «живые» вершины, но connected_components подавляет filtered_graph . Я думаю, это как-то связано с тем фактом, что отфильтрованный граф имеет несмежные идентификаторы вершин, и поэтому operator[], который был определен, больше не определен, но я не уверен, почему и как его кодировать.

typedef boost::adjacency_list<boost::hash_mapS, boost::vecS, boost::undirectedS, VertexProperties> Graph;
typedef boost::property_map<Graph, ::vertex_alive_t>::type AliveMap;

template <typename AliveMap>
struct vertex_is_alive {
  vertex_is_alive() { }
  vertex_is_alive(AliveMap alive) : m_alive(alive) { }
  template <typename Vertex>
  bool operator()(const Vertex& v) const {
    return boost::get(m_alive,v) == STILL_ALIVE_CODE;
  }
  AliveMap m_alive;
};

Graph G;
//generate G...
int N = boost::num_vertices(G);
vector<int> component(N);
int num = boost::connected_components(G, &component[0]);
//do something with component and play around with vertex_alive statuses...this part works fine.
vertex_is_alive<AliveMap> filter(boost::get(::vertex_alive_t(), G));
boost::filtered_graph<Graph, vertex_is_alive<AliveMap> > fG (G, filter); 
int num = boost::connected_components(fG, &component[0]);
//this makes it choke

Сообщения об ошибках, которые я получаю (удаление генеалогии):

/usr/local/include/boost/property_map/property_map.hpp:354:56: error: no match for ‘operator[]’ in ‘((const boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::hash_mapS, boost::vecS, boost::undirectedS, boost::property<vertex_alive_t, unsigned int> >, boost::adjacency_list<boost::hash_mapS, boost::vecS, boost::undirectedS, boost::property<vertex_alive_t, unsigned int> >*, unsigned int, unsigned int&, vertex_alive_t>&)pa)[k]’
/usr/local/include/boost/property_map/property_map.hpp:354:56: note: candidate is:
In file included from /usr/local/include/boost/graph/adjacency_list.hpp:245:0,
                 from main.cpp:1:
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2465:24: note: Reference boost::vec_adj_list_vertex_property_map<Graph, GraphPtr, ValueType, Reference, Tag>::operator[](boost::vec_adj_list_vertex_property_map<Graph, GraphPtr, ValueType, Reference, Tag>::key_type) const [with Graph = boost::adjacency_list<boost::hash_mapS, boost::vecS, boost::undirectedS, boost::property<vertex_alive_t, unsigned int> >; GraphPtr = boost::adjacency_list<boost::hash_mapS, boost::vecS, boost::undirectedS, boost::property<vertex_alive_t, unsigned int> >*; ValueType = unsigned int; Reference = unsigned int&; Tag = vertex_alive_t; boost::vec_adj_list_vertex_property_map<Graph, GraphPtr, ValueType, Reference, Tag>::key_type = unsigned int]
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2465:24: note:   no known conversion for argument 1 from ‘const boost::detail::edge_desc_impl<boost::undirected_tag, unsigned int>’ to ‘boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::hash_mapS, boost::vecS, boost::undirectedS, boost::property<vertex_alive_t, unsigned int> >, boost::adjacency_list<boost::hash_mapS, boost::vecS, boost::undirectedS, boost::property<vertex_alive_t, unsigned int> >*, unsigned int, unsigned int&, vertex_alive_t>::key_type {aka unsigned int}’

person mmdanziger    schedule 13.11.2012    source источник
comment
Вы должны использовать boost::filtered_graph<Graph,boost::keep_all, vertex_is_alive<AliveMap> > fG (G, boost::keep_all(), filter);. Сигнатура отфильтрованного графа — `filter_graph‹Graph, EdgePredicate, VertexPredicate›, поэтому вы использовали свой вершинный фильтр как краевой. Последняя строка в вашей ошибке подразумевает, что boost::get(m_alive,x) требует, чтобы x был дескриптором вершины (unsigned int), и ему передавался дескриптор ребра (const boost::detail::edge_desc_impl‹boost::undirected_tag, unsigned int›).   -  person    schedule 13.11.2012


Ответы (1)


Вы должны использовать boost::filtered_graph > fG (G, boost::keep_all(), filter);. Сигнатура отфильтрованного графа — filtered_graph<Graph, EdgePredicate, VertexPredicate>, поэтому вы использовали свой вершинный фильтр в качестве реберного. Последняя строка в вашей ошибке подразумевает, что boost::get(m_alive,x) требует, чтобы x был дескриптором вершины (unsigned int), и ему передавался дескриптор ребра (const boost::detail::edge_desc_impl<boost::undirected_tag, unsigned int>).

person Community    schedule 14.11.2012