April 2010 - Boost - lists.boost.org

space complexity of push_relabel_max_flow
by Dan Jiang 16 Apr '10

16 Apr '10

Hi All, I am a new BOOST user and like it very much. I have a question regarding space complexity of push_relabel_max_flow. The push_relabel_max_flow is very efficient compared to Edmond's and Karp. In my application, I need to deal with half a million nodes and half a billion arcs. It requires lots of ram (>= 6gb). Two questions: 1) How do I find out space used per node and per arc? 2) My network does not need any reverse edge (currently I set the capacity of reverse edge to 0), is there anyway to not supply reverse edges to save space? 3) Does push_relabel_algorithm dynamically allocates lots of memory (besides the ram required by the input graph, i.e., adjacency_list)? 4) Is it possible to implement custom file-based edge lists so that I could explicitly page to disk when not enough ram is available? How slower would it be? Thanks, Dan Jiang _________________________________________________________________ Hotmail & Messenger. Get them on your phone now. http://go.microsoft.com/?linkid=9724463

3 17

[Bind] How do I get bind to deduce the return type of for_each?
by Thomas Jordan 16 Apr '10

16 Apr '10

Hi, I have been trying to use Boost.bind to create an 'STL algorithm function object' to pass into another, 'higher order,' STL algorithm (e.g., to pass a for_each into a for_each). However, I am struggling to get bind to deduce the correct return type of the for_each function object. I include the relevant bits of the code below. class myClass { public: int func(){return mValue;} private: int mValue; }; //wrapper for STL for_each struct myForEach { template <typename II, typename F> F operator()(II begin, II end, F function) const { return std::for_each(begin, end, function); } }; typedef vector<myClass> vocType; typedef vector<vocType> vovType; //overloaded member functions vocType::begin & end typedef vocType::iterator (vocType::*fnPtr)(); typedef const vocType::iterator (vocType::*constFnPtr)() const; vovType vov(10, vocType(10, myClass())); main() { for_each(vov.begin(), vov.end(), bind< ? >(myForEach(), bind(static_cast<fnPtr>(&vocType::begin),_1), bind(static_cast<fnPtr>(&vocType::end),_1), protect(bind(&myClass::func, _1))) } I tried various things for bind<?>, but was only able to get the code to compile (eventually) on my Unix box when I substituted bind< boost::_bi::protected_bind_t<boost::_bi::bind_t<int, boost::_mfi::mf0<int, myClass>, boost::_bi::list1<boost::arg<1> (*)()> > > > for the bind<?>. I had guessed this might work from studying the compiler error messages. Obviously, this is not an ideal solution! Also, I only used the myForEach wrapper after having first attempted - and similarly failed - to bind the raw STL for_each. Is there any way I can help bind to deduce the correct return type - for either myForEach or std::for_each, or both? WIth Best Regards, Tom Jordan (Software Engineer)

3 2

Permission to merge Interprocess/Intrusive bugfixes for 1.43 in release branch?
by Ion Gaztañaga 16 Apr '10

16 Apr '10

Hi, I know it's a bit late, but I would like to ask if it's possible to merge Interprocess/Intrusive bug-fixes from trunk to release. They've been in trunk for some weeks and tests are ok. Best, Ion

5 8

[contract] with Boost.Parameter (was "Contract Programming Library")
by Lorenzo Caminiti 15 Apr '10

15 Apr '10

On Wed, Feb 17, 2010 at 4:05 AM, Andrzej Krzemienski <akrzemi1(a)gmail.com> wrote: >> > it is inevitable, etc., but.. read on. I know at least one library in >> > Boost that also spoils function declarations in order to provide >> > additional functionality: Concept Check library; they may be others >> > too (MPL?). >> > My suggestion is that if there are (or will be) libraries that require >> > spoiling function declarations, they should all provide the same >> > "spoiled" syntax. Otherwise I will be always asking "how do I declare >> > a function in this library?". It would be very convenient if Boost >> > provided one alternative function definition syntax that when used >> > would enable all its libraries to work. >> >> I agree. However, in the past I did look into harmonizing my library >> API with the ones of Boost.ConceptCheck and/or Boost.Parameter but it >> did not seem feasible... I will double check it. > > This is not only about clarity. As a super-correct programmer I may want to > apply both concept checking and pre-/post-conditions checking to my functions. > > Perhaps, if the 'compromise' syntax is possible, it requires changing > concept-checking library. I have verified that it is possible to use Boost.Parameter together with the current implementation of Boost.Contract. However, I have not yet verified compatibility with the entire set of Boost.Parameter features (template parameters, free-functions, etc). #include <boost/parameter.hpp> #include <boost/graph/depth_first_search.hpp> #include <contract.hpp> #include <iostream> namespace graphs { BOOST_PARAMETER_NAME(graph) BOOST_PARAMETER_NAME(visitor) BOOST_PARAMETER_NAME(root_vertex) BOOST_PARAMETER_NAME(index_map) BOOST_PARAMETER_NAME(color_map) struct g { CONTRACT_CLASS( (g) ) BOOST_PARAMETER_MEMBER_FUNCTION( (void), depth_first_search, tag, (required (graph, *) ) (optional (visitor, *, boost::dfs_visitor<>()) (root_vertex, *, *vertices(graph).first) (index_map, *, get(boost::vertex_index, graph)) (in_out(color_map), *, default_color_map(num_verticies(graph), index_map)) ) ) CONTRACT_FUNCTION( (public) (template)( (typename)(graph_type) (typename)(visitor_type) (typename)(root_vertex_type) (typename)(index_map_type) (typename)(color_map_type) ) (void) (depth_firt_search)( (graph_type&)(graph) (visitor_type&)(visitor) (root_vertex_type&)(root_vertex) (index_map_type&)(index_map) (copyable)(color_map_type&)(color_map) ) (postcondition) ({ CONTRACT_ASSERT( color_map == CONTRACT_OLDOF(color_map) + 10 ); }) (body) ({ color_map += 10; std::cout << "graph=" << graph << std::endl; std::cout << "visitor=" << visitor << std::endl; std::cout << "root_vertex=" << root_vertex << std::endl; std::cout << "index_map=" << index_map << std::endl; std::cout << "color_map=" << color_map << std::endl; }) ) }; } // namespace int main() { using namespace graphs; g gg; int cm = 0; gg.depth_first_search(1, 2, 3, 4, cm); std::cout << std::endl; gg.depth_first_search("1", '2', _color_map = cm, _index_map = "4", _root_vertex = "3"); return 0; } This function declaration syntax is terrible as it mixes the syntactic complexity of both Boost.Parameter and Boost.Contract... I will try to provide the following syntax instead: CONTRACT_FUNCTION( (public) (void) (depth_first_search)( // No (tag)(namespace-id) so use `tag`. // (auto) for no type requirements (preprocessor can't use `*`). (auto) (graph) // (default) for optional param. (auto) (visitor) (default)(boost::dfs_visitor<>()) (auto) (root_vertex) (vertices(graph).first) (auto) (index_map) (default)(get(boost::vertex_index, graph)) // (inout) for in-out type. (copyable)(inout)(auto) (color_map) (default) (default_color_map(num_verticies(graph), index_map)) // Plus, (deduced)( parameter-sequence ) for deduced params. ) (postcondition) ( (color_map == CONTRACT_OLDOF(color_map) + 10) ) ({ color_map += 10; std::cout << "graph=" << graph << std::endl; ... }) (IMO, this syntax looks cleaner that the original Boost.Parameter one.) -- Lorenzo

1 0

[intrusive.set] Accessing the last (largest) element.
by Andy Venikov 15 Apr '10

15 Apr '10

Since there is no "back" method for intrusive set, what's the best way to access the last (greatest) element? Is this OK:? IntrusiveSet set1; IntrusiveSet::iterator itEnd = set1.end(); //Make sure that set isn't empty. Value v = *--itEnd; ++itEnd; //will itEnd point to set1.end() after this? In general, is there anything sinister about this construct? (provided that the set isn't empty) Thanks, Andy.

2 2

[asio] read_until -- possibly misleading documentation?
by Richard Smith 15 Apr '10

15 Apr '10

The documentation for Boost.ASIO (which is otherwise very comprehensive) says of the boost::asio::read_until set of overloads: | Read data into a streambuf until a delimiter is | encountered. <http://www.boost.org/doc/libs/1_35_0/doc/html/boost_asio/reference/read_unt…> What the function actually does is to read blocks of data into the streambuf, and stop when the delimiter is found. This means that frequently data beyond the delimiter will be read into the streambuf. (And this is elaborated in more detail on the individual function's pages, if a reader looks there.) I appreciate that this behaviour is compatible with the documentation, but someone less familiar with ASIO could easily assume that the function will read as far as the delimiter and no further. (And I have just spent a fair amount of time debugging a piece of code where the author had made this assumption.) Could we change the summary documentation to read something like: | Read data into a streambuf at least until a delimiter is | encountered. The implementation may read beyond the | delimiter, but will not block when doing so. While I'm on the subject of ASIO documentation, I can't see any documentation on whether the service_name parameters to the basic_resolver_query constructors are allowed to be port numbers (e.g. "80") or whether they have to be symbolic names (e.g. "http"). Port numbers work, at least on Linux, but it's not clear whether this is something that I should be relying on. Similarly for IPv4 and IPv6 addresses in the host_name parameter. Richard Smith

3 2

[contract] concepts (was "Contract Programming Library")
by Lorenzo Caminiti 15 Apr '10

15 Apr '10

On Wed, Feb 17, 2010 at 4:05 AM, Andrzej Krzemienski <akrzemi1(a)gmail.com> wrote: >> > it is inevitable, etc., but.. read on. I know at least one library in >> > Boost that also spoils function declarations in order to provide >> > additional functionality: Concept Check library; they may be others >> > too (MPL?). >> > My suggestion is that if there are (or will be) libraries that require >> > spoiling function declarations, they should all provide the same >> > "spoiled" syntax. Otherwise I will be always asking "how do I declare >> > a function in this library?". It would be very convenient if Boost >> > provided one alternative function definition syntax that when used >> > would enable all its libraries to work. >> >> I agree. However, in the past I did look into harmonizing my library >> API with the ones of Boost.ConceptCheck and/or Boost.Parameter but it >> did not seem feasible... I will double check it. > > This is not only about clarity. As a super-correct programmer I may want to > apply both concept checking and pre-/post-conditions checking to my functions. > > Perhaps, if the 'compromise' syntax is possible, it requires changing > concept-checking library. I have verified that it is possible to use Boost.ConceptCheck together with the current implementation of Boost.Contract as shown below. I will look into doing something similar also for Boost.Parameter. #include <boost/concept_check.hpp> #include <boost/concept/requires.hpp> #include <contract.hpp> #include <iostream> struct x { CONTRACT_CLASS( (x) ) template<typename T> BOOST_CONCEPT_REQUIRES( ((boost::Integer<T>)), (int)) f(const T& x) CONTRACT_FUNCTION( (public) (template)( (typename)(T) ) (int) (f)( (const T&)(x) ) (precondition) ({ CONTRACT_ASSERT( x >= 0 ); }) (postcondition) (result) ({ CONTRACT_ASSERT( result == x ); }) (body) ({ return x; }) ) }; int main() { x xx; std::cout << xx.f(123) << std::endl; // OK: Passes both concept and contract checks. // std::cout << xx.f(1.23) << std::endl; // Error: Fails concept check (compile-time). // std::cout << xx.f(-123) << std::endl; // Error: Fails contract precondition check (run-time). return 0; } This works because CONTRACT_FUNCTION() follows the function declaration which can be spoiled by BOOST_CONCEPT_REQUIRES() as usual to support concepts. However, I am planning to change CONTRACT_FUNCTION() so the function declaration tokens do not need to be repeated and I will add concept support following ConceptC++ syntax: CONTRACT_FUNCTION( (public) (template)( (typename)(T) ) (requires)( (boost::Integer<T>) ) (int) (f)( (const T&)(x) ) (precondition)( (x >= 0) ) (postcondition)(result)( (result == x) ) ({ return x; }) ) This will call Boost.ConceptCheck behind the scenes. Even after this change to CONTRACT_FUNCTION(), Boost.Contract will still provide a CONTRACT_FUNCTION_DEF() that will follow the function declaration (as the current implementation of CONTRACT_FUNCTION() does). Therefore, the example above where Boost.ConceptCheck is used directly can still be programmed using the DEF() macro. Lorenzo

1 0

[date_time][patch] #2757: Warning C4244: conversion from 'int' to 'unsigned short' in microsec_time_clock.hpp line 103
by Sylvester-Bradley, Gareth 15 Apr '10

15 Apr '10

Ticket #2757 describes a simple patch for Boost.Date_Time to get rid of some annoying compiler warnings. Is anyone actively maintaining Boost.Date_Time? This patch has been sitting there for 6 releases already... https://svn.boost.org/trac/boost/ticket/2757 Thanks. ************************************************************************ The information contained in this message or any of its attachments may be confidential and is intended for the exclusive use of the addressee(s). Any disclosure, reproduction, distribution or other dissemination or use of this communication is strictly prohibited without the express permission of the sender. The views expressed in this email are those of the individual and not necessarily those of Sony or Sony affiliated companies. Sony email is for business use only. This email and any response may be monitored by Sony to be in compliance with Sony's global policies and standards

2 1

[contract] importance ordering (was "diff n1962")
by Lorenzo Caminiti 15 Apr '10

15 Apr '10

Hello all, On Thu, Apr 8, 2010 at 7:26 PM, Lorenzo Caminiti <lorcaminiti(a)gmail.com> wrote: > Below is a summary of the differences between Boost.Contract and the > Contract Programming C++ standard proposal n1962. I know some of the > authors of n1962, and also of its previous revisions, are on this > mailing list -- I hope that they can provide comments at least. > > [n1962] Crowl and T. Ottosen, Proposal to add Contract Programming to > C++ (revision 4), The C++ Standards Committee, 2006. All previous > revisions of this proposal are also relevant (and related authors > comments encouraged). I would like to ask: Should Boost.Contract support assertion importance ordering? Importance ordering was introduced in revision 3 of the CP C++ standard proposal but then removed in revision 4: * From n1866 (n1962 revision 3) section 2.1.2 << default assertions syntax: 1. runtime-assertion : boolean-expression importance-ordering opt ; 2. importance-ordering : : integer-constant 8. Importance ordering allows users to specify multiple levels of assertions. The higher an integer, the more crucial it is to keep an assertion in the object code. 9. The default importance ordering is 0 and is in effect when no integer is specified.>> * From n1962 (revision 4) <<Removed the notion of "importance ordering" [10]. [10] (1, 2) In many contexts it is useful to inform the compiler of certain properties. This is true for efficient garbage collection as well as Contract Programming. The same mechanism may be reused to tag a piece of code with some property; in this case we would like to tag individual assertions.>> For example: void f(int x) precondition { x >= 0 : 100; // Importance ordering 100. find(v.begin(), v.end(), x) != v.end(); // Default importance ordering of 0. } ... And in Boost.Contract the syntax: CONTRACT_FUNCTION( (void) (f)( (int)(x) ) (precondition) ( ( x >= 0 )(importance)(100) // Importance ordering 100. ( find(v.begin(), v.end(), x) != v.end() ) // Default importance ordering of 0. ) ... ) Boost.Contract could then provide an API to say "compile and check only assertions with importance ordering within <user-specified-range>". One use case for this is to tag assertions that are expensive to check with a lower importance so they can be disabled selectively to achieve better performance trade off (this was suggested by Andrzej). [Mitchell2002] addresses this use case recommending to never program expensive assertions in preconditions because they will likely be part of production releases (while expensive assertions in postconditions and possibly invariants are acceptable because they, and their run-time overhead, will be removed from production releases). However, this is a binary approach whereas importance ordering would provide a more granular control tool to achieve better performance trade-offs. I would personally recommend for Boost.Contract to support importance ordering -- what do you think? Thank you. Lorenzo

2 1

Re: [boost] [range] iterator_range::operator[] broken
by Eric Niebler 14 Apr '10

14 Apr '10

Neil, let's keep this discussion on-list. It's important. On 4/14/2010 12:21 AM, Neil Groves wrote: > On Wed, Apr 14, 2010 at 7:13 AM, Eric Niebler <eric(a)boostpro.com> wrote: > >> On 4/13/2010 8:03 PM, Steven Watanabe wrote: >>> AMDG >>> >>> Eric Niebler wrote: >>>> Neil, I know you patched this a mere 5 hours ago, but it's still broken. >>>> The attached patch *really* fixes the problem, I think. >>> >>> Whoa. Why is this only returning a real reference for pointers? >> >> Yeah, I dunno. It's this way on the release branch, too. It's very, very >> seriously broken. I think we need to revert range on the release branch >> to the 1.42 version, and fast. >> > I would much prefer to revert just iterator_range.hpp as the change to > handle iterator proxies is orthogonal to the other changes. The change as > applied attempts to leverage the same mechanism as is used in the > iterator_facade to provide a real reference or a proxy where appropriate for > the index operator. It is a breaking interface change in a core library. What is the technical reason for it? >> Neil? >> > I need to take another look at the code and perhaps the operator[] of > iterator_range is broken, but I believe that this issue aside that the other > changes are working well. It would be extremely disappointing to revert all > of the adaptors, and algorithms just because of this issue. I'm more than > happy to fix the problem as soon as I can. I'm seeing massive breakages all over trunk and release, not all of which are related to the changed return type of iterator_range::operator[]. For instance, there seems to be some new ambiguity in the "detail" symbol. See for instance: http://beta.boost.org/development/tests/release/developer/output/RW_WinXP_V… I can't be certain at this point if RangeEx is responsible, but it's where I would start looking. Could you have a look and report back? == Volunteers Needed === If anybody else is reading this: please look at the regressions on the release branch here: http://beta.boost.org/development/tests/release/developer/summary.html. Pick a broken library that interests you and figure out why it's busted. Report back. -- Eric Niebler BoostPro Computing http://www.boostpro.com

2 3