Re: [boost] BGL limitations (?) and possible solutions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-08 23:22:43

----- Original Message -----
From: "Dietmar Kuehl" <dietmar_kuehl_at_[hidden]>

> i haven't checked the BGL sources but graph search algorithms need a
> flag indicating whether a node was visited. Of course, storing the
> distince can be considered a flag: Actually, often search algorithms are
> formulated to update a distance which is initially set to infinity.

Yep.

> Whether a property map actually stored anything with all nodes or just
> with the nodes needing a different value than the default value, is,
> however, an entirely different issue :-) What does not work general
> graphs is to store nothing with nodes: This works with trees and DAGs
> but as soon as there can be cycles it does not work.

I suppose you mean that you need a visited marker to break the cycles, and
thus you need to be able to change and hold state corresponding to arbitrary
nodes?

It seems to me that that is true for many algorithms over DAGs as well,
since it is often an error to visit the same node twice.

-Dave