Boost logo

Boost :

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?


Boost list run by bdawes at, gregod at, cpdaniel at, john at