Changeset 1680:4f8b9cee576b in lemon-0.x for lemon
- Timestamp:
- 09/12/05 11:19:52 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2199
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/grid_graph.h
r1623 r1680 48 48 /// 49 49 /// Creates a grid graph with the given size. 50 void construct(int height, int width) {50 void construct(int width, int height) { 51 51 _height = height; _width = width; 52 52 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; 53 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 105 public: … … 60 109 /// Gives back the node on the given position. 61 110 Node operator()(int i, int j) const { 62 return Node(i * _width + j);111 return Node(i + j * _width); 63 112 } 64 113 … … 73 122 /// 74 123 /// Gives back the coloumn index of the node. 75 int col(Node n ode) const {124 int col(Node n) const { 76 125 return n.id % _width; 77 126 } … … 278 327 279 328 280 typedef UndirGraphExtender<GridGraphBase> 281 UndirGridGraphBase; 282 typedef AlterableUndirGraphExtender<UndirGridGraphBase> 283 AlterableGridGraphBase; 284 typedef IterableUndirGraphExtender<AlterableGridGraphBase> 285 IterableGridGraphBase; 286 typedef MappableUndirGraphExtender<IterableGridGraphBase> 287 MappableGridGraphBase; 329 typedef MappableUndirGraphExtender< 330 IterableUndirGraphExtender< 331 AlterableUndirGraphExtender< 332 UndirGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase; 288 333 289 334 /// \ingroup graphs … … 312 357 /// 313 358 /// \author Balazs Dezso 314 class GridGraph : public MappableGridGraphBase {359 class GridGraph : public ExtendedGridGraphBase { 315 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 }
Note: See TracChangeset
for help on using the changeset viewer.