Re: [boost] [graph]

Subject: Re: [boost] [graph]
From: Doug Gregor (doug.gregor_at_[hidden])
Date: 2009-02-09 10:02:20

On Sun, Feb 8, 2009 at 9:03 AM, Andrew Sutton <andrew.n.sutton_at_[hidden]> wrote:
> 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.

This is great!

> 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."

Ah, interesting. That is helpful.

> 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.

Quickbook documentation for BGL would be *wonderful*. Perhaps someone
from the Boost Documentation project would like to help out (?).

  - Doug