Re: [boost] How to speed up the djikstra graph

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
themselves:

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.