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 12:30:55

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

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);
};

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

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

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);
}

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.

Andrew Sutton
andrew.n.sutton_at_[hidden]