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@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Andrew Sutton Sent: 22. maj 2009 14:09 To: boost@lists.boost.org 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@gmail.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost