lemon/dfs.h
changeset 1209 4a170261cc54
parent 1197 f179aa1045a4
equal deleted inserted replaced
48:291c79ee681f 49:05255451c8e2
   179     //Pointer to the map of processed status of the nodes.
   179     //Pointer to the map of processed status of the nodes.
   180     ProcessedMap *_processed;
   180     ProcessedMap *_processed;
   181     //Indicates if _processed is locally allocated (true) or not.
   181     //Indicates if _processed is locally allocated (true) or not.
   182     bool local_processed;
   182     bool local_processed;
   183 
   183 
   184     std::vector<typename Digraph::OutArcIt> _stack;
   184     std::vector<typename Digraph::Arc> _stack;
   185     int _stack_head;
   185     int _stack_head;
   186 
   186 
   187     //Creates the maps if necessary.
   187     //Creates the maps if necessary.
   188     void create_maps()
   188     void create_maps()
   189     {
   189     {
   455       LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
   455       LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
   456       if(!(*_reached)[s])
   456       if(!(*_reached)[s])
   457         {
   457         {
   458           _reached->set(s,true);
   458           _reached->set(s,true);
   459           _pred->set(s,INVALID);
   459           _pred->set(s,INVALID);
   460           OutArcIt e(*G,s);
   460           Arc e;
       
   461           G->firstOut(e,s);
   461           if(e!=INVALID) {
   462           if(e!=INVALID) {
   462             _stack[++_stack_head]=e;
   463             _stack[++_stack_head]=e;
   463             _dist->set(s,_stack_head);
   464             _dist->set(s,_stack_head);
   464           }
   465           }
   465           else {
   466           else {
   482       Arc e=_stack[_stack_head];
   483       Arc e=_stack[_stack_head];
   483       if(!(*_reached)[m=G->target(e)]) {
   484       if(!(*_reached)[m=G->target(e)]) {
   484         _pred->set(m,e);
   485         _pred->set(m,e);
   485         _reached->set(m,true);
   486         _reached->set(m,true);
   486         ++_stack_head;
   487         ++_stack_head;
   487         _stack[_stack_head] = OutArcIt(*G, m);
   488         G->firstOut(_stack[_stack_head],m);
   488         _dist->set(m,_stack_head);
   489         _dist->set(m,_stack_head);
   489       }
   490       }
   490       else {
   491       else {
   491         m=G->source(e);
   492         m=G->source(e);
   492         ++_stack[_stack_head];
   493         G->nextOut(_stack[_stack_head]);
   493       }
   494       }
   494       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
   495       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
   495         _processed->set(m,true);
   496         _processed->set(m,true);
   496         --_stack_head;
   497         --_stack_head;
   497         if(_stack_head>=0) {
   498         if(_stack_head>=0) {
   498           m=G->source(_stack[_stack_head]);
   499           m=G->source(_stack[_stack_head]);
   499           ++_stack[_stack_head];
   500           G->nextOut(_stack[_stack_head]);
   500         }
   501         }
   501       }
   502       }
   502       return e;
   503       return e;
   503     }
   504     }
   504 
   505 
   508     ///
   509     ///
   509     ///\return The next arc to be processed or \c INVALID if the stack
   510     ///\return The next arc to be processed or \c INVALID if the stack
   510     ///is empty.
   511     ///is empty.
   511     OutArcIt nextArc() const
   512     OutArcIt nextArc() const
   512     {
   513     {
   513       return _stack_head>=0?_stack[_stack_head]:INVALID;
   514       return OutArcIt(*G,_stack_head>=0?_stack[_stack_head]:INVALID);
   514     }
   515     }
   515 
   516 
   516     ///Returns \c false if there are nodes to be processed.
   517     ///Returns \c false if there are nodes to be processed.
   517 
   518 
   518     ///Returns \c false if there are nodes to be processed
   519     ///Returns \c false if there are nodes to be processed