COIN-OR::LEMON - Graph Library

Changeset 960:b89e46862dc2 in lemon


Ignore:
Timestamp:
03/18/10 14:17:03 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
959:38213abd2911 (diff), 958:d6052a9c4e8d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge backout of a6eb9698c321 (#360,#51)

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/bellman_ford.h

    r958 r960  
    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).
     
    3636
    3737  /// \brief Default OperationTraits for the BellmanFord algorithm class.
    38   /// 
     38  ///
    3939  /// This operation traits class defines all computational operations
    4040  /// and constants that are used in the Bellman-Ford algorithm.
     
    4343  /// value is used as extremal infinity value.
    4444  template <
    45     typename V, 
     45    typename V,
    4646    bool has_inf = std::numeric_limits<V>::has_infinity>
    4747  struct BellmanFordDefaultOperationTraits {
     
    8484    }
    8585  };
    86  
     86
    8787  /// \brief Default traits class of BellmanFord class.
    8888  ///
     
    9292  template<typename GR, typename LEN>
    9393  struct BellmanFordDefaultTraits {
    94     /// The type of the digraph the algorithm runs on. 
     94    /// The type of the digraph the algorithm runs on.
    9595    typedef GR Digraph;
    9696
     
    110110    /// \see BellmanFordDefaultOperationTraits
    111111    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    112  
    113     /// \brief The type of the map that stores the last arcs of the 
     112
     113    /// \brief The type of the map that stores the last arcs of the
    114114    /// shortest paths.
    115     /// 
     115    ///
    116116    /// The type of the map that stores the last
    117117    /// arcs of the shortest paths.
     
    120120
    121121    /// \brief Instantiates a \c PredMap.
    122     /// 
    123     /// This function instantiates a \ref PredMap. 
     122    ///
     123    /// This function instantiates a \ref PredMap.
    124124    /// \param g is the digraph to which we would like to define the
    125125    /// \ref PredMap.
     
    136136    /// \brief Instantiates a \c DistMap.
    137137    ///
    138     /// This function instantiates a \ref DistMap. 
    139     /// \param g is the digraph to which we would like to define the 
     138    /// This function instantiates a \ref DistMap.
     139    /// \param g is the digraph to which we would like to define the
    140140    /// \ref DistMap.
    141141    static DistMap *createDistMap(const GR& g) {
     
    144144
    145145  };
    146  
     146
    147147  /// \brief %BellmanFord algorithm class.
    148148  ///
    149149  /// \ingroup shortest_path
    150   /// This class provides an efficient implementation of the Bellman-Ford 
     150  /// This class provides an efficient implementation of the Bellman-Ford
    151151  /// algorithm. The maximum time complexity of the algorithm is
    152152  /// <tt>O(ne)</tt>.
     
    159159  ///
    160160  /// The arc lengths are passed to the algorithm using a
    161   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
     161  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
    162162  /// kind of length. The type of the length values is determined by the
    163163  /// \ref concepts::ReadMap::Value "Value" type of the length map.
     
    189189    ///The type of the underlying digraph.
    190190    typedef typename TR::Digraph Digraph;
    191    
     191
    192192    /// \brief The type of the arc lengths.
    193193    typedef typename TR::LengthMap::Value Value;
     
    236236    void create_maps() {
    237237      if(!_pred) {
    238         _local_pred = true;
    239         _pred = Traits::createPredMap(*_gr);
     238        _local_pred = true;
     239        _pred = Traits::createPredMap(*_gr);
    240240      }
    241241      if(!_dist) {
    242         _local_dist = true;
    243         _dist = Traits::createDistMap(*_gr);
     242        _local_dist = true;
     243        _dist = Traits::createDistMap(*_gr);
    244244      }
    245245      if(!_mask) {
     
    247247      }
    248248    }
    249    
     249
    250250  public :
    251  
     251
    252252    typedef BellmanFord Create;
    253253
     
    272272    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    273273    template <class T>
    274     struct SetPredMap 
     274    struct SetPredMap
    275275      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
    276276      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
    277277    };
    278    
     278
    279279    template <class T>
    280280    struct SetDistMapTraits : public Traits {
     
    293293    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    294294    template <class T>
    295     struct SetDistMap 
     295    struct SetDistMap
    296296      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
    297297      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
     
    302302      typedef T OperationTraits;
    303303    };
    304    
    305     /// \brief \ref named-templ-param "Named parameter" for setting 
     304
     305    /// \brief \ref named-templ-param "Named parameter" for setting
    306306    /// \c OperationTraits type.
    307307    ///
     
    315315      Create;
    316316    };
    317    
     317
    318318    ///@}
    319319
    320320  protected:
    321    
     321
    322322    BellmanFord() {}
    323323
    324   public:     
    325    
     324  public:
     325
    326326    /// \brief Constructor.
    327327    ///
     
    333333      _pred(0), _local_pred(false),
    334334      _dist(0), _local_dist(false), _mask(0) {}
    335    
     335
    336336    ///Destructor.
    337337    ~BellmanFord() {
     
    360360    BellmanFord &predMap(PredMap &map) {
    361361      if(_local_pred) {
    362         delete _pred;
    363         _local_pred=false;
     362        delete _pred;
     363        _local_pred=false;
    364364      }
    365365      _pred = &map;
     
    378378    BellmanFord &distMap(DistMap &map) {
    379379      if(_local_dist) {
    380         delete _dist;
    381         _local_dist=false;
     380        delete _dist;
     381        _local_dist=false;
    382382      }
    383383      _dist = &map;
     
    397397
    398398    /// \brief Initializes the internal data structures.
    399     /// 
     399    ///
    400400    /// Initializes the internal data structures. The optional parameter
    401401    /// is the initial distance of each node.
     
    403403      create_maps();
    404404      for (NodeIt it(*_gr); it != INVALID; ++it) {
    405         _pred->set(it, INVALID);
    406         _dist->set(it, value);
     405        _pred->set(it, INVALID);
     406        _dist->set(it, value);
    407407      }
    408408      _process.clear();
    409409      if (OperationTraits::less(value, OperationTraits::infinity())) {
    410         for (NodeIt it(*_gr); it != INVALID; ++it) {
    411           _process.push_back(it);
    412           _mask->set(it, true);
    413         }
     410        for (NodeIt it(*_gr); it != INVALID; ++it) {
     411          _process.push_back(it);
     412          _mask->set(it, true);
     413        }
    414414      } else {
    415         for (NodeIt it(*_gr); it != INVALID; ++it) {
    416           _mask->set(it, false);
    417         }
    418       }
    419     }
    420    
     415        for (NodeIt it(*_gr); it != INVALID; ++it) {
     416          _mask->set(it, false);
     417        }
     418      }
     419    }
     420
    421421    /// \brief Adds a new source node.
    422422    ///
     
    426426      _dist->set(source, dst);
    427427      if (!(*_mask)[source]) {
    428         _process.push_back(source);
    429         _mask->set(source, true);
     428        _process.push_back(source);
     429        _mask->set(source, true);
    430430      }
    431431    }
     
    452452    bool processNextRound() {
    453453      for (int i = 0; i < int(_process.size()); ++i) {
    454         _mask->set(_process[i], false);
     454        _mask->set(_process[i], false);
    455455      }
    456456      std::vector<Node> nextProcess;
    457457      std::vector<Value> values(_process.size());
    458458      for (int i = 0; i < int(_process.size()); ++i) {
    459         values[i] = (*_dist)[_process[i]];
     459        values[i] = (*_dist)[_process[i]];
    460460      }
    461461      for (int i = 0; i < int(_process.size()); ++i) {
    462         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    463           Node target = _gr->target(it);
    464           Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
    465           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    466             _pred->set(target, it);
    467             _dist->set(target, relaxed);
    468             if (!(*_mask)[target]) {
    469               _mask->set(target, true);
    470               nextProcess.push_back(target);
    471             }
    472           }       
    473         }
     462        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     463          Node target = _gr->target(it);
     464          Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
     465          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     466            _pred->set(target, it);
     467            _dist->set(target, relaxed);
     468            if (!(*_mask)[target]) {
     469              _mask->set(target, true);
     470              nextProcess.push_back(target);
     471            }
     472          }
     473        }
    474474      }
    475475      _process.swap(nextProcess);
     
    493493    bool processNextWeakRound() {
    494494      for (int i = 0; i < int(_process.size()); ++i) {
    495         _mask->set(_process[i], false);
     495        _mask->set(_process[i], false);
    496496      }
    497497      std::vector<Node> nextProcess;
    498498      for (int i = 0; i < int(_process.size()); ++i) {
    499         for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
    500           Node target = _gr->target(it);
    501           Value relaxed =
    502             OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
    503           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    504             _pred->set(target, it);
    505             _dist->set(target, relaxed);
    506             if (!(*_mask)[target]) {
    507               _mask->set(target, true);
    508               nextProcess.push_back(target);
    509             }
    510           }       
    511         }
     499        for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
     500          Node target = _gr->target(it);
     501          Value relaxed =
     502            OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
     503          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     504            _pred->set(target, it);
     505            _dist->set(target, relaxed);
     506            if (!(*_mask)[target]) {
     507              _mask->set(target, true);
     508              nextProcess.push_back(target);
     509            }
     510          }
     511        }
    512512      }
    513513      _process.swap(nextProcess);
     
    531531      int num = countNodes(*_gr) - 1;
    532532      for (int i = 0; i < num; ++i) {
    533         if (processNextWeakRound()) break;
     533        if (processNextWeakRound()) break;
    534534      }
    535535    }
     
    543543    /// if the digraph contains cycles with negative total length.
    544544    ///
    545     /// The algorithm computes 
     545    /// The algorithm computes
    546546    /// - the shortest path tree (forest),
    547547    /// - the distance of each node from the root(s).
    548     /// 
     548    ///
    549549    /// \return \c false if there is a negative cycle in the digraph.
    550550    ///
    551551    /// \pre init() must be called and at least one root node should be
    552     /// added with addSource() before using this function. 
     552    /// added with addSource() before using this function.
    553553    bool checkedStart() {
    554554      int num = countNodes(*_gr);
    555555      for (int i = 0; i < num; ++i) {
    556         if (processNextWeakRound()) return true;
     556        if (processNextWeakRound()) return true;
    557557      }
    558558      return _process.empty();
     
    578578    ///
    579579    /// \pre init() must be called and at least one root node should be
    580     /// added with addSource() before using this function. 
     580    /// added with addSource() before using this function.
    581581    void limitedStart(int num) {
    582582      for (int i = 0; i < num; ++i) {
    583         if (processNextRound()) break;
    584       }
    585     }
    586    
     583        if (processNextRound()) break;
     584      }
     585    }
     586
    587587    /// \brief Runs the algorithm from the given root node.
    588     ///   
     588    ///
    589589    /// This method runs the Bellman-Ford algorithm from the given root
    590590    /// node \c s in order to compute the shortest path to each node.
     
    605605      start();
    606606    }
    607    
     607
    608608    /// \brief Runs the algorithm from the given root node with arc
    609609    /// number limit.
    610     ///   
     610    ///
    611611    /// This method runs the Bellman-Ford algorithm from the given root
    612612    /// node \c s in order to compute the shortest path distance for each
     
    634634      limitedStart(num);
    635635    }
    636    
     636
    637637    ///@}
    638638
     
    649649      ///
    650650      /// Constructor for getting the active nodes of the given BellmanFord
    651       /// instance. 
     651      /// instance.
    652652      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
    653653      {
     
    663663      ///
    664664      /// Conversion to \c Node.
    665       operator Node() const { 
     665      operator Node() const {
    666666        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
    667667      }
     
    672672      ActiveIt& operator++() {
    673673        --_index;
    674         return *this; 
    675       }
    676 
    677       bool operator==(const ActiveIt& it) const { 
    678         return static_cast<Node>(*this) == static_cast<Node>(it); 
    679       }
    680       bool operator!=(const ActiveIt& it) const { 
    681         return static_cast<Node>(*this) != static_cast<Node>(it); 
    682       }
    683       bool operator<(const ActiveIt& it) const { 
    684         return static_cast<Node>(*this) < static_cast<Node>(it); 
    685       }
    686      
     674        return *this;
     675      }
     676
     677      bool operator==(const ActiveIt& it) const {
     678        return static_cast<Node>(*this) == static_cast<Node>(it);
     679      }
     680      bool operator!=(const ActiveIt& it) const {
     681        return static_cast<Node>(*this) != static_cast<Node>(it);
     682      }
     683      bool operator<(const ActiveIt& it) const {
     684        return static_cast<Node>(*this) < static_cast<Node>(it);
     685      }
     686
    687687    private:
    688688      const BellmanFord* _algorithm;
    689689      int _index;
    690690    };
    691    
     691
    692692    /// \name Query Functions
    693693    /// The result of the Bellman-Ford algorithm can be obtained using these
    694694    /// functions.\n
    695695    /// Either \ref run() or \ref init() should be called before using them.
    696    
     696
    697697    ///@{
    698698
    699699    /// \brief The shortest path to the given node.
    700     ///   
     700    ///
    701701    /// Gives back the shortest path to the given node from the root(s).
    702702    ///
     
    709709      return Path(*_gr, *_pred, t);
    710710    }
    711          
     711
    712712    /// \brief The distance of the given node from the root(s).
    713713    ///
     
    749749    /// \pre Either \ref run() or \ref init() must be called before
    750750    /// using this function.
    751     Node predNode(Node v) const { 
    752       return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 
    753     }
    754    
     751    Node predNode(Node v) const {
     752      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
     753    }
     754
    755755    /// \brief Returns a const reference to the node map that stores the
    756756    /// distances of the nodes.
     
    762762    /// using this function.
    763763    const DistMap &distMap() const { return *_dist;}
    764  
     764
    765765    /// \brief Returns a const reference to the node map that stores the
    766766    /// predecessor arcs.
     
    772772    /// using this function.
    773773    const PredMap &predMap() const { return *_pred; }
    774  
     774
    775775    /// \brief Checks if a node is reached from the root(s).
    776776    ///
     
    784784
    785785    /// \brief Gives back a negative cycle.
    786     ///   
     786    ///
    787787    /// This function gives back a directed cycle with negative total
    788788    /// length if the algorithm has already found one.
     
    811811      return cycle;
    812812    }
    813    
     813
    814814    ///@}
    815815  };
    816  
     816
    817817  /// \brief Default traits class of bellmanFord() function.
    818818  ///
     
    822822  template <typename GR, typename LEN>
    823823  struct BellmanFordWizardDefaultTraits {
    824     /// The type of the digraph the algorithm runs on. 
     824    /// The type of the digraph the algorithm runs on.
    825825    typedef GR Digraph;
    826826
     
    843843    /// \brief The type of the map that stores the last
    844844    /// arcs of the shortest paths.
    845     /// 
     845    ///
    846846    /// The type of the map that stores the last arcs of the shortest paths.
    847847    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     
    849849
    850850    /// \brief Instantiates a \c PredMap.
    851     /// 
     851    ///
    852852    /// This function instantiates a \ref PredMap.
    853853    /// \param g is the digraph to which we would like to define the
     
    865865    /// \brief Instantiates a \c DistMap.
    866866    ///
    867     /// This function instantiates a \ref DistMap. 
     867    /// This function instantiates a \ref DistMap.
    868868    /// \param g is the digraph to which we would like to define the
    869869    /// \ref DistMap.
     
    878878    typedef lemon::Path<Digraph> Path;
    879879  };
    880  
     880
    881881  /// \brief Default traits class used by BellmanFordWizard.
    882882  ///
     
    885885  /// \tparam LEN The type of the length map.
    886886  template <typename GR, typename LEN>
    887   class BellmanFordWizardBase 
     887  class BellmanFordWizardBase
    888888    : public BellmanFordWizardDefaultTraits<GR, LEN> {
    889889
     
    908908    public:
    909909    /// Constructor.
    910    
     910
    911911    /// This constructor does not require parameters, it initiates
    912912    /// all of the attributes to default values \c 0.
     
    915915
    916916    /// Constructor.
    917    
     917
    918918    /// This constructor requires two parameters,
    919919    /// others are initiated to \c 0.
    920920    /// \param gr The digraph the algorithm runs on.
    921921    /// \param len The length map.
    922     BellmanFordWizardBase(const GR& gr, 
    923                           const LEN& len) :
    924       _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 
    925       _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 
     922    BellmanFordWizardBase(const GR& gr,
     923                          const LEN& len) :
     924      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
     925      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
    926926      _pred(0), _dist(0), _path(0), _di(0) {}
    927927
    928928  };
    929  
     929
    930930  /// \brief Auxiliary class for the function-type interface of the
    931931  /// \ref BellmanFord "Bellman-Ford" algorithm.
     
    952952    typedef typename Digraph::Arc Arc;
    953953    typedef typename Digraph::OutArcIt ArcIt;
    954    
     954
    955955    typedef typename TR::LengthMap LengthMap;
    956956    typedef typename LengthMap::Value Value;
     
    969969    /// \param gr The digraph the algorithm runs on.
    970970    /// \param len The length map.
    971     BellmanFordWizard(const Digraph& gr, const LengthMap& len) 
     971    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
    972972      : TR(gr, len) {}
    973973
     
    978978
    979979    /// \brief Runs the Bellman-Ford algorithm from the given source node.
    980     ///   
     980    ///
    981981    /// This method runs the Bellman-Ford algorithm from the given source
    982982    /// node in order to compute the shortest path to each node.
    983983    void run(Node s) {
    984       BellmanFord<Digraph,LengthMap,TR> 
    985         bf(*reinterpret_cast<const Digraph*>(Base::_graph),
     984      BellmanFord<Digraph,LengthMap,TR>
     985        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
    986986           *reinterpret_cast<const LengthMap*>(Base::_length));
    987987      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     
    10181018      SetPredMapBase(const TR &b) : TR(b) {}
    10191019    };
    1020    
     1020
    10211021    /// \brief \ref named-templ-param "Named parameter" for setting
    10221022    /// the predecessor map.
     
    10291029      return BellmanFordWizard<SetPredMapBase<T> >(*this);
    10301030    }
    1031    
     1031
    10321032    template<class T>
    10331033    struct SetDistMapBase : public Base {
     
    10361036      SetDistMapBase(const TR &b) : TR(b) {}
    10371037    };
    1038    
     1038
    10391039    /// \brief \ref named-templ-param "Named parameter" for setting
    10401040    /// the distance map.
     
    10771077      return *this;
    10781078    }
    1079    
     1079
    10801080  };
    1081  
     1081
    10821082  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
    10831083  /// algorithm.
     
    10871087  /// algorithm.
    10881088  ///
    1089   /// This function also has several \ref named-templ-func-param 
    1090   /// "named parameters", they are declared as the members of class 
     1089  /// This function also has several \ref named-templ-func-param
     1090  /// "named parameters", they are declared as the members of class
    10911091  /// \ref BellmanFordWizard.
    10921092  /// The following examples show how to use these parameters.
     
    11051105  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
    11061106  bellmanFord(const GR& digraph,
    1107               const LEN& length)
     1107              const LEN& length)
    11081108  {
    11091109    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
  • lemon/bellman_ford.h

    r956 r960  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
    31 #include <lemon/tolerance.h>
    3231#include <lemon/path.h>
    3332
     
    3635namespace lemon {
    3736
    38   /// \brief Default operation traits for the BellmanFord algorithm class.
     37  /// \brief Default OperationTraits for the BellmanFord algorithm class.
    3938  ///
    4039  /// This operation traits class defines all computational operations
     
    4342  /// If the numeric type does not have infinity value, then the maximum
    4443  /// value is used as extremal infinity value.
    45   ///
    46   /// \see BellmanFordToleranceOperationTraits
    4744  template <
    4845    typename V,
    4946    bool has_inf = std::numeric_limits<V>::has_infinity>
    5047  struct BellmanFordDefaultOperationTraits {
    51     /// \brief Value type for the algorithm.
     48    /// \e
    5249    typedef V Value;
    5350    /// \brief Gives back the zero value of the type.
     
    8582    static bool less(const Value& left, const Value& right) {
    8683      return left < right;
    87     }
    88   };
    89 
    90   /// \brief Operation traits for the BellmanFord algorithm class
    91   /// using tolerance.
    92   ///
    93   /// This operation traits class defines all computational operations
    94   /// and constants that are used in the Bellman-Ford algorithm.
    95   /// The only difference between this implementation and
    96   /// \ref BellmanFordDefaultOperationTraits is that this class uses
    97   /// the \ref Tolerance "tolerance technique" in its \ref less()
    98   /// function.
    99   ///
    100   /// \tparam V The value type.
    101   /// \tparam eps The epsilon value for the \ref less() function.
    102   /// By default, it is the epsilon value used by \ref Tolerance
    103   /// "Tolerance<V>".
    104   ///
    105   /// \see BellmanFordDefaultOperationTraits
    106 #ifdef DOXYGEN
    107   template <typename V, V eps>
    108 #else
    109   template <
    110     typename V,
    111     V eps = Tolerance<V>::def_epsilon>
    112 #endif
    113   struct BellmanFordToleranceOperationTraits {
    114     /// \brief Value type for the algorithm.
    115     typedef V Value;
    116     /// \brief Gives back the zero value of the type.
    117     static Value zero() {
    118       return static_cast<Value>(0);
    119     }
    120     /// \brief Gives back the positive infinity value of the type.
    121     static Value infinity() {
    122       return std::numeric_limits<Value>::infinity();
    123     }
    124     /// \brief Gives back the sum of the given two elements.
    125     static Value plus(const Value& left, const Value& right) {
    126       return left + right;
    127     }
    128     /// \brief Gives back \c true only if the first value is less than
    129     /// the second.
    130     static bool less(const Value& left, const Value& right) {
    131       return left + eps < right;
    13284    }
    13385  };
     
    156108    /// It defines the used operations and the infinity value for the
    157109    /// given \c Value type.
    158     /// \see BellmanFordDefaultOperationTraits,
    159     /// BellmanFordToleranceOperationTraits
     110    /// \see BellmanFordDefaultOperationTraits
    160111    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    161112
     
    887838    /// It defines the used operations and the infinity value for the
    888839    /// given \c Value type.
    889     /// \see BellmanFordDefaultOperationTraits,
    890     /// BellmanFordToleranceOperationTraits
     840    /// \see BellmanFordDefaultOperationTraits
    891841    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
    892842
  • test/bellman_ford_test.cc

    r958 r960  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9898    pp = const_bf_test.path(t);
    9999    pp = const_bf_test.negativeCycle();
    100    
     100
    101101    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
    102102  }
     
    110110    concepts::ReadWriteMap<Node,Arc> pred_map;
    111111    concepts::ReadWriteMap<Node,Value> dist_map;
    112    
     112
    113113    bf_test
    114114      .lengthMap(length_map)
     
    189189  check(pathSource(gr, p) == s, "path() found a wrong path.");
    190190  check(pathTarget(gr, p) == t, "path() found a wrong path.");
    191  
     191
    192192  ListPath<Digraph> path;
    193193  Value dist;
     
    228228  SmartDigraph gr;
    229229  IntArcMap length(gr);
    230  
     230
    231231  Node n1 = gr.addNode();
    232232  Node n2 = gr.addNode();
    233233  Node n3 = gr.addNode();
    234234  Node n4 = gr.addNode();
    235  
     235
    236236  Arc a1 = gr.addArc(n1, n2);
    237237  Arc a2 = gr.addArc(n2, n2);
    238  
     238
    239239  length[a1] = 2;
    240240  length[a2] = -1;
    241  
     241
    242242  {
    243243    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     
    247247          "Wrong negative cycle.");
    248248  }
    249  
     249
    250250  length[a2] = 0;
    251  
     251
    252252  {
    253253    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
     
    256256          "Negative cycle should not be found.");
    257257  }
    258  
     258
    259259  length[gr.addArc(n1, n3)] = 5;
    260260  length[gr.addArc(n4, n3)] = 1;
    261261  length[gr.addArc(n2, n4)] = 2;
    262262  length[gr.addArc(n3, n2)] = -4;
    263  
     263
    264264  {
    265265    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
  • test/bellman_ford_test.cc

    r956 r960  
    105105      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
    106106      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
    107       ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >
    108107      ::Create bf_test(gr,length);
    109108
Note: See TracChangeset for help on using the changeset viewer.