Boost logo

Boost :

Subject: Re: [boost] [Boost Graph Library] larger neighborhood in grid_graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-01-31 17:18:51


On Mon, 31 Jan 2011, Hannes Schulz wrote:

> Hi all,
>
> i recently discovered grid_graph and found it quite useful so far.
>
> However, I would prefer a larger neighborhood in the graph (e.g. 8 instead of
> 4 for 2D; 26 instead of 6 in 3D). I already started looking into copying and
> modifying grid_graph.hpp accordingly, but cannot entirely anticipate the
> complexity of the problem. Therefore I decided to ask here first:
>
> - Why did the developers restrict grid_graph to "orthogonal" neighborhoods?

It was simpler that way; there is not a really strong reason other than
that is what we thought people needed.

> - Is a modification of grid_graph worth it, or am I going to throw away
> everything anyway and should start over anew instead? (without the wrapping
> overhead, which I do not need)

Try to copy-and-hack the grid_graph first, get it to work, then we can
discuss merging it into the original grid_graph codebase. There are a lot
of details in there, but you should be able to pick out the key parts that
search for vertex neighbors, which is what you need to change. In
particular, here are some members of grid_graph to look at and possibly
change:

next() [maybe]
previous() [maybe]
num_edges()
edge_at()
index_of(edge_descriptor)
out_degree()
out_edge_at()
in_degree() [maybe]
in_edge_at() [maybe]
precalculate() [maybe]

plus the following free function:

edge()

-- Jeremiah Willcock


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk