[BGL] grid_graph, vertex_index and shared_ptr
Hello, Recently I've found that the vertex_index property map of grid_graph holds a shared_ptr to a graph copy. Is there any reason for it? Actually, other classes which are tied with grid_graph holds it by plain pointer. Switching to it in grid_graph_index_map almost doubled the performance on some of my algorithms. Even copying the graph object by value (which actually holds 5 fields with 3 being small boost::array) still has better performance than using shared_ptr. Maybe it should be switched to plain pointer? -- ------------ Sergey Mitsyn.
On Wed, 20 Jun 2012, Sergey Mitsyn wrote:
Hello,
Recently I've found that the vertex_index property map of grid_graph holds a shared_ptr to a graph copy. Is there any reason for it?
Actually, other classes which are tied with grid_graph holds it by plain pointer. Switching to it in grid_graph_index_map almost doubled the performance on some of my algorithms. Even copying the graph object by value (which actually holds 5 fields with 3 being small boost::array) still has better performance than using shared_ptr.
Maybe it should be switched to plain pointer?
I've made that change on the trunk in r79017. -- Jeremiah Willcock
Several questions: (1) Is there support for mapping the index of a vertex to the coordinate multiindex of that vertex? E.g., in the example on http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/grid_graph.html (bottommost image) , if vertex 6 is taken as the origin (0, 0), I'd like to be able to map vertex 5 to the multiindex (2, 1), assuming the horizontal coordinate increases left to right, and the vertical one upwards. (2) I'd like to build economically a certain subgraph of a (high-dimensional) grid graph. For a simple and representative example in 2-D, assuming the multiindexing convention of the pervious question, I'd like to keep only those vertices (x, y) satisfying k1 x < y < k2 x, where k1 and k2 are positive constants between 0 and 1. This gives a subgraph with vertices lying in a "wedge" bounded by the lines with slopes k1 and k2. (In higher dimensions, the above double inequality would be imposed for every pair of coordinates, giving a polyhedral cone.) Is it feasible first to build a grid graph and then exclude the unwanted vertices, or is this too computationally prohibitive and should be abandoned in favor of something more clever? Thanks, Alex
On Wed, 20 Jun 2012, Alex Sadovsky wrote:
Several questions:
(1) Is there support for mapping the index of a vertex to the coordinate multiindex of that vertex? E.g., in the example on http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/grid_graph.html (bottommost image) , if vertex 6 is taken as the origin (0, 0), I'd like to be able to map vertex 5 to the multiindex (2, 1), assuming the horizontal coordinate increases left to right, and the vertical one upwards.
Yes -- the function is named vertex(), and the corresponding one for edges is edge_at().
(2) I'd like to build economically a certain subgraph of a (high-dimensional) grid graph. For a simple and representative example in 2-D, assuming the multiindexing convention of the pervious question, I'd like to keep only those vertices (x, y) satisfying k1 x < y < k2 x, where k1 and k2 are positive constants between 0 and 1. This gives a subgraph with vertices lying in a "wedge" bounded by the lines with slopes k1 and k2. (In higher dimensions, the above double inequality would be imposed for every pair of coordinates, giving a polyhedral cone.) Is it feasible first to build a grid graph and then exclude the unwanted vertices, or is this too computationally prohibitive and should be abandoned in favor of something more clever?
Try using a filtered_graph on top of your grid_graph, but if you are doing this in a performance-sensitive context, you might want to look at a library for discrete polyhedra such as PolyLib or the Parma Polyhedron Library. -- Jeremiah Willcock
participants (3)
-
Alex Sadovsky -
Jeremiah Willcock -
Sergey Mitsyn