May 2006 - Boost - lists.boost.org

[BGL] Fruchtermann-Reingold: grid
by Jens Müller 01 Jun '06

01 Jun '06

My questions are concerning this part: > std::size_t adj_start_row = row == 0? 0 : row - 1; > std::size_t adj_end_row = row == rows - 1? row : row + 1; > std::size_t adj_start_column = column == 0? 0 : column - 1; > std::size_t adj_end_column = column == columns - 1? column : column + 1; > for (std::size_t other_row = adj_start_row; other_row <= adj_end_row; > ++other_row) > for (std::size_t other_column = adj_start_column; > other_column <= adj_end_column; ++other_column) > if (other_row != row || other_column != column) { > // Repulse vertices in this bucket > bucket_t& other_bucket > = buckets[other_row * columns + other_column]; > for (v = other_bucket.begin(); v != other_bucket.end(); ++v) > apply_force(*u, *v); > } In the code above, where repelling forces inside a bucket are computed, each pair of nodes is considered only once, and then apply_force(*u, *v); apply_force(*v, *u); are called. Wouldn't something like this be more efficient here, too? We have +------+------+------+ | | | | | 1 | 2 | 3 | | | | | |------|------|------| | | | | | 4 | X | 6 | | | | | |------|------|------| | | | | | 7 | 8 | 9 | | | | | +------+------+------+, where X is the bucket u resides in, and the others are the adjacent buckets considered. For every u, all nodes from all other buckets are considered. My proposal: Consider only 1, 2, 3 and 4 and do apply_force(*u, *v); apply_force(*v, *u); again 6, 7, 8 and 9 will be considered when those buckets are processed. Shouldn't this be (at least a bit) more efficient?

2 4

Re: [boost] [array] optional constructors in Boost.Array
by Martin Bonner 31 May '06

31 May '06

Thorsten Ottosen wrote: > Maybe you should just wrap boost::array: > > template< class T, unsigned N > > struct my_array : boost::array<T,N> > { > // provide constructors here How? > }; You can't construct the base boost_array in the base class initialization list of the constructor (because boost_array doesn't have a constructor that takes arguments), and by the time you get into the body of the my_array constructor it is too late - the boost_array is already default constructed. Having said which, personally I think that a seperate class with constructors would be better than adding another template class to boost::array. -- Martin Bonner Martin.Bonner(a)Pitechnology.com Pi Technology, Milton Hall, Ely Road, Milton, Cambridge, CB4 6WZ, ENGLAND Tel: +44 (0)1223 203894

6 12

[format] %d with char types
by Luke Elliott 31 May '06

31 May '06

I previously posted this to the users group (http://search.gmane.org/search.php?group=gmane.comp.lib.boost.user&query=%5…) with no response - I thought I'd try here before giving up, so sorry for repeating myself... Anyway, using %d, %u etc. with char types prints the character rather than the integral value. I've had a quick hack around with the code, adding the following to feed_args.hpp: template< class Ch, class Tr> inline void put_last( BOOST_IO_STD basic_ostream<Ch, Tr> & os, const char& x ) { if (os.flags() & (std::ios_base::dec | std::ios_base::hex | std::ios_base::oct)) os << static_cast<int32_t>(x); else os << x ; } (ditto for unsigned char) and modding internals.hpp: template<class Ch, class Tr> inline void stream_format_state<Ch,Tr>:: reset(Ch fill) { // set our params to standard's default state. cf § 27.4.4.1 of the C++ norm width_=0; precision_=6; fill_=fill; // default is widen(' '), but we cant compute it without the locale flags_ = std::ios_base::skipws; // the adjust_field part is left equal to 0, which means right. exceptions_ = std::ios_base::goodbit; rdstate_ = std::ios_base::goodbit; } (i.e. remove std::ios_base::dec from flags_) 'works' (vc71) for the very few limited cases I've tried. I'm sure that's horribly broken for any number of reasons, but I'm more interested in whether this is considered a problem or not? It seems a shame to have to cast arguments to format if they happen to be char and %d is specified in the format string (also obviously making writing generic code more difficult!). Thanks in advance Luke Elliott.

1 0

Re: [boost] Endian library - request for comments
by Benaka Moorthi 31 May '06

31 May '06

Beman Dawes wrote: I think the names for the types might be a little bit too cute. "bin" makes me think binary, not signed big-endian. That being said, I'm not sure I have any good name that isn't far too verbose. unsigned_littleendian_aligned<4> is admittedly starting to push convenience, though bigendian<5> isn't too bad. I'm often amazed at the clever names Boosters suggest, so I think it is worthwhile to speculate a bit about better names. But the everyday use typedefs really do need to be short and memorable. I've been using the "bin2", "bun3", etc. since 1984 or so, with several hundred programmers now using them all the time, and never had a request to change the names. How about using namespaces: namespace endian { namespace big { typedef ... unum1; typedef ... snum1; ... } namespace little { typedef ... unum1; typedef ... snum1; ... } typedef big::unum1 bun1; typedef big::snum1 bin1; ... } -- http://www.fastmail.fm - Does exactly what it says on the tin

1 0

Re: [boost] Infinite precision integer draft
by Jarrad Waterloo 31 May '06

31 May '06

Sorry for confusing us both! When I say heap I was referring to memory allocated dynamically via the POSIX methods or C++ new/delete. Although the majority of my background has been in a Win32 environment when I deal with standard C++ and boost the word Microsoft doesn't enter into my vocabulary. I was working/speaking under the mistaken assumption that each instance of integer has its own allocator by type as in the standard library or at runtime as many but not all wish it. As such I thought integer_allocator was an interface or close to one and there was a separate class that implements that interface or abstract class that had the code for the dynamic memory allocations. I totally missed the following sentences in the spec. > The abstract class integer allocator provides the interface to provide a > user-defined derived allocator class for class integer. Classes derived > from this class can only be used as static allocators for other classes > derived from class integer. > Makes the static allocator active for all integer memory allocations. What I was hoping to be able to do was something like this? integer<stack_allocator<T> > or integer(stack_allocator<T>) or integer<T> where T is the minimum number of bits, minimum number of bytes or minimum number of longs (bits may be better as the internal implementation may very from processor to processor). The implementation is simple because the size of the stack_allocator or stack_integer is allocated at compile time on the stack. As allocate will just return the already allocated memory and deallocate will do nothing. The demand for this is the need/preference for large finite precision numbers. Currently C++ provides the ability to work with small finite numbers and integer provides infinite precision numbers. This addition would fill in the gap between the two with many of the strength and advantages of both worlds without negating the need to be able to go to either extreme. Your code is capable of filling this gap it just needs the ability to limit itself to stack operations on a per instance basis. This request is similar to the differences between std::bitset<T> and boost::bitset. Sure boost::bitset can do everything std::bitset can do but users will still use std::bitset for efficiency when they know the size up front since it is created on the stack and the other is dynamically allocated. Users just want the two to have a common base class which can't currently be done as that will change the std. However as yours is a new library, I was hoping it would handle this need and do it correctly from the beginning. With the current design how would one do this? Deriving from integer_allocator is straight forward but what must one do to a derived integer to use this new allocator? If you do concur that this is a need wouldn't it be good to go ahead and provide an implementation of stack_integer and stack_integer_allocator that can do this so users don't have to keep reinventing the wheel. Further could there be any changes to the allocator architecture to make things easier not from its interface standpoint but from from how it is used and stored to get better reuse especially with all this talk on unsigned integer and modulus integer. I would hate to see stack variants for all three. -----Original Message----- From: Maarten Kronenburg [mailto:M.Kronenburg@inter.nl.net] Sent: Tuesday, May 30, 2006 3:46 PM To: Jarrad Waterloo Subject: Re: Infinite precision integer draft Jarrad, Thanks for your reply. The default integer_allocator used by integer use the standard POSIX malloc, realloc and free functions. You are right that I should add this remark to the spec document. The making of a heap_allocator is trivial, using HeapCreate and HeapDestroy, and HeapAlloc, HeapReAlloc and HeapFree. But this only works on Win32 systems, so this cannot be added to the spec. Your stack_integer_allocator<size_t>, how would that allocate, reallocate and deallocate look like? Do you have such an implementation ? Or a literature reference where I can find it ? When I have an implementation, then I feel safe to add it to the spec. Regards, Maarten. ----- Original Message ----- From: "Jarrad Waterloo" <jwaterloo(a)dynamicquest.com> To: "'Maarten Kronenburg'" <M.Kronenburg(a)inter.nl.net>; <boost(a)lists.boost.org> Sent: Tuesday, May 30, 2006 5:12 PM Subject: RE: Infinite precision integer draft > Thanks for the welcome of all the other enhancements, especially in the area > of conversion, to make your integer library easy to use for everyone. > > Further, don't get discouraged as your colleagues discuss the meaning of 0, > life and the universe while people who actually would use it already > understand what 0 means because we have been without, 0, this library for so > long. > > 'Feed a mouse a cookie and he will ask for a glass of milk.' > > > Creating integers with variable size on the stack, > > that is in any case something that I will not > > specify, but users that want to use these tricks > > can just override the integer_allocator. > > Currently you have an integer class which takes an integer_allocator base > class. Even though the spec doesn't mention this or I glossed over reading > it but you probably are going to provide a heap_integer_allocator class that > could be named whatever but exists as the default integer_allocator for the > integer class. This way users can just start using the library right away > instead creating there own allocator the first time they use this library. > > What I was suggesting was not a change to the integer, integer_allocator > base class or the currently unnamed heap_integer_allocator! Rather the > addition of a stack_integer_allocator<size_t> : public integer_allocator. > > The reasons for the library to provide this instead of the end user is as > follows: > 1) Performance, stack based allocations are faster than heap based and in > some field domains one will know the upper limit on size. This generates the > need for multiple people wanting to do this especially when performance > matters. > 2) Standardization, if you foresee that many people are going to need this > functionality than your library becomes easier because you can go ahead and > provide the class instead of a large unsigned integer of people having to > reinvent the wheel and create the exact same class themselves. > 3) Maintain ease of use as complexity increases, in just this one area this > library could suffer from the opposite problem of the standard library. The > standard library algorithms was all passing 2 iterators around which allows > for maximum flexibility for more complicated scenarios but lacked the > overrides like boost Range where you could pass the collection and the > algorithm uses begin and end for the more common and simple scenarios. > Integer library does the opposite which is mostly good, it provides the heap > allocator for the most common and general use but as complexity increases > and someone needs stack based allocator the user is left in the lurch and > have to right there own, over and over again from user to user. I just > believe this library would be more feature complete if it would just go > ahead and provide the both implementations up front. > 4) Architectural consistency, this library is designed to behave like > existing integer types that can be created both on the stack and on the > heap. > > > > >

3 2

Logging in Boost
by Armin Nagel 31 May '06

31 May '06

Hi All, will there be logging support in boost further time? log4cxx isn´t uptodate and I suggest logging in boost. Maybe u have heard about the unofficial logging for boost. Can someone tell me a release date within logging-support? So long Armin

3 3

[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