Re: [Boost-users] [BGL] clustering coefficient implementation

Subject: Re: [Boost-users] [BGL] clustering coefficient implementation
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-06-07 07:33:42

>
> After giving up for the first time approximately 1,5 year ago due to so to
> speak a bit discouraging documentation, for a couple of weeks I'm trying to
> work things out with BGL.
> I implemented a clustering coefficient calculation algorithm for graphs [
> http://emreguney.googlepages.com/clustering_coefficient.hpp ] (only
> afterwards I discovered that Andrew Sutton has already implemented one
> waiting to be deployed). I would really appreciate any comments&suggestion
> about the code (quality, missing concept checks, consistency with genericity
> of BGL, ...).

While my clustering_coefficient is in trunk, it's not really an official
component just yet since the documentation hasn't been merged. Actually I'm
supposed to be in the process of converting all of the docs to quickbook,
but have had to postpone the work while some fairly large changes come
through the pipeline (plus, I'm really busy, otherwise).

> Although I thought, this implementation would not work on AdjacencyMatrix
> graphs, it works. Therefore, AdjacencyMatrix graphs do provide
> adjacent_vertices and out_edges methods. In the documentation (Graph
> Concepts page), however, I understand that AdjacencyMatrix Graph is a
> refinement of Graph (not IncidenceGraph or AdjacencyGraph) and do not
> provide such methods. Am I missing or misinterpreting something?
>

Concepts don't restrict the interface of a class. A concept only describes
what interface is required of a class within a generic algorithm (function
template). Just because adjacency_matrix models the AdjacencyMatrix concept,
doesn't mean that it can't also be a model of IncidenceGraph (I think it
is).

In fact, to tell a dirty secret about the BGL, virtually every graph class
and graph adaptor supports the interfaces required by every concept. For
example, all graph classes define an edge(u, v, g) overload.

Andrew Sutton
andrew.n.sutton_at_[hidden]