Re: [Boost-users] [Graph] depth_first_search and specifying the edge order

From: Gordon Woodhull (gordon_at_[hidden])
Date: 2008-08-04 16:49:33

On Aug 2, 2008, at 4:54 PM, Pedro Teixeira wrote:
> I don't think you can do that. Can't you implement whatever rule you  
> want on with a custom visitor?

The problem with using a visitor is that it's too late to sort the  
edges at that time (would slow down search considerably).  What I  
think you want to do is maintain the edges in the correct order - i.e.  
customize the edge storage container.

> On Wed, Jul 30, 2008 at 5:52 PM, David Walthall <walthall_at_[hidden] 
> > wrote:
> Hello.  I have a graph that I'd like to run a depth first search  
> on.  Is it possible to control the order that edges for each node  
> are traversed?  I read through the documentation, but I didn't see  
> anything that would do this.
>
I believe that this is possible with BGL adjacency_list, but I haven't  
tried it myself.

What you would do is to specify your own edge container with your own  
custom ordering - see
http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/using_adjacency_list.html#sec 
:choosing-graph-type
and especially the container generator stuff here:
http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/using_adjacency_list.html#sec 
:custom-storage

You would probably use a set (ordered however you want) and then tell  
BGL it's a non-associative sequence so it doesn't try to check for  
parallel edges that way.

Again, I haven't tried this myself, but it is my understanding that  
the customized storage mechanism is there expressly to allow alternate  
ordering and multi-indexing, etc.

Gordon