45 protected: |
45 protected: |
46 |
46 |
47 /// \brief Creates a grid graph with the given size. |
47 /// \brief Creates a grid graph with the given size. |
48 /// |
48 /// |
49 /// Creates a grid graph with the given size. |
49 /// Creates a grid graph with the given size. |
50 void construct(int height, int width) { |
50 void construct(int width, int height) { |
51 _height = height; _width = width; |
51 _height = height; _width = width; |
52 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; |
52 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; |
53 _edgeLimit = _nodeNum - width; |
53 _edgeLimit = _nodeNum - width; |
54 } |
54 } |
|
55 |
|
56 /// \brief Gives back the edge goes down from the node. |
|
57 /// |
|
58 /// Gives back the edge goes down from the node. If there is not |
|
59 /// outgoing edge then it gives back INVALID. |
|
60 Edge _down(Node n) const { |
|
61 if (n.id < _nodeNum - _width) { |
|
62 return Edge(n.id); |
|
63 } else { |
|
64 return INVALID; |
|
65 } |
|
66 } |
|
67 |
|
68 /// \brief Gives back the edge comes from up into the node. |
|
69 /// |
|
70 /// Gives back the edge comes from up into the node. If there is not |
|
71 /// incoming edge then it gives back INVALID. |
|
72 Edge _up(Node n) const { |
|
73 if (n.id >= _width) { |
|
74 return Edge(n.id - _width); |
|
75 } else { |
|
76 return INVALID; |
|
77 } |
|
78 } |
|
79 |
|
80 /// \brief Gives back the edge goes right from the node. |
|
81 /// |
|
82 /// Gives back the edge goes right from the node. If there is not |
|
83 /// outgoing edge then it gives back INVALID. |
|
84 Edge _right(Node n) const { |
|
85 if (n.id % _width < _width - 1) { |
|
86 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1); |
|
87 } else { |
|
88 return INVALID; |
|
89 } |
|
90 } |
|
91 |
|
92 /// \brief Gives back the edge comes from left into the node. |
|
93 /// |
|
94 /// Gives back the edge comes left up into the node. If there is not |
|
95 /// incoming edge then it gives back INVALID. |
|
96 Edge _left(Node n) const { |
|
97 if (n.id % _width > 0) { |
|
98 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; |
|
99 } else { |
|
100 return INVALID; |
|
101 } |
|
102 } |
|
103 |
55 |
104 |
56 public: |
105 public: |
57 |
106 |
58 /// \brief The node on the given position. |
107 /// \brief The node on the given position. |
59 /// |
108 /// |
60 /// Gives back the node on the given position. |
109 /// Gives back the node on the given position. |
61 Node operator()(int i, int j) const { |
110 Node operator()(int i, int j) const { |
62 return Node(i * _width + j); |
111 return Node(i + j * _width); |
63 } |
112 } |
64 |
113 |
65 /// \brief Gives back the row index of the node. |
114 /// \brief Gives back the row index of the node. |
66 /// |
115 /// |
67 /// Gives back the row index of the node. |
116 /// Gives back the row index of the node. |
275 int _nodeNum, _edgeNum; |
324 int _nodeNum, _edgeNum; |
276 int _edgeLimit; |
325 int _edgeLimit; |
277 }; |
326 }; |
278 |
327 |
279 |
328 |
280 typedef UndirGraphExtender<GridGraphBase> |
329 typedef MappableUndirGraphExtender< |
281 UndirGridGraphBase; |
330 IterableUndirGraphExtender< |
282 typedef AlterableUndirGraphExtender<UndirGridGraphBase> |
331 AlterableUndirGraphExtender< |
283 AlterableGridGraphBase; |
332 UndirGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase; |
284 typedef IterableUndirGraphExtender<AlterableGridGraphBase> |
|
285 IterableGridGraphBase; |
|
286 typedef MappableUndirGraphExtender<IterableGridGraphBase> |
|
287 MappableGridGraphBase; |
|
288 |
333 |
289 /// \ingroup graphs |
334 /// \ingroup graphs |
290 /// |
335 /// |
291 /// \brief Grid graph class |
336 /// \brief Grid graph class |
292 /// |
337 /// |
309 /// |
354 /// |
310 /// The graph type is fully conform to the \ref concept::UndirGraph |
355 /// The graph type is fully conform to the \ref concept::UndirGraph |
311 /// "Undirected Graph" concept. |
356 /// "Undirected Graph" concept. |
312 /// |
357 /// |
313 /// \author Balazs Dezso |
358 /// \author Balazs Dezso |
314 class GridGraph : public MappableGridGraphBase { |
359 class GridGraph : public ExtendedGridGraphBase { |
315 public: |
360 public: |
316 |
361 |
317 GridGraph(int m, int n) { construct(m, n); } |
362 GridGraph(int n, int m) { construct(n, m); } |
|
363 |
|
364 /// \brief Gives back the edge goes down from the node. |
|
365 /// |
|
366 /// Gives back the edge goes down from the node. If there is not |
|
367 /// outgoing edge then it gives back INVALID. |
|
368 Edge down(Node n) const { |
|
369 UndirEdge ue = _down(n); |
|
370 return ue != INVALID ? direct(ue, true) : INVALID; |
|
371 } |
|
372 |
|
373 /// \brief Gives back the edge goes up from the node. |
|
374 /// |
|
375 /// Gives back the edge goes up from the node. If there is not |
|
376 /// outgoing edge then it gives back INVALID. |
|
377 Edge up(Node n) const { |
|
378 UndirEdge ue = _up(n); |
|
379 return ue != INVALID ? direct(ue, false) : INVALID; |
|
380 } |
|
381 |
|
382 /// \brief Gives back the edge goes right from the node. |
|
383 /// |
|
384 /// Gives back the edge goes right from the node. If there is not |
|
385 /// outgoing edge then it gives back INVALID. |
|
386 Edge right(Node n) const { |
|
387 UndirEdge ue = _right(n); |
|
388 return ue != INVALID ? direct(ue, true) : INVALID; |
|
389 } |
|
390 |
|
391 /// \brief Gives back the edge goes left from the node. |
|
392 /// |
|
393 /// Gives back the edge goes left from the node. If there is not |
|
394 /// outgoing edge then it gives back INVALID. |
|
395 Edge left(Node n) const { |
|
396 UndirEdge ue = _left(n); |
|
397 return ue != INVALID ? direct(ue, false) : INVALID; |
|
398 } |
|
399 |
318 }; |
400 }; |
319 } |
401 } |
320 #endif |
402 #endif |