Boost logo

Boost Users :

Subject: Re: [Boost-users] [BGL]Why the output of algorithms are vertex sequence(PredecessorMap)? How about parallel edges??
From: Li Ning (Ning.c.Li_at_[hidden])
Date: 2009-05-10 21:54:15

Andrew Sutton-2 wrote:
>> The code works...
> I'm not convinced that it does. First, the predecessor map is not actually
> a
> property map - you are using it to accumulate relaxed edges. Second, the
> order of edges may be arbitrary and certainly not contiguous. I'm not sure
> I
> see how to efficiently recover the path using this approach.
>> I don't know how to use edge_predecessor_recorder, it seems unable to
>> slove
>> this problem, because it just has a operator().
> I think it maps onto a visitor that has a tree_edge function, so its only
> useful for BSF, DSF, and MST visitors.
>> And I has some additional questions:
>> 1. Why BGL introduce descriptor? This new thing bring what advantage? In
>> STL, the communication between Algo & Container is iterator. But in BGL,
>> a
>> new "iterator-like" thing: descriptor has been introduced. What is the
>> difference? The document says descriptor is a "handle", isn't iterator
>> also
>> a "handle"??
> Descriptors can't "move" (++/--) and can't be dereferenced. The biggest
> reason for using descriptors is that they can provide a higher degree of
> stability than iterators. For example, a vector will invalidate all
> iterators on insert and remove. This makes it virtually impossible to
> build
> a relational data structure (like a graph) on top of vectors, if you use
> iterators (or pointers) from vertex to edge, edge to vertex, and both
> their
> properties.
>> 2. Can descriptor convertable with iterator?
> The BGL does not provide a translation between iterators and descriptors.
> Andrew Sutton
> andrew.n.sutton_at_[hidden]
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]

Is BGL provide tools to do this job? Or how to write a visitor to record
this infomation?

View this message in context:
Sent from the Boost - Users mailing list archive at

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at