Index: src/work/alpar/dijkstra.h =================================================================== --- src/work/alpar/dijkstra.h (revision 953) +++ src/work/alpar/dijkstra.h (revision 954) @@ -31,13 +31,14 @@ /// @{ + ///Default traits class of Dijkstra class. + + ///Default traits class of Dijkstra class. + ///\param GR Graph type. + ///\param LM Type of length map. template struct DijkstraDefaultTraits { - ///\e + ///The graph type the algorithm runs on. typedef GR Graph; - ///\e - typedef typename Graph::Node Node; - ///\e - typedef typename Graph::Edge Edge; ///The type of the map that stores the edge lengths. @@ -45,7 +46,7 @@ /// typedef LM LengthMap; - ///The type of the length of the edges. + //The type of the length of the edges. typedef typename LM::ValueType ValueType; - ///The heap type used by the dijkstra algorithm. + ///The heap type used by Dijkstra algorithm. typedef BinHeap PredMap; - /// + typedef typename Graph::template NodeMap PredMap; + ///Instantiates a PredMap. ///\todo Please document... /// - static PredMap *createPredMap(const Graph &G) + static PredMap *createPredMap(const GR &G) { return new PredMap(G); @@ -72,10 +73,10 @@ ///It must meet the \ref WriteMap concept. /// - typedef typename Graph::template NodeMap PredNodeMap; - /// + typedef typename Graph::template NodeMap PredNodeMap; + ///Instantiates a PredNodeMap. ///\todo Please document... /// - static PredNodeMap *createPredNodeMap(const Graph &G) + static PredNodeMap *createPredNodeMap(const GR &G) { return new PredNodeMap(G); @@ -85,10 +86,10 @@ ///It must meet the \ref WriteMap concept. /// - typedef typename Graph::template NodeMap DistMap; - /// + typedef typename Graph::template NodeMap DistMap; + ///Instantiates a DistMap. ///\todo Please document... /// - static DistMap *createDistMap(const Graph &G) + static DistMap *createDistMap(const GR &G) { return new DistMap(G); @@ -109,5 +110,6 @@ /// ///\param GR The graph type the algorithm runs on. The default value is - ///\ref ListGraph + ///\ref ListGraph. The value of GR is not used directly by %Dijsktra, it + ///is only passed to \ref DijkstraDefaultTraits. ///\param LM This read-only ///EdgeMap @@ -116,13 +118,15 @@ ///may involve in relatively time consuming process to compute the edge ///length if it is necessary. The default map type is - ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap" - ///\param Heap The heap type used by the %Dijkstra - ///algorithm. The default - ///is using \ref BinHeap "binary heap". + ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap". + ///The value of LM is not used directly by %Dijsktra, it + ///is only passed to \ref DijkstraDefaultTraits. + ///\param TR Traits class to set various data types used by the algorithm. + ///The default traits class is + ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits". + ///See \ref DijkstraDefaultTraits for the documentation of + ///a Dijkstra traits class. /// ///\author Jacint Szabo and Alpar Juttner ///\todo We need a typedef-names should be standardized. (-: - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap - ///should not be fixed. (Problematic to solve). #ifdef DOXYGEN @@ -139,5 +143,5 @@ typedef TR Traits; ///The type of the underlying graph. - typedef GR Graph; + typedef typename TR::Graph Graph; ///\e typedef typename Graph::Node Node; @@ -150,7 +154,7 @@ ///The type of the length of the edges. - typedef typename LM::ValueType ValueType; + typedef typename TR::LengthMap::ValueType ValueType; ///The type of the map that stores the edge lengths. - typedef LM LengthMap; + typedef typename TR::LengthMap LengthMap; ///\brief The type of the map that stores the last ///edges of the shortest paths. @@ -161,5 +165,4 @@ ///The type of the map that stores the dists of the nodes. typedef typename TR::DistMap DistMap; - ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; @@ -169,5 +172,5 @@ const Graph *G; /// Pointer to the length map - const LM *length; + const LengthMap *length; ///Pointer to the map of predecessors edges. PredMap *predecessor; @@ -220,5 +223,8 @@ } }; - ///\ref named-templ-param "Named parameter" for setting PredMap's type + ///\ref named-templ-param "Named parameter" for setting PredMap type + + ///\ingroup flowalgs + ///\ref named-templ-param "Named parameter" for setting PredMap type template class SetPredMap : public Dijkstra< Graph, @@ -238,5 +244,8 @@ } }; - ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type + ///\ref named-templ-param "Named parameter" for setting PredNodeMap type + + ///\ingroup flowalgs + ///\ref named-templ-param "Named parameter" for setting PredNodeMap type template class SetPredNodeMap : public Dijkstra< Graph, @@ -256,5 +265,8 @@ } }; - ///\ref named-templ-param "Named parameter" for setting DistMap's type + ///\ref named-templ-param "Named parameter" for setting DistMap type + + ///\ingroup flowalgs + ///\ref named-templ-param "Named parameter" for setting DistMap type template class SetDistMap : public Dijkstra< Graph, @@ -266,5 +278,5 @@ ///\param _G the graph the algorithm will run on. ///\param _length the length map used by the algorithm. - Dijkstra(const Graph& _G, const LM& _length) : + Dijkstra(const Graph& _G, const LengthMap& _length) : G(&_G), length(&_length), predecessor(NULL), local_predecessor(false), @@ -285,5 +297,5 @@ ///Sets the length map. ///\return (*this) - Dijkstra &setLengthMap(const LM &m) + Dijkstra &setLengthMap(const LengthMap &m) { length = &m; @@ -350,5 +362,5 @@ ///- The shortest path tree. ///- The distance of each node from the root. - + ///\todo heap_map's type could also be in the traits class. void run(Node s) { @@ -362,5 +374,5 @@ } - typename GR::template NodeMap heap_map(*G,-1); + typename Graph::template NodeMap heap_map(*G,-1); Heap heap(heap_map); @@ -584,5 +596,5 @@ ///\e - ///\e + ///\todo Please document... /// template