lemon-0.x: comparison src/work/alpar/dijkstra.h

equal deleted inserted replaced

-:d6746a9cc1b4
+:26db6da01207
 namespace lemon {
 /// \addtogroup flowalgs
 /// @{
+///Default traits class of Dijkstra class.
+///Default traits class of Dijkstra class.
+///\param GR Graph type.
+///\param LM Type of length map.
 template<class GR, class LM>
 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.
 ///It must meet the \ref ReadMap concept.
 ///
 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<typename Graph::Node,
 		    typename LM::ValueType,
 		    typename GR::template NodeMap<int>,
 		    std::less<ValueType> > Heap;
 ///\brief The type of the map that stores the last
 ///edges of the shortest paths.
 ///
 ///It must meet the \ref WriteMap concept.
 ///
-typedef typename Graph::template NodeMap<Edge> PredMap;
+typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
-///
+///Instantiates a PredMap.
 ///\todo Please document...
 ///
-static PredMap *createPredMap(const Graph &G)
+static PredMap *createPredMap(const GR &G)
 {
 return new PredMap(G);
 }
 ///\brief The type of the map that stores the last but one
 ///nodes of the shortest paths.
 ///
 ///It must meet the \ref WriteMap concept.
 ///
-typedef typename Graph::template NodeMap<Node> PredNodeMap;
+typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
-///
+///Instantiates a PredNodeMap.
 ///\todo Please document...
 ///
-static PredNodeMap *createPredNodeMap(const Graph &G)
+static PredNodeMap *createPredNodeMap(const GR &G)
 {
 return new PredNodeMap(G);
 }
 ///The type of the map that stores the dists of the nodes.
 ///It must meet the \ref WriteMap concept.
 ///
-typedef typename Graph::template NodeMap<ValueType> DistMap;
+typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap;
-///
+///Instantiates a DistMap.
 ///\todo Please document...
 ///
-static DistMap *createDistMap(const Graph &G)
+static DistMap *createDistMap(const GR &G)
 {
 return new DistMap(G);
 }
 };
 ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map.
 ///
 ///It is also possible to change the underlying priority heap.
 ///
 ///\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
 ///determines the
 ///lengths of the edges. It is read once for each edge, so the map
 ///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<int>"
+///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
-///\param Heap The heap type used by the %Dijkstra
+///The value of LM is not used directly by %Dijsktra, it
-///algorithm. The default
+///is only passed to \ref DijkstraDefaultTraits.
-///is using \ref BinHeap "binary heap".
+///\param TR Traits class to set various data types used by the algorithm.
+///The default traits class is
+///\ref DijkstraDefaultTraits<GR,LM> "DijkstraDefaultTraits<GR,LM>".
+///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
 template <typename GR,
 	    typename LM,
 	    typename TR>
 #endif
 class Dijkstra{
 public:
 typedef TR Traits;
 ///The type of the underlying graph.
-typedef GR Graph;
+typedef typename TR::Graph Graph;
 ///\e
 typedef typename Graph::Node Node;
 ///\e
 typedef typename Graph::NodeIt NodeIt;
 ///\e
 typedef typename Graph::Edge Edge;
 ///\e
 typedef typename Graph::OutEdgeIt OutEdgeIt;
 ///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.
 typedef typename TR::PredMap PredMap;
 ///\brief The type of the map that stores the last but one
 ///nodes of the shortest paths.
 typedef typename TR::PredNodeMap PredNodeMap;
 ///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;
 private:
 /// Pointer to the underlying graph.
 const Graph *G;
 /// Pointer to the length map
-const LM *length;
+const LengthMap *length;
 ///Pointer to the map of predecessors edges.
 PredMap *predecessor;
 ///Indicates if \ref predecessor is locally allocated (\c true) or not.
 bool local_predecessor;
 ///Pointer to the map of predecessors nodes.
 	std::cerr << __FILE__ ":" << __LINE__ <<
 	  ": error: Special maps should be manually created" << std::endl;
 	exit(1);
 }
 };
-///\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 T>
 class SetPredMap : public Dijkstra< Graph,
 					LengthMap,
 					SetPredMapTraits<T> > { };
 	std::cerr << __FILE__ ":" << __LINE__ <<
 	  ": error: Special maps should be manually created" << std::endl;
 	exit(1);
 }
 };
-///\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 T>
 class SetPredNodeMap : public Dijkstra< Graph,
 					    LengthMap,
 					    SetPredNodeMapTraits<T> > { };
 	std::cerr << __FILE__ ":" << __LINE__ <<
 	  ": error: Special maps should be manually created" << std::endl;
 	exit(1);
 }
 };
-///\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 T>
 class SetDistMap : public Dijkstra< Graph,
 					LengthMap,
 					SetDistMapTraits<T> > { };
 ///Constructor.
 ///\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),
 pred_node(NULL), local_pred_node(false),
 distance(NULL), local_distance(false)
 { }
 ///Sets the length map.
 ///Sets the length map.
 ///\return <tt> (*this) </tt>
-Dijkstra &setLengthMap(const LM &m)
+Dijkstra &setLengthMap(const LengthMap &m)
 {
 length = &m;
 return *this;
 }
 ///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.
+///\todo heap_map's type could also be in the traits class.
 void run(Node s) {
 init_maps();
 source = s;
 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 	predecessor->set(u,INVALID);
 	pred_node->set(u,INVALID);
 }
-typename GR::template NodeMap<int> heap_map(*G,-1);
+typename Graph::template NodeMap<int> heap_map(*G,-1);
 Heap heap(heap_map);
 heap.push(s,0);
 };
 ///\e
-///\e
+///\todo Please document...
 ///
 template<class GR, class LM>
 _Dijkstra<DijkstraDefaultTraits<GR,LM> >
 dijkstra(const GR &g,const LM &l,typename GR::Node s)
 {

changeset 954	5b1ffef43d4c
parent 953	d9c115e2eeaf
child 955	0a066f80e05f