Re: [Boost-users] [BGL] overlaying a graph-like structure

From: martin f krafft (madduck_at_[hidden])
Date: 2005-06-14 17:22:17

also sprach David Abrahams <dave_at_[hidden]> [2005.06.14.2259 +0200]:
> > The other reason is that your claim is not true. It *sounds* easy,
> > and it's really easy to get wrong.
> 
> Maybe you should have asked for help with _that_ project.  It
> *really* shouldn't be too hard.

I did, but not here, since it's not boost. Most of it was in
##c++/irc.freenode.org, so it's not really archived.

Surely, simple edges and nodes are easy. My challenge is that
I wanted to make it configurable whether the node should keep a list
of edges, only keep one of them (incoming or outgoing), or actually
store both.

You can see my current state at http://xrl.us/ge3a. I don't quite
have it compiling yet, this is tomorrow's task. However, you can get
the idea I was trying to go with: edge list policies, and
EmptySequence to simulate a lacking edge list.

The main problems I see with this approach are:

  - users are currently expected to derive from Node and Edge. Since
    they do not have a virtual destructor though, this could become
    a problem should they ever store objects by pointer to Node and
    Edge. My code never deletes anything it did not allocate, so
    there is no real problem.

  - even though it seems possible to mix nodes with different edge
    policies in a single graph, there is a compile-time dependency
    between the node and the edge to use. I would much rather prefer
    to have a single type of edge. I will have to investigate
    a BasicNode abstract base class similar to BasicEdge, which is
    to be hidden away behind the API such that users are never
    exposed to it.

  - the approach with the EmptySequence seems okay, but it has the
    flair of a hack. Unfortunately, I saw no other way to make nodes
    with and without edge lists interchangeable other than to
    replace the list implementation for those without lists with
    a mock object.

There are possibly others; I have not used the code in four weeks.

> > Then again, my implementation tried to be generic wrt to the
> > types you store for each edge or node *and* to avoid
> > polymorphism for space efficiency reasons. 
> 
> Avoiding runtime polymorphism is pretty natural with
> BGL-conformant graphs.

Yeah, and it's simple to do with an adjacency list/matrix, it seems.
If you look at my code, you'll see that circular dependencies are
a major problem...

-- 
martin;              (greetings from the heart of the sun.)
  \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net_at_madduck
 
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver!
spamtraps: madduck.bogus_at_[hidden]
 
there are lies, statistics, and benchmarks.