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

Re: [Boost-users] Find all the shortest path from a graph
by Harsh Deshmane 08 Dec '05

08 Dec '05

Hi Volodya, thanks for this solution [k_shortest.hpp]. It compiles and works for the files given (with minor changes - commenting out the io::<< declaration and some cout statements). However, when I use bundledProps for vectices and edges, I get compilation errors. So, for instance if the graph definition used is the following, instead of the one you have in the example k_shortest_test.cpp, then the compilation fails. struct CCRVertexProps { std::string vertex_name; // name of CCR int tmp; // could be anything }; struct CCREdgeProps { string name; // edgename int edge_weight_t; }; typedef boost::adjacency_list<vecS,vecS,bidirectionalS,CCRVertexProps, CCREdgeProps> myGraph; Do you have any recommendations (other than changing my graph definitions), to make it work with bundledProps ? I tried the simplistic changes recommended from http://www.boost.org/libs/graph/doc/bundles.html (&CCREdgeProps::edge_weight_t in the put() and get() calls), but there are still lots of errors. thanks for any help! -harsh top message of compilation errors is at the end of this mail.. >From boost archives: ------------------------------------------------------------------------------------------------------- Hi Giulio, > Hi all, > > I'd like to extract all possible shortest path from a source to a > destination... not only one path. Please, could you help me to resolve > this problem? Hi, I'm afraid BGL does not have such a algorithm at the moment. One though that comes to me is the use another algorithm (not present in BGL, either), for finding k shortest paths. You'll then be getting next shortest path until the lengths are all the same. There are several algorithms for finding k shortest paths, one being http://citeseer.ist.psu.edu/jimenez94algorithm.html My implementation can be found at http://zigzag.cs.msu.su/~ghost/k_shortest Look specifically at the k_shortest.hpp file. Of course, no warranties. This worked for me and I did test it against independent implementation, but the only way to find it it works for you is to test. - Volodya ------------------------------------------------------------------------------------------------------ ------------------------------------------begin------------------------------------------------------ k_shortest.hpp: In member function `boost::Shortest_paths_finder<G>::Path_set::heap_type* boost::Shortest_paths_finder<G>::initialize_heap(boost::graph_traits<G>::vertex_descriptor) [with G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, CCRVertexProps, CCREdgeProps, boost::no_property, boost::listS>]': k_shortest.hpp:208: instantiated from `boost::Shortest_paths_finder<G>::Path_set* boost::Shortest_paths_finder<G>::next_path_set(boost::Shortest_paths_finder<G>::Path_s et*) [with G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, CCRVertexProps, CCREdgeProps, boost::no_property, boost::listS>]' k_shortest.hpp:174: instantiated from `bool boost::Shortest_paths_finder<G>::find_alternative() [with G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirec tionalS, CCRVertexProps, CCREdgeProps, boost::no_property, boost::listS>]' k_shortest.hpp:321: instantiated from `void boost::k_shortest_f(const G&, boost::graph_traits<G>::vertex_descriptor, boost::graph_traits<G>::vertex_descriptor, int, New PathHandler) [with G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, CCRVertexProps, CCREdgeProps, boost::no_property, boost::listS>, NewPathHand ler = boost::paths_recorder<main(int, char**)::ccrGraph>]' k_shortest.hpp:352: instantiated from `void boost::k_shortest(const G&, boost::graph_traits<G>::vertex_descriptor, boost::graph_traits<G>::vertex_descriptor, int, std:: vector<std::vector<boost::graph_traits<G>::vertex_descriptor, std::allocator<boost::detail::bfs_helper(VertexListGraph&, boost::graph_traits<G>::vertex_descriptor, ColorM ap, BFSVisitor, const boost::bgl_named_params<P, T, R>&)::Traits::vertex_descriptor> >, std::allocator<std::vector<boost::graph_traits<G>::vertex_descriptor, std::allocat or<boost::detail::bfs_helper(VertexListGraph&, boost::graph_traits<G>::vertex_descriptor, ColorMap, BFSVisitor, const boost::bgl_named_params<P, T, R>&)::Traits::vertex_d escriptor> > > >&) [with G = main(int, char**)::ccrGraph]' k_shortest_test.cpp:287: instantiated from here k_shortest.hpp:191: no match for `int& + boost::detail::error_property_not_found' operator -------------------------------------------end----------------------------------- for reference, line 287: boost::k_shortest(g, *vertices(g).first, *prior(vertices(g).second),100,paths);

1 0

ANN: Data processing toolkit
by zvrba＠globalnet.hr 08 Dec '05

08 Dec '05

-----BEGIN PGP SIGNED MESSAGE----- Hash: RIPEMD160 The toolkit and the documentation can be downloaded from the following URL: http://heim.ifi.uio.no/~zvrba/ under the Resources heading. All comments are welcome. This also goes to the Spirit mailing list as the initial implementation of the toolkit was supposed to use the Phoenix-2 library. I had to give up on that idea since at the time Phoenix-2 had some serious bugs. Nevertheless, I'd like to thank Joel for his patience and support in my attempts to use Phoenix. It has by no means been a waste of time, since I do have on my agenda a port to Phoenix-2 in the future, if enough people get interested. === ABSTRACT: We have designed a C++ toolkit for sequential processing of data streams. Along with sequential processing it provides some features normally found in RDBMS, such as aggregate functions. Empirically it has been shown to be several times faster than PostgreSQL 8, although exact measurements were not performed. The main motivation for writing the toolkit was inadequacy of PostgreSQL for stateful processing of large amounts of data. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFDmFe5FtofFpCIfhMRA+9wAJ9B7XcfcVP1ogmRQcNbRJXps6Ne6wCfYibS KuBLClnwqjP2nscdge60u/0= =9yy4 -----END PGP SIGNATURE-----

1 0

SIGSEGV in pthread_mutex_lock with Boost::threads
by Shridhar Daithankar 08 Dec '05

08 Dec '05

Hello, I am writing a thread pool implementation and experiencing SIGSEGV in pthread_mutex_lock under very heavy load. The crashes are repeatable and always produce the same backtrace. Brief description: The threadpool creates the thread with default function objects on request. The default function object launch a user defined function object along with other house keeping. When done the the thread returns itself to pool of free threads(a std::vector) for further assignment. The pool also keeps a map of thread_id(pthread_t) to thread object so that it can signal termination to all of the threads, busy or not. The test has a short function object defined as struct f2 : public pyr::threadFunction { virtual void operator()(void) { int i=0; i++; } }; It assigns the thread from pool to an object of above type in very tight loop. It works will it attempts 600000 objects. Around 700000 objects it starts producing segfaults. There is no importance of either of the figure from testing point of view but the crash is certainly not what I expect. I stumbled upon http://lists.boost.org/boost-users/2005/04/11196.php but this does not seem to be the case in here. But I don't know for sure if I can trust the error checking method I have used. Any help would be greatly appreciated. Regards, Shridhar Following are the details. Platform: Slackware Linux 10.2, Kernel 2.6.13, GCC 3.3.6, NPTL thread library, part of glibc-2.3.5. The backtrace #0 0xb7c9f1f4 in pthread_mutex_lock () from /lib/tls/libpthread.so.0 #1 0xb7d76b2f in pthread_mutex_lock () from /lib/tls/libc.so.6 #2 0xb7ed647e in boost::mutex::do_lock () from /usr/local/lib/libboost_thread-gcc-mt-1_33.so.1.33.0 #3 0xb7efbaa1 in pyr::threadPool::returnThreadToPool () from /home/shridhar/source/shlib/libutils.1.so #4 0xb7ef9732 in pyr::threadState::threadRunDone () from /home/shridhar/source/shlib/libutils.1.so #5 0xb7ef9a6f in pyr::threadWorker::operator() () from /home/shridhar/source/shlib/libutils.1.so #6 0xb7efc96c in boost::detail::function::void_function_obj_invoker0<pyr::threadWorker, void>::invoke () from /home/shridhar/source/shlib/libutils.1.so #7 0xb7edebfa in boost::function0<void, std::allocator<boost::function_base> >::operator() () from /usr/local/lib/libboost_thread-gcc-mt-1_33.so.1.33.0 #8 0xb7ede81f in boost::thread_group::size () from /usr/local/lib/libboost_thread-gcc-mt-1_33.so.1.33.0 #9 0xb7c9d0fb in start_thread () from /lib/tls/libpthread.so.0 #10 0xb7d6a99e in clone () from /lib/tls/libc.so.6 The source function void pyr::threadPool::returnThreadToPool(const tid id) { //Lock the pool so that nobody else can modify it. std::cout << pyr::tid() << " " << "The earth" << std::endl; boost::mutex::scoped_lock lock(poolmutex); std::cout << pyr::tid() << " " << "The stone" << std::endl; pyr::threadptr p = allthreads[id]; std::cout << pyr::tid() << " " << "The carving" << std::endl; pool.push_back(p); std::cout << pyr::tid() << " " << "The step" << std::endl; } The error checking script: #!/bin/bash a=`grep "The earth" log.err |wc -l` b=`grep "The stone" log.err |wc -l` c=`grep "The carving" log.err |wc -l` d=`grep "The step" log.err |wc -l` echo "$a $b $c $d" The results: shridhar@ps0499: $ testprograms/threadpool >log.err 2>&1;error.sh Segmentation fault 67420 67419 67419 67419 shridhar@ps0499: $ testprograms/threadpool >log.err 2>&1;error.sh Segmentation fault 55222 55221 55221 55221 shridhar@ps0499: $ testprograms/threadpool >log.err 2>&1;error.sh Segmentation fault 55702 55701 55701 55701 shridhar@ps0499: $ testprograms/threadpool >log.err 2>&1;error.sh Segmentation fault 123284 123250 123250 123250 shridhar@ps0499: $ testprograms/threadpool >log.err 2>&1;error.sh Segmentation fault 54965 54963 54963 54963 shridhar@ps0499: $ testprograms/threadpool >log.err 2>&1;error.sh Segmentation fault 122436 122419 122419 122419 shridhar@ps0499: $ testprograms/threadpool >log.err 2>&1;error.sh Segmentation fault 57508 57507 57507 57507

1 0

newbie problems with installing boost for vc 7.1
by Piotr Obrzut 08 Dec '05

08 Dec '05

hi, I know related questions was asked before, but I think my situatuation is special: My visual studio instalation is devided on 2 partitions. That's why I think runing vsvars32.bat might not be enough before installing boost (after runing it, boost instalator didn't found my vc7 files). First it was problems with cl.exe (fixed by changing PATH), but later I recieved this message: D:\programowanie\boost_1_33_1>bjam "-sTOOLS=vc-7_1" install ****************************************************** Building Boost.Iostreams with bzip2 support disabled. To enable bzip2, consult the Boost.Iostreams documentation ****************************************************** ****************************************************** Building Boost.Iostreams with zlib and gzip support disabled. To enable zlib and gzip, consult the Boost.Iostreams documentation ****************************************************** Building Boost.Regex with the optional Unicode/ICU support disabled. Please refer to the Boost.Regex documentation for more information (and if you don't know what ICU is then you probably don't need it). ...found 13709 targets... ...updating 1480 targets... vc-C++ bin\boost\libs\date_time\build\boost_date_time.dll\vc-7_1\debug\threading -multi\greg_month.obj spawn: No such file or directory and now I don't know what to do, any ideas? -- greetings, Piotr Obrzut mailto:piotr_obrzut@o2.pl

2 2

Re: [Boost-users] [program_options] how to use case_insensitive
by Merrill Cornish 08 Dec '05

08 Dec '05

Volodya, When someone asked about case insensitive program options, you responsed: >>> it's a regression from 1.32. I'll see if I can fix this quickly. Has this been fixed in 1.33.1? Merrill

2 1

[Build] boost.jam usage examples
by Chris Morley 08 Dec '05

08 Dec '05

Hi, I'm after some more bjam project examples. Have been looking at the ones in the example directory, and wouldn't mind some more just to drill the usage into my head. I'm looking to use this for building our inhouse libaries, seems pretty sweet. Thanks in advance, Chris

2 1

iteration from pure abstract classes
by Hugh Hoover 08 Dec '05

08 Dec '05

I have a need to provide STL compliant iterators from an abstract class A, that is, without knowing the runtime type of the actual "collection" being iterated.. As near as I can tell, these things don't mix well. My best so far is to create an abstract "iterator_assister" which provides dereference, (in|de)crement and is_equal, and use a boost::iterator_adaptor derived class to provide the iterator the client code uses, and allocate the iterator_assister derived class from the implementation class (derived from A) that's being iterated over. This solution has obvious downsides. I can't imagine that this is a unique problem. Certainly, people significantly smarter than me have figured out a good solution to this? In my reading and browsing, though, I've never seen the problem presented, never mind solved. In my early C++ days, we used allocated iterators rather than the current STL style. Can anyone provide pointers to what I SHOULD be reading for a good solution? I believe I NEED to use abstract classes here rather than meta- programming with known types at runtime - the client code will need to iterate over classes loaded from dynamic libraries that are not known to the client code (except by abstract interface). Thanks Hugh Hoover Enumclaw Software

4 8

Re: [Boost-users] Intel Compiler on Windows with stlport
by Marco Azimonti 08 Dec '05

08 Dec '05

Rene Rivera wrote: >To me the "stlpd_std" mention says that it's trying to build with >STLport. Could you provide some details as to how you are configuring >and the bjam commands you are using? Possibly more of the bjam output, >like the compile commands. (removing Python, zlib, etc.)The bjam command is as follows... /////////////////////////////////////////// bjam "-sBUILD=debug release <runtime-link>static/dynamic <threading>single/multi" "-sTOOLS=intel-win32" "-d+2" "-sINTEL_PATH=C:\Program Files\intel\Compiler\C++\9.0\IA32" "-sINTEL_BASE_MSVC_TOOLSET=vc-7_1-stlport" "--prefix=D:\Dlls\boost-1_33_1\VS_2003_Intel" -"sSTLPORT_PATH=K:\coding\src" "-sSTLPORT_VERSION=5.0" install /////////////////////////////////////////// Once is starting compiling, the compiler execute... /////////////////////////////////////////// bin\boost\libs\date_time\build\boost_date_time.dll\intel-win32\debug\threading-multi\greg_month.obj CALL "C:\Program Files\intel\Compiler\C++\9.0\IA32\bin\ICLVARS.BAT" > nul "C:\Program Files\intel\Compiler\C++\9.0\IA32\bin\icl" /Zm800 -nologo /EHsc -c -DBOOST_ALL_DYN_LINK=1 -DUSE_DATE_TIME_PRE_1_33_FACET_IO -D_STLP_DEBUG=1 -D_STLP_DEBUG_UNINITIALIZED=1 -D_STLP_USE_DYNAMIC_LIB=1 /Z7 /Od /Ob0 /EHsc /GR /MDd /Op /wd4675 /Zc:forScope /Qwn5 /Qwd985 /Qwe556 -Qoption,c,--arg_dep_lookup /Qansi_alias /Qvc7.1 /Zc:wchar_t -D_NATIVE_WCHAR_T_DEFINED -I"bin\boost\libs\date_time\build" -I"K:\coding\src\STLport-5.0\stlport" -I"K:\coding\src\boost_1_33_1" -Fo"bin\boost\libs\date_time\build\boost_date_time.dll\intel-win32\debug\threading-multi\greg_month.obj" -Tp"K:\coding\src\boost_1_33_1\libs\date_time\build\../src/gregorian/greg_month.cpp" greg_month.cpp K:\coding\src\boost_1_33_1/boost/detail/sp_counted_base_w32.hpp(68): error: namespace "stlpd_std" has no member "type_info" virtual void * get_deleter( std::type_info const & ti ) = 0; ^ K:\coding\src\boost_1_33_1/boost/detail/sp_counted_impl.hpp(79): error: namespace "stlpd_std" has no member "type_info" virtual void * get_deleter( std::type_info const & ) /////////////////////////////////////////// I added in cc also the boost-build mailing list. Perhaps it is a more appropriate place for discussion. Kind Regards, Marco

1 0

Re: [Boost-users] how to disable autolink feature?
by Marco Azimonti 07 Dec '05

07 Dec '05

Hello Andre, >so what to do? is there a flag to disable autolink? you can modify the file boost/config/user.hpp (http://www.boost.org/libs/config/config.htm) Quote.. /// BOOST_WHATEVER_NO_LIB Tells the config system not to automatically select which library to link against for library "whatever", replace WHATEVER in the macro name with the name of the library; for example BOOST_DATE_TIME_NO_LIB or BOOST_REGEX_NO_LIB. Normally if a compiler supports #pragma lib, then the correct library build variant will be automatically selected and linked against, simply by the act of including one of that library's headers. This macro turns that feature off. ///// Marco

4 3

how to disable autolink feature?
by Andre Krause 07 Dec '05

07 Dec '05

dear boost-users, could someone explain me how to disable the autolink feature of boost? why? 1. no hassle with configurations ( i become independent from the compile mode, i.e. debug/release/multithreaded etc) 2. i do NOT like to be forced to any naming conventions for the libs 3. i do not want to build the full boost lib, just want to include the .cpp files from the few libs of boost i'm using. just including the cpp files works, but the project does not link because visual c++ stops linking because it does not find the libs automagically and unwanted inserted into my project by autolink somewhere.. sadly there even is no simple way to disable the #pragma comment(lib, "autolinkwantstogivealongnametoiostreams.lib"). so what to do? is there a flag to disable autolink?

2 1