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-05-22 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: boost-bounces_at_[hidden] [mailto:boost-bounces_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