Re: [Boost-users] [graph] Unique vertices using setS

Subject: Re: [Boost-users] [graph] Unique vertices using setS
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2014-08-29 14:50:26

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.

-- Jeremiah Willcock