Changeset 584:1d4855f5312e in lemon0.x
 Timestamp:
 05/08/04 17:58:34 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@761
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/dijkstra.h
r570 r584 26 26 ///It is also possible to change the underlying priority heap. 27 27 /// 28 ///\param G raphThe graph type the algorithm runs on.29 ///\param L engthMapThis readonly28 ///\param GR The graph type the algorithm runs on. 29 ///\param LM This readonly 30 30 ///EdgeMap 31 31 ///determines the … … 39 39 /// 40 40 ///\author Jacint Szabo 41 ///\todo We need a LengthMap typedef 41 ///\todo We need a typedefnames should be standardized. 42 42 43 #ifdef DOXYGEN 43 template <typename G raph,44 typename L engthMap,44 template <typename GR, 45 typename LM, 45 46 typename Heap> 46 47 #else 47 template <typename G raph,48 typename L engthMap=typename Graph::template EdgeMap<int>,48 template <typename GR, 49 typename LM=typename GR::template EdgeMap<int>, 49 50 template <class,class,class,class> class Heap = BinHeap > 50 51 #endif 51 52 class Dijkstra{ 52 53 public: 54 ///The type of the underlying graph. 55 typedef GR Graph; 53 56 typedef typename Graph::Node Node; 54 57 typedef typename Graph::NodeIt NodeIt; … … 56 59 typedef typename Graph::OutEdgeIt OutEdgeIt; 57 60 58 typedef typename LengthMap::ValueType ValueType; 61 ///The type of the length of the edges. 62 typedef typename LM::ValueType ValueType; 63 ///The the type of the map that stores the edge lengths. 64 typedef LM LengthMap; 65 ///\brief The the type of the map that stores the last 66 ///edges of the shortest paths. 59 67 typedef typename Graph::template NodeMap<Edge> PredMap; 68 ///\brief The the type of the map that stores the last but one 69 ///nodes of the shortest paths. 60 70 typedef typename Graph::template NodeMap<Node> PredNodeMap; 71 ///The the type of the map that stores the dists of the nodes. 61 72 typedef typename Graph::template NodeMap<ValueType> DistMap; 62 73 63 74 private: 64 75 const Graph& G; 65 const L engthMap& length;76 const LM& length; 66 77 PredMap predecessor; 67 78 PredNodeMap pred_node; … … 70 81 public : 71 82 72 Dijkstra(const Graph& _G, const L engthMap& _length) :83 Dijkstra(const Graph& _G, const LM& _length) : 73 84 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } 74 85 … … 83 94 ValueType dist(Node v) const { return distance[v]; } 84 95 85 ///Returns the previous edgeof the shortest path tree.86 87 ///For a node \c v it returns the previous edgeof the shortest path tree,96 ///Returns the 'previous edge' of the shortest path tree. 97 98 ///For a node \c v it returns the 'previous edge' of the shortest path tree, 88 99 ///i.e. it returns the last edge from a shortest path from the root to \c 89 100 ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The … … 93 104 Edge pred(Node v) const { return predecessor[v]; } 94 105 95 ///Returns the previous nodeof the shortest path tree.96 97 ///For a node \c v it returns the previous nodeof the shortest path tree,106 ///Returns the 'previous node' of the shortest path tree. 107 108 ///For a node \c v it returns the 'previous node' of the shortest path tree, 98 109 ///i.e. it returns the last but one node from a shortest path from the 99 110 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if … … 147 158 /// The shortest path tree. 148 159 /// The distance of each node from the root. 149 template <typename G raph, typename LengthMap,160 template <typename GR, typename LM, 150 161 template<class,class,class,class> class Heap > 151 void Dijkstra<G raph,LengthMap,Heap>::run(Node s) {162 void Dijkstra<GR,LM,Heap>::run(Node s) { 152 163 153 164 NodeIt u; … … 157 168 } 158 169 159 typename G raph::template NodeMap<int> heap_map(G,1);160 161 typedef Heap<Node, ValueType, typename G raph::template NodeMap<int>,170 typename GR::template NodeMap<int> heap_map(G,1); 171 172 typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, 162 173 std::less<ValueType> > 163 174 HeapType;
Note: See TracChangeset
for help on using the changeset viewer.