- Boost - lists.boost.org

[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 26 Mar '09

26 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

[config] A question about BOOST_NO_NESTED_FRIENDSHIP
by Andrey Semashev 26 Mar '09

26 Mar '09

Hi, I've been merging my recent additions to the release branch and came across the BOOST_NO_NESTED_FRIENDSHIP macro, which hasn't been merged. Looking at its description and test, I'm not certain whether this macro actually flags a compiler deficiency, rather than valid behavior. Here's the description: If the compiler fails to support access to private members from nested classes And the test: class A { static int b; class B { int f() { return b; } }; }; To my understanding, 11.8 says that it shouldn't compile, as B doesn't have any privileged access to A::b. Am I missing something?

2 2

BOOST_NO_INTRINSIC_INT64_T
by Robert Ramey 26 Mar '09

26 Mar '09

boost config includes BOOST_NO_INTRINSIC_WCHAR_T. boost Is there any chance we might see BOOST_NO_INTRINSIC_INT64_T appear in the near future? Robert Ramey

3 7

best way to serialize a GIL image
by Kenny Riddile 26 Mar '09

26 Mar '09

I have a class which contains a boost::gil::rgba8_image_t instance that I'd like to serialize via boost.serialization. I'm just wondering what the optimal way to do this would be. I have a couple naive ideas, but they involve additional copies of pixel data that aren't conceptually necessary.

2 1

[asio] need help with timer crash please
by bnv＠nc.rr.com 26 Mar '09

26 Mar '09

I'm seeing two distinct crashes (gdb output below) on expiration of a deadline timer, and could use some help identifying possible reasons. The timer has not been deleted. The timer expired once before and was later rescheduled using expires_from_now() and async_wait(). The timer is only accessed by threads in io_service::run(), and is protected by a mutex. Form the gdb output, I'm guessing the timer is being removed on expiration and the internal structures have somehow been trashed. Any pointers to possible explanations would be appreciated. crash 1... Program received signal SIGSEGV, Segmentation fault. [Switching to thread 3500.0x83c] 0x5ae9a800 in ?? () (gdb) bt full #0 0x5ae9a800 in ?? () No symbol table info available. #1 0x005ae5f7 in boost::asio::detail::timer_queue<boost::asio::time_traits<boos t::posix_time::ptime> >::complete_timers (this=0x5387f74) at /usr/local/include/boost-1_38/boost/asio/detail/timer_queue.hpp:205 this = ( timer_queue<boost::asio::time_traits<boost::posix_time::ptime> > * const) 0x 5387f74 this_timer = ( timer_queue<boost::asio::time_traits<boost::posix_time::ptime> >::timer_base *) 0x53a4faf #2 0x053a4fb7 in ?? () No symbol table info available. #3 0x1dcdcb20 in ?? () No symbol table info available. #4 0x005bf1c0 in boost::asio::detail::select_reactor<false>::complete_operation s_and_timers (this=0x658, lock=@0x1dcd9498) at /usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_vector.h:462 this = (class select_reactor< false> * const) 0x658 this = (scoped_lock<boost::asio::detail::posix_mutex> * const) 0xa i = 500011328 #5 0x00000000 in ?? () No symbol table info available. (gdb) crash 2... Program received signal SIGSEGV, Segmentation fault. [Switching to thread 1320.0xa08] 0x005adff1 in boost::asio::detail::timer_queue<boost::asio::time_traits<boost::p osix_time::ptime> >::remove_timer (this=0x5387f74, t=0x53aac70) at /usr/local/include/boost-1_38/boost/asio/detail/timer_queue.hpp:399 399 t->prev_->next_ = t->next_; (gdb) bt full #0 0x005adff1 in boost::asio::detail::timer_queue<boost::asio::time_traits<boos t::posix_time::ptime> >::remove_timer (this=0x5387f74, t=0x53aac70) at /usr/local/include/boost-1_38/boost/asio/detail/timer_queue.hpp:399 this = ( timer_queue<boost::asio::time_traits<boost::posix_time::ptime> > * const) 0x 5387f74 index = 87735592 it = {_M_node = 0x53aad20} #1 0x00000002 in ?? () No symbol table info available. #2 0x00000000 in ?? () No symbol table info available. (gdb) Thanks, Brian

1 0

Function Input Iterator Implementation (Interest Check, Submission)
by Dean Michael Berris 26 Mar '09

26 Mar '09

Hi Everyone, Let's say I have a function object that I wrap in a generator iterator and I want it to signal that it's done generating values or that there's nothing more to generate. In the current version of the Generator Iterator, there's no way to create an iterator that has a bound. This is great if you want an infinite input iterator, but there are cases where you might want one that is bounded (or at least, create a pair of iterators representing a range gotten from an infinite source). I've attached the implementation of a proposed 'function_input_iterator' which allows the creation of bounded input ranges from a nullary function object which models the Generator concept. This doesn't aim to replace the generator_iterator implementation, but rather is an implementation that allows for the following use case: ---->8-- #include <boost/function_input_iterator.hpp> #include <iostream> #include <iterator> #include <algorithm> struct generator { typedef int result_type; generator() { srand(time(0)); } result_type operator() () const { return rand(); } }; using namespace std; using namespace boost; int main(int argc, char * argv[]) { generator f; copy( make_function_input_iterator(f, infinite()), make_function_input_iterator(f, infinite()), ostream_iterator<int>(cout, " ") ); return 0; } ---->8-- In the attached implementation, I've implemented a simple 'infinite' class that supports the post- and pre-increment operator and comparison between two infinite instances always result to false. This allows the use of infinite() as a dummy state variable internal to the function_input_iterator to make sure that the created range resulting from the iterator is infinite. Another use case enabled is given below: ---->8-- copy( make_function_input_iterator(f, 0), make_function_input_iterator(f, 10), ostream_iterator<int>(cout, " ") ); ---->8-- This creates a range of 10 random numbers. If we were going to populate an STL container using the range constructors, we can do: vector<int> random_ints( make_function_input_iterator(f, 0), make_function_input_iterator(f, 10) ); I'm currently in the process of writing documentation in RST format. I'm submitting this implementation to Boost in case there's interest for inclusion. Question: Does a library like this qualify for a fast-track review? What is the criteria for inclusion to an existing library like Boost.Iterators? Thanks in advance and I hope this helps! -- Dean Michael Berris | Software Engineer, Friendster, Inc. blog.cplusplus-soup.com | twitter.com/mikhailberis | linkedin.com/in/mikhailberis | profiles.friendster.com/mikhailberis | deanberris.com

1 1