Re: [boost] directed graph template library

From: jsiek_at_[hidden]
Date: 2000-04-20 12:29:32

Hi David,

David Bien writes:
 > > That work is not limited to undirected graphs. It isn't simple, but 
 > lots of
 > > thought went into it. It really is worth understanding.
 > Are you referring to the boost section ?

In the boost vault we have an interface (or concept) description for
graphs. There is currently not a *real* implementation, just some
prototype code.

 > I read and I think I understood the two files in the boost section 
 > relating to graphs. "graph_structure.hpp" seems to address the names 
 > of iterator types, and declare an adjacency iterator. 

Right, this is the heart of the interface, but like I said it is
incomplete. If you would like to propose additions to
the interface go for it! I suggest that you
attempt to follow the "style" of the current interface in new
material. A lot of thought went into making the current interface
suitable for generic programming and ease of use/implementation.

 > "property_accessor.html" is some type of generic property 
 > accessing/modifying templates, that I can't see how is particularly 
 > related to graphs.

Ahh, this is particularly important to graphs. In any graph algorithm
you need to access and operate on properties associated with vertices
and edges. The property accessor provides a *generic* interface for
accessing these properties.

 > Then I see a list of algorthms and whether they apply to a 
 > undirected, directed, or directed acyclic graphs. Now, I have to 
 > admit that I don't know squat about any of those algorithms, so my 
 > level of understanding there was probably pretty low.

I would suggest familiarizing yourself with graph algorithms, at
least the classical ones. As Stepanov says, interfaces and data
structures derived from, and are meant to serve the algorithms.

 > The "ggcl" section seemed to contain an entire implementation of some 
 > sort - but I have to admit that the lack of any documentation or 
 > examples of its use limits my understanding of it. Certainly, I would 
 > like to spend the months of coding time it would take to merge my 
 > library with another, when I could be writing new code :-)

That is just prototype code.

 > Anyway, I have a directed graph *implementation* - for which I 
 > happened to define my own type names and interface names. This was 
 > not meant as an affront to anyone associated with boost, I did not 
 
Of couse not, and I don't think anyone took it that way.

 > Anyway, I will get it out on anonomous FTP, but it has its own 
 > namespace and stuff and probably currently only compiles on the 
 > intel4.0 compiler - though, unless it breaks gcc ( always a 
 > possibility ) it should compile on it with very little work.

Please do!

Cheers,

Jeremy