Another quick thought. If you know the role of a node in your tree a-priori, that is you know that it's a root,inner,or leaf at the time you're actually inserting the vertices/edges into the BGL graph, then I would go with the external multimap solution and build that in parallel with building the graph. Then as soon as the graph was built, you could directly get an iterator on the multimap (using a simple predicate that returned an multimap::iterator by type) where vertex_desc = (*iter).second. This saves you three graph filter operations (maybe significant, maybe not?). Plusses: higher performance, simple. Minuses: need to know roll of tree node a-priori, changing the graphs vertex or edge sets invalidates external multimap forcing you to rebuild it (requires at least one traversal of the graph). I have something similar I need to figure out soon so any comments on my proposed solutions would be instructive and appreciated. - Chris "Chris Russell" wrote in message news:amptik$ab0$1@main.gmane.org...

Hi Björn, Several ideas that may or may not be appropriate to the specifics of your situation:

First an observation: your internal property ROOT,LEAF,INNER is actually redundant information. Given a vertex descriptor, this information can be deduced by examining the number of in and out edges. If ((some in edges) AND (some out edges)) then INNER, if ((some in edges) AND (no out edges)) then LEAF, if ((no in edges)) then ROOT. I've found that it's most convenient to use bidirectionalS so that I can easily get at both in and out edge degrees given a vertex desc.

You could iterate over all the vertices, examine the in and out degrees and build an external multimap, and then iterate over the multimap by type predicate. OR, write three little predicates and use them to filter the graph? You could filter the graph by, for example PredicateLeafNode, and then get a vertex iterator on the filtered graph. I think this would do what you want with the existing BGL infrastructure. But maybe I'm missing something important here.

- Chris

"Björn Lindberg" wrote in message news:3D9059C8.AFD80D45@nada.kth.se...

...

I have a BGL graph (adjacency_list). I use it to represent a tree, and so I have an internal vertex property of type enum representing the node type, ie ROOT, LEAF, INNER.

Now, I would like a way to access only the leaves of a tree, preferrably through iterators. I can't think of any good way to accomplish this, except possibly by writing new iterator classes which would internally keep track of a property map and thus hide traversal of the non-leaf nodes from the code using the iterators. This seems like a cumbersome approach though, and I'm hoping there is a simpler way?

Björn