Re: [boost] Graph_traits and Graph

From: Douglas Gregor (dgregor_at_[hidden])
Date: 2005-02-02 09:52:17

On Feb 2, 2005, at 4:20 AM, Jannel Rémi wrote:
> Now, if i want to wite an algorithm which will search for all the 
> vertices for example, i'll have to use my Graph as a template and i'll 
> get the vertex type for example using
> typedef typename graph_traits<Graph>::vertex_descriptor 
> vertex_descriptor;
>
> That's why I wanted to ask you why this method is used instead of just
>
> typedef typename Graph::vertex_descriptor vertex_descriptor;
>
> used in the class graph_traits definition.

Using graph_traits allows the Graph library to work with more graph 
data types. For instance, say you have a graph type that you wrote a 
long time ago.
You could adapt this graph type to work with the BGL by adding the 
right functions in its namespace (e.g., vertices, out_edges, etc.) and 
by creating a graph_traits specialization for it (to say what the types 
are). All of these changes are external to the graph type itself, so 
you should be able to do it without even touching the source code for 
the graph type! If we always required that the "vertex_descriptor" type 
be a member of the graph type, then making a graph work with the BGL 
would require changing the graph type itself, and that's not always 
possible.

For a neat example of this, check out the LEDA adaptors in the BGL. 
LEDA is a popular commercial C++ graph library. We were able to make 
its graphs work with the BGL without having to change any of LEDAs 
code.

        Doug