Oddly enough, you actually have to provide all of the iterator types, even if some of them are void and unsupported. I don't think we really have graphs without edges, but we don't require access to them in any particular way in the base concepts.
That might strike me as having the potential for refactoring :)
concept VertexGraph<typename G> { };
concept EdgeGraph<typename G> : VertexGraph<G> { } concept AdjacencyGraph<typename G> : VertexGraph<G> { };
To me, this is too fine-grained, since almost no algorithms would require these concepts. EdgeGraph might be useful as a common location for source() and target(), which are independently in several unrelated concepts, however.
It might be a viable approach if the BGL included "edgeless" graphs and graph algorithms. Since we don't... I would say that edge() is more like a generic algorithm, except that it
doesn't have a generic definition. It has to be implemented specificaally for every graph data structure. The operation is kind of in a weird place - I guess it's a little bit like swap().
Maybe one way to look at it is to classify its implementations by
complexity: there's AdjacencyMatrix::edge (O(1)), there's IncidenceGraph::edge (O(deg(v))), and then there's an EdgeList::edge (O(E)).
Why not write it as a generic algorithm that dispatches on the graph concept, and can be overloaded for specific graph types? That would avoid hand-writing it in many cases, while making it available for users and algorithms.
I think this is a good idea. Unfortunately, it's going to require some serious restructuring. We have that through a tag. The edges() function you list there is named
"edge_range", and at least some graphs provide it. It is really hard to implement efficiently with parallel edges for graphs that don't sort their out edges by target, though.
Really? I never knew even that function existed. It looks like it's only defined for csr and adj_list. It seems like we could probably give that the same treatment as the edge() query. Are there any other "algorithms" hiding out there? I think the vertex() function may be viable. Hopefully I'll find the time some next week to write up a full proposal and list of changes based on this discussion. We'll see what happens from there. Andrew Sutton andrew.n.sutton@gmail.com