Hi, I am new to boost and I face the same problem mentioned here with "connected_components()" using a mutable graph (hence using a list for the vertex container). I try the detailed solution of Aaron Windsor in the previous post but I still get some errors at compilation. Here is my little code: #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp> using namespace std; using namespace boost; Box& b = conf.GetBox(); if (!ai) { ai = new AtomList(); *ai = conf.GetAtoms().AtomSelector(selecti, b); } typedef boost::adjacency_list< listS, listS, undirectedS, property<vertex_index_t, size_t>, no_property> > graph_t; graph_t g(ai->size()); property_map<graph_t, vertex_index_t>::type index = get(vertex_index, g); graph_traits<graph_t>::vertex_iterator vi, vi_end; graph_traits<graph_t>::vertices_size_type cnt = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) put(index, *vi, cnt++); for (unsigned int i = 0; i < ai->size(); ++i) { Cartesian& crdi = ai->GetElement(i)->pos; for (unsigned int j = i + 1; j < ai->size(); ++j) { Cartesian& crdj = ai->GetElement(j)->pos; double r = conf.GetBox().CartesianDistance(crdi, crdj); if (r < rcut) { add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map if distance criteria is satisfied } } } vector<int> component(num_vertices(g)); int num_clusters = connected_components(g, &component[0], vertex_index_map(index)); The compilation is successfull until I add the last line: int num_clusters = connected_components(g, &component[0], vertex_index_map(index)); Hope somebody can give a hint gabriel
Hi, On Wednesday, 6. April 2011 12:55:52 Gabriel Marchand wrote:
Hi, I am new to boost and I face the same problem mentioned here with "connected_components()" using a mutable graph (hence using a list for the vertex container). I try the detailed solution of Aaron Windsor in the previous post but I still get some errors at compilation. Here is my little code:
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp>
using namespace std; using namespace boost;
Box& b = conf.GetBox();
You seem to use your own classes and you do not provide the definition. Thus this is unfortunately not a minimal example. So in the future, it might facilitate help from others to you, with this in the back of your head.
if (!ai) { ai = new AtomList(); *ai = conf.GetAtoms().AtomSelector(selecti, b); }
typedef boost::adjacency_list< listS, listS, undirectedS, property<vertex_index_t, size_t>, no_property>
> graph_t;
graph_t g(ai->size()); property_map<graph_t, vertex_index_t>::type index = get(vertex_index, g);
With listS as the vertex container, I would expect it to fail here. An adjacency_list with listS does not automatically create a vertex_index property. So you might give vecS a try. Especially, if you insert most of the vertices (if not all) at one specific moment and you are not constantly changing the number of vertices in the graph, I think it will make no big difference in performance whether you use vecS or listS. But you have the benefit of automatic vertex_index property-creation. I can however not compile your example (s. above) nor did you provide the error message you get, so I can't tell you for sure if this is the source of error.
graph_traits<graph_t>::vertex_iterator vi, vi_end; graph_traits<graph_t>::vertices_size_type cnt = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) put(index, *vi, cnt++);
for (unsigned int i = 0; i < ai->size(); ++i) { Cartesian& crdi = ai->GetElement(i)->pos; for (unsigned int j = i + 1; j < ai->size(); ++j) { Cartesian& crdj = ai->GetElement(j)->pos; double r = conf.GetBox().CartesianDistance(crdi, crdj); if (r < rcut) { add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map if distance criteria is satisfied
} } }
vector<int> component(num_vertices(g)); int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
The compilation is successfull until I add the last line: int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
This confuses me a bit, as I would expect the error in an earlier line. So you might look forward to provide your error message or a really working, minimal example.
Hope somebody can give a hint
Hope this helps.
gabriel
Best, Cedric
Hi Cedric and thank you for your reply. Actually I need the mutable graph type (using listS as vertex container) because I'll need to use the functions clear_vertex() and remove_vertex(). And I am facing the problem to create this index map property to the vertices to use the function connected_components(). I wrote a more consistent version of the code (test.cpp attached), following the instructions in a previous post by Aaron Windsor: http://boost.2283326.n4.nabble.com/connected-components-td2576097.html It compiles until I added the last line: "int num_clusters = connected_components(G, &component[0], vertex_index_map(index));" The compiler tells: gmarchand@bohr:~/TMP$ g++ test.cpp In file included from /usr/include/c++/4.4/backward/hash_set:60, from /usr/include/boost/graph/adjacency_list.hpp:25, from test.cpp:3: /usr/include/c++/4.4/backward/backward_warning.h:28:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. In file included from /usr/include/boost/graph/adjacency_list.hpp:42, from test.cpp:3: /usr/include/boost/property_map/property_map.hpp: In member function ‘void boost::WritablePropertyMapConcept<PMap, Key>::constraints() [with PMap = int*, Key = void*]’: /usr/include/boost/concept/detail/has_constraints.hpp:40: instantiated from ‘const bool boost::concept::not_satisfied<boost::WritablePropertyMapConcept<int*, void*> >::value’ /usr/include/boost/concept/detail/has_constraints.hpp:43: instantiated from ‘boost::concept::not_satisfied<boost::WritablePropertyMapConcept<int*, void*> >’ /usr/include/boost/mpl/if.hpp:67: instantiated from ‘boost::mpl::if_<boost::concept::not_satisfied<boost::WritablePropertyMapConcept<int*, void*> >, boost::concept::constraint<boost::WritablePropertyMapConcept<int*, void*> >, boost::concept::requirement<boost::WritablePropertyMapConcept<int*, void*> > >’ /usr/include/boost/concept/detail/general.hpp:19: instantiated from ‘boost::concept::requirement_<void (*)(boost::WritablePropertyMapConcept<int*, void*>)>’ /usr/include/boost/concept_check.hpp:43: instantiated from ‘void boost::function_requires(Model*) [with Model = boost::WritablePropertyMapConcept<int*, void*>]’ /usr/include/boost/graph/connected_components.hpp:67: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/property_map/property_map.hpp:195: error: no matching function for call to ‘put(int*&, void*&, int&)’ In file included from test.cpp:4: /usr/include/boost/graph/connected_components.hpp: In member function ‘void boost::detail::components_recorder<ComponentsMap>::discover_vertex(Vertex, Graph&) [with Vertex = void*, Graph = const boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, ComponentsMap = int*]’: /usr/include/boost/graph/depth_first_search.hpp:103: instantiated from ‘void boost::detail::depth_first_visit_impl(const IncidenceGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, DFSVisitor&, ColorMap, TerminatorFunc) [with IncidenceGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >, TerminatorFunc = boost::detail::nontruth2]’ /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >]’ /usr/include/boost/graph/depth_first_search.hpp:296: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, P = boost::detail::components_recorder<int*>, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, boost::vertex_index_t, boost::no_property>]’ /usr/include/boost/graph/connected_components.hpp:75: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/graph/connected_components.hpp:46: error: no matching function for call to ‘put(int*&, void*&, int&)’ /usr/include/boost/graph/connected_components.hpp: In member function ‘void boost::detail::components_recorder<ComponentsMap>::discover_vertex(Vertex, Graph&) [with Vertex = void*, Graph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, ComponentsMap = int*]’: /usr/include/boost/graph/depth_first_search.hpp:38: instantiated from ‘void boost::DFSVisitorConcept<Visitor, Graph>::constraints() [with Visitor = boost::detail::components_recorder<int*>, Graph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>]’ /usr/include/boost/concept/detail/has_constraints.hpp:40: instantiated from ‘const bool boost::concept::not_satisfied<boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >::value’ /usr/include/boost/concept/detail/has_constraints.hpp:43: instantiated from ‘boost::concept::not_satisfied<boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >’ /usr/include/boost/mpl/if.hpp:67: instantiated from ‘boost::mpl::if_<boost::concept::not_satisfied<boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >, boost::concept::constraint<boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >, boost::concept::requirement<boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > > >’ /usr/include/boost/concept/detail/general.hpp:19: instantiated from ‘boost::concept::requirement_<void (*)(boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> >)>’ /usr/include/boost/concept_check.hpp:43: instantiated from ‘void boost::function_requires(Model*) [with Model = boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> >]’ /usr/include/boost/graph/depth_first_search.hpp:191: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >]’ /usr/include/boost/graph/depth_first_search.hpp:296: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, P = boost::detail::components_recorder<int*>, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, boost::vertex_index_t, boost::no_property>]’ /usr/include/boost/graph/connected_components.hpp:75: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/graph/connected_components.hpp:46: error: no matching function for call to ‘put(int*&, void*&, int&)’ gmarchand@bohr:~/TMP$ I hope it is more clear now, Gabriel --- En date de : Mer 6.4.11, Cedric Laczny <cedric.laczny@gmx.de> a écrit : De: Cedric Laczny <cedric.laczny@gmx.de> Objet: Re: [Boost-users] (no subject) À: boost-users@lists.boost.org Date: Mercredi 6 avril 2011, 16h15 Hi, On Wednesday, 6. April 2011 12:55:52 Gabriel Marchand wrote:
Hi, I am new to boost and I face the same problem mentioned here with "connected_components()" using a mutable graph (hence using a list for the vertex container). I try the detailed solution of Aaron Windsor in the previous post but I still get some errors at compilation. Here is my little code:
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp>
using namespace std; using namespace boost;
Box& b = conf.GetBox();
You seem to use your own classes and you do not provide the definition. Thus this is unfortunately not a minimal example. So in the future, it might facilitate help from others to you, with this in the back of your head.
if (!ai) { ai = new AtomList(); *ai = conf.GetAtoms().AtomSelector(selecti, b); }
typedef boost::adjacency_list< listS, listS, undirectedS, property<vertex_index_t, size_t>, no_property>
> graph_t;
graph_t g(ai->size()); property_map<graph_t, vertex_index_t>::type index = get(vertex_index, g);
With listS as the vertex container, I would expect it to fail here. An adjacency_list with listS does not automatically create a vertex_index property. So you might give vecS a try. Especially, if you insert most of the vertices (if not all) at one specific moment and you are not constantly changing the number of vertices in the graph, I think it will make no big difference in performance whether you use vecS or listS. But you have the benefit of automatic vertex_index property-creation. I can however not compile your example (s. above) nor did you provide the error message you get, so I can't tell you for sure if this is the source of error.
graph_traits<graph_t>::vertex_iterator vi, vi_end; graph_traits<graph_t>::vertices_size_type cnt = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) put(index, *vi, cnt++);
for (unsigned int i = 0; i < ai->size(); ++i) { Cartesian& crdi = ai->GetElement(i)->pos; for (unsigned int j = i + 1; j < ai->size(); ++j) { Cartesian& crdj = ai->GetElement(j)->pos; double r = conf.GetBox().CartesianDistance(crdi, crdj); if (r < rcut) { add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map if distance criteria is satisfied
} } }
vector<int> component(num_vertices(g)); int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
The compilation is successfull until I add the last line: int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
This confuses me a bit, as I would expect the error in an earlier line. So you might look forward to provide your error message or a really working, minimal example.
Hope somebody can give a hint
Hope this helps.
gabriel
Best, Cedric _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Wednesday, 6. April 2011 19:33:00 Gabriel Marchand wrote:
Hi Cedric and thank you for your reply.
Actually I need the mutable graph type (using listS as vertex container) because I'll need to use the functions clear_vertex() and remove_vertex(). And I am facing the problem to create this index map property to the vertices to use the function connected_components().
I wrote a more consistent version of the code (test.cpp attached),
Could it be that you forgot to really attach it, or did the mailinglist truncate your original mail? Alternatively, you could put your code on a pastebin service (e.g. dpaste). When I search for errors, I like to play with the erroneous code, therefore having it would be great. Thanks for refering to the original topic.
following the instructions in a previous post by Aaron Windsor: http://boost.2283326.n4.nabble.com/connected-components-td2576097.html
It compiles until I added the last line: "int num_clusters = connected_components(G, &component[0], vertex_index_map(index));"
The compiler tells:
, boost::concept::requirement<boost::WritablePropertyMapConcept<int*, void*> > >’ /usr/include/boost/concept/detail/general.hpp:19: instantiated from ‘boost::concept::requirement_<void (*)(boost::WritablePropertyMapConcept<int*, void*>)>’ /usr/include/boost/concept_check.hpp:43: instantiated from ‘void boost::function_requires(Model*) [with Model = boost::WritablePropertyMapConcept<int*, void*>]’ /usr/include/boost/graph/connected_components.hpp:67: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/property_map/property_map.hpp:195: error: no matching function for call to ‘put(int*&, void*&, int&)’ In file included from test.cpp:4: /usr/include/boost/graph/connected_components.hpp: In member function ‘void boost::detail::components_recorder<ComponentsMap>::discover_vertex(Vertex, Graph&) [with Vertex = void*, Graph = const boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, ComponentsMap = int*]’: /usr/include/boost/graph/depth_first_search.hpp:103: instantiated from ‘void boost::detail::depth_first_visit_impl(const IncidenceGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, DFSVisitor&, ColorMap, TerminatorFunc) [with IncidenceGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >, TerminatorFunc = boost::detail::nontruth2]’ /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >]’ /usr/include/boost/graph/depth_first_search.hpp:296: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, P = boost::detail::components_recorder<int*>, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::adj_list_vertex_property_map<boost::adjacen cy_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, boost::vertex_index_t, boost::no_property>]’ /usr/include/boost/graph/connected_components.hpp:75: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/graph/connected_components.hpp:46: error: no matching function for call to ‘put(int*&, void*&, int&)’ /usr/include/boost/graph/connected_components.hpp: In member function ‘void boost::detail::components_recorder<ComponentsMap>::discover_vertex(Vertex, Graph&) [with Vertex = void*, Graph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, ComponentsMap = int*]’: /usr/include/boost/graph/depth_first_search.hpp:38: instantiated from ‘void boost::DFSVisitorConcept<Visitor, Graph>::constraints() [with Visitor = boost::detail::components_recorder<int*>, Graph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>]’ /usr/include/boost/concept/detail/has_constraints.hpp:40: instantiated from ‘const bool boost::concept::not_satisfied<boost::DFSVisitorConcept<boost::detail::comp onents_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >::value’ /usr/include/boost/concept/detail/has_constraints.hpp:43: instantiated from ‘boost::concept::not_satisfied<boost::DFSVisitorConcept<boost::detail::com
gmarchand@bohr:~/TMP$ g++ test.cpp In file included from /usr/include/c++/4.4/backward/hash_set:60, from /usr/include/boost/graph/adjacency_list.hpp:25, from test.cpp:3: /usr/include/c++/4.4/backward/backward_warning.h:28:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. In file included from /usr/include/boost/graph/adjacency_list.hpp:42, from test.cpp:3: /usr/include/boost/property_map/property_map.hpp: In member function ‘void boost::WritablePropertyMapConcept<PMap, Key>::constraints() [with PMap = int*, Key = void*]’: /usr/include/boost/concept/detail/has_constraints.hpp:40: instantiated from ‘const bool boost::concept::not_satisfied<boost::WritablePropertyMapConcept<int*, void*> >::value’ /usr/include/boost/concept/detail/has_constraints.hpp:43: instantiated from ‘boost::concept::not_satisfied<boost::WritablePropertyMapConcept<int*, void*> >’ /usr/include/boost/mpl/if.hpp:67: instantiated from ‘boost::mpl::if_<boost::concept::not_satisfied<boost::WritablePropertyMapC oncept<int*, void*> >, boost::concept::constraint<boost::WritablePropertyMapConcept<int*, void*> ponents_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >’ /usr/include/boost/mpl/if.hpp:67: instantiated from ‘boost::mpl::if_<boost::concept::not_satisfied<boost::DFSVisitorConcept<bo ost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >, boost::concept::constraint<boost::DFSVisitorConcept<boost::detail::compone nts_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >, boost::concept::requirement<boost::DFSVisitorConcept<boost::detail::compon ents_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > > >’ /usr/include/boost/concept/detail/general.hpp:19: instantiated from ‘boost::concept::requirement_<void (*)(boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>
)>’ /usr/include/boost/concept_check.hpp:43: instantiated from ‘void boost::function_requires(Model*) [with Model = boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> ]’ /usr/include/boost/graph/depth_first_search.hpp:191: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >]’ /usr/include/boost/graph/depth_first_search.hpp:296: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, P = boost::detail::components_recorder<int*>, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::adj_list_vertex_property_map<boost::adjacen cy_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, boost::vertex_index_t, boost::no_property>]’ /usr/include/boost/graph/connected_components.hpp:75: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/graph/connected_components.hpp:46: error: no matching function for call to ‘put(int*&, void*&, int&)’ gmarchand@bohr:~/TMP$
I hope it is more clear now, Gabriel
--- En date de : Mer 6.4.11, Cedric Laczny <cedric.laczny@gmx.de> a écrit :
De: Cedric Laczny <cedric.laczny@gmx.de> Objet: Re: [Boost-users] (no subject) À: boost-users@lists.boost.org Date: Mercredi 6 avril 2011, 16h15
Hi,
On Wednesday, 6. April 2011 12:55:52 Gabriel Marchand wrote:
Hi, I am new to boost and I face the same problem mentioned here with "connected_components()" using a mutable graph (hence using a list for the vertex container). I try the detailed solution of Aaron Windsor in the previous post but I still get some errors at compilation. Here is my
little code: #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp>
using namespace std; using namespace boost;
Box& b = conf.GetBox();
You seem to use your own classes and you do not provide the definition. Thus this is unfortunately not a minimal example. So in the future, it might facilitate help from others to you, with this in the back of your head.
if (!ai) { ai = new AtomList(); *ai = conf.GetAtoms().AtomSelector(selecti, b); }
typedef boost::adjacency_list< listS, listS, undirectedS, property<vertex_index_t, size_t>, no_property>
> graph_t;
graph_t g(ai->size()); property_map<graph_t, vertex_index_t>::type index = get(vertex_index,
g);
With listS as the vertex container, I would expect it to fail here. An adjacency_list with listS does not automatically create a vertex_index property. So you might give vecS a try. Especially, if you insert most of the vertices (if not all) at one specific moment and you are not constantly changing the number of vertices in the graph, I think it will make no big difference in performance whether you use vecS or listS. But you have the benefit of automatic vertex_index property-creation. I can however not compile your example (s. above) nor did you provide the error message you get, so I can't tell you for sure if this is the source of error.
graph_traits<graph_t>::vertex_iterator vi, vi_end;
graph_traits<graph_t>::vertices_size_type cnt = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) put(index, *vi, cnt++);
for (unsigned int i = 0; i < ai->size(); ++i) { Cartesian& crdi = ai->GetElement(i)->pos; for (unsigned int j = i + 1; j < ai->size(); ++j) { Cartesian& crdj = ai->GetElement(j)->pos; double r = conf.GetBox().CartesianDistance(crdi, crdj); if (r < rcut) { add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map
if distance criteria is satisfied
} } }
vector<int> component(num_vertices(g)); int num_clusters = connected_components(g, &component[0],
vertex_index_map(index));
The compilation is successfull until I add the last line: int num_clusters = connected_components(g, &component[0],
vertex_index_map(index));
This confuses me a bit, as I would expect the error in an earlier line. So you might look forward to provide your error message or a really working, minimal example.
Hope somebody can give a hint
Hope this helps.
gabriel
Best,
Cedric
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Wednesday, 6. April 2011 19:33:00 Gabriel Marchand wrote:
Hi Cedric and thank you for your reply.
Actually I need the mutable graph type (using listS as vertex container) because I'll need to use the functions clear_vertex() and remove_vertex(). And I am facing the problem to create this index map property to the vertices to use the function connected_components().
I wrote a more consistent version of the code (test.cpp attached), following the instructions in a previous post by Aaron Windsor: http://boost.2283326.n4.nabble.com/connected-components-td2576097.html
Actually, Aaron Windsor also described the way you should normally follow (in case of listS as vertex container) and that is to create your _own_ vertex- index map. In your code, you try to get it from the graph, but with listS, such an index is _not_ created. To give you an idea, please look at point 5 in http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/faq.html where it explains how to create your own index map. Basically, you create an entry for each vertex, incrementing a counter. Still, I am confused that it only complains about the call of connected_components() at the end, but not about the get(vertex_index, g). Therefore, I would need to play with your code.
It compiles until I added the last line: "int num_clusters = connected_components(G, &component[0], vertex_index_map(index));"
The compiler tells:
, boost::concept::requirement<boost::WritablePropertyMapConcept<int*, void*> > >’ /usr/include/boost/concept/detail/general.hpp:19: instantiated from ‘boost::concept::requirement_<void (*)(boost::WritablePropertyMapConcept<int*, void*>)>’ /usr/include/boost/concept_check.hpp:43: instantiated from ‘void boost::function_requires(Model*) [with Model = boost::WritablePropertyMapConcept<int*, void*>]’ /usr/include/boost/graph/connected_components.hpp:67: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/property_map/property_map.hpp:195: error: no matching function for call to ‘put(int*&, void*&, int&)’ In file included from test.cpp:4: /usr/include/boost/graph/connected_components.hpp: In member function ‘void boost::detail::components_recorder<ComponentsMap>::discover_vertex(Vertex, Graph&) [with Vertex = void*, Graph = const boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, ComponentsMap = int*]’: /usr/include/boost/graph/depth_first_search.hpp:103: instantiated from ‘void boost::detail::depth_first_visit_impl(const IncidenceGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, DFSVisitor&, ColorMap, TerminatorFunc) [with IncidenceGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >, TerminatorFunc = boost::detail::nontruth2]’ /usr/include/boost/graph/depth_first_search.hpp:201: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >]’ /usr/include/boost/graph/depth_first_search.hpp:296: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, P = boost::detail::components_recorder<int*>, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::adj_list_vertex_property_map<boost::adjacen cy_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, boost::vertex_index_t, boost::no_property>]’ /usr/include/boost/graph/connected_components.hpp:75: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/graph/connected_components.hpp:46: error: no matching function for call to ‘put(int*&, void*&, int&)’ /usr/include/boost/graph/connected_components.hpp: In member function ‘void boost::detail::components_recorder<ComponentsMap>::discover_vertex(Vertex, Graph&) [with Vertex = void*, Graph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, ComponentsMap = int*]’: /usr/include/boost/graph/depth_first_search.hpp:38: instantiated from ‘void boost::DFSVisitorConcept<Visitor, Graph>::constraints() [with Visitor = boost::detail::components_recorder<int*>, Graph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>]’ /usr/include/boost/concept/detail/has_constraints.hpp:40: instantiated from ‘const bool boost::concept::not_satisfied<boost::DFSVisitorConcept<boost::detail::comp onents_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >::value’ /usr/include/boost/concept/detail/has_constraints.hpp:43: instantiated from ‘boost::concept::not_satisfied<boost::DFSVisitorConcept<boost::detail::com
gmarchand@bohr:~/TMP$ g++ test.cpp In file included from /usr/include/c++/4.4/backward/hash_set:60, from /usr/include/boost/graph/adjacency_list.hpp:25, from test.cpp:3: /usr/include/c++/4.4/backward/backward_warning.h:28:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. In file included from /usr/include/boost/graph/adjacency_list.hpp:42, from test.cpp:3: /usr/include/boost/property_map/property_map.hpp: In member function ‘void boost::WritablePropertyMapConcept<PMap, Key>::constraints() [with PMap = int*, Key = void*]’: /usr/include/boost/concept/detail/has_constraints.hpp:40: instantiated from ‘const bool boost::concept::not_satisfied<boost::WritablePropertyMapConcept<int*, void*> >::value’ /usr/include/boost/concept/detail/has_constraints.hpp:43: instantiated from ‘boost::concept::not_satisfied<boost::WritablePropertyMapConcept<int*, void*> >’ /usr/include/boost/mpl/if.hpp:67: instantiated from ‘boost::mpl::if_<boost::concept::not_satisfied<boost::WritablePropertyMapC oncept<int*, void*> >, boost::concept::constraint<boost::WritablePropertyMapConcept<int*, void*> ponents_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >’ /usr/include/boost/mpl/if.hpp:67: instantiated from ‘boost::mpl::if_<boost::concept::not_satisfied<boost::DFSVisitorConcept<bo ost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >, boost::concept::constraint<boost::DFSVisitorConcept<boost::detail::compone nts_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > >, boost::concept::requirement<boost::DFSVisitorConcept<boost::detail::compon ents_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> > > >’ /usr/include/boost/concept/detail/general.hpp:19: instantiated from ‘boost::concept::requirement_<void (*)(boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>
)>’ /usr/include/boost/concept_check.hpp:43: instantiated from ‘void boost::function_requires(Model*) [with Model = boost::DFSVisitorConcept<boost::detail::components_recorder<int*>, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS> ]’ /usr/include/boost/graph/depth_first_search.hpp:191: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, DFSVisitor = boost::detail::components_recorder<int*>, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t> >]’ /usr/include/boost/graph/depth_first_search.hpp:296: instantiated from ‘void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, P = boost::detail::components_recorder<int*>, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::adj_list_vertex_property_map<boost::adjacen cy_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, boost::vertex_index_t, boost::no_property>]’ /usr/include/boost/graph/connected_components.hpp:75: instantiated from ‘typename boost::property_traits<IndexMap>::value_type boost::connected_components(const Graph&, ComponentMap, const boost::bgl_named_params<P, T, R>&, typename boost::enable_if_c<boost::is_base_and_derived::value, boost::graph::detail::no_parameter>::type) [with Graph = main()::graph_t, ComponentMap = int*, P = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, boost::property<boost::vertex_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, long unsigned int, long unsigned int&, boost::vertex_index_t>, T = boost::vertex_index_t, R = boost::no_property]’ test.cpp:54: instantiated from here /usr/include/boost/graph/connected_components.hpp:46: error: no matching function for call to ‘put(int*&, void*&, int&)’ gmarchand@bohr:~/TMP$
I hope it is more clear now, Gabriel
--- En date de : Mer 6.4.11, Cedric Laczny <cedric.laczny@gmx.de> a écrit :
De: Cedric Laczny <cedric.laczny@gmx.de> Objet: Re: [Boost-users] (no subject) À: boost-users@lists.boost.org Date: Mercredi 6 avril 2011, 16h15
Hi,
On Wednesday, 6. April 2011 12:55:52 Gabriel Marchand wrote:
Hi, I am new to boost and I face the same problem mentioned here with "connected_components()" using a mutable graph (hence using a list for the vertex container). I try the detailed solution of Aaron Windsor in the previous post but I still get some errors at compilation. Here is my
little code: #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp>
using namespace std; using namespace boost;
Box& b = conf.GetBox();
You seem to use your own classes and you do not provide the definition. Thus this is unfortunately not a minimal example. So in the future, it might facilitate help from others to you, with this in the back of your head.
if (!ai) { ai = new AtomList(); *ai = conf.GetAtoms().AtomSelector(selecti, b); }
typedef boost::adjacency_list< listS, listS, undirectedS, property<vertex_index_t, size_t>, no_property>
> graph_t;
graph_t g(ai->size()); property_map<graph_t, vertex_index_t>::type index = get(vertex_index,
g);
With listS as the vertex container, I would expect it to fail here. An adjacency_list with listS does not automatically create a vertex_index property. So you might give vecS a try. Especially, if you insert most of the vertices (if not all) at one specific moment and you are not constantly changing the number of vertices in the graph, I think it will make no big difference in performance whether you use vecS or listS. But you have the benefit of automatic vertex_index property-creation. I can however not compile your example (s. above) nor did you provide the error message you get, so I can't tell you for sure if this is the source of error.
graph_traits<graph_t>::vertex_iterator vi, vi_end;
graph_traits<graph_t>::vertices_size_type cnt = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) put(index, *vi, cnt++);
for (unsigned int i = 0; i < ai->size(); ++i) { Cartesian& crdi = ai->GetElement(i)->pos; for (unsigned int j = i + 1; j < ai->size(); ++j) { Cartesian& crdj = ai->GetElement(j)->pos; double r = conf.GetBox().CartesianDistance(crdi, crdj); if (r < rcut) { add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map
if distance criteria is satisfied
} } }
vector<int> component(num_vertices(g)); int num_clusters = connected_components(g, &component[0],
vertex_index_map(index));
The compilation is successfull until I add the last line: int num_clusters = connected_components(g, &component[0],
vertex_index_map(index));
This confuses me a bit, as I would expect the error in an earlier line. So you might look forward to provide your error message or a really working, minimal example.
Hope somebody can give a hint
Hope this helps.
gabriel
Best,
Cedric
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Wednesday, 6. April 2011 12:55:52 Gabriel Marchand wrote:
Hi, I am new to boost and I face the same problem mentioned here with "connected_components()" using a mutable graph (hence using a list for the vertex container). I try the detailed solution of Aaron Windsor in the previous post but I still get some errors at compilation. Here is my little code:
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp>
using namespace std; using namespace boost;
Box& b = conf.GetBox();
if (!ai) { ai = new AtomList(); *ai = conf.GetAtoms().AtomSelector(selecti, b); }
typedef boost::adjacency_list< listS, listS, undirectedS, property<vertex_index_t, size_t>, no_property>
> graph_t;
graph_t g(ai->size()); property_map<graph_t, vertex_index_t>::type index = get(vertex_index, g); graph_traits<graph_t>::vertex_iterator vi, vi_end; graph_traits<graph_t>::vertices_size_type cnt = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) put(index, *vi, cnt++);
for (unsigned int i = 0; i < ai->size(); ++i) { Cartesian& crdi = ai->GetElement(i)->pos; for (unsigned int j = i + 1; j < ai->size(); ++j) { Cartesian& crdj = ai->GetElement(j)->pos; double r = conf.GetBox().CartesianDistance(crdi, crdj); if (r < rcut) { add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map if distance criteria is satisfied
} } }
vector<int> component(num_vertices(g)); int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
Interstingly, while your code does in fact compile with listS and connected_component() being commented out, it results in a Segmentation Fault at the line containing put(index, *vi, cnt++); I don't know yet what causes this, but I am assuming that it has something to do with the error message you also provided stating missing put() definition for void*. By this, I mean that I assume that the usage of listS works somehow with void* (would make sense to me in some way) but this seems to be problematic, at least as fas as I know until now. I will have a deeper look at it. Until then, perhaps someone else will drop in and maybe even clarify this.
The compilation is successfull until I add the last line: int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
Hope somebody can give a hint gabriel
Sorry, I have to correct my last post. The Segmentation Fault was due to modifications from me in the code and I simply missed something there thus causing the error. My apologies. Nevertheless, I will still have a deeper look at it. Best, Cedric On Wednesday, 6. April 2011 12:55:52 Gabriel Marchand wrote:
Hi, I am new to boost and I face the same problem mentioned here with "connected_components()" using a mutable graph (hence using a list for the vertex container). I try the detailed solution of Aaron Windsor in the previous post but I still get some errors at compilation. Here is my little code:
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp>
using namespace std; using namespace boost;
Box& b = conf.GetBox();
if (!ai) { ai = new AtomList(); *ai = conf.GetAtoms().AtomSelector(selecti, b); }
typedef boost::adjacency_list< listS, listS, undirectedS, property<vertex_index_t, size_t>, no_property>
> graph_t;
graph_t g(ai->size()); property_map<graph_t, vertex_index_t>::type index = get(vertex_index, g); graph_traits<graph_t>::vertex_iterator vi, vi_end; graph_traits<graph_t>::vertices_size_type cnt = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) put(index, *vi, cnt++);
for (unsigned int i = 0; i < ai->size(); ++i) { Cartesian& crdi = ai->GetElement(i)->pos; for (unsigned int j = i + 1; j < ai->size(); ++j) { Cartesian& crdj = ai->GetElement(j)->pos; double r = conf.GetBox().CartesianDistance(crdi, crdj); if (r < rcut) { add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map if distance criteria is satisfied
} } }
vector<int> component(num_vertices(g)); int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
The compilation is successfull until I add the last line: int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
Hope somebody can give a hint gabriel
Alright, now that was a somehow tricky one... Details s. below. On Wednesday, 6. April 2011 12:55:52 Gabriel Marchand wrote:
Hi, I am new to boost and I face the same problem mentioned here with "connected_components()" using a mutable graph (hence using a list for the vertex container). I try the detailed solution of Aaron Windsor in the previous post but I still get some errors at compilation. Here is my little code:
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp>
using namespace std; using namespace boost;
Box& b = conf.GetBox();
if (!ai) { ai = new AtomList(); *ai = conf.GetAtoms().AtomSelector(selecti, b); }
typedef boost::adjacency_list< listS, listS, undirectedS, property<vertex_index_t, size_t>, no_property>
> graph_t;
graph_t g(ai->size()); property_map<graph_t, vertex_index_t>::type index = get(vertex_index, g); graph_traits<graph_t>::vertex_iterator vi, vi_end; graph_traits<graph_t>::vertices_size_type cnt = 0; for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) put(index, *vi, cnt++);
for (unsigned int i = 0; i < ai->size(); ++i) { Cartesian& crdi = ai->GetElement(i)->pos; for (unsigned int j = i + 1; j < ai->size(); ++j) { Cartesian& crdj = ai->GetElement(j)->pos; double r = conf.GetBox().CartesianDistance(crdi, crdj); if (r < rcut) { add_edge(vertex(i,g), vertex(j,g), g); // Add edge to Map if distance criteria is satisfied
} } }
vector<int> component(num_vertices(g)); int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
In the example for connected_components() you used, you probably found the "&component[0]" notation and simply used it. However, this does _not_ work for graphs with listS, only for vecS. So basically what you have to do is to define your own components map and _not_ use that wrapper around a vector. As boost seems to model vertices with listS as void* this can hardly work as it is missing the index that it would normally have when using vecS. Also, for vecS, vertices seem to be modeled as int and therefore can serve as indices for vectors directly. So, to make your code compiles, you should use: typedef graph_traits<graph_t>::vertex_descriptor Vertex; map< Vertex, unsigned int > index_std_map; typedef associative_property_map< map< Vertex, unsigned int > > IndexMap; IndexMap index( index_std_map ); // put() the values by iterating over all vertices instead of getting the vertex_index from the graph via "get(vertex_index, G)". With this, you can define your own components-map: vector<int> v_component(num_vertices(G)); iterator_property_map< vector<int>::iterator, IndexMap > component( v_component.begin(), index ); and call connected_components() via: int num_clusters = connected_components(G, component, vertex_index_map(index));
The compilation is successfull until I add the last line: int num_clusters = connected_components(g, &component[0], vertex_index_map(index));
Hope somebody can give a hint gabriel
Hope that I could help and that this solution will be correct for you. Please, of course, test the whole approach in order to make sure it works as you expect it to. Generally it should, as long as the mapping from vertex to index/offset is correct. If there are further questions about the problem or my solution, feel free to mail again. Best, Cedric
participants (2)
-
Cedric Laczny -
Gabriel Marchand