Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search

Subject: Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-05 17:06:14

On Mon, 5 Jul 2010, W.P. McNeill wrote:

> I'm using my own graph class because I need an implicit graph for the task I'm trying to do.
> 
> Here's the full background: I'm writing a program that solves a maze using a-star search.  (It's on github as Searchable Graph Example.)
> Â The maze is a grid of cells in which you can move up, down, right and left. Â Cells are either empty or blocked. Â The cost of entering an
> empty cell is 1, and the cost of entering a blocked cell is infinity.
> (This is actually a warm-up for a more sophisticated graph search program, but that one also operates on a grid, so a lot of this code
> will be reusable. Â Plus, I think an a-star maze search example would be useful for others to see.)
> 
> Because the graph topology is a grid, it seemed like the best way to implement this is with an implicit graph. Â I first tried adding edge
> and vertex properties to Boost's grid_graph class, but I ran into compile errors, some of which are documented earlier in this thread.
> Â Even after I worked around those errors I hit others, and it seemed like I was writing an awful lot of boilerplate code to use
> grid_graph, so it would be easier to implement my own grid.
> 
> Now I'm writing my own grid class (called maze_search::maze in the code on github). Â It will have an out edge iterator that determines
> the the grid structure, a read/write boolean vertex property for whether or not a cell is blocked, and a read-only edge weight property
> that returns the cost of entering a cell. Â I've finished the iterator and the edge weight property, and am starting to look at the vertex
> property.

Why not just have a class that contains a grid_graph and property maps for 
the vertices and edges?  You can use grid_graph's vertex_index and 
edge_index maps to provide indices for iterator_property_maps for those 
properties.  You can also use external properties that you keep as 
separate data structures and pass into algorithms explicitly; that I think 
would be much easier than what you're doing.  The Knight's Tour example 
uses something similar, but its property map implementation is custom and 
overcomplicated because the graph there doesn't have vertex_index and 
edge_index properties.  If you look in 
libs/graph/test/random_spanning_tree_test.cpp (in the trunk and 1.44), 
there is an example of using external properties with a grid_graph.  It 
just seems to me that what you're doing should not require a new graph 
type and should actually be fairly simple, even if it doesn't seem that 
way from the documentation.

-- Jeremiah Willcock