Re: [boost] VertexListGraph (Was: a small bug in BGL doc)

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-02-02 10:24:53

Hi Hankel,

On Fri, 2 Feb 2001 hankel_o_fung_at_[hidden] wrote:
hankel> 
hankel> However, I wonder if a VertexListGraph concept has to refine
hankel> both the AdjacencyGraph and the IncidenceGraph concepts. E.g.,
hankel> it seems (correct me if I am wrong) that all the four core
hankel> algorithm patterns in BGL that are implemented without using
hankel> adjacency_iterator or adjacency_vertices(), although they require
hankel> the VertexListGraph concept. Some graph algorithms (such as
hankel> dijkstra_shortest_paths()) also work well without the
hankel> AdjacencyGraph requirement.

The AdjacencyGraph concept use to refine IncidenceGraph. When that was
changed I must have forgotten to update VertexListGraph.html, though
you'll notice that in graph_concepts.hpp the requirement is already there.

The AdjacencyGraph concept is a bit odd, it is somewhat frivolous since
IncidenceGraph really covers the same functionality (and more).
AdjacencyGraph is there just because I can imagine situations where
adjacent_vertices() would be more convenient to use than out_edges(). One
thing in favor of keeping AdjacencyGraph is that it is trivial to
implement using the graph/detail/adjacency_iterator class. I should
document this class and make it public.

hankel> In fact, the ability of traversing all vertices has nothing to
hankel> do with the ability of traversing all out edges or adjacent vertices.
hankel> Perhaps we should eliminate the requirement that a VertexListGraph
hankel> must refine the other two graph concepts, and make all the three
hankel> Concepts orthogonal to each other???

That was suggested during the BGL review. I decided against it because a
vertex list concept that only allows vertex traversal is hardly a graph at
all, it is really just a set. We have container concepts in the STL that
can handle that. Also, the algorithms in BGL that require vertex traversal
also require out-edge traversal, so it is convenient to group them
together.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------