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