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@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@mail.ru