[boost] Re: Graph concepts

From: jsiek_at_[hidden]
Date: 1999-12-13 19:54:28

Hi Dietmar,

The new version of graph_structure.html, and the file
algo_overview.html should address a number of the
concerns you mentioned in this email.

Dietmar Kuehl writes:
 > Why do we want a hierarchy? In fact, I can't see any reason to
 > define any sort of hierarchy in general. Sometimes it turns out
 > that there is some form of a hierarchy like is the case for the STL
 > iterators and the property accessors. But note that in both cases
 > the hierarchy is not a tree: It is a DAG. I would be very surprised
 > if the fundamental graph concepts happen to be organized in a
 > tree!

I agree that for many of the properties it will probably not
make sense to have a hierarchy, but I think it may work
for some of the basic ops, hence my current experiments
with a hierarchy. However, if it turns out to be unhelpfull
for algorithms, I'll be perfectly happy to throw the whole
thing out the door :)

 > I can see certain groups of requirements going together. There
 > is occasionally a small overlap between these group but I don't
 > think that this alone justifies a hierarchy (see eg. the 'value_type'
 > in the readable and writable property accessors). I think that a
 > reasonable approach to useful graph concepts is the definition
 > of rather small groups or requirements which may be refinements
 > of existing groups where this is natural, ie. where the new
 > requirements clearly need the other requirements to be useful.

Yes, it is something like this that I'm trying to form.

Perhaps there won't be a single hierarchy tree, but instead
a forest ;) 

 > Once we have sufficient graph algorithms we can tell which
 > groups of requirements often go together in the requirements
 > listed for an algorithm. These groups of requirements can then
 > be documented and given a name, partially because it eases the
 > documentation of algorithms but also because it eases the
 > descision which requirements should be imposed by a specific
 > algorithm: Clearly the minimal ones but sometimes this is not
 > unique and there are may be slightly different approaches how
 > to implement the same algorithm using different graph properties.

Right, I've made a rough start on this with the "algo_overview.html"
file.

 > >EdgeGraph
 > >  source(e,g)
 > >  target(e,g)
 > 
 > Of course, this is not a complete list because obviously the
 > following two definitions are also required for this to be useful
 > at all:
 >   typename boost::graph_traits<Graph>::vertex_descriptor
 >   typename boost::graph_traits<Graph>::edge_descriptor

Right, I included the typedefs in the writeup for graph_structure.html.

 > In addition, I would separate the functions source() and target()
 > into two different groups of requirements: In my implementation
 > of DFS and BFS I don't need source() at all. In fact, I rarely need
 > this function and it is also rather likely that it is not implementable
 > at all for certain graph representation without imposing considerable
 > overhead either for the actual representation or for edge descriptors.
 > This is not acceptable for a requirement which is not really used.

Right, I noticed that too. Any ideas for what the two concepts
should be named?

 > Like for EdgeGraph, this list is incomplete (the two iterator types
 > are missing) and overspecified at the same time: Algorithms rarely
 > need both operations (actually, all algorithm I have implemented
 > only need 'out_edges()'!) and I would separate the requirements.

Yes, the GGCL algorithms also tend to use just out_edges() and not
adj().

 > However, I would also create a template class taking an incidence
 > iterator and transforming it into an adjacency iterator. This is similar
 > to the reverse iterators used  in the standard containers. However,
 > there is rarely a requirement for the reverse iterators imposed by
 > algorithms. It is only imposed by certain container requirements.

Nod.

 > Of course, I should write up a corresponding proposal. Unfortunately
 > I fear that I have to do some of the work I'm paid for this week :-)
 > I will try to write things up but I can't tell when I can post it...

I'll try to incorporate your suggestions into the document I'm working
on... perhaps by the time you get your write-up done we'll already
be closer to convergence on this.

Cheers,

Jeremy