Re: [Boost-users] How to test whether a vertex or edge exists?

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.

D.

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