Boost Users :
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
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.
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net