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
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk