Boost logo

Boost Users :

From: Daniel Mitchell (danmitchell_at_[hidden])
Date: 2006-05-07 20:35:35

On Sunday 07 May 2006 17:09, sean yang wrote:
> Yeah, I agree with you. For the first question, I think I'd better to save
> the strings to an vector and build a relationship between strings in this
> vector and vertices in the graph.

I think that's a reasonable approach. I suggested a set since it would
automatically take care of the problem of duplicates, but you obviously know
your application better than I do.

> Thanks for the reply. I have a question for concept requirements.
> For example, if I declare a Graph representation by
> typedef adjacency_list<vecS, vecS, directedS,
> property<vertex_color_t, default_color_type>,
> property<edge_weight_t, int> > Graph;
> How can I know if this Graph satisfies the reqirement of a certain concept,
> say AdjacencyMatrix ?

The answer is slightly complex because of the nature of concepts. A concept is
a set of syntactic and semantic requirements a type must satisfy to qualify
as an argument to a generic function. For example, if objects of type Graph
are to qualify as arguments to a function that requires the AdjacencyMatrix
concept, the expression edge( u, v, g ) must compile. This can obviously be
checked by the compiler, and the BGL makes it easy to do so:

#include <boost/graph/graph_concepts.hpp>
boost::function_requires<boost::AdjacencyMatrixConcept<Graph> >();

AdjacencyMatrixConcept is called a concept-checking class, and the above will
only compile if Graph satisfies the syntactic requirements of
AdjacencyMatrix. There are similar concept-checking classes for
IncidenceGraph, VertexListGraph, etc.

The compiler cannot, however, check that edge( u, v, g ) does the right thing,
so you also have to rely on the documentation for Graph. If you look at the
documentation for adjacency_list, it says that adjacency_list models the
VertexListGraph and EdgeListGraph concepts. Unfortunately, in this case the
documentation seems to be incomplete*, since adjacency_list also models
IncidenceGraph and AdjacencyGraph, and sometimes BidirectionalGraph. So your
best bet is to use the concept-checking classes.

Hope that helps.


*It isn't clear from the documentation if VertexListGraph is a refinement of
IncidenceGraph and AdjacencyGraph or not. The language is in the "Design
Rational" seems to imply that it is, but those concepts do no appear in the
list of concepts refined by VertexListGraph.

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at