Boost logo

Boost :

Subject: Re: [boost] How to speed up the djikstra graph
From: Lennart Berg (LB_at_[hidden])
Date: 2009-06-23 09:35:10

I think I have got a good solution together now.
The A* solution is written as a feature issue and will be tested later on.

First of all, here are some measurements I made with release mode:
( before changes where made)

United Kingdom:
Calculating path cost : 3.12 ms
Calls to Add_edge : 10.50 ms
Dijkstra_shortest_Path : 8.10 ms
Retrieve data from list : 0.22 ms
Total : 21.94 ms

knowing that the add_edge was the biggest problem, the only solution I could
see was to simplify the graph and reduce edges.
Any vertexes with constant weight are now simulated.
The simulation now is not 100% accurate, but the results speak for

United Kingdom:
Calculating path cost : 3.27 ms
Calls to Add_edge : 4.28 ms
Dijkstra_shortest_Path : 3.17 ms
Retrieve data from list : 0.21 ms
Total : 10.94 ms

It is playable now, but there will be some bottlenecks later on in the game,
as countries ally and we get larger graphs for each country.

I have tried changing the list from vecS to ListS, but it suddenly
complains, and I couldn't find any good examples on how to get it to work.
All I found was a note on the documentation that I have to keep track of the
vertexes myself..

Would there be any gain in going that way?

Also is it possible (and would it be faster) to avoid creating a graph and
calling add edge altogether and instead use a static graph with a visitor to
determine edge cost, and if the edge is valid...

I used the whole day yesterday to look for examples, but I couldn't find any
using the boost library for that purpose.

Boost list run by bdawes at, gregod at, cpdaniel at, john at