- Boost-users - lists.boost.org

Re: [Boost-users] Visitor makes Dijkstra slow
by Cromwell Enage 14 May '04

14 May '04

Hello, Martin! Graphs are supposed to be passed by reference to visitor functions. Your program didn't do that, so it created tons of temporary graph copies. Changing template<typename V, typename G> void operator()(V v, G g) { ++dummy; } to template<typename V, typename G> void operator()(V v, G& g) { ++dummy; } and template<typename V, typename G> void examine_vertex(V v, G g) { ++dummy; } to template<typename V, typename G> void examine_vertex(V v, G& g) { ++dummy; } should reduce your running times about 500-fold, down to the expected running times. HTH Cromwell Enage __________________________________ Do you Yahoo!? Yahoo! Movies - Buy advance tickets for 'Shrek 2' http://movies.yahoo.com/showtimes/movie?mid=1808405861

1 0

BGL: why is the prim algorithm only useable for undirected graphs?
by boost＠spyderworks.de 13 May '04

13 May '04

Hi all, in the documentation of prim_minimum_spanning_tree is mentioned "... solving the minimum spanning tree problem for an undirected graph with weighted edges ...". In my application I use this graph type (the graph type is bidirectionalS => not directed): typedef adjacency_list<vecS,vecS,bidirectionalS,no_property,property<edge_weight_t,int> > BGraph; This type modells the VertexListGraph and IncidenceGraph concepts, which are required by the prim function. If I call the prim_minimum_spanning_tree, I get reasonalble results. In literature, I can only find usage of Prims algorithm for undirected graphs, too. But I can see no reason, why it shouldn't work for directed graphs. Can you tell me more? Best regards Stefan Rauch

3 2

Visitor makes Dijkstra slow
by Martin von Gagern 13 May '04

13 May '04

Hello. I compiled the attached program on my system: boost-1.31.0 g++ (GCC) 3.3.2 20031218 (Gentoo Linux 3.3.2-r5, propolice-3.3-7) CXXFLAGS="-O3" Linux 2.6.5 #1 SMP i686 Pentium III (Coppermine) GenuineIntel GNU/Linux I get the following timings: Without any visitor: 10000 With dijkstra visitor: 7450000 With event visitor: 7430000 I cannot understand this difference, for the visitor is doing almost no work at all. Can you explain why using a visitor slows things down so much? Did I do anything wrong? Greetings, Martin von Gagern

1 0

Shared_Ptr problem with 1.30.2 and gcc 3.2.3
by Joshua Little 13 May '04

13 May '04

I've been using shared_ptr's for a while now with gcc 3.1 and recently had to upgrade to gcc 3.2.3. Ever since then I'm getting strange crashes when shared_ptr's are destructed. Heres a backtrace : Program received signal SIGSEGV, Segmentation fault. 0x77f967bf in ?? () (gdb) bt #0 0x77f967bf in ?? () #1 0x77fb5c15 in ?? () #2 0x77fa6afc in ?? () #3 0x77fccc55 in ?? () #4 0x78001e00 in _libmsvcrt_a_iname () #5 0x0050f4f5 in operator delete(void*) () #6 0x00541cc4 in boost::detail::sp_counted_base_impl<BeamWeaponXMLLoader*, boost::checked_deleter<BeamWeaponXMLLoader> >::~sp_counted_base_impl() ( this=0x1899aa0) at e:/MinGW/include/c++/3.2.3/iostream:63 #7 0x0053fada in boost::detail::sp_counted_base::destruct() (this=0x1899aa0) at e:/boost-1.30.2/boost/detail/shared_count.hpp:113 #8 0x0053f996 in boost::detail::sp_counted_base::weak_release() ( this=0x1899aa0) at e:/boost-1.30.2/boost/detail/shared_count.hpp:168 #9 0x0053fab4 in boost::detail::sp_counted_base::release() (this=0x1899aa0) at e:/boost-1.30.2/boost/detail/shared_count.hpp:144 #10 0x0053f913 in boost::detail::shared_count::~shared_count() (this=0x1899154) at e:/boost-1.30.2/boost/detail/shared_count.hpp:376 #11 0x005393e5 in boost::shared_ptr<BeamWeaponXMLLoader>::~shared_ptr() ( this=0x1899150) at src/loaders/HullXMLLoader.cpp:19 #12 0x0043489a in HullXMLLoader::~HullXMLLoader() (this=0x1899100) at src/loaders/HullXMLLoader.cpp:32 #13 0x0053b5ba in void boost::checked_delete<HullXMLLoader>(HullXMLLoader*) ( x=0x1899100) at e:/boost-1.30.2/boost/checked_delete.hpp:34 #14 0x0055b43d in boost::checked_deleter<HullXMLLoader>::operator()(HullXMLLoader*) const (this=0x1899d08, x=0x1899100) at e:/boost-1.30.2/boost/checked_delete.hpp:52 #15 0x00540b8b in boost::detail::sp_counted_base_impl<HullXMLLoader*, boost::checked_deleter<HullXMLLoader> >::dispose() (this=0x1899cf8) at e:/boost-1.30.2/boost/detail/shared_count.hpp:262 #16 0x0053faa6 in boost::detail::sp_counted_base::release() (this=0x1899cf8) at e:/boost-1.30.2/boost/detail/shared_count.hpp:143 #17 0x0053f913 in boost::detail::shared_count::~shared_count() (this=0x18990e4) at e:/boost-1.30.2/boost/detail/shared_count.hpp:376 #18 0x00536f09 in boost::shared_ptr<HullXMLLoader>::~shared_ptr() ( this=0x18990e0) at src/loaders/StarShipXMLLoader.cpp:13 #19 0x00432ba8 in StarShipXMLLoader::~StarShipXMLLoader() (this=0x18990c8) at src/loaders/StarShipXMLLoader.cpp:23 #20 0x00523926 in void baleet<StarShipXMLLoader>(StarShipXMLLoader*) ( x=0x18990c8) at src/Deleters.hpp:36 #21 0x0055d119 in baleeter<StarShipXMLLoader>::operator()(StarShipXMLLoader*) const (this=0x1899d40, x=0x18990c8) at src/Deleters.hpp:48 #22 0x0054170f in boost::detail::sp_counted_base_impl<StarShipXMLLoader*, baleeter<StarShipXMLLoader> >::dispose() (this=0x1899d30) at e:/boost-1.30.2/boost/detail/shared_count.hpp:262 #23 0x0053faa6 in boost::detail::sp_counted_base::release() (this=0x1899d30) at e:/boost-1.30.2/boost/detail/shared_count.hpp:143 #24 0x0053f913 in boost::detail::shared_count::~shared_count() (this=0x22fd14) at e:/boost-1.30.2/boost/detail/shared_count.hpp:376 #25 0x00538b1d in boost::shared_ptr<StarShipXMLLoader>::~shared_ptr() ( this=0x22fd10) at src/Player.cpp:76 #26 0x0040cd8f in Player::Player(EngineManager*, GameManager*) ( this=0x1898cd8, NewEngine=0x17d7a20, NewGameManager=0x1852ec8) at src/Player.cpp:96 #27 0x00407e4e in GameManager::Initialise() (this=0x1852ec8) at src/GameManager.cpp:125 #28 0x0040398a in main (argc=1, argv=0x17924f8) at src/ZeroSpace.cpp:32 I am constructing the shared_ptr's in a normal way : HullLoader.reset(new HullXMLLoader()); for instance. It seems to segfault when delete is called either with the default deleter or with one of my own. This was working fine when using gcc 3.1, do I need to upgrade my boost or use some compile flag? Any help would be greatfully appriciated, Joshua.

1 0

boost regex support for 64-bit
by itay 12 May '04

12 May '04

does boost regex support 64-bit for SunOS 5.8, HP-UX 11i (native compilers), WIN (MSVC-6) ? we are using an old(?) version - regexpp version 3.12. Is it recommended to upgrade to the latest version ? Is it essential to upgrade to the latest version with relevance to 64-bit compilation ? thanks, Itay

2 1

BGL: record tree-edges of MST during prim_minimum_spanning_tree
by boost＠spyderworks.de 12 May '04

12 May '04

Hi, I'm looking for a possibility to record the tree edges in the minimum spanning tree (like the result of kruskal_minimum_spanning_tree). But unfortenuatley I depend on using the prim_minimum_spanning_tree function, because the root of the tree has to be defined. My first idea was, to use a dijkstra visitor and do something with the edge_relaxed respectivley edge_not_relaxed events, but this doesn't work, because these events doesn't give me an unique edge state. Maybe anyone has another hint? best regards Stefan Rauch

1 0

AW: [Boost-users] BGL: using an edge_descriptor as key in a map
by boost＠spyderworks.de 12 May '04

12 May '04

Hi Doug, [...] > > I intend to write a visitor class which sets a boolean to each edge, and > > therefore I need the edge as key. > > Common ways to do this include using internal properties and maintaining your > own edge_index (internal) property so that you can build property maps out of > vectors. [...] I don't know, if I understand correctly? Would I request the edges' index in the callback member function of the visitor and use this as index to a vector? Maybe you can give me an example? I'm pretty new to boost. Thanks Stefan Rauch

1 0

Re: Boostifying GluCat
by Paul C. Leopardi 11 May '04

11 May '04

Hi all, Back in January last year, I asked if there was any documentation which could help me to Boostify GluCat: http://lists.boost.org/MailArchives/boost-users/msg02787.php Since then I have been very busy, but in the next few months I may be able to find the time to get this done right, so I'm asking again: GluCat is a new numeric template class library, hopefully destined for promotion to Boost. I would like to know where there is some documentation on how to: 1. Add concepts. Is there such a thing as a non-commutative multiplication concept? How do I check concepts? 2. Add numeric limits. Limits of U<T> would default to limits of T. 3. Add numeric promotion_traits. What are promotion_traits ? There is a discussion on ublas-dev mailing list about promotion_traits within uBLAS. 4. Add numeric type_traits. Also, is there a set of documented procedures which explain what is required for a library to be included in Boost? GluCat uses uBLAS. Should I take these questions to ublas-dev? Thanks

1 0

Re: is_sequence
by Rozental, Gennadiy 11 May '04

11 May '04

> It already works. If you want to detect STL sequence-ness, you'll > have to try some nasty hacks. I'm have doubts about whether it's even > possible to approximate that metafunction in portable code. Wouldn't something about these lines work? template<typename T> char test( T const&, long ); template<typename T> int test( std::list<T> const&, int ); template<typename T> struct is_list { static T t; enum { value = sizeof( test( t, 0 ) ) == 4; } }; Gennadiy.

2 1

[BGL] graph constness and vertex/edge iterators
by Cyrille Damez 11 May '04

11 May '04

Hi all, I'm currently trying to write a wrapper in order to use the BGL algorithms and visitors on a home-made graph class. If I'm not mistaken, this requires me to write (amongst other things) a couple functions that will return iterators over my graph edges and vertices, eg: std::pair<graph_traits<MyGraph>::out_edge_iterator, graph_traits<MyGraph>::out_edge_iterator > out_edges(graph_traits<MyGraph>::vertex_descriptor u, const MyGraph& g) and similarly in_edges(...) , vertices(...) and edges(...) functions. However, it seems that this function profile forces me to do a const_cast on g when implementing the function body since the out_edge_iterators are not const iterators, though they point to internal elements of g. I had a look at the example given in the documentation (dealing with converting LEDA graphs to the BGL), but I didn't see anything helping me on this particular issue (also, the example in the doc is a bit outdated since it uses the deprecated Boost iterator adaptors). Am I forced to rely on const_cast in these functions, or is there a way to declare my graph edges, vertices and the corresponding iterators as const in my graph_traits class ? I'm a newbie with the BGL, and more generally with this whole traits/template specialization style of programming, so please excuse me if I overlooked something obvious. Cheers.

3 4