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

Subject: Re: [Boost-users] [BGL] another question on grid_graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-06-20 13:23:02

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