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

[astar search] Computation time for large graph
by Yann-Hervé Hellouvry 09 Jan '13

09 Jan '13

Hi, I try to use the "astar-cities" example but for graph of about 10000 nodes and edges (which are weighted) in order to find the fastest path between two random nodes... and I want to do it several times. I encountered very large computation time : about 4 min to perform 100 searches. Is it supposed to be slow for large graph? My machine is not very powerful but I think I've missed something...Is there ways to optimize? Can it be a problem from the weighted edges or from the heuristic distance ? my astar_search function call is : boost::astar_search(m_g, vertexStart, heuristicDistance, boost::predecessor_map(&p[0]) .distance_map(&d[0]) .visitor(astarVisitor) ); with m_g my graph which is a: typedef boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, VertexProperties, boost::property<boost::edge_weight_t, float> > my_graph; heuristicDistance : same as the example (a simple euclidian distance) astarVisitor : same as the example any help is appreciated ! Thanks, Happy new year btw, YH

2 3

[Locale] as::ftime formatting
by Szymon Gatner 09 Jan '13

09 Jan '13

Hey, docs say: "There is a list of supported strftime flags by ICU backend:". I didn't build my boost/locale with ICU but still tried what happens when I try as::ftime("%A") an to my surprise I got correctly localized day of the week. My questions are: is it correct that it works without ICU? will it work on other machines (Win 32 bit)? What is the encoding of output string? I am seeing it correctly displayed as utf-8 but would like to know what is happening. Can I ensure utf-8 output? My test code: using namespace boost::locale; generator gen; locale loc=gen(""); std::ostringstream ostr; ostr.imbue(loc); ostr << as::datetime << as::ftime("%A") << info.time; std::String timeStr = ostr.str(); Cheers, Simon -- Szymon Gatner The Lordz Games Studio www.thelordzgamesstudio.com

2 1

boost serialization: can't deserialize pointer to abstract base class where derived classes overload load_construct_data
by Rebecca Lehman 09 Jan '13

09 Jan '13

I have some pointers to instances of an abstract base class. Some of the derived classes have no default constructors. I can serialize instances of these derived classes by overloading load_construct_data and save_construct_data, but I always get segmentation faults when I try to serialize the base class pointers. Saving works fine, and loading will correctly load the instances of the derived classes, but it segfaults before initializing the pointers. It doesn't seem to matter whether I overload the load_construct_data and save_construct_data of the base class, or how I register my classes and the base/derived relationship, or whether the pointers are ordinary pointers or boost::shared_ptrs. (The details of the segfault messages vary, but it always segfaults). Does anyone have an example of how to serialize such pointers? Here's a trivial example of what I'm trying to do: class Base { Base() {} public: virtual int Apply()=0 const; protected: friend class boost::serialization::access; template<class Archive> void serialize(Archive &ar, const unsigned int version){ } }; BOOST_ASSUME_ABSTRACT(Base); class D1 { public: D1( int der_input): der_int(der_input){} int Apply() const { return der_int; } protected: const int & der_int; friend class boost::serialization::access; template<class Archive> void serialize(Archive &ar, const unsigned int version){ ar & boost::serialization::base_object<Base>(*this); // or boost::serialization::void_cast_register<D1, Base>( // static_cast<D1 *>(NULL), // static_cast<Base *>(NULL) // ) } }; BOOST_CLASS_EXPORT_GUID(D1, "D1"); class D2 { public: D2( int der_input): der_int(der_input){} int Apply() const { return 2*der_int; } protected: const int der_int; friend class boost::serialization::access; template<class Archive> void serialize(Archive &ar, const unsigned int version){ ar & boost::serialization::base_object<base_class_of_T>(*this); // save/load class member variables } }; BOOST_CLASS_EXPORT_GUID(D1, "D1"); namespace boost { namespace serialization { template<class Archive> inline void save_construct_data( Archive & ar, const D1* t, const unsigned int file_version ){ // save data required to construct instance ar << t->der_int; } template<class Archive> inline void load_construct_data( Archive & ar, D1 * t, const unsigned int file_version ){ // retrieve data from archive required to construct new instance int attribute; ar >> attribute; // invoke inplace constructor to initialize instance of my_class ::new(t)D1(attribute); } template<class Archive> inline void save_construct_data( Archive & ar, const D2* t, const unsigned int file_version ){ // save data required to construct instance ar << t->der_int; } template<class Archive> inline void load_construct_data( Archive & ar, D2 * t, const unsigned int file_version ){ // retrieve data from archive required to construct new instance int attribute; ar >> attribute; // invoke inplace constructor to initialize instance of my_class ::new(t)D2(attribute); } }} main(){ ... ar.template register_type<D1>(); ar.template register_type<D2>(); std::vector<Base *> b; ... ar & b; }

2 2

Boost.MSM: Executable size
by RaRi 08 Jan '13

08 Jan '13

Hi all, I'm using boost.MSM for a productive embedded system. My concern is, that my compiler produces a executable size of all most 2MB for a state machine consisting of 4 sub-machine and nearly 40 transition for the complete state machine, but with no action and guard code. My compilation system is as follows: - eclipse juno - mingw 4.7.0 - Compiler settings for the release of the binary are: "-O3 -Wall -c -fmessage-length=0" Is this a good size or should I be worried about this nearly 2 MB for the release executable? I'm asking as like stated in http://www.boost.org/doc/libs/1_52_0/libs/msm/doc/HTML/ch04s02.html <http://www.boost.org/doc/libs/1_52_0/libs/msm/doc/HTML/ch04s02.html> the executable size for a good sized state machine could reach a size of almost 600kB, and my state machine is still not finished (50 % more code has to be added for further submachine...) Using the "-Os" produces a executable size which is almost 20% smaller as with the "-O3". In case I compile the state machine with the default debug level (-g) the binary is allmost 35MB big.... The compilation takes around 1m:30sec ( using the *favor_compile_time* policy)... Best regard, RaRi -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-MSM-Executable-size-tp4641132.html Sent from the Boost - Users mailing list archive at Nabble.com.

2 1

Problem with installation
by Evan Driscoll 08 Jan '13

08 Jan '13

Hi, I'm having problems with the installation procedure. I'm using the 1.53 beta. I have run the following: ./bootstrap.sh --prefix=/unsup/boost-1.53.0/beta/common --exec-prefix=/unsup/boost-1.53.0/beta/amd64_rhel6 ./b2 --prefix=/unsup/boost-1.53.0/beta/common --exec-prefix=/unsup/boost-1.53.0/beta/amd64_rhel6 -j12 ./b2 --prefix=/unsup/boost-1.53.0/beta/common --exec-prefix=/unsup/boost-1.53.0/beta/amd64_rhel6 -j12 install however it is ignoring my --exec-prefix and installing everything to /unsup/boost-1.53.0/beta/common. I actually haven't really used --exec-prefix before I think, and have just manually moved stuff around post-installation instead. But I figured I'd try to do it "right" this time and actually use the tools I've been given. :-) What am I doing wrong? [Disclaimer: I made a typo originally and ran both bootstrap.sh and b2 with both --prefix and --exec-prefix set to ..../common. I did run './b2 clean' after that though.] Evan

1 0

How to use geometry::within with a polygon that encompasses a pole
by Cameron Sabol 08 Jan '13

08 Jan '13

Hi, I'm have an issue with polygons from the geometry library using the spherical_equatorial coordinates when the polygon is meant to wrap a pole. e.g. namespace bg = boost::geometry; typedef bg::model::point < double, 2, bg::cs::spherical_equatorial<bg::degree> > LonLatPoint; bg::model::polygon < LonLatPoint> northPoleBoundary; double lon = -180; while (lon <= 180) { bg::append(northPoleBoundary, LonLatPoint(lon, 88)); lon += 5; } LonLatPoint northPole(90, 0); bool isInNorthPole = bg::within(northPole, northPoleBoundary); This code is giving me isInNorthPole == false. Am I constructing my polygon incorrectly? Is this a bug? Or is this behavior simply not implemented? Thanks for your help!

2 2

[MultiArray, Intrusive] Instantiating a multi_array of intrusive lists as a class member
by Jiri Vyskocil 08 Jan '13

08 Jan '13

Hello, I want to try Boost Intrusive list instead of std::list in a performance and memory critical part of code. I have a Domain object, which contains a boost::multi_array of cells. each cell contains a list of particles std::list<Particle>. This sample code works as expected (std::list): #include <list> #include <iostream> #include <boost/multi_array.hpp> struct Particle { unsigned number; Particle(unsigned n){ number = n; } }; typedef std::list<Particle> ParticleList; typedef boost::multi_array<ParticleList, 3> ParticleArray; class Domain { public: ParticleArray particles; Domain(int x, int y, int z) : particles(boost::extents[x][y][z]) { } }; int main(){ Domain* dom = new Domain(10,10,10); dom->particles[5][5][5].push_back(Particle(1)); std::cout << dom->particles[5][5][5].front().number << std::endl; return 0; } When I try to swap the std::list for an intrusive list, I get a compile error on Domain instantiation. Minimal code leading to the error: #include <boost/intrusive/list.hpp> #include <boost/multi_array.hpp> typedef boost::intrusive::list_base_hook<> BaseHook; struct Particle : BaseHook { unsigned number; }; typedef boost::intrusive::list<Particle> ParticleList; typedef boost::multi_array<ParticleList, 3> ParticleArray; class Domain { public: ParticleArray particles; Domain(int x, int y, int z) : particles(boost::extents[x][y][z]) { } }; int main(){ Domain* dom = new Domain(10,10,10); return 0; } When I try to compile the above code, gcc tells me: In file included from /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_tempbuf.h:61:0, from /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_algo.h:64, from /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/algorithm:63, from /usr/include/boost/move/move.hpp:37, from /usr/include/boost/intrusive/detail/has_member_function_callable_with.hpp:22, from /usr/include/boost/intrusive/detail/memory_util.hpp:112, from /usr/include/boost/intrusive/pointer_traits.hpp:26, from /usr/include/boost/intrusive/detail/utilities.hpp:17, from /usr/include/boost/intrusive/list_hook.hpp:19, from /usr/include/boost/intrusive/list.hpp:20, from intrusive.cc:1: /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_construct.h: In function ‘void std::_Construct(_T1*, const _T2&) [with _T1 = boost::intrusive::list<Particle>, _T2 = boost::intrusive::list<Particle>]’: /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_uninitialized.h:189:3: instantiated from ‘static void std::__uninitialized_fill_n<_TrivialValueType>::__uninit_fill_n(_ForwardIterator, _Size, const _Tp&) [with _ForwardIterator = boost::intrusive::list<Particle>*, _Size = long unsigned int, _Tp = boost::intrusive::list<Particle>, bool _TrivialValueType = false]’ /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_uninitialized.h:225:7: instantiated from ‘void std::uninitialized_fill_n(_ForwardIterator, _Size, const _Tp&) [with _ForwardIterator = boost::intrusive::list<Particle>*, _Size = long unsigned int, _Tp = boost::intrusive::list<Particle>]’ /usr/include/boost/multi_array.hpp:477:5: instantiated from ‘void boost::multi_array<T, NumDims, Allocator>::allocate_space() [with T = boost::intrusive::list<Particle>, long unsigned int NumDims = 3ul, Allocator = std::allocator<boost::intrusive::list<Particle> >]’ /usr/include/boost/multi_array.hpp:186:5: instantiated from ‘boost::multi_array<T, NumDims, Allocator>::multi_array(const boost::detail::multi_array::extent_gen<NumDims>&) [with T = boost::intrusive::list<Particle>, long unsigned int NumDims = 3ul, Allocator = std::allocator<boost::intrusive::list<Particle> >]’ intrusive.cc:18:49: instantiated from here /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_construct.h:84:7: error: passing ‘const boost::intrusive::list<Particle>’ as ‘this’ argument of ‘boost::intrusive::list<T, O1, O2, O3>::operator boost::rv<boost::intrusive::list<T, O1, O2, O3> >&() [with T = Particle, O1 = boost::intrusive::none, O2 = boost::intrusive::none, O3 = boost::intrusive::none]’ discards qualifiers [-fpermissive] This is just a minimal sample code to trigger an error. In the actual code, both Domain and Particle objects are more complicated. The last line of error output is sligtly different: /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_construct.h:84:7: error: no matching function for call to ‘boost::intrusive::list<Particle>::list(const boost::intrusive::list<Particle>&)’ followed by a note with a list of candidate functions. If I define the multi_array so that it contains pointers to ParticleArray, i.e.: typedef boost::multi_array<ParticleList*, 3> ParticleArray; there seems to be no benefit over the std::list approach, since I have to hold the additional pointer. In a test simulation, this variant eats about 10% more RAM, which is of concern in our situation. Any ideas how to replace std::list with boost::intrusive::list in a multi_array in a way which wouldn't consume more memory than the std::list approach? (I would want to see if it also brings the much needed performance benefit) Jiri Vyskocil

2 5

[Iterator] filter_iterator over greedy?
by Robert Jones 07 Jan '13

07 Jan '13

Hi Folks, Somewhat to my surprise this code, simply creating a filter_iterator, evaluates the predicate until an element satisfying the predicate is found. This seems wrong to me. Shouldn't evaluation of the predicate be delayed until the filter_iterator is dereferenced? Thx, Rob. #include <iostream> #include <boost/range.hpp> #include <boost/iterator/filter_iterator.hpp> bool predicate( int i ) { std::cout << "predicate(" << i << ")" << std::endl; return true; } int main( ) { int array[] = { 0, 1 }; boost::make_filter_iterator( predicate, boost::begin( array ), boost::end( array ) ); } > [Run] predicate(0) >

2 1

Using OvenToBoost 'taken'.
by Robert Jones 07 Jan '13

07 Jan '13

Hi Folks This question is about using the OvenToBoost port, not currently part of Boost, but likely to be soon, I understand. The code below evaluates the predicate for the first and second elements of the array. The evaluation of the second element seems to me to be unnecessary and wrong, since the 'taken' adaptor knows the range is ended after the first element is taken. Thoughts? Thx, Rob. #include <boost/range/adaptor/filtered.hpp> #include <boost/range/adaptor/taken.hpp> #include <boost/range/algorithm/for_each.hpp> #include <iostream> bool predicate( int i ) { std::cout << "predicate(" << i << ")" << std::endl; return true; } void doNothing( int ) { } int main( ) { int array[ ] = { 0, 1, 2, 3, 4, 5 }; for_each( array | boost::adaptors::filtered( predicate ) | boost::adaptors::taken( 1 ), doNothing ); }

2 2

[Property Tree] Complexity of find and get methods
by Elizabeta 07 Jan '13

07 Jan '13

Hi I want to know the complexity of boost property tree find and get methods. I tried the following link http://www.boost.org/doc/libs/1_41_0/doc/html/boost/property_tree/basic_ptr… but it seems that the complexity is not specified. Also can find function accept string paths or it just finds immediate childs? Thank you

2 1