[boost] Re: graph structure interface compomise?

From: Dietmar Kuehl (dietmar.kuehl_at_[hidden])
Date: 1999-12-09 09:11:19

Hi.
At 01:13 PM 12/8/99 -0600, Bill Wade wrote:
>I missed any discussion of performance requirements.

I'm assuming that basically all operations are amortized O(1). Only
some constructors are allowed to take O(n) time, eg. the copy ctor for
property accessors might take O(n) time where n is the number of
underlying objects (eg. vertices or edges).

>In STL almost all
>iterators support advance() but relatively few (the fast ones) support
>integer addition.  That interface makes it easy for me to write code that
>assumes random access, without writing any explicit compile time assertions.

I think the classification used to choose different graph properties is
rather different from the classification used for sequences. In graph
algorithms normally sets of objects (all vertices or edges of a graph,
all edges incident to a vertex, etc) are processed. For this purpose
basically input iterator with a multi-pass feature are sufficient (ie.
something between input and forward iterators).

>Writing graph algorithms I might want to make similar distinctions between
>graphs that provide fast (O(1) or O(ln N)) adjacency operations and those
>that don't.  In a similar vein, only fast decorators should use [] notation.

I think that the basic operations we have discussed so far should
always be "fast", ie. amortized constant time. However, there are
operations and properties supported only by graphs with special
known structure which algorithms use to provide faster solutions to
problems. For example, if the graph is known to be planer, the concepts
of a dual edges and facets are defined, etc. Although algorithms normally
don't take such properties into account, solvers for problems do!

That brings up an important distinction for graph algorithms: Since
often algorithms solving a complex problem are extensions of algorithms
solving a simpler problem (extremely simple example: path search is an
extension of graph search where the predecessor node is remembered),
it is necessary to distinguish between "algorithms" and "functions
solving a problem" (ie. problem solver). While algorithms should not
change just because the graph supports a special structure, the algorithm
used by a problem solver is even likely to change.

There are two issues with respect to additional properties supported
by a graph data structure:
- Finding out about them at compile time to select the best algorithm.
- Interfaces to the special properties.

So far, the interface defined for the graph structure is rather general
and the details of the abstraction are actually lumped together rather
arbitrarily. This needs some clean up: Eg. not all algorithms need
access to the list of nodes (actually, only *very* few algorithms
need the list of all nodes!). Anyway, it should be possible to find
out about the features supported by a graph module in an extensible
way. Also, I think that most of these features are rather othogonal
and thus there is probably not such a nice hierarchy of requirements
as is for STL iterators.

On possible approach to find out about features is to put them into
the graph traits. This has the drawback that you need to extend these
traits whenever you add a new feature. By deriving from a common
base class, it would be sufficient to the add a default (ie. "not
supported") to the base class. A better approach is the use of special
traits classes which take the graph traits as template arguments and
can be specialized for graph traits where the special features are
supported. For example:

  // from a supporting library:
  struct has_property {};
  struct does_not_have_property {};
  // default:
  template <typename GT> struct is_planar {
    typedef does_not_have_property property;
  };
  // user provided specialization ("quad edges" is a data structure for
  // efficient representation of planar graphs):
  template <> struct is_planar<quad_edge_traits> {
    typedef has_property property;
  };

This structure is just a Boolean compile time flag for the selection of
the best algorithm. The necessary properties are accessed using the
graph object like any other properties with the effect that this will
result in a compile time error if a property is used which is not present.

Of course, it is necessary to agree on a common interface for such
features like it was necessary to agree on a common interface for the
general graph structure. However, with the agreement on the general
graph structure it is possible to  implement a lot of graph algorithms
ranging from rather basic algorithms (eg. various searches), over
typical textbook examples (eg. various flow algorithms) to rather
special and sophisticated algorithms solving non-trivial problems
(well, certain flow problems can savely be considered to be
non-trivial already :-)

Interfaces for special graph structures like eg. planar or acyclic graphs
(just to name two well known special cases, there are a *lot* more
special structure which might be interesting) can be discussed later
when somebody starts implementing algorithms taking these special
properties into account. What should be discussed earlier is the
general approach to be taken to determine the properties at compile
time and how the interface for the graph structure should be extended.
However, I think this is fairly obvious: The compile time features can
be determined as mentioned above (but the details have to be worked
out) and access to special properties is through global function taking
a graph object as argument.

There is definitely more to come in this area but I'm quite happy with
what is already achieved: This is rather likely to motivate some
submissions to Boost, at least it motivates me :-)

Regards,
  dk