30 #include <invalid.h> |
30 #include <invalid.h> |
31 |
31 |
32 namespace hugo { |
32 namespace hugo { |
33 |
33 |
34 //Alpar: Changed the order of the parameters |
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 read-only 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 template <typename Graph, |
55 template <typename Graph, |
36 typename LengthMap=typename Graph::EdgeMap<int>, |
56 typename LengthMap=typename Graph::EdgeMap<int>, |
37 typename Heap=FibHeap<typename Graph::Node, |
57 typename Heap=BinHeap<typename Graph::Node, |
38 typename LengthMap::ValueType, |
58 typename LengthMap::ValueType, |
39 typename Graph::NodeMap<int> > > |
59 typename Graph::NodeMap<int> > > |
40 class Dijkstra{ |
60 class Dijkstra{ |
41 public: |
61 public: |
42 typedef typename LengthMap::ValueType ValueType; |
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 private: |
67 private: |
45 typedef typename Graph::Node Node; |
68 typedef typename Graph::Node Node; |
46 typedef typename Graph::NodeIt NodeIt; |
69 typedef typename Graph::NodeIt NodeIt; |
47 typedef typename Graph::Edge Edge; |
70 typedef typename Graph::Edge Edge; |
48 typedef typename Graph::OutEdgeIt OutEdgeIt; |
71 typedef typename Graph::OutEdgeIt OutEdgeIt; |
49 |
72 |
50 const Graph& G; |
73 const Graph& G; |
51 const LengthMap& length; |
74 const LengthMap& length; |
52 typedef typename Graph::NodeMap<Edge> PredMap; |
|
53 PredMap predecessor; |
75 PredMap predecessor; |
54 //In place of reach: |
76 //In place of reach: |
55 typedef typename Graph::NodeMap<Node> PredNodeMap; |
|
56 PredNodeMap pred_node; |
77 PredNodeMap pred_node; |
57 typedef typename Graph::NodeMap<ValueType> DistMap; |
|
58 DistMap distance; |
78 DistMap distance; |
59 //I don't like this: |
79 //I don't like this: |
60 // //FIXME: |
80 // //FIXME: |
61 // typename Graph::NodeMap<bool> reach; |
81 // typename Graph::NodeMap<bool> reach; |
62 // //typename Graph::NodeMap<int> reach; |
82 // //typename Graph::NodeMap<int> reach; |
70 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
90 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
71 |
91 |
72 |
92 |
73 void run(Node s); |
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 ValueType dist(Node v) const { return distance[v]; } |
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 Edge pred(Node v) const { return predecessor[v]; } |
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 Node predNode(Node v) const { return pred_node[v]; } |
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 const DistMap &distMap() const { return distance;} |
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 const PredMap &predMap() const { return predecessor;} |
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 const PredNodeMap &predNodeMap() const { return pred_node;} |
131 const PredNodeMap &predNodeMap() const { return pred_node;} |
82 |
132 |
83 // bool reached(Node v) { return reach[v]; } |
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 bool reached(Node v) { return G.valid(predecessor[v]); } |
142 bool reached(Node v) { return G.valid(predecessor[v]); } |
87 |
143 |
88 }; |
144 }; |
89 |
145 |
90 |
146 |
91 // IMPLEMENTATIONS |
147 // ********************************************************************** |
92 |
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 template <typename Graph, typename LengthMap, typename Heap > |
158 template <typename Graph, typename LengthMap, typename Heap > |
94 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
159 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
95 |
160 |
96 NodeIt u; |
161 NodeIt u; |
97 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
162 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { |
98 predecessor.set(u,INVALID); |
163 predecessor.set(u,INVALID); |
|
164 pred_node.set(u,INVALID); |
99 // If a node is unreacheable, then why should be the dist=0? |
165 // If a node is unreacheable, then why should be the dist=0? |
100 // distance.set(u,0); |
166 // distance.set(u,0); |
101 // reach.set(u,false); |
167 // reach.set(u,false); |
102 } |
168 } |
103 |
169 |