[boost] Re: Graph concepts

From: Dave Abrahams (abrahams_at_[hidden])
Date: 1999-12-11 19:51:15

> 
> I've created a hierarchy of graph concepts for organizing 
> the basic operations. I've updated the document in the
> vault.

This seems much better to me, though I'm now wondering if I really read what
I thought I had read. Before, it seemed like you were misusing the term
"refinement" such that more refined the concept, the fewer the requirements
on it.

> Graph -> EdgeGraph -> VertexGraph -> VertexListGraph
>                   \
>                    -> EdgeListGraph
>
> Graph
>   empty for now, just a placeholder for comments about graph objects
>   in general. Later more traits stuff can be added here.
>
> EdgeGraph
>   source(e,g)
>   target(e,g)
>
> VertexGraph refines EdgeGraph
>   adj(v,g)
>   out_edges(v,g)
>
> VertexListGraph refines VertexGraph
>   vertices(g)
>
> EdgeListGraph refines EdgeGraph
>   edges(g)

Looking at my Python code for graphs I notice that I assumed there would be
a use for a graph where you could find out in O(1) time whether there was an
edge between any given pair of nodes. I also notice I didn't make use of the
corresponding functionality in any of the limited number of algorithms I
implemented. Perhaps you or Dietmar would care to comment on this?

-Dave