[boost] Re: Graph concepts

From: Dietmar Kuehl (dietmar.kuehl_at_[hidden])
Date: 1999-12-13 11:00:06

Hi,
At 06:50 PM 12/11/99 -0500, you wrote:
>I've created a hierarchy of graph concepts for organizing 
>the basic operations. I've updated the document in the
>vault.

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!

Basically what happens for both STL iterators and property
accessors is that there are fundamental but orthogonal traits of
the types. As it turns out, it is often useful to have two
fundamental traits at the same time. This way the hierarchy is
formed. I think the same also applies to graphs but I cannot yet
see a useful hierarchy!

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.

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.

>Graph -> EdgeGraph -> VertexGraph -> VertexListGraph
>                  \          
>                   -> EdgeListGraph
>
>Graph
>  empty for now, just a placeholder for comments about graph objects
>  in general. Later more traits stuff can be added here.

If I can implement something just using the requirements by
EdgeGraph, any additional requirement imposed on Graph would
restrict the applicability of algorithms implemented only in terms
of EdgeGraph! This seems to be silly to me... Sure, there can be
a group of requirements named "Graph" but I would not require all
requirements of this group to be universally imposed on all other
groups of requirements.

>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

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.

>VertexGraph refines EdgeGraph
>  adj(v,g)           
>  out_edges(v,g)         

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

Regards,
  dk