lemon-0.x: comparison lemon/bellman

equal deleted inserted replaced

-:0cf01fe691ad
+:ae1949538876
 /* -*- 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
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 #ifndef LEMON_BELMANN_FORD_H
 #define LEMON_BELMANN_FORD_H
 /// \ingroup flowalgs
 /// \file
-/// \brief BelmannFord algorithm.
+/// \brief BellmanFord algorithm.
 ///
 #include <lemon/list_graph.h>
 #include <lemon/invalid.h>
 #include <lemon/error.h>
 #include <limits>
 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
 /// infinity value.
 template <
 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() {
 return static_cast<Value>(0);
 }
 /// \brief Gives back the positive infinity value of the type.
 return left < right;
 }
 };
 template <typename Value>
-struct BelmannFordDefaultOperationTraits<Value, false> {
+struct BellmanFordDefaultOperationTraits<Value, false> {
 static Value zero() {
 return static_cast<Value>(0);
 }
 static Value infinity() {
 return std::numeric_limits<Value>::max();
 static bool less(const Value& left, const Value& right) {
 return left < right;
 }
 };
-/// \brief Default traits class of BelmannFord class.
+/// \brief Default traits class of BellmanFord class.
 ///
-/// Default traits class of BelmannFord 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;
 /// \brief The type of the map that stores the edge lengths.
 ///
 typedef _LengthMap LengthMap;
 // The type of the length of the edges.
 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
+/// \see BellmanFordDefaultOperationTraits
-typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
+typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 /// \brief The type of the map that stores the last edges of the
 /// shortest paths.
 ///
 /// The type of the map that stores the last
 return new DistMap(graph);
 }
 };
-/// \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
 /// that all edge is non-negative in the graph then the dijkstra algorithm
 /// should be used rather.
 ///
 /// The type of the length is determined by the
 /// \ref concept::ReadMap::Value "Value" of the length map.
 ///
 /// \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
+/// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
-/// "BelmannFordDefaultTraits<_Graph,_LengthMap>".  See \ref
+/// "BellmanFordDefaultTraits<_Graph,_LengthMap>".  See \ref
-/// BelmannFordDefaultTraits for the documentation of a BelmannFord traits
+/// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
 /// class.
 ///
 /// \author Balazs Dezso
 #ifdef DOXYGEN
 template <typename _Graph, typename _LengthMap, typename _Traits>
 #else
 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:
 /// \brief \ref Exception for uninitialized parameters.
 ///
 /// This error represents problems in the initialization
 /// of the parameters of the algorithms.
 class UninitializedParameter : public lemon::UninitializedParameter {
 public:
 virtual const char* exceptionName() const {
-	return "lemon::BelmannFord::UninitializedParameter";
+	return "lemon::BellmanFord::UninitializedParameter";
 }
 };
 typedef _Traits Traits;
 ///The type of the underlying graph.
 _mask = new MaskMap(*graph, false);
 }
 public :
-typedef BelmannFord Create;
+typedef BellmanFord Create;
 /// \name Named template parameters
 ///@{
 /// type
 /// \ref named-templ-param "Named parameter" for setting PredMap type
 ///
 template <class T>
 struct DefPredMap
-: public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > {
+: public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
-typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
+typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
 };
 template <class T>
 struct DefDistMapTraits : public Traits {
 typedef T DistMap;
 ///
 /// \ref named-templ-param "Named parameter" for setting DistMap type
 ///
 template <class T>
 struct DefDistMap
-: public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {
+: public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
-typedef BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
+typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
 };
 template <class T>
 struct DefOperationTraitsTraits : public Traits {
 typedef T OperationTraits;
 ///
 /// \ref named-templ-param "Named parameter" for setting OperationTraits
 /// type
 template <class T>
 struct DefOperationTraits
-: public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
+: public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
-typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
+typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
 Create;
 };
 ///@}
 protected:
-BelmannFord() {}
+BellmanFord() {}
 public:
 /// \brief Constructor.
 ///
 /// \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),
 _dist(0), local_dist(false) {}
 ///Destructor.
-~BelmannFord() {
+~BellmanFord() {
 if(local_pred) delete _pred;
 if(local_dist) delete _dist;
 delete _mask;
 }
 /// \brief Sets the length map.
 ///
 /// Sets the length map.
 /// \return \c (*this)
-BelmannFord &lengthMap(const LengthMap &m) {
+BellmanFord &lengthMap(const LengthMap &m) {
 length = &m;
 return *this;
 }
 /// \brief Sets the map storing the predecessor edges.
 /// Sets the map storing the predecessor edges.
 /// If you don't use this function before calling \ref run(),
 /// it will allocate one. The destuctor deallocates this
 /// automatically allocated map, of course.
 /// \return \c (*this)
-BelmannFord &predMap(PredMap &m) {
+BellmanFord &predMap(PredMap &m) {
 if(local_pred) {
 	delete _pred;
 	local_pred=false;
 }
 _pred = &m;
 /// Sets the map storing the distances calculated by the algorithm.
 /// If you don't use this function before calling \ref run(),
 /// it will allocate one. The destuctor deallocates this
 /// automatically allocated map, of course.
 /// \return \c (*this)
-BelmannFord &distMap(DistMap &m) {
+BellmanFord &distMap(DistMap &m) {
 if(local_dist) {
 	delete _dist;
 	local_dist=false;
 }
 _dist = &m;
 	_process.push_back(source);
 	_mask->set(source, true);
 }
 }
-/// \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
 /// strictly for all at most k length paths then it will calculate the
 /// distances strictly for all at most k + 1 length paths. With k
 /// iteration this function calculates the at most k length paths.
 }
 _process.swap(nextProcess);
 return _process.empty();
 }
-/// \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
 /// previous round at least for all at most k length paths then it will
 /// calculate the distances at least for all at most k + 1 length paths.
 /// This function does not make it possible to calculate strictly the
 /// \brief Executes the algorithm.
 ///
 /// \pre init() must be called and at least one node should be added
 /// 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
 /// - The shortest path tree.
 /// - The distance of each node from the root(s).
 void start() {
 ///
 /// \pre init() must be called and at least one node should be added
 /// with addSource() before using this function. If there is
 /// 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
 /// - The shortest path tree.
 /// - The distance of each node from the root(s).
 bool checkedStart() {
 /// \brief Executes the algorithm with path length limit.
 ///
 /// \pre init() must be called and at least one node should be added
 /// 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
 /// - The shortest path tree.
 /// - The limited distance of each node from the root(s).
 void limitedStart(int length) {
 for (int i = 0; i < length; ++i) {
 	if (processNextRound()) break;
 }
 }
-/// \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
 /// - The shortest path tree.
 /// - The distance of each node from the root.
 ///
 init();
 addSource(s);
 start();
 }
-/// \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
 /// - The shortest path tree.
 /// - The distance of each node from the root.
 ///
 }
 ///@}
 /// \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,
 /// either run() or start() must be called.
 ///@{
 bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
 ///@}
 };
-/// \brief Default traits class of BelmannFord function.
+/// \brief Default traits class of BellmanFord function.
 ///
-/// Default traits class of BelmannFord 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;
 /// \brief The type of the map that stores the edge lengths.
 ///
 typedef _LengthMap LengthMap;
 /// \brief The value type of the length map.
 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
+/// \see BellmanFordDefaultOperationTraits
-typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
+typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 /// \brief The type of the map that stores the last
 /// edges of the shortest paths.
 ///
 /// The type of the map that stores the last
 static DistMap *createDistMap(const _Graph &) {
 return new DistMap();
 }
 };
-/// \brief Default traits used by \ref BelmannFordWizard
+/// \brief Default traits used by \ref BellmanFordWizard
 ///
-/// To make it easier to use BelmannFord algorithm
+/// To make it easier to use BellmanFord algorithm
 /// we have created a wizard class.
-/// This \ref BelmannFordWizard class needs default traits,
+/// This \ref BellmanFordWizard class needs default traits,
-/// as well as the \ref BelmannFord class.
+/// as well as the \ref BellmanFord class.
-/// The \ref BelmannFordWizardBase is a class to be the default traits of the
+/// The \ref BellmanFordWizardBase is a class to be the default traits of the
-/// \ref BelmannFordWizard class.
+/// \ref BellmanFordWizard class.
 /// \todo More named parameters are required...
 template<class _Graph,class _LengthMap>
-class BelmannFordWizardBase
+class BellmanFordWizardBase
-: public BelmannFordWizardDefaultTraits<_Graph,_LengthMap> {
+: public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
-typedef BelmannFordWizardDefaultTraits<_Graph,_LengthMap> Base;
+typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
 protected:
 /// Type of the nodes in the graph.
 typedef typename Base::Graph::Node Node;
 /// Pointer to the underlying graph.
 public:
 /// Constructor.
 /// 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) {}
 /// Constructor.
 /// This constructor requires some parameters,
 /// listed in the parameters list.
 /// Others are initiated to 0.
 /// \param graph is the initial value of  \ref _graph
 /// \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) :
 _graph((void *)&graph), _length((void *)&length), _pred(0),
 _dist(0), _source(source) {}
 };
-/// A class to make the usage of BelmannFord algorithm easier
+/// A class to make the usage of BellmanFord algorithm easier
-/// This class is created to make it easier to use BelmannFord algorithm.
+/// This class is created to make it easier to use BellmanFord algorithm.
-/// It uses the functions and features of the plain \ref BelmannFord,
+/// It uses the functions and features of the plain \ref BellmanFord,
 /// but it is much simpler to use it.
 ///
 /// Simplicity means that the way to change the types defined
 /// 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
+/// it initiates a plain \ref BellmanFord class, and calls the \ref
-/// BelmannFord::run method of it.
+/// BellmanFord::run method of it.
 template<class _Traits>
-class BelmannFordWizard : public _Traits {
+class BellmanFordWizard : public _Traits {
 typedef _Traits Base;
 ///The type of the underlying graph.
 typedef typename _Traits::Graph Graph;
 ///The type of the map that stores the dists of the nodes.
 typedef typename _Traits::DistMap DistMap;
 public:
 /// Constructor.
-BelmannFordWizard() : _Traits() {}
+BellmanFordWizard() : _Traits() {}
 /// \brief Constructor that requires parameters.
 ///
 /// 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) {}
+BellmanFordWizard(const _Traits &b) : _Traits(b) {}
-~BelmannFordWizard() {}
+~BellmanFordWizard() {}
-/// \brief Runs BelmannFord algorithm from a given node.
+/// \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);
 if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
 bf.run(Base::_source);
 }
-/// \brief Runs BelmannFord algorithm from the given node.
+/// \brief Runs BellmanFord algorithm from the given node.
 ///
-/// Runs BelmannFord algorithm from the given node.
+/// Runs BellmanFord algorithm from the given node.
 /// \param source is the given source.
 void run(Node source) {
 Base::_source = source;
 run();
 }
 ///
 /// \ref named-templ-param "Named parameter"
 ///function for setting PredMap type
 ///
 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);
 }
 template<class T>
 struct DefDistMapBase : public Base {
 typedef T DistMap;
 ///
 /// \ref named-templ-param "Named parameter"
 ///function for setting DistMap type
 ///
 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);
 }
 template<class T>
 struct DefOperationTraitsBase : public Base {
 typedef T OperationTraits;
 ///
 /// \ref named-templ-param "Named parameter"
 ///function for setting OperationTraits type
 ///
 template<class T>
-BelmannFordWizard<DefOperationTraitsBase<T> > distMap() {
+BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
-return BelmannFordWizard<DefDistMapBase<T> >(*this);
+return BellmanFordWizard<DefDistMapBase<T> >(*this);
 }
-/// \brief Sets the source node, from which the BelmannFord algorithm runs.
+/// \brief Sets the source node, from which the BellmanFord algorithm runs.
 ///
-/// Sets the source node, from which the BelmannFord 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;
 }
 };
-/// \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 BellmanFordWizard
-/// \sa BelmannFord
+/// \sa BellmanFord
 template<class _Graph, class _LengthMap>
-BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
+BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
-belmannFord(const _Graph& graph,
+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);
 }
 } //END OF NAMESPACE LEMON

changeset 1865	dcefd1d1377f
parent 1858	a5b6d941ed52
child 1875	98698b69a902