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. Andrew Sutton andrew.n.sutton@gmail.com

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.

Does that mean that mean that we minimally require VertexListGraph<G> (in what I will not refer to as C?? syntax). I know of only one adaptor that doesn't model VertexListGraph (edge_list), but that's just a weird data structure anyway. Actually Michael Lopez (SoC09, function graphs) has cases where a function does not model this concept, but that's a weird data structure too. Maybe vertex is more like swap(), where we have a general algorithm with lots of specializations?

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).

Logically that sounds about right. The following is purely hypothetical. template <EdgeListGraph G> pairedge(Vertex u, Vertex v, G const& g) { for(...) { if source(e, g) == u && target(e, g) == v) return {e, true}; } } template <AdajcencyMatrix G> pair edge(Vertex u, Vertex v, G const& g) { return g(u, v); } template <IncidenceGraph G> requires Range pair edge(Vertex u, Vertex v, G const& g) { /* linear search in out_edges */ } template <IncidenceGraph G> requires SortedRange pair edge(Vertex u, Vertex v, G const& g) { /* binary search in out_edges */ } template <IncidenceGraph G> requires AssociativeContainer pair edge(Vertex u, Vertex v, G const& g) { /* use x.find() */ } We can map these back to tag dispatch with a little bit of work. The biggest problem I see here is that the BGL doesn't let us easily reason about the internal properties of out edge lists for adjacency list-like data structures or adaptors. It would be one thing to return the a legitimate range or reference to a container, but that's not where we are right now. One might require member functions for efficient edge queries like my theoretical adjacency_matrix () overload. That would certainly reduce the requirements on overloads, but leaves us more or less where we are now (maybe?) I wonder if this also admits the existence of an AdjacencyList concept. Andrew Sutton andrew.n.sutton@gmail.com