Boost logo

Boost :

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"

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

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


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



Boost list run by bdawes at, gregod at, cpdaniel at, john at