
Boost : 
Subject: Re: [boost] How to speed up the djikstra graph
From: Lennart Berg (LB_at_[hidden])
Date: 20090522 09:53:25
Thanks for the reply, I am not sure yet how to use adjancy list effectively
to improve the speed... I am looking for some inspiration on google now..
If you could provide me with some short pseudo code or an example, that
would be grat
Also I have compiled some extra information:
Here is my code:
{
const int V = MAX_PROVINCE; //Max provinces = 2608
graph_t g(V);
for (int ij = 0; ij < V;ij++)
{
CProvince &Prov = CGameMapProvince::Province[ij];
if (!HaveAccess(Prov)) continue; //This call determines the
owner of the province, their diplomatic status to us, and if it is blockaded
by enemy units.
int nNeighbors = Prov.GetNumberOfNeighbors();
for (int n=0; n < nNeighbors; n++)
{
...
Check province type and compute "Cost" if edge is
valid
if possible: ( is not called if not possible)
...
add_edge(ij,To.GetProvinceID(),Cost, g);
}
}
// Keeps track of the predecessor of each vertex
std::vector<vertex_descriptor> p(num_vertices(g));
// Keeps track of the distance to each vertex
std::vector<int> d(num_vertices(g));
property_map<graph_t, edge_weight_t>::type weightmap =
get(edge_weight, g);
property_map<graph_t, vertex_index_t>::type indexmap =
get(vertex_index, g);
vertex_descriptor s = vertex(GetCapital(), g);//Source????
dijkstra_shortest_paths(g, s, &p[0], &d[0], weightmap, indexmap,
std::less<int>(), closed_plus<int>(),
(std::numeric_limits<int>::max)(), 0,
default_dijkstra_visitor());
// Readout of variables:
graph_traits < graph_t >::vertex_iterator vi, vend;
for (tie(vi, vend) = vertices(g); vi != vend; ++vi)
{
int ProvID = *vi;
int Cost = d[ProvID];//Cost!!
_TransportCost[ProvID] = CMath::diminishing_returns(Cost,2);
}
}
I have done some performance tests in debug mode, and there it seems
add_edge is using up most of the time (51% of total calc time).
It might be that this time is reduced considerably in release, that I
haven't tested.
Some times I have measured:
Calculation of edge cost and Access test: 1.2ms
Add_edge calls: 10.1ms
Djikstra: 8.3ms
ReadOut of variables: 0.2ms
Would it be a good idea to make a static map (with 0 cost edges), and use a
visitor to determine edge cost before they are used?
As far as I can see that would allow me to replace the Add_edge
Original Message
From: boostbounces_at_[hidden] [mailto:boostbounces_at_[hidden]]
On Behalf Of Andrew Sutton
Sent: 22. maj 2009 14:09
To: boost_at_[hidden]
Subject: Re: [boost] How to speed up the djikstra graph
>
> 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]
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk