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

From: Gordon Woodhull (gordon_at_[hidden])
Date: 2008-08-06 22:55:45

On Aug 6, 2008, at 1:17 PM, David Walthall wrote:

> Hi Gordon,
>
> Gordon Woodhull wrote:
>>> 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
>
> I didn't see anything in the documentation of adjacency_list that  
> specified the order that they would be visited, and I don't want to  
> rely on an implementation detail of the depth first search.  Did I  
> miss a mention of the ordering in there, or is it just implicit?

The ordering comes from the container that is used to store the edges  
in each node.

Again, I'm only an observer of the BGL and haven't written extensive  
code with it, but I would assume that if you used vector or list for  
your edge container type then you would get edge traversal in the  
order that the edges were created, because all it's doing is putting  
the edges into the source and target nodes' edge containers as you  
create them.

If that's not the ordering that you want, then there are customization  
options so that you can substitute your own edge container with  
whatever ordering predicate you want.

Gordon