equal
deleted
inserted
replaced
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 |