[Boost Graph Library] larger neighborhood in grid_graph
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? - 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) Thank you very much! Hannes
--- On Tue, 2/1/11, Hannes Schulz wrote:
I recently discovered grid_graph and found it quite useful so far.
I *just* discovered this in the trunk. Too bad I don't share your enthusiasm, which I normally have for BGL utilities.
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.
Not to mention the proximity of the impending release.
Therefore I decided to ask here first:
- Why did the developers restrict grid_graph to "orthogonal" neighborhoods?
+1 for this question. I wouldn't be able to use it in my game_of_life example program from my automaton library.
- 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)
Personally, I'm taking the algorithmic approach. (Look up Algorithms/graph/intrusive_layout.zip in the Vault.) Cromwell D. Enage
On 01/02/2011 6:53 AM, 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?
- 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)
Thank you very much!
Hannes
I agree, in my case the movement is restricted to 45 degree (along 8 cardinal directions) rotations with a 135 degree forward-facing point of view (ie, move forward, turn left or right), with the right number of dimensions the vertex addressing was suitable as-is, but out-edge traversal had to be reworked. I read in the documentation that the decision was made for the graph abstraction to consist of both vertex and edge traits (ie. within boost::graph_traits), I believe this is one case though where I feel having separate vertex and edge traits classes (which graph_traits might then bring together into one binding interface) to allow customization only of edge traversal would have been nice. Thanks, Geoff
participants (2)
-
Cromwell Enage -
Geoff Hilton -
Hannes Schulz