Boost logo

Boost :

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

> 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, gregod at, cpdaniel at, john at