September 2006 - Boost-users

The fibonacci heap is behaving strange
by Magnus Ekdahl 15 Dec '06

15 Dec '06

Hi, I put in 0,1,2,3,4 into a Fibonacci heap, manipulate some and get 0,2,4,1,25 back. With the relaxed heap I get 0,2,4,1,3 back, which is as expected with my code. AFAIK this is due to a bug in the Fibonacci heap? Anyway here is code adopted from the cvs (fibonacci_heap.cpp) that reproduces the result on two different machines (intel/amd), where the programs are compiled using g++ 4.0.4. Any help in clearing out this confusing result is appreciated :) #include <iostream> #include <cstdlib> #include <vector> #include <boost/pending/Fibonacci_heap.hpp> #include <boost/pending/relaxed_heap.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/pending/indirect_cmp.hpp> using namespace std; using namespace boost; int main(int argc, char *argv[]) { typedef indirect_cmp<unsigned*,std::less<unsigned> > ICmp; unsigned current; const unsigned N=5; vector<unsigned> w(N); ICmp cmp(&w[0], std::less<unsigned>()); Fibonacci_heap<unsigned, ICmp> Q(N, cmp); //relaxed_heap<unsigned, ICmp> Q(N, cmp); Q.push(0); current=Q.top(); cout << current << " "; Q.pop(); w[1]=180428938; Q.push(1); w[2]=84693088; Q.push(2); w[3]=168169277; Q.push(3); w[4]=171463691; Q.push(4); current = Q.top(); cout << current << " "; Q.pop(); w[3]=164976049; Q.update(3); w[4]=59651664; Q.update(4); current = Q.top(); cout << current << " "; Q.pop(); w[1]=71988538; Q.update(1); w[3]=118964142; Q.update(3); current = Q.top(); cout << current << " "; Q.pop(); w[3]=42423833; Q.update(3); current = Q.top(); cout << current << " "; Q.pop(); return EXIT_SUCCESS; }

4 5

[BGL] how to actually search with DFS/BFS?
by martin f krafft 22 Nov '06

22 Nov '06

This may seem like a silly question, but how does one actually search with DFS or BFS? Say I want to find the first node for which a predicate returns true in a BFS traversal starting at node N... The function signatures don't have a parameter for "criteria" or "predicate", so I guess it's up for a Visitor to implement such a check. What is not clear to me is how the visitor functions can break out of the search once a condition is true. Thanks, -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus(a)madduck.net "information superhighway" is just an anagram for "i'm on a huge wispy rhino fart".

9 12

Serialization problem on 64-bit Windows release
by Sigurd Saue 31 Oct '06

31 Oct '06

We've started to use boost serialization and I've run into problems with serialization of derived classes. The "funny" thing is that this happens only on 64-bit Windows release compiled with MS Visual 2005. The same code works fine on Linux 32/64 bit debug/release, on Windows 32-bit debug/release and on Windows 64-bit debug. But not Windows 64-bit release. We use boost version 1.33.1. Here's the code that causes problems (Parameter is the base class, ParamCollection is a vector of Parameters): template<class Archive> static void serialize(Archive & ar, ParamCollection & col, const unsigned int /*version*/) { ar.register_type(static_cast<FloatParameter*>(NULL)); ar.register_type(static_cast<IntParameter*>(NULL)); ar.register_type(static_cast<ChoiceParameter*>(NULL)); ar.register_type(static_cast<StringParameter*>(NULL)); ar.register_type(static_cast<BlobParameter*>(NULL)); ar & boost::serialization::base_object<std::vector<Parameter*> >(col); } When serializing the ParamCollection (serializing, not deserializing) an archive exception is thrown: unregistered class. I've tried to use both abstract and non-abstract base class without any success. I did some research in the boost code and found that the exception was thrown in polymorphic::save (oserializer.hpp) by the last condition (NULL == bpos_ptr). Any clues? Is there a workaround? Thanks, Sigurd

3 4

Boost string allocator
by Thompson, Ian 05 Oct '06

05 Oct '06

Hello, I have recently used the fast_pool_allocator as the allocator for std::map with excellent results wrt performance. My application also uses a lot of strings (basic_string) and I was seeking some advice on changing the basic_string allocator to a "boost allocator" . Can anyone offer some advice in this regard? Thanks in advance, Ian Commonwealth Bank Ian Thompson Developer Risk Systems Project Global Markets Risk Management ************** IMPORTANT MESSAGE ************** This e-mail message is intended only for the addressee(s) and contains information which may be confidential. If you are not the intended recipient please advise the sender by return email, do not use or disclose the contents, and delete the message and any attachments from your system. Unless specifically indicated, this email does not constitute formal advice or commitment by the sender or the Commonwealth Bank of Australia (ABN 48 123 123 124) or its subsidiaries. We can be contacted through our web site: commbank.com.au. If you no longer wish to receive commercial electronic messages from us, please reply to this e-mail by typing Unsubscribe in the subject line. ***************************************************************

2 1

[Boost][1_33_1] Assertion during build stage: Solaris 10
by Prashant Thakre 04 Oct '06

04 Oct '06

Hi, I have encountered following error during the build process for [Boost].[1_33_1] on Solaris 10. bjam install "-sTOOLS=sunpro" "-sBUILD=release <runtime-link>dynamic/static <threading>multi" --without-python Jamfile sunpro-C++-action /export/home/user/tmp/bin/boost/libs/regex/build/ libboost_regex.so/sunpro/release/cregex.o Assertion: (../lnk/init.cc, line 1032) while processing /db2/sunstudio11/SUNWspro/prod/include/CC/Cstd/rw/collate.cc at l ine 0. ...failed sunpro-C++-action /export/home/user/tmp/bin/boost/libs/regex/build/ libboost_regex.so/sunpro/release/cregex.o... CC: Sun C++ 5.8 2005/10/13 SunOS <hostname> 5.10 Generic_118833-03 sun4u sparc SUNW,Sun-Fire-280R Thanks. regards, Prashant Thakre

3 3

[BGL] Boost poor performance (against LEDA)
by Leandro Melo 03 Oct '06

03 Oct '06

Hi! I'm making some performance tests (nothing too fancy) between LEDA and Boost graphs. I'm not testing algorithms, but some basic adjacency list operations (add_vertex, add_edge, remove_vertex and remove_edge). I will not post the whole code I used here, but if anyone is interested, I can send the files. It's very surprising (taking into account the Boost claims to be a high performance library) that LEDA did better in all tests I made. Actually, in most tests LEDA was more than one order of magnitude better than Boost. For example: I generated a random (self-loops and parallel edges) directed graph with 10000 vertices and 20000 edges. The generation time for LEDA was 0.025 seconds in average and the generation time for Boost was 0.500 seconds in the average. I know the template arguments I parameterized the adjacency list are important. In this case I used the following definition (I also switched the listS for vecS, but the results were pretty much the same): typedef adjacency_list<listS, listS, directedS> Graph; I also tested remove_edge and remove_vertex operations with various template parameters. But in all situations LEDA did better than Boost. In some cases, LEDA did much better (more that one oder of magnitude again). The reason of this post is not to start some kind of arguments here (LEDA X Bosst), but to try to clarify some questions. Naturally, I'd be convenient if someone has already done such things I just did (actually, this is what I'm looking for). Anyway, I'm trying to find out: - Has anyone come up with results similar to mine's. In other words, if anyone has tested LEDA against Boost. Has LEDA done better (like in my case)? If so, how better? - Does anyone happen to know some reasons that make LEDA so efficient (assuming my results are correct in a general way)? And it's not even made using generic programming techniques (which provide some optimizations at compile time). - I made tests with versions 4.1 and 5.0 of LEDA. I believe that when the GGCL ('old' Boost) was released, LEDA was in a version close to 4. And even in LEDA's 4.1 version, the results were pretty much the same (better than Boost). However, the Boost Graph Library book presents Boost as a flexible and high performace library as 'better options' than LEDA (among others like GTL and Stanford Graph). I agree with the 'flexible' part of the statement, but according to my results that 'high performance' part is not realistic. One important thing to note is the following. As I mentioned, I did switch some template parameters of the adjacency list (basically, the edges and vertices container for both directed and undirected graphs). However, the tests I'm working on are supposed to be tests for general situations in which you might have remove_edges, remove_vertices and even other operations. Thus, it'd be more realistic to use Boost's adjacency list with template arguments that together represent the 'best' or a 'good' relationship between 'cost and benefit'. Because I'm trying to simulate a situation in which I'd need all operations with the same 'importance' (add_vertex, add_edge, remove_vertex, remove_edge, etc). Well, I'd appreciate if anyone could comment on this post. Thank you for reading. Bellow are the some of the functions I used (assume Graph is defined and all_vertices and all_edges are vectors of defined vertex and edge descriptors). void generate_random_graph(Graph& g) { for (int i = 0; i < num_v; i++) all_vertices[i] = add_vertex(g); for (int i = 0; i < num_e; i++) { vertex_desc s = all_vertices[rand() % num_v]; vertex_desc t = all_vertices[rand() % num_v]; all_edges[i] = add_edge(s, t, g).first; } } void remove_edges(Graph& g) { //I didn't test the other version of remove_edge(s, t, g) because LEDA doesn't have a similar one. for (int i = 0; i < 1000; i++) { edge_desc edge = all_edges[i]; remove_edge(edge, g); } } void remove_vertices(Graph& g) { for (int i = 0; i < 1000; i++) { vertex_desc vertex = vertices[i]; clear_vertex(vertex, g); remove_vertex(vertex, g); } } -- Leandro Terra C. Melo

5 11

bug in boost::multi_index::sequenced splice (patch)
by Hubert Schmid 02 Oct '06

02 Oct '06

Hi, I guess there is a bug in boost/multi_index/sequenced_index.hpp. The following program fails to compile, because there is no matching operator== for class C. But this operator shouldn't be required for splice. #include "boost/multi_index/sequenced_index.hpp" #include "boost/multi_index_container.hpp" struct C { }; int main() { using namespace boost; using namespace boost::multi_index; typedef multi_index_container<C, indexed_by<sequenced<> > > Cs; Cs cs; cs.push_back(C()); cs.splice(cs.end(), cs, cs.begin()); // XXX: compile error } The following program compiles, but both assertions fail at runtime: #include "boost/multi_index/sequenced_index.hpp" #include "boost/multi_index_container.hpp" int main() { using namespace boost; using namespace boost::multi_index; typedef multi_index_container<int, indexed_by<sequenced<> > > ints; ints foo; foo.push_back(42); ints bar; bar.push_back(42); foo.splice(foo.end(), bar, bar.begin()); assert(foo.size() == 2); assert(bar.size() == 0); } I have made both tests with the boost library in Debian/unstable (version 1.33.1-7). I have also compared the source file sequenced_index.hpp with the CVS-MAIN version (1.12). I guess the following patch should fix this bug: --- sequenced_index.hpp.orig 2006-09-29 11:38:06.000000000 +0200 +++ sequenced_index.hpp 2006-09-29 11:39:43.000000000 +0200 @@ -355,7 +355,7 @@ BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x); BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; - if(x==*this){ + if(&x==this){ if(position!=i)relink(position.get_node(),i.get_node()); } else{ @@ -388,7 +388,7 @@ BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x); BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; - if(x==*this){ + if(&x==this){ BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last); if(position!=last)relink( position.get_node(),first.get_node(),last.get_node()); regards, Hubert

5 5

[date_time] Stricter stream input validation
by Johan Nilsson 02 Oct '06

02 Oct '06

Hi, is there any way to force ptime stream input fail when the time duration part is not between 00:00:00 and 23:59:59? I'm using a time_input_facet with a formatting string of "%Y-%m-%d %H:%M:%S" imbued into a streams with exceptions(failbit) enabled. I'd like an exception raised when time parts such as 25:00:00 are parsed instead of getting the next day's date. I guess I could use regex validation, but was hoping to have support for this in the date_time library. Currently using cvs boost (RC_1_34_0). Thanks / Johan

2 8

[date-time]time zone input
by Sean Huang 02 Oct '06

02 Oct '06

Jeff, Do you plan to add the time zone input support to date-time anytime soon. Specifically, I am asking for using "%q" and "%Q" on input. Thanks, Sean

2 13

Array of smart pointers to base class
by scott velasquez 02 Oct '06

02 Oct '06

Here is what I desire to have in my GUI library as it pertains to boost: 1. No raw widgt pointers. Container functions should take a reference to a base class smart pointer type rather then accepting raw pointers of the base class type. 2. Containers store an array of smart pointers of the base GUI widget type. This is needed because containers can contain many widget derived types. I'm just showing the class code that matters; Normally, you would have constructors, destructors, access label, etc. class OWidget; class ODerivedWidget : public OWidget; class OWidgetContainer : public OWidget { public: void Add( boost::shared_ptr<OWidget>& widget ) { mWidgets.pushback(widget); } std::vector<boost::shared_ptr<OWidget>> mWidgets; } int main(void) { OWidgetContainer root; // Works just fine since the types match boost::shared_ptr<OWidget> base(new OWidget()); root.Add(base); // Doesn't work since the Add() function can't convert ODerivedWidget shared pointer to OWidget shared pointer type. boost::shared_ptr<ODerivedWidget> derived(new ODerivedWidget()); root.Add( derived); } Is this even possible? I've read about boost::any and boost:variant and while that might solve my problem of storing smart pointers of differing types, it doesn't allow me to pass smart pointers of derived types. Any ideas/suggestions would be GREATLY appreciated! -scottv

6 8