Changeset 1864:1788205e36af in lemon-0.x

Timestamp:

12/19/05 10:43:13 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2436

Message:

Fixing Bellman's name

Location:

lemon

Files:

• Makefile.am (modified) (1 diff)
• bellman_ford.h (copied) (copied from lemon/belmann_ford.h) (43 diffs)
• johnson.h (modified) (4 diffs)

lemon/Makefile.am

@@ -22 +22 @@
 
 nobase_pkginclude_HEADERS = \
-        belmann_ford.h \
+        bellman_ford.h \
         bezier.h \
         bfs.h \

lemon/bellman_ford.h

@@ -1 +1 @@
 /* -*- C++ -*-
- * lemon/belmann_ford.h - Part of LEMON, a generic C++ optimization library
+ * lemon/bellman_ford.h - Part of LEMON, a generic C++ optimization library
  *
  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -20 +20 @@
 /// \ingroup flowalgs
 /// \file
-/// \brief BelmannFord algorithm.
+/// \brief BellmanFord algorithm.
 ///
 
@@ -32 +32 @@
 namespace lemon {
 
-  /// \brief Default OperationTraits for the BelmannFord algorithm class.
+  /// \brief Default OperationTraits for the BellmanFord algorithm class.
   ///  
   /// It defines all computational operations and constants which are
-  /// used in the belmann ford algorithm. The default implementation
+  /// used in the bellman ford algorithm. The default implementation
   /// is based on the numeric_limits class. If the numeric type does not
   /// have infinity value then the maximum value is used as extremal
@@ -42 +42 @@
     typename Value, 
     bool has_infinity = std::numeric_limits<Value>::has_infinity>
-  struct BelmannFordDefaultOperationTraits {
+  struct BellmanFordDefaultOperationTraits {
     /// \brief Gives back the zero value of the type.
     static Value zero() {
@@ -62 +62 @@
 
   template <typename Value>
-  struct BelmannFordDefaultOperationTraits<Value, false> {
+  struct BellmanFordDefaultOperationTraits<Value, false> {
     static Value zero() {
       return static_cast<Value>(0);
@@ -78 +78 @@
   };
   
-  /// \brief Default traits class of BelmannFord class.
-  ///
-  /// Default traits class of BelmannFord class.
+  /// \brief Default traits class of BellmanFord class.
+  ///
+  /// Default traits class of BellmanFord class.
   /// \param _Graph Graph type.
   /// \param _LegthMap Type of length map.
   template<class _Graph, class _LengthMap>
-  struct BelmannFordDefaultTraits {
+  struct BellmanFordDefaultTraits {
     /// The graph type the algorithm runs on. 
     typedef _Graph Graph;
@@ -97 +97 @@
     typedef typename _LengthMap::Value Value;
 
-    /// \brief Operation traits for belmann-ford algorithm.
+    /// \brief Operation traits for bellman-ford algorithm.
     ///
     /// It defines the infinity type on the given Value type
     /// and the used operation.
-    /// \see BelmannFordDefaultOperationTraits
-    typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
+    /// \see BellmanFordDefaultOperationTraits
+    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
  
     /// \brief The type of the map that stores the last edges of the 
@@ -140 +140 @@
   };
   
-  /// \brief %BelmannFord algorithm class.
+  /// \brief %BellmanFord algorithm class.
   ///
   /// \ingroup flowalgs
-  /// This class provides an efficient implementation of \c Belmann-Ford 
+  /// This class provides an efficient implementation of \c Bellman-Ford 
   /// algorithm. The edge lengths are passed to the algorithm using a
   /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
   /// kind of length.
   ///
-  /// The Belmann-Ford algorithm solves the shortest path from one node
+  /// The Bellman-Ford algorithm solves the shortest path from one node
   /// problem when the edges can have negative length but the graph should
   /// not contain cycles with negative sum of length. If we can assume
@@ -161 +161 @@
   /// \param _Graph The graph type the algorithm runs on. The default value
   /// is \ref ListGraph. The value of _Graph is not used directly by
-  /// BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.
+  /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
   /// \param _LengthMap This read-only EdgeMap determines the lengths of the
   /// edges. The default map type is \ref concept::StaticGraph::EdgeMap 
   /// "Graph::EdgeMap<int>".  The value of _LengthMap is not used directly 
-  /// by BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.  
+  /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.  
   /// \param _Traits Traits class to set various data types used by the 
-  /// algorithm.  The default traits class is \ref BelmannFordDefaultTraits
-  /// "BelmannFordDefaultTraits<_Graph,_LengthMap>".  See \ref
-  /// BelmannFordDefaultTraits for the documentation of a BelmannFord traits
+  /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
+  /// "BellmanFordDefaultTraits<_Graph,_LengthMap>".  See \ref
+  /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
   /// class.
   ///
@@ -179 +179 @@
   template <typename _Graph=ListGraph,
             typename _LengthMap=typename _Graph::template EdgeMap<int>,
-            typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> >
+            typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> >
 #endif
-  class BelmannFord {
+  class BellmanFord {
   public:
     
@@ -192 +192 @@
     public:
       virtual const char* exceptionName() const {
-        return "lemon::BelmannFord::UninitializedParameter";
+        return "lemon::BellmanFord::UninitializedParameter";
       }
     };
@@ -250 +250 @@
   public :
  
-    typedef BelmannFord Create;
+    typedef BellmanFord Create;
 
     /// \name Named template parameters
@@ -270 +270 @@
     template <class T>
     struct DefPredMap 
-      : public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > {
-      typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
+      : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
+      typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
     };
     
@@ -289 +289 @@
     template <class T>
     struct DefDistMap 
-      : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {
-      typedef BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
+      : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
+      typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
     };
     
@@ -305 +305 @@
     template <class T>
     struct DefOperationTraits
-      : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
-      typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
+      : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
+      typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
       Create;
     };
@@ -314 +314 @@
   protected:
     
-    BelmannFord() {}
+    BellmanFord() {}
 
   public:      
@@ -322 +322 @@
     /// \param _graph the graph the algorithm will run on.
     /// \param _length the length map used by the algorithm.
-    BelmannFord(const Graph& _graph, const LengthMap& _length) :
+    BellmanFord(const Graph& _graph, const LengthMap& _length) :
       graph(&_graph), length(&_length),
       _pred(0), local_pred(false),
@@ -328 +328 @@
     
     ///Destructor.
-    ~BelmannFord() {
+    ~BellmanFord() {
       if(local_pred) delete _pred;
       if(local_dist) delete _dist;
@@ -338 +338 @@
     /// Sets the length map.
     /// \return \c (*this)
-    BelmannFord &lengthMap(const LengthMap &m) {
+    BellmanFord &lengthMap(const LengthMap &m) {
       length = &m;
       return *this;
@@ -350 +350 @@
     /// automatically allocated map, of course.
     /// \return \c (*this)
-    BelmannFord &predMap(PredMap &m) {
+    BellmanFord &predMap(PredMap &m) {
       if(local_pred) {
         delete _pred;
@@ -366 +366 @@
     /// automatically allocated map, of course.
     /// \return \c (*this)
-    BelmannFord &distMap(DistMap &m) {
+    BellmanFord &distMap(DistMap &m) {
       if(local_dist) {
         delete _dist;
@@ -417 +417 @@
     }
 
-    /// \brief Executes one round from the belmann ford algorithm.
+    /// \brief Executes one round from the bellman ford algorithm.
     ///
     /// If the algoritm calculated the distances in the previous round 
@@ -451 +451 @@
     }
 
-    /// \brief Executes one weak round from the belmann ford algorithm.
+    /// \brief Executes one weak round from the bellman ford algorithm.
     ///
     /// If the algorithm calculated the distances in the
@@ -489 +489 @@
     /// with addSource() before using this function.
     ///
-    /// This method runs the %BelmannFord algorithm from the root node(s)
+    /// This method runs the %BellmanFord algorithm from the root node(s)
     /// in order to compute the shortest path to each node. The algorithm 
     /// computes 
@@ -507 +507 @@
     /// a negative cycles in the graph it gives back false.
     ///
-    /// This method runs the %BelmannFord algorithm from the root node(s)
+    /// This method runs the %BellmanFord algorithm from the root node(s)
     /// in order to compute the shortest path to each node. The algorithm 
     /// computes 
@@ -525 +525 @@
     /// with addSource() before using this function.
     ///
-    /// This method runs the %BelmannFord algorithm from the root node(s)
+    /// This method runs the %BellmanFord algorithm from the root node(s)
     /// in order to compute the shortest path with at most \c length edge 
     /// long paths to each node. The algorithm computes 
@@ -536 +536 @@
     }
     
-    /// \brief Runs %BelmannFord algorithm from node \c s.
+    /// \brief Runs %BellmanFord algorithm from node \c s.
     ///    
-    /// This method runs the %BelmannFord algorithm from a root node \c s
+    /// This method runs the %BellmanFord algorithm from a root node \c s
     /// in order to compute the shortest path to each node. The algorithm 
     /// computes
@@ -556 +556 @@
     }
     
-    /// \brief Runs %BelmannFord algorithm with limited path length 
+    /// \brief Runs %BellmanFord algorithm with limited path length 
     /// from node \c s.
     ///    
-    /// This method runs the %BelmannFord algorithm from a root node \c s
+    /// This method runs the %BellmanFord algorithm from a root node \c s
     /// in order to compute the shortest path with at most \c len edges 
     /// to each node. The algorithm computes
@@ -580 +580 @@
 
     /// \name Query Functions
-    /// The result of the %BelmannFord algorithm can be obtained using these
+    /// The result of the %BellmanFord algorithm can be obtained using these
     /// functions.\n
     /// Before the use of these functions,
@@ -663 +663 @@
   };
  
-  /// \brief Default traits class of BelmannFord function.
-  ///
-  /// Default traits class of BelmannFord function.
+  /// \brief Default traits class of BellmanFord function.
+  ///
+  /// Default traits class of BellmanFord function.
   /// \param _Graph Graph type.
   /// \param _LengthMap Type of length map.
   template <typename _Graph, typename _LengthMap>
-  struct BelmannFordWizardDefaultTraits {
+  struct BellmanFordWizardDefaultTraits {
     /// \brief The graph type the algorithm runs on. 
     typedef _Graph Graph;
@@ -682 +682 @@
     typedef typename _LengthMap::Value Value;
 
-    /// \brief Operation traits for belmann-ford algorithm.
+    /// \brief Operation traits for bellman-ford algorithm.
     ///
     /// It defines the infinity type on the given Value type
     /// and the used operation.
-    /// \see BelmannFordDefaultOperationTraits
-    typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
+    /// \see BellmanFordDefaultOperationTraits
+    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 
     /// \brief The type of the map that stores the last
@@ -716 +716 @@
   };
   
-  /// \brief Default traits used by \ref BelmannFordWizard
-  ///
-  /// To make it easier to use BelmannFord algorithm
+  /// \brief Default traits used by \ref BellmanFordWizard
+  ///
+  /// To make it easier to use BellmanFord algorithm
   /// we have created a wizard class.
-  /// This \ref BelmannFordWizard class needs default traits,
-  /// as well as the \ref BelmannFord class.
-  /// The \ref BelmannFordWizardBase is a class to be the default traits of the
-  /// \ref BelmannFordWizard class.
+  /// This \ref BellmanFordWizard class needs default traits,
+  /// as well as the \ref BellmanFord class.
+  /// The \ref BellmanFordWizardBase is a class to be the default traits of the
+  /// \ref BellmanFordWizard class.
   /// \todo More named parameters are required...
   template<class _Graph,class _LengthMap>
-  class BelmannFordWizardBase 
-    : public BelmannFordWizardDefaultTraits<_Graph,_LengthMap> {
-
-    typedef BelmannFordWizardDefaultTraits<_Graph,_LengthMap> Base;
+  class BellmanFordWizardBase 
+    : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
+
+    typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
   protected:
     /// Type of the nodes in the graph.
@@ -750 +750 @@
     /// This constructor does not require parameters, therefore it initiates
     /// all of the attributes to default values (0, INVALID).
-    BelmannFordWizardBase() : _graph(0), _length(0), _pred(0),
+    BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
                            _dist(0), _source(INVALID) {}
 
@@ -761 +761 @@
     /// \param length is the initial value of  \ref _length
     /// \param source is the initial value of  \ref _source
-    BelmannFordWizardBase(const _Graph& graph, 
+    BellmanFordWizardBase(const _Graph& graph, 
                           const _LengthMap& length, 
                           Node source = INVALID) :
@@ -769 +769 @@
   };
   
-  /// A class to make the usage of BelmannFord algorithm easier
-
-  /// This class is created to make it easier to use BelmannFord algorithm.
-  /// It uses the functions and features of the plain \ref BelmannFord,
+  /// A class to make the usage of BellmanFord algorithm easier
+
+  /// This class is created to make it easier to use BellmanFord algorithm.
+  /// It uses the functions and features of the plain \ref BellmanFord,
   /// but it is much simpler to use it.
   ///
@@ -778 +778 @@
   /// in the traits class is based on functions that returns the new class
   /// and not on templatable built-in classes.
-  /// When using the plain \ref BelmannFord
+  /// When using the plain \ref BellmanFord
   /// the new class with the modified type comes from
   /// the original class by using the ::
-  /// operator. In the case of \ref BelmannFordWizard only
+  /// operator. In the case of \ref BellmanFordWizard only
   /// a function have to be called and it will
   /// return the needed class.
   ///
   /// It does not have own \ref run method. When its \ref run method is called
-  /// it initiates a plain \ref BelmannFord class, and calls the \ref 
-  /// BelmannFord::run method of it.
+  /// it initiates a plain \ref BellmanFord class, and calls the \ref 
+  /// BellmanFord::run method of it.
   template<class _Traits>
-  class BelmannFordWizard : public _Traits {
+  class BellmanFordWizard : public _Traits {
     typedef _Traits Base;
 
@@ -815 +815 @@
   public:
     /// Constructor.
-    BelmannFordWizard() : _Traits() {}
+    BellmanFordWizard() : _Traits() {}
 
     /// \brief Constructor that requires parameters.
@@ -821 +821 @@
     /// Constructor that requires parameters.
     /// These parameters will be the default values for the traits class.
-    BelmannFordWizard(const Graph& graph, const LengthMap& length, 
+    BellmanFordWizard(const Graph& graph, const LengthMap& length, 
                       Node source = INVALID) 
       : _Traits(graph, length, source) {}
 
     /// \brief Copy constructor
-    BelmannFordWizard(const _Traits &b) : _Traits(b) {}
-
-    ~BelmannFordWizard() {}
-
-    /// \brief Runs BelmannFord algorithm from a given node.
+    BellmanFordWizard(const _Traits &b) : _Traits(b) {}
+
+    ~BellmanFordWizard() {}
+
+    /// \brief Runs BellmanFord algorithm from a given node.
     ///    
-    /// Runs BelmannFord algorithm from a given node.
+    /// Runs BellmanFord algorithm from a given node.
     /// The node can be given by the \ref source function.
     void run() {
       if(Base::_source == INVALID) throw UninitializedParameter();
-      BelmannFord<Graph,LengthMap,_Traits> 
+      BellmanFord<Graph,LengthMap,_Traits> 
         bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
       if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
@@ -843 +843 @@
     }
 
-    /// \brief Runs BelmannFord algorithm from the given node.
-    ///
-    /// Runs BelmannFord algorithm from the given node.
+    /// \brief Runs BellmanFord algorithm from the given node.
+    ///
+    /// Runs BellmanFord algorithm from the given node.
     /// \param source is the given source.
     void run(Node source) {
@@ -866 +866 @@
     ///
     template<class T>
-    BelmannFordWizard<DefPredMapBase<T> > predMap(const T &t) 
+    BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 
     {
       Base::_pred=(void *)&t;
-      return BelmannFordWizard<DefPredMapBase<T> >(*this);
+      return BellmanFordWizard<DefPredMapBase<T> >(*this);
     }
     
@@ -886 +886 @@
     ///
     template<class T>
-    BelmannFordWizard<DefDistMapBase<T> > distMap(const T &t) {
+    BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
       Base::_dist=(void *)&t;
-      return BelmannFordWizard<DefDistMapBase<T> >(*this);
+      return BellmanFordWizard<DefDistMapBase<T> >(*this);
     }
 
@@ -904 +904 @@
     ///
     template<class T>
-    BelmannFordWizard<DefOperationTraitsBase<T> > distMap() {
-      return BelmannFordWizard<DefDistMapBase<T> >(*this);
-    }
-    
-    /// \brief Sets the source node, from which the BelmannFord algorithm runs.
-    ///
-    /// Sets the source node, from which the BelmannFord algorithm runs.
+    BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
+      return BellmanFordWizard<DefDistMapBase<T> >(*this);
+    }
+    
+    /// \brief Sets the source node, from which the BellmanFord algorithm runs.
+    ///
+    /// Sets the source node, from which the BellmanFord algorithm runs.
     /// \param source is the source node.
-    BelmannFordWizard<_Traits>& source(Node source) {
+    BellmanFordWizard<_Traits>& source(Node source) {
       Base::_source = source;
       return *this;
@@ -919 +919 @@
   };
   
-  /// \brief Function type interface for BelmannFord algorithm.
+  /// \brief Function type interface for BellmanFord algorithm.
   ///
   /// \ingroup flowalgs
-  /// Function type interface for BelmannFord algorithm.
+  /// Function type interface for BellmanFord algorithm.
   ///
   /// This function also has several \ref named-templ-func-param 
   /// "named parameters", they are declared as the members of class 
-  /// \ref BelmannFordWizard.
+  /// \ref BellmanFordWizard.
   /// The following
   /// example shows how to use these parameters.
   /// \code
-  /// belmannford(g,length,source).predMap(preds).run();
+  /// bellmanford(g,length,source).predMap(preds).run();
   /// \endcode
-  /// \warning Don't forget to put the \ref BelmannFordWizard::run() "run()"
+  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
   /// to the end of the parameter list.
-  /// \sa BelmannFordWizard
-  /// \sa BelmannFord
+  /// \sa BellmanFordWizard
+  /// \sa BellmanFord
   template<class _Graph, class _LengthMap>
-  BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
-  belmannFord(const _Graph& graph,
+  BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
+  bellmanFord(const _Graph& graph,
               const _LengthMap& length, 
               typename _Graph::Node source = INVALID) {
-    return BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
+    return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
       (graph, length, source);
   }

lemon/johnson.h

@@ -26 +26 @@
 #include <lemon/graph_utils.h>
 #include <lemon/dijkstra.h>
-#include <lemon/belmann_ford.h>
+#include <lemon/bellman_ford.h>
 #include <lemon/invalid.h>
 #include <lemon/error.h>
@@ -101 +101 @@
     typedef typename _LengthMap::Value Value;
 
-    /// \brief Operation traits for belmann-ford algorithm.
+    /// \brief Operation traits for bellman-ford algorithm.
     ///
     /// It defines the infinity type on the given Value type
@@ -545 +545 @@
     void start() {
 
-      typedef typename BelmannFord<Graph, LengthMap>::
+      typedef typename BellmanFord<Graph, LengthMap>::
       template DefOperationTraits<OperationTraits>::
       template DefPredMap<NullMap<Node, Edge> >::
-      Create BelmannFordType;
+      Create BellmanFordType;
       
-      BelmannFordType belmannford(*graph, *length);
+      BellmanFordType bellmanford(*graph, *length);
 
       NullMap<Node, Edge> predMap;
 
-      belmannford.predMap(predMap);
+      bellmanford.predMap(predMap);
       
-      belmannford.init(OperationTraits::zero());
-      belmannford.start();
-
-      shiftedRun(belmannford.distMap());
+      bellmanford.init(OperationTraits::zero());
+      bellmanford.start();
+
+      shiftedRun(bellmanford.distMap());
     }
 
@@ -572 +572 @@
     bool checkedStart() {
       
-      typedef typename BelmannFord<Graph, LengthMap>::
+      typedef typename BellmanFord<Graph, LengthMap>::
       template DefOperationTraits<OperationTraits>::
       template DefPredMap<NullMap<Node, Edge> >::
-      Create BelmannFordType;
-
-      BelmannFordType belmannford(*graph, *length);
+      Create BellmanFordType;
+
+      BellmanFordType bellmanford(*graph, *length);
 
       NullMap<Node, Edge> predMap;
 
-      belmannford.predMap(predMap);
+      bellmanford.predMap(predMap);
       
-      belmannford.init(OperationTraits::zero());
-      if (!belmannford.checkedStart()) return false;
-
-      shiftedRun(belmannford.distMap());
+      bellmanford.init(OperationTraits::zero());
+      if (!bellmanford.checkedStart()) return false;
+
+      shiftedRun(bellmanford.distMap());
       return true;
     }