Changeset 1864:1788205e36af in lemon-0.x
- Timestamp:
- 12/19/05 10:43:13 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2436
- Location:
- lemon
- Files:
-
- 2 edited
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r1847 r1864 22 22 23 23 nobase_pkginclude_HEADERS = \ 24 bel mann_ford.h \24 bellman_ford.h \ 25 25 bezier.h \ 26 26 bfs.h \ -
lemon/bellman_ford.h
r1858 r1864 1 1 /* -*- C++ -*- 2 * lemon/bel mann_ford.h - Part of LEMON, a generic C++ optimization library2 * lemon/bellman_ford.h - Part of LEMON, a generic C++ optimization library 3 3 * 4 4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport … … 20 20 /// \ingroup flowalgs 21 21 /// \file 22 /// \brief Bel mannFord algorithm.22 /// \brief BellmanFord algorithm. 23 23 /// 24 24 … … 32 32 namespace lemon { 33 33 34 /// \brief Default OperationTraits for the Bel mannFord algorithm class.34 /// \brief Default OperationTraits for the BellmanFord algorithm class. 35 35 /// 36 36 /// It defines all computational operations and constants which are 37 /// used in the bel mann ford algorithm. The default implementation37 /// used in the bellman ford algorithm. The default implementation 38 38 /// is based on the numeric_limits class. If the numeric type does not 39 39 /// have infinity value then the maximum value is used as extremal … … 42 42 typename Value, 43 43 bool has_infinity = std::numeric_limits<Value>::has_infinity> 44 struct Bel mannFordDefaultOperationTraits {44 struct BellmanFordDefaultOperationTraits { 45 45 /// \brief Gives back the zero value of the type. 46 46 static Value zero() { … … 62 62 63 63 template <typename Value> 64 struct Bel mannFordDefaultOperationTraits<Value, false> {64 struct BellmanFordDefaultOperationTraits<Value, false> { 65 65 static Value zero() { 66 66 return static_cast<Value>(0); … … 78 78 }; 79 79 80 /// \brief Default traits class of Bel mannFord class.81 /// 82 /// Default traits class of Bel mannFord class.80 /// \brief Default traits class of BellmanFord class. 81 /// 82 /// Default traits class of BellmanFord class. 83 83 /// \param _Graph Graph type. 84 84 /// \param _LegthMap Type of length map. 85 85 template<class _Graph, class _LengthMap> 86 struct Bel mannFordDefaultTraits {86 struct BellmanFordDefaultTraits { 87 87 /// The graph type the algorithm runs on. 88 88 typedef _Graph Graph; … … 97 97 typedef typename _LengthMap::Value Value; 98 98 99 /// \brief Operation traits for bel mann-ford algorithm.99 /// \brief Operation traits for bellman-ford algorithm. 100 100 /// 101 101 /// It defines the infinity type on the given Value type 102 102 /// and the used operation. 103 /// \see Bel mannFordDefaultOperationTraits104 typedef Bel mannFordDefaultOperationTraits<Value> OperationTraits;103 /// \see BellmanFordDefaultOperationTraits 104 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 105 105 106 106 /// \brief The type of the map that stores the last edges of the … … 140 140 }; 141 141 142 /// \brief %Bel mannFord algorithm class.142 /// \brief %BellmanFord algorithm class. 143 143 /// 144 144 /// \ingroup flowalgs 145 /// This class provides an efficient implementation of \c Bel mann-Ford145 /// This class provides an efficient implementation of \c Bellman-Ford 146 146 /// algorithm. The edge lengths are passed to the algorithm using a 147 147 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 148 148 /// kind of length. 149 149 /// 150 /// The Bel mann-Ford algorithm solves the shortest path from one node150 /// The Bellman-Ford algorithm solves the shortest path from one node 151 151 /// problem when the edges can have negative length but the graph should 152 152 /// 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 162 162 /// is \ref ListGraph. The value of _Graph is not used directly by 163 /// Bel mannFord, it is only passed to \ref BelmannFordDefaultTraits.163 /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. 164 164 /// \param _LengthMap This read-only EdgeMap determines the lengths of the 165 165 /// edges. The default map type is \ref concept::StaticGraph::EdgeMap 166 166 /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly 167 /// by Bel mannFord, it is only passed to \ref BelmannFordDefaultTraits.167 /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits. 168 168 /// \param _Traits Traits class to set various data types used by the 169 /// algorithm. The default traits class is \ref Bel mannFordDefaultTraits170 /// "Bel mannFordDefaultTraits<_Graph,_LengthMap>". See \ref171 /// Bel mannFordDefaultTraits for the documentation of a BelmannFord traits169 /// algorithm. The default traits class is \ref BellmanFordDefaultTraits 170 /// "BellmanFordDefaultTraits<_Graph,_LengthMap>". See \ref 171 /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits 172 172 /// class. 173 173 /// … … 179 179 template <typename _Graph=ListGraph, 180 180 typename _LengthMap=typename _Graph::template EdgeMap<int>, 181 typename _Traits=Bel mannFordDefaultTraits<_Graph,_LengthMap> >181 typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> > 182 182 #endif 183 class Bel mannFord {183 class BellmanFord { 184 184 public: 185 185 … … 192 192 public: 193 193 virtual const char* exceptionName() const { 194 return "lemon::Bel mannFord::UninitializedParameter";194 return "lemon::BellmanFord::UninitializedParameter"; 195 195 } 196 196 }; … … 250 250 public : 251 251 252 typedef Bel mannFord Create;252 typedef BellmanFord Create; 253 253 254 254 /// \name Named template parameters … … 270 270 template <class T> 271 271 struct DefPredMap 272 : public Bel mannFord< Graph, LengthMap, DefPredMapTraits<T> > {273 typedef Bel mannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;272 : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > { 273 typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create; 274 274 }; 275 275 … … 289 289 template <class T> 290 290 struct DefDistMap 291 : public Bel mannFord< Graph, LengthMap, DefDistMapTraits<T> > {292 typedef Bel mannFord< Graph, LengthMap, DefDistMapTraits<T> > Create;291 : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > { 292 typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create; 293 293 }; 294 294 … … 305 305 template <class T> 306 306 struct DefOperationTraits 307 : public Bel mannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {308 typedef Bel mannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >307 : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > { 308 typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > 309 309 Create; 310 310 }; … … 314 314 protected: 315 315 316 Bel mannFord() {}316 BellmanFord() {} 317 317 318 318 public: … … 322 322 /// \param _graph the graph the algorithm will run on. 323 323 /// \param _length the length map used by the algorithm. 324 Bel mannFord(const Graph& _graph, const LengthMap& _length) :324 BellmanFord(const Graph& _graph, const LengthMap& _length) : 325 325 graph(&_graph), length(&_length), 326 326 _pred(0), local_pred(false), … … 328 328 329 329 ///Destructor. 330 ~Bel mannFord() {330 ~BellmanFord() { 331 331 if(local_pred) delete _pred; 332 332 if(local_dist) delete _dist; … … 338 338 /// Sets the length map. 339 339 /// \return \c (*this) 340 Bel mannFord &lengthMap(const LengthMap &m) {340 BellmanFord &lengthMap(const LengthMap &m) { 341 341 length = &m; 342 342 return *this; … … 350 350 /// automatically allocated map, of course. 351 351 /// \return \c (*this) 352 Bel mannFord &predMap(PredMap &m) {352 BellmanFord &predMap(PredMap &m) { 353 353 if(local_pred) { 354 354 delete _pred; … … 366 366 /// automatically allocated map, of course. 367 367 /// \return \c (*this) 368 Bel mannFord &distMap(DistMap &m) {368 BellmanFord &distMap(DistMap &m) { 369 369 if(local_dist) { 370 370 delete _dist; … … 417 417 } 418 418 419 /// \brief Executes one round from the bel mann ford algorithm.419 /// \brief Executes one round from the bellman ford algorithm. 420 420 /// 421 421 /// If the algoritm calculated the distances in the previous round … … 451 451 } 452 452 453 /// \brief Executes one weak round from the bel mann ford algorithm.453 /// \brief Executes one weak round from the bellman ford algorithm. 454 454 /// 455 455 /// If the algorithm calculated the distances in the … … 489 489 /// with addSource() before using this function. 490 490 /// 491 /// This method runs the %Bel mannFord algorithm from the root node(s)491 /// This method runs the %BellmanFord algorithm from the root node(s) 492 492 /// in order to compute the shortest path to each node. The algorithm 493 493 /// computes … … 507 507 /// a negative cycles in the graph it gives back false. 508 508 /// 509 /// This method runs the %Bel mannFord algorithm from the root node(s)509 /// This method runs the %BellmanFord algorithm from the root node(s) 510 510 /// in order to compute the shortest path to each node. The algorithm 511 511 /// computes … … 525 525 /// with addSource() before using this function. 526 526 /// 527 /// This method runs the %Bel mannFord algorithm from the root node(s)527 /// This method runs the %BellmanFord algorithm from the root node(s) 528 528 /// in order to compute the shortest path with at most \c length edge 529 529 /// long paths to each node. The algorithm computes … … 536 536 } 537 537 538 /// \brief Runs %Bel mannFord algorithm from node \c s.538 /// \brief Runs %BellmanFord algorithm from node \c s. 539 539 /// 540 /// This method runs the %Bel mannFord algorithm from a root node \c s540 /// This method runs the %BellmanFord algorithm from a root node \c s 541 541 /// in order to compute the shortest path to each node. The algorithm 542 542 /// computes … … 556 556 } 557 557 558 /// \brief Runs %Bel mannFord algorithm with limited path length558 /// \brief Runs %BellmanFord algorithm with limited path length 559 559 /// from node \c s. 560 560 /// 561 /// This method runs the %Bel mannFord algorithm from a root node \c s561 /// This method runs the %BellmanFord algorithm from a root node \c s 562 562 /// in order to compute the shortest path with at most \c len edges 563 563 /// to each node. The algorithm computes … … 580 580 581 581 /// \name Query Functions 582 /// The result of the %Bel mannFord algorithm can be obtained using these582 /// The result of the %BellmanFord algorithm can be obtained using these 583 583 /// functions.\n 584 584 /// Before the use of these functions, … … 663 663 }; 664 664 665 /// \brief Default traits class of Bel mannFord function.666 /// 667 /// Default traits class of Bel mannFord function.665 /// \brief Default traits class of BellmanFord function. 666 /// 667 /// Default traits class of BellmanFord function. 668 668 /// \param _Graph Graph type. 669 669 /// \param _LengthMap Type of length map. 670 670 template <typename _Graph, typename _LengthMap> 671 struct Bel mannFordWizardDefaultTraits {671 struct BellmanFordWizardDefaultTraits { 672 672 /// \brief The graph type the algorithm runs on. 673 673 typedef _Graph Graph; … … 682 682 typedef typename _LengthMap::Value Value; 683 683 684 /// \brief Operation traits for bel mann-ford algorithm.684 /// \brief Operation traits for bellman-ford algorithm. 685 685 /// 686 686 /// It defines the infinity type on the given Value type 687 687 /// and the used operation. 688 /// \see Bel mannFordDefaultOperationTraits689 typedef Bel mannFordDefaultOperationTraits<Value> OperationTraits;688 /// \see BellmanFordDefaultOperationTraits 689 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 690 690 691 691 /// \brief The type of the map that stores the last … … 716 716 }; 717 717 718 /// \brief Default traits used by \ref Bel mannFordWizard719 /// 720 /// To make it easier to use Bel mannFord algorithm718 /// \brief Default traits used by \ref BellmanFordWizard 719 /// 720 /// To make it easier to use BellmanFord algorithm 721 721 /// we have created a wizard class. 722 /// This \ref Bel mannFordWizard class needs default traits,723 /// as well as the \ref Bel mannFord class.724 /// The \ref Bel mannFordWizardBase is a class to be the default traits of the725 /// \ref Bel mannFordWizard class.722 /// This \ref BellmanFordWizard class needs default traits, 723 /// as well as the \ref BellmanFord class. 724 /// The \ref BellmanFordWizardBase is a class to be the default traits of the 725 /// \ref BellmanFordWizard class. 726 726 /// \todo More named parameters are required... 727 727 template<class _Graph,class _LengthMap> 728 class Bel mannFordWizardBase729 : public Bel mannFordWizardDefaultTraits<_Graph,_LengthMap> {730 731 typedef Bel mannFordWizardDefaultTraits<_Graph,_LengthMap> Base;728 class BellmanFordWizardBase 729 : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> { 730 731 typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base; 732 732 protected: 733 733 /// Type of the nodes in the graph. … … 750 750 /// This constructor does not require parameters, therefore it initiates 751 751 /// all of the attributes to default values (0, INVALID). 752 Bel mannFordWizardBase() : _graph(0), _length(0), _pred(0),752 BellmanFordWizardBase() : _graph(0), _length(0), _pred(0), 753 753 _dist(0), _source(INVALID) {} 754 754 … … 761 761 /// \param length is the initial value of \ref _length 762 762 /// \param source is the initial value of \ref _source 763 Bel mannFordWizardBase(const _Graph& graph,763 BellmanFordWizardBase(const _Graph& graph, 764 764 const _LengthMap& length, 765 765 Node source = INVALID) : … … 769 769 }; 770 770 771 /// A class to make the usage of Bel mannFord algorithm easier772 773 /// This class is created to make it easier to use Bel mannFord algorithm.774 /// It uses the functions and features of the plain \ref Bel mannFord,771 /// A class to make the usage of BellmanFord algorithm easier 772 773 /// This class is created to make it easier to use BellmanFord algorithm. 774 /// It uses the functions and features of the plain \ref BellmanFord, 775 775 /// but it is much simpler to use it. 776 776 /// … … 778 778 /// in the traits class is based on functions that returns the new class 779 779 /// and not on templatable built-in classes. 780 /// When using the plain \ref Bel mannFord780 /// When using the plain \ref BellmanFord 781 781 /// the new class with the modified type comes from 782 782 /// the original class by using the :: 783 /// operator. In the case of \ref Bel mannFordWizard only783 /// operator. In the case of \ref BellmanFordWizard only 784 784 /// a function have to be called and it will 785 785 /// return the needed class. 786 786 /// 787 787 /// It does not have own \ref run method. When its \ref run method is called 788 /// it initiates a plain \ref Bel mannFord class, and calls the \ref789 /// Bel mannFord::run method of it.788 /// it initiates a plain \ref BellmanFord class, and calls the \ref 789 /// BellmanFord::run method of it. 790 790 template<class _Traits> 791 class Bel mannFordWizard : public _Traits {791 class BellmanFordWizard : public _Traits { 792 792 typedef _Traits Base; 793 793 … … 815 815 public: 816 816 /// Constructor. 817 Bel mannFordWizard() : _Traits() {}817 BellmanFordWizard() : _Traits() {} 818 818 819 819 /// \brief Constructor that requires parameters. … … 821 821 /// Constructor that requires parameters. 822 822 /// These parameters will be the default values for the traits class. 823 Bel mannFordWizard(const Graph& graph, const LengthMap& length,823 BellmanFordWizard(const Graph& graph, const LengthMap& length, 824 824 Node source = INVALID) 825 825 : _Traits(graph, length, source) {} 826 826 827 827 /// \brief Copy constructor 828 Bel mannFordWizard(const _Traits &b) : _Traits(b) {}829 830 ~Bel mannFordWizard() {}831 832 /// \brief Runs Bel mannFord algorithm from a given node.828 BellmanFordWizard(const _Traits &b) : _Traits(b) {} 829 830 ~BellmanFordWizard() {} 831 832 /// \brief Runs BellmanFord algorithm from a given node. 833 833 /// 834 /// Runs Bel mannFord algorithm from a given node.834 /// Runs BellmanFord algorithm from a given node. 835 835 /// The node can be given by the \ref source function. 836 836 void run() { 837 837 if(Base::_source == INVALID) throw UninitializedParameter(); 838 Bel mannFord<Graph,LengthMap,_Traits>838 BellmanFord<Graph,LengthMap,_Traits> 839 839 bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length); 840 840 if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred); … … 843 843 } 844 844 845 /// \brief Runs Bel mannFord algorithm from the given node.846 /// 847 /// Runs Bel mannFord algorithm from the given node.845 /// \brief Runs BellmanFord algorithm from the given node. 846 /// 847 /// Runs BellmanFord algorithm from the given node. 848 848 /// \param source is the given source. 849 849 void run(Node source) { … … 866 866 /// 867 867 template<class T> 868 Bel mannFordWizard<DefPredMapBase<T> > predMap(const T &t)868 BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 869 869 { 870 870 Base::_pred=(void *)&t; 871 return Bel mannFordWizard<DefPredMapBase<T> >(*this);871 return BellmanFordWizard<DefPredMapBase<T> >(*this); 872 872 } 873 873 … … 886 886 /// 887 887 template<class T> 888 Bel mannFordWizard<DefDistMapBase<T> > distMap(const T &t) {888 BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) { 889 889 Base::_dist=(void *)&t; 890 return Bel mannFordWizard<DefDistMapBase<T> >(*this);890 return BellmanFordWizard<DefDistMapBase<T> >(*this); 891 891 } 892 892 … … 904 904 /// 905 905 template<class T> 906 Bel mannFordWizard<DefOperationTraitsBase<T> > distMap() {907 return Bel mannFordWizard<DefDistMapBase<T> >(*this);908 } 909 910 /// \brief Sets the source node, from which the Bel mannFord algorithm runs.911 /// 912 /// Sets the source node, from which the Bel mannFord algorithm runs.906 BellmanFordWizard<DefOperationTraitsBase<T> > distMap() { 907 return BellmanFordWizard<DefDistMapBase<T> >(*this); 908 } 909 910 /// \brief Sets the source node, from which the BellmanFord algorithm runs. 911 /// 912 /// Sets the source node, from which the BellmanFord algorithm runs. 913 913 /// \param source is the source node. 914 Bel mannFordWizard<_Traits>& source(Node source) {914 BellmanFordWizard<_Traits>& source(Node source) { 915 915 Base::_source = source; 916 916 return *this; … … 919 919 }; 920 920 921 /// \brief Function type interface for Bel mannFord algorithm.921 /// \brief Function type interface for BellmanFord algorithm. 922 922 /// 923 923 /// \ingroup flowalgs 924 /// Function type interface for Bel mannFord algorithm.924 /// Function type interface for BellmanFord algorithm. 925 925 /// 926 926 /// This function also has several \ref named-templ-func-param 927 927 /// "named parameters", they are declared as the members of class 928 /// \ref Bel mannFordWizard.928 /// \ref BellmanFordWizard. 929 929 /// The following 930 930 /// example shows how to use these parameters. 931 931 /// \code 932 /// bel mannford(g,length,source).predMap(preds).run();932 /// bellmanford(g,length,source).predMap(preds).run(); 933 933 /// \endcode 934 /// \warning Don't forget to put the \ref Bel mannFordWizard::run() "run()"934 /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()" 935 935 /// to the end of the parameter list. 936 /// \sa Bel mannFordWizard937 /// \sa Bel mannFord936 /// \sa BellmanFordWizard 937 /// \sa BellmanFord 938 938 template<class _Graph, class _LengthMap> 939 Bel mannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >940 bel mannFord(const _Graph& graph,939 BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> > 940 bellmanFord(const _Graph& graph, 941 941 const _LengthMap& length, 942 942 typename _Graph::Node source = INVALID) { 943 return Bel mannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >943 return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> > 944 944 (graph, length, source); 945 945 } -
lemon/johnson.h
r1784 r1864 26 26 #include <lemon/graph_utils.h> 27 27 #include <lemon/dijkstra.h> 28 #include <lemon/bel mann_ford.h>28 #include <lemon/bellman_ford.h> 29 29 #include <lemon/invalid.h> 30 30 #include <lemon/error.h> … … 101 101 typedef typename _LengthMap::Value Value; 102 102 103 /// \brief Operation traits for bel mann-ford algorithm.103 /// \brief Operation traits for bellman-ford algorithm. 104 104 /// 105 105 /// It defines the infinity type on the given Value type … … 545 545 void start() { 546 546 547 typedef typename Bel mannFord<Graph, LengthMap>::547 typedef typename BellmanFord<Graph, LengthMap>:: 548 548 template DefOperationTraits<OperationTraits>:: 549 549 template DefPredMap<NullMap<Node, Edge> >:: 550 Create Bel mannFordType;550 Create BellmanFordType; 551 551 552 Bel mannFordType belmannford(*graph, *length);552 BellmanFordType bellmanford(*graph, *length); 553 553 554 554 NullMap<Node, Edge> predMap; 555 555 556 bel mannford.predMap(predMap);556 bellmanford.predMap(predMap); 557 557 558 bel mannford.init(OperationTraits::zero());559 bel mannford.start();560 561 shiftedRun(bel mannford.distMap());558 bellmanford.init(OperationTraits::zero()); 559 bellmanford.start(); 560 561 shiftedRun(bellmanford.distMap()); 562 562 } 563 563 … … 572 572 bool checkedStart() { 573 573 574 typedef typename Bel mannFord<Graph, LengthMap>::574 typedef typename BellmanFord<Graph, LengthMap>:: 575 575 template DefOperationTraits<OperationTraits>:: 576 576 template DefPredMap<NullMap<Node, Edge> >:: 577 Create Bel mannFordType;578 579 Bel mannFordType belmannford(*graph, *length);577 Create BellmanFordType; 578 579 BellmanFordType bellmanford(*graph, *length); 580 580 581 581 NullMap<Node, Edge> predMap; 582 582 583 bel mannford.predMap(predMap);583 bellmanford.predMap(predMap); 584 584 585 bel mannford.init(OperationTraits::zero());586 if (!bel mannford.checkedStart()) return false;587 588 shiftedRun(bel mannford.distMap());585 bellmanford.init(OperationTraits::zero()); 586 if (!bellmanford.checkedStart()) return false; 587 588 shiftedRun(bellmanford.distMap()); 589 589 return true; 590 590 }
Note: See TracChangeset
for help on using the changeset viewer.