Re: [Boost-users] [BGL] premature termination in dijkstra using visitor

Subject: Re: [Boost-users] [BGL] premature termination in dijkstra using visitor
From: Ralf Goertz (R_Goertz_at_[hidden])
Date: 2009-10-06 10:38:49

I managed to create a visitor now, however, instead of speeding things
up dijkstra_shortest_paths now runs several orders of magnitudes slower!
I created the visitor according to the bfs_name_printer example in the
BGL User Guide and Reference Book page 11.

----- 

class dijkstra_finish : public Exception {
};

template<unsigned maxdist>
class MyVisitor : public default_dijkstra_visitor {
public:
    MyVisitor(const vector<unsigned> &d_) : d(d_) {}
    template <typename Vertex, typename Graph>
        void finish_vertex(Vertex u, Graph g) {
            if (d[u]> maxdist) throw dijkstra_finish();
        }
private:
    const vector<unsigned> &d;
};

struct Distance {
    unsigned d;
};

int main() {
        vector<unsigned> dists(num_edges(g));
        MyVisitor(dists);

        try {
       
dijkstra_shortest_paths(g,source_vertex,weight_map(get(&Distance::d,g)).distance_map(make_iterator_property_map(dists.begin(),get(vertex_index,g))).visitor(vis2));
        } catch(const dijkstra_finish&) {}

}

----- 

The code seems to do what I want, all dists are either 0,1,2,3 or
numeric_limits<unsigned>::max(). But for a graph with 15000 edges it
takes a few ms to run dijkstra without a visitor but with it it takes 14
seconds. What am I doing wrong?