[boost] [graph]

Subject: [boost] [graph]
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-02-08 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 small-world 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]