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