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

questions on the BFS example of Parallel BGL
by Da Zheng 27 Apr '11

27 Apr '11

Hello, I'm testing PBGL on my cluster. I have 4 nodes and each node has a dual-core processor. I changed the BFS example a little bit. The code generates a graph with RMAT, and it does BFS 10 times, starting from different nodes. I first run the program in a sequential mode, and the graph has 1,000,000 vertices. Then I run it in the cluster. The result is shown below, but I don't see much speedup. The running time is reduced from 14 seconds to 9.5 seconds. Can the result be right? I see very good speedup in the PBGL document. Another problem is that BFS starting from some vertices only needs very little time. I can imagine that it traverses only very few vertices. Is there any way I can count how many vertices are visited from the specific root vertex? My code is also shown below. Thanks, Da [zhengda@amdahl36 pbgl]$ ./bfs ~/bfs.out 1000000 generate graph takes 162.336 seconds to generate graph start BFS random v: 1395111516 takes 14.3496 seconds for BFS search random v: 488302563 takes 0.029389 seconds for BFS search random v: 72509101 takes 14.1103 seconds for BFS search random v: 1835953408 takes 0.028544 seconds for BFS search random v: 951813172 takes 14.7907 seconds for BFS search random v: 1708481694 takes 14.2254 seconds for BFS search random v: 305355333 takes 14.1587 seconds for BFS search random v: 1627009882 takes 0.02749 seconds for BFS search random v: 1769559585 takes 0.027495 seconds for BFS search random v: 101184463 takes 0.02756 seconds for BFS search [zhengda@amdahl36 pbgl]$ mpirun -np 8 --hostfile ~/.mpi_hostfile ./bfs ~/bfs.out 1000000 generate graph generate graph generate graph generate graph generate graph generate graph generate graph generate graph takes 136.623 seconds to generate graph start BFS random v: 1395111516 takes 9.6362 seconds for BFS search random v: 488302563 takes 0.017129 seconds for BFS search random v: 72509101 takes 9.49864 seconds for BFS search random v: 1835953408 takes 0.031777 seconds for BFS search random v: 951813172 takes 9.53063 seconds for BFS search random v: 1708481694 takes 9.45427 seconds for BFS search random v: 305355333 takes 9.58886 seconds for BFS search random v: 1627009882 takes 0.018723 seconds for BFS search random v: 1769559585 takes 0.020844 seconds for BFS search random v: 101184463 takes 0.016004 seconds for BFS search boost::minstd_rand gen; std::cout << "generate graph" << std::endl; struct timeval start_time; struct timeval end_time; gettimeofday (&start_time, NULL); Graph g(RMATGen(gen, nvertices, 16 * nvertices, 0.57, 0.19, 0.19, 0.05), RMATGen(), nvertices); gettimeofday (&end_time, NULL); if (process_id(process_group(g)) == 0) { std::cout << "takes " << (end_time.tv_sec - start_time.tv_sec) + ((double) end_time.tv_usec - start_time.tv_usec) / 1000000 << " seconds to generate graph" << std::endl; std::cout << "start BFS" << std::endl; } for (int i = 0; i < 10; i++) { int rv = gen(); if (process_id(process_group(g)) == 0) { std::cout << "random v: " << rv << std::endl; } graph_traits<Graph>::vertex_descriptor start = vertex(rv % nvertices, g); // Compute BFS levels from vertex 0 property_map<Graph, vertex_distance_t>::type distance = get(vertex_distance, g); put(distance, start, 0); gettimeofday (&start_time, NULL); breadth_first_search (g, start, visitor(make_bfs_visitor(record_distances(distance, on_tree_edge())))); gettimeofday (&end_time, NULL); if (process_id(process_group(g)) == 0) { std::cout << "takes " << (end_time.tv_sec - start_time.tv_sec) + ((double) end_time.tv_usec - start_time.tv_usec) / 1000000 << " seconds for BFS search" << std::endl; } }

1 0

converting bison to boost::spirit
by Littlefield, Tyler 27 Apr '11

27 Apr '11

Hello all: I have a server I am trying to rewrite, but it uses bison to generate the parser. I know near to nothing about either of these, and the examples kind of confuse me. Is there a way that I can somehow convert the bison to boost::spirit for parsing? Also: I'm kind of curious how one would go about making a parser with boost::spirit. So I define my tokens, (lets say I want to make a calculator as it's pretty simple). Then I would need to generate a tree, correct? My first thought was to just use the [] operator to pass in a function to receive the tokens, then push it to a vector, but that seems like it would be really slow when it comes to parsing the tokens. I also know of an abstract syntax tree, but I'm kind of confused how that works and how spirit would work with it. The calculator overloaded a lot of operators, but I sort of got lost down the line in terms of what was supposed to be happening. Anyone willing to explain this would be greatly appreciated. -- Thanks, Ty

2 1

[units][uBlas] Problems using matrix operations with dimension constraints
by Ryan 27 Apr '11

27 Apr '11

I'm currently trying to use the uBlas library with the units library and I'm running into some problems. The matrix and vector classes I've instantiated with unit constraints don't seem to play well with uBlas methods. Has anyone found ways of using the two libraries together? I've included some lines of what I'm trying to do and would really appreciate some help. Ryan using namespace boost::numeric::ublas; using namespace boost::units; //Works fine. This is expected though since dimensionless quantity can accept //regular built in types. bounded_matrix<quantity<si::dimensionless, 3, 3> rotate = identity_matrix<double>(3); //How do I initialize a vector of dimension lengths with something like the zero_matrix? bounded_vector<quantity<si::length>, 3> diff = zero_matrix<double>(3) * si::meter; //??? //Lets pretend the diff variable has values in it. This line doesn't compile. //The compiler is saying it can't deduce the template argument. //What can I do to help the compiler out so I can get the correct result? bounded_vector<quantity<si::length>, 3> result = prod(rotate, diff);

2 3

[Thread] Solution to conflict with MFC?
by Christian Larsen 27 Apr '11

27 Apr '11

Hello, I know this has been asked before, but I could not find a good solution. I'm experiencing problems with an application using both MFC and Boost.Thread. Specifically the assertion ASSERT(AfxGetModuleState() != AfxGetAppModuleState()); in AfxCoreInitModule() fails. I link Boost.Thread statically into a DLL in my project. From previous posts to this list and elsewhere, e.g. http://lists.boost.org/boost-users/2009/04/46929.php, I see that the issue is caused by setting _pRawDllMain in tss_pe.cpp. Commenting this line does "solve" the problem, but I would rather not have to hack the Boost source code this way. It seems there is a patch somewhere for this problem (referred to in http://lists.boost.org/boost-users/2009/04/47015.php) but it appears it never made it into the source. Is there any chance of this issue being solved in a better way? Best regards, Christian Larsen

4 5

boost build problem?...
by Krzysztof 27 Apr '11

27 Apr '11

I wrote a few lines of code just for start with a library of boost (program_options). Before I did it I had built boost library as prescribed and *.a and *.so files were created in my /home/krzysztof/Documents/Projects/boost/lib directory. However, compilation fails because of undefined references of some external symbols which belongs to program_options library. Could anyone help me with it? Below, there is the code and g++ output. (Linux 64b, Qt Creator and Code::Blocks used as IDE) #include "boost/program_options.hpp" using namespace boost::program_options; using namespace std; int main(int argc, char *argv[]) { options_description opd; opd.add_options() ("help","Display help") ("input_file,if",value<string>(),"Specifies input file") ("fet_file",value<string>(),"definitions file") ("output_file,of",value<string>(),"file after edition"); } g++ -o fetxedit main.o -L/usr/lib -L/home/krzysztof/Documents/Projects/boost/lib -lQtCore -lpthread main.o: In function `main': /home/krzysztof/Documents/Projects/fetxedit-build-desktop/../fetxedit/main.cpp:8: undefined reference to `boost::program_options::options_description::m_default_line_length' /home/krzysztof/Documents/Projects/fetxedit-build-desktop/../fetxedit/main.cpp:8: undefined reference to `boost::program_options::options_description::m_default_line_length' /home/krzysztof/Documents/Projects/fetxedit-build-desktop/../fetxedit/main.cpp:8: undefined reference to `boost::program_options::options_description::options_description(unsigned int, unsigned int)' /home/krzysztof/Documents/Projects/fetxedit-build-desktop/../fetxedit/main.cpp:14: undefined reference to `boost::program_options::options_description::add_options()' /home/krzysztof/Documents/Projects/fetxedit-build-desktop/../fetxedit/main.cpp:14: undefined reference to `boost::program_options::options_description_easy_init::operator()(char const*, char const*)' ... and so on -- Regards Krzysztof Jasieński

2 1

Re: [Boost-users] Boost-users Digest, Vol 2650, Issue 4
by Robert Lupton the Good 27 Apr '11

27 Apr '11

> Sorry for the slow response. I simply defined the following: > > typedef boost::gil::pixel<float, boost::gil::gray_layout_t> gray_float_pixel_t; > typedef boost::gil::image<gray_float_pixel_t, false> gray_float_image_t; > typedef gray_float_image_t::view_t gray_float_view_t; > typedef gray_float_image_t::const_view_t gray_float_const_view_t; > > As Dr. Bourdev advised, I do not use with these typedefs any of the color conversion operations offered by GIL. Apparently those rely on the scaling properties of the float wrapper type. > > So far, all I have done with these typedefs is ... > > 1. construct views using interleaved_view and pixel data pointed to by [const] float*, as illustrated near the beginning of the GIL tutorial > 2. create x- and y- iterators for the views to apply row- and column-oriented algorithms? Sorry for _my_ slow response (I was in Japan). I don't care about colour conversions, but I think that these types will convert to integral types with scaling unless you add more boilerplate. I added the following -- but it may not all have been needed; this was quite a while ago and I was new to gil. I also have some remaining conversion problems where I have to rewrite expressions to make them compile, but this may be something else. Anyway, I'd really like to see native gil support for a complete set of NON-scaling types. namespace boost { namespace gil { /* * Define a type that's a pure float, without scaling into [0, 1] */ typedef float bits32f_noscale; GIL_DEFINE_BASE_TYPEDEFS(32f_noscale, gray) GIL_DEFINE_ALL_TYPEDEFS_INTERNAL(32f_noscale, dev2n, devicen_t<2>, devicen_layout_t<2>) template<> struct channel_multiplier<bits32f_noscale> : public std::binary_function<bits32f_noscale,bits32f_noscale,bits32f_noscale> { bits32f_noscale operator()(bits32f_noscale a, bits32f_noscale b) const { return a*b; } }; template <typename DstChannelV> struct channel_converter<bits32f_noscale, DstChannelV> : public std::unary_function<bits32f_noscale,DstChannelV> { DstChannelV operator()(bits32f_noscale x) const { return DstChannelV(x + 0.5f); } }; template <typename SrcChannelV> struct channel_converter<SrcChannelV,bits32f_noscale> : public std::unary_function<SrcChannelV,bits32f_noscale> { bits32f_noscale operator()(SrcChannelV x) const { return bits32f_noscale(x); } }; // // Totally specialised templates to resolve ambiguities // #define CONVERT_NOOP(T1, T2) \ template <> \ struct channel_converter<T1, T2> : public std::unary_function<T1, T2> { \ T2 operator()(T1 x) const { return static_cast<T2>(x); } \ }; \ \ template <> \ struct channel_converter<T2, T1> : public std::unary_function<T2, T1> { \ T1 operator()(T2 x) const { return static_cast<T1>(x); } \ } CONVERT_NOOP(unsigned char, short); CONVERT_NOOP(unsigned char, unsigned short); CONVERT_NOOP(unsigned char, int); CONVERT_NOOP(unsigned short, short); CONVERT_NOOP(unsigned short, int); CONVERT_NOOP(short, int); #undef CONVERT_NOOP

3 2

[Units] Extension for units of data (and data rate)
by David, Robert (NSN - HU/Budapest) 27 Apr '11

27 Apr '11

Hello, I have created an extension to Boost.Units to support data sizes (bit / byte / kilobit / etc.) and data rates (bit per sec / Byte per sec / kbps / etc.), trying to mimic the logic behind the SI, GCS systems, so it might be added to the library after some review and fixes. Please see the attachment for the code (8 kB zip). Before that, a problem has to be fixed in my implementation: If I define the unit byte_per_second using make_scaled_unit and bit_per_second, I get a mile-long template error about not being able to figure out the prefix when I try to convert a quantity using that unit to string. I did a workaround for this problem using decltype(), but that requires including data_size.hpp and time.hpp to data_rate.hpp (although I don't know if it is a problem), and also, it only works on compilers supporting c++0x. You can see this workaround starting at line 40 in boostex/units/systems/data/data_rate.hpp. If I comment back line 41, and comment out line 44-45, the following will not compile: quantity<byte_per_sec_unit> speed(5.0 * byte_per_sec_unit); std::cout << speed << std::endl; however, auto speed = 5.0 * byte_per_sec_unit; std::cout << speed << std::endl; does (although only on compilers supporting c++0x auto), but prints out "second^-1 byte" instead of "byte/second" - effectively it does not call the name_string specialization for byte_per_sec in boostex/units/systems/data/io.hpp. All of this works correctly with the decltype() workaround. So my question is: can I define byte_per_sec (kilobyte_per_sec, megabyte_per_sec, etc.) in a c++03-compatible way? Br, Robert

1 0

Boost::serialization problem when use archive in a loop
by mikesam 27 Apr '11

27 Apr '11

I have a problem with serialization, and I do not know how to solve it. Time to serialize the class a lot of growing when I do it in a loop. The first iteration takes about 40 ms, for example, but any other takes about 400 ms. class NODE { public: NODE(){} NODE* add(NODE* node) { children.push_back(node); return node; } ~NODE() { for(vector<NODE*>::const_iterator it = children.begin(); it != children.end(); ++it) { delete *it; } } vector<NODE*> children; private: friend class boost::serialization::access; template <typename Archive> void serialize(Archive &ar, const unsigned int version) { ar & children; } }; void save(NODE* main) { std::ofstream stream("test", std::ios::binary); boost::archive::binary_oarchive oa(stream, boost::archive::no_header); oa << main; } int main() { boost::timer t; NODE* main(new NODE()); for (int i=0; i<2000;i++) { NODE* subnode = main->add( new NODE()); for (int k=0; k<20; k++) subnode->add( new NODE()); } for (int i=0; i<4; i++) { t.restart(); save(main); cout<<"serialize: "<<t.elapsed()<<endl; } delete main; return 0; } -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-serialization-problem-when-use-arc… Sent from the Boost - Users mailing list archive at Nabble.com.

2 1

[Boost][BGL] Dynamic Property, dynamic_get_failure.
by Mathieu - 27 Apr '11

27 Apr '11

Hi, I'm trying to generate random graphs (with random edge weight) and write them to a dot file, but I get this exception in the write_graphviz_dp() function : "what(): dynamic property get cannot retrieve value for property: weight." The code looks like this : typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, property<edge_index_t, int>, property<edge_weight_t, int> > graph; boost::minstd_rand gen; graph g; boost::generate_random_graph(g, 10, 30, gen, false, false); boost::randomize_property<boost::edge_weight_t>(g, gen); dynamic_properties dp; dp.property("weight", get(edge_weight, g)); boost::write_graphviz_dp(std::cout, g, dp, std::string("weight")); (don't pay attention to the random generator it's just to keep it simple). I've been looking at the examples and at the doc and it doesn't seem to me that I'm doing something wrong... but apparently I am. Thanks in advance!.

2 4

Re: [Boost-users] Boost versions and the Interprocess library
by David Ohlemacher 27 Apr '11

27 Apr '11

Ion: I think you are probably quite right...and I am just going to have to find another method. I guess I could always give a quick try, but testing would become an issue. How would I really know there are no broken edge cases... Nat: The CORBA implementation works this way. I submit an IDL file that defines my object model (OM) to a website. What I get back is a library (binary, no source) and a pile of additional source files. Together they implement my OM using CORBA. They have dependencies on Boost 1.31. When I link my application, I link in autogenerated COBRA libs, Boost 1.31 libs, and include in various places Boost header files. | I'm perplexed what "closed source" means in this context. Maybe it's | because I don't understand the CORBA environment. But if you have a | prebuilt CORBA executable using Boost version 1.31, I don't understand | how that would constrain in any way the version of Boost you yourself | choose? Thanks for the input, -d

1 0