March 2009 - Boost - lists.boost.org

[Boost.Config] Using <cstddef> instead of <utility> for std lib detection
by David Deakins 28 Mar '09

28 Mar '09

I am in the process of migrating our VeecoFTC regression tests from VC8 and STLport 5.1 to VC9 and STLport 5.2. While working on this, I have experimented with turning on STLport's _STLP_USE_BOOST_SUPPORT macro. When this macro is defined, STLport will pull in the Boost.TypeTraits header files instead of its own type traits implementations. It also suppliments a few of the standard headers (memory and functional) with Boost-based TR1 functionality much like Boost.TR1 does. However, similar to some of what Boost.TR1 had to deal with, some caution is required to avoid circular dependencies in the headers. One area where this tends to come up is in detecting the standard library in use in Boost.Config. Currently config/select_stdlib_config.hpp and config/stdlib/stlport.hpp include <utility> to determine what std library is provided. However, <utility> can tend to pull in some code that wants type traits and thus may circularly pull in Boost. One convenient way to resolve this would be to use the much simpler <cstddef> header instead of <utlity> to determine the std lib. Is this a reasonable change to make or is there something special about using <utility> in the select_stdlib_config code? -Dave

1 0

[gsoc] Status
by troy d. straszheim 27 Mar '09

27 Mar '09

We have 9 proposals. Four of these are for the devector idea: students who have filed these overlapping proposals are encouraged to take the initiative, come up with some ideas and discuss them on the list. We have enough mentors, but it isn't clear that each proposal will match up well with an individual mentor. More mentors welcome to apply. Currently we have no way to make the current set of proposals visible to the general community. I've filed a bug with google and have reason to hope this will get resolved soon. Until then only accepted mentors can see the full list. :/ Students who are working on a proposal who haven't submitted it yet are encouraged to get a draft together, put it up on a webpage or wiki someplace, solicit comments, and refine. This can only help your chances. -t

2 2

[Boost][Random] Question on random_test.cpp
by n1driver＠charter.net 27 Mar '09

27 Mar '09

The following is an excerpt from the random_test.cpp file (part of the instantiate_urng function): urng2 = urng; { // narrow stream first std::ostringstream file; file << urng; // move forward urng(); // restore old state std::istringstream input(file.str()); input >> urng; // std::cout << file.str() << std::endl; #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 // MSVC brokenness // advance some more so that state is exercised for(int i = 0; i < 10000; ++i) { urng(); urng2(); } BOOST_CHECK(urng == urng2); #endif // BOOST_MSVC } My concern is that when a random number generator with an underlying double type (like fibonacci607) is stored to the stream and then pulled back out, then precision may be lost, and the underlying data is not guaranteed to be the same. If a double is written out to a stream in decimal form and then read back in the value may be changed. Am I missing some sort of language guarantee that this is supposed to work? I've tried this on AIX and the test failed at this point for fibonacci607 because some (but not all) of the underlying doubles had changed after the object was stored and retrieved. Thanks!

2 1

[gsoc][graph] Hierarchical graph layout algorithms.
by Daniel Arbelo 27 Mar '09

27 Mar '09

Hello, I'm a student interested in adding hierarchical layout algorithms as mentioned in https://svn.boost.org/trac/boost/wiki/soc2009#Hierarchicalgraphlayoutalgori… . Is there someone available I could discuss the details for it? Are there any prospective mentors for this proposal? I'm mostly looking to discuss a proper scope for this and what Boost needs or expects from a proposal in this area. Daniel Arbelo Arrocha

1 0

boost::interprocess -- How do I construct a anonymous object ?
by Oncaphillis 27 Mar '09

27 Mar '09

Hi, I'm using boost::interprocess (1.37) and would like to construct a couple of anonymous objects. The idea is to construct a named object via Object *o segment.find_or_construct<Object>("theObject")(); and let this one dynamically construct a couple of other objects to which it holds offset_ptrs. On destruction one could simply use segment.destroy_ptr<Object2>( myOffset.get() ); to get rid of these objects. This works fine with objects I constructed with segment.construct<Object2>("GAGA NAME")(); but the reference by name seems to be unnecessary. The doc tells something about constructing and creating of anonymous objects but so far I only find allocators or copy constructors for anonymous objects. Thanks you .... O.

2 1

[gsoc] Boost graph library - Hypergraphs
by Om Prasad Patri 27 Mar '09

27 Mar '09

Hi, I'm a Computer Science undergrad from India applying for GSoC 2009. This mail is regarding the hypergraph project for the BGL on the ideas list. I have taken courses in graph theory and algorithms and have the C++ background required. I have gone through the idea and done a little 'research' on the topic. I have also read the boost graph library documentation and found the concept to be quite interesting and somewhat tough to implement. I have certain ideas and doubts on the hypergraph project which I would like to discuss with a mentor. First of all, what about the assumptions. Can we assume the hypergraph to be directed ro undirected or do we have to try to find a generic solution for both? "This project minimally involves the definition of one hypergraph data structure and a generic traversal algorithm". Now, for the data structure, we can use an incidence matrix with vertices as rows and edges as columns. This incidence matrix structure will have to be implemented. As an alternative, we can have a 'bipartite' kind of data structure with two groups of vertices V and E, where V represents the group of vertices and E the group of edges. Identification and definition of other concepts related to hypergraphs, like hyperedges etc. can then be done accordingly. As for the traversal algorithm, is it to be decided now (before applying) which algorithm is to be used ? I searched for and found a few on the internet like http://www.icsi.berkeley.edu/cgi-bin/pubs/publication.pl?ID=000778 . I would be happy if you could provide me links of some traversal algorithms I should look at and which would help me understand the concept better. I'm new to Boost and I hope I have made an humble beginning. :) Hoping for some replies and suggestions, Ciao, Om P Patri, Sophomore, Computer Science and Engineering Indian Institute of Technology, Guwahati, India --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- A hypergraph (http://en.wikipedia.org/wiki/Hypergraph) is a generalization of graphs where an edge can connect any number of vertices (instead of exactly two). Hypergraphs can also be directed or undirected, and have their own algorithms (e.g., traversal and partitioning). This project minimally involves the definition of one hypergraph data structure and a generic traversal algorithm. This project would also involve the identification and definition of generic concepts related to hypergraphs. Note: This is a non-trivial project that requires substantial knowledge of graph theory, algorithms, and generic programming.

5 9

[gsoc] Graph : BGL - Incidence Matrices Project
by Om Prasad Patri 27 Mar '09

27 Mar '09

Hi, I'm a student applying for GSoC to Boost Graph Library. This is my second post here and this mail is regarding the incidence matrices project for the BGL(earlier one was for hypergraphs and these are the two ideas which interested me the most in the 'ideas list'.) I have gone through the idea and the BGL documentation and the idea appeals to me as pretty interesting, useful and implementable. Also, I do not have any other commitments during the summer. I am giving a rough idea of what I understood we have to do in this project. Please correct me if I am wrong anywhere and clarify my doubts. Most of the concepts which I'm discussing here are obtained from wikipedia ( http://en.wikipedia.org/wiki/Incidence_matrix) . As far as I understand, we have to implement generic incidence matrices for: 1. oriented incidence matrices for undirected graphs. The matrix will contain zeroes and ones. 1 if the corresponding vertex and edge are incident, 0 otherwise. One edge has two incident vertices. 2. incidence matrices for directed graphs. matrix will contain 1, 0 and -1. -1 for edge coming out of vertex, +1 for edge going into vertex (or maybe the opposite convention) and 0 for edge and vertex not incident. 3. unoriented incidence matrices for undirected graphs (similar to above case). 4. Signed graphs. A method for filling up the incidence matrix is given here : http://en.wikipedia.org/wiki/Signed_graph#Incidence_matrix 5. Bidirected graphs. A convention can be made but I'm not sure yet. It would be better if you could throw some light on this topic, i.e how to get an incidence matrix of a bidirected graph. 6. Hypergraphs. Incidence matrices are a good way of representing hypergraphs and this adpatation can help a lot in implementing hypergraphs. The incidence matrix can be obtained as given here: http://en.wikipedia.org/wiki/Hypergraph#Incidence_matrix Apart from these, we can also think of using incidence matrices to get the Kirchoff Matrix and adjacency matrix (I am not sure if adjacency matrix already exists in BGL) if it is possible and time permits. Please tell me if I am going in the right direction and if there is anything I left out or included unnecessarily. Any other information regarding the project will be highly appreciated. Thanks for your reply in advance, Ciao, Om P Patri, Sophomore, Computer Science and Engineering Indian Institute of Technology, Guwahati, India. ----------------------------------------------------------------------------------------------------------- Incidence Matrices <https://svn.boost.org/trac/boost/wiki/soc2009#IncidenceMatrices> An incidence matrix (http://en.wikipedia.org/wiki/Incidence_matrix) is a graph data structure that relates vertices to the set of edges that connect them. This project would entail the implementation of a generic incidence matrix data structure that fits into the BGL generic graph interface. This project can include the development and definition of concepts related to graphs represented by incidence matrices (e.g., signed and bidirected graphs). Incidence matrices can also be adapted to implement hypergraphs.

2 1

Final report of GSOC project 'Spatial Indexes'
by Federico J. Fernández 27 Mar '09

27 Mar '09

Hi List! I'm writing this email as a final report of my Google Summer of Code 2008 project for Boost. My project consist in adding some spatial indexing structures to Boost in the context of the Geometry proposal done by Barend Gehrels. Spatial indexes are data structures optimized for spatial oriented queries. The classic index structures (i.e. a binary tree) aren't spatially enabled, they have different ordering criteria but none of them relates to topological properties. The scope of these structures is really wide, from collision detection for games to geometry indexing for GIS software. The original project goals were: - Build a Quadtree. - Build an rTree. - Integrate some previous work from a former GSoC project of a k-d-tree. - Test and document everything. Both indexes are implemented now and everything is tested and documented. The only task that we didn't complete is the k-d-tree integration, because when we analyzed the code it was not ready, and we didn't have the time to finish it. About the results, we made several tests and benchmarks. We tested both indexes with 230.000 objects from GIS data to check the correctness of the implementation, and we made some benchmarks comparing the quadtree vs. rtree and comparing both of them to existing implementation (like GEOS) with very good results. We describe this benchmarks in the documentation offering this as a guide to choose the best index for each use. The code is still beta (or maybe alpha) and not recommended for production use because it is still not tested enough, but if you want to check the actual status you can find it in the following location: https://svn.boost.org/svn/boost/sandbox/SOC/2008/spacial_indexing/ And the docs are at: https://svn.boost.org/svn/boost/sandbox/SOC/2008/spacial_indexing/libs/spat… The future work now is huge. We have some ideas about integrating this in some way to multindexes, and we want to implement also a 'packed' version of the rtree to improve bulk-loading times among another things. Finally, I would like to thank to Boost for allowing me to be part of this year's SOC. And specially to my mentor Hartmut Kaiser for all his help during the program. -- federico j. fernandez

8 13

[endian] superfluous boost::operators<> ?
by Roland Schwarz 27 Mar '09

27 Mar '09

I discovered, that the following will not compile: unsigned u; ulittle32_t u1; ulittle32_t u2; u = 1; u1 = 1; u2 = u1 + u; The compiler complains about not being able to resolve similar conversions. My guess is, that using boost::operators<> _and_ providing type conversion operators at the same time is causing this. I think it should be enough to define the essential operators in cover_operators template, and omit boost::operators<> at all. At least I am not able to find any problems with this, since the compiler adjusts the arguments (using the provided type conversion operators?) and calls the built in operators, thereby resolving ambiguity. Any thoughts? -- _________________________________________ _ _ | Roland Schwarz |_)(_ | aka. speedsnail | \__) | mailto:roland.schwarz@chello.at ________| http://www.blackspace.at

2 1

Dependance obetween boost::mpi, boost::serialization and iostreams
by Joel Falcou 26 Mar '09

26 Mar '09

Boost::MPI uses Boost::serialization for marshalling data and sending them in a pervasive way. I have a small scale implementation of MPI running on the Cell processor and I'm trying to patch boost::mpi to use it. However, as serialization seems ot use iostream or sstream at some point, the resulting executable blow up the 256Kb limits of SPE local store. How deep is iostream needed by serialization and how can I limit this dependance so I can have a proper Cell-enabled boost::mpi ? -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35

2 2