Re: [Boost-users] (no subject)

Subject: Re: [Boost-users] (no subject)
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-04-06 13:58:04

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:
> 
> gmarchand_at_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*>
> >, 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
> 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_at_bohr:~/TMP$
> 
> I hope it is more clear now,
> Gabriel
> 
> 
> --- En date de : Mer 6.4.11, Cedric Laczny <cedric.laczny_at_[hidden]> a écrit :
> 
> De: Cedric Laczny <cedric.laczny_at_[hidden]>
> Objet: Re: [Boost-users] (no subject)
> À: boost-users_at_[hidden]
> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users