On Tue, 27 Nov 2012, Dave Abrahams wrote:
Hi,
I was just trying to work up an example for a class I'm teaching, to illustrate implicit graphs. The following shows how far I've gotten:
https://gist.github.com/4153918
This is attempting to apply Warnsdorff's heuristic (choose the next move with the least out-degree) using A* search. I'm running into several problems having to do with the requirements of astar_search_no_init. In particular, the requirement that we can assign an index to every vertex is quite painful, since enumerating all the possible vertices in the search space is difficult. Any advice here? I suppose I could keep a real map and simply assign indices in the order vertices are encountered, but that seems pretty ugly to me.
I think that's the best you can do with the current code. Longer-term, it would be better to make IndexInHeapMap a parameter so that you can replace it with an associative property map. Even now, you might want to use associative_property_maps for distance_map, rank_map, and color_map to avoid going through the index table for those. -- Jeremiah Willcock