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

From: Chris Russell (cdr_at_[hidden])
Date: 2002-09-24 10:08:53

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" <cdr_at_[hidden]> wrote in message
news:amptik$ab0$1_at_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<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
> >
> >
> >
> >
>
>
>
>
>