[boost] [graph] Graph and AdjacencyMatrix

Subject: [boost] [graph] Graph and AdjacencyMatrix
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-07-17 08:25:38

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_at_[hidden]