On Fri, 17 Jul 2009, Andrew Sutton wrote:
I suggest that we modify the Graph concept to define the following valid
expressions.
edge(u, v, g) -> pair<edge_descriptor, bool> source(e, g) -> vertex_descriptor target(e, g) -> vertex_descriptor
It turns out that the current graph concepts do not actually require edges to exist; even AdjacencyGraph does not require edges at all (each vertex just links to adjacent vertices with the edges implicit).
But as a refinement from Graph, you still have to provide edge descriptors. Maybe Graph isn't the best-conceived concept. Why should you define an edge_descriptor if your implementation doesn't have edges? Maybe what we actually have is something more like this:
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.
concept VertexGraph<typename G> { typename vertex_descriptor; // ... }; concept EdgeGraph<typename G> : VertexGraph<G> { typename edge_descriptor; // ... } concept AdjacencyGraph<typename G> : VertexGraph<G> { Iterator adjacenct_vertex_range; requrires SameType<Iterator::reference, vertex_descriptor>; adjacenct_vertex_range adjacenct_vertices(vertex_descriptor v, G const& 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.
I strongly disagree with adding the edge() function to Graph. The base
Graph concept does not require any topology information to be available at all. Also, how would parallel edges be handled?
You're right... Adding edge() to Graph would be bad for the reasons above - that you can build a graph without edges. Adding edge() to EdgeGraph would be viable.
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().
It has a few generic definitions, as you show later.
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)).
The only reason I would consider moving edge() up the hiearchy (into EdgeGraph per se) is not because it can be efficiently implemented, but because it's a valid operation for any graph that defines edges, and it helps define the clarify the semantics of edge descriptors via source() and target().
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.
Parallel edges aren't handled very gracefully in the BGL right now! I always figured that we needed something like:
concept ParallelEdgeGraph<typename G> : EdgeGraph<G> { Iterator parallel_edge_range; requires SameType<Iterator::reference, edge_descriptor>; parallel_edge_range edges(vertex_descriptor u, vertex_descriptor v, G const& g); }
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.
There aren't too many algorithms that use edge() directly. There may be some that essentially implement edge() on their own by iterating over out edges (common_subgraphs does). It's really hard to determine the extent.
That one used to use edge() and was changed to allow graphs that don't have it. If edge() were provided as a generic algorithm, it would probably be switched back. -- Jeremiah Willcock