Re: [boost] [graph] Graph and AdjacencyMatrix

Subject: Re: [boost] [graph] Graph and AdjacencyMatrix
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-07-17 21:39:03

> 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.

That might strike me as having the potential for refactoring :)

>
> concept VertexGraph<typename G> { };
>> concept EdgeGraph<typename G> : VertexGraph<G> { }
>> concept AdjacencyGraph<typename G> : VertexGraph<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.

It might be a viable approach if the BGL included "edgeless"  graphs and
graph algorithms. Since we don't...

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().
>>
>
>  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)).
>>
>
> 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.

I think this is a good idea. Unfortunately, it's going to require some
serious restructuring.

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.

Really? I never knew even that function existed. It looks like it's only
defined for csr and adj_list. It seems like we could probably give that the
same treatment as the edge() query.

Are there any other "algorithms" hiding out there? I think the vertex()
function may be viable.

Hopefully I'll find the time some next week to write up a full proposal and
list of changes based on this discussion. We'll see what happens from there.

Andrew Sutton
andrew.n.sutton_at_[hidden]