[boost] Re: Graph concepts

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?

Cheers,

Jeremy