Hi Himar,
actually I realized that I do not need an exact case of BFS or DFS. In my case
I need some kind of mixture processing. Thus every group node has to be
processed until after every of its parents has been processed. So in my case I
found a solution by using standard osg's DFS traverser with small changes while
traversing groups.
However, the same code as you posted here, I have also tried. But as I said, it
didn't helped me. But I am glad to see a solution for that. In deed I tried
different examples on the paper and it seems to work, but didn't made any
proove to show that this in deed a correct algorithm :)
So maybe it could help somebody in the future.
regards,
art
Himar Carmona wrote:
> Hi,
>
> i agree with both of you. Queue seems to be necessary. I coded a
> BFS node visitor in response to this thread. Here is the code:
>
> class BFSNodeVisitor: public osg::NodeVisitor
> {
> public:
>
> std::queue<osg::ref_ptr<osg::Node>> _pendingNodesToVisit;
>
> BFSNodeVisitor() : osg::NodeVisitor(
> osg::NodeVisitor::TRAVERSE_ALL_CHILDREN )
> {
> }
>
> virtual void apply ( osg::Node& node )
> {
> std::cout << "Processing " << node.getName() << std::endl;
> }
>
> virtual void apply ( osg::Group& group )
> {
> std::cout << "Processing " << group.getName() << std::endl;
> for(int i = 0; i < group.getNumChildren(); i++)
> {
> _pendingNodesToVisit.push(group.getChild(i));
> }
> while(_pendingNodesToVisit.size() != 0)
> {
> osg::Node* node = _pendingNodesToVisit.front();
> _pendingNodesToVisit.pop();
> node->accept(*this);
> }
> }
> };
>
> I tested it with a little test scene and this seems to do the job (but
> not tested in a true complex graph). This code do a BFS traversal
> through the scene graph, with two noticeable points to take into
> account:
>
> 1) As a node can have more than one parent, this code will traverse
> the node so many times as it has parents (same behavior as the depth
> traverse implemented in OSG).
>
> 2) The scene graph must be acyclic, since this code doesn't have any
> visited flag or stop condition. If there were a cycle in the scene
> graph, the queue would never emptied and the while loop (recursive)
> would never stop.
>
> It works exactly like Art Tevs says, visit the node and then add its
> children to a queue. I suppose Art will have already his code
> complete, but i post it for other interested readers (or just Art
> could have another solution). Just a half hour of coding (ughhh), so
> take it as it is: no more than a possible starting point. Perhaps
> someone smarter can optimize it a bit (for example, avoiding queue
> growing up to much), but remember a tenet of optimization: Optimizing
> memory normally involves more code (and hence less optimized execution
> time) and viceversa. :)
>
> Hope this helps and best regards,
> Himar.
>
> 2009/10/23 Jason Daly <>:
>
> > Art Tevs wrote:
> >
> > >
> > > In deed, current osg implementation uses recursion to traverse over the
> > > graph. Which is very suitable for DFS. Implementing BFS with recursion is
> > > not that easy, then DFS. The way, how I can solve that problem would be to
> > > write a method which just iteratively collects nodes in a queue and then
> > > apply the new visitor on each node. Does anybody has other ideas? Or maybe
> > > somebody can correct me if I am doing mistakes here.
> > >
> > >
> >
> > A BFS will always involve a queue, by its very nature, in the same way that
> > a DFS always involves a stack (usually the stack of recursive calls, but you
> > can also do a DFS iteratively by implementing your own stack).
> >
> > You're right, it's not easy (if it's even possible) to implement a BFS
> > recursively.
> >
> > --"J"
> > _______________________________________________
> > osg-users mailing list
> >
> > http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
> >
> >
> _______________________________________________
> osg-users mailing list
>
> http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
>
> ------------------
> Post generated by Mail2Forum
------------------
Read this topic online here:
http://forum.openscenegraph.org/viewtopic.php?p=18648#18648
_______________________________________________
osg-users mailing list
osg-users@lists.openscenegraph.org
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
