On Tue, Sep 2, 2014 11:29 AM MDT Jeremiah Willcock wrote:
On Sun, Aug 31, 2014 10:53 PM MDT Nicholas Dahm wrote:
On Wed, Aug 27, 2014 7:24 PM EDT Nicholas Dahm wrote:
Is there any place where I could enforce unique properties? (i.e. not add a new vertex if it's properties are the same as an existing vertex)
Not that I know of.
My graph is actually an implicit search tree for an A* search so there's lots of nodes which will be revisited via different paths. My current thought is to create the new vertex (which is a search tree state), then simply iterate through all existing vertices to see if any are identical in properties. However if the vertices were sorted by their properties in a set (i.e. weakly ordered), this would be much faster.
Do you need to store the explored part of the search tree explicitly? You could instead use a custom graph type with your choice of vertex descriptor, then use associative_property_map to check for multiple visits to the same state.
No need to store the explored part. I have exactly zero clue on how to create a custom graph type with a special vertex descriptor. At current I've gotten around it by having a "set" of vertex descriptors which use a custom "less" function which actually checks the vertex bundled properties instead of the descriptor. It's not the perfect solution but it wasn't very ugly either so it'll do. If you have a link to info on how to create custom graph types with special vertex descriptors please do let me know
Please look at https://github.com/wpm/Boost-Implicit-Graph-Example for a simple example. You only need to do the incident edge iterator and property parts from that example, and can skip the other iterator types. There is also an A*-specific example at https://github.com/wpm/Astar-Maze-Solver, but it stores more of the data explicitly and uses existing BGL graph types.
-- Jeremiah Willcock
There is also http://www.boost.org/doc/libs/1_56_0/libs/graph/example/knights-tour.cpp as an example, but you'll probably need the BGL book for its documentation. -- Jeremiah Willcock