1.1 --- a/src/work/alpar/dijkstra.h Thu Feb 03 19:31:37 2005 +0000
1.2 +++ b/src/work/alpar/dijkstra.h Fri Feb 04 15:32:11 2005 +0000
1.3 @@ -72,7 +72,8 @@
1.4 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
1.5 ///Instantiates a PredMap.
1.6
1.7 - ///\todo Please document...
1.8 + ///This function instantiates a \ref PredMap.
1.9 + ///\param G is the graph, to which we would like to define the PredMap.
1.10 ///\todo The graph alone may be insufficient for the initialization
1.11 static PredMap *createPredMap(const GR &G)
1.12 {
1.13 @@ -86,8 +87,8 @@
1.14 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
1.15 ///Instantiates a PredNodeMap.
1.16
1.17 - ///\todo Please document...
1.18 - ///
1.19 + ///This function instantiates a \ref PredNodeMap.
1.20 + ///\param G is the graph, to which we would like to define the \ref PredNodeMap
1.21 static PredNodeMap *createPredNodeMap(const GR &G)
1.22 {
1.23 return new PredNodeMap(G);
1.24 @@ -102,8 +103,8 @@
1.25 typedef NullMap<typename Graph::Node,bool> ReachedMap;
1.26 ///Instantiates a ReachedMap.
1.27
1.28 - ///\todo Please document...
1.29 - ///
1.30 + ///This function instantiates a \ref ReachedMap.
1.31 + ///\param G is the graph, to which we would like to define the \ref ReachedMap
1.32 static ReachedMap *createReachedMap(const GR &G)
1.33 {
1.34 return new ReachedMap();
1.35 @@ -115,8 +116,8 @@
1.36 typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
1.37 ///Instantiates a DistMap.
1.38
1.39 - ///\todo Please document...
1.40 - ///
1.41 + ///This function instantiates a \ref DistMap.
1.42 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.43 static DistMap *createDistMap(const GR &G)
1.44 {
1.45 return new DistMap(G);
1.46 @@ -506,6 +507,12 @@
1.47
1.48 };
1.49
1.50 + /// Default traits used by \ref DijkstraWizard
1.51 +
1.52 + /// To make it easier to use Dijkstra algorithm we created a wizard class.
1.53 + /// This \ref DijkstraWizard class also needs default traits.
1.54 + /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.55 + /// \ref DijkstraWizard class.
1.56 template<class GR,class LM>
1.57 class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
1.58 {
1.59 @@ -525,28 +532,52 @@
1.60 ///Pointer to the source node.
1.61 void *_source;
1.62
1.63 + /// Type of the nodes in the graph.
1.64 typedef typename Base::Graph::Node Node;
1.65
1.66 public:
1.67 + /// Constructor.
1.68 +
1.69 + /// This constructor does not require parameters, therefore it initiates
1.70 + /// all of the attributes to default values (0, INVALID).
1.71 DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
1.72 _dist(0), _source(INVALID) {}
1.73
1.74 + /// Constructor.
1.75 +
1.76 + /// This constructor requires some parameters, listed in the parameters list.
1.77 + /// Others are initiated to 0.
1.78 + /// \param g is the initial value of \ref _g
1.79 + /// \param l is the initial value of \ref _length
1.80 + /// \param s is the initial value of \ref _source
1.81 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1.82 _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
1.83 _dist(0), _source((void *)&s) {}
1.84
1.85 };
1.86
1.87 - ///\e
1.88 + /// A class to make easier the usage of Dijkstra algorithm
1.89
1.90 - ///\e
1.91 + /// This class is created to make it easier to use Dijkstra algorithm.
1.92 + /// It uses the functions and features of the plain \ref Dijkstra,
1.93 + /// but it is much more simple to use it.
1.94 ///
1.95 + /// Simplicity means that the way to change the types defined
1.96 + /// in the traits class is based on functions that returns the new class
1.97 + /// and not on templatable built-in classes. When using the plain \Dijkstra
1.98 + /// the new class with the modified type comes from the original by using the ::
1.99 + /// operator. In this case only a function have to be called and it will
1.100 + /// return the needed class.
1.101 + ///
1.102 + /// It does not have own \ref run method. When its \ref run method is called
1.103 + /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
1.104 + /// method of it.
1.105 template<class TR>
1.106 class DijkstraWizard : public TR
1.107 {
1.108 typedef TR Base;
1.109
1.110 - //The type of the underlying graph.
1.111 + ///The type of the underlying graph.
1.112 typedef typename TR::Graph Graph;
1.113 //\e
1.114 typedef typename Graph::Node Node;
1.115 @@ -557,32 +588,39 @@
1.116 //\e
1.117 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.118
1.119 - //The type of the map that stores the edge lengths.
1.120 + ///The type of the map that stores the edge lengths.
1.121 typedef typename TR::LengthMap LengthMap;
1.122 - //The type of the length of the edges.
1.123 + ///The type of the length of the edges.
1.124 typedef typename LengthMap::Value Value;
1.125 - //\brief The type of the map that stores the last
1.126 - //edges of the shortest paths.
1.127 + ///\brief The type of the map that stores the last
1.128 + ///edges of the shortest paths.
1.129 typedef typename TR::PredMap PredMap;
1.130 - //\brief The type of the map that stores the last but one
1.131 - //nodes of the shortest paths.
1.132 + ///\brief The type of the map that stores the last but one
1.133 + ///nodes of the shortest paths.
1.134 typedef typename TR::PredNodeMap PredNodeMap;
1.135 - //The type of the map that stores the dists of the nodes.
1.136 + ///The type of the map that stores the dists of the nodes.
1.137 typedef typename TR::DistMap DistMap;
1.138
1.139 - //The heap type used by the dijkstra algorithm.
1.140 + ///The heap type used by the dijkstra algorithm.
1.141 typedef typename TR::Heap Heap;
1.142 public:
1.143 + /// Constructor.
1.144 DijkstraWizard() : TR() {}
1.145
1.146 + /// Constructor that requires parameters.
1.147 + /// These parameters will be the default values for the traits class.
1.148 DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
1.149 TR(g,l,s) {}
1.150
1.151 + ///Copy constructor
1.152 DijkstraWizard(const TR &b) : TR(b) {}
1.153
1.154 ~DijkstraWizard() {}
1.155
1.156 - ///\e
1.157 + ///Runs Dijkstra algorithm from a given node.
1.158 +
1.159 + ///Runs Dijkstra algorithm from a given node.
1.160 + ///The node can be given by the \ref source function.
1.161 void run()
1.162 {
1.163 if(_source==0) throw UninitializedData();
1.164 @@ -593,7 +631,10 @@
1.165 Dij.run(*(Node*)_source);
1.166 }
1.167
1.168 - ///\e
1.169 + ///Runs Dijkstra algorithm from a given node.
1.170 +
1.171 + ///Runs Dijkstra algorithm from a given node.
1.172 + ///\param s is the given source.
1.173 void run(Node s)
1.174 {
1.175 _source=(void *)&s;
1.176 @@ -607,7 +648,9 @@
1.177 DefPredMapBase(const Base &b) : Base(b) {}
1.178 };
1.179
1.180 - ///\e
1.181 + /// \ref named-templ-param "Named parameter" function for setting PredMap type
1.182 +
1.183 + /// \ref named-templ-param "Named parameter" function for setting PredMap type
1.184 template<class T>
1.185 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1.186 {
1.187 @@ -623,7 +666,9 @@
1.188 DefPredNodeMapBase(const Base &b) : Base(b) {}
1.189 };
1.190
1.191 - ///\e
1.192 + /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
1.193 +
1.194 + /// \ref named-templ-param "Named parameter" function for setting PredNodeMap type
1.195 template<class T>
1.196 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.197 {
1.198 @@ -638,7 +683,9 @@
1.199 DefDistMapBase(const Base &b) : Base(b) {}
1.200 };
1.201
1.202 - ///\e
1.203 + /// \ref named-templ-param "Named parameter" function for setting DistMap type
1.204 +
1.205 + /// \ref named-templ-param "Named parameter" function for setting DistMap type
1.206 template<class T>
1.207 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1.208 {
1.209 @@ -646,7 +693,10 @@
1.210 return DijkstraWizard<DefDistMapBase<T> >(*this);
1.211 }
1.212
1.213 - ///\e
1.214 + /// Sets the source node, from which the Dijkstra algorithm runs.
1.215 +
1.216 + /// Sets the source node, from which the Dijkstra algorithm runs.
1.217 + /// \param s is the source node.
1.218 DijkstraWizard<TR> &source(Node s)
1.219 {
1.220 source=(void *)&s;