Date: 1999-12-11 20:03:53
Dave Abrahams writes:
> 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.
No, I did mean refinement in the sense of more requirements,
e.g. VertexGraph has more requirements than EdgeGraph.
Perhaps I confused you by changing "Graph" from all requirements
to no requirements. Also, the direction of the arrows may be
confusing? (the arrow direction is the opposite of the refinement).
> > 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?
To get that information in O(1) requires an adjacency-matrix or
something similar (basically need a dense graph representation and
random-access-iterators). Perhaps the thing to do is add that as
another concept, with the following operations:
AdjacencyMatrix: refines both VertexListGraph and EdgeListGraph
bool flag = has_edge(v,v,g)
e = edge(v,v,g)
Dietmar, what do you think about this?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk