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@gmail.com