[boost] Re: graph interface/implementation

From: Dave Abrahams (abrahams_at_[hidden])
Date: 1999-12-09 23:29:28

Dietmar,

Thank you for your explanation of iterators/descriptors. I now understand
the concepts (I think).

>>[do you expect to be able to compare node iterators for equality?
>
> Yes, I think so. On the other hand, if equality is defined for the
> descriptors, this might be sufficient.
>
>>What about op<()?
>
> No, probably not: The iterators are used to get at the objects in a
> set. This set is normally not ordered in any particular way. The only
> exception to this rule I'm aware of are planar graphs but these are
> very special beasts anyway: They need several special treatment to
> take advantage of their special structure eg. access to the dual of
> an edge.
>
>>Hashing?
>
> Unless the answer to 'op<()' already answered this question, this
> question is a little bit too brief to me to understand it...

Here I'm aiming at the fact that many algorithms need to look up nodes or
edges in short order (e.g. in a hash table). A simple example is marking
nodes as visited in a search.

>>What about searches where the space of all nodes isn't easily captured --
>>answer this at the bottom!]
>
> First of all, the algorithms I have dealt with never need the list all nodes
> for a different purpose than initialization of properties which is better
> done differently anyway! However, this question might as well apply
> to the list of all edges incident to a node. Here is an attempt to provide
> input without actually understanding the question exactly: If you
> cannot iterate over these sets of objects but they are need by an
> algorithm, you are lost! Now, the iterators used are not just input
> iterators but require a little bit more, ie. basically some support for
> multiple passes and object identity (not for the iterator itself but for
> the object currently identified). I don't think that you can successfully
> apply graph algorithms to structure where these rather basic
> requirements cannot be fulfilled. Potentially the requrement for
> [amortized] constant time operations cannot be provided... Do you
> have examples where you see a problem?

No, and I didn't see a problem with your proposals, but wanted to make sure
I hadn't overlooked anything.

> Honestly, I don't know! I have measured the effect of using this
> approach compared with and written code (I used DFS or BFS for
> a path search where the predecessors are stored in the nodes) and
> got a penalty of a few percent (I think something like 5%). The effect
> should definitely be measured. However, due to the rather structured
> use I can imagine that compiler can optimize things a lot! BUT: This
> is just a guess, not the result of measurements.

> On the other hand, using this approach makes it viable to reuse
> algorithms in the first place rather than implementing them from
> scratch over and over again. The callback interface is not necessarily
> better because it gives less control over the algorithm.

If you have enough callbacks, you can surely do all the same things. I'm not
sure what loss of control you fear, but from an efficiency point-of-view it
might make sense to exit the algorithm by throwing an exception (no, I'm
really NOT kidding).

> What should
> be used and what is more effective should definitely be measured.
> Having a stable interface for the graph structure should give the
> opportunity to do so!

Agreed!
-Dave