Boost logo

Boost :

From: jsiek_at_[hidden]
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, gregod at, cpdaniel at, john at