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.

On Sun, Jul 4, 2010 at 7:48 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Sun, 4 Jul 2010, W.P. McNeill wrote:

The property type problem was because I didn't have property_traits<> correctly defined. I rewrote this from scratch and defined my own grid object instead of using Boost's grid_graph.  Now I can get a-star to run, but only if I use the latest version of astar_search.hpp.  If I use the Boost 1.42 version installed on my machine by Macports, it fails to compile because of bug 3917.

Is 3917 fixed in version 1.43?  (I'm guessing that's what the struckthrough "Boost 1.43.0" in the Milestone field of the bug report means.)

I'm pretty sure the fix made it into 1.43.  The milestone fields are not really up to date, though.  Are you now using your own graph class just in order to add an internal property map?

-- Jeremiah Willcock
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users