[boost] [GSoC 2010]: BGL Graph Connectives ideas

Subject: [boost] [GSoC 2010]: BGL Graph Connectives ideas
From: Yaroslav Vorontsov (DarthYarius_0990_at_[hidden])
Date: 2010-04-02 15:03:57

>
> 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_at_[hidden]
>
>    
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_at_[hidden]