[astar search] Computation time for large graph
Hi,
I try to use the "astar-cities" example but for graph of about 10000 nodes
and edges (which are weighted) in order to find the fastest path between
two random nodes... and I want to do it several times. I encountered very
large computation time : about 4 min to perform 100 searches.
Is it supposed to be slow for large graph?
My machine is not very powerful but I think I've missed something...Is
there ways to optimize? Can it be a problem from the weighted edges or from
the heuristic distance ?
my astar_search function call is :
boost::astar_search(m_g,
vertexStart,
heuristicDistance,
boost::predecessor_map(&p[0])
.distance_map(&d[0])
.visitor(astarVisitor)
);
with m_g my graph which is a:
typedef boost::adjacency_list
On Wed, 9 Jan 2013, Yann-Hervé Hellouvry wrote:
Hi,
I try to use the "astar-cities" example but for graph of about 10000 nodes and edges (which are weighted) in order to find the fastest path between two random nodes... and I want to do it several times. I encountered very large computation time : about 4 min to perform 100 searches.
Is it supposed to be slow for large graph? My machine is not very powerful but I think I've missed something...Is there ways to optimize? Can it be a problem from the weighted edges or from the heuristic distance ?
One issue could be that your graph uses listS as out edge container, but that shouldn't cause the search to be as slow as you're experiencing. Are you sure your compiler's optimization is enabled and that NDEBUG is defined? -- Jeremiah Willcock
Hi,
My compiler is in "optimization mode" and I am on a release version... If
listS could be an issue, what could I use instead for my edge container?
Regards,
YH
2013/1/9 Jeremiah Willcock
On Wed, 9 Jan 2013, Yann-Hervé Hellouvry wrote:
One issue could be that your graph uses listS as out edge container, but that shouldn't cause the search to be as slow as you're experiencing. Are you sure your compiler's optimization is enabled and that NDEBUG is defined?
-- Jeremiah Willcock
On Wed, 9 Jan 2013, Yann-Hervé Hellouvry wrote:
Hi,
My compiler is in "optimization mode" and I am on a release version... If listS could be an issue, what could I use instead for my edge container?
vecS is the usual option for performance when the graph doesn't change often. You can also use compressed_sparse_row_graph if it doesn't change at all after construction. -- Jeremiah Willcock
participants (2)
-
Jeremiah Willcock -
Yann-Hervé Hellouvry