On Fri, 4 Sep 2009, Andrew Sutton wrote:
If I am not wrong, then the vertex(std::size_t i, Graph) function is required in no graph concept at all. However, adjacency_list defines it and csr-graphs use it ...
Did I overlook something or shouldn't the function belong to some graph concept?
I have now made the CSR graphs not use it for other graphs being copied into CSR format. There should not be any other algorithms that use it; however, it is provided by almost all graphs. It is the inverse function to the vertex_index property map. Some graphs also have edge_from_index which is the inverse of the edge_index property map.
I think this function falls into the same category as edge(), which I'm starting to believe is exactly like iterator operations distance(), advance(), next() and prev(). Not part of a concept, not a full-fledged algorithm, but nonetheless an operation that can be implemented for every graph, with varying degrees of efficiency.
I agree. Should vertex() by default just be vertex(i, g) = {vertex_iterator it = vertices(g).first; advance(it, i); return *it;}? I don't think we can guarantee that matches the vertex_index map, though. For edge(), I imagine we should have a trait for whether the out edges of a vertex are sorted, and then we can use logarithmic or linear-time algorithms. Particular graphs can specialize it for their own types (such as for adjacency_matrix's constant-time version). The edge_range() function should be the same thing, except that it requires that the edges are sorted in some way so that parallel edges are together (or we can use a filtered_iterator which would be a lot slower). -- Jeremiah Willcock