[boost] Re: graph structure interface compomise?

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 1999-12-10 13:55:02

Hi,
> I've uploaded the description of the graph structure interface
> to the boost vault.

Just a brief note on the format: Although I like the format of the
description you have choosen (after all, it resembles the format I
have choosen :-) I want to point out that this is not some kind of a
must! If it looks useful to you, I'm just fine. However, I would also
change the format of the documentation if there are good suggestions,
good guidelines, or common preferences.

In any case, I think that the use of HTML is a very reasonable file
format which can be conveniently viewed by everybody (ie. the "format"
mentioned above refers only to the contents, not to the choosen markup
language).

> http://www.egroups.com/docvault/boost/graphs/graph_structure.html

- In the mathematical definition of the graph I dislike a particular
  implied restriction: Sets, by definition, do not include multiple
  copies of the same elements. That is, the definition of a graph
  you have given rules out parallel edges. This is rather typical
  for theoretical work but basically useless in practical situations:
  Parallel edges, as well as loops (ie. edges where the source and
  target vertex are identical), are present in graphs encountered in
  practise. The abstraction and the algorithms should cope with them,
  especially as most algorithms have no problem at all with these edges
  (except that the asympotical complexity looks different which is,
  however, irrelevant in practise once you have choosen an algorithm).

- Although they are low, there are requirements imposed on the
  descriptor types: These types have to be Assignable (this reminds
  me that the value type for the property accessors also has to be
  assignable for all property accessors except
ReadablePropertyAccessor;
  this is not yet mentioned...) and potentially even EqualiyComparable.

- We need to define exactly what an adjacency iterator iterates over.
  There are two options (I can see...):
  - The *set* of adjacent edges. In this case there would be
significant
    difference to incidence iterators, eg. because the cardinality of
    the resulting nodes differs if parallel edges are present. However,
    this is in general non-trivial to achieve and I can't think of an
    algorithm which really needs this feature.
  - Adjacency iterators are basically the same as incidence iterators
    except that they directly access the corresponding node. That is,
    an adjacency iterator 'ait' can be implemented in terms of an
    incidence iterator 'iit', ie. basically 'operator*()' for 'ait'
does
    this: 'return target(*iit, g)'. Of course, for specific graphs
    there can be better implementations (eg. an implementation which
    does not require a reference to the graph object).
  
  If we decide that we don't want to decide this yet because we first
  want to gain experience with the interface, there are two options:
  - Either we remove all mention for adjacency iterators for now and
    introduce it when there is experience and a need/use for this
    iterator.
  - We document clearly that the exact semantics are not yet defined
    for this kind of iterators. In this case, algorithms should
    assume that it does the wrong thing, ie. if they depend on either
    of the specific semantics, they should *not* use it.
  
- A minor nit making no semantic difference: Since the incidence
  iterator is likely to iterate over the outgoing edges for a node,
  it might be counterintuitive to call it "InIt" although I can see
  the logic of the name :-)

- The valid expression should include the following operations:

    expression      type  semantic
    *ait            V         obtain a vertex descriptor from an
                              adjacency iterator
    *iit            E         obtain an edge descriptor from an
                              incidence iterator
    *vit            V         obtain a vertex descriptor from a
                              vertex iterator
    *eit            E         obtain an edge descriptor from an
                              edge iterator

  I was also thinking about an orthogonal use of a pair for the
incident
  nodes of an edge, ie.

    incident(e,g)  pair<V,V>  get descriptors for the nodes incident
                              to an edge.

  instead of the functions source() and target(). I have no strong
  opinion on this one, though (actually, there are arguments against
  this, namely separation of requirements; see below: I thought of
  this only much after first writing the suggestion...).

- What is the "head" or "source" vertex of a graph? Where is it
  used?

- Instead of guaranteeing the complexity I would "assume" it! This
  way it would be possible to apply the abstraction even to graphs
  having a different time complexity. However, in this case the
  complexity given for the algorithm does not necessarily hold.

- In addition to requiring the possibility of multiple passes, I
  think the following requirement also has to be added:
    it1 == it2  => *it1 == *it2
  This definition, of course, implies that descriptors support the
  comparison. This could be a reasonable requirement by itself (and
  should in this case be listed with the descriptors) but even if
  this is not required, a similar requirement providing object
  identify should be formulated.

A major issue is how to document and determine at compile time
requirements for graphs. My preference would go a different approach
especially with respect to orthogonal requirements: There are
application
where the list of all edges are required, applications where the list
of
all nodes are required, as well as applications where neither or both
are required. A graph supporting these featues just lists them in its
traits, a graph not supporting them does nothing, in particular does
not provide typedefs for the corresponding types: If they are accessed
by an algorithm it is an error anyway.

It can be argued that at compile time it could be useful to have the
typedef for 'void' to specialize for this type (actually, I'm not sure
whether this is indeed possible but using some other type invented
specifically for this purpose would definitely do). Thus, this way the
compile time detection of features can be achieved.  This is definitely
true but this approach is not extensible to future properties like
eg. support for special graph categories like planar or directed
acyclic
graphs.

I would prefer an approach where the graph traits can be extended as
needed without having to change existing graph traits (except if the
corresponding graphs support more specific traits which are not yet
listed; ie. the traits for graphs which have nothing to do with the new
traits should go unchanged). A simple approach are the special classes
I outlined in a previous mail. The same approach which can be used to
determine whether a graph structure guarantees planar graphs can be
used to determine whether a graph structure supports iteratation over
all nodes. The details may look different, the general outline could
look something like this:

  struct is_supported { static const bool flag = true; };
  struct is_not_supported { static const bool flag = false; };

  template <typename Property, typename Graph>
  struct graph_property { typedef is_not_supported support; };

  struct planar_graph {};
  struct directed_acyclic_graph {};
  // ...

If a graph class G supports some property, it would just specialize
the class 'graph_property', implement the corresponding access
functions, and provide corresponding typedefs in the graph traits
class. To test for a specific property, specialization can be used
on the subtype 'support' or the static member 'flag' of this type
can be used in conditionals. For example:

  // note that alway the default for the template argument is used!
  template <typename G,
    typename dummy = typename graph_property<planar_graph, G>::support>
  class algo1
  {
    // ...
  };
  template <typename G>
  class algo1<G, is_supported>
  {
    // ...
  };

  template <typename G>
  class algo2
  {
    void foo() {
      if (graph_property<planar_graph, G>::support::flag)
        something_assuming_planarity_but_no_special_functions();
      else
        handling_the_general_case();
    }
    // ...
  };

There are two things to note about this code:
- The default template argument for the first style of specialization
  is always used, ie. this template argument is never explicitly
  provided! This template argument is only there for specialization.
- The second style only works if the special case does not require
  any special interface (unless the called function is specialized;
  however, I have more in mind that no function is actually called
  anyway). However, sometimes certain extra operations can be omitted
if
  a certain structure is known for the graph. For example, in a
directed
  acyclic graph there are no "backward edges" closing a cycle during a
  graph search. This does not need a special interface, just the
knowledge
  that it is not there.

The handling of a list of nodes, edge, adjacent nodes, etc. can be
done similarily. Only some basic operations should go into the
general graph traits. Thinking of it, this is of course a reason
to separate the source() and target() functions for an edge: There
are graph representations supporting only one of them (the target()
operation) but not the other... Thus, the pair idea I mentioned above
is not really that clever (I left it in anyway so others don't have to
go into this dead end).

Regards,
  dk
__________________________________________________
Do You Yahoo!?
Thousands of Stores.  Millions of Products.  All in one place.
Yahoo! Shopping: http://shopping.yahoo.com