[boost] vertex descriptors, LessThanComparable...

From: jsiek_at_[hidden]
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.

VertexListGraph
  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
  of vertices).

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.

Cheers,

Jeremy