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

Subject: Re: [boost] How to speed up the djikstra graph
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-05-22 08:09:25

>
> Optimally the graph should be persistant and allow me to dynamically add /
>> remove provinces and change the cost of the edges every hour (as I
>> understand it the boost library allows that right now with vertex_clear /
>> add etc.), and giving new values without recomputing every single edge in
>> the graph 300 times every hour.
>> Is that possible? And if how would that be done?
>>
>
> That
>

Apparently Google /really/ wanted to send a 1 word response.

It all depends your type of graph. It's hard to determine where performance
increases could be made without seeing roughly what you're doing. However,
if you want a persistent, dynamic graph, you're only real option is using
adjacency_list<OEL, listS> (OEL is an out edge list selector).
Unfortunately, using the listS selector means you'll have to keep track of
vertex indices.

If you were going to wait for 1.40, I might suggest using undirected_graph
or directed_graph. They're built for exactly these purposes.

Andrew Sutton
andrew.n.sutton_at_[hidden]