Re: [Boost-users] [BGL]Why the output of algorithms are vertex sequence(PredecessorMap)? How about parallel edges??

Subject: Re: [Boost-users] [BGL]Why the output of algorithms are vertex sequence(PredecessorMap)? How about parallel edges??
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-05-08 07:54:23

> 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]