112 } |
82 } |
113 |
83 |
114 typedef True NodeNumTag; |
84 typedef True NodeNumTag; |
115 typedef True ArcNumTag; |
85 typedef True ArcNumTag; |
116 |
86 |
117 int nodeNum() const { return _nodeNum; } |
87 int nodeNum() const { return _node_num; } |
118 int arcNum() const { return _arcNum; } |
88 int edgeNum() const { return _edge_num; } |
119 |
89 int arcNum() const { return 2 * _edge_num; } |
120 int maxNodeId() const { return nodeNum() - 1; } |
90 |
121 int maxArcId() const { return arcNum() - 1; } |
91 Node u(Edge edge) const { |
122 |
92 if (edge._id < _edge_limit) { |
123 Node source(Arc e) const { |
93 return edge._id; |
124 if (e.id < _arcLimit) { |
94 } else { |
125 return e.id; |
95 return (edge._id - _edge_limit) % (_width - 1) + |
126 } else { |
96 (edge._id - _edge_limit) / (_width - 1) * _width; |
127 return (e.id - _arcLimit) % (_width - 1) + |
97 } |
128 (e.id - _arcLimit) / (_width - 1) * _width; |
98 } |
129 } |
99 |
130 } |
100 Node v(Edge edge) const { |
131 |
101 if (edge._id < _edge_limit) { |
132 Node target(Arc e) const { |
102 return edge._id + _width; |
133 if (e.id < _arcLimit) { |
103 } else { |
134 return e.id + _width; |
104 return (edge._id - _edge_limit) % (_width - 1) + |
135 } else { |
105 (edge._id - _edge_limit) / (_width - 1) * _width + 1; |
136 return (e.id - _arcLimit) % (_width - 1) + |
106 } |
137 (e.id - _arcLimit) / (_width - 1) * _width + 1; |
107 } |
138 } |
108 |
139 } |
109 Node source(Arc arc) const { |
140 |
110 return (arc._id & 1) == 1 ? u(arc) : v(arc); |
141 static int id(Node v) { return v.id; } |
111 } |
142 static int id(Arc e) { return e.id; } |
112 |
|
113 Node target(Arc arc) const { |
|
114 return (arc._id & 1) == 1 ? v(arc) : u(arc); |
|
115 } |
|
116 |
|
117 static int id(Node node) { return node._id; } |
|
118 static int id(Edge edge) { return edge._id; } |
|
119 static int id(Arc arc) { return arc._id; } |
|
120 |
|
121 int maxNodeId() const { return _node_num - 1; } |
|
122 int maxEdgeId() const { return _edge_num - 1; } |
|
123 int maxArcId() const { return 2 * _edge_num - 1; } |
143 |
124 |
144 static Node nodeFromId(int id) { return Node(id);} |
125 static Node nodeFromId(int id) { return Node(id);} |
145 |
126 static Edge edgeFromId(int id) { return Edge(id);} |
146 static Arc arcFromId(int id) { return Arc(id);} |
127 static Arc arcFromId(int id) { return Arc(id);} |
147 |
128 |
148 typedef True FindArcTag; |
129 typedef True FindEdgeTag; |
|
130 |
|
131 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { |
|
132 if (prev != INVALID) return INVALID; |
|
133 if (v._id > u._id) { |
|
134 if (v._id - u._id == _width) |
|
135 return Edge(u._id); |
|
136 if (v._id - u._id == 1 && u._id % _width < _width - 1) { |
|
137 return Edge(u._id / _width * (_width - 1) + |
|
138 u._id % _width + _edge_limit); |
|
139 } |
|
140 } else { |
|
141 if (u._id - v._id == _width) |
|
142 return Edge(v._id); |
|
143 if (u._id - v._id == 1 && v._id % _width < _width - 1) { |
|
144 return Edge(v._id / _width * (_width - 1) + |
|
145 v._id % _width + _edge_limit); |
|
146 } |
|
147 } |
|
148 return INVALID; |
|
149 } |
149 |
150 |
150 Arc findArc(Node u, Node v, Arc prev = INVALID) const { |
151 Arc findArc(Node u, Node v, Arc prev = INVALID) const { |
151 if (prev != INVALID) return INVALID; |
152 if (prev != INVALID) return INVALID; |
152 if (v.id - u.id == _width) return Arc(u.id); |
153 if (v._id > u._id) { |
153 if (v.id - u.id == 1 && u.id % _width < _width - 1) { |
154 if (v._id - u._id == _width) |
154 return Arc(u.id / _width * (_width - 1) + |
155 return Arc((u._id << 1) | 1); |
155 u.id % _width + _arcLimit); |
156 if (v._id - u._id == 1 && u._id % _width < _width - 1) { |
|
157 return Arc(((u._id / _width * (_width - 1) + |
|
158 u._id % _width + _edge_limit) << 1) | 1); |
|
159 } |
|
160 } else { |
|
161 if (u._id - v._id == _width) |
|
162 return Arc(v._id << 1); |
|
163 if (u._id - v._id == 1 && v._id % _width < _width - 1) { |
|
164 return Arc((v._id / _width * (_width - 1) + |
|
165 v._id % _width + _edge_limit) << 1); |
|
166 } |
156 } |
167 } |
157 return INVALID; |
168 return INVALID; |
158 } |
169 } |
159 |
170 |
160 class Node { |
171 class Node { |
161 friend class GridGraphBase; |
172 friend class GridGraphBase; |
162 |
173 |
163 protected: |
174 protected: |
164 int id; |
175 int _id; |
165 Node(int _id) : id(_id) {} |
176 Node(int id) : _id(id) {} |
166 public: |
177 public: |
167 Node() {} |
178 Node() {} |
168 Node (Invalid) { id = -1; } |
179 Node (Invalid) : _id(-1) {} |
169 bool operator==(const Node node) const { return id == node.id; } |
180 bool operator==(const Node node) const {return _id == node._id;} |
170 bool operator!=(const Node node) const { return id != node.id; } |
181 bool operator!=(const Node node) const {return _id != node._id;} |
171 bool operator<(const Node node) const { return id < node.id; } |
182 bool operator<(const Node node) const {return _id < node._id;} |
|
183 }; |
|
184 |
|
185 class Edge { |
|
186 friend class GridGraphBase; |
|
187 |
|
188 protected: |
|
189 int _id; |
|
190 |
|
191 Edge(int id) : _id(id) {} |
|
192 |
|
193 public: |
|
194 Edge() {} |
|
195 Edge (Invalid) : _id(-1) {} |
|
196 bool operator==(const Edge edge) const {return _id == edge._id;} |
|
197 bool operator!=(const Edge edge) const {return _id != edge._id;} |
|
198 bool operator<(const Edge edge) const {return _id < edge._id;} |
172 }; |
199 }; |
173 |
200 |
174 class Arc { |
201 class Arc { |
175 friend class GridGraphBase; |
202 friend class GridGraphBase; |
176 |
203 |
177 protected: |
204 protected: |
178 int id; |
205 int _id; |
179 Arc(int _id) : id(_id) {} |
206 |
|
207 Arc(int id) : _id(id) {} |
|
208 |
180 public: |
209 public: |
181 Arc() {} |
210 Arc() {} |
182 Arc (Invalid) { id = -1; } |
211 Arc (Invalid) : _id(-1) {} |
183 bool operator==(const Arc arc) const { return id == arc.id; } |
212 operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; } |
184 bool operator!=(const Arc arc) const { return id != arc.id; } |
213 bool operator==(const Arc arc) const {return _id == arc._id;} |
185 bool operator<(const Arc arc) const { return id < arc.id; } |
214 bool operator!=(const Arc arc) const {return _id != arc._id;} |
|
215 bool operator<(const Arc arc) const {return _id < arc._id;} |
186 }; |
216 }; |
187 |
217 |
|
218 static bool direction(Arc arc) { |
|
219 return (arc._id & 1) == 1; |
|
220 } |
|
221 |
|
222 static Arc direct(Edge edge, bool dir) { |
|
223 return Arc((edge._id << 1) | (dir ? 1 : 0)); |
|
224 } |
|
225 |
188 void first(Node& node) const { |
226 void first(Node& node) const { |
189 node.id = nodeNum() - 1; |
227 node._id = _node_num - 1; |
190 } |
228 } |
191 |
229 |
192 static void next(Node& node) { |
230 static void next(Node& node) { |
193 --node.id; |
231 --node._id; |
|
232 } |
|
233 |
|
234 void first(Edge& edge) const { |
|
235 edge._id = _edge_num - 1; |
|
236 } |
|
237 |
|
238 static void next(Edge& edge) { |
|
239 --edge._id; |
194 } |
240 } |
195 |
241 |
196 void first(Arc& arc) const { |
242 void first(Arc& arc) const { |
197 arc.id = arcNum() - 1; |
243 arc._id = 2 * _edge_num - 1; |
198 } |
244 } |
199 |
245 |
200 static void next(Arc& arc) { |
246 static void next(Arc& arc) { |
201 --arc.id; |
247 --arc._id; |
202 } |
248 } |
203 |
249 |
204 void firstOut(Arc& arc, const Node& node) const { |
250 void firstOut(Arc& arc, const Node& node) const { |
205 if (node.id < _nodeNum - _width) { |
251 if (node._id % _width < _width - 1) { |
206 arc.id = node.id; |
252 arc._id = (_edge_limit + node._id % _width + |
207 } else if (node.id % _width < _width - 1) { |
253 (node._id / _width) * (_width - 1)) << 1 | 1; |
208 arc.id = _arcLimit + node.id % _width + |
254 return; |
209 (node.id / _width) * (_width - 1); |
255 } |
210 } else { |
256 if (node._id < _node_num - _width) { |
211 arc.id = -1; |
257 arc._id = node._id << 1 | 1; |
212 } |
258 return; |
|
259 } |
|
260 if (node._id % _width > 0) { |
|
261 arc._id = (_edge_limit + node._id % _width + |
|
262 (node._id / _width) * (_width - 1) - 1) << 1; |
|
263 return; |
|
264 } |
|
265 if (node._id >= _width) { |
|
266 arc._id = (node._id - _width) << 1; |
|
267 return; |
|
268 } |
|
269 arc._id = -1; |
213 } |
270 } |
214 |
271 |
215 void nextOut(Arc& arc) const { |
272 void nextOut(Arc& arc) const { |
216 if (arc.id >= _arcLimit) { |
273 int nid = arc._id >> 1; |
217 arc.id = -1; |
274 if ((arc._id & 1) == 1) { |
218 } else if (arc.id % _width < _width - 1) { |
275 if (nid >= _edge_limit) { |
219 arc.id = _arcLimit + arc.id % _width + |
276 nid = (nid - _edge_limit) % (_width - 1) + |
220 (arc.id / _width) * (_width - 1); |
277 (nid - _edge_limit) / (_width - 1) * _width; |
221 } else { |
278 if (nid < _node_num - _width) { |
222 arc.id = -1; |
279 arc._id = nid << 1 | 1; |
223 } |
280 return; |
|
281 } |
|
282 } |
|
283 if (nid % _width > 0) { |
|
284 arc._id = (_edge_limit + nid % _width + |
|
285 (nid / _width) * (_width - 1) - 1) << 1; |
|
286 return; |
|
287 } |
|
288 if (nid >= _width) { |
|
289 arc._id = (nid - _width) << 1; |
|
290 return; |
|
291 } |
|
292 } else { |
|
293 if (nid >= _edge_limit) { |
|
294 nid = (nid - _edge_limit) % (_width - 1) + |
|
295 (nid - _edge_limit) / (_width - 1) * _width + 1; |
|
296 if (nid >= _width) { |
|
297 arc._id = (nid - _width) << 1; |
|
298 return; |
|
299 } |
|
300 } |
|
301 } |
|
302 arc._id = -1; |
224 } |
303 } |
225 |
304 |
226 void firstIn(Arc& arc, const Node& node) const { |
305 void firstIn(Arc& arc, const Node& node) const { |
227 if (node.id >= _width) { |
306 if (node._id % _width < _width - 1) { |
228 arc.id = node.id - _width; |
307 arc._id = (_edge_limit + node._id % _width + |
229 } else if (node.id % _width > 0) { |
308 (node._id / _width) * (_width - 1)) << 1; |
230 arc.id = _arcLimit + node.id % _width + |
309 return; |
231 (node.id / _width) * (_width - 1) - 1; |
310 } |
232 } else { |
311 if (node._id < _node_num - _width) { |
233 arc.id = -1; |
312 arc._id = node._id << 1; |
234 } |
313 return; |
|
314 } |
|
315 if (node._id % _width > 0) { |
|
316 arc._id = (_edge_limit + node._id % _width + |
|
317 (node._id / _width) * (_width - 1) - 1) << 1 | 1; |
|
318 return; |
|
319 } |
|
320 if (node._id >= _width) { |
|
321 arc._id = (node._id - _width) << 1 | 1; |
|
322 return; |
|
323 } |
|
324 arc._id = -1; |
235 } |
325 } |
236 |
326 |
237 void nextIn(Arc& arc) const { |
327 void nextIn(Arc& arc) const { |
238 if (arc.id >= _arcLimit) { |
328 int nid = arc._id >> 1; |
239 arc.id = -1; |
329 if ((arc._id & 1) == 0) { |
240 } else if (arc.id % _width > 0) { |
330 if (nid >= _edge_limit) { |
241 arc.id = _arcLimit + arc.id % _width + |
331 nid = (nid - _edge_limit) % (_width - 1) + |
242 (arc.id / _width + 1) * (_width - 1) - 1; |
332 (nid - _edge_limit) / (_width - 1) * _width; |
243 } else { |
333 if (nid < _node_num - _width) { |
244 arc.id = -1; |
334 arc._id = nid << 1; |
|
335 return; |
|
336 } |
|
337 } |
|
338 if (nid % _width > 0) { |
|
339 arc._id = (_edge_limit + nid % _width + |
|
340 (nid / _width) * (_width - 1) - 1) << 1 | 1; |
|
341 return; |
|
342 } |
|
343 if (nid >= _width) { |
|
344 arc._id = (nid - _width) << 1 | 1; |
|
345 return; |
|
346 } |
|
347 } else { |
|
348 if (nid >= _edge_limit) { |
|
349 nid = (nid - _edge_limit) % (_width - 1) + |
|
350 (nid - _edge_limit) / (_width - 1) * _width + 1; |
|
351 if (nid >= _width) { |
|
352 arc._id = (nid - _width) << 1 | 1; |
|
353 return; |
|
354 } |
|
355 } |
|
356 } |
|
357 arc._id = -1; |
|
358 } |
|
359 |
|
360 void firstInc(Edge& edge, bool& dir, const Node& node) const { |
|
361 if (node._id % _width < _width - 1) { |
|
362 edge._id = _edge_limit + node._id % _width + |
|
363 (node._id / _width) * (_width - 1); |
|
364 dir = true; |
|
365 return; |
|
366 } |
|
367 if (node._id < _node_num - _width) { |
|
368 edge._id = node._id; |
|
369 dir = true; |
|
370 return; |
|
371 } |
|
372 if (node._id % _width > 0) { |
|
373 edge._id = _edge_limit + node._id % _width + |
|
374 (node._id / _width) * (_width - 1) - 1; |
|
375 dir = false; |
|
376 return; |
|
377 } |
|
378 if (node._id >= _width) { |
|
379 edge._id = node._id - _width; |
|
380 dir = false; |
|
381 return; |
|
382 } |
|
383 edge._id = -1; |
|
384 dir = true; |
|
385 } |
|
386 |
|
387 void nextInc(Edge& edge, bool& dir) const { |
|
388 int nid = edge._id; |
|
389 if (dir) { |
|
390 if (nid >= _edge_limit) { |
|
391 nid = (nid - _edge_limit) % (_width - 1) + |
|
392 (nid - _edge_limit) / (_width - 1) * _width; |
|
393 if (nid < _node_num - _width) { |
|
394 edge._id = nid; |
|
395 return; |
|
396 } |
|
397 } |
|
398 if (nid % _width > 0) { |
|
399 edge._id = _edge_limit + nid % _width + |
|
400 (nid / _width) * (_width - 1) - 1; |
|
401 dir = false; |
|
402 return; |
|
403 } |
|
404 if (nid >= _width) { |
|
405 edge._id = nid - _width; |
|
406 dir = false; |
|
407 return; |
|
408 } |
|
409 } else { |
|
410 if (nid >= _edge_limit) { |
|
411 nid = (nid - _edge_limit) % (_width - 1) + |
|
412 (nid - _edge_limit) / (_width - 1) * _width + 1; |
|
413 if (nid >= _width) { |
|
414 edge._id = nid - _width; |
|
415 return; |
|
416 } |
|
417 } |
|
418 } |
|
419 edge._id = -1; |
|
420 dir = true; |
|
421 } |
|
422 |
|
423 Arc right(Node n) const { |
|
424 if (n._id % _width < _width - 1) { |
|
425 return Arc(((_edge_limit + n._id % _width + |
|
426 (n._id / _width) * (_width - 1)) << 1) | 1); |
|
427 } else { |
|
428 return INVALID; |
|
429 } |
|
430 } |
|
431 |
|
432 Arc left(Node n) const { |
|
433 if (n._id % _width > 0) { |
|
434 return Arc((_edge_limit + n._id % _width + |
|
435 (n._id / _width) * (_width - 1) - 1) << 1); |
|
436 } else { |
|
437 return INVALID; |
|
438 } |
|
439 } |
|
440 |
|
441 Arc up(Node n) const { |
|
442 if (n._id < _edge_limit) { |
|
443 return Arc((n._id << 1) | 1); |
|
444 } else { |
|
445 return INVALID; |
|
446 } |
|
447 } |
|
448 |
|
449 Arc down(Node n) const { |
|
450 if (n._id >= _width) { |
|
451 return Arc((n._id - _width) << 1); |
|
452 } else { |
|
453 return INVALID; |
245 } |
454 } |
246 } |
455 } |
247 |
456 |
248 private: |
457 private: |
249 int _width, _height; |
458 int _width, _height; |
250 int _nodeNum, _arcNum; |
459 int _node_num, _edge_num; |
251 int _arcLimit; |
460 int _edge_limit; |
252 }; |
461 }; |
253 |
462 |
254 typedef GraphExtender<UndirDigraphExtender<GridGraphBase> > |
463 |
255 ExtendedGridGraphBase; |
464 typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase; |
256 |
465 |
257 /// \ingroup graphs |
466 /// \ingroup graphs |
258 /// |
467 /// |
259 /// \brief Grid graph class |
468 /// \brief Grid graph class |
260 /// |
469 /// |
261 /// This class implements a special graph type. The nodes of the |
470 /// This class implements a special graph type. The nodes of the |
262 /// graph can be indiced by two integer \c (i,j) value where \c i |
471 /// graph can be indexed by two integer \c (i,j) value where \c i is |
263 /// is in the \c [0,width) range and j is in the [0, height) range. |
472 /// in the \c [0..width()-1] range and j is in the \c |
264 /// Two nodes are connected in the graph if the indices differ only |
473 /// [0..height()-1] range. Two nodes are connected in the graph if |
265 /// on one position and only one is the difference. |
474 /// the indexes differ exactly on one position and exactly one is |
|
475 /// the difference. The nodes of the graph be indexed by position |
|
476 /// with \c operator()() function. The positions of the nodes can be |
|
477 /// get with \c pos(), \c col() and \c row() members. The outgoing |
|
478 /// arcs can be retrieved with the \c right(), \c up(), \c left() |
|
479 /// and \c down() functions, where the bottom-left corner is the |
|
480 /// origin. |
266 /// |
481 /// |
267 /// \image html grid_graph.png |
482 /// \image html grid_graph.png |
268 /// \image latex grid_graph.eps "Grid graph" width=\textwidth |
483 /// \image latex grid_graph.eps "Grid digraph" row_num=\textrow_num |
269 /// |
484 /// |
270 /// The graph can be indiced in the following way: |
485 /// A short example about the basic usage: |
271 ///\code |
486 ///\code |
272 /// GridGraph gr(w, h); |
487 /// GridGraph graph(rows, cols); |
273 /// GridGraph::NodeMap<int> val(gr); |
488 /// GridGraph::NodeMap<int> val(graph); |
274 /// for (int i = 0; i < gr.width(); ++i) { |
489 /// for (int i = 0; i < graph.width(); ++i) { |
275 /// for (int j = 0; j < gr.height(); ++j) { |
490 /// for (int j = 0; j < graph.height(); ++j) { |
276 /// val[gr(i, j)] = i + j; |
491 /// val[graph(i, j)] = i + j; |
277 /// } |
492 /// } |
278 /// } |
493 /// } |
279 ///\endcode |
494 ///\endcode |
280 /// |
495 /// |
281 /// This graph type is fully conform to the \ref concepts::Graph |
496 /// The graph type is fully conform to the \ref concepts::Graph |
282 /// "Undirected Graph" concept, and it also has an important extra |
497 /// "Graph" concept, and it also has an important extra feature |
283 /// feature that its maps are real \ref concepts::ReferenceMap |
498 /// that its maps are real \ref concepts::ReferenceMap "reference |
284 /// "reference map"s. |
499 /// map"s. |
285 class GridGraph : public ExtendedGridGraphBase { |
500 class GridGraph : public ExtendedGridGraphBase { |
286 public: |
501 public: |
287 |
502 |
288 typedef ExtendedGridGraphBase Parent; |
503 typedef ExtendedGridGraphBase Parent; |
289 |
504 |
290 /// \brief Map to get the indices of the nodes as dim2::Point<int>. |
505 /// \brief Map to get the indices of the nodes as dim2::Point<int>. |
291 /// |
506 /// |
292 /// Map to get the indices of the nodes as dim2::Point<int>. |
507 /// Map to get the indices of the nodes as dim2::Point<int>. |
293 class IndexMap { |
508 class IndexMap { |
294 public: |
509 public: |
295 /// The key type of the map |
510 /// \brief The key type of the map |
296 typedef GridGraph::Node Key; |
511 typedef GridGraph::Node Key; |
297 /// The value type of the map |
512 /// \brief The value type of the map |
298 typedef dim2::Point<int> Value; |
513 typedef dim2::Point<int> Value; |
299 |
514 |
|
515 /// \brief Constructor |
|
516 /// |
300 /// Constructor |
517 /// Constructor |
301 IndexMap(const GridGraph& graph) : _graph(graph) {} |
518 IndexMap(const GridGraph& graph) : _graph(graph) {} |
302 |
519 |
303 /// The subscript operator |
520 /// \brief The subscript operator |
304 Value operator[](const Key& key) const { |
521 /// |
305 return dim2::Point<int>(_graph.row(key), _graph.col(key)); |
522 /// The subscript operator. |
|
523 Value operator[](Key key) const { |
|
524 return _graph.pos(key); |
306 } |
525 } |
307 |
526 |
308 private: |
527 private: |
309 const GridGraph& _graph; |
528 const GridGraph& _graph; |
310 }; |
529 }; |
311 |
530 |
|
531 /// \brief Map to get the column of the nodes. |
|
532 /// |
|
533 /// Map to get the column of the nodes. |
|
534 class ColMap { |
|
535 public: |
|
536 /// \brief The key type of the map |
|
537 typedef GridGraph::Node Key; |
|
538 /// \brief The value type of the map |
|
539 typedef int Value; |
|
540 |
|
541 /// \brief Constructor |
|
542 /// |
|
543 /// Constructor |
|
544 ColMap(const GridGraph& graph) : _graph(graph) {} |
|
545 |
|
546 /// \brief The subscript operator |
|
547 /// |
|
548 /// The subscript operator. |
|
549 Value operator[](Key key) const { |
|
550 return _graph.col(key); |
|
551 } |
|
552 |
|
553 private: |
|
554 const GridGraph& _graph; |
|
555 }; |
|
556 |
312 /// \brief Map to get the row of the nodes. |
557 /// \brief Map to get the row of the nodes. |
313 /// |
558 /// |
314 /// Map to get the row of the nodes. |
559 /// Map to get the row of the nodes. |
315 class RowMap { |
560 class RowMap { |
316 public: |
561 public: |
317 /// The key type of the map |
562 /// \brief The key type of the map |
318 typedef GridGraph::Node Key; |
563 typedef GridGraph::Node Key; |
319 /// The value type of the map |
564 /// \brief The value type of the map |
320 typedef int Value; |
565 typedef int Value; |
321 |
566 |
|
567 /// \brief Constructor |
|
568 /// |
322 /// Constructor |
569 /// Constructor |
323 RowMap(const GridGraph& graph) : _graph(graph) {} |
570 RowMap(const GridGraph& graph) : _graph(graph) {} |
324 |
571 |
325 /// The subscript operator |
572 /// \brief The subscript operator |
326 Value operator[](const Key& key) const { |
573 /// |
|
574 /// The subscript operator. |
|
575 Value operator[](Key key) const { |
327 return _graph.row(key); |
576 return _graph.row(key); |
328 } |
577 } |
329 |
578 |
330 private: |
579 private: |
331 const GridGraph& _graph; |
580 const GridGraph& _graph; |
332 }; |
581 }; |
333 |
582 |
334 /// \brief Map to get the column of the nodes. |
|
335 /// |
|
336 /// Map to get the column of the nodes. |
|
337 class ColMap { |
|
338 public: |
|
339 /// The key type of the map |
|
340 typedef GridGraph::Node Key; |
|
341 /// The value type of the map |
|
342 typedef int Value; |
|
343 |
|
344 /// Constructor |
|
345 ColMap(const GridGraph& graph) : _graph(graph) {} |
|
346 |
|
347 /// The subscript operator |
|
348 Value operator[](const Key& key) const { |
|
349 return _graph.col(key); |
|
350 } |
|
351 |
|
352 private: |
|
353 const GridGraph& _graph; |
|
354 }; |
|
355 |
|
356 /// \brief Constructor |
583 /// \brief Constructor |
357 /// |
584 /// |
358 /// Constructor. |
585 /// Construct a grid graph with given size. |
359 /// \param width The width of the grid. |
|
360 /// \param height The height of the grid. |
|
361 GridGraph(int width, int height) { construct(width, height); } |
586 GridGraph(int width, int height) { construct(width, height); } |
362 |
587 |
363 /// \brief Resize the graph |
588 /// \brief Resize the graph |
364 /// |
589 /// |
365 /// Resize the grid. |
590 /// Resize the graph. The function will fully destroy and rebuild |
|
591 /// the graph. This cause that the maps of the graph will |
|
592 /// reallocated automatically and the previous values will be |
|
593 /// lost. |
366 void resize(int width, int height) { |
594 void resize(int width, int height) { |
367 Parent::notifier(Arc()).clear(); |
595 Parent::notifier(Arc()).clear(); |
368 Parent::notifier(Edge()).clear(); |
596 Parent::notifier(Edge()).clear(); |
369 Parent::notifier(Node()).clear(); |
597 Parent::notifier(Node()).clear(); |
370 construct(width, height); |
598 construct(width, height); |
378 /// Gives back the node on the given position. |
606 /// Gives back the node on the given position. |
379 Node operator()(int i, int j) const { |
607 Node operator()(int i, int j) const { |
380 return Parent::operator()(i, j); |
608 return Parent::operator()(i, j); |
381 } |
609 } |
382 |
610 |
|
611 /// \brief Gives back the column index of the node. |
|
612 /// |
|
613 /// Gives back the column index of the node. |
|
614 int col(Node n) const { |
|
615 return Parent::col(n); |
|
616 } |
|
617 |
383 /// \brief Gives back the row index of the node. |
618 /// \brief Gives back the row index of the node. |
384 /// |
619 /// |
385 /// Gives back the row index of the node. |
620 /// Gives back the row index of the node. |
386 int row(Node n) const { |
621 int row(Node n) const { |
387 return Parent::row(n); |
622 return Parent::row(n); |
388 } |
623 } |
389 |
624 |
390 /// \brief Gives back the column index of the node. |
625 /// \brief Gives back the position of the node. |
391 /// |
626 /// |
392 /// Gives back the column index of the node. |
627 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair. |
393 int col(Node n) const { |
628 dim2::Point<int> pos(Node n) const { |
394 return Parent::col(n); |
629 return Parent::pos(n); |
395 } |
630 } |
396 |
631 |
397 /// \brief Gives back the width of the grid. |
632 /// \brief Gives back the number of the columns. |
398 /// |
633 /// |
399 /// Gives back the width of the grid. |
634 /// Gives back the number of the columns. |
400 int width() const { |
635 int width() const { |
401 return Parent::width(); |
636 return Parent::width(); |
402 } |
637 } |
403 |
638 |
404 /// \brief Gives back the height of the grid. |
639 /// \brief Gives back the number of the rows. |
405 /// |
640 /// |
406 /// Gives back the height of the grid. |
641 /// Gives back the number of the rows. |
407 int height() const { |
642 int height() const { |
408 return Parent::height(); |
643 return Parent::height(); |
409 } |
644 } |
410 |
645 |
|
646 /// \brief Gives back the arc goes right from the node. |
|
647 /// |
|
648 /// Gives back the arc goes right from the node. If there is not |
|
649 /// outgoing arc then it gives back INVALID. |
|
650 Arc right(Node n) const { |
|
651 return Parent::right(n); |
|
652 } |
|
653 |
|
654 /// \brief Gives back the arc goes left from the node. |
|
655 /// |
|
656 /// Gives back the arc goes left from the node. If there is not |
|
657 /// outgoing arc then it gives back INVALID. |
|
658 Arc left(Node n) const { |
|
659 return Parent::left(n); |
|
660 } |
|
661 |
|
662 /// \brief Gives back the arc goes up from the node. |
|
663 /// |
|
664 /// Gives back the arc goes up from the node. If there is not |
|
665 /// outgoing arc then it gives back INVALID. |
|
666 Arc up(Node n) const { |
|
667 return Parent::up(n); |
|
668 } |
|
669 |
411 /// \brief Gives back the arc goes down from the node. |
670 /// \brief Gives back the arc goes down from the node. |
412 /// |
671 /// |
413 /// Gives back the arc goes down from the node. If there is not |
672 /// Gives back the arc goes down from the node. If there is not |
414 /// outgoing arc then it gives back \c INVALID. |
673 /// outgoing arc then it gives back INVALID. |
415 Arc down(Node n) const { |
674 Arc down(Node n) const { |
416 Edge e = _down(n); |
675 return Parent::down(n); |
417 return e != INVALID ? direct(e, true) : INVALID; |
676 } |
418 } |
677 |
419 |
678 /// \brief Index map of the grid graph |
420 /// \brief Gives back the arc goes up from the node. |
679 /// |
421 /// |
680 /// Just returns an IndexMap for the grid graph. |
422 /// Gives back the arc goes up from the node. If there is not |
681 IndexMap indexMap() const { |
423 /// outgoing arc then it gives back \c INVALID. |
682 return IndexMap(*this); |
424 Arc up(Node n) const { |
683 } |
425 Edge e = _up(n); |
684 |
426 return e != INVALID ? direct(e, false) : INVALID; |
685 /// \brief Row map of the grid graph |
427 } |
686 /// |
428 |
687 /// Just returns a RowMap for the grid graph. |
429 /// \brief Gives back the arc goes right from the node. |
688 RowMap rowMap() const { |
430 /// |
689 return RowMap(*this); |
431 /// Gives back the arc goes right from the node. If there is not |
690 } |
432 /// outgoing arc then it gives back \c INVALID. |
691 |
433 Arc right(Node n) const { |
692 /// \brief Column map of the grid graph |
434 Edge e = _right(n); |
693 /// |
435 return e != INVALID ? direct(e, true) : INVALID; |
694 /// Just returns a ColMap for the grid graph. |
436 } |
695 ColMap colMap() const { |
437 |
696 return ColMap(*this); |
438 /// \brief Gives back the arc goes left from the node. |
697 } |
439 /// |
698 |
440 /// Gives back the arc goes left from the node. If there is not |
699 }; |
441 /// outgoing arc then it gives back \c INVALID. |
700 |
442 Arc left(Node n) const { |
|
443 Edge e = _left(n); |
|
444 return e != INVALID ? direct(e, false) : INVALID; |
|
445 } |
|
446 |
|
447 }; // class GridGraph |
|
448 |
|
449 /// \brief Index map of the grid graph |
|
450 /// |
|
451 /// Just returns an IndexMap for the grid graph. |
|
452 inline GridGraph::IndexMap indexMap(const GridGraph& graph) { |
|
453 return GridGraph::IndexMap(graph); |
|
454 } |
|
455 |
|
456 /// \brief Row map of the grid graph |
|
457 /// |
|
458 /// Just returns a RowMap for the grid graph. |
|
459 inline GridGraph::RowMap rowMap(const GridGraph& graph) { |
|
460 return GridGraph::RowMap(graph); |
|
461 } |
|
462 |
|
463 /// \brief Column map of the grid graph |
|
464 /// |
|
465 /// Just returns a ColMap for the grid graph. |
|
466 inline GridGraph::ColMap colMap(const GridGraph& graph) { |
|
467 return GridGraph::ColMap(graph); |
|
468 } |
|
469 } |
701 } |
470 |
702 #endif |
471 #endif // GRID_GRAPH_H |
|