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

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

...

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.htm... :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.htm... :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