April 2010 - Boost - lists.boost.org

Graph class, an idea
by Alexander Golec 03 Apr '10

03 Apr '10

Hey all, I have recently been working on a project that has led me to some interesting ideas for a graph class. Chief among them is the structure of the cycle matrix. This is a matrix representing the fundamental cycles of a graph. With this matrix, one can easily determine if, given an arbitrary set of vertices, if there is a cycle that passes through all of them. Whats more, it can easily provide that cycle if it exists. I'd like to ask if this sounds like something that would be useful in Boost's Graph class. Thanks, Alex

2 1

Re: [boost] [GSoC 2010]: BGL Graph Connectives ideas
by Yaroslav Vorontsov 02 Apr '10

02 Apr '10

>> > I have some ideas about implementing graph connectives. I think that the >> > best way to implement first four binary operations (union, join, >> > intersection and difference) is to use adjacency matrices. >> > >> > I think variants of these algorithms for non-adjacency matrices are just as > important. It would be best to focus on these problems and their generic > solution than to propose more solutions for a smaller set of graphs. > OK, let it be so. The implementation of graph connectives using the adjacency matrices isn't too difficult. Regarding adjacency lists or incidency matrices, it's more difficult and intererestring to perform such operations. I meant that it's more convenient to do the operations for adjacency matrices and then to convert them into another graph representation, but now I doubt that this will be more effective (it needs some time to convert a graph from one representation to another (and a lot of memory), and the algorithm needs time and memory, too).

1 0

Re: [boost] Boost Digest, Vol 2869, Issue 5
by Yaroslav Vorontsov 02 Apr '10

02 Apr '10

>> > I have some ideas about implementing graph connectives. I think that the >> > best way to implement first four binary operations (union, join, >> > intersection and difference) is to use adjacency matrices. >> > >> > I think variants of these algorithms for non-adjacency matrices are just as > important. It would be best to focus on these problems and their generic > solution than to propose more solutions for a smaller set of graphs. > OK, let it be so. The implementation of graph connectives using the adjacency matrices isn't too difficult. Regarding adjacency lists or incidency matrices, it's more difficult and intererestring to perform such operations. I meant that it's more convenient to do the operations for adjacency matrices and then to convert them into another graph representation, but now I doubt that this will be more effective (it needs some time to convert a graph from one representation to another (and a lot of memory), and the algorithm needs time and memory, too).

1 0

A Pimpl variant
by vicente.botet 02 Apr '10

02 Apr '10

Hi, I don't know if this is the correct ML to talk about this subject, but as there was recently a discussion about wether Boost should or not use Pimpl, I have decided to post this here. In http://www.gotw.ca/publications/mill05.htm H. Sutter states "There are four main alternative disciplines: 1. Put all private data (but not functions) into XImpl. 2. Put all private members into XImpl. 3. Put all private and protected members into XImpl. 4. Make XImpl entirely the class that X would have been, and write X as only the public interface made up entirely of simple forwarding functions (another handle/body variant)." My experience is that I add more private member functions than private member data. I have explored a different variant 5. Put all private funtion and static data (but not instance data) into XImpl. XImpl needs only to store the back pointer. While this approach doesn't encapsulates all the private members has some advantages: * The XImpl class has no inherent instance data, so no space overhead * The class doesn't needs to store any XImpl pointer as there is no data to maintain, so no need to allocate/deallocate it. * Reduce the performance overhead of the Pimpl idiom. The drawbacks are: * Need to include the headers needed for the private instance data. * There is yet a minimal performance overhead on the construction of the temporary XImpl class and the derreference of the back pointer. Next follows an implementation exaple. * Grant friend access to the private implementation class class C { public: void f(); void g(); protected: // ... private: struct impl; friend struct impl; // the private part contains only instance data and virtual functions int priv; }; * Identify the private functions and the private static data and put them on the implementation class struct C::impl { C::impl(C* thisC) : that(*thisC) {} void ifct() { that.priv = ... // use of private data that.g(); // call to a public function jfct(); // call another private function } C& that; static int icount; }; * Prefix all the ex private function calls by impl(this) impl(this).ifct(); * Access without constraints the impl static data impl::icount; There is a proposal from Francis Glassborow, N1742: Auxiliary class interfaces:<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1742.pdf> that address this problem in a general context. What do you think of this variant? Best, _____________________ Vicente Juan Botet Escribá

6 11

[lambda] [result_of] Lambda enhancements
by Adam Butcher 02 Apr '10

02 Apr '10

Hi Perhaps this would have been better as two separate mails but since it is all lambda related I have included it as one (despite one patch actually being to the result_of library). [lambda] I discovered recently that member-function-ptrs wrapped in boost::lambda objects do not apply directly if the subject is held in a smart-ptr (unless that smart-ptr has an implicit conversion to T*). There are a number of places in our code base where we have worked around this by using something like *free1 rather than simply free1 which ends up calling the 'apply member-function to object-by-reference' adaptor. This works providing the smart-ptr defines a type 'element_type' to be the underlying object type (as shared_ptr et al do). It does not work for third-party smart-ptrs that do not define this type. It struck me that since boost.bind uses boost.mem_fn's get_pointer template to handle this use case it would be reasonable to add an overload of 'apply' to lambda/detail/function_adaptors.hpp that deferred to that. I knocked up a perl script which adds the necessary overloads to each specialization in function_adaptors which I have attached (I have also attached the resulting diff). It may be that this yields some unpleasant side-effects that I haven't thought of or observed but so far it seems to work okay with our code base. The get_pointer overload is disabled if the argument is convertible to ref-to-const-object-type (e.g. if it is a derived type) since then the reference overload should be used. I would appreciate any feedback on the idea and implementation. [result_of] Whilst implementing a front-end template for a set of functions that accept boost.function objects with various return types, I discovered that boost.result_of does not implement support for the nested sig<tuple> template used by boost.lambda objects. My intent was to accept any user-supplied function at the front-end and, based on the given function's return type when applied to a specific set of arguments, forward to the appropriate implementation. This determination currently fails if the user supplies a lambda object. The attached result_of patch adds detection of the nested sig template in order to support determining the return type of lambda functions (providing the necessary arguments are given). This is done in a non-intrusive way; i.e. there is no physical dependency on boost.lambda or boost.tuple, though the boost.tuple classes 'cons' and 'null_type' are forward declared. Since they are only ever instantiated when a boost.lambda object is provided (which will have already brought in their definitions) I think it should be okay. In order to provide the sig template with its required tuple, a facility has been added (with implementation generated by some additional preprocessor code) that converts from function-type to tuple (i.e. F(A,B...) -> cons<F,cons<A, cons<B,...null_type>>>). Since only the type declarations are required this can be done without pulling in any tuple headers. One thing I am a little concerned about is that the determination mechanism for the existence of the sig template is probably not very portable (I have only tried it on GCC 4 and VC9). Is there an MPL/type_traits predicate generator for portable nested template detection? I am aware of BOOST_MPL_HAS_XXX_TRAIT_(NAMED_)DEF but I couldn't see any generator around that area that would do nested template detection. We have such a facility in our code base but it will have only been tried on GCC 4 and VC9 (maybe also VC7.1). Again I would appreciate any feedback on these diffs and whether or not they are suitable for inclusion into the respective libraries. Regards, Adam

4 4

Review results missing for boost.log
by Michael Caisse 02 Apr '10

02 Apr '10

In an attempt to reduce the FUD on IRC I pointed people to the review schedule page to find results on the Boost Log review. To my sheepish chagrin the results are not in the table. Not sure who has permissions to update the table. The following link is Volodya's posted review results. http://article.gmane.org/gmane.comp.lib.boost.devel/201541 thanks - michael -- ---------------------------------- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com

1 0

[GSoC] Heaps & Queues (draft proposal)
by iaml 02 Apr '10

02 Apr '10

Hi everyone. I am Lintao from Sun Yat-sen University, China. This is my first time to send mail on mailing list. I'm a little nervous:-). I am interested in Heaps & Queues provided by Boost in 2010 GSoC. And I have finished my draft proposal after viewing the mailing list these days. Thank you for your comments and suggestions. ====== project proposal ====== In my opinion, most of work is to reuse and rearrange the existing data structure in boost/pending and other data structures which have already existed.[1] The most important thing I should consider is the APIs design of the new library. So for each data structure, it should not only agree to the formulation provided by the BGL, but also should be easy to remember and user-friendly. Besides, I would like to add d-ary heap and splay heap into the new library. Because d-ary heap is a variation of binary heap and has faster running time. As for splay heap, it has the attractive property that recently accessed elements are quick to access again. I think it will be very useful in application software programming. If time permits, I want to add others implementations of heap [2] into the new library. Below is my design to the library APIs. template <class T, class Compare = std::less<T>> class heap{ public: * void insert(T& key);* * void delete(T* key);* * void update(T* t, T& new_key);* T* getRoot(); T* find(T& key); bool empty() const; size_type size() const; void print() const; private: void print_recur() const; protected: T* _root; }; NOTICE: * operations in bold mean it should be implement by the subclass. * operations print and print_recur is optional. But I prefer to include them because it'll be helpful when debugging the programs using this library. The class mentioned above is the base class for all the heap structures in the new library. The classes such as Fibonacci heap, relaxed heap, binomial heap and splay heap should inherit from this abstract class and add additional operations if needed. And I would prefer to use lists rather than vectors (as shown in boost/pending/fibonacci_heap.hpp) to implement it for three reasons. 1. It will save memory since the later needs extra space to store the key to value mapping. 2. Vector requires continuous memory while list doesn’t. It does not matter when the amount of data is small. But when the amount of data becomes large, it will be a tough problem; 3. It takes time to resize and reallocate the memory for vectors. Of course, list implementation has its own drawback such as easy to leak memory and cost more time when searching the heap. From my point of view, it is acceptable comparing with the problems mentioned before. As the adaptor of heaps, the priority queue API may like: template<class T, class Compare = std::less<T>, class Container = fibonacci_heap<T, Compare>> class priority_queue{ public: void push(T& key); T pop(); const T& front() const; T& front(); T* find(T& key); void update(T* t, T& new_key); bool empty() const; size_type size() const; void print() const; private: void print_recur() const; }; [1][2] It means the data structure in this URL: https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/ Thank you for reading.

3 3

[GSoC 2010]: BGL Graph Connectives ideas
by Yaroslav Vorontsov 02 Apr '10

02 Apr '10

> > I'm Yaroslav Vorontsov (or simply Jerry Lee :-)), a student of Computer > > Science Department of Voronezh State University, Russia. I'm interested in > > both generic programming and graph theory, and I also would like to > > participate in Google Summer of Code 2010. I had some experience of generic > > programming before when I tried to implement my own generic graph library in > > C# (of course, as a task on one of programming courses at the university). > > I've read that (quote) "The Boost.Graph library is missing connectives...". > > I'm quite familiar with C++ and the idea of generic programming and I'm > > working with some graph theory aspects at the moment, so I want to know: > > what particular skills (in programming, of course) are needed to develop > > graph connectives? > > > > Hi Simply Jerry Lee:), > > Good question. Working on the Boost graph library requires a sound > understanding of its organization and its construction. There are a lot of > techniques used in its construction that are atypical of most OO libraries > (even C# generic data structures). You should be able to identify aspects of > an algorithm that aren't "universally generic" and understand how to > abstract them using templates, types, metaprogramming, etc. > > Most of that can be learned on the job, so to speak, but having a good eye > for abstraction certainly helps. > > Andrew Sutton > andrew.n.sutton(a)gmail.com > > Mr Sutton, Many thanks for your exhaustive explanation! :-) I have some ideas about implementing graph connectives. I think that the best way to implement first four binary operations (union, join, intersection and difference) is to use adjacency matrices. Also I'd like to add an operation which wasn't mentioned in the task proposal. It's ring sum of two graphs. Here is a short description: let A(Va,Ea) and B(Vb,Eb) be two graphs, where Va and Vb are sets of vertices of these graphs and Ea and Eb are sets of edges. The ring sum of A and B is a new graph C=A(+)B which has no isolated vertices and which has edges included only in Ea or in Eb (but not in both sets). It's something like symmetric difference between two sets in the set theory. As for unary operations, adjacency matrices may be useful in the implementation of graph closure, removal of edge and shrinkage of graph. Yaroslav Vorontsov DarthYarius_0990(a)mail.ru

2 1

use case of [move] rvalue reference emulation
by DE 02 Apr '10

02 Apr '10

hi all once i needed to pass around an object of a reference-like type i.e. a class with reference semantics something as trivial as template<typename type> struct ref { typedef typename type::value_type value_type; type &reference; const size_t index; ref(ref &a) : reference(a.reference), index(a.index) {} ref(type &a, size_t i) : reference(a), index(i) {} ref &operator=(const value_type &a) { /*setting value, e.g. 'reference.set(index, a)'*/ return *this; } operator value_type() const {/*return appropriate value, e.g. 'reference.at(index)'*/} }; so an access function returned an object of that ref type by value and no function wanted to take it because eventually a rvalue could not be bound to a non-const reference then an idea of using a rvalue emulation proposed by boost move library came in my mind although it's not a move constructor it allows to construct objects of type 'ref' from rvalues: ref(rv_ref<ref> &a) : reference(a.reference), index(a.index) {} and also a conversion to rv_ref sholud be added: operator rv_ref<ref>&() { return *static_cast<rv_ref<ref>*>(this); } see fully working code example at http://codepad.org/rRM93AFo defining a reference type "rvalue copy assignable" makes it behave almost the same as ordinary c++ references also constness is preserved perfectly and it happend so that all limitations of the emulation only strengthen the design of such reference types (e.g. unavailability of 'type(const type&)' constructor) an example of the application of such reference types may be an advanced map class when you subscript an stl map object like map[key]; a record with the 'key' is created in the map if it's not there already so not to overpopulate our map we write something like value_type value; if (map.is_there(key)) value = map[key]; of course there is no such 'is_there()' member function in an stl map i'm just trying to make my intention clear so were that smart reference typedefed in the map like template</*...*/> class map { public: //... typedef map_ref<map> reference; //... }; it could have slightly better semantics: map[key]; //always does nothing map[key] = new_value; //if there is no record with 'key' -> creates it //assignes 'new_value' to the value of the record value = map[key]; //retrieves a value associated to 'key' in the last case if there is no such record in the map it may return an invalid value or throw an exception anyway i consider this semantics more natural than that of the current std::map not to mention that you may pass a reference to a function: void foo(map::reference a) { a = "42"; } //if there was no record -> creates it //... foo(map[key]); //does not create record at this point and it will work flawlessly -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out

1 1

[contract] Released Contract Programming Library on SourceForge
by Lorenzo Caminiti 02 Apr '10

02 Apr '10

Hi all, I have released on SourceForge a library that implements Contract Programming (a.k.a. Design by Contract(TM) ) for C++. I am considering to submit this library to Boost (as Boost.Contract). Contract++ Library * Download http://sourceforge.net/projects/dbcpp/ * Documentation http://dbcpp.sourceforge.net/ * Examples http://dbcpp.sourceforge.net/contract__/examples.html Comments? Regards, Lorenzo

2 9