[boost] [graph] SoC update

From: Andrew Sutton (asutton_at_[hidden])
Date: 2007-08-27 12:10:33

To those interested,		// sorrt

Alas summer is over. and the students have returned to clog the  
hallowed (and somewhat narrow) halls of my building... No more quiet  
days in my lab hacking out Boost.Graph code and documentation.

On the brighter side, I have finished - at least to the satisfaction  
of mentor Jeremy Siek and myself  - the goals that I had originally  
planned for my Summer of Code project. The end results are:

- Two new graph classes (undirected and directed) which are intended  
to make the library more approachable for new developers
- A suite of graph measures including degree and closeness  
centrality, mean geodesic distance, eccentricity, and clustering  
coefficients.
- An algorithm for visiting all cycles in a directed graph (Tiernan's  
from 1970ish). It works for undirected graphs too, but reports cycles  
twice (one for each direction).
- An algorithm for visiting all the cliques a graph (Bron&Kerbosch).  
Works for both directed and undirected.
- Derived graph measures radius and diameter (from eccentricity) and  
girth and circumference (from Tiernan), and clique number (from  
Bron&Kerbosch).
- An exterior_property class that helps hides some of the weirdness  
with exterior properties.
- A constant-valued property map - useful for naturally unweighted  
graphs.
- A noop-writing property map - useful when you have to provide an  
argument, but just don't care about the output.

There are also a couple of other informal introductions that need to  
be polished, documented and tested. These include:

- Graph cores - Implemented by David Gleich (@Stanford University)
- Deterministic graph generators - capable of creating or inducing  
specific types of graphs over a vertex set (e.g., star graph, wheel  
graph, prism graph, etc). There are several other specific types that  
could be added to this, but I haven't had the time just yet.

There are also some introductions in this package that can - or  
probably should be - backported to existing code. Specifically,  
issues dealing with vertex and edge indices and how they are mapped  
into exterior properties.

There are also a couple of changes to the current codebase that can  
be immediately applied. Specifically, this includes new and updated  
concept checking classes and a completely new archetype system for  
concept coverage testing.

I've also written quickbook docs for much of the new code - and have  
been slowly folding the older docs in - it's a long process. Also, if  
you aren't on a Linux box, you can't build the new docs since I'm  
using Makefiles, graphviz and latex to generate images. So, the up-to- 
date stuff is here:

http://warhol.sdml.cs.kent.edu/~asutton/boost/libs/graph/doc/html/

Most of the "good" docs are toward the bottom of the ToC.

I have more to say on the topic, but I will split it into a second  
email since this is pretty long.

Andrew Sutton
asutton_at_[hidden]