dfs.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_DFS_H
00020 #define LEMON_DFS_H
00021 
00025 
00026 #include <lemon/list_graph.h>
00027 #include <lemon/graph_utils.h>
00028 #include <lemon/invalid.h>
00029 #include <lemon/error.h>
00030 #include <lemon/maps.h>
00031 
00032 #include <lemon/concept_check.h>
00033 
00034 namespace lemon {
00035 
00036   
00038 
00041   template<class GR>
00042   struct DfsDefaultTraits
00043   {
00045     typedef GR Graph;
00053     typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
00055  
00059     static PredMap *createPredMap(const GR &G) 
00060     {
00061       return new PredMap(G);
00062     }
00063 
00065  
00069     typedef NullMap<typename Graph::Node,bool> ProcessedMap;
00071  
00075 #ifdef DOXYGEN
00076     static ProcessedMap *createProcessedMap(const GR &g)
00077 #else
00078     static ProcessedMap *createProcessedMap(const GR &)
00079 #endif
00080     {
00081       return new ProcessedMap();
00082     }
00084  
00088     typedef typename Graph::template NodeMap<bool> ReachedMap;
00090  
00094     static ReachedMap *createReachedMap(const GR &G)
00095     {
00096       return new ReachedMap(G);
00097     }
00099  
00103     typedef typename Graph::template NodeMap<int> DistMap;
00105  
00108     static DistMap *createDistMap(const GR &G)
00109     {
00110       return new DistMap(G);
00111     }
00112   };
00113   
00115   
00129 #ifdef DOXYGEN
00130   template <typename GR,
00131             typename TR>
00132 #else
00133   template <typename GR=ListGraph,
00134             typename TR=DfsDefaultTraits<GR> >
00135 #endif
00136   class Dfs {
00137   public:
00144     class UninitializedParameter : public lemon::UninitializedParameter {
00145     public:
00146       virtual const char* exceptionName() const {
00147         return "lemon::Dfs::UninitializedParameter";
00148       }
00149     };
00150 
00151     typedef TR Traits;
00153     typedef typename TR::Graph Graph;
00155     typedef typename Graph::Node Node;
00157     typedef typename Graph::NodeIt NodeIt;
00159     typedef typename Graph::Edge Edge;
00161     typedef typename Graph::OutEdgeIt OutEdgeIt;
00162     
00165     typedef typename TR::PredMap PredMap;
00167     typedef typename TR::ReachedMap ReachedMap;
00169     typedef typename TR::ProcessedMap ProcessedMap;
00171     typedef typename TR::DistMap DistMap;
00172   private:
00174     const Graph *G;
00176     PredMap *_pred;
00178     bool local_pred;
00180     DistMap *_dist;
00182     bool local_dist;
00184     ReachedMap *_reached;
00186     bool local_reached;
00188     ProcessedMap *_processed;
00190     bool local_processed;
00191 
00192     std::vector<typename Graph::OutEdgeIt> _stack;
00193     int _stack_head;
00194 
00196     
00198     void create_maps() 
00199     {
00200       if(!_pred) {
00201         local_pred = true;
00202         _pred = Traits::createPredMap(*G);
00203       }
00204       if(!_dist) {
00205         local_dist = true;
00206         _dist = Traits::createDistMap(*G);
00207       }
00208       if(!_reached) {
00209         local_reached = true;
00210         _reached = Traits::createReachedMap(*G);
00211       }
00212       if(!_processed) {
00213         local_processed = true;
00214         _processed = Traits::createProcessedMap(*G);
00215       }
00216     }
00217 
00218   protected:
00219 
00220     Dfs() {}
00221     
00222   public:
00223 
00224     typedef Dfs Create;
00225 
00227 
00229 
00230     template <class T>
00231     struct DefPredMapTraits : public Traits {
00232       typedef T PredMap;
00233       static PredMap *createPredMap(const Graph &G) 
00234       {
00235         throw UninitializedParameter();
00236       }
00237     };
00239 
00242     template <class T>
00243     struct DefPredMap : public Dfs<Graph, DefPredMapTraits<T> > {
00244       typedef Dfs<Graph, DefPredMapTraits<T> > Create;
00245     };
00246     
00247     
00248     template <class T>
00249     struct DefDistMapTraits : public Traits {
00250       typedef T DistMap;
00251       static DistMap *createDistMap(const Graph &G) 
00252       {
00253         throw UninitializedParameter();
00254       }
00255     };
00257 
00260     template <class T>
00261     struct DefDistMap {
00262       typedef Dfs<Graph, DefDistMapTraits<T> > Create;
00263     };
00264     
00265     template <class T>
00266     struct DefReachedMapTraits : public Traits {
00267       typedef T ReachedMap;
00268       static ReachedMap *createReachedMap(const Graph &G) 
00269       {
00270         throw UninitializedParameter();
00271       }
00272     };
00274 
00277     template <class T>
00278     struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
00279       typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
00280     };
00281 
00282     template <class T>
00283     struct DefProcessedMapTraits : public Traits {
00284       typedef T ProcessedMap;
00285       static ProcessedMap *createProcessedMap(const Graph &G) 
00286       {
00287         throw UninitializedParameter();
00288       }
00289     };
00291 
00294     template <class T>
00295     struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > { 
00296       typedef Dfs< Graph, DefProcessedMapTraits<T> > Create;
00297     };
00298     
00299     struct DefGraphProcessedMapTraits : public Traits {
00300       typedef typename Graph::template NodeMap<bool> ProcessedMap;
00301       static ProcessedMap *createProcessedMap(const Graph &G) 
00302       {
00303         return new ProcessedMap(G);
00304       }
00305     };
00312     template <class T>
00313     class DefProcessedMapToBeDefaultMap :
00314       public Dfs< Graph, DefGraphProcessedMapTraits> { 
00315       typedef Dfs< Graph, DefGraphProcessedMapTraits> Create;
00316     };
00317     
00319 
00320   public:      
00321     
00323     
00326     Dfs(const Graph& _G) :
00327       G(&_G),
00328       _pred(NULL), local_pred(false),
00329       _dist(NULL), local_dist(false),
00330       _reached(NULL), local_reached(false),
00331       _processed(NULL), local_processed(false)
00332     { }
00333     
00335     ~Dfs() 
00336     {
00337       if(local_pred) delete _pred;
00338       if(local_dist) delete _dist;
00339       if(local_reached) delete _reached;
00340       if(local_processed) delete _processed;
00341     }
00342 
00344 
00350     Dfs &predMap(PredMap &m) 
00351     {
00352       if(local_pred) {
00353         delete _pred;
00354         local_pred=false;
00355       }
00356       _pred = &m;
00357       return *this;
00358     }
00359 
00361 
00367     Dfs &distMap(DistMap &m) 
00368     {
00369       if(local_dist) {
00370         delete _dist;
00371         local_dist=false;
00372       }
00373       _dist = &m;
00374       return *this;
00375     }
00376 
00378 
00384     Dfs &reachedMap(ReachedMap &m) 
00385     {
00386       if(local_reached) {
00387         delete _reached;
00388         local_reached=false;
00389       }
00390       _reached = &m;
00391       return *this;
00392     }
00393 
00395 
00401     Dfs &processedMap(ProcessedMap &m) 
00402     {
00403       if(local_processed) {
00404         delete _processed;
00405         local_processed=false;
00406       }
00407       _processed = &m;
00408       return *this;
00409     }
00410 
00411   public:
00421 
00423 
00425 
00428     void init()
00429     {
00430       create_maps();
00431       _stack.resize(countNodes(*G));
00432       _stack_head=-1;
00433       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
00434         _pred->set(u,INVALID);
00435         // _predNode->set(u,INVALID);
00436         _reached->set(u,false);
00437         _processed->set(u,false);
00438       }
00439     }
00440     
00442 
00447     void addSource(Node s)
00448     {
00449       if(!(*_reached)[s])
00450         {
00451           _reached->set(s,true);
00452           _pred->set(s,INVALID);
00453           OutEdgeIt e(*G,s);
00454           if(e!=INVALID) {
00455             _stack[++_stack_head]=e;
00456             _dist->set(s,_stack_head);
00457           }
00458           else {
00459             _processed->set(s,true);
00460             _dist->set(s,0);
00461           }
00462         }
00463     }
00464     
00466 
00472     Edge processNextEdge()
00473     { 
00474       Node m;
00475       Edge e=_stack[_stack_head];
00476       if(!(*_reached)[m=G->target(e)]) {
00477         _pred->set(m,e);
00478         _reached->set(m,true);
00479         ++_stack_head;
00480         _stack[_stack_head] = OutEdgeIt(*G, m);
00481         _dist->set(m,_stack_head);
00482       }
00483       else {
00484         m=G->source(e);
00485         ++_stack[_stack_head];
00486       }
00487       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
00488         _processed->set(m,true);
00489         --_stack_head;
00490         if(_stack_head>=0) {
00491           m=G->source(_stack[_stack_head]);
00492           ++_stack[_stack_head];
00493         }
00494       }
00495       return e;
00496     }
00498 
00503     OutEdgeIt nextEdge()
00504     { 
00505       return _stack_head>=0?_stack[_stack_head]:INVALID;
00506     }
00507 
00513     bool emptyQueue() { return _stack_head<0; }
00515     
00517     int queueSize() { return _stack_head+1; }
00518     
00520 
00533     void start()
00534     {
00535       while ( !emptyQueue() ) processNextEdge();
00536     }
00537     
00539 
00552     void start(Node dest)
00553     {
00554       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
00555         processNextEdge();
00556     }
00557     
00559 
00570     template<class EM>
00571     void start(const EM &em)
00572     {
00573       while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
00574     }
00575 
00577     
00591     void run(Node s) {
00592       init();
00593       addSource(s);
00594       start();
00595     }
00596     
00598     
00610     int run(Node s,Node t) {
00611       init();
00612       addSource(s);
00613       start(t);
00614       return reached(t)?_stack_head+1:0;
00615     }
00616     
00618 
00624     
00626 
00628     
00636     template<class P>
00637     bool getPath(P &p,Node t) 
00638     {
00639       if(reached(t)) {
00640         p.clear();
00641         typename P::Builder b(p);
00642         for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
00643           b.pushFront(predEdge(t));
00644         b.commit();
00645         return true;
00646       }
00647       return false;
00648     }
00649 
00651 
00656     int dist(Node v) const { return (*_dist)[v]; }
00657 
00659 
00669     Edge predEdge(Node v) const { return (*_pred)[v];}
00670 
00672 
00683     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
00684                                   G->source((*_pred)[v]); }
00685     
00687 
00691     const DistMap &distMap() const { return *_dist;}
00692  
00694 
00699     const PredMap &predMap() const { return *_pred;}
00700  
00702 
00708     bool reached(Node v) { return (*_reached)[v]; }
00709     
00711   };
00712 
00714 
00717   template<class GR>
00718   struct DfsWizardDefaultTraits
00719   {
00721     typedef GR Graph;
00729     typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
00731  
00735 #ifdef DOXYGEN
00736     static PredMap *createPredMap(const GR &g) 
00737 #else
00738     static PredMap *createPredMap(const GR &) 
00739 #endif
00740     {
00741       return new PredMap();
00742     }
00743 
00745  
00749     typedef NullMap<typename Graph::Node,bool> ProcessedMap;
00751  
00755 #ifdef DOXYGEN
00756     static ProcessedMap *createProcessedMap(const GR &g)
00757 #else
00758     static ProcessedMap *createProcessedMap(const GR &)
00759 #endif
00760     {
00761       return new ProcessedMap();
00762     }
00764  
00768     typedef typename Graph::template NodeMap<bool> ReachedMap;
00770  
00774     static ReachedMap *createReachedMap(const GR &G)
00775     {
00776       return new ReachedMap(G);
00777     }
00779  
00783     typedef NullMap<typename Graph::Node,int> DistMap;
00785  
00788 #ifdef DOXYGEN
00789     static DistMap *createDistMap(const GR &g)
00790 #else
00791     static DistMap *createDistMap(const GR &)
00792 #endif
00793     {
00794       return new DistMap();
00795     }
00796   };
00797   
00799 
00806   template<class GR>
00807   class DfsWizardBase : public DfsWizardDefaultTraits<GR>
00808   {
00809 
00810     typedef DfsWizardDefaultTraits<GR> Base;
00811   protected:
00813     typedef typename Base::Graph::Node Node;
00814 
00816     void *_g;
00818     void *_reached;
00820     void *_processed;
00822     void *_pred;
00824     void *_dist;
00826     Node _source;
00827     
00828     public:
00830     
00833     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
00834                            _dist(0), _source(INVALID) {}
00835 
00837     
00843     DfsWizardBase(const GR &g, Node s=INVALID) :
00844       _g((void *)&g), _reached(0), _processed(0), _pred(0),
00845       _dist(0), _source(s) {}
00846 
00847   };
00848   
00850 
00868   template<class TR>
00869   class DfsWizard : public TR
00870   {
00871     typedef TR Base;
00872 
00874     typedef typename TR::Graph Graph;
00875     //\e
00876     typedef typename Graph::Node Node;
00877     //\e
00878     typedef typename Graph::NodeIt NodeIt;
00879     //\e
00880     typedef typename Graph::Edge Edge;
00881     //\e
00882     typedef typename Graph::OutEdgeIt OutEdgeIt;
00883     
00886     typedef typename TR::ReachedMap ReachedMap;
00889     typedef typename TR::ProcessedMap ProcessedMap;
00892     typedef typename TR::PredMap PredMap;
00894     typedef typename TR::DistMap DistMap;
00895 
00896 public:
00898     DfsWizard() : TR() {}
00899 
00901 
00904     DfsWizard(const Graph &g, Node s=INVALID) :
00905       TR(g,s) {}
00906 
00908     DfsWizard(const TR &b) : TR(b) {}
00909 
00910     ~DfsWizard() {}
00911 
00913     
00916     void run()
00917     {
00918       if(Base::_source==INVALID) throw UninitializedParameter();
00919       Dfs<Graph,TR> alg(*(Graph*)Base::_g);
00920       if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
00921       if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
00922       if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
00923       if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
00924       alg.run(Base::_source);
00925     }
00926 
00928 
00931     void run(Node s)
00932     {
00933       Base::_source=s;
00934       run();
00935     }
00936 
00937     template<class T>
00938     struct DefPredMapBase : public Base {
00939       typedef T PredMap;
00940       static PredMap *createPredMap(const Graph &) { return 0; };
00941       DefPredMapBase(const TR &b) : TR(b) {}
00942     };
00943     
00950     template<class T>
00951     DfsWizard<DefPredMapBase<T> > predMap(const T &t) 
00952     {
00953       Base::_pred=(void *)&t;
00954       return DfsWizard<DefPredMapBase<T> >(*this);
00955     }
00956     
00957  
00958     template<class T>
00959     struct DefReachedMapBase : public Base {
00960       typedef T ReachedMap;
00961       static ReachedMap *createReachedMap(const Graph &) { return 0; };
00962       DefReachedMapBase(const TR &b) : TR(b) {}
00963     };
00964     
00971     template<class T>
00972     DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
00973     {
00974       Base::_pred=(void *)&t;
00975       return DfsWizard<DefReachedMapBase<T> >(*this);
00976     }
00977     
00978 
00979     template<class T>
00980     struct DefProcessedMapBase : public Base {
00981       typedef T ProcessedMap;
00982       static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
00983       DefProcessedMapBase(const TR &b) : TR(b) {}
00984     };
00985     
00992     template<class T>
00993     DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
00994     {
00995       Base::_pred=(void *)&t;
00996       return DfsWizard<DefProcessedMapBase<T> >(*this);
00997     }
00998     
00999     template<class T>
01000     struct DefDistMapBase : public Base {
01001       typedef T DistMap;
01002       static DistMap *createDistMap(const Graph &) { return 0; };
01003       DefDistMapBase(const TR &b) : TR(b) {}
01004     };
01005     
01012     template<class T>
01013     DfsWizard<DefDistMapBase<T> > distMap(const T &t) 
01014     {
01015       Base::_dist=(void *)&t;
01016       return DfsWizard<DefDistMapBase<T> >(*this);
01017     }
01018     
01020 
01023     DfsWizard<TR> &source(Node s) 
01024     {
01025       Base::_source=s;
01026       return *this;
01027     }
01028     
01029   };
01030   
01032 
01048   template<class GR>
01049   DfsWizard<DfsWizardBase<GR> >
01050   dfs(const GR &g,typename GR::Node s=INVALID)
01051   {
01052     return DfsWizard<DfsWizardBase<GR> >(g,s);
01053   }
01054 
01055 #ifdef DOXYGEN
01060   template <typename _Graph>
01061   struct DfsVisitor {
01062     typedef _Graph Graph;
01063     typedef typename Graph::Edge Edge;
01064     typedef typename Graph::Node Node;
01069     void discover(const Edge& edge) {}
01073     void reach(const Node& node) {}
01077     void backtrack(const Edge& edge) {}
01081     void leave(const Node& node) {}
01087     void examine(const Edge& edge) {}
01091     void start(const Node& node) {}
01095     void stop(const Node& node) {}
01096 
01097   };
01098 #else
01099   template <typename _Graph>
01100   struct DfsVisitor {
01101     typedef _Graph Graph;
01102     typedef typename Graph::Edge Edge;
01103     typedef typename Graph::Node Node;
01104     void discover(const Edge&) {}
01105     void reach(const Node&) {}
01106     void backtrack(const Edge&) {}
01107     void leave(const Node&) {}
01108     void examine(const Edge&) {}
01109     void start(const Node&) {}
01110     void stop(const Node&) {}
01111 
01112     template <typename _Visitor>
01113     struct Constraints {
01114       void constraints() {
01115         Edge edge;
01116         Node node;
01117         visitor.discover(edge);
01118         visitor.reach(node);
01119         visitor.backtrack(edge);
01120         visitor.leave(node);
01121         visitor.examine(edge);
01122         visitor.start(node);
01123         visitor.stop(edge);
01124       }
01125       _Visitor& visitor;
01126     };
01127   };
01128 #endif
01129 
01134   template<class _Graph>
01135   struct DfsVisitDefaultTraits {
01136 
01138     typedef _Graph Graph;
01139 
01145     typedef typename Graph::template NodeMap<bool> ReachedMap;
01146 
01152     static ReachedMap *createReachedMap(const Graph &graph) {
01153       return new ReachedMap(graph);
01154     }
01155 
01156   };
01157   
01159   
01182 #ifdef DOXYGEN
01183   template <typename _Graph, typename _Visitor, typename _Traits>
01184 #else
01185   template <typename _Graph = ListGraph,
01186             typename _Visitor = DfsVisitor<_Graph>,
01187             typename _Traits = DfsDefaultTraits<_Graph> >
01188 #endif
01189   class DfsVisit {
01190   public:
01191     
01196     class UninitializedParameter : public lemon::UninitializedParameter {
01197     public:
01198       virtual const char* exceptionName() const {
01199         return "lemon::DfsVisit::UninitializedParameter";
01200       }
01201     };
01202 
01203     typedef _Traits Traits;
01204 
01205     typedef typename Traits::Graph Graph;
01206 
01207     typedef _Visitor Visitor;
01208 
01210     typedef typename Traits::ReachedMap ReachedMap;
01211 
01212   private:
01213 
01214     typedef typename Graph::Node Node;
01215     typedef typename Graph::NodeIt NodeIt;
01216     typedef typename Graph::Edge Edge;
01217     typedef typename Graph::OutEdgeIt OutEdgeIt;
01218 
01220     const Graph *_graph;
01222     Visitor *_visitor;
01224     ReachedMap *_reached;
01226     bool local_reached;
01227 
01228     std::vector<typename Graph::Edge> _stack;
01229     int _stack_head;
01230 
01234     void create_maps() {
01235       if(!_reached) {
01236         local_reached = true;
01237         _reached = Traits::createReachedMap(*_graph);
01238       }
01239     }
01240 
01241   protected:
01242 
01243     DfsVisit() {}
01244     
01245   public:
01246 
01247     typedef DfsVisit Create;
01248 
01250 
01252     template <class T>
01253     struct DefReachedMapTraits : public Traits {
01254       typedef T ReachedMap;
01255       static ReachedMap *createReachedMap(const Graph &graph) {
01256         throw UninitializedParameter();
01257       }
01258     };
01263     template <class T>
01264     struct DefReachedMap : public DfsVisit< Graph, Visitor,
01265                                             DefReachedMapTraits<T> > {
01266       typedef DfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
01267     };
01269 
01270   public:      
01271     
01279     DfsVisit(const Graph& graph, Visitor& visitor) 
01280       : _graph(&graph), _visitor(&visitor),
01281         _reached(0), local_reached(false) {}
01282     
01286     ~DfsVisit() {
01287       if(local_reached) delete _reached;
01288     }
01289 
01297     DfsVisit &reachedMap(ReachedMap &m) {
01298       if(local_reached) {
01299         delete _reached;
01300         local_reached=false;
01301       }
01302       _reached = &m;
01303       return *this;
01304     }
01305 
01306   public:
01316 
01322     void init() {
01323       create_maps();
01324       _stack.resize(countNodes(*_graph));
01325       _stack_head = -1;
01326       for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
01327         _reached->set(u, false);
01328       }
01329     }
01330     
01334     void addSource(Node s) {
01335       if(!(*_reached)[s]) {
01336           _reached->set(s,true);
01337           _visitor->start(s);
01338           _visitor->reach(s);
01339           Edge e; 
01340           _graph->firstOut(e, s);
01341           if (e != INVALID) {
01342             _stack[++_stack_head] = e;
01343           } else {
01344             _visitor->leave(s);
01345           }
01346         }
01347     }
01348     
01356     Edge processNextEdge() { 
01357       Edge e = _stack[_stack_head];
01358       Node m = _graph->target(e);
01359       if(!(*_reached)[m]) {
01360         _visitor->discover(e);
01361         _visitor->reach(m);
01362         _reached->set(m, true);
01363         _graph->firstOut(_stack[++_stack_head], m);
01364       } else {
01365         _visitor->examine(e);
01366         m = _graph->source(e);
01367         _graph->nextOut(_stack[_stack_head]);
01368       }
01369       while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
01370         _visitor->leave(m);
01371         --_stack_head;
01372         if (_stack_head >= 0) {
01373           _visitor->backtrack(_stack[_stack_head]);
01374           m = _graph->source(_stack[_stack_head]);
01375           _graph->nextOut(_stack[_stack_head]);
01376         } else {
01377           _visitor->stop(m);      
01378         }
01379       }
01380       return e;
01381     }
01382 
01389     Edge nextEdge() { 
01390       return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
01391     }
01392 
01398     bool emptyQueue() { return _stack_head < 0; }
01399 
01403     int queueSize() { return _stack_head + 1; }
01404     
01411     void start() {
01412       while ( !emptyQueue() ) processNextEdge();
01413     }
01414     
01421     void start(Node dest) {
01422       while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest) 
01423         processNextEdge();
01424     }
01425     
01438     template <typename EM>
01439     void start(const EM &em) {
01440       while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
01441     }
01442 
01452     void run(Node s) {
01453       init();
01454       addSource(s);
01455       start();
01456     }
01458 
01472     bool reached(Node v) { return (*_reached)[v]; }
01474   };
01475 
01476 
01477 } //END OF NAMESPACE LEMON
01478 
01479 #endif
01480 

Generated on Fri Feb 3 18:36:23 2006 for LEMON by  doxygen 1.4.6