Re: [boost] [graph] Graph and AdjacencyMatrix

Subject: Re: [boost] [graph] Graph and AdjacencyMatrix
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-07-17 15:04:30

On Fri, 17 Jul 2009, Andrew Sutton wrote:

>>
>>  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).
>
>
> But as a refinement from Graph, you still have to provide edge descriptors.
> Maybe Graph isn't the best-conceived concept.  Why should you define an
> edge_descriptor if your implementation doesn't have edges? Maybe what we
> actually have is  something more like this:

Oddly enough, you actually have to provide all of the iterator types, even 
if some of them are void and unsupported.  I don't think we really have 
graphs without edges, but we don't require access to them in any 
particular way in the base concepts.

> concept VertexGraph<typename G> {
>  typename vertex_descriptor;
>  // ...
> };
> concept EdgeGraph<typename G> : VertexGraph<G> {
>  typename edge_descriptor;
>  // ...
> }
> concept AdjacencyGraph<typename G> : VertexGraph<G> {
>  Iterator adjacenct_vertex_range;
>  requrires SameType<Iterator::reference, vertex_descriptor>;
>  adjacenct_vertex_range adjacenct_vertices(vertex_descriptor v, G const&
> g);
> };

To me, this is too fine-grained, since almost no algorithms would require 
these concepts.  EdgeGraph might be useful as a common location for 
source() and target(), which are independently in several unrelated 
concepts, however.

> 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?
>
>
> You're right... Adding edge() to Graph would be bad for the reasons above -
> that you can build a graph without edges. Adding edge() to EdgeGraph would
> be viable.
>
> I would say that edge() is more like a generic algorithm, except that it
> doesn't have a generic definition. It has to be implemented specificaally
> for every graph data structure. The operation is kind of in a weird place -
> I guess it's a little bit like swap().

It has a few generic definitions, as you show later.

> Maybe one way to look at it is to classify its implementations by
> complexity: there's AdjacencyMatrix::edge (O(1)), there's
> IncidenceGraph::edge (O(deg(v))), and then there's an EdgeList::edge (O(E)).
>
> The only reason I would consider moving edge() up the hiearchy (into
> EdgeGraph per se) is not because it can be efficiently implemented, but
> because it's a valid operation for any graph that defines edges, and it
> helps define the clarify the semantics of edge descriptors via source() and
> target().

Why not write it as a generic algorithm that dispatches on the graph 
concept, and can be overloaded for specific graph types?  That would avoid 
hand-writing it in many cases, while making it available for users and 
algorithms.

> Parallel edges aren't handled very gracefully in the BGL right now! I always
> figured that we needed something like:
>
> concept ParallelEdgeGraph<typename G> : EdgeGraph<G> {
>  Iterator parallel_edge_range;
>  requires SameType<Iterator::reference, edge_descriptor>;
>  parallel_edge_range edges(vertex_descriptor u, vertex_descriptor v, G
> const& g);
> }

We have that through a tag.  The edges() function you list there is named 
"edge_range", and at least some graphs provide it.  It is really hard to 
implement efficiently with parallel edges for graphs that don't sort their 
out edges by target, though.

> There aren't too many algorithms that use edge() directly. There may be some
> that essentially implement edge() on their own by iterating over out edges
> (common_subgraphs does). It's really hard to determine the extent.

That one used to use edge() and was changed to allow graphs that don't 
have it.  If edge() were provided as a generic algorithm, it would 
probably be switched back.

-- Jeremiah Willcock