Re: [Boost-users] [BGL] another question on grid_graph

Subject: Re: [Boost-users] [BGL] another question on grid_graph
From: Alex Sadovsky (a_sadovsky_at_[hidden])
Date: 2012-06-20 13:07:19

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