Date: 1999-12-11 20:44:18
So I think it makes sense to add the requirement of LessThanComparable
to vertex descriptors for *some* graph types.
Vertex descriptors are LessThanComparable, and the
iterator-range returned by vertices() is ordered.
OrderedVertexListGraph (this is new)
The iterator-range returned by adj() and out_edges() (according
to the target vertex) is ordered.
Perhaps the edge() function should be added to this concept,
but with logarithmic time complexity. It could even be
added to the VertexListGraph, but then it would have linear
complexity in the length of the edge list (which for a sparse
graph would actually be short, so the complexity is
still in some sense constant with respect to the number
AdjacencyMatrix would refine OrderedVertexListGraph.
Of course, I don't want to add requirements that shouldn't be there,
so shout if this seems overly restrictive. I'm just trying to bring
out properties that might be usefull for algorithms.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk