53 #endif |
53 #endif |
54 class Dijkstra{ |
54 class Dijkstra{ |
55 public: |
55 public: |
56 ///The type of the underlying graph. |
56 ///The type of the underlying graph. |
57 typedef GR Graph; |
57 typedef GR Graph; |
|
58 ///. |
58 typedef typename Graph::Node Node; |
59 typedef typename Graph::Node Node; |
|
60 ///. |
59 typedef typename Graph::NodeIt NodeIt; |
61 typedef typename Graph::NodeIt NodeIt; |
|
62 ///. |
60 typedef typename Graph::Edge Edge; |
63 typedef typename Graph::Edge Edge; |
|
64 ///. |
61 typedef typename Graph::OutEdgeIt OutEdgeIt; |
65 typedef typename Graph::OutEdgeIt OutEdgeIt; |
62 |
66 |
63 ///The type of the length of the edges. |
67 ///The type of the length of the edges. |
64 typedef typename LM::ValueType ValueType; |
68 typedef typename LM::ValueType ValueType; |
65 ///The type of the map that stores the edge lengths. |
69 ///The type of the map that stores the edge lengths. |
72 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
76 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
73 ///The type of the map that stores the dists of the nodes. |
77 ///The type of the map that stores the dists of the nodes. |
74 typedef typename Graph::template NodeMap<ValueType> DistMap; |
78 typedef typename Graph::template NodeMap<ValueType> DistMap; |
75 |
79 |
76 private: |
80 private: |
|
81 /// Pointer to the underlying graph. |
77 const Graph *G; |
82 const Graph *G; |
|
83 /// Pointer to the length map |
78 const LM *length; |
84 const LM *length; |
79 // bool local_length; |
85 ///Pointer to the map of predecessors edges. |
80 PredMap *predecessor; |
86 PredMap *predecessor; |
|
87 ///Indicates if \ref predecessor is locally allocated (\c true) or not. |
81 bool local_predecessor; |
88 bool local_predecessor; |
|
89 ///Pointer to the map of predecessors nodes. |
82 PredNodeMap *pred_node; |
90 PredNodeMap *pred_node; |
|
91 ///Indicates if \ref pred_node is locally allocated (\c true) or not. |
83 bool local_pred_node; |
92 bool local_pred_node; |
|
93 ///Pointer to the map of distances. |
84 DistMap *distance; |
94 DistMap *distance; |
|
95 ///Indicates if \ref distance is locally allocated (\c true) or not. |
85 bool local_distance; |
96 bool local_distance; |
86 |
97 |
87 //The source node of the last execution. |
98 ///The source node of the last execution. |
88 Node source; |
99 Node source; |
89 |
100 |
90 ///Initializes the maps. |
101 ///Initializes the maps. |
91 |
102 |
92 ///\todo Error if \c G or are \c NULL. What about \c length? |
103 ///\todo Error if \c G or are \c NULL. What about \c length? |
93 ///\todo Better memory allocation (instead of new). |
104 ///\todo Better memory allocation (instead of new). |
94 void init_maps() |
105 void init_maps() |
95 { |
106 { |
96 // if(!length) { |
|
97 // local_length = true; |
|
98 // length = new LM(G); |
|
99 // } |
|
100 if(!predecessor) { |
107 if(!predecessor) { |
101 local_predecessor = true; |
108 local_predecessor = true; |
102 predecessor = new PredMap(*G); |
109 predecessor = new PredMap(*G); |
103 } |
110 } |
104 if(!pred_node) { |
111 if(!pred_node) { |
110 distance = new DistMap(*G); |
117 distance = new DistMap(*G); |
111 } |
118 } |
112 } |
119 } |
113 |
120 |
114 public : |
121 public : |
115 |
122 ///Constructor. |
|
123 |
|
124 ///\param _G the graph the algorithm will run on. |
|
125 ///\param _length the length map used by the algorithm. |
116 Dijkstra(const Graph& _G, const LM& _length) : |
126 Dijkstra(const Graph& _G, const LM& _length) : |
117 G(&_G), length(&_length), |
127 G(&_G), length(&_length), |
118 predecessor(NULL), local_predecessor(false), |
128 predecessor(NULL), local_predecessor(false), |
119 pred_node(NULL), local_pred_node(false), |
129 pred_node(NULL), local_pred_node(false), |
120 distance(NULL), local_distance(false) |
130 distance(NULL), local_distance(false) |
121 { } |
131 { } |
122 |
132 |
|
133 ///Destructor. |
123 ~Dijkstra() |
134 ~Dijkstra() |
124 { |
135 { |
125 // if(local_length) delete length; |
|
126 if(local_predecessor) delete predecessor; |
136 if(local_predecessor) delete predecessor; |
127 if(local_pred_node) delete pred_node; |
137 if(local_pred_node) delete pred_node; |
128 if(local_distance) delete distance; |
138 if(local_distance) delete distance; |
129 } |
139 } |
130 |
140 |
131 ///Sets the graph the algorithm will run on. |
|
132 |
|
133 ///Sets the graph the algorithm will run on. |
|
134 ///\return <tt> (*this) </tt> |
|
135 ///\bug What about maps? |
|
136 ///\todo It may be unnecessary |
|
137 Dijkstra &setGraph(const Graph &_G) |
|
138 { |
|
139 G = &_G; |
|
140 return *this; |
|
141 } |
|
142 ///Sets the length map. |
141 ///Sets the length map. |
143 |
142 |
144 ///Sets the length map. |
143 ///Sets the length map. |
145 ///\return <tt> (*this) </tt> |
144 ///\return <tt> (*this) </tt> |
146 Dijkstra &setLengthMap(const LM &m) |
145 Dijkstra &setLengthMap(const LM &m) |
147 { |
146 { |
148 // if(local_length) { |
|
149 // delete length; |
|
150 // local_length=false; |
|
151 // } |
|
152 length = &m; |
147 length = &m; |
153 return *this; |
148 return *this; |
154 } |
149 } |
155 |
150 |
156 ///Sets the map storing the predecessor edges. |
151 ///Sets the map storing the predecessor edges. |
315 const PredNodeMap &predNodeMap() const { return *pred_node;} |
310 const PredNodeMap &predNodeMap() const { return *pred_node;} |
316 |
311 |
317 ///Checks if a node is reachable from the root. |
312 ///Checks if a node is reachable from the root. |
318 |
313 |
319 ///Returns \c true if \c v is reachable from the root. |
314 ///Returns \c true if \c v is reachable from the root. |
320 ///\warning the root node is reported to be reached! |
315 ///\note The root node is reported to be reached! |
321 ///\pre \ref run() must be called before using this function. |
316 ///\pre \ref run() must be called before using this function. |
322 /// |
317 /// |
323 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
318 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
324 |
319 |
325 }; |
320 }; |