Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net