[Lemon-devel] [Lemon-commits] deba: r3073 - hugo/trunk/lemon

[Alpár Jüttner]

Balazs,

have you carried out any running time test (compared to the previous
version) on the changes below? What was the result?

Regards,
Alpar


On Mon, 2006-11-13 at 13:31 +0100, Lemon SVN wrote:
> Author: deba
> Date: Mon Nov 13 13:30:59 2006
> New Revision: 3073
> 
> Modified:
>    hugo/trunk/lemon/bfs.h
> 
> Log:
> Conditional execution until the target is reached 
> /previous implementation: until the target is the next to process/
> 
> todo: query the target when we give nodemap as condition
> 
> 
> 
> Modified: hugo/trunk/lemon/bfs.h
> ==============================================================================
> --- hugo/trunk/lemon/bfs.h	(original)
> +++ hugo/trunk/lemon/bfs.h	Mon Nov 13 13:30:59 2006
> @@ -478,6 +478,72 @@
>  	}
>        return n;
>      }
> +
> +    ///Processes the next node.
> +
> +    ///Processes the next node. And checks that the given target node
> +    ///is reached. If the target node is reachable from the processed
> +    ///node then the reached parameter will be set true. The reached
> +    ///parameter should be initially false.
> +    ///
> +    ///\param target The target node.
> +    ///\retval reached Indicates that the target node is reached.
> +    ///\return The processed node.
> +    ///
> +    ///\warning The queue must not be empty!
> +    Node processNextNode(Node target, bool& reached)
> +    {
> +      if(_queue_tail==_queue_next_dist) {
> +	_curr_dist++;
> +	_queue_next_dist=_queue_head;
> +      }
> +      Node n=_queue[_queue_tail++];
> +      _processed->set(n,true);
> +      Node m;
> +      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
> +	if(!(*_reached)[m=G->target(e)]) {
> +	  _queue[_queue_head++]=m;
> +	  _reached->set(m,true);
> +	  _pred->set(m,e);
> +	  _dist->set(m,_curr_dist);
> +          reached = reached || (target == m);
> +	}
> +      return n;
> +    }
> +
> +    ///Processes the next node.
> +
> +    ///Processes the next node. And checks that at least one of
> +    ///reached node has true value in the \c nm nodemap. If one node
> +    ///with true value is reachable from the processed node then the
> +    ///reached parameter will be set true. The reached parameter
> +    ///should be initially false.
> +    ///
> +    ///\param target The nodemaps of possible targets.
> +    ///\retval reached Indicates that one of the target nodes is reached.
> +    ///\return The processed node.
> +    ///
> +    ///\warning The queue must not be empty!
> +    template<class NM>
> +    Node processNextNode(const NM& nm, bool& reached)
> +    {
> +      if(_queue_tail==_queue_next_dist) {
> +	_curr_dist++;
> +	_queue_next_dist=_queue_head;
> +      }
> +      Node n=_queue[_queue_tail++];
> +      _processed->set(n,true);
> +      Node m;
> +      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
> +	if(!(*_reached)[m=G->target(e)]) {
> +	  _queue[_queue_head++]=m;
> +	  _reached->set(m,true);
> +	  _pred->set(m,e);
> +	  _dist->set(m,_curr_dist);
> +          reached = reached || nm[m];
> +	}
> +      return n;
> +    }
>        
>      ///Next node to be processed.
>  
> @@ -537,7 +603,8 @@
>      ///
>      void start(Node dest)
>      {
> -      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
> +      bool reached = false;
> +      while ( !emptyQueue() && !reached) processNextNode(dest, reached);
>      }
>      
>      ///Executes the algorithm until a condition is met.
> @@ -549,10 +616,12 @@
>      ///
>      ///\param nm must be a bool (or convertible) node map. The algorithm
>      ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
> +    ///\todo query the reached target
>      template<class NM>
>      void start(const NM &nm)
>      {
> -      while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
> +      bool reached = false;
> +      while ( !emptyQueue() && !reached) processNextNode(nm, reached);
>      }
>      
>      ///Runs %BFS algorithm from node \c s.
> @@ -593,7 +662,7 @@
>        init();
>        addSource(s);
>        start(t);
> -      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
> +      return reached(t)? _curr_dist : 0;
>      }
>      
>      ///@}
> _______________________________________________
> Lemon-commits mailing list
> Lemon-commits at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-commits
-- 
In order to prevent people from receiving viruses
that would seem to originate from my email,
if you use Microsoft Windows you do not have permission
to add this address to your address book.
If I am in your address book, please remove me.
Of course, this does not apply to GNU/Linux users. 
Thank you.