How to speed up the djikstra graph
Hi Everybody I have had the pleasure of using the boost graph library for my project now, but I have ran into some problems, that I hope you can guide me on. First of all, let me tell a little about the project. I am a third party developer for paradox interactive, making an expansion for one of their games. Now i have implemented the djikstra alghorithm to simulate the transport capacity of countries, and it works pretty well. However I still think that the speeds to be improved somewhat (takes about 1-2 secs to compute), to make it more playable. First of all the map consists of ~2500 provinces / vertexes each with 4-8 edges / neighbours. I Find all the provinces I can access and then add all neighbours from it as edges. Each edge is allocated a cost according to infrastructure, terrain and distance from orgin to destination. Each "round" of the game is an hour, so a day is effectively 24 rounds. Right now I make a new graph once every day, one separate graph for each country, and compute it for every country once a day. However as the game has up to 300+ countries that becomes a pretty harsh computational burden. Now pretty much every variable in this setup can change hourly. ( location of units, conquest / loss of provinces, destruction of infrastructure, expansion / repair of infrastructure) So the question is how I can improve this approach. 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? Thanks in advance Lennart Berg
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 Andrew Sutton andrew.n.sutton@gmail.com
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
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
On Fri, 22 May 2009, Lennart Berg wrote:
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
(snip) One potential issue is that BGL performance in debug mode is not representative of what will happen in release mode. Also, it appears that you are completely rebuilding the graph in every round of your game. If that is true, you might want to use the compressed_sparse_row_graph and its sorted add_edge operation in all versions of the CSR graph; or pre-build a sequence of pairs and corresponding distances (possibly unsorted) using the constructors coming out in 1.40 and that are currently in the trunk. The CSR graph type tends to be faster for read-only access, and its sorted add_edge function is also fast. It is only for directed graphs, but you should be able to insert each distance twice (once for each direction) if your distances are all positive. Also, x86 performance of Dijkstra is ~25% better on the trunk than in 1.38 (and probably 1.39) so you might want to benchmark against that; again, release mode is important to get accurate performance information. -- Jeremiah Willcock
Sadly due to the restriction of the engine I have to stick with the now dated Visual C++ 6. I am running with boost 1.35. I have tried the last couple of hours to port the boost trunk to VC6 but it seems more or less hopeless for me. So unless the 25% speedup is a small patch that can be implemented, I dont see any change in the current setup. (The sparsed graph is calling out for a newer compiler) I am currently looking into the parallel boost project and will try to get a previus trunk version to work with the 1.35. -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: 22. maj 2009 16:50 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph On Fri, 22 May 2009, Lennart Berg wrote:
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
(snip) One potential issue is that BGL performance in debug mode is not representative of what will happen in release mode. Also, it appears that you are completely rebuilding the graph in every round of your game. If that is true, you might want to use the compressed_sparse_row_graph and its sorted add_edge operation in all versions of the CSR graph; or pre-build a sequence of pairs and corresponding distances (possibly unsorted) using the constructors coming out in 1.40 and that are currently in the trunk. The CSR graph type tends to be faster for read-only access, and its sorted add_edge function is also fast. It is only for directed graphs, but you should be able to insert each distance twice (once for each direction) if your distances are all positive. Also, x86 performance of Dijkstra is ~25% better on the trunk than in 1.38 (and probably 1.39) so you might want to benchmark against that; again, release mode is important to get accurate performance information. -- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sun, 24 May 2009, Lennart Berg wrote:
Sadly due to the restriction of the engine I have to stick with the now dated Visual C++ 6.
I am running with boost 1.35.
I have tried the last couple of hours to port the boost trunk to VC6 but it seems more or less hopeless for me. So unless the 25% speedup is a small patch that can be implemented, I dont see any change in the current setup. (The sparsed graph is calling out for a newer compiler)
I am currently looking into the parallel boost project and will try to get a previus trunk version to work with the 1.35.
You still should benchmark things in release mode. Please try that and see if it changes your performance behavior. The 25% speedup is a relatively small patch, but hasn't been tested on that old of a copy of Boost or on that compiler. To get that, copy over boost/graph/detail/d_ary_heap.hpp from a new copy of Boost and look at the diffs between the boost/graph/dijkstra_shortest_paths.hpp files to find the part where d_ary_heap is used. I think that can probably be ported over; the code is not using C++ in any fancy ways. As to the compressed sparse row graph, you might be able to take out the vertex and edge property support and then use the vertex_index and edge_index property maps defined by the graph type as key to external property maps. I believe partial specialization is only required in there for bundled properties, which you can avoid by using external properties. -- Jeremiah Willcock
Hi I have tried mixing and fixing the graph files for quite some time now. the last problem I have met is that: namespace detail { template <class Graph, class IndexMap, class Value, bool KnownNumVertices> struct vertex_property_map_generator_helper {}; template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> { typedef boost::iterator_property_map<Value*, IndexMap> type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { array_holder.reset(new Value[num_vertices(g)]); std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value()); return make_iterator_property_map(array_holder.get(), index); } }; template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> { typedef boost::vector_property_map<Value, IndexMap> type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { return boost::make_vector_property_map<Value>(index); } }; template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator { typedef boost::is_base_and_derived< boost::vertex_list_graph_tag, typename boost::graph_traits<Graph>::traversal_category> known_num_vertices; typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper; typedef typename helper::type type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { return helper::build(g, index, array_holder); } }; } And the corresponding default color helper resulting in VC6 compiler errors. (template already defined as non-template) I am stuck, if you could please advise me on how to rewrite these templates for VC6. -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: 24. maj 2009 00:18 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph On Sun, 24 May 2009, Lennart Berg wrote:
Sadly due to the restriction of the engine I have to stick with the now dated Visual C++ 6.
I am running with boost 1.35.
I have tried the last couple of hours to port the boost trunk to VC6 but it seems more or less hopeless for me. So unless the 25% speedup is a small patch that can be implemented, I dont see any change in the current setup. (The sparsed graph is calling out for a newer compiler)
I am currently looking into the parallel boost project and will try to get a previus trunk version to work with the 1.35.
You still should benchmark things in release mode. Please try that and see if it changes your performance behavior. The 25% speedup is a relatively small patch, but hasn't been tested on that old of a copy of Boost or on that compiler. To get that, copy over boost/graph/detail/d_ary_heap.hpp from a new copy of Boost and look at the diffs between the boost/graph/dijkstra_shortest_paths.hpp files to find the part where d_ary_heap is used. I think that can probably be ported over; the code is not using C++ in any fancy ways. As to the compressed sparse row graph, you might be able to take out the vertex and edge property support and then use the vertex_index and edge_index property maps defined by the graph type as key to external property maps. I believe partial specialization is only required in there for bundled properties, which you can avoid by using external properties. -- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hi Lennart, Have you considered using astar_search instead of djikstra? With a good heuristic, A* can be much faster than Djikstra, which is a special case of A* where the heuristic is constant. On Fri, Jun 19, 2009 at 5:56 PM, Lennart Berg <LB@bl-logic.dk> wrote:
Hi
I have tried mixing and fixing the graph files for quite some time now.
the last problem I have met is that:
namespace detail { template <class Graph, class IndexMap, class Value, bool KnownNumVertices> struct vertex_property_map_generator_helper {}; template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> { typedef boost::iterator_property_map<Value*, IndexMap> type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { array_holder.reset(new Value[num_vertices(g)]); std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value()); return make_iterator_property_map(array_holder.get(), index); } };
template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> { typedef boost::vector_property_map<Value, IndexMap> type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { return boost::make_vector_property_map<Value>(index); } };
template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator { typedef boost::is_base_and_derived< boost::vertex_list_graph_tag, typename boost::graph_traits<Graph>::traversal_category> known_num_vertices; typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper; typedef typename helper::type type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { return helper::build(g, index, array_holder); } }; }
And the corresponding default color helper resulting in VC6 compiler errors. (template already defined as non-template) I am stuck, if you could please advise me on how to rewrite these templates for VC6.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: 24. maj 2009 00:18 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph
On Sun, 24 May 2009, Lennart Berg wrote:
Sadly due to the restriction of the engine I have to stick with the now dated Visual C++ 6.
I am running with boost 1.35.
I have tried the last couple of hours to port the boost trunk to VC6 but it seems more or less hopeless for me. So unless the 25% speedup is a small patch that can be implemented, I dont see any change in the current setup. (The sparsed graph is calling out for a newer compiler)
I am currently looking into the parallel boost project and will try to get a previus trunk version to work with the 1.35.
You still should benchmark things in release mode. Please try that and see if it changes your performance behavior. The 25% speedup is a relatively small patch, but hasn't been tested on that old of a copy of Boost or on that compiler. To get that, copy over boost/graph/detail/d_ary_heap.hpp from a new copy of Boost and look at the diffs between the boost/graph/dijkstra_shortest_paths.hpp files to find the part where d_ary_heap is used. I think that can probably be ported over; the code is not using C++ in any fancy ways.
As to the compressed sparse row graph, you might be able to take out the vertex and edge property support and then use the vertex_index and edge_index property maps defined by the graph type as key to external property maps. I believe partial specialization is only required in there for bundled properties, which you can avoid by using external properties.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Well I need a path cost from one source to all possible destinations, so naturally I picked dijkstra. judging from the time complexity I thought dijstra would be faster than A* A*: O((E + V) log V). Dijkstra: O(V Log V) I have never given heuristics any thoughts. I still would like to hear how to solve the last issue to implement the new d-ary heap. But that might only give me a 5-10% boost. isn't there a way to do incremental updates to a graph instead of running a new total run every time? (changing edge weights and adding / removing edges on the fly, and then only update the vertexes that where affected by the update?) -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Ross Levine Sent: 21. juni 2009 05:17 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph Hi Lennart, Have you considered using astar_search instead of djikstra? With a good heuristic, A* can be much faster than Djikstra, which is a special case of A* where the heuristic is constant. On Fri, Jun 19, 2009 at 5:56 PM, Lennart Berg <LB@bl-logic.dk> wrote:
Hi
I have tried mixing and fixing the graph files for quite some time now.
the last problem I have met is that:
namespace detail { template <class Graph, class IndexMap, class Value, bool KnownNumVertices> struct vertex_property_map_generator_helper {}; template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> { typedef boost::iterator_property_map<Value*, IndexMap> type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { array_holder.reset(new Value[num_vertices(g)]); std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value()); return make_iterator_property_map(array_holder.get(), index); } };
template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> { typedef boost::vector_property_map<Value, IndexMap> type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { return boost::make_vector_property_map<Value>(index); } };
template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator { typedef boost::is_base_and_derived< boost::vertex_list_graph_tag, typename boost::graph_traits<Graph>::traversal_category> known_num_vertices; typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper; typedef typename helper::type type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { return helper::build(g, index, array_holder); } }; }
And the corresponding default color helper resulting in VC6 compiler errors. (template already defined as non-template) I am stuck, if you could please advise me on how to rewrite these templates for VC6.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: 24. maj 2009 00:18 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph
On Sun, 24 May 2009, Lennart Berg wrote:
Sadly due to the restriction of the engine I have to stick with the now dated Visual C++ 6.
I am running with boost 1.35.
I have tried the last couple of hours to port the boost trunk to VC6 but it seems more or less hopeless for me. So unless the 25% speedup is a small patch that can be implemented, I dont see any change in the current setup. (The sparsed graph is calling out for a newer compiler)
I am currently looking into the parallel boost project and will try to get a previus trunk version to work with the 1.35.
You still should benchmark things in release mode. Please try that and see if it changes your performance behavior. The 25% speedup is a relatively small patch, but hasn't been tested on that old of a copy of Boost or on that compiler. To get that, copy over boost/graph/detail/d_ary_heap.hpp from a new copy of Boost and look at the diffs between the boost/graph/dijkstra_shortest_paths.hpp files to find the part where d_ary_heap is used. I think that can probably be ported over; the code is not using C++ in any fancy ways.
As to the compressed sparse row graph, you might be able to take out the vertex and edge property support and then use the vertex_index and edge_index property maps defined by the graph type as key to external property maps. I believe partial specialization is only required in there for bundled properties, which you can avoid by using external properties.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
For A*, a heuristic should be ideally less than the actual minimum distance from the current point to the end. So for example, euclidean distance is often used. Also, A* tends to be faster if the Heuristic is good, since it tests fewer paths. On Sun, Jun 21, 2009 at 9:44 AM, Lennart Berg <LB@bl-logic.dk> wrote:
Well I need a path cost from one source to all possible destinations, so naturally I picked dijkstra.
judging from the time complexity I thought dijstra would be faster than A* A*: O((E + V) log V). Dijkstra: O(V Log V)
I have never given heuristics any thoughts.
I still would like to hear how to solve the last issue to implement the new d-ary heap.
But that might only give me a 5-10% boost.
isn't there a way to do incremental updates to a graph instead of running a new total run every time? (changing edge weights and adding / removing edges on the fly, and then only update the vertexes that where affected by the update?)
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Ross Levine Sent: 21. juni 2009 05:17 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph
Hi Lennart,
Have you considered using astar_search instead of djikstra? With a good heuristic, A* can be much faster than Djikstra, which is a special case of A* where the heuristic is constant.
On Fri, Jun 19, 2009 at 5:56 PM, Lennart Berg <LB@bl-logic.dk> wrote:
Hi
I have tried mixing and fixing the graph files for quite some time now.
the last problem I have met is that:
namespace detail { template <class Graph, class IndexMap, class Value, bool KnownNumVertices> struct vertex_property_map_generator_helper {}; template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> { typedef boost::iterator_property_map<Value*, IndexMap> type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { array_holder.reset(new Value[num_vertices(g)]); std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value()); return make_iterator_property_map(array_holder.get(), index); } };
template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> { typedef boost::vector_property_map<Value, IndexMap> type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { return boost::make_vector_property_map<Value>(index); } };
template <class Graph, class IndexMap, class Value> struct vertex_property_map_generator { typedef boost::is_base_and_derived< boost::vertex_list_graph_tag, typename boost::graph_traits<Graph>::traversal_category> known_num_vertices; typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper; typedef typename helper::type type; static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) { return helper::build(g, index, array_holder); } }; }
And the corresponding default color helper resulting in VC6 compiler errors. (template already defined as non-template) I am stuck, if you could please advise me on how to rewrite these templates for VC6.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto: boost-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: 24. maj 2009 00:18 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph
On Sun, 24 May 2009, Lennart Berg wrote:
Sadly due to the restriction of the engine I have to stick with the now dated Visual C++ 6.
I am running with boost 1.35.
I have tried the last couple of hours to port the boost trunk to VC6 but it seems more or less hopeless for me. So unless the 25% speedup is a small patch that can be implemented, I dont see any change in the current setup. (The sparsed graph is calling out for a newer compiler)
I am currently looking into the parallel boost project and will try to get a previus trunk version to work with the 1.35.
You still should benchmark things in release mode. Please try that and see if it changes your performance behavior. The 25% speedup is a relatively small patch, but hasn't been tested on that old of a copy of Boost or on that compiler. To get that, copy over boost/graph/detail/d_ary_heap.hpp from a new copy of Boost and look at the diffs between the boost/graph/dijkstra_shortest_paths.hpp files to find the part where d_ary_heap is used. I think that can probably be ported over; the code is not using C++ in any fancy ways.
As to the compressed sparse row graph, you might be able to take out the vertex and edge property support and then use the vertex_index and edge_index property maps defined by the graph type as key to external property maps. I believe partial specialization is only required in there for bundled properties, which you can avoid by using external properties.
-- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
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.
On Tue, 23 Jun 2009, Lennart Berg wrote: (snip)
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.
I don't think you need a visitor. You can change edge properties without changing the structure of the graph. If you set the weight of an edge to infinity (using the distance_inf value that is passed into dijkstra_shortest_paths, which is usually (std::numeric_limits<Dist>::max)()), it is as though it doesn't exist in the graph for Dijkstra's algorithm. You just need to check the output distance map for that value to determine if a vertex is unreachable. If turning on and off edges in the graph is the only structure modification you need, that might be a good way. Note that this saves you the add_edge cost, but Dijkstra will still need to traverse all of the edges including those that have infinite weight. -- Jeremiah Willcock
Mhh... I am a little confused. As I understand your post, dijstra recognizes "std::numeric_limits<Dist>::max" as beeing unreachable. That means that a graph like this: A-1-B-2-C-1-D-max-E-4-F-3-G Where StartVertex = A, will only have 4 ilterations, as we only have 4 edges on vertexes that are accessible. The rest will remain as MAX, as they have not been visited. Now is that correct, or does the djikstra graph go through ALL edges and vertices and just hit the limit on all edges after D-E. Or in short: Is the djikstra time static with a static mount of edges? Or does it recognize and shorten the search at inaccessible edges. -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jeremiah Willcock Sent: 23. juni 2009 15:42 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph On Tue, 23 Jun 2009, Lennart Berg wrote: (snip)
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.
I don't think you need a visitor. You can change edge properties without changing the structure of the graph. If you set the weight of an edge to infinity (using the distance_inf value that is passed into dijkstra_shortest_paths, which is usually (std::numeric_limits<Dist>::max)()), it is as though it doesn't exist in the graph for Dijkstra's algorithm. You just need to check the output distance map for that value to determine if a vertex is unreachable. If turning on and off edges in the graph is the only structure modification you need, that might be a good way. Note that this saves you the add_edge cost, but Dijkstra will still need to traverse all of the edges including those that have infinite weight. -- Jeremiah Willcock _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Lennart Berg wrote:
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.
Don't do performance tests in debug mode. In my experience compiler optimization speeds up heavily templated code by ~6X, versus about 20% speedup for heavily c-style code. Your real performance break down in optimized build could be very different from what you measured. In the extreme case add_edge may be inlined by the compiler and not even show up in your profiling. There is a certain challenge in profiling heavily inlined code, though, since it becomes hard to know which inline functions are taking up the runtime because their time is attributed to the caller. We had one standalone benchmark that heavily used templated code I had written that we eventually got the compiler to inline 100% of functions so that all runtime was attributed to main(). I have also compared two algorithms in debug build and found one to be faster than the other by 2X, but when compared in optimized algorithms the other was 4X faster than the first. The point is, unoptimized build performance is not a reliable indication of real performance, particularly when code is heavily templated (like boost graph.) Regards, Luke
On Fri, May 22, 2009 at 2:12 AM, Lennart Berg <LB@bl-logic.dk> wrote:
Hi Everybody
I have had the pleasure of using the boost graph library for my project now, but I have ran into some problems, that I hope you can guide me on.
First of all, let me tell a little about the project. I am a third party developer for paradox interactive, making an expansion for one of their games.
tell me it's Europa Universalis :)...
close... very close... Its Hearts of iron 2 -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of hurcan solter Sent: 22. maj 2009 15:20 To: boost@lists.boost.org Subject: Re: [boost] How to speed up the djikstra graph On Fri, May 22, 2009 at 2:12 AM, Lennart Berg <LB@bl-logic.dk> wrote:
Hi Everybody
I have had the pleasure of using the boost graph library for my project now, but I have ran into some problems, that I hope you can guide me on.
First of all, let me tell a little about the project. I am a third party developer for paradox interactive, making an expansion for one of their games.
tell me it's Europa Universalis :)... _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Just to be clear, are you computing the minimum total cost from a single initial point to all other accessible points within the country (single source shortest path problem) or are you computing minimum cost between all pairs of provinces within the country (all sources shortest path problem)? In the latter case, you should get a huge speed-up by using the Floyd–Warshall algorithm instead of repeated use of the Dijkstra algorithm. For the single source problem it's hard to see how you could improve on just repeating the Dijkstra algorithm for a dynamic graph -- even keeping around some form of traces of the original run -- since modifying the weight of any edge might switch the course of the algorithm to considering a path completely ignored originally. Without having thought it through too thoroughly, the information from a distance between all pairs of vertexes matrix (maybe with some trace info) might allow updating to be kept more localized. This might come out quite naturally from a slightly tweaked F-W algorithm, or perhaps from Johnson's algorithm (which is usually reserved for use in solving this problem for sparse graphs). In fact, it might be that you could get an overall lower cost by using F-W at the outset and then revising it, even if you really want the single-source shortest path problem (i.e., what Dijkstra's algorithm would normally be used for). I'm going to be traveling this weekend. Maybe I'll work on it, on the road. Topher Lennart Berg wrote:
First of all, let me tell a little about the project. I am a third party developer for paradox interactive, making an expansion for one of their games.
Now i have implemented the djikstra alghorithm to simulate the transport capacity of countries, and it works pretty well. However I still think that the speeds to be improved somewhat (takes about 1-2 secs to compute), to make it more playable.
First of all the map consists of ~2500 provinces / vertexes each with 4-8 edges / neighbours. I Find all the provinces I can access and then add all neighbours from it as edges. Each edge is allocated a cost according to infrastructure, terrain and distance from orgin to destination.
on Thu May 21 2009, "Lennart Berg" <LB-AT-BL-Logic.dk> wrote:
Now i have implemented the djikstra alghorithm
You mean you're using the dijkstra_shortest_paths algorithm from BGL, right? Just checking. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (8)
-
Andrew Sutton -
David Abrahams -
hurcan solter -
Jeremiah Willcock -
Lennart Berg -
Ross Levine -
Simonson, Lucanus J -
Topher Cooper