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: Li Ning (Ning.c.Li_at_[hidden])
Date: 2009-05-08 05:40:36

Dmitry Bufistov wrote:
> 
> Li Ning wrote:
>> For example, a graph has 2 nodes: A & B. There are 2 edges form A to B
>> which
>> are edge1 & edge2. edge1 has weight 1, edge2 has weight 2. Then the
>> shortest
>> path form A to B is: vertex A---edge1---vertex B. But the default output
>> of
>> all algorithm is vertex sequence. Why? How to get the edge sequence?? 
>> I have noticed vistor.hpp has a class edge_predecessor_recorder, but I
>> don't
>> know how to use it. 
>> Anybody give me a hint?
>> 
> For the shortest path problem you can translate "edgeless" 
> representation to "vertexless" as follows:
> 
> vertexless_path translate(weight_map, pred_map, source, tail)
> {
>    result := [];
>    s := source; t := tail;
>    while (t != s)
>    {
>       result += min_arg(weight_map[(pred_map[t], t)]); //Edge with the 
> minimal weight
>       t = pred_map[t];	
>    }
>    return result;
> }
> 
> Of cause, using the edge_predecessor_recorder is a better solution. If 
> you provide your working code I will try to modify it accordingly.
> 
> Regards,
> Dmitry
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 
> 

I wrote a recorder that derived from dijkstra_visitor<> and implement the
edge_relax to record the edges sequence. 
template <class PredecessorVec>
class record_edge_predecessors : public dijkstra_visitor<>
{
public:
        record_edge_predecessors(PredecessorVec& p)
                : m_predecessor(p) { }

                template <class Edge, class Graph>
                        void edge_relaxed(Edge e, Graph& g) {
                                m_predecessor.push_back(get(edge_index_t(), g, e));
                        }
protected:
        PredecessorVec& m_predecessor;
};

template <class PredecessorMap> record_edge_predecessors<PredecessorMap>
make_edge_predecessor_recorder(PredecessorMap& p) 
{
        return record_edge_predecessors<PredecessorMap>(p);
}
............................
std::vector<int> q;
graph_traits<G>::vertex_descriptor s = vertex(1, g);
dijkstra_shortest_paths(g, s,
predecessor_map(&p[0]).weight_map(weightmap).visitor(make_edge_predecessor_recorder(q)));

The code works...

I don't know how to use edge_predecessor_recorder, it seems unable to slove
this problem, because it just has a operator(). 
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"?? 
2. Can descriptor convertable with iterator?
-- 
View this message in context: http://www.nabble.com/-BGL-Why-the-output-of-algorithms-are-vertex-sequence%28PredecessorMap%29--How-about-parallel-edges---tp23439356p23443003.html
Sent from the Boost - Users mailing list archive at Nabble.com.