Re: [boost] [graph] Graph and AdjacencyMatrix

Subject: Re: [boost] [graph] Graph and AdjacencyMatrix
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-07-17 10:16:51

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