Boost logo

Boost Users :

From: Fonzi Chat (fonzi337_at_[hidden])
Date: 2008-04-11 21:05:35


Hello,
 
I just started using the Boost graph library a few days ago, so I am pretty new to all of this. What I'm trying to do is to record the path distance between a given source and target vertex using a variety of algorithms. So far, I've gotten BFS and Dijkstra's working correctly, however I'm having some trouble having distance information recorded in my distance_map Property when attempting to do this with DFS.
 
For instance, this is what I wrote for Dijkstra's:
 
dijkstra_shortest_paths(G, s, distance_map(&d[0]).visitor(*(new DijkstraVisitor(s, t))));
 
where G is a Graph, s is the start Vertex, d is defined as an integer vector and DijkstraVisitor is a class I have defined that is used as the visitor for the algorithm.
 
Similarly, for DFS I have:
 
depth_first_search(G, visitor(*(new DFSVisitor(s, t))).distance_map(&d[0]).root_vertex(s));
 
Unfortunately, when I try reading the d vector, all the values are zero and seem to have never been updated. My question is: what am I doing wrong and what can I do to record the distance correctly?
 
Another somewhat related problem I have is that the algorithms seem to take VERY long to complete when larger graphs are processed. For instance, a graph with 100 vertices and 10,000 edges (mesh topology) takes about 10 minutes to complete the shortest path problem between two given vertices. Is this normal?
 
Thank you for putting up with my amateur questions! Any and all help is appreciated.
_________________________________________________________________
Get in touch in an instant. Get Windows Live Messenger now.
http://www.windowslive.com/messenger/overview.html?ocid=TXT_TAGLM_WL_Refresh_getintouch_042008



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