COIN-OR::LEMON - Graph Library

Changeset 877:141f9c0db4a3 in lemon-1.2 for lemon/bellman_ford.h


Ignore:
Timestamp:
03/06/10 15:35:12 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
878:f802439d2b58, 880:38213abd2911, 909:f112c18bc304
Phase:
public
Message:

Unify the sources (#339)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bellman_ford.h

    r844 r877  
    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 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    3737
    3838  /// \brief Default operation traits for the BellmanFord algorithm class.
    39   /// 
     39  ///
    4040  /// This operation traits class defines all computational operations
    4141  /// and constants that are used in the Bellman-Ford algorithm.
     
    4646  /// \see BellmanFordToleranceOperationTraits
    4747  template <
    48     typename V, 
     48    typename V,
    4949    bool has_inf = std::numeric_limits<V>::has_infinity>
    5050  struct BellmanFordDefaultOperationTraits {
     
    8787    }
    8888  };
    89  
     89
    9090  /// \brief Operation traits for the BellmanFord algorithm class
    9191  /// using tolerance.
     
    140140  template<typename GR, typename LEN>
    141141  struct BellmanFordDefaultTraits {
    142     /// The type of the digraph the algorithm runs on. 
     142    /// The type of the digraph the algorithm runs on.
    143143    typedef GR Digraph;
    144144
     
    159159    /// BellmanFordToleranceOperationTraits
    160160    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    161  
    162     /// \brief The type of the map that stores the last arcs of the 
     161
     162    /// \brief The type of the map that stores the last arcs of the
    163163    /// shortest paths.
    164     /// 
     164    ///
    165165    /// The type of the map that stores the last
    166166    /// arcs of the shortest paths.
     
    169169
    170170    /// \brief Instantiates a \c PredMap.
    171     /// 
    172     /// This function instantiates a \ref PredMap. 
     171    ///
     172    /// This function instantiates a \ref PredMap.
    173173    /// \param g is the digraph to which we would like to define the
    174174    /// \ref PredMap.
     
    185185    /// \brief Instantiates a \c DistMap.
    186186    ///
    187     /// This function instantiates a \ref DistMap. 
    188     /// \param g is the digraph to which we would like to define the 
     187    /// This function instantiates a \ref DistMap.
     188    /// \param g is the digraph to which we would like to define the
    189189    /// \ref DistMap.
    190190    static DistMap *createDistMap(const GR& g) {
     
    193193
    194194  };
    195  
     195
    196196  /// \brief %BellmanFord algorithm class.
    197197  ///
    198198  /// \ingroup shortest_path
    199   /// This class provides an efficient implementation of the Bellman-Ford 
     199  /// This class provides an efficient implementation of the Bellman-Ford
    200200  /// algorithm. The maximum time complexity of the algorithm is
    201201  /// <tt>O(ne)</tt>.
     
    208208  ///
    209209  /// The arc lengths are passed to the algorithm using a
    210   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
     210  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
    211211  /// kind of length. The type of the length values is determined by the
    212212  /// \ref concepts::ReadMap::Value "Value" type of the length map.
     
    238238    ///The type of the underlying digraph.
    239239    typedef typename TR::Digraph Digraph;
    240    
     240
    241241    /// \brief The type of the arc lengths.
    242242    typedef typename TR::LengthMap::Value Value;
     
    285285    void create_maps() {
    286286      if(!_pred) {
    287         _local_pred = true;
    288         _pred = Traits::createPredMap(*_gr);
     287        _local_pred = true;
     288        _pred = Traits::createPredMap(*_gr);
    289289      }
    290290      if(!_dist) {
    291         _local_dist = true;
    292         _dist = Traits::createDistMap(*_gr);
     291        _local_dist = true;
     292        _dist = Traits::createDistMap(*_gr);
    293293      }
    294294      if(!_mask) {
     
    296296      }
    297297    }
    298    
     298
    299299  public :
    300  
     300
    301301    typedef BellmanFord Create;
    302302
     
    321321    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    322322    template <class T>
    323     struct SetPredMap 
     323    struct SetPredMap
    324324      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
    325325      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
    326326    };
    327    
     327
    328328    template <class T>
    329329    struct SetDistMapTraits : public Traits {
     
    342342    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    343343    template <class T>
    344     struct SetDistMap 
     344    struct SetDistMap
    345345      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
    346346      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
     
    351351      typedef T OperationTraits;
    352352    };
    353    
    354     /// \brief \ref named-templ-param "Named parameter" for setting 
     353
     354    /// \brief \ref named-templ-param "Named parameter" for setting
    355355    /// \c OperationTraits type.
    356356    ///
     
    364364      Create;
    365365    };
    366    
     366
    367367    ///@}
    368368
    369369  protected:
    370    
     370
    371371    BellmanFord() {}
    372372
    373   public:     
    374    
     373  public:
     374
    375375    /// \brief Constructor.
    376376    ///
     
    382382      _pred(0), _local_pred(false),
    383383      _dist(0), _local_dist(false), _mask(0) {}
    384    
     384
    385385    ///Destructor.
    386386    ~BellmanFord() {
     
    409409    BellmanFord &predMap(PredMap &map) {
    410410      if(_local_pred) {
    411         delete _pred;
    412         _local_pred=false;
     411        delete _pred;
     412        _local_pred=false;
    413413      }
    414414      _pred = &map;
     
    427427    BellmanFord &distMap(DistMap &map) {
    428428      if(_local_dist) {
    429         delete _dist;
    430         _local_dist=false;
     429        delete _dist;
     430        _local_dist=false;
    431431      }
    432432      _dist = &map;
     
    446446
    447447    /// \brief Initializes the internal data structures.
    448     /// 
     448    ///
    449449    /// Initializes the internal data structures. The optional parameter
    450450    /// is the initial distance of each node.
     
    452452      create_maps();
    453453      for (NodeIt it(*_gr); it != INVALID; ++it) {
    454         _pred->set(it, INVALID);
    455         _dist->set(it, value);
     454        _pred->set(it, INVALID);
     455        _dist->set(it, value);
    456456      }
    457457      _process.clear();
    458458      if (OperationTraits::less(value, OperationTraits::infinity())) {
    459         for (NodeIt it(*_gr); it != INVALID; ++it) {
    460           _process.push_back(it);
    461           _mask->set(it, true);
    462         }
     459        for (NodeIt it(*_gr); it != INVALID; ++it) {
     460          _process.push_back(it);
     461          _mask->set(it, true);
     462        }
    463463      } else {
    464         for (NodeIt it(*_gr); it != INVALID; ++it) {
    465           _mask->set(it, false);
    466         }
    467       }
    468     }
    469    
     464        for (NodeIt it(*_gr); it != INVALID; ++it) {
     465          _mask->set(it, false);
     466        }
     467      }
     468    }
     469
    470470    /// \brief Adds a new source node.
    471471    ///
     
    475475      _dist->set(source, dst);
    476476      if (!(*_mask)[source]) {
    477         _process.push_back(source);
    478         _mask->set(source, true);
     477        _process.push_back(source);
     478        _mask->set(source, true);
    479479      }
    480480    }
     
    501501    bool processNextRound() {
    502502      for (int i = 0; i < int(_process.size()); ++i) {
    503         _mask->set(_process[i], false);
     503        _mask->set(_process[i], false);
    504504      }
    505505      std::vector<Node> nextProcess;
    506506      std::vector<Value> values(_process.size());
    507507      for (int i = 0; i < int(_process.size()); ++i) {
    508         values[i] = (*_dist)[_process[i]];
     508        values[i] = (*_dist)[_process[i]];
    509509      }
    510510      for (int i = 0; i < int(_process.size()); ++i) {
    511         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    512           Node target = _gr->target(it);
    513           Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
    514           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    515             _pred->set(target, it);
    516             _dist->set(target, relaxed);
    517             if (!(*_mask)[target]) {
    518               _mask->set(target, true);
    519               nextProcess.push_back(target);
    520             }
    521           }       
    522         }
     511        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     512          Node target = _gr->target(it);
     513          Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
     514          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     515            _pred->set(target, it);
     516            _dist->set(target, relaxed);
     517            if (!(*_mask)[target]) {
     518              _mask->set(target, true);
     519              nextProcess.push_back(target);
     520            }
     521          }
     522        }
    523523      }
    524524      _process.swap(nextProcess);
     
    542542    bool processNextWeakRound() {
    543543      for (int i = 0; i < int(_process.size()); ++i) {
    544         _mask->set(_process[i], false);
     544        _mask->set(_process[i], false);
    545545      }
    546546      std::vector<Node> nextProcess;
    547547      for (int i = 0; i < int(_process.size()); ++i) {
    548         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    549           Node target = _gr->target(it);
    550           Value relaxed =
    551             OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
    552           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    553             _pred->set(target, it);
    554             _dist->set(target, relaxed);
    555             if (!(*_mask)[target]) {
    556               _mask->set(target, true);
    557               nextProcess.push_back(target);
    558             }
    559           }       
    560         }
     548        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     549          Node target = _gr->target(it);
     550          Value relaxed =
     551            OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
     552          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     553            _pred->set(target, it);
     554            _dist->set(target, relaxed);
     555            if (!(*_mask)[target]) {
     556              _mask->set(target, true);
     557              nextProcess.push_back(target);
     558            }
     559          }
     560        }
    561561      }
    562562      _process.swap(nextProcess);
     
    580580      int num = countNodes(*_gr) - 1;
    581581      for (int i = 0; i < num; ++i) {
    582         if (processNextWeakRound()) break;
     582        if (processNextWeakRound()) break;
    583583      }
    584584    }
     
    592592    /// if the digraph contains cycles with negative total length.
    593593    ///
    594     /// The algorithm computes 
     594    /// The algorithm computes
    595595    /// - the shortest path tree (forest),
    596596    /// - the distance of each node from the root(s).
    597     /// 
     597    ///
    598598    /// \return \c false if there is a negative cycle in the digraph.
    599599    ///
    600600    /// \pre init() must be called and at least one root node should be
    601     /// added with addSource() before using this function. 
     601    /// added with addSource() before using this function.
    602602    bool checkedStart() {
    603603      int num = countNodes(*_gr);
    604604      for (int i = 0; i < num; ++i) {
    605         if (processNextWeakRound()) return true;
     605        if (processNextWeakRound()) return true;
    606606      }
    607607      return _process.empty();
     
    627627    ///
    628628    /// \pre init() must be called and at least one root node should be
    629     /// added with addSource() before using this function. 
     629    /// added with addSource() before using this function.
    630630    void limitedStart(int num) {
    631631      for (int i = 0; i < num; ++i) {
    632         if (processNextRound()) break;
    633       }
    634     }
    635    
     632        if (processNextRound()) break;
     633      }
     634    }
     635
    636636    /// \brief Runs the algorithm from the given root node.
    637     ///   
     637    ///
    638638    /// This method runs the Bellman-Ford algorithm from the given root
    639639    /// node \c s in order to compute the shortest path to each node.
     
    654654      start();
    655655    }
    656    
     656
    657657    /// \brief Runs the algorithm from the given root node with arc
    658658    /// number limit.
    659     ///   
     659    ///
    660660    /// This method runs the Bellman-Ford algorithm from the given root
    661661    /// node \c s in order to compute the shortest path distance for each
     
    683683      limitedStart(num);
    684684    }
    685    
     685
    686686    ///@}
    687687
     
    698698      ///
    699699      /// Constructor for getting the active nodes of the given BellmanFord
    700       /// instance. 
     700      /// instance.
    701701      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
    702702      {
     
    712712      ///
    713713      /// Conversion to \c Node.
    714       operator Node() const { 
     714      operator Node() const {
    715715        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
    716716      }
     
    721721      ActiveIt& operator++() {
    722722        --_index;
    723         return *this; 
    724       }
    725 
    726       bool operator==(const ActiveIt& it) const { 
    727         return static_cast<Node>(*this) == static_cast<Node>(it); 
    728       }
    729       bool operator!=(const ActiveIt& it) const { 
    730         return static_cast<Node>(*this) != static_cast<Node>(it); 
    731       }
    732       bool operator<(const ActiveIt& it) const { 
    733         return static_cast<Node>(*this) < static_cast<Node>(it); 
    734       }
    735      
     723        return *this;
     724      }
     725
     726      bool operator==(const ActiveIt& it) const {
     727        return static_cast<Node>(*this) == static_cast<Node>(it);
     728      }
     729      bool operator!=(const ActiveIt& it) const {
     730        return static_cast<Node>(*this) != static_cast<Node>(it);
     731      }
     732      bool operator<(const ActiveIt& it) const {
     733        return static_cast<Node>(*this) < static_cast<Node>(it);
     734      }
     735
    736736    private:
    737737      const BellmanFord* _algorithm;
    738738      int _index;
    739739    };
    740    
     740
    741741    /// \name Query Functions
    742742    /// The result of the Bellman-Ford algorithm can be obtained using these
    743743    /// functions.\n
    744744    /// Either \ref run() or \ref init() should be called before using them.
    745    
     745
    746746    ///@{
    747747
    748748    /// \brief The shortest path to the given node.
    749     ///   
     749    ///
    750750    /// Gives back the shortest path to the given node from the root(s).
    751751    ///
     
    758758      return Path(*_gr, *_pred, t);
    759759    }
    760          
     760
    761761    /// \brief The distance of the given node from the root(s).
    762762    ///
     
    798798    /// \pre Either \ref run() or \ref init() must be called before
    799799    /// using this function.
    800     Node predNode(Node v) const { 
    801       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
    802     }
    803    
     800    Node predNode(Node v) const {
     801      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
     802    }
     803
    804804    /// \brief Returns a const reference to the node map that stores the
    805805    /// distances of the nodes.
     
    811811    /// using this function.
    812812    const DistMap &distMap() const { return *_dist;}
    813  
     813
    814814    /// \brief Returns a const reference to the node map that stores the
    815815    /// predecessor arcs.
     
    821821    /// using this function.
    822822    const PredMap &predMap() const { return *_pred; }
    823  
     823
    824824    /// \brief Checks if a node is reached from the root(s).
    825825    ///
     
    833833
    834834    /// \brief Gives back a negative cycle.
    835     ///   
     835    ///
    836836    /// This function gives back a directed cycle with negative total
    837837    /// length if the algorithm has already found one.
     
    860860      return cycle;
    861861    }
    862    
     862
    863863    ///@}
    864864  };
    865  
     865
    866866  /// \brief Default traits class of bellmanFord() function.
    867867  ///
     
    871871  template <typename GR, typename LEN>
    872872  struct BellmanFordWizardDefaultTraits {
    873     /// The type of the digraph the algorithm runs on. 
     873    /// The type of the digraph the algorithm runs on.
    874874    typedef GR Digraph;
    875875
     
    893893    /// \brief The type of the map that stores the last
    894894    /// arcs of the shortest paths.
    895     /// 
     895    ///
    896896    /// The type of the map that stores the last arcs of the shortest paths.
    897897    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     
    899899
    900900    /// \brief Instantiates a \c PredMap.
    901     /// 
     901    ///
    902902    /// This function instantiates a \ref PredMap.
    903903    /// \param g is the digraph to which we would like to define the
     
    915915    /// \brief Instantiates a \c DistMap.
    916916    ///
    917     /// This function instantiates a \ref DistMap. 
     917    /// This function instantiates a \ref DistMap.
    918918    /// \param g is the digraph to which we would like to define the
    919919    /// \ref DistMap.
     
    928928    typedef lemon::Path<Digraph> Path;
    929929  };
    930  
     930
    931931  /// \brief Default traits class used by BellmanFordWizard.
    932932  ///
     
    935935  /// \tparam LEN The type of the length map.
    936936  template <typename GR, typename LEN>
    937   class BellmanFordWizardBase 
     937  class BellmanFordWizardBase
    938938    : public BellmanFordWizardDefaultTraits<GR, LEN> {
    939939
     
    958958    public:
    959959    /// Constructor.
    960    
     960
    961961    /// This constructor does not require parameters, it initiates
    962962    /// all of the attributes to default values \c 0.
     
    965965
    966966    /// Constructor.
    967    
     967
    968968    /// This constructor requires two parameters,
    969969    /// others are initiated to \c 0.
    970970    /// \param gr The digraph the algorithm runs on.
    971971    /// \param len The length map.
    972     BellmanFordWizardBase(const GR& gr, 
    973                           const LEN& len) :
    974       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
    975       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
     972    BellmanFordWizardBase(const GR& gr,
     973                          const LEN& len) :
     974      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
     975      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
    976976      _pred(0), _dist(0), _path(0), _di(0) {}
    977977
    978978  };
    979  
     979
    980980  /// \brief Auxiliary class for the function-type interface of the
    981981  /// \ref BellmanFord "Bellman-Ford" algorithm.
     
    10021002    typedef typename Digraph::Arc Arc;
    10031003    typedef typename Digraph::OutArcIt ArcIt;
    1004    
     1004
    10051005    typedef typename TR::LengthMap LengthMap;
    10061006    typedef typename LengthMap::Value Value;
     
    10191019    /// \param gr The digraph the algorithm runs on.
    10201020    /// \param len The length map.
    1021     BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
     1021    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
    10221022      : TR(gr, len) {}
    10231023
     
    10281028
    10291029    /// \brief Runs the Bellman-Ford algorithm from the given source node.
    1030     ///   
     1030    ///
    10311031    /// This method runs the Bellman-Ford algorithm from the given source
    10321032    /// node in order to compute the shortest path to each node.
    10331033    void run(Node s) {
    1034       BellmanFord<Digraph,LengthMap,TR> 
    1035         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
     1034      BellmanFord<Digraph,LengthMap,TR>
     1035        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
    10361036           *reinterpret_cast<const LengthMap*>(Base::_length));
    10371037      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     
    10681068      SetPredMapBase(const TR &b) : TR(b) {}
    10691069    };
    1070    
     1070
    10711071    /// \brief \ref named-templ-param "Named parameter" for setting
    10721072    /// the predecessor map.
     
    10791079      return BellmanFordWizard<SetPredMapBase<T> >(*this);
    10801080    }
    1081    
     1081
    10821082    template<class T>
    10831083    struct SetDistMapBase : public Base {
     
    10861086      SetDistMapBase(const TR &b) : TR(b) {}
    10871087    };
    1088    
     1088
    10891089    /// \brief \ref named-templ-param "Named parameter" for setting
    10901090    /// the distance map.
     
    11271127      return *this;
    11281128    }
    1129    
     1129
    11301130  };
    1131  
     1131
    11321132  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
    11331133  /// algorithm.
     
    11371137  /// algorithm.
    11381138  ///
    1139   /// This function also has several \ref named-templ-func-param 
    1140   /// "named parameters", they are declared as the members of class 
     1139  /// This function also has several \ref named-templ-func-param
     1140  /// "named parameters", they are declared as the members of class
    11411141  /// \ref BellmanFordWizard.
    11421142  /// The following examples show how to use these parameters.
     
    11551155  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
    11561156  bellmanFord(const GR& digraph,
    1157               const LEN& length)
     1157              const LEN& length)
    11581158  {
    11591159    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
Note: See TracChangeset for help on using the changeset viewer.