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

Re: [Boost-users] graph: Min Spanning Tree (advanced start)
by Jeremy Siek 13 Nov '03

13 Nov '03

Hi Matthew, Yes, that is, as long as that initial list of edges forms a tree. Here's my guess as how to do it for prim's minimum spanning tree. You'll have to directly call breadth_first_visit, redoing all the initialization work done in dijkstra and prim (prim calls dijkstra, which then calls bfs). You'll need to initialize the predecessor map to reflect the starting tree, and also you'll want to set the color of the nodes in the starting tree to black. Then you'll have to color the nodes adjacent to nodes in the tree (that aren't in the tree) gray and stick them in the priority queue... that is, all except for one of the nodes adjacent to the tree (pick an arbitrary one). That node will be your starting node for the bfs. In you're using Kruskal's it is a different story... I'll look at that later if you need it. Cheers, Jeremy On Wednesday, November 12, 2003, at 11:24 AM, Matthew Galati wrote: > Is there a way to give an advanced start to solve Min Spanning Tree > using boost/graph? That is, I have a list of edges in my graph that > must be in the Min Spanning Tree (i.e., their cost is -M, for very big > M). > > Since algorithms for MST are greedy, I assume this can be done - but > is their an easy way to interface to boost/graph's MST algorithms? > > Thanks for any help. > Matt > > -- > Matthew Galati > ISE Lehigh University > IBM Service Parts Solutions > 610.758.4042 (Office) > 610.882.0779 (Home) > magh(a)lehigh.edu, magal11(a)us.ibm.com > http://sagan.ie.lehigh.edu/mgalati/ > > _______________________________________________ > Boost-users mailing list > Boost-users(a)lists.boost.org > http://lists.boost.org/mailman/listinfo.cgi/boost-users

1 0

boost::shared_ptr inside std::list
by James Mastro 13 Nov '03

13 Nov '03

This one has been driving me nuts all day. In a function I have the following: std::list< boost::shared_ptr<MyObject> > * objectList; When debugging my code, the debugger (gdb) dies upon entering the function with this in it. It says "The Debugger has exited due to signal 11 (SIGSEGV).The Debugger has exited due to signal 11 (SIGSEGV)." My dev tools felt the need to say it twice for some reason. I pulled this out and put it in a new project all by itself with the same result. If I make it not be a pointer, like this: std::list< boost::shared_ptr<MyObject> > objectList; then there's no problem. Oddly, both versions of the code work fine when run normally (not being debugged.) I don't see what's wrong with the first version. Is it OK to put boost shared ptrs in a std::list? Is there something else I'm missing? Or is my dev environment just having problems? -jim

1 0

Re:[Boost-users] graph: Min Spanning Tree (advanced start)
by rlyon＠comgroup.net.au 12 Nov '03

12 Nov '03

It's no longer necessarily a minimum spanning tree. The exact algorithm will depend upon whether your starting set of edges always is a tree. Regards ... ____________________Reply Separator____________________ Subject: [Boost-users] graph: Min Spanning Tree (advanced start) Author: Matthew Galati <magh(a)lehigh.edu> Date: 12/11/2003 11:24 AM Is there a way to give an advanced start to solve Min Spanning Tree using boost/graph? That is, I have a list of edges in my graph that must be in the Min Spanning Tree (i.e., their cost is -M, for very big M). Since algorithms for MST are greedy, I assume this can be done - but is their an easy way to interface to boost/graph's MST algorithms?

1 0

Re: [Boost-users] int64_t error
by Gilad Suberri 12 Nov '03

12 Nov '03

Thanks. It seems that I do not have the file "stdint.h", so in cstdint.hpp, int64_t is defined in the last #else section (that goes with #ifdef BOOST_HAS_STDINT_H). When operators.hpp is included before this file (cstdint.hpp,) int64_t does not get defined at all because this next statement from cstdint.hpp becomes false: # if defined(BOOST_HAS_LONG_LONG) && \ !defined(BOOST_MSVC) && !defined(__BORLANDC__) && \ (!defined(__GLIBCPP__) || defined(_GLIBCPP_USE_LONG_LONG)) && \ (defined(ULLONG_MAX) || defined(ULONG_LONG_MAX) || defined(ULONGLONG_MAX)) When the include statements are switched around int64_t gets defined. This is connected to posix_time_config.h where "boost/date_time/time_duration.hpp" is included before "boost/date_time/time_resolution_traits.hpp", which causes the above problem. I switched the two include statements and I am not running into that compiler error anymore, but I am not sure if that will cause other compiler errrors. Hope some of this made sense, let me know what you think or if I am missing anything. Thanks. Gilad ----- Original Message ----- From: "Jeff Garland" <jeff(a)crystalclearsoftware.com> To: "Boost Users mailing list" <boost-users(a)lists.boost.org> Sent: Wednesday, November 12, 2003 10:10 AM Subject: Re: [Boost-users] int64_t error > On Wed, 12 Nov 2003 08:42:08 -0500, Gilad Suberri wrote > > Hi, I am compiling my projects on Solaris, using the latest version > > of the boost date_time library. All the gregorian examples compile > > and build fine, but when I try to compile posix_time ones I get this > > error: > > > > ...error details snipped... > > The version of gcc is 3.0.2. > > I do not get this compiler error when I use gcc 2.95.3, but I needed > > to use the newer version. > > > > Any ideas? Thanks. > > I suspect that somehow you are not getting boost::int64_t defined. Although > looking at the logic in boost/config I'm not seeing why at the moment -- you > might experiment with trying to make sure boost::int64_t is defined. I won't > have a chance to look until later as I'm running out the door. Bottom line is > it should work with this compiler... > > Jeff > > > > _______________________________________________ > Boost-users mailing list > Boost-users(a)lists.boost.org > http://lists.boost.org/mailman/listinfo.cgi/boost-users

2 2

Re: [Boost-users] Re: Intoductory Boost Presentation
by Jon Kalb 12 Nov '03

12 Nov '03

On 11/12/03 12:39 AM, "David Abrahams" <dave(a)boost-consulting.com> wrote: > Jon Kalb <Kalb(a)LibertySoft.com> writes: > >> I will forward this message to him and ask if he wants to comment more >> specifically, but I'll give you one example that he found. I don't recall >> the exact number, but he found that a function call using Boost::function >> generated about 20K of code (in our development environment). I realize that >> in a day when gigabyte hard drives are a dime a dozen it seems miserly to >> worry about 20K, but that is for *one function call*. > > With optimization on? Apparently not. It isn't so bad in the ship build and the hit is not in the invocation, but in the construction. > I find that _very_ hard to swallow, as I have > some idea what's involved under the hood of Boost.Function. Unless, > of course, the size was really going into the function object being > wrapped by Boost.Function... if you're just wrapping (member) > function pointers Boost.Function should generate very little extra > code. Can you have your coworker post an example which demonstrates? He has already posted to this list saying: On 11/11/03 11:25 AM, "Jorg Brown" <jorg(a)microsoft.com> wrote: > an enormous amount of > code (660 bytes in an optimized, no-symbols build) is generated when I > say something as simple as > > void Testbed(void) { > boost::function<void> SimpleFPtr(&Testbed); > } > -- Jon Kalb Kalb(a)LibertySoft.com

1 0

graph: Min Spanning Tree (advanced start)
by Matthew Galati 12 Nov '03

12 Nov '03

Is there a way to give an advanced start to solve Min Spanning Tree using boost/graph? That is, I have a list of edges in my graph that must be in the Min Spanning Tree (i.e., their cost is -M, for very big M). Since algorithms for MST are greedy, I assume this can be done - but is their an easy way to interface to boost/graph's MST algorithms? Thanks for any help. Matt -- Matthew Galati ISE Lehigh University IBM Service Parts Solutions 610.758.4042 (Office) 610.882.0779 (Home) magh(a)lehigh.edu, magal11(a)us.ibm.com http://sagan.ie.lehigh.edu/mgalati/

1 0

RE: [Boost-users] Intoductory Boost Presentation
by Darryl Green 12 Nov '03

12 Nov '03

> -----Original Message----- > From: Jon Kalb [mailto:Kalb@LibertySoft.com] > Sent: Wednesday, 12 November 2003 7:22 AM > To: Boost Users > Subject: Re: [Boost-users] Intoductory Boost Presentation > > > > the documentation (and the code?) deficient? That would be as useful as > > Matt's overview could be to those just getting into/considering using > > boost libs. As it stands, all that the above statement adds is FUD. > > I passed on my friend's comments without attribution because > I didn't ask > his permission and I don't think he really intended the > comments for so > large an audience. His comments were directed to our > co-workers and we know > a little about some of the research that he has done on some > of the Boost > libraries. With that audience it isn't exactly FUD. I agree - FUD is audience dependent. I am 100% serious about thinking that any addition that clarifies what the issues/pitfalls are would be valuable, while FUD definitely isn't. > > I will forward this message to him and ask if he wants to comment more > specifically, but I'll give you one example that he found. I > don't recall > the exact number, but he found that a function call using > Boost::function > generated about 20K of code (in our development environment). > I realize that > in a day when gigabyte hard drives are a dime a dozen it > seems miserly to > worry about 20K, but that is for *one function call*. I don't think he > benchmarked it to see how long it takes to execute this code, > but still I > think he has a point when he talks about code bloat. I'm sure he has a point. I only asked him to make it. I don't really want this to turn into an attack on your co-worker's reasearch - I would honestly like to see some information on these issues. We did some basic tests on the performance of boost::function before using it and found that the actual despatch overhead is very low (which was our main concern at the time) and the size of the actual function wrapper is acceptable. We have not (yet) used boost::function in a context where the allocation performance would be expected to be significant. We didn't specifically check code size, but I can safely say we don't see 20K/function call (and yes, we do care about code size - embedded system). One thing that I have found with boost is that by providing powerful concepts in its libraries it can replace a lot of bloatware libraries/frameworks in a way that reduces overall code size, even though toy benchmarks might indicate otherwise. > > I also think he has a point about discussing the performance > trade-off issue > of each library. When the STL was first introduced, it was so > revolutionary > that it was given a very skeptical reception. But most people > were won over. > The power/overhead ratio was very favorable and it looked > like compilers > would likely improve in ways that would make it even more favorable. Absolutely agreed. Some of the stl tradeoffs don't fit some systems - hence boost:array for example... > > Now we are comfortable with template libraries and are less > skeptical of new > ones. But every library has some overhead cost and has some > applications for > which it is ill-suited. We need to evaluate each library on > its own merits > and never assume that because one was accepted in Boost it > has some magic > property that means there are no performance trade-offs or that the > performance profiles of all Boost libraries are similar. Yes - maybe something like that disclaimer would be a good start in an introductory overview. It is ultimately up to the library user to eveluate these issues - nothing special about boost in that regard. > > Suppose users determine that Boost::function (I'm just > picking on this as an > example) is great for creating flexible interfaces, but > should be avoided > for any inner-loop use or where code size is at a premium. A user would have to determine that from an understanding of what a boost::function really is/does and an understanding of their application of it. In my opinion a statement similar to the above isn't a reasonable way to present usage guidelines for boost::function. If you need a generalised function interface in an inner-loop (hopefully rare) I can't see that boost::function is going to be out-performed significantly by anything else. If you are using a generalised function object interface for invoking functions where the cost of an indirection in the call is a significant part of the cost of the function (and the performance actually matters) you have a design problem. As to code size - there will always be places where code size matters, but I haven't seen a problem - maybe a system where there are a huge number of different boost::function specializations? > That doesn't make > the library worthless, in fact, adding advice about the best > situations to > use the library enhances its value. I agree - I really was asking you/your colleague to provide some information to turn the FUD into something valuable. I don't think boost::function needs any more guidelines, it is pretty well documented. The only one I'd suggest emphasising in an introductory coverage is: Carefully consider whether using boost::ref to avoid copying the target function object is necessary/desirable for performance and/or semantic reasons using boost::function. I just checked, and this is covered in Douglas Gregor's tutorial anyway. Maybe the guideline should just be RTFM..... Regards Darryl Green ########################################################################## This e-mail is for the use of the intended recipient(s) only. If you have received this e-mail in error, please notify the sender immediately and then delete it. If you are not the intended recipient, you must not use, disclose or distribute this e-mail without the author's prior permission. We have taken precautions to minimise the risk of transmitting software viruses, but we advise you to carry out your own virus checks on any attachment to this message. We cannot accept liability for any loss or damage caused by software viruses. ##########################################################################

1 0

RE: [Boost-users] Re: Intoductory Boost Presentation
by Ben Hutchings 12 Nov '03

12 Nov '03

Matt S Trentini <matt_s_trentini(a)hotmail.com> wrote: <snip> > You'll notice that I left the typedef in there. I can't find > anything in the standard (or with google) about it being illegal in > main, nor does my compiler emit any warnings. Can anyone shed some > light on this? There's nothing wrong with it. A typedef declaration is allowed wherever any other declaration is allowed, except in the condition of a 'for', 'if', 'switch' or 'while' statement. > And I've got to disagree with your friend about the correct ordering > - the expected output is 3, 1, 2 (Remember that foo_ptr gets deleted > first). I don't see any requirement on the order of destruction of sequence elements, so I think it can be either 3, 1, 2 or 3, 2, 1.

2 1

RE: [Boost-users] Intoductory Boost Presentation
by Darryl Green 11 Nov '03

11 Nov '03

Hi Jon, > -----Original Message----- > From: Jon Kalb [mailto:Kalb@LibertySoft.com] > Sent: Tuesday, 11 November 2003 11:16 AM > To: Boost Users > Subject: Re: [Boost-users] Intoductory Boost Presentation > > > On 11/9/03 8:06 PM, "Matthew S Trentini" <matt_s_trentini(a)hotmail.com> > wrote: > > > Heya Everyone, > > > > I recently gave a presentation to my work colleagues on the > wonders of the > > Boost library. [snip] > > Matt, > > I don't know if you plan to keep this updated, but here is > some feedback > from a co-worker. I have not verified his findings. > [snip] > > > > The rest of the pages have the classic boost downfall: they > > don't discuss any of the pitfalls, performance problems, or > > code bloat issues, which frankly, seem like the "crazy aunt > > in the basement" of boost. > I don't suppose your co-worker would like to enlighten us about these issues/areas with which he obviously has some expertise and considers the documentation (and the code?) deficient? That would be as useful as Matt's overview could be to those just getting into/considering using boost libs. As it stands, all that the above statement adds is FUD. Regards Darryl Green ########################################################################## This e-mail is for the use of the intended recipient(s) only. If you have received this e-mail in error, please notify the sender immediately and then delete it. If you are not the intended recipient, you must not use, disclose or distribute this e-mail without the author's prior permission. We have taken precautions to minimise the risk of transmitting software viruses, but we advise you to carry out your own virus checks on any attachment to this message. We cannot accept liability for any loss or damage caused by software viruses. ##########################################################################

3 2

Library array
by Dave 11 Nov '03

11 Nov '03

Hello all, I have recently reviewed the Boost presentation put together by Matthew and intend to present it to my peers also. It was especially welcome to see this because I've been wanting to present to my peers on Boost for awhile but haven't had the time to learn enough about the library to put a presentation together. So, something I wanted fell right in my lap! Kinda like finding a $100 bill on the street! I do have one question about the array library. In the documentation, the statement is made that the advantage array has over vector is the fact that since vectors provide the semantics of dynamic arrays, "This results in some overhead in case only arrays with static sizes are needed.". When discussing this with my peers, I'd like to present something a little more concrete to them. If I have a number of elements that is known at compile time, why, *specifically*, should I prefer boost::array to std::vector? Thanks! Dave

2 2