March 2009 - Boost-users - lists.preview.boost.org

Re: [Boost-users] [Graph] Computing reachable vertices on a graph
by Florian.PONROY＠fr.thalesgroup.com 23 Mar '09

23 Mar '09

Hi Andrew, Thank you very much for your reply. I eventually implemented Steven Watanabe's solution, which seems easier to me. Since I only need to know which nodes are actually reachable, I may get rid of distances for now. Thanks again, Florian -----Message d'origine----- De : boost-users-bounces(a)lists.boost.org [mailto:boost-users-bounces@lists.boost.org]De la part de Andrew Sutton Envoyé : vendredi 20 mars 2009 18:35 À : boost-users(a)lists.boost.org Objet : Re: [Boost-users] [Graph] Computing reachable vertices on a graph However, I encounter the following issue : in this example, vertices are numbered from 0 to 5. However, in my project, this is not the case, vertices could be numbered 5, 38, 42, 384... Using a vector in that case might not work as expected, a map<vertex, distance> would probably be better. I'm not quite familiar with BGL so far, maybe should I deal with a specific property map? Or using a visitor to record a vertex distance upon graph discovery? I'm a little bit lost, any help will be greatly appreciated! You probably shouldn't rely on vertex indices as the canonical id of the vertex. The method of identifying vertices (and edges) in an adjacency list varies with the vertex set and edge set type selectors (indices or identifeirs for vecS aren't the same as listS). There are a couple of different approaches. The easiest would be to simply maintain a mapping of id to vertex descriptor. For example: map<int, graph_traits<Graph>::vertex_descriptor> verts; verts[5] = add_vertex(g); verts[58] = add_vertex(g); // and so on. You can couple that bundled vertex properties to get a kind of bimap. struct vertex_props { int id; } typedef adj_list<vecS, vecS, directedS, vertex_props> Graph; template <typename Graph, typename Map> void add_vertex(Graph& g, Map& verts, int id) { vertex_descriptor v = add_vertex(g); verts[id] = v; g[v].id = id; } add_vertex(g, verts, 5); add_vertex(g, verts, 58); ... cout << g[*vertices(g).begin]->id << "\n"; Hope that helps, Andrew Sutton andrew.n.sutton(a)gmail.com <mailto:andrew.n.sutton@gmail.com>

1 0

Re: [Boost-users] [Graph] Computing reachable vertices on a graph
by Florian.PONROY＠fr.thalesgroup.com 23 Mar '09

23 Mar '09

Hi Steven, I just tried your solution, which works perfectly well. The vector is actually sized to the number of reachable nodes. I just added a reachable.reserve(max_number_of_nodes) to avoid multiple reallocations. Thank you very much for your help, Florian -----Message d'origine----- De : boost-users-bounces(a)lists.boost.org [mailto:boost-users-bounces@lists.boost.org]De la part de Steven Watanabe Envoyé : vendredi 20 mars 2009 18:36 À : boost-users(a)lists.boost.org Objet : Re: [Boost-users] [Graph] Computing reachable vertices on a graph AMDG Florian.PONROY(a)fr.thalesgroup.com wrote: > I need to get the list of all reachable vertices from a given vertex in a graph. I'm currently using the BFS algorithm to achieve that, which seems to fit well to my need. > How does this work: #include <boost/graph/adjacency_list.hpp> #include <boost/graph/breadth_first_search.hpp> #include <boost/graph/visitors.hpp> #include <vector> #include <iterator> typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS > Graph; int main() { Graph G(1); boost::add_edge(0, 1, G); boost::add_edge(1, 2, G); boost::add_edge(2, 5, G); boost::add_edge(3, 2, G); boost::add_edge(4, 3, G); boost::add_edge(5, 3, G); typedef Graph::vertex_descriptor Vertex; std::vector<Vertex> reachable; // The source vertex Vertex s = *(boost::vertices(G).first); boost::breadth_first_search(G, s, boost::visitor( boost::make_bfs_visitor( boost::write_property( boost::identity_property_map(), std::back_inserter(reachable), boost::on_discover_vertex())))); } In Christ, Steven Watanabe _______________________________________________ Boost-users mailing list Boost-users(a)lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

1 0

trouble with correct type definition of multi_index::nth_index
by Sandeep Gupta 23 Mar '09

23 Mar '09

Hi, In the following code I am trying to get an handle to the index of a multi_index container. The compiler says "invalid initialization of reference of type ‘boost::multi_index::detail:..". Not sure why this is so. Since I wasn't sure about the source of error I have pasted the full code ( sans declarations) is give below. Thanks sandeep ///-------------------------Full code --------------------- template<typename Col1_t, typename Col2_t, typename Col3_t, typename Col4_t> class TupleStore { typedef tuple<Col1_t, Col2_t, Col3_t, Col4_t> tuple_t; typedef multi_index_container < tuple_t, indexed_by < ordered_unique<tuple_member_extractor<tuple_t,0> > > > tuplestore_t; tuplestore_t m_tuplestore; public: template<int n> void lookup_key(Col1_t key) const { typedef typename tuplestore_t:: template nth_index<n>::type tuplestore_index_t; ///compiler error here tuplestore_index_t& indexx = m_tuplestore.get<n>(); } }; int main() { TupleStore<int,int,int,int> tstr; tstr.lookup_key<0>(5); }

2 1

phoenix for_each and std::cout
by Sandeep Gupta 23 Mar '09

23 Mar '09

Hi, I am trying to use phoenix::for_each to print each element of iterator range. Would appreciate if any clarification as to why statements 1 and 2 are giving compile errors. Thanks sandeep //-------------code snippet int x; counting_iterator<int> first(0), last(10); iterator_range<counting_iterator<int> > ir(first, last); phoenix::for_each(ir, std::cout<<x<<' ')(); //stmt 1 ; compile error phoenix::for_each(ir, std::cout<<arg1<<' ')(); //stmt 2; compile error

2 1

Struggling to compile encfs, linking with boost library
by Jean Jordaan 22 Mar '09

22 Mar '09

Hi there I want to use encfs on a box with a Debian distro that doesn't have recent encfs and boost packages available, so I'm compiling them from source. I installed boost like this:: $ ./configure --prefix=/home/zope/local It seems to complete fine. This incantation finds the libraries, but dies shortly thereafter:: zope@iwlearn:/home/zope/src/encfs-1.5$ CPPFLAGS=-I/home/zope/local/include/boost-1_38 ./configure --with-boost-libdir=/home/zope/local/lib --prefix=/home/zope/local [...] checking for boostlib >= 1.34... yes checking whether the Boost::System library is available... yes checking for exit in -lboost_system-gcc41-mt-1_38... yes configure: WARNING: BOOST_CPPFLAGS -I/usr/include checking whether the Boost::Serialization library is available... yes checking for exit in -lboost_serialization-gcc41-mt-1_38... yes checking whether the Boost::Filesystem library is available... yes checking for exit in -lboost_filesystem-gcc41-mt-1_38... no checking for exit in -lboost_filesystem-gcc41-mt-1_38... (cached) no checking for exit in -lboost_filesystem-gcc41-mt-1_38... (cached) no checking for exit in -lboost_filesystem-gcc41-mt... no checking for exit in -lboost_filesystem-gcc41-mt... (cached) no configure: error: Could not link against boost_filesystem-gcc41-mt ! I wonder why "checking for exit" works in -lboost_serialization-gcc41-mt-1_38 and not in -lboost_filesystem-gcc41-mt-1_38 .. What does that mean, "checking for exit"? (Googling ..) -- jean . .. .... //\\\oo///\\

2 4

Boost and C++ "physical design"
by Yang Zhang 22 Mar '09

22 Mar '09

I have a couple questions about Boost and its implications for the "physical design" of C++ projects. I'm guessing there probably aren't that many non-member, non-template functions in the Boost library, but of the ones that exist, are these usually labeled `static`, since boost is mostly a header library? Is there any advice on taming (1) the generated code size and/or (2) the build times* which result from using a header-mostly library like Boost? A large C++ project consists of many translation units (.o files) which are generated from source files that include many of the same Boost headers over and over again. (2) can be ameliorated with a distributed build process, but the more general issue here is that of consumption of compute resources, be it time or machines. -- Yang Zhang http://www.mit.edu/~y_z/

7 7

[numeric::converter] finding the smallest c such that (a/c) + (b/c) < inf
by er 22 Mar '09

22 Mar '09

Hi All, template<typename T> struct promote{}; template<> struct promote<float> : mpl::identity<double>{}; template<> struct promote<double> : mpl::identity<long double>{}; template<typename T> //T: float, double struct fit_a_plus_b_to_range{ static T divider(T a, T b){ static const T mx = math::tools::max_value<T>(); static const T mi = math::tools::min_value<T>(); if(a > (mx - b)){ typedef typename promote<T>::type prom_t; typedef numeric::converter<T,prom_t> up_t; typedef numeric::converter<prom_t,T> down_t; prom_t au = up_t::convert(a); prom_t bu = up_t::convert(b); prom_t mu = up_t::convert(mx); prom_t cu = ((au/mu)+(bu/mu)); T delta = ...; T c = down_t::convert(cu) + delta; BOOST_ASSERT(!math::isinf((a/c)+(b/c))); return c; }else{ return (T)(1); } } }; With delta = 0.0 the assertion fails, with delta = 1.0 it works (for a few examples). What's the smallest delta value? Is there a better way to do this overall? If this is off topic, let me know...

2 3

Serialization of a std::vector< boost::shared_ptr< A > > throws unregistered_class exception
by Benoit Gagnon 21 Mar '09

21 Mar '09

Given the following classes: class Building { ... }; class House : public Building { ... }; class Hospital : public Building { ... }; With appropriate serialization method templates such as: class House: public Building { friend class boost::serialization::access; template<class Archive> void serialize(Archive& ar, const unsigned int version ) { ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP( Building ); ar & BOOST_SERIALIZATION_NVP( mNumBedrooms ); ar & BOOST_SERIALIZATION_NVP( mNumBathrooms ); } ... I have the following registrations in main.cpp where the archiving/ restoring is performed: BOOST_SERIALIZATION_SHARED_PTR( Building ) BOOST_SERIALIZATION_SHARED_PTR( House ) BOOST_SERIALIZATION_SHARED_PTR( Hospital ) In main.ccp, I would like to serialize a std::vector< boost::shared_ptr< Building > > object. Like this: std::vector< boost::shared_ptr< Building > > buildings; ... std::ofstream ofs( "archive.txt" ); boost::archive::text_oarchive oa( ofs ); oa & BOOST_SERIALIZATION_NVP( buildings ); This compiles correctly but fails at runtime with a "unregistered_class" exception. The individual classes (Building, House, Hospital) can be serialized and restored fine individually. That is true for objects, pointers and shared_ptr. A vector of plain pointers to any of those types also works fine. But a vector of shared_ptr to any of those types fails at runtime.. What kind of registration must be done to achieve this?

3 7

[math] log_max_value<long double>
by er 21 Mar '09

21 Mar '09

Hi All, Was this discussed before? <cmath> using namespace math::tools; typedef double RealType; log_max_value<RealType>() 709 log(max_value<RealType>()) 709.783 !math::isinf(exp(log_max_value<RealType>())) //true typedef long double RealType; log_max_value<RealType>() 11356 log(max_value<RealType>()) inf !math::isinf(exp(log_max_value<RealType>())) //false i.e. exp in cmath seems to "assume" RealType = double. i686-apple-darwin9-gcc-4.0.1

2 2

shared_ptr as reference argument
by anony 20 Mar '09

20 Mar '09

Is there some utility in passing shared_ptr's as references as here: void bla(boost::shared_ptr<T>& bla_ptr); This avoids creating of a new object and copying overhead, but is it safe? When would you recommend it and when not?

6 18