- Boost - lists.boost.org

[BGL] Fruchterman-Reingold: clipping strategy
by Jens Müller 31 May '06

31 May '06

This code: > // Update positions > for (tie(v, v_end) = vertices(g); v != v_end; ++v) { > BOOST_USING_STD_MIN(); > BOOST_USING_STD_MAX(); > Dim disp_size = sqrt(displacement[*v].x * displacement[*v].x > + displacement[*v].y * displacement[*v].y); > position[*v].x += displacement[*v].x / disp_size > * min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp); > position[*v].y += displacement[*v].y / disp_size > * min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp); > position[*v].x = min BOOST_PREVENT_MACRO_SUBSTITUTION > (width / 2, > max BOOST_PREVENT_MACRO_SUBSTITUTION(-width / 2, > position[*v].x)); > position[*v].y = min BOOST_PREVENT_MACRO_SUBSTITUTION > (height / 2, > max BOOST_PREVENT_MACRO_SUBSTITUTION(-height / 2, > position[*v].y)); > } determines the both how objects with strong forces in one direction are "slowed down" and how clipping is done when nodes are about to leave the drawing area. IMO, this should be a bit more generic. E.g., another clipping strategy would be to let nodes "bounce" from the walls. The way the temperature is taken into account could also be different (I presume you have taken it from literature? All these values etc. seem to be largely based on experiments ...). Btw, does anyone have a better test program (e.g., reading and writing Graphviz, together with a sufficiently large example graph)?

1 0

[fusion] MPL-lambda adapter
by Tobias Schwinger 31 May '06

31 May '06

Hi Dan & Joel, >>Tobias Schwinger wrote: >>> (It would also be cool if one could just typedef the lambda expression to nested >>> result or inherit from a wrapper. I don't know whether it's possible and a good >>> idea - this part is just loud thinking)... > > // rtc stands for runtime code > > struct a_func > : result< munch< _1, tweak<_2> > > > { > template<typename A, typename B> > typename result<A,B>::type operator()(A const & a, B const & b) const > { > return rtc::munch(a,rtc::tweak(b)); > } > }; > Here's an implementation. I changed the name from 'result' to 'lambda' (because nested classes shouldn't have the same name as the enclosing ones). FILES: ====== o lambda.hpp MPL-lambda adapter for result computation o lambda_test.cpp test/example for MPL-lambda adapter TESTED WITH: ============ o GCC 3.4.2 o MSVC 8.0 o MSVC 7.1 It works really well -- the technique also reduces ambiguity problems caused by ADL with mutliple namespaces! Hope you like it as much as I do... Regards, Tobias // (C) Copyright Tobias Schwinger // // Use modification and distribution are subject to the boost Software License, // Version 1.0. (See http://www.boost.org/LICENSE_1_0.txt) //------------------------------------------------------------------------------ #include <boost/type.hpp> #include <boost/fusion/algorithm/transformation/transform.hpp> #include <boost/fusion/sequence/container/vector.hpp> #include <boost/fusion/sequence/generation/make_vector.hpp> #include <boost/fusion/support/lambda.hpp> // namespace setup namespace rmf // result metafunctions { using namespace boost::fusion::result_of; using namespace boost::mpl::placeholders; using boost::add_const; } namespace rtc // runtime code { using namespace boost::fusion; } // ---- transform function namespace rmf { typedef lambda< boost::type<_> > a_transform_op; } namespace rtc { using namespace boost::mpl::placeholders; struct a_transform_op : rmf::a_transform_op { template<typename T> typename result<T>::type operator()(T const &) const { return boost::type<T>(); } }; } // ---- user defined algorithm built on top of fusion::transform namespace rmf { typedef lambda< transform<add_const<_>, rtc::a_transform_op> > a_transform; } namespace rtc { template<typename Seq> typename rmf::a_transform::template result<Seq>::type inline a_transform(Seq const & seq) { return rtc::transform(seq, a_transform_op()); // qualification pleases gcc } void test() { a_transform(make_vector("hi","there")); } } // (C) Copyright Tobias Schwinger // // Use modification and distribution are subject to the boost Software License, // Version 1.0. (See http://www.boost.org/LICENSE_1_0.txt) //------------------------------------------------------------------------------ #ifndef BOOST_FUSION_LAMBDA_HPP_INCLUDED #define BOOST_FUSION_LABBDA_HPP_INCLUDED #include <boost/mpl/lambda.hpp> #include <boost/preprocessor/repetition/enum_params.hpp> #include <boost/preprocessor/repetition/enum_binary_params.hpp> #include <boost/preprocessor/facilities/intercept.hpp> namespace boost { namespace fusion { namespace result_of { template<typename PlaceholderExpression> struct lambda { template < BOOST_PP_ENUM_BINARY_PARAMS(BOOST_MPL_LIMIT_METAFUNCTION_ARITY, typename T, = mpl::na BOOST_PP_INTERCEPT) > struct result : mpl::lambda<PlaceholderExpression>::type::template apply< BOOST_PP_ENUM_PARAMS(BOOST_MPL_LIMIT_METAFUNCTION_ARITY, T) > { }; }; }}} #endif

5 13

Re: [boost] [multi_index] benchmarking
by JOAQUIN LOPEZ MU?Z 31 May '06

31 May '06

----- Mensaje original ----- De: Maxim Yegorushkin <maxim.yegorushkin(a)gmail.com> Fecha: Martes, Mayo 30, 2006 10:25 pm Asunto: Re: [boost] [multi_index] benchmarking > Darren Cook wrote: > >> Here are results for cvs head version with your modification, > which show that > >> your analysis was correct: > > > > It would be interesting to see how your results compare to Google's > > (open source) hash map: > > http://goog-sparsehash.sourceforge.net/ > > http://goog-sparsehash.sourceforge.net/doc/performance.html > > > > I've not used them but they seem to give some good improvements > (memory> or speed, but not both) over std_hash and std_map. > > Surprisingly google::dense_hash_set often outperforms all other > containers in both speed and memory usage. [...] > 99997 elements; 10 iterations [...] > memory test (lower is better) > gs_hash [ 21.64%] OOOOOOOO 432760 bytes > gd_hash [ 52.43%] OOOOOOOOOOOOOOOOOOOO 1048576 bytes > std_hash [ 61.58%] OOOOOOOOOOOOOOOOOOOOOOOO 1231568 bytes > ext_hash [ 79.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586428 bytes > mi_hash [ 79.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586440 bytes > mi_set [ 80.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1599968 bytes > std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO > 1999940 bytes Hello Maxim, gd_hash is expected to be faster than other hash containers, but in general it occupies more memory --only that your test is particularly favorable to gd_hash, let me explain: For a regular, bucket-based singly-linked hashed container, the memory consumption for n elements can be calculated as (assuming a 32-bit architecture where pointers are 4 bytes): R(n)=n*(sizeof(element)+4*(1+1/lf)) where lf is the load factor, typically oscillating between 0.5 and 1. Setting n=99997, element=unsigned int, lf=0.75, we've got R = 99997*(4+4(1+1/0.75) = 1333293 which is between actual values for std_hash and ext_hash/mi_hash. Now, for a Google dense hash set the memory consumption is expressed by the formula D(n)=2^(ceil(1+logbin n)) * sizeof(element) where ^ denotes exponentiation, ceil(x) is the smallest integer not less than x, and logbin is the binary logarithm. With the same settings as above we've got D = 2^(ceil(1+logbin 99997)) * 4 = = 2^(ceil(1+16,06)) * 4 = 2^18 * 4 = = 1048576 that is, exactly what your figures show. Why is your test favorable to gd_hash? Because sizeof(element) is small; if you had used a not too large class having, say, four int-sized elements, i.e. sizeof(element)=4*4=16, the resulting numbers change a lot: R = 99997*(16+4*(1+1/0.75)) = = 2533257 D = 2^(ceil(1+logbin 99997) * 16 = 2^18 * 16 = = 4194304 That is, R(n) grows as n*(C+sizeof(element)) with C a constant, while D(n) has the form K*n*sizeof(element) with K always >=2. Hence, when sizeof(element) is sufficiently large gd_hash takes nearly twice the space as a regular hash container. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

3 2

[Boost-bugs] [ boost-Bugs-1497880 ] "edmunds_karps"
by SourceForge.net 31 May '06

31 May '06

Bugs item #1497880, was opened at 2006-05-31 02:55 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1497880&group_… Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: graph Group: None Status: Open Resolution: None Priority: 5 Submitted By: Jens MÃ¼ller (tessarakt) Assigned to: Jeremy Siek (jsiek) Summary: "edmunds_karps" Initial Comment: boost/graph/edmunds_karp_max_flow.hpp - should be edmonds_karps, see http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm ... ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1497880&group_… _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[type_traits][result_of] Handling of cv-qualified function pointers/references
by João Abecasis 30 May '06

30 May '06

Hi! While fixing some issues with fusion::unpack_args I noticed that cv-qualified function pointers are not handled by result_of and type_traits::is_function doesn't handle cv-qualified functions. Here's a simple test case for result_of: #include <boost/utility/result_of.hpp> typedef int (* const c_func_ptr)(int); typedef boost::result_of<c_func_ptr(int)>::type return_type; and a slightly more convoluted for type_traits::is_pointer: #include <boost/type_traits/is_function.hpp> #include <boost/static_assert.hpp> void foo (); template <class F> void bar(F &) { BOOST_STATIC_ASSERT(boost::is_function<F const>::value); } template <class F> void baz(F const & f) { bar(f); } int main() { baz(foo); } Both failing with gcc-4.x. The first test case also fails with gcc-3.2.3. while the second case fails for a completely different reason in overload resolution. For unpack_args I worked around these issues by applying remove_cv to pointers in general and also before testing with is_function. In either case cv-qualification shouldn't affect the type of the arguments or the result, which is what I'm interested in. Anyway I'm thinking that the solution could be moved upstream so others won't stumble upon the same issues. Thoughts? Best regards, João

2 2

[SoC][tree] Theoretical foundations etc.
by Bernhard Reiter 30 May '06

30 May '06

Dear all, just a quick note to * say thanks for accepting my application for the Generic Tree Container * point everyone to my freshly set-up blog at http://www.unet.univie.ac.at/~a0057324/php/blog/ * ask everybody to read the (admittedly pretty lengthy) blog post there on trying to distill a powerful tree interface * and, most importantly, invite everybody to comment on it as that blog is supposed to be the place where i'd like to get in touch with people on technical details without burdening the dev list initially. Kind Regards Bernhard Reiter

2 1

Re: [boost] [multi_index] benchmarking
by JOAQUIN LOPEZ MU?Z 30 May '06

30 May '06

Hello Maxim, ----- Mensaje original ----- De: Maxim Yegorushkin <maxim.yegorushkin(a)gmail.com> Fecha: Domingo, Mayo 28, 2006 12:54 pm Asunto: [boost] [multi_index] benchmarking > As a part of a project I needed to compare performances of > boost::multi_index hashed_unique/ordered_unique indexes > with those of std::tr1::unordered_set, > __gnu_cxx::hash_set, std::set. multi_index performance > documentation page does not provide this kind of > information, Main reason being that std::tr1::unordered containers are not generally available in current environments, although this seems to be improving fast. > so I had to write my own test. I thought > it might be a good idea to add the results to the > documentation page. Source code for the test is provided. > > Here is a sample run: [...] Thank you for sharing your data. Figures show that hashed indices have ample room for improvement with respect to implementations of unordered containers. I have a question, an open question, a request and an invitation. * Which compiler/environment have you run this with? I guess GCC 4.x since you've got tr1 containers. * From the figures on memory consumption of mi_set looks like you're using Boost 1.33.1 (which still doesn't have the spatial optimization suggested by you and described at http://tinyurl.com/rwvvt) right? If so, I cannot find a reason why mi_set performs in general sensibly better than std_set, since the data structures and algorithms are basically equivalent, and B.MI introduces some metaprogramming overhead that the optimizer usually doesn't clean away entirely. I'd have hoped for a small decrease in performance for B.MI, though not as high as that observed in mi_hash wrt std_hash. Do you have an idea anout this? * I'd be grateful if you could rerun the tests for the RC_1_34_0 branch, since mi_set should perform quite better, and erase test(mi_hash) should also improve. If you do this, please report your results back. I must say that B.MI does not intend to outperform single-index std containers since in general the data structures are equivalent; it is when multi-indexing comes into play that I expect a large impact in favor of B.MI. That said, I do what I can in order to optimize the internal algorithms, and your data shows that there's room for improvement in hashed indices --I know you've got good knowledge of the internals of B.MI, so if you feel like contributing to this task or have some ideas to increase performance, you are most welcome. Best regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

4 7

Problem with range (make_iterator_range)?
by Neal Becker 30 May '06

30 May '06

#include <boost/range.hpp> #include <vector> template<typename in_t, typename out_t> void copy (in_t const& in, out_t &out) {} int main() { std::vector<int> out (2); copy (boost::make_iterator_range (out.begin(), out.begin()+2), boost::make_iterator_range (out.begin(), out.begin()+2)); } wrap/test.cc:12: error: invalid initialization of non-const reference of type 'boost::iterator_range<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >&' from a temporary of type 'boost::iterator_range<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >' wrap/test.cc:6: error: in passing argument 2 of 'void copy(const in_t&, out_t&) [with in_t = boost::iterator_range<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >, out_t = boost::iterator_range<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >]'

4 12

Errors in source
by Silex 30 May '06

30 May '06

In compiler_config.hpp, I found the following line: #include "boost/date_time/locale_config.hpp" Maybe it'd be more conventionnal if it used <> instead of "" but that's a minor issue, the problem is when I open this include file I see : #ifndef DATE_TIME_LOCALE_CONFIG_HPP___ #define DATE_TIME_LOCALE_CONFIG_HPP____ This could maybe lead to linker errors as multiple inclusions could occurs. Philippe

2 3

[filesystem] xlC error compiling operations.hpp
by K. Noel Belcourt 30 May '06

30 May '06

Hi, The xlC compiler on the IBM issues a severe error when compiling operations.hpp. The compile error appears to be legitimate (use of an undefined class). Unfortunately I don't have a patch to offer, just the bug report. Thanks. -- Noel Belcourt vacpp.compile.c++ ../../../bin.v2/tools/regression/build/vacpp/ release/link-static/process_jam_log.o "../../../boost/filesystem/operations.hpp", line 732.72: 1540-1118 (S) The declaration of "end_itr" uses the undefined class "boost::filesystem::basic_directory_iterator<boost::filesystem::basic_pa th<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,boost::filesystem::path_traits> >" when the class must be complete. "../../../boost/filesystem/operations.hpp", line 730.21: 1540-0700 (I) The previous message was produced while processing "boost::filesystem::detail::remove_all_aux<boost::filesystem::basic_path <std::basic_string<char,std::char_traits<char>,std::allocator<char> >,boost::filesystem::path_traits> >(const basic_path<std::basic_string<char,std::char_traits<char>,std::allocator< char> >,boost::filesystem::path_traits> &)". "../../../boost/filesystem/operations.hpp", line 473.11: 1540-0700 (I) The previous message was produced while processing "boost::filesystem::remove_all<boost::filesystem::basic_path<std::basic_ string<char,std::char_traits<char>,std::allocator<char> >,boost::filesystem::path_traits> >(const basic_path<std::basic_string<char,std::char_traits<char>,std::allocator< char> >,boost::filesystem::path_traits> &)". "../../../boost/filesystem/operations.hpp", line 689.16: 1540-0700 (I) The previous message was produced while processing "boost::filesystem::remove_all(const path &)". mpCC -c -DBOOST_ALL_NO_LIB=1 -DNDEBUG -O3 -qstrict -qinline -qeh - qrtti -I"../../.." -o "../../../bin.v2/tools/regression/build/vacpp/ release/link-static/process_jam_log.o" "../process_jam_log.cpp"

1 0