
Boost : 
Subject: Re: [boost] [graph] Graph and AdjacencyMatrix
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20090717 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 bestconceived 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 finegrained, 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
handwriting 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk