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]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

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

-- 
View this message in context: http://www.nabble.com/-BGL-Why-the-output-of-algorithms-are-vertex-sequence%28PredecessorMap%29--How-about-parallel-edges---tp23439356p23476064.html
Sent from the Boost - Users mailing list archive at Nabble.com.

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