COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 209:765619b7cbb2 in lemon-1.0 for lemon/dfs.h


Ignore:
Timestamp:
07/13/08 20:51:02 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/dfs.h

    r158 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    3535namespace lemon {
    3636
    37  
     37
    3838  ///Default traits class of Dfs class.
    3939
    … …  
    4343  struct DfsDefaultTraits
    4444  {
    45     ///The digraph type the algorithm runs on. 
     45    ///The digraph type the algorithm runs on.
    4646    typedef GR Digraph;
    4747    ///\brief The type of the map that stores the last
    4848    ///arcs of the %DFS paths.
    49     /// 
     49    ///
    5050    ///The type of the map that stores the last
    5151    ///arcs of the %DFS paths.
    … …  
    5454    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    5555    ///Instantiates a PredMap.
    56  
    57     ///This function instantiates a \ref PredMap. 
     56
     57    ///This function instantiates a \ref PredMap.
    5858    ///\param G is the digraph, to which we would like to define the PredMap.
    5959    ///\todo The digraph alone may be insufficient to initialize
    60     static PredMap *createPredMap(const GR &G) 
     60    static PredMap *createPredMap(const GR &G)
    6161    {
    6262      return new PredMap(G);
    … …  
    6464
    6565    ///The type of the map that indicates which nodes are processed.
    66  
     66
    6767    ///The type of the map that indicates which nodes are processed.
    6868    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    7070    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    7171    ///Instantiates a ProcessedMap.
    72  
    73     ///This function instantiates a \ref ProcessedMap. 
     72
     73    ///This function instantiates a \ref ProcessedMap.
    7474    ///\param g is the digraph, to which
    7575    ///we would like to define the \ref ProcessedMap
    … …  
    8383    }
    8484    ///The type of the map that indicates which nodes are reached.
    85  
     85
    8686    ///The type of the map that indicates which nodes are reached.
    8787    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    8989    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    9090    ///Instantiates a ReachedMap.
    91  
    92     ///This function instantiates a \ref ReachedMap. 
     91
     92    ///This function instantiates a \ref ReachedMap.
    9393    ///\param G is the digraph, to which
    9494    ///we would like to define the \ref ReachedMap.
    … …  
    9898    }
    9999    ///The type of the map that stores the dists of the nodes.
    100  
     100
    101101    ///The type of the map that stores the dists of the nodes.
    102102    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    104104    typedef typename Digraph::template NodeMap<int> DistMap;
    105105    ///Instantiates a DistMap.
    106  
    107     ///This function instantiates a \ref DistMap. 
     106
     107    ///This function instantiates a \ref DistMap.
    108108    ///\param G is the digraph, to which we would like to define the \ref DistMap
    109109    static DistMap *createDistMap(const GR &G)
    … …  
    112112    }
    113113  };
    114  
     114
    115115  ///%DFS algorithm class.
    116  
     116
    117117  ///\ingroup search
    118118  ///This class provides an efficient implementation of the %DFS algorithm.
    … …  
    128128#ifdef DOXYGEN
    129129  template <typename GR,
    130             typename TR>
     130            typename TR>
    131131#else
    132132  template <typename GR=ListDigraph,
    133             typename TR=DfsDefaultTraits<GR> >
     133            typename TR=DfsDefaultTraits<GR> >
    134134#endif
    135135  class Dfs {
    … …  
    144144    public:
    145145      virtual const char* what() const throw() {
    146         return "lemon::Dfs::UninitializedParameter";
     146        return "lemon::Dfs::UninitializedParameter";
    147147      }
    148148    };
    … …  
    159159    ///\e
    160160    typedef typename Digraph::OutArcIt OutArcIt;
    161    
     161
    162162    ///\brief The type of the map that stores the last
    163163    ///arcs of the %DFS paths.
    … …  
    193193
    194194    ///Creates the maps if necessary.
    195    
     195
    196196    ///\todo Better memory allocation (instead of new).
    197     void create_maps() 
     197    void create_maps()
    198198    {
    199199      if(!_pred) {
    200         local_pred = true;
    201         _pred = Traits::createPredMap(*G);
     200        local_pred = true;
     201        _pred = Traits::createPredMap(*G);
    202202      }
    203203      if(!_dist) {
    204         local_dist = true;
    205         _dist = Traits::createDistMap(*G);
     204        local_dist = true;
     205        _dist = Traits::createDistMap(*G);
    206206      }
    207207      if(!_reached) {
    208         local_reached = true;
    209         _reached = Traits::createReachedMap(*G);
     208        local_reached = true;
     209        _reached = Traits::createReachedMap(*G);
    210210      }
    211211      if(!_processed) {
    212         local_processed = true;
    213         _processed = Traits::createProcessedMap(*G);
     212        local_processed = true;
     213        _processed = Traits::createProcessedMap(*G);
    214214      }
    215215    }
    … …  
    218218
    219219    Dfs() {}
    220    
     220
    221221  public:
    222222
    … …  
    230230    struct DefPredMapTraits : public Traits {
    231231      typedef T PredMap;
    232       static PredMap *createPredMap(const Digraph &G) 
     232      static PredMap *createPredMap(const Digraph &G)
    233233      {
    234         throw UninitializedParameter();
     234        throw UninitializedParameter();
    235235      }
    236236    };
    … …  
    244244      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
    245245    };
    246    
    247    
     246
     247
    248248    template <class T>
    249249    struct DefDistMapTraits : public Traits {
    250250      typedef T DistMap;
    251       static DistMap *createDistMap(const Digraph &) 
     251      static DistMap *createDistMap(const Digraph &)
    252252      {
    253         throw UninitializedParameter();
     253        throw UninitializedParameter();
    254254      }
    255255    };
    … …  
    263263      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
    264264    };
    265    
     265
    266266    template <class T>
    267267    struct DefReachedMapTraits : public Traits {
    268268      typedef T ReachedMap;
    269       static ReachedMap *createReachedMap(const Digraph &) 
     269      static ReachedMap *createReachedMap(const Digraph &)
    270270      {
    271         throw UninitializedParameter();
     271        throw UninitializedParameter();
    272272      }
    273273    };
    … …  
    285285    struct DefProcessedMapTraits : public Traits {
    286286      typedef T ProcessedMap;
    287       static ProcessedMap *createProcessedMap(const Digraph &) 
     287      static ProcessedMap *createProcessedMap(const Digraph &)
    288288      {
    289         throw UninitializedParameter();
     289        throw UninitializedParameter();
    290290      }
    291291    };
    … …  
    296296    ///
    297297    template <class T>
    298     struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { 
     298    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
    299299      typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
    300300    };
    301    
     301
    302302    struct DefDigraphProcessedMapTraits : public Traits {
    303303      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    304       static ProcessedMap *createProcessedMap(const Digraph &G) 
     304      static ProcessedMap *createProcessedMap(const Digraph &G)
    305305      {
    306         return new ProcessedMap(G);
     306        return new ProcessedMap(G);
    307307      }
    308308    };
    … …  
    315315    template <class T>
    316316    class DefProcessedMapToBeDefaultMap :
    317       public Dfs< Digraph, DefDigraphProcessedMapTraits> { 
     317      public Dfs< Digraph, DefDigraphProcessedMapTraits> {
    318318      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
    319319    };
    320    
     320
    321321    ///@}
    322322
    323   public:     
    324    
     323  public:
     324
    325325    ///Constructor.
    326    
     326
    327327    ///\param _G the digraph the algorithm will run on.
    328328    ///
    … …  
    334334      _processed(NULL), local_processed(false)
    335335    { }
    336    
     336
    337337    ///Destructor.
    338     ~Dfs() 
     338    ~Dfs()
    339339    {
    340340      if(local_pred) delete _pred;
    … …  
    351351    ///automatically allocated map, of course.
    352352    ///\return <tt> (*this) </tt>
    353     Dfs &predMap(PredMap &m) 
     353    Dfs &predMap(PredMap &m)
    354354    {
    355355      if(local_pred) {
    356         delete _pred;
    357         local_pred=false;
     356        delete _pred;
     357        local_pred=false;
    358358      }
    359359      _pred = &m;
    … …  
    368368    ///automatically allocated map, of course.
    369369    ///\return <tt> (*this) </tt>
    370     Dfs &distMap(DistMap &m) 
     370    Dfs &distMap(DistMap &m)
    371371    {
    372372      if(local_dist) {
    373         delete _dist;
    374         local_dist=false;
     373        delete _dist;
     374        local_dist=false;
    375375      }
    376376      _dist = &m;
    … …  
    385385    ///automatically allocated map, of course.
    386386    ///\return <tt> (*this) </tt>
    387     Dfs &reachedMap(ReachedMap &m) 
     387    Dfs &reachedMap(ReachedMap &m)
    388388    {
    389389      if(local_reached) {
    390         delete _reached;
    391         local_reached=false;
     390        delete _reached;
     391        local_reached=false;
    392392      }
    393393      _reached = &m;
    … …  
    402402    ///automatically allocated map, of course.
    403403    ///\return <tt> (*this) </tt>
    404     Dfs &processedMap(ProcessedMap &m) 
     404    Dfs &processedMap(ProcessedMap &m)
    405405    {
    406406      if(local_processed) {
    407         delete _processed;
    408         local_processed=false;
     407        delete _processed;
     408        local_processed=false;
    409409      }
    410410      _processed = &m;
    … …  
    435435      _stack_head=-1;
    436436      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    437         _pred->set(u,INVALID);
    438         // _predNode->set(u,INVALID);
    439         _reached->set(u,false);
    440         _processed->set(u,false);
    441       }
    442     }
    443    
     437        _pred->set(u,INVALID);
     438        // _predNode->set(u,INVALID);
     439        _reached->set(u,false);
     440        _processed->set(u,false);
     441      }
     442    }
     443
    444444    ///Adds a new source node.
    445445
    … …  
    451451    {
    452452      if(!(*_reached)[s])
    453         {
    454           _reached->set(s,true);
    455           _pred->set(s,INVALID);
    456           OutArcIt e(*G,s);
    457           if(e!=INVALID) {
    458             _stack[++_stack_head]=e;
    459             _dist->set(s,_stack_head);
    460           }
    461           else {
    462             _processed->set(s,true);
    463             _dist->set(s,0);
    464           }
    465         }
    466     }
    467    
     453        {
     454          _reached->set(s,true);
     455          _pred->set(s,INVALID);
     456          OutArcIt e(*G,s);
     457          if(e!=INVALID) {
     458            _stack[++_stack_head]=e;
     459            _dist->set(s,_stack_head);
     460          }
     461          else {
     462            _processed->set(s,true);
     463            _dist->set(s,0);
     464          }
     465        }
     466    }
     467
    468468    ///Processes the next arc.
    469469
    … …  
    474474    ///\pre The stack must not be empty!
    475475    Arc processNextArc()
    476     { 
     476    {
    477477      Node m;
    478478      Arc e=_stack[_stack_head];
    479479      if(!(*_reached)[m=G->target(e)]) {
    480         _pred->set(m,e);
    481         _reached->set(m,true);
    482         ++_stack_head;
    483         _stack[_stack_head] = OutArcIt(*G, m);
    484         _dist->set(m,_stack_head);
     480        _pred->set(m,e);
     481        _reached->set(m,true);
     482        ++_stack_head;
     483        _stack[_stack_head] = OutArcIt(*G, m);
     484        _dist->set(m,_stack_head);
    485485      }
    486486      else {
    487         m=G->source(e);
    488         ++_stack[_stack_head];
     487        m=G->source(e);
     488        ++_stack[_stack_head];
    489489      }
    490490      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
    491         _processed->set(m,true);
    492         --_stack_head;
    493         if(_stack_head>=0) {
    494           m=G->source(_stack[_stack_head]);
    495           ++_stack[_stack_head];
    496         }
     491        _processed->set(m,true);
     492        --_stack_head;
     493        if(_stack_head>=0) {
     494          m=G->source(_stack[_stack_head]);
     495          ++_stack[_stack_head];
     496        }
    497497      }
    498498      return e;
    … …  
    505505    /// empty.
    506506    OutArcIt nextArc()
    507     { 
     507    {
    508508      return _stack_head>=0?_stack[_stack_head]:INVALID;
    509509    }
    … …  
    516516    bool emptyQueue() { return _stack_head<0; }
    517517    ///Returns the number of the nodes to be processed.
    518    
     518
    519519    ///Returns the number of the nodes to be processed in the queue.
    520520    int queueSize() { return _stack_head+1; }
    521    
     521
    522522    ///Executes the algorithm.
    523523
    … …  
    538538      while ( !emptyQueue() ) processNextArc();
    539539    }
    540    
     540
    541541    ///Executes the algorithm until \c dest is reached.
    542542
    … …  
    555555    void start(Node dest)
    556556    {
    557       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
    558         processNextArc();
    559     }
    560    
     557      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
     558        processNextArc();
     559    }
     560
    561561    ///Executes the algorithm until a condition is met.
    562562
    … …  
    583583
    584584    ///Runs %DFS algorithm to visit all nodes in the digraph.
    585    
     585
    586586    ///This method runs the %DFS algorithm in order to
    587587    ///compute the
    … …  
    611611
    612612    ///Runs %DFS algorithm from node \c s.
    613    
     613
    614614    ///This method runs the %DFS algorithm from a root node \c s
    615615    ///in order to
    … …  
    630630      start();
    631631    }
    632    
     632
    633633    ///Finds the %DFS path between \c s and \c t.
    634    
     634
    635635    ///Finds the %DFS path between \c s and \c t.
    636636    ///
    … …  
    650650      return reached(t)?_stack_head+1:0;
    651651    }
    652    
     652
    653653    ///@}
    654654
    … …  
    658658    ///Before the use of these functions,
    659659    ///either run() or start() must be called.
    660    
     660
    661661    ///@{
    662662
    … …  
    664664
    665665    ///Gives back the shortest path.
    666    
     666
    667667    ///Gives back the shortest path.
    668668    ///\pre The \c t should be reachable from the source.
    669     Path path(Node t) 
     669    Path path(Node t)
    670670    {
    671671      return Path(*G, *_pred, t);
    … …  
    676676    ///Returns the distance of a node from the root(s).
    677677    ///\pre \ref run() must be called before using this function.
    678     ///\warning If node \c v is unreachable from the root(s) then the return 
     678    ///\warning If node \c v is unreachable from the root(s) then the return
    679679    ///value of this funcion is undefined.
    680680    int dist(Node v) const { return (*_dist)[v]; }
    … …  
    706706    ///using this function.
    707707    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    708                                   G->source((*_pred)[v]); }
    709    
     708                                  G->source((*_pred)[v]); }
     709
    710710    ///Returns a reference to the NodeMap of distances.
    711711
    … …  
    714714    ///be called before using this function.
    715715    const DistMap &distMap() const { return *_dist;}
    716  
     716
    717717    ///Returns a reference to the %DFS arc-tree map.
    718718
    … …  
    722722    ///must be called before using this function.
    723723    const PredMap &predMap() const { return *_pred;}
    724  
     724
    725725    ///Checks if a node is reachable from the root.
    726726
    … …  
    731731    ///
    732732    bool reached(Node v) { return (*_reached)[v]; }
    733    
     733
    734734    ///@}
    735735  };
    … …  
    742742  struct DfsWizardDefaultTraits
    743743  {
    744     ///The digraph type the algorithm runs on. 
     744    ///The digraph type the algorithm runs on.
    745745    typedef GR Digraph;
    746746    ///\brief The type of the map that stores the last
    747747    ///arcs of the %DFS paths.
    748     /// 
     748    ///
    749749    ///The type of the map that stores the last
    750750    ///arcs of the %DFS paths.
    … …  
    753753    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
    754754    ///Instantiates a PredMap.
    755  
    756     ///This function instantiates a \ref PredMap. 
     755
     756    ///This function instantiates a \ref PredMap.
    757757    ///\param g is the digraph, to which we would like to define the PredMap.
    758758    ///\todo The digraph alone may be insufficient to initialize
    759759#ifdef DOXYGEN
    760     static PredMap *createPredMap(const GR &g) 
     760    static PredMap *createPredMap(const GR &g)
    761761#else
    762     static PredMap *createPredMap(const GR &) 
     762    static PredMap *createPredMap(const GR &)
    763763#endif
    764764    {
    … …  
    767767
    768768    ///The type of the map that indicates which nodes are processed.
    769  
     769
    770770    ///The type of the map that indicates which nodes are processed.
    771771    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    773773    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    774774    ///Instantiates a ProcessedMap.
    775  
    776     ///This function instantiates a \ref ProcessedMap. 
     775
     776    ///This function instantiates a \ref ProcessedMap.
    777777    ///\param g is the digraph, to which
    778778    ///we would like to define the \ref ProcessedMap
    … …  
    786786    }
    787787    ///The type of the map that indicates which nodes are reached.
    788  
     788
    789789    ///The type of the map that indicates which nodes are reached.
    790790    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    792792    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    793793    ///Instantiates a ReachedMap.
    794  
    795     ///This function instantiates a \ref ReachedMap. 
     794
     795    ///This function instantiates a \ref ReachedMap.
    796796    ///\param G is the digraph, to which
    797797    ///we would like to define the \ref ReachedMap.
    … …  
    801801    }
    802802    ///The type of the map that stores the dists of the nodes.
    803  
     803
    804804    ///The type of the map that stores the dists of the nodes.
    805805    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    807807    typedef NullMap<typename Digraph::Node,int> DistMap;
    808808    ///Instantiates a DistMap.
    809  
    810     ///This function instantiates a \ref DistMap. 
     809
     810    ///This function instantiates a \ref DistMap.
    811811    ///\param g is the digraph, to which we would like to define the \ref DistMap
    812812#ifdef DOXYGEN
    … …  
    819819    }
    820820  };
    821  
     821
    822822  /// Default traits used by \ref DfsWizard
    823823
    … …  
    849849    ///Pointer to the source node.
    850850    Node _source;
    851    
     851
    852852    public:
    853853    /// Constructor.
    854    
     854
    855855    /// This constructor does not require parameters, therefore it initiates
    856856    /// all of the attributes to default values (0, INVALID).
    857857    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    858                            _dist(0), _source(INVALID) {}
     858                           _dist(0), _source(INVALID) {}
    859859
    860860    /// Constructor.
    861    
     861
    862862    /// This constructor requires some parameters,
    863863    /// listed in the parameters list.
    … …  
    866866    /// \param s is the initial value of  \ref _source
    867867    DfsWizardBase(const GR &g, Node s=INVALID) :
    868       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 
     868      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    869869      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
    870870
    871871  };
    872  
     872
    873873  /// A class to make the usage of the Dfs algorithm easier
    874874
    … …  
    905905    //\e
    906906    typedef typename Digraph::OutArcIt OutArcIt;
    907    
     907
    908908    ///\brief The type of the map that stores
    909909    ///the reached nodes
    … …  
    935935
    936936    ///Runs Dfs algorithm from a given node.
    937    
     937
    938938    ///Runs Dfs algorithm from a given node.
    939939    ///The node can be given by the \ref source function.
    … …  
    942942      if(Base::_source==INVALID) throw UninitializedParameter();
    943943      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    944       if(Base::_reached) 
     944      if(Base::_reached)
    945945        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    946       if(Base::_processed) 
     946      if(Base::_processed)
    947947        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    948       if(Base::_pred) 
     948      if(Base::_pred)
    949949        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    950       if(Base::_dist) 
     950      if(Base::_dist)
    951951        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    952952      alg.run(Base::_source);
    … …  
    969969      DefPredMapBase(const TR &b) : TR(b) {}
    970970    };
    971    
     971
    972972    ///\brief \ref named-templ-param "Named parameter"
    973973    ///function for setting PredMap type
    … …  
    977977    ///
    978978    template<class T>
    979     DfsWizard<DefPredMapBase<T> > predMap(const T &t) 
     979    DfsWizard<DefPredMapBase<T> > predMap(const T &t)
    980980    {
    981981      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    982982      return DfsWizard<DefPredMapBase<T> >(*this);
    983983    }
    984    
    985  
     984
     985
    986986    template<class T>
    987987    struct DefReachedMapBase : public Base {
    … …  
    990990      DefReachedMapBase(const TR &b) : TR(b) {}
    991991    };
    992    
     992
    993993    ///\brief \ref named-templ-param "Named parameter"
    994994    ///function for setting ReachedMap
    … …  
    998998    ///
    999999    template<class T>
    1000     DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
     1000    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
    10011001    {
    10021002      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    10031003      return DfsWizard<DefReachedMapBase<T> >(*this);
    10041004    }
    1005    
     1005
    10061006
    10071007    template<class T>
    … …  
    10111011      DefProcessedMapBase(const TR &b) : TR(b) {}
    10121012    };
    1013    
     1013
    10141014    ///\brief \ref named-templ-param "Named parameter"
    10151015    ///function for setting ProcessedMap
    … …  
    10191019    ///
    10201020    template<class T>
    1021     DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
     1021    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
    10221022    {
    10231023      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
    10241024      return DfsWizard<DefProcessedMapBase<T> >(*this);
    10251025    }
    1026    
     1026
    10271027    template<class T>
    10281028    struct DefDistMapBase : public Base {
    … …  
    10311031      DefDistMapBase(const TR &b) : TR(b) {}
    10321032    };
    1033    
     1033
    10341034    ///\brief \ref named-templ-param "Named parameter"
    10351035    ///function for setting DistMap type
    … …  
    10391039    ///
    10401040    template<class T>
    1041     DfsWizard<DefDistMapBase<T> > distMap(const T &t) 
     1041    DfsWizard<DefDistMapBase<T> > distMap(const T &t)
    10421042    {
    10431043      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    10441044      return DfsWizard<DefDistMapBase<T> >(*this);
    10451045    }
    1046    
     1046
    10471047    /// Sets the source node, from which the Dfs algorithm runs.
    10481048
    10491049    /// Sets the source node, from which the Dfs algorithm runs.
    10501050    /// \param s is the source node.
    1051     DfsWizard<TR> &source(Node s) 
     1051    DfsWizard<TR> &source(Node s)
    10521052    {
    10531053      Base::_source=s;
    10541054      return *this;
    10551055    }
    1056    
     1056
    10571057  };
    1058  
     1058
    10591059  ///Function type interface for Dfs algorithm.
    10601060
    … …  
    10831083#ifdef DOXYGEN
    10841084  /// \brief Visitor class for dfs.
    1085   /// 
    1086   /// It gives a simple interface for a functional interface for dfs 
    1087   /// traversal. The traversal on a linear data structure. 
     1085  ///
     1086  /// It gives a simple interface for a functional interface for dfs
     1087  /// traversal. The traversal on a linear data structure.
    10881088  template <typename _Digraph>
    10891089  struct DfsVisitor {
    … …  
    10921092    typedef typename Digraph::Node Node;
    10931093    /// \brief Called when the arc reach a node.
    1094     /// 
     1094    ///
    10951095    /// It is called when the dfs find an arc which target is not
    10961096    /// reached yet.
    10971097    void discover(const Arc& arc) {}
    10981098    /// \brief Called when the node reached first time.
    1099     /// 
     1099    ///
    11001100    /// It is Called when the node reached first time.
    11011101    void reach(const Node& node) {}
    11021102    /// \brief Called when we step back on an arc.
    1103     /// 
     1103    ///
    11041104    /// It is called when the dfs should step back on the arc.
    11051105    void backtrack(const Arc& arc) {}
    11061106    /// \brief Called when we step back from the node.
    1107     /// 
     1107    ///
    11081108    /// It is called when we step back from the node.
    11091109    void leave(const Node& node) {}
    1110     /// \brief Called when the arc examined but target of the arc 
     1110    /// \brief Called when the arc examined but target of the arc
    11111111    /// already discovered.
    1112     /// 
    1113     /// It called when the arc examined but the target of the arc 
     1112    ///
     1113    /// It called when the arc examined but the target of the arc
    11141114    /// already discovered.
    11151115    void examine(const Arc& arc) {}
    11161116    /// \brief Called for the source node of the dfs.
    1117     /// 
     1117    ///
    11181118    /// It is called for the source node of the dfs.
    11191119    void start(const Node& node) {}
    11201120    /// \brief Called when we leave the source node of the dfs.
    1121     /// 
     1121    ///
    11221122    /// It is called when we leave the source node of the dfs.
    11231123    void stop(const Node& node) {}
    … …  
    11411141    struct Constraints {
    11421142      void constraints() {
    1143         Arc arc;
    1144         Node node;
    1145         visitor.discover(arc);
    1146         visitor.reach(node);
    1147         visitor.backtrack(arc);
    1148         visitor.leave(node);
    1149         visitor.examine(arc);
    1150         visitor.start(node);
    1151         visitor.stop(arc);
     1143        Arc arc;
     1144        Node node;
     1145        visitor.discover(arc);
     1146        visitor.reach(node);
     1147        visitor.backtrack(arc);
     1148        visitor.leave(node);
     1149        visitor.examine(arc);
     1150        visitor.start(node);
     1151        visitor.stop(arc);
    11521152      }
    11531153      _Visitor& visitor;
    … …  
    11631163  struct DfsVisitDefaultTraits {
    11641164
    1165     /// \brief The digraph type the algorithm runs on. 
     1165    /// \brief The digraph type the algorithm runs on.
    11661166    typedef _Digraph Digraph;
    11671167
    11681168    /// \brief The type of the map that indicates which nodes are reached.
    1169     /// 
     1169    ///
    11701170    /// The type of the map that indicates which nodes are reached.
    11711171    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    11751175    /// \brief Instantiates a ReachedMap.
    11761176    ///
    1177     /// This function instantiates a \ref ReachedMap. 
     1177    /// This function instantiates a \ref ReachedMap.
    11781178    /// \param digraph is the digraph, to which
    11791179    /// we would like to define the \ref ReachedMap.
    … …  
    11831183
    11841184  };
    1185  
     1185
    11861186  /// %DFS Visit algorithm class.
    1187  
     1187
    11881188  /// \ingroup search
    11891189  /// This class provides an efficient implementation of the %DFS algorithm
    … …  
    11921192  /// The %DfsVisit class provides an alternative interface to the Dfs
    11931193  /// class. It works with callback mechanism, the DfsVisit object calls
    1194   /// on every dfs event the \c Visitor class member functions. 
     1194  /// on every dfs event the \c Visitor class member functions.
    11951195  ///
    11961196  /// \tparam _Digraph The digraph type the algorithm runs on. The default value is
    11971197  /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
    11981198  /// is only passed to \ref DfsDefaultTraits.
    1199   /// \tparam _Visitor The Visitor object for the algorithm. The 
     1199  /// \tparam _Visitor The Visitor object for the algorithm. The
    12001200  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
    12011201  /// does not observe the Dfs events. If you want to observe the dfs
    12021202  /// events you should implement your own Visitor class.
    1203   /// \tparam _Traits Traits class to set various data types used by the 
     1203  /// \tparam _Traits Traits class to set various data types used by the
    12041204  /// algorithm. The default traits class is
    12051205  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
    … …  
    12121212#else
    12131213  template <typename _Digraph = ListDigraph,
    1214             typename _Visitor = DfsVisitor<_Digraph>,
    1215             typename _Traits = DfsDefaultTraits<_Digraph> >
     1214            typename _Visitor = DfsVisitor<_Digraph>,
     1215            typename _Traits = DfsDefaultTraits<_Digraph> >
    12161216#endif
    12171217  class DfsVisit {
    12181218  public:
    1219    
     1219
    12201220    /// \brief \ref Exception for uninitialized parameters.
    12211221    ///
    … …  
    12241224    class UninitializedParameter : public lemon::UninitializedParameter {
    12251225    public:
    1226       virtual const char* what() const throw() 
     1226      virtual const char* what() const throw()
    12271227      {
    1228         return "lemon::DfsVisit::UninitializedParameter";
     1228        return "lemon::DfsVisit::UninitializedParameter";
    12291229      }
    12301230    };
    … …  
    12631263    void create_maps() {
    12641264      if(!_reached) {
    1265         local_reached = true;
    1266         _reached = Traits::createReachedMap(*_digraph);
     1265        local_reached = true;
     1266        _reached = Traits::createReachedMap(*_digraph);
    12671267      }
    12681268    }
    … …  
    12711271
    12721272    DfsVisit() {}
    1273    
     1273
    12741274  public:
    12751275
    … …  
    12831283      typedef T ReachedMap;
    12841284      static ReachedMap *createReachedMap(const Digraph &digraph) {
    1285         throw UninitializedParameter();
    1286       }
    1287     };
    1288     /// \brief \ref named-templ-param "Named parameter" for setting 
     1285        throw UninitializedParameter();
     1286      }
     1287    };
     1288    /// \brief \ref named-templ-param "Named parameter" for setting
    12891289    /// ReachedMap type
    12901290    ///
    … …  
    12921292    template <class T>
    12931293    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
    1294                                             DefReachedMapTraits<T> > {
     1294                                            DefReachedMapTraits<T> > {
    12951295      typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
    12961296    };
    12971297    ///@}
    12981298
    1299   public:     
    1300    
     1299  public:
     1300
    13011301    /// \brief Constructor.
    13021302    ///
    … …  
    13061306    /// \param visitor The visitor of the algorithm.
    13071307    ///
    1308     DfsVisit(const Digraph& digraph, Visitor& visitor) 
     1308    DfsVisit(const Digraph& digraph, Visitor& visitor)
    13091309      : _digraph(&digraph), _visitor(&visitor),
    1310         _reached(0), local_reached(false) {}
    1311    
     1310        _reached(0), local_reached(false) {}
     1311
    13121312    /// \brief Destructor.
    13131313    ///
    … …  
    13261326    DfsVisit &reachedMap(ReachedMap &m) {
    13271327      if(local_reached) {
    1328         delete _reached;
    1329         local_reached=false;
     1328        delete _reached;
     1329        local_reached=false;
    13301330      }
    13311331      _reached = &m;
    … …  
    13541354      _stack_head = -1;
    13551355      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
    1356         _reached->set(u, false);
    1357       }
    1358     }
    1359    
     1356        _reached->set(u, false);
     1357      }
     1358    }
     1359
    13601360    /// \brief Adds a new source node.
    13611361    ///
    … …  
    13631363    void addSource(Node s) {
    13641364      if(!(*_reached)[s]) {
    1365           _reached->set(s,true);
    1366           _visitor->start(s);
    1367           _visitor->reach(s);
    1368           Arc e;
    1369           _digraph->firstOut(e, s);
    1370           if (e != INVALID) {
    1371             _stack[++_stack_head] = e;
    1372           } else {
    1373             _visitor->leave(s);
    1374           }
    1375         }
    1376     }
    1377    
     1365          _reached->set(s,true);
     1366          _visitor->start(s);
     1367          _visitor->reach(s);
     1368          Arc e;
     1369          _digraph->firstOut(e, s);
     1370          if (e != INVALID) {
     1371            _stack[++_stack_head] = e;
     1372          } else {
     1373            _visitor->leave(s);
     1374          }
     1375        }
     1376    }
     1377
    13781378    /// \brief Processes the next arc.
    13791379    ///
    … …  
    13831383    ///
    13841384    /// \pre The stack must not be empty!
    1385     Arc processNextArc() { 
     1385    Arc processNextArc() {
    13861386      Arc e = _stack[_stack_head];
    13871387      Node m = _digraph->target(e);
    13881388      if(!(*_reached)[m]) {
    1389         _visitor->discover(e);
    1390         _visitor->reach(m);
    1391         _reached->set(m, true);
    1392         _digraph->firstOut(_stack[++_stack_head], m);
     1389        _visitor->discover(e);
     1390        _visitor->reach(m);
     1391        _reached->set(m, true);
     1392        _digraph->firstOut(_stack[++_stack_head], m);
    13931393      } else {
    1394         _visitor->examine(e);
    1395         m = _digraph->source(e);
    1396         _digraph->nextOut(_stack[_stack_head]);
     1394        _visitor->examine(e);
     1395        m = _digraph->source(e);
     1396        _digraph->nextOut(_stack[_stack_head]);
    13971397      }
    13981398      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
    1399         _visitor->leave(m);
    1400         --_stack_head;
    1401         if (_stack_head >= 0) {
    1402           _visitor->backtrack(_stack[_stack_head]);
    1403           m = _digraph->source(_stack[_stack_head]);
    1404           _digraph->nextOut(_stack[_stack_head]);
    1405         } else {
    1406           _visitor->stop(m);     
    1407         }
     1399        _visitor->leave(m);
     1400        --_stack_head;
     1401        if (_stack_head >= 0) {
     1402          _visitor->backtrack(_stack[_stack_head]);
     1403          m = _digraph->source(_stack[_stack_head]);
     1404          _digraph->nextOut(_stack[_stack_head]);
     1405        } else {
     1406          _visitor->stop(m);
     1407        }
    14081408      }
    14091409      return e;
    … …  
    14161416    /// \return The next arc to be processed or INVALID if the stack is
    14171417    /// empty.
    1418     Arc nextArc() { 
     1418    Arc nextArc() {
    14191419      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
    14201420    }
    … …  
    14311431    /// Returns the number of the nodes to be processed in the queue.
    14321432    int queueSize() { return _stack_head + 1; }
    1433    
     1433
    14341434    /// \brief Executes the algorithm.
    14351435    ///
    … …  
    14411441      while ( !emptyQueue() ) processNextArc();
    14421442    }
    1443    
     1443
    14441444    /// \brief Executes the algorithm until \c dest is reached.
    14451445    ///
    … …  
    14491449    /// with addSource() before using this function.
    14501450    void start(Node dest) {
    1451       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) 
    1452         processNextArc();
    1453     }
    1454    
     1451      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
     1452        processNextArc();
     1453    }
     1454
    14551455    /// \brief Executes the algorithm until a condition is met.
    14561456    ///
    … …  
    14911491
    14921492    /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
    1493    
     1493
    14941494    /// This method runs the %DFS algorithm in order to
    14951495    /// compute the %DFS path to each node. The algorithm computes
Note: See TracChangeset for help on using the changeset viewer.