- Boost-users - lists.boost.org

[BGL] BFS < given distance.
by Adam Spargo 29 Nov '10

29 Nov '10

Hi, I have finally managed to implement my genome assembly algorithm! Except one part is too slow. I'm doing a breadth first search starting from each vertex i in an undirected graph, looking for its mate-pair (another given vertex j, of approximately known distance, where distance is the same as summed edge weight). Ideally I want to follow the BFS until either (i) I find the mate-pair vertex j (ii) I have visited all vertices up to some given distance away from the source vertex i. I want to bail out of the algorithm at the first occurrance of either (i) or (ii) and not carry on to search through the rest of the graph, which is very large. So I'm wondering if anybody has had a similar requirement and if they implemented a BFS visitor which accomplishes it? I have managed to limit it to the same connected component, but it still takes too long. The limiting distance is small and so I could just write something, but it would obviously be more elegant to use a BFS visitor. Thanks for any advice, Adam. -- Dr Adam Spargo High Performance Assembly Group email: aws(a)sanger.ac.uk Wellcome Trust Sanger Institute Tel: +44 (0)1223 834244 x7728 Hinxton, Cambridge CB10 1SA Fax: +44 (0)1223 494919 -- The Wellcome Trust Sanger Institute is operated by Genome Research Limited, a charity registered in England with number 1021457 and a company registered in England with number 2742969, whose registered office is 215 Euston Road, London, NW1 2BE.

2 4

thread group
by Lloyd Kanakkassery 29 Nov '10

29 Nov '10

Hi, I am creating "n" number of thread in a loop like this. for(int i=0;i<n;++i) { boost::shared_ptr<boost::thread> th(new boost::thread(boost::bind(&Enum::Execute,shared_from_this(),i,x))); } How can I join all these threads? The approach I used is given below... Before the loop I have created a thread_group object boost::thread_group tg; for(int i=0;i<n;++i) { boost::shared_ptr<boost::thread> th(new boost::thread(boost::bind(&Enum::Execute,shared_from_this(),i,x))); tg.add_thread(th.get()); } tg.join_all(); But the threads are not joined, it is exiting without completion. What could be the mistake I am doing? Thanks, Lloyd

3 2

[thread][repost] recursive shared mutex
by JOAQUIN M. LOPEZ MUÑOZ 29 Nov '10

29 Nov '10

[Trying my luck again with this query.] Hi, Boost.Threads provides a recursive mutex and a shared mutex, but no recursive *and* shared mutex. Would it be a good idea to add this to the library? How hard is it to construct a recursive shared mutex from boost::sahred_mutex (i.e. adding reentrancy to boost::shared_mutex)? Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

5 7

Visiting an element of fusion sequence, selected at run-time
by Max Motovilov 29 Nov '10

29 Nov '10

Here's a seemingly simple problem that I have spent most of my Thanksgiving weekend on, and still don't have enough to boast: Given: 1. A Boost.Fusion-compatible sequence; 2. An integral value i computed at runtime, known to be within 0..size(sequence); implement an algorithm applying some sort of a generic visitor to the i-th element of the sequence. However long I looked through the documentation, I didn't find a ready solution. Here's the best I was able to come up with on my own: ====================================================================== struct at_v { template<typename Seq, typename N> struct result : public fusion::result_of::at<Seq,N> {}; template<typename Seq, typename N> typename result<Seq,N>::type operator()( Seq& seq, N ) const { return fusion::at<N>( seq ); } }; template<typename F, typename Seq, typename IntV> void apply_at( F f, Seq& seq, IntV i ) { fusion::for_each( fusion::as_vector( mpl::range_c< IntV, 0, IntV( fusion::result_of::size<Seq>::type::value ) >() ), phoenix::if_( phoenix::arg_names::arg1 == i ) [ phoenix::function<F>( f )( phoenix::function<at_v>()( phoenix::ref( seq ), phoenix::arg_names::arg1 ) ) ] ); } ====================================================================== Drawbacks: 1. Requires a Boost.Phoenix-compliant visitor -- even though I managed to hide the Phoenix dependency inside apply_at(), it still requires a full-blown templatized result metafunction as part of the visitor even though the latter is not expected to return a value. Be nice to have simpler requirements for a visitor. 2. Can't figure out an easy way of returning a value from the visitor. I tried some constructs using fusion::fold() but only halfheartedly: the big problem is that there is no obvious way to specify that the visitor always returns results of the same type, no matter what argument type it is given. Note that the function calls the visitor only once, so, in principle, there should always be exactly one value to return (index out of bounds should naturally be a contract violation, which is not checked in my version). 3. The complexity is O( size(sequence) ) which is quite atrocious for random access (even though in practice it should not be much of a problem given that it simply means N integer comparisons with a relatively small N). Still, a O( log N ) or even a constant-time implementation should be quite possible... Even though the solution above should be sufficient for my purposes I'm still openly wondering whether I have overlooked something in the Boost libraries and/or whether someone more versed in Fusion/Phoenix/MPL might suggest a better approach. Thanks in advance for any responses, ...Max... PS. Without fusion::as_vector() around the index sequence constructor, GCC 4.4.3 complained of not being able to match operator(), suggestive of a forwarding function problem: looks like operator* on an iterator over mpl::range_c<> returns something that can't be digested by a Phoenix actor. I wonder if this should really be taken care of by the Fusion adapter for MPL sequences? PPS. Is there better documentation for Boost.Phoenix than what's at http://www.boost.org/doc/libs/1_45_0/libs/spirit/phoenix ? Not even a straightforward reference manual?

2 2

using boost serialization with uint64_t, stream error (vista 64bit)
by emeplease 29 Nov '10

29 Nov '10

Hi, I am having difficulties in using boost serialization under ** Windows Vista 64bit **. My boost libraries are built in 64bit. (I have attached the test program below) It seems that boost serialization is not able to serialize uint64_t with maximum value or anything larger then "14757395258967641292", as shown in main() " check_serialization( test64t, "boost::uint64_t" );" Also, If I use multiple inheritance, like below, "YYConfig" and " typedef YYConfig<FakeC, FakeB> MyConfig;" and trying to serialize "MyConfig" , stream error can occurr. Thank you very much for your help. Best Regards, Joseph Here is my output =========== uint32_t ================ succeeded =========== boost::uint64_t ================ failed Input : 18446744073709551615 Output : 14757395258967641292 The following will throw exception : stream error //serialize_and_deserialize( cfg ); Press any key to continue . . . Test Code ===================================================================================== #include<iostream> #include<boost/cstdint.hpp> #include<boost/archive/text_oarchive.hpp> #include<boost/archive/text_iarchive.hpp> #include<sstream> #include<cstdlib> using namespace std; template< class T1, class T2> struct YYConfig : public T1 , public T2 { public: friend class boost::serialization::access; template<class Archive> void serialize(Archive& ar, const unsigned int version) { ar& boost::serialization::base_object< T1> (*this); ar& boost::serialization::base_object< T2> (*this); } }; class FakeB { public: int x; FakeB(): x(0){} friend class boost::serialization::access; template<class Archive> void serialize(Archive& ar, const unsigned int version) { ar& x; } }; class FakeC { public: boost::uint64_t targetNumSamples; friend class boost::serialization::access; FakeC() : targetNumSamples( std::numeric_limits< boost::uint64_t>::max() ){} template<class Archive> void serialize(Archive& ar, const unsigned int version) { ar& targetNumSamples; } }; // ======================= Testing ================================/ template<typename T> T serialize_and_deserialize( T typeValue1 ) { T typeValue2; // Set std::string content; std::ostringstream oss; { boost::archive::text_oarchive oa(oss); oa<< typeValue1; content = oss.str(); } // Extract std::istringstream iss( content ); { boost::archive::text_iarchive ia( iss ); ia>> typeValue2; } return typeValue2; } template<typename T> bool check_serialization( T typeValue1, std::string testName ) { T typeValue2 = serialize_and_deserialize( typeValue1 ); std::cout<< std::endl<< "=========== "<< testName<< " ================"; if( typeValue1 == typeValue2 ){ std::cout<< std::endl<< "succeeded "; return true; } else{ std::cout<< std::endl<< "failed "; std::cout<< std::endl<< "Input : "<< typeValue1; std::cout<< std::endl<< "Output : "<< typeValue2; std::cout<< std::endl; return false; } } typedef YYConfig<FakeC, FakeB> MyConfig; int main(int argc, char** argv ) { boost::uint32_t test32t = std::numeric_limits< boost::uint32_t>::max(); boost::uint64_t test64t = std::numeric_limits< boost::uint64_t>::max(); check_serialization( test32t, "uint32_t" ); check_serialization( test64t, "boost::uint64_t" ); std::cout<< std::endl<< "The following will throw exception : stream error"<< std::endl ; system("pause"); MyConfig cfg; serialize_and_deserialize( cfg ); return 0; }

1 0

[phoenix][phoenix3][MPL] incompatibility between MPL and Phoenix3
by alfC 28 Nov '10

28 Nov '10

Hi, I decided to try Phoenix3. I looked up at a couple of examples and since I use Boost.Units (which depends on Boost.MPL) heavily I tried to mix both only to find out that there is an obscure incompatibility between MPL and Phoenix3. The way to show this is just to compile the phoenix3/.../function.cpp example https://svn.boost.org/svn/boost/sandbox/SOC/2010/phoenix3/libs/phoenix/exam… with the following added line: #include<boost/mpl/multiplies.hpp> I get this error message: In file included from function.cpp:12: /home/user/usr/include/boost/mpl/multiplies.hpp:38: error: wrong number of template arguments (7, should be 5) /home/user/usr/include/boost/mpl/aux_/preprocessed/gcc/times.hpp:68: error: provided for ‘template<class N1, class N2, class N3, class N4, class N5> struct boost::mpl::times’ The full code (almost identical to the example) follows -- Thank you, Alfredo / *============================================================================= Copyright (c) 2001-2003 Joel de Guzman Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) ==============================================================================*/ #include <vector> #include <algorithm> #include <iostream> #include <boost/phoenix/core.hpp> #include <boost/phoenix/function.hpp> #include<boost/mpl/multiplies.hpp> ///////////// offending line using boost::phoenix::function; struct is_odd_ { template <typename Arg> struct result { typedef bool type; }; template <typename Arg> bool operator()(Arg arg1) const { return arg1 % 2 == 1; } }; function<is_odd_> is_odd; int main() { using boost::phoenix::arg_names::arg1; int init[] = { 2, 10, 4, 5, 1, 6, 8, 3, 9, 7 }; std::vector<int> c(init, init + 10); typedef std::vector<int>::iterator iterator; // Find the first odd number in container c iterator it = std::find_if(c.begin(), c.end(), is_odd(arg1)); if (it != c.end()) std::cout << *it << std::endl; // if found, print the result return 0; }

3 3

Cannot build Boost
by Ondřej Majerech 28 Nov '10

28 Nov '10

Hello, I'm trying to build Boost libraries from source (I want to use Boost.Python and Boost.Test, also I want to use a compiler other than my system one). I grabbed the boost_1_45_0.tar.bz2 and boost-jam-3.1.18.tgz tarballs. Built Jam by doing ./build.sh gcc and then copied the bjam executable to my ~/bin directory which is in $PATH. Then I went to the boost_1_45_0/tools/build/v2/example/hello directory, ran bjam, the example compiled and I was able to run it successfuly. I created ~/boost-build.jam file with boost-build /usr/home/oxyd/development/boost/boost_1_45_0/tools/build/v2 ; in it. Then I came back to the boost_1_45_0 directory. As per the instructions -- http://www.boost.org/doc/libs/1_45_0/more/getting_started/unix-variants.htm… -- I ran bjam and got an error: ~/development/boost/boost_1_45_0 > bjam toolset=gcc stage Class top-level-target already defined zsh: abort bjam toolset=gcc stage I have only Googled a little info on this error -- in fact, the only useful hit is this: http://lists.boost.org/boost-build/2009/05/21793.php . I guess I can just as well provide the info asked for in that post: ~/development/boost/boost_1_45_0 > grep 'class top-level-target' Jamroot | wc -l 1 -- exactly one occurence of class top-level-target there. The only Jam-related file in the directory is Jamroot. Running with --debug-loading I get the lovely output that I attached to this mail. Additionally, I'm running FreeBSD 8.1-RELEASE, and I want to use GCC 4.5.2 installed from Ports (system compiler is GCC 4.2.1). Thanks for any thoughts on the issue, Ondra

4 11

Boost.FileSystem dependency on Boost.System?
by Matthew Gwynne 28 Nov '10

28 Nov '10

Hi, It seems when compiling anything using Boost.FileSystem that the Boost.System library is also linked. Is this always the case? I can't see any clear documentation of this on the Boost.FileSystem page. If this is the case, is there a nice list of all such dependencies somewhere, as this is currently causing us certain issues? Thanks! Matthew Gwynne http://cs.swan.ac.uk/~csmg/

5 8

[PBGL] Betweenness centrality and named vertexes
by Carmine Paolino 28 Nov '10

28 Nov '10

Hello, I'm trying to use `brandes_betweenness_centrality` with named vertexes but so far I haven't managed to get it working. These are the two approaches I tried: 1. passing an iterator_property_map on the vertex_index: https://gist.github.com/f02f18f30f0eef146a58#file_betweenness_named_graph.c… 2. passing a property_map on a float inside the vertex: https://gist.github.com/f02f18f30f0eef146a58#file_betweenness_named_graph2.… And these are the compile logs for the first file: clang: https://gist.github.com/f02f18f30f0eef146a58#file_compile_clang.log gcc:https://gist.github.com/f02f18f30f0eef146a58#file_compile_gcc.log and the second file: clang: https://gist.github.com/f02f18f30f0eef146a58#file_compile_clang2.log gcc: https://gist.github.com/f02f18f30f0eef146a58#file_compile_gcc2.log What I'm doing wrong? Thanks in advance

2 12

Boost 1.45.0 Release Notice
by Beman Dawes 28 Nov '10

28 Nov '10

Release 1.45.0 of the Boost C++ Libraries is now available. These open-source libraries work well with the C++ Standard Library, and are usable across a broad spectrum of applications. The Boost license encourages both commercial and non-commercial use. This release contains numerous enhancements and bug fixes for existing libraries. For details, see http://www.boost.org/users/news/version_1_45_0 The release can be downloaded directly from SourceForge. See http://sourceforge.net/projects/boost/files/boost/1.45.0/ To install this release on your system, see http://www.boost.org/doc/libs/release/more/getting_started/index.html Thanks, --The Boost release team Beman Dawes Daniel James Eric Niebler Rene Rivera Vladimir Prus

2 1