Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk