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
On Sun, Feb 8, 2009 at 9:03 AM, Andrew Sutton <andrew.n.sutton@gmail.com> 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
Hi Andrew ! On Sunday 08 February 2009, Andrew Sutton wrote:
Update on the BGL. I've just ported my SOC work en masse from 2007 to the BGL trunk. New features include:
Cool ;-)) I'll certainly take a closer look at it.
Questions? Comments?
Some minor glitch: This checkin broke my gcc build with -Wextra -pedantic: boost/boost/graph/numeric_values.hpp:45: error: extra ';' boost/boost/graph/numeric_values.hpp:46: error: extra ';' boost/boost/graph/numeric_values.hpp:47: error: extra ';' The macro BOOST_GRAPH_SPECIALIZE_NUMERIC_FLOAT already contains a finishing ";", so gcc bails out. It would be nice if you could remove the extra semicolon. Yours, Jürgen -- * Dipl.-Math. Jürgen Hunold ! Ingenieurgesellschaft für * voice: ++49 511 262926 57 ! Verkehrs- und Eisenbahnwesen mbH * fax : ++49 511 262926 99 ! Lister Straße 15 * juergen.hunold@ivembh.de ! www.ivembh.de * * Geschäftsführer: ! Sitz des Unternehmens: Hannover * Prof. Dr.-Ing. Thomas Siefer ! Amtsgericht Hannover, HRB 56965 * PD Dr.-Ing. Alfons Radtke !
participants (3)
-
Andrew Sutton -
Doug Gregor -
Juergen Hunold