Changeset 224:5bc1c83257f8 in lemon0.x
 Timestamp:
 03/21/04 15:59:51 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@321
 Location:
 src/work/alpar/dijkstra
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra/bin_heap.hh
r222 r224 66 66 namespace hugo { 67 67 68 /// A Binary Heap implementation. 68 69 template <typename Key, typename Val, typename KeyIntMap, 69 70 typename Compare = std::less<Val> > 
src/work/alpar/dijkstra/dijkstra.h
r222 r224 33 33 34 34 //Alpar: Changed the order of the parameters 35 36 ///Dijkstra algorithm class. 37 38 ///This class provides an efficient implementation of Dijkstra algorithm. 39 ///The edge lengths are passed to the algorithm using a 40 ///\ref ReadMapSkeleton "readable map", 41 ///so it is easy to change it to any kind of length. 42 /// 43 ///The type of the length is determined by the \c ValueType of the length map. 44 /// 45 ///It is also posible to change the underlying priority heap. 46 /// 47 ///\param Graph The graph type the algorithm runs on. 48 ///\param LengthMap This readonly EdgeMap determines the 49 ///lengths of the edges. It is read once for each edge, so the map 50 ///may involve in relatively time consuming process to compute the edge 51 ///length if it is necessary. 52 ///\param Heap The heap type used by the Dijkstra 53 ///algorithm. The default 54 ///is using \ref BinHeap "binary heap". 35 55 template <typename Graph, 36 56 typename LengthMap=typename Graph::EdgeMap<int>, 37 typename Heap= FibHeap<typename Graph::Node,57 typename Heap=BinHeap<typename Graph::Node, 38 58 typename LengthMap::ValueType, 39 59 typename Graph::NodeMap<int> > > … … 41 61 public: 42 62 typedef typename LengthMap::ValueType ValueType; 63 typedef typename Graph::NodeMap<Edge> PredMap; 64 typedef typename Graph::NodeMap<Node> PredNodeMap; 65 typedef typename Graph::NodeMap<ValueType> DistMap; 43 66 44 67 private: … … 50 73 const Graph& G; 51 74 const LengthMap& length; 52 typedef typename Graph::NodeMap<Edge> PredMap;53 75 PredMap predecessor; 54 76 //In place of reach: 55 typedef typename Graph::NodeMap<Node> PredNodeMap;56 77 PredNodeMap pred_node; 57 typedef typename Graph::NodeMap<ValueType> DistMap;58 78 DistMap distance; 59 79 //I don't like this: … … 73 93 void run(Node s); 74 94 95 ///The distance of a node from the source. 96 97 ///Returns the distance of a node from the source. 98 ///\pre \ref run() must be called before using this function. 99 ///\warning If node \c v in unreachable from \c s the return value 100 ///of this funcion is undefined. 75 101 ValueType dist(Node v) const { return distance[v]; } 102 ///Returns the edges of the shortest path tree. 103 104 ///For a node \c v it returns the last edge of the shortest path 105 ///from \c s to \c v or INVALID if \c v is unreachable from \c s. 106 ///\pre \ref run() must be called before using this function. 76 107 Edge pred(Node v) const { return predecessor[v]; } 108 ///Returns the nodes of the shortest paths. 109 110 ///For a node \c v it returns the last but one node of the shortest path 111 ///from \c s to \c v or INVALID if \c v is unreachable from \c s. 112 ///\pre \ref run() must be called before using this function. 77 113 Node predNode(Node v) const { return pred_node[v]; } 78 114 115 ///Returns a reference to the NodeMap of distances. 116 117 ///\pre \ref run() must be called before using this function. 118 /// 79 119 const DistMap &distMap() const { return distance;} 120 ///Returns a reference to the shortest path tree map. 121 122 ///Returns a reference to the NodeMap of the edges of the 123 ///shortest path tree. 124 ///\pre \ref run() must be called before using this function. 80 125 const PredMap &predMap() const { return predecessor;} 126 ///Returns a reference to the map of nodes of shortest paths. 127 128 ///Returns a reference to the NodeMap of the last but one nodes of the 129 ///shortest paths. 130 ///\pre \ref run() must be called before using this function. 81 131 const PredNodeMap &predNodeMap() const { return pred_node;} 82 132 83 133 // bool reached(Node v) { return reach[v]; } 84 ///\warning \c s is not reached! 134 135 ///Chech if a node is reachable from \c s. 136 137 ///Returns \c true if \c v is reachable from \c s. 138 ///\warning \c s is reported to be unreached! 139 ///\todo Is this what we want? 140 ///\pre \ref run() must be called before using this function. 85 141 /// 86 142 bool reached(Node v) { return G.valid(predecessor[v]); } … … 89 145 90 146 91 // IMPLEMENTATIONS 92 147 // ********************************************************************** 148 // IMPLEMENTATIONS 149 // ********************************************************************** 150 151 ///Runs Dijkstra algorithm from node \c s. 152 153 ///This method runs the Dijkstra algorithm from node \c s in order to 154 ///compute the 155 ///shortest path to each node. The algorithm computes 156 /// The shortest path tree. 157 /// The distance of each node. 93 158 template <typename Graph, typename LengthMap, typename Heap > 94 159 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { … … 97 162 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { 98 163 predecessor.set(u,INVALID); 164 pred_node.set(u,INVALID); 99 165 // If a node is unreacheable, then why should be the dist=0? 100 166 // distance.set(u,0); 
src/work/alpar/dijkstra/fib_heap.h
r222 r224 58 58 namespace hugo { 59 59 60 /// A Fibonacci Heap implementation. 60 61 template <typename Item, typename Prio, typename ItemIntMap, 61 typename Compare = std::less<Prio> > 62 62 typename Compare = std::less<Prio> > 63 63 class FibHeap { 64 64 65 65 typedef Prio PrioType; 66 66
Note: See TracChangeset
for help on using the changeset viewer.