[graph] Graph and AdjacencyMatrix
There was a bug reported (#3266) that brings up a valid problem with the BGL concept hierarchy and the edge() function. It turns out that virtually every graph defines the edge() function, but only the AdjacencyMatrix concept actually requires it as part of its interface. This means that every algorithms (e.g., Kolomogrov's Max Flow) that uses the edge() function implicitly requires graphs to model the AdjacencyMatrix concept. Since we're addressing edge-related operations, we could also take this time to clean up some of the confusion on source, target, and edge descriptors. Specifically, source() and target() are always defined and that edge descriptors - even those for undirected graphs - imply directionality. Basically, it doesn't matter if the underlying graph implementation defines source and target, the adaptation to the BGL /has to/ in order for even the most basic algorithms to work correctly. 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 And the following semantics: source(edge(u, v, g), g) == u target(edge(u, v, g), g) == v edge, source, target = O(E) // upper bound on an edge list. Basically this requires the edge() function to preserve the source/target ordering of the vertices in the edge that it describes. I don't believe that any graph implementations or adaptors need to be modified in order to support these changes. We can then modify the AdjacencyMatrix concept to document a refinement of the edge function, specifically that it return in O(1) time. Does anybody see any obvious problems with these changes? Andrew Sutton andrew.n.sutton@gmail.com
On Fri, 17 Jul 2009, Andrew Sutton wrote:
There was a bug reported (#3266) that brings up a valid problem with the BGL concept hierarchy and the edge() function. It turns out that virtually every graph defines the edge() function, but only the AdjacencyMatrix concept actually requires it as part of its interface. This means that every algorithms (e.g., Kolomogrov's Max Flow) that uses the edge() function implicitly requires graphs to model the AdjacencyMatrix concept.
Kolmogorov's algorithm appears to only use edge() as an optimization, and could probably use the reverse_edge_map to avoid needing edge() at all.
Since we're addressing edge-related operations, we could also take this time to clean up some of the confusion on source, target, and edge descriptors. Specifically, source() and target() are always defined and that edge descriptors - even those for undirected graphs - imply directionality. Basically, it doesn't matter if the underlying graph implementation defines source and target, the adaptation to the BGL /has to/ in order for even the most basic algorithms to work correctly.
That is fine, as long as it doesn't break anything.
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). 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? What complexity would be required of edge()? Lastly, there are graphs, such as the new interface to compressed_sparse_row_graph, that do not provide edge() at all because it would require a linear search to do. The edge_range() function would be impractical to implement as well (it would require a filtered_iterator over all out edges of the source vertex, filtering them by target).
And the following semantics:
source(edge(u, v, g), g) == u target(edge(u, v, g), g) == v edge, source, target = O(E) // upper bound on an edge list.
Basically this requires the edge() function to preserve the source/target ordering of the vertices in the edge that it describes. I don't believe that any graph implementations or adaptors need to be modified in order to support these changes.
We can then modify the AdjacencyMatrix concept to document a refinement of the edge function, specifically that it return in O(1) time.
Which algorithms actually need the edge() function? Are there any that are intended for sparse graphs and where edge lookup is essential? Are there any that would change behavior if edge directionality was changed? -- Jeremiah Willcock
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: 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); }; 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(). 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(). 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); } 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. Andrew Sutton andrew.n.sutton@gmail.com
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
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
participants (2)
-
Andrew Sutton -
Jeremiah Willcock