Re: [BGL]: Iterating through internal properties of specific value

From: Chris Russell (cdr_at_[hidden])
Date: 2002-09-24 09:41:29

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<type, vertex_desc>, 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" <yg-boost-users_at_[hidden]> wrote in message
news:3D9059C8.AFD80D45_at_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
>
>
>
>