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