1.1 --- a/lemon/belmann_ford.h Wed Oct 05 16:45:37 2005 +0000
1.2 +++ b/lemon/belmann_ford.h Thu Oct 06 09:37:53 2005 +0000
1.3 @@ -167,9 +167,13 @@
1.4 ///
1.5 /// \author Balazs Dezso
1.6
1.7 +#ifdef DOXYGEN
1.8 + template <typename _Graph, typename _LengthMap, typename _Traits>
1.9 +#else
1.10 template <typename _Graph=ListGraph,
1.11 typename _LengthMap=typename _Graph::template EdgeMap<int>,
1.12 typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> >
1.13 +#endif
1.14 class BelmannFord {
1.15 public:
1.16
1.17 @@ -233,6 +237,8 @@
1.18
1.19 public :
1.20
1.21 + typedef BelmannFord Create;
1.22 +
1.23 /// \name Named template parameters
1.24
1.25 ///@{
1.26 @@ -240,7 +246,7 @@
1.27 template <class T>
1.28 struct DefPredMapTraits : public Traits {
1.29 typedef T PredMap;
1.30 - static PredMap *createPredMap(const Graph& graph) {
1.31 + static PredMap *createPredMap(const Graph&) {
1.32 throw UninitializedParameter();
1.33 }
1.34 };
1.35 @@ -250,8 +256,9 @@
1.36 /// \ref named-templ-param "Named parameter" for setting PredMap type
1.37 ///
1.38 template <class T>
1.39 - class DefPredMap
1.40 - : public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > {};
1.41 + struct DefPredMap {
1.42 + typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
1.43 + };
1.44
1.45 template <class T>
1.46 struct DefDistMapTraits : public Traits {
1.47 @@ -267,8 +274,10 @@
1.48 /// \ref named-templ-param "Named parameter" for setting DistMap type
1.49 ///
1.50 template <class T>
1.51 - class DefDistMap
1.52 - : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {};
1.53 + struct DefDistMap
1.54 + : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {
1.55 + typedef BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
1.56 + };
1.57
1.58 template <class T>
1.59 struct DefOperationTraitsTraits : public Traits {
1.60 @@ -278,17 +287,21 @@
1.61 /// \brief \ref named-templ-param "Named parameter" for setting
1.62 /// OperationTraits type
1.63 ///
1.64 - /// \ref named-templ-param "Named parameter" for setting PredMap type
1.65 + /// \ref named-templ-param "Named parameter" for setting OperationTraits
1.66 + /// type
1.67 template <class T>
1.68 - class DefOperationTraits
1.69 + struct DefOperationTraits
1.70 : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
1.71 - public:
1.72 typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
1.73 - BelmannFord;
1.74 + Create;
1.75 };
1.76
1.77 ///@}
1.78
1.79 + protected:
1.80 +
1.81 + BelmannFord() {}
1.82 +
1.83 public:
1.84
1.85 /// \brief Constructor.
1.86 @@ -362,11 +375,11 @@
1.87 /// \brief Initializes the internal data structures.
1.88 ///
1.89 /// Initializes the internal data structures.
1.90 - void init() {
1.91 + void init(const Value value = OperationTraits::infinity()) {
1.92 create_maps();
1.93 for (NodeIt it(*graph); it != INVALID; ++it) {
1.94 _pred->set(it, INVALID);
1.95 - _dist->set(it, OperationTraits::infinity());
1.96 + _dist->set(it, value);
1.97 }
1.98 }
1.99
1.100 @@ -740,6 +753,23 @@
1.101 Base::_dist=(void *)&t;
1.102 return BelmannFordWizard<DefDistMapBase<T> >(*this);
1.103 }
1.104 +
1.105 + template<class T>
1.106 + struct DefOperationTraitsBase : public Base {
1.107 + typedef T OperationTraits;
1.108 + DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1.109 + };
1.110 +
1.111 + ///\brief \ref named-templ-param "Named parameter"
1.112 + ///function for setting OperationTraits type
1.113 + ///
1.114 + /// \ref named-templ-param "Named parameter"
1.115 + ///function for setting OperationTraits type
1.116 + ///
1.117 + template<class T>
1.118 + BelmannFordWizard<DefOperationTraitsBase<T> > distMap() {
1.119 + return BelmannFordWizard<DefDistMapBase<T> >(*this);
1.120 + }
1.121
1.122 /// \brief Sets the source node, from which the BelmannFord algorithm runs.
1.123 ///
2.1 --- a/lemon/bfs.h Wed Oct 05 16:45:37 2005 +0000
2.2 +++ b/lemon/bfs.h Thu Oct 06 09:37:53 2005 +0000
2.3 @@ -214,9 +214,15 @@
2.4 _processed = Traits::createProcessedMap(*G);
2.5 }
2.6 }
2.7 +
2.8 + protected:
2.9
2.10 - public :
2.11 + Bfs() {}
2.12 +
2.13 + public:
2.14
2.15 + typedef Bfs Create;
2.16 +
2.17 ///\name Named template parameters
2.18
2.19 ///@{
3.1 --- a/lemon/dfs.h Wed Oct 05 16:45:37 2005 +0000
3.2 +++ b/lemon/dfs.h Thu Oct 06 09:37:53 2005 +0000
3.3 @@ -214,8 +214,12 @@
3.4 _processed = Traits::createProcessedMap(*G);
3.5 }
3.6 }
3.7 +
3.8 + protected:
3.9 +
3.10 + Dfs() {}
3.11
3.12 - public :
3.13 + public:
3.14
3.15 typedef Dfs Create;
3.16
4.1 --- a/lemon/dijkstra.h Wed Oct 05 16:45:37 2005 +0000
4.2 +++ b/lemon/dijkstra.h Thu Oct 06 09:37:53 2005 +0000
4.3 @@ -236,6 +236,8 @@
4.4 }
4.5
4.6 public :
4.7 +
4.8 + typedef Dijkstra Create;
4.9
4.10 ///\name Named template parameters
4.11
4.12 @@ -320,6 +322,10 @@
4.13 private:
4.14 typename Graph::template NodeMap<int> _heap_map;
4.15 Heap _heap;
4.16 + protected:
4.17 +
4.18 + Dijkstra() {}
4.19 +
4.20 public:
4.21
4.22 ///Constructor.
5.1 --- a/lemon/floyd_warshall.h Wed Oct 05 16:45:37 2005 +0000
5.2 +++ b/lemon/floyd_warshall.h Thu Oct 06 09:37:53 2005 +0000
5.3 @@ -170,10 +170,13 @@
5.4 ///
5.5 /// \author Balazs Dezso
5.6
5.7 -
5.8 +#ifdef DOXYGEN
5.9 + template <typename _Graph, typename _LengthMap typename _Traits >
5.10 +#else
5.11 template <typename _Graph=ListGraph,
5.12 typename _LengthMap=typename _Graph::template EdgeMap<int>,
5.13 typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
5.14 +#endif
5.15 class FloydWarshall {
5.16 public:
5.17
5.18 @@ -256,8 +259,10 @@
5.19 /// \ref named-templ-param "Named parameter" for setting PredMap type
5.20 ///
5.21 template <class T>
5.22 - class DefPredMap
5.23 - : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {};
5.24 + struct DefPredMap
5.25 + : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {
5.26 + typedef FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > Create;
5.27 + };
5.28
5.29 template <class T>
5.30 struct DefDistMapTraits : public Traits {
5.31 @@ -272,8 +277,10 @@
5.32 /// \ref named-templ-param "Named parameter" for setting DistMap type
5.33 ///
5.34 template <class T>
5.35 - class DefDistMap
5.36 - : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {};
5.37 + struct DefDistMap
5.38 + : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {
5.39 + typedef FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > Create;
5.40 + };
5.41
5.42 template <class T>
5.43 struct DefOperationTraitsTraits : public Traits {
5.44 @@ -285,13 +292,21 @@
5.45 ///
5.46 /// \ref named-templ-param "Named parameter" for setting PredMap type
5.47 template <class T>
5.48 - class DefOperationTraits
5.49 + struct DefOperationTraits
5.50 : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
5.51 + typedef FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> >
5.52 + Create;
5.53 };
5.54
5.55 ///@}
5.56
5.57 + protected:
5.58 +
5.59 + FloydWarshall() {}
5.60 +
5.61 public:
5.62 +
5.63 + typedef FloydWarshall Create;
5.64
5.65 /// \brief Constructor.
5.66 ///
6.1 --- a/lemon/johnson.h Wed Oct 05 16:45:37 2005 +0000
6.2 +++ b/lemon/johnson.h Thu Oct 06 09:37:53 2005 +0000
6.3 @@ -24,7 +24,6 @@
6.4
6.5 #include <lemon/list_graph.h>
6.6 #include <lemon/graph_utils.h>
6.7 -#include <lemon/dfs.h>
6.8 #include <lemon/dijkstra.h>
6.9 #include <lemon/belmann_ford.h>
6.10 #include <lemon/invalid.h>
6.11 @@ -172,9 +171,13 @@
6.12 ///
6.13 /// \author Balazs Dezso
6.14
6.15 +#ifdef DOXYGEN
6.16 + template <typename _Graph, typename _LengthMap, typename _Traits>
6.17 +#else
6.18 template <typename _Graph=ListGraph,
6.19 typename _LengthMap=typename _Graph::template EdgeMap<int>,
6.20 typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> >
6.21 +#endif
6.22 class Johnson {
6.23 public:
6.24
6.25 @@ -257,8 +260,10 @@
6.26 /// \ref named-templ-param "Named parameter" for setting PredMap type
6.27 ///
6.28 template <class T>
6.29 - class DefPredMap
6.30 - : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {};
6.31 + struct DefPredMap
6.32 + : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {
6.33 + typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create;
6.34 + };
6.35
6.36 template <class T>
6.37 struct DefDistMapTraits : public Traits {
6.38 @@ -273,8 +278,10 @@
6.39 /// \ref named-templ-param "Named parameter" for setting DistMap type
6.40 ///
6.41 template <class T>
6.42 - class DefDistMap
6.43 - : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {};
6.44 + struct DefDistMap
6.45 + : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {
6.46 + typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create;
6.47 + };
6.48
6.49 template <class T>
6.50 struct DefOperationTraitsTraits : public Traits {
6.51 @@ -284,13 +291,20 @@
6.52 /// \brief \ref named-templ-param "Named parameter" for setting
6.53 /// OperationTraits type
6.54 ///
6.55 - /// \ref named-templ-param "Named parameter" for setting PredMap type
6.56 + /// \ref named-templ-param "Named parameter" for setting
6.57 + /// OperationTraits type
6.58 template <class T>
6.59 - class DefOperationTraits
6.60 - : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {};
6.61 + struct DefOperationTraits
6.62 + : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
6.63 + typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
6.64 + };
6.65
6.66 ///@}
6.67
6.68 + protected:
6.69 +
6.70 + Johnson() {}
6.71 +
6.72 public:
6.73
6.74 /// \brief Constructor.
6.75 @@ -374,40 +388,23 @@
6.76 /// - The shortest path tree for each node.
6.77 /// - The distance between each node pairs.
6.78 void start() {
6.79 - typename BelmannFord<Graph, LengthMap>::
6.80 + typedef typename BelmannFord<Graph, LengthMap>::
6.81 template DefOperationTraits<OperationTraits>::
6.82 - BelmannFord belmannford(*graph, *length);
6.83 + template DefPredMap<NullMap<Node, Edge> >::
6.84 + Create BelmannFordType;
6.85 +
6.86 + BelmannFordType belmannford(*graph, *length);
6.87 +
6.88 + NullMap<Node, Edge> predMap;
6.89 +
6.90 + belmannford.predMap(predMap);
6.91
6.92 - belmannford.init();
6.93 -
6.94 - typename Graph::template NodeMap<bool> initial(*graph, false);
6.95 -
6.96 - {
6.97 - Dfs<Graph> dfs(*graph);
6.98 -
6.99 - dfs.init();
6.100 - for (NodeIt it(*graph); it != INVALID; ++it) {
6.101 - if (!dfs.reached(it)) {
6.102 - dfs.addSource(it);
6.103 - while (!dfs.emptyQueue()) {
6.104 - Edge edge = dfs.processNextEdge();
6.105 - initial.set(graph->target(edge), false);
6.106 - }
6.107 - initial.set(it, true);
6.108 - }
6.109 - }
6.110 - for (NodeIt it(*graph); it != INVALID; ++it) {
6.111 - if (initial[it]) {
6.112 - belmannford.addSource(it);
6.113 - }
6.114 - }
6.115 - }
6.116 -
6.117 + belmannford.init(OperationTraits::zero());
6.118 belmannford.start();
6.119
6.120 for (NodeIt it(*graph); it != INVALID; ++it) {
6.121 typedef PotentialDifferenceMap<Graph,
6.122 - typename BelmannFord<Graph, LengthMap>::DistMap> PotDiffMap;
6.123 + typename BelmannFordType::DistMap> PotDiffMap;
6.124 PotDiffMap potdiff(*graph, belmannford.distMap());
6.125 typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
6.126 ShiftLengthMap shiftlen(*length, potdiff);