
Boost : 
Subject: [boost] [graph]
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 20090208 12:03:22
Update on the BGL. I've just ported my SOC work en masse from 2007 to the
BGL trunk. New features include:
* [un]directed_graph classes  wrappers around adjacency lists. These serve
as introductory classes to help with prototyping. They also try to hide all
of the problems with vertex indices and property maps  as in every
algorithm requires vertex maps, but only VerteSet == vecS provides them.
* degree_centraility  algorithms for computing the degree centrality of
vertices in a graph. Includes measures of influence and prestige.
* closeness_centraltiy  algoritghms for computing the closeness centraility
(based on SSPs) for vertices in a graph.
* geodesic_distance  Computes the smallworld and mean geodesic distances
of graphs.
* eccentricity  Algorithms for computing eccentricity, and the radius and
diameter of the graph.
* clustering_coefficient  Returns the clustering coefficient of a vertex or
the average CC for the entire graph.
* core_numbers  Partitioning of a graph into cores based on vertex degree
(from David Gleich)
* all_cycles  Find and visit all cycles in a graph (Tiernan)
* all_cliques  Find and visit all cliques in a graph (Bron & Kerbosch)
* exterior_properties  A new framework for helping define exterior
properties (and property maps) for graphs.
New graph concepts:
* VertexIndexGraph  any graph for which get(vertex_index, g) is valid
* EdgeIndexGraph  any graph for which get(edge_index, g) is valid
Since nearly every algorithm requires a vertex index map in one way or
another, these may as well be concepts. Also, its a convenient documentary
artifact that lets you write, "If your graph is not a *IndexMap, then you
must provide an index map as an exterior property."
Documentation for these features is forthcoming. Its part of my project to
(finally) migrate the BGL docs over to quickbook. There are tests for most
of these features  some are in progress  others are woefully inadequate
and under development. Since I'm generally pretty busy, these will probably
materialize slowly. I'm aiming at 1.40.
Questions? Comments?
Andrew Sutton
andrew.n.sutton_at_[hidden]
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk