[boost] Re: graph structure interface compomise?

From: jsiek_at_[hidden]
Date: 1999-12-10 03:33:25

Dietmar Kuehl writes:
 > 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.

I've tried to start to address this issue. See the "Graph Module
Variants" section in graph_structure.html.  Here's what I've got so
far:

Graph  (everything)

GraphVL (VL for vertex list)
  doesn't have edges()

GraphEL (EL for edge list)
  doesn't have vertices()

GraphHV (HV for head vertex)
  doesn't have edges() or vertices(), I've added a function
  v = head(g) which returns the "head" or "source" of the graph.
  (other names for this are welcom)
  The kind of graph I have in mind here is a bunch of nodes
  linked together without any "backbone". A tree is often
  represented this way.

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

Yes, the traits should be expanded... this will probably take
a lot more time as Dietmar said.

Cheers,

Jeremy