[BGL]: Highest performance graph-type available?
I'm using BGL for the johnson_all_pairs_shortest_path algorithm, and spending about 98% of my runtime in that algorithm. Breaking it down, the BFS_visit itself is consuming some 85% of my total runtime. Hence, any and every improvement I can get in my BGL performance will make my app much much snappier. Currently, my graph type is a adjacency_list <vecS, vecS, undirectedS, no_property, property <edge_weight_t, double> > and I'm wondering if that's the best choice. My graph has (E=2*V), and all nodes are of constant degree, with 4 edges incident on them. V is usually in the range of 150-500. Would one of the other types (such as listS) perhaps be faster, and still work? I know some BGL algorithms require certain graph storage types, so I'm hesitant to just start poking around and trying random things. That, and other than "listS", I don't know of any other types of graph, as I'm quite new to both the BGL and boost in general. Any thoughts on what might make things faster? Additionally, are there any compiler flags I should consider other than the 'vanilla' ones? (-O3). I'm using GCC 4.0.1 currently, if it matters. Thanks for the great library, and such a friendly list, Greg Link
Greg Link <link@cse.psu.edu> writes:
I'm using BGL for the johnson_all_pairs_shortest_path algorithm, and spending about 98% of my runtime in that algorithm. Breaking it down, the BFS_visit itself is consuming some 85% of my total runtime. Hence, any and every improvement I can get in my BGL performance will make my app much much snappier.
Currently, my graph type is a
adjacency_list <vecS, vecS, undirectedS, no_property, property <edge_weight_t, double> >
and I'm wondering if that's the best choice. My graph has (E=2*V), and all nodes are of constant degree, with 4 edges incident on them. V is usually in the range of 150-500.
Oh, it sounds to me like you could probably eke some mileage out of a custom graph data structure. There's no need to use the supplied adjacency_list; you can just build something that meets all the appropriate graph concept requirements and minimally satisfies your needs. For example, you could think about using a vector of these: struct node { node* neighbors[4]; }; That will save a bunch of allocations in constructing the graph (you probably don't care about these much) and a bunch of indirections in traversing it, which could affect speed. You might also think about struct node { unsigned short neighbor_indices[4]; }; which might buy you some speed through improved cache locality if a short is smaller than a pointer on your system.
Would one of the other types (such as listS) perhaps be faster, and still work?
Unlikely.
I know some BGL algorithms require certain graph storage types,
Not really. If you look at the requirements of the algorithms, you won't see anything mentioned about storage.
Any thoughts on what might make things faster? Additionally, are there any compiler flags I should consider other than the 'vanilla' ones? (-O3). I'm using GCC 4.0.1 currently, if it matters.
-O3 -funroll-loops -finline-functions HTH, -- Dave Abrahams Boost Consulting www.boost-consulting.com
Greg Link wrote:
I'm using BGL for the johnson_all_pairs_shortest_path algorithm, [snip] and I'm wondering if that's the best choice. My graph has (E=2*V), and all nodes are of constant degree, with 4 edges incident on them.
Hi Grek, Probably there is better algorithm for your original problem). Could you describe in brief it? Regards, --dima
Dima - I've got a 2D grid-structure, of some size "n x n". Each point in the grid is connected to it's four neighboring and adjacent cells in the grid by an edge. The edges (and their weights) represent the delay to travel between those two points in the grid. The weight of the edges is non-uniform, and determined at run-time. I have a set of {X1,Y1} and {X2,Y2} pairs that I want to find the shortest path between. The set is 'large'. Rather than running the standard dijkstra_shortest_path, and therefore having a run-time of O (num_pairs * V^2), I use johnson to find the all_pairs paths, at a cost of O(V*E*log(V)). Since E=2*V, that's effectively (V^2 log(V)). For any num_pairs > log(V), the johnson algorithm /should/ be faster. I do this a number of times (10 million), constructing a new graph each time, putting the edges in, and then solving the all_pairs paths. Profling the code shows that the graph construction is fairly trivial compared to the actual johnson algorithm (and the BFS_Visitor beneath that). Anything else that might help? Thanks for your interest, - Greg On May 11, 2006, at 10:53 AM, Dmitry Bufistov wrote:
Greg Link wrote:
I'm using BGL for the johnson_all_pairs_shortest_path algorithm, [snip] and I'm wondering if that's the best choice. My graph has (E=2*V), and all nodes are of constant degree, with 4 edges incident on them.
Hi Grek, Probably there is better algorithm for your original problem). Could you describe in brief it? Regards, --dima
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On 5/11/06, Greg Link <link@cse.psu.edu> wrote:
I've got a 2D grid-structure, of some size "n x n". Each point in the grid is connected to it's four neighboring and adjacent cells in the grid by an edge. The edges (and their weights) represent the delay to travel between those two points in the grid. The weight of the edges is non-uniform, and determined at run-time.
I have a set of {X1,Y1} and {X2,Y2} pairs that I want to find the shortest path between.
Have you looked into using the A* search? I'm not a BGL expert, but since you are working on a grid, you should probably just be using an implicit graph. I think there is mention of that in the A* BGL docs. You can calculate your neighbors given your current position and the offset to the neighboring grid cells. That way you would only be allocating nodes that were actually worth looking at. HTH, --Michael Fawcett
Dima - I've got a 2D grid-structure, of some size "n x n". Each point in the grid is connected to it's four neighboring and adjacent cells in the grid by an edge. The edges (and their weights) represent the delay to travel between those two points in the grid. The weight of the edges is non-uniform, and determined at run-time.
I have a set of {X1,Y1} and {X2,Y2} pairs that I want to find the shortest path between. The set is 'large'. Rather than running the standard dijkstra_shortest_path, and therefore having a run-time of O (num_pairs * V^2), I use johnson to find the all_pairs paths, at a cost of O(V*E*log(V)). Since E=2*V, that's effectively (V^2 log(V)). For any num_pairs > log(V), the johnson algorithm /should/ be faster.
I do this a number of times (10 million) If every time your delays being changed at the same value, then you
Greg Link wrote: probably don´t need to rerun shortest pathes algorithm every time, you just can recalculate all you shortest-pathes trees in linear time as described here http://arxiv.org/PS_cache/cs/pdf/0205/0205041.pdf (Note sure that even in this case it will increase perfomance, but if you are really concerned about it then you can try) --dima
participants (4)
-
David Abrahams -
Dmitry Bufistov -
Greg Link -
Michael Fawcett