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
- 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
- An exterior_property class that helps hides some of the weirdness
with exterior properties.
- A constant-valued property map - useful for naturally unweighted
- 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:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk