[Graph] bundled properties and connected_components
Hi, I use an undirected graph with bundled properties and want to find out, whether it is connected, or not. Reading the documentation and some examples using property maps, I did not succeed in getting it to work. A minimal example that reproduces the compile errors follows. What am I doing wrong here: #include <boost/config.hpp> #include <vector> #include <iostream> // for std::cout #include <algorithm> // for std::for_each #include <boost/utility.hpp> // for boost::tie #include <boost/graph/graph_traits.hpp> // for boost::graph_traits #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp> using namespace boost; struct Node { int index; }; struct Boundary { double something; }; typedef boost::adjacency_list< boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS> Graph; int main(int argc, char*argv[]) { Graph g(5); boost::graph_traits<Graph>::vertex_iterator vi, viend; std::vector<int> c(num_vertices(g)); int num; // manually intialize the vertex index, // because we have listS as vertex list type int n = 0; for (tie(vi, viend) = vertices(g); vi != viend; ++vi, ++n) { g[*vi].index = n; } num = connected_components(g, make_iterator_property_map(c.begin(), get(&Node::index, g), c[0])); return 0; } compile log: Compiler: Default compiler Executing g++.exe... g++.exe "Y:\graph\boost\test2.cpp" -o "Y:\graph\boost\test2.exe" -I"C:\Dev-Cpp\lib\gcc\mingw32\3.4.2\include" -I"C:\Dev-Cpp\include\c++\3.4.2\backward" -I"C:\Dev-Cpp\include\c++\3.4.2\mingw32" -I"C:\Dev-Cpp\include\c++\3.4.2" -I"C:\Dev-Cpp\include" -L"C:\Dev-Cpp\lib" C:/Dev-Cpp/include/boost/property_map.hpp: In member function `R boost::iterator_property_map<RandomAccessIterator, IndexMap, T, R>::operator[](typename boost::property_traits<IndexMap>::key_type) const [with RandomAccessIterator = __gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, IndexMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, T = boost::default_color_type, R = boost::default_color_type&]': C:/Dev-Cpp/include/boost/property_map.hpp:319: instantiated from `void boost::put(const boost::put_get_helper<Reference, PropertyMap>&, K, const V&) [with PropertyMap = boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>, Reference = boost::default_color_type&, K = void*, V = boost::default_color_type]' C:/Dev-Cpp/include/boost/graph/depth_first_search.hpp:197: instantiated from `void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, DFSVisitor = boost::detail::components_recorder<boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, boost::bundle_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, void*, Node, int>, int, int&> >, ColorMap = boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>]' C:/Dev-Cpp/include/boost/graph/depth_first_search.hpp:246: instantiated from `static void boost::detail::dfs_dispatch<boost::detail::error_property_not_found>::apply(const VertexListGraph&, DFSVisitor, Vertex, const boost::bgl_named_params<P, T, R>&, boost::detail::error_property_not_found) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, Vertex = void*, DFSVisitor = boost::detail::components_recorder<boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, boost::bundle_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, void*, Node, int>, int, int&> >, P = boost::detail::components_recorder<boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, boost::bundle_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, void*, Node, int>, int, int&> >, T = boost::graph_visitor_t, R = boost::no_property]' C:/Dev-Cpp/include/boost/graph/depth_first_search.hpp:324: instantiated from `void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, P = boost::detail::components_recorder<boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, boost::bundle_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, void*, Node, int>, int, int&> >, T = boost::graph_visitor_t, R = boost::no_property]' C:/Dev-Cpp/include/boost/graph/connected_components.hpp:93: instantiated from `typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap) [with Graph = Graph, ComponentMap = boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, boost::bundle_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, void*, Node, int>, int, int&>]' Y:\graph\boost\test2.cpp:38: instantiated from here C:/Dev-Cpp/include/boost/property_map.hpp:349: error: no match for 'operator+' in '((const boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>*)this)->boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>::iter + boost::get [with PropertyMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, Reference = const boost::detail::error_property_not_found&, K = void*](((const boost::put_get_helper<const boost::detail::error_property_not_found&, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>
&)((const boost::put_get_helper<const boost::detail::error_property_not_found&, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> *)(((const boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>*)((const boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::default_color_type, std::allocator<boost::default_color_type> > >, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::setS, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, boost::default_color_type, boost::default_color_type&>*)this)) + 4u))), ((void* const&)((void* const*)(&v))))' C:/Dev-Cpp/include/c++/3.4.2/bits/stl_iterator.h:654: note: candidates are: __gnu_cxx::__normal_iterator<_Iterator, _Container> __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator+(const typename std::iterator_traits<_Iterator>::difference_type&) const [with _Iterator = boost::default_color_type*, _Container = std::vector<boost::default_color_type, std::allocator<boost::default_color_type> >] C:/Dev-Cpp/include/c++/3.4.2/bits/stl_bvector.h:345: note: std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&) C:/Dev-Cpp/include/c++/3.4.2/bits/stl_bvector.h:261: note: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
Execution terminated
Hola Andre, pleas take a look in this. Works more o less. Atentamente, --dmitry André Loose wrote:
Hi,
I use an undirected graph with bundled properties and want to find out, whether it is connected, or not. Reading the documentation and some examples using property maps, I did not succeed in getting it to work. A minimal example that reproduces the compile errors follows. What am I doing wrong here:
#include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> // for boost::graph_traits #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp> #include <boost/graph/iteration_macros.hpp> struct Node { typedef int vertex_index_t; vertex_index_t m_vertex_index; static vertex_index_t Node::* svertex_index; }; Node::vertex_index_t Node::* svertex_index = &Node::m_vertex_index; struct Boundary { double something; }; typedef boost::adjacency_list< boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::no_property, boost::setS> Graph; int main(int argc, char*argv[]) { using namespace boost; Graph g(5); // manually intialize the vertex index, // because we have listS as vertex list type int n = 0; BGL_FORALL_VERTICES(vd, g, Graph) { put(svertex_index, g, vd, n++); } typedef graph_traits<Graph>::vertex_descriptor vertex_t; std::map<vertex_t, int> comps; property_map<Graph, Node::vertex_index_t Node::*>::type i_m(get(svertex_index, g)); int num = connected_components(g, make_assoc_property_map(comps), boost::vertex_index_map(i_m)); std::cout << "Number of cc: " << num << std::endl; return 0; }
Ups, I think this is better. References: http://boost.org/libs/graph/doc/connected_components.html --dima #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> // for boost::graph_traits #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp> #include <boost/graph/iteration_macros.hpp> /**/ struct Node { typedef int vertex_index_t; vertex_index_t m_vertex_index; static vertex_index_t Node::* svertex_index; }; Node::vertex_index_t Node::* svertex_index = &Node::m_vertex_index; struct Boundary { double something; }; typedef boost::adjacency_list< boost::setS, boost::listS, boost::undirectedS, Node, Boundary, boost::no_property, boost::setS> Graph; int main(int argc, char*argv[]) { Graph g(5); typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t; std::map<vertex_t, int> comps; std::map<vertex_t, boost::default_color_type> c_m; int num = boost::connected_components(g, boost::make_assoc_property_map(comps), boost::color_map(boost::make_assoc_property_map(c_m))); std::cout << "Number of cc: " << num << std::endl; return 0; }
participants (2)
-
André Loose
-
Dmitry Bufistov