
Boost Users : 
Subject: Re: [Boostusers] [BGL] another question on grid_graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20120620 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
> (highdimensional) grid graph. For a simple and representative example
> in 2D, 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 performancesensitive context, you might want to look at a
library for discrete polyhedra such as PolyLib or the Parma Polyhedron
Library.
 Jeremiah Willcock
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net