Changeset 335:160bf92c7cdc in lemonmain for lemon/grid_graph.h
 Timestamp:
 10/20/08 12:36:02 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/grid_graph.h
r334 r335 20 20 #define GRID_GRAPH_H 21 21 22 #include <iostream>23 22 #include <lemon/core.h> 23 #include <lemon/bits/graph_extender.h> 24 #include <lemon/dim2.h> 24 25 #include <lemon/assert.h> 25 26 #include <lemon/bits/base_extender.h>27 #include <lemon/bits/graph_extender.h>28 29 #include <lemon/dim2.h>30 26 31 27 ///\ingroup graphs … … 42 38 43 39 class Node; 40 class Edge; 44 41 class Arc; 45 42 … … 50 47 protected: 51 48 52 void construct(int w, int h) { 53 _height = h; _width = w; 54 _nodeNum = h * w; _arcNum = 2 * _nodeNum  w  h; 55 _arcLimit = _nodeNum  w; 56 } 57 58 Arc _down(Node n) const { 59 if (n.id < _nodeNum  _width) { 60 return Arc(n.id); 61 } else { 62 return INVALID; 63 } 64 } 65 66 Arc _up(Node n) const { 67 if (n.id >= _width) { 68 return Arc(n.id  _width); 69 } else { 70 return INVALID; 71 } 72 } 73 74 Arc _right(Node n) const { 75 if (n.id % _width < _width  1) { 76 return _arcLimit + n.id % _width + (n.id / _width) * (_width  1); 77 } else { 78 return INVALID; 79 } 80 } 81 82 Arc _left(Node n) const { 83 if (n.id % _width > 0) { 84 return _arcLimit + n.id % _width + (n.id / _width) * (_width  1)  1; 85 } else { 86 return INVALID; 87 } 49 void construct(int width, int height) { 50 _width = width; _height = height; 51 _node_num = width * height; 52 _edge_num = 2 * _node_num  width  height; 53 _edge_limit = _node_num  _width; 88 54 } 89 55 … … 91 57 92 58 Node operator()(int i, int j) const { 93 LEMON_ ASSERT(0 <= i && i < width()&&94 0 <= j && j < height(), "lemon::GridGraph::IndexError");59 LEMON_DEBUG(0 <= i && i < _width && 60 0 <= j && j < _height, "Index out of range"); 95 61 return Node(i + j * _width); 96 62 } 97 63 64 int col(Node n) const { 65 return n._id % _width; 66 } 67 98 68 int row(Node n) const { 99 return n. id / _width;100 } 101 102 int col(Node n) const {103 return n.id % _width;69 return n._id / _width; 70 } 71 72 dim2::Point<int> pos(Node n) const { 73 return dim2::Point<int>(col(n), row(n)); 104 74 } 105 75 … … 115 85 typedef True ArcNumTag; 116 86 117 int nodeNum() const { return _nodeNum; } 118 int arcNum() const { return _arcNum; } 119 120 int maxNodeId() const { return nodeNum()  1; } 121 int maxArcId() const { return arcNum()  1; } 122 123 Node source(Arc e) const { 124 if (e.id < _arcLimit) { 125 return e.id; 126 } else { 127 return (e.id  _arcLimit) % (_width  1) + 128 (e.id  _arcLimit) / (_width  1) * _width; 129 } 130 } 131 132 Node target(Arc e) const { 133 if (e.id < _arcLimit) { 134 return e.id + _width; 135 } else { 136 return (e.id  _arcLimit) % (_width  1) + 137 (e.id  _arcLimit) / (_width  1) * _width + 1; 138 } 139 } 140 141 static int id(Node v) { return v.id; } 142 static int id(Arc e) { return e.id; } 87 int nodeNum() const { return _node_num; } 88 int edgeNum() const { return _edge_num; } 89 int arcNum() const { return 2 * _edge_num; } 90 91 Node u(Edge edge) const { 92 if (edge._id < _edge_limit) { 93 return edge._id; 94 } else { 95 return (edge._id  _edge_limit) % (_width  1) + 96 (edge._id  _edge_limit) / (_width  1) * _width; 97 } 98 } 99 100 Node v(Edge edge) const { 101 if (edge._id < _edge_limit) { 102 return edge._id + _width; 103 } else { 104 return (edge._id  _edge_limit) % (_width  1) + 105 (edge._id  _edge_limit) / (_width  1) * _width + 1; 106 } 107 } 108 109 Node source(Arc arc) const { 110 return (arc._id & 1) == 1 ? u(arc) : v(arc); 111 } 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 125 static Node nodeFromId(int id) { return Node(id);} 145 126 static Edge edgeFromId(int id) { return Edge(id);} 146 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 151 Arc findArc(Node u, Node v, Arc prev = INVALID) const { 151 152 if (prev != INVALID) return INVALID; 152 if (v.id  u.id == _width) return Arc(u.id); 153 if (v.id  u.id == 1 && u.id % _width < _width  1) { 154 return Arc(u.id / _width * (_width  1) + 155 u.id % _width + _arcLimit); 153 if (v._id > u._id) { 154 if (v._id  u._id == _width) 155 return Arc((u._id << 1)  1); 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 168 return INVALID; … … 162 173 163 174 protected: 164 int id;165 Node(int _id) : id(_id) {}175 int _id; 176 Node(int id) : _id(id) {} 166 177 public: 167 178 Node() {} 168 Node (Invalid) { id = 1; } 169 bool operator==(const Node node) const { return id == node.id; } 170 bool operator!=(const Node node) const { return id != node.id; } 171 bool operator<(const Node node) const { return id < node.id; } 179 Node (Invalid) : _id(1) {} 180 bool operator==(const Node node) const {return _id == node._id;} 181 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 … … 176 203 177 204 protected: 178 int id; 179 Arc(int _id) : id(_id) {} 205 int _id; 206 207 Arc(int id) : _id(id) {} 208 180 209 public: 181 210 Arc() {} 182 Arc (Invalid) { id = 1; } 183 bool operator==(const Arc arc) const { return id == arc.id; } 184 bool operator!=(const Arc arc) const { return id != arc.id; } 185 bool operator<(const Arc arc) const { return id < arc.id; } 211 Arc (Invalid) : _id(1) {} 212 operator Edge() const { return _id != 1 ? Edge(_id >> 1) : INVALID; } 213 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 226 void first(Node& node) const { 189 node. id = nodeNum() 1;227 node._id = _node_num  1; 190 228 } 191 229 192 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 242 void first(Arc& arc) const { 197 arc. id = arcNum() 1;243 arc._id = 2 * _edge_num  1; 198 244 } 199 245 200 246 static void next(Arc& arc) { 201 arc. id;247 arc._id; 202 248 } 203 249 204 250 void firstOut(Arc& arc, const Node& node) const { 205 if (node.id < _nodeNum  _width) { 206 arc.id = node.id; 207 } else if (node.id % _width < _width  1) { 208 arc.id = _arcLimit + node.id % _width + 209 (node.id / _width) * (_width  1); 210 } else { 211 arc.id = 1; 212 } 251 if (node._id % _width < _width  1) { 252 arc._id = (_edge_limit + node._id % _width + 253 (node._id / _width) * (_width  1)) << 1  1; 254 return; 255 } 256 if (node._id < _node_num  _width) { 257 arc._id = node._id << 1  1; 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 272 void nextOut(Arc& arc) const { 216 if (arc.id >= _arcLimit) { 217 arc.id = 1; 218 } else if (arc.id % _width < _width  1) { 219 arc.id = _arcLimit + arc.id % _width + 220 (arc.id / _width) * (_width  1); 221 } else { 222 arc.id = 1; 223 } 273 int nid = arc._id >> 1; 274 if ((arc._id & 1) == 1) { 275 if (nid >= _edge_limit) { 276 nid = (nid  _edge_limit) % (_width  1) + 277 (nid  _edge_limit) / (_width  1) * _width; 278 if (nid < _node_num  _width) { 279 arc._id = nid << 1  1; 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 305 void firstIn(Arc& arc, const Node& node) const { 227 if (node.id >= _width) { 228 arc.id = node.id  _width; 229 } else if (node.id % _width > 0) { 230 arc.id = _arcLimit + node.id % _width + 231 (node.id / _width) * (_width  1)  1; 232 } else { 233 arc.id = 1; 234 } 306 if (node._id % _width < _width  1) { 307 arc._id = (_edge_limit + node._id % _width + 308 (node._id / _width) * (_width  1)) << 1; 309 return; 310 } 311 if (node._id < _node_num  _width) { 312 arc._id = node._id << 1; 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 327 void nextIn(Arc& arc) const { 238 if (arc.id >= _arcLimit) { 239 arc.id = 1; 240 } else if (arc.id % _width > 0) { 241 arc.id = _arcLimit + arc.id % _width + 242 (arc.id / _width + 1) * (_width  1)  1; 243 } else { 244 arc.id = 1; 328 int nid = arc._id >> 1; 329 if ((arc._id & 1) == 0) { 330 if (nid >= _edge_limit) { 331 nid = (nid  _edge_limit) % (_width  1) + 332 (nid  _edge_limit) / (_width  1) * _width; 333 if (nid < _node_num  _width) { 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 } … … 248 457 private: 249 458 int _width, _height; 250 int _node Num, _arcNum;251 int _ arcLimit;459 int _node_num, _edge_num; 460 int _edge_limit; 252 461 }; 253 462 254 typedef GraphExtender<UndirDigraphExtender<GridGraphBase> > 255 463 464 typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase; 256 465 257 466 /// \ingroup graphs … … 260 469 /// 261 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 263 /// is in the \c [0,width) range and j is in the [0, height) range. 264 /// Two nodes are connected in the graph if the indices differ only 265 /// on one position and only one is the difference. 471 /// graph can be indexed by two integer \c (i,j) value where \c i is 472 /// in the \c [0..width()1] range and j is in the \c 473 /// [0..height()1] range. Two nodes are connected in the graph if 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 bottomleft corner is the 480 /// origin. 266 481 /// 267 482 /// \image html grid_graph.png 268 /// \image latex grid_graph.eps "Grid graph" width=\textwidth483 /// \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 486 ///\code 272 /// GridGraph gr (w, h);273 /// GridGraph::NodeMap<int> val(gr );274 /// for (int i = 0; i < gr .width(); ++i) {275 /// for (int j = 0; j < gr .height(); ++j) {276 /// val[gr (i, j)] = i + j;487 /// GridGraph graph(rows, cols); 488 /// GridGraph::NodeMap<int> val(graph); 489 /// for (int i = 0; i < graph.width(); ++i) { 490 /// for (int j = 0; j < graph.height(); ++j) { 491 /// val[graph(i, j)] = i + j; 277 492 /// } 278 493 /// } 279 494 ///\endcode 280 495 /// 281 /// Th isgraph type is fully conform to the \ref concepts::Graph282 /// " Undirected Graph" concept, and it also has an important extra283 /// feature that its maps are real \ref concepts::ReferenceMap284 /// "referencemap"s.496 /// The graph type is fully conform to the \ref concepts::Graph 497 /// "Graph" concept, and it also has an important extra feature 498 /// that its maps are real \ref concepts::ReferenceMap "reference 499 /// map"s. 285 500 class GridGraph : public ExtendedGridGraphBase { 286 501 public: … … 293 508 class IndexMap { 294 509 public: 295 /// The key type of the map510 /// \brief The key type of the map 296 511 typedef GridGraph::Node Key; 297 /// The value type of the map512 /// \brief The value type of the map 298 513 typedef dim2::Point<int> Value; 299 514 515 /// \brief Constructor 516 /// 300 517 /// Constructor 301 518 IndexMap(const GridGraph& graph) : _graph(graph) {} 302 519 303 /// The subscript operator 304 Value operator[](const Key& key) const { 305 return dim2::Point<int>(_graph.row(key), _graph.col(key)); 520 /// \brief The subscript operator 521 /// 522 /// The subscript operator. 523 Value operator[](Key key) const { 524 return _graph.pos(key); 306 525 } 307 526 … … 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 557 /// \brief Map to get the row of the nodes. 313 558 /// … … 315 560 class RowMap { 316 561 public: 317 /// The key type of the map562 /// \brief The key type of the map 318 563 typedef GridGraph::Node Key; 319 /// The value type of the map564 /// \brief The value type of the map 320 565 typedef int Value; 321 566 567 /// \brief Constructor 568 /// 322 569 /// Constructor 323 570 RowMap(const GridGraph& graph) : _graph(graph) {} 324 571 325 /// The subscript operator 326 Value operator[](const Key& key) const { 572 /// \brief The subscript operator 573 /// 574 /// The subscript operator. 575 Value operator[](Key key) const { 327 576 return _graph.row(key); 328 577 } … … 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 map340 typedef GridGraph::Node Key;341 /// The value type of the map342 typedef int Value;343 344 /// Constructor345 ColMap(const GridGraph& graph) : _graph(graph) {}346 347 /// The subscript operator348 Value operator[](const Key& key) const {349 return _graph.col(key);350 }351 352 private:353 const GridGraph& _graph;354 };355 356 583 /// \brief Constructor 357 584 /// 358 /// Constructor. 359 /// \param width The width of the grid. 360 /// \param height The height of the grid. 585 /// Construct a grid graph with given size. 361 586 GridGraph(int width, int height) { construct(width, height); } 362 587 363 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 594 void resize(int width, int height) { 367 595 Parent::notifier(Arc()).clear(); … … 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 618 /// \brief Gives back the row index of the node. 384 619 /// … … 388 623 } 389 624 390 /// \brief Gives back the column indexof the node.391 /// 392 /// Gives back the column index of the node.393 int col(Node n) const {394 return Parent:: col(n);395 } 396 397 /// \brief Gives back the width of the grid.398 /// 399 /// Gives back the width of the grid.625 /// \brief Gives back the position of the node. 626 /// 627 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair. 628 dim2::Point<int> pos(Node n) const { 629 return Parent::pos(n); 630 } 631 632 /// \brief Gives back the number of the columns. 633 /// 634 /// Gives back the number of the columns. 400 635 int width() const { 401 636 return Parent::width(); 402 637 } 403 638 404 /// \brief Gives back the height of the grid.405 /// 406 /// Gives back the height of the grid.639 /// \brief Gives back the number of the rows. 640 /// 641 /// Gives back the number of the rows. 407 642 int height() const { 408 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 670 /// \brief Gives back the arc goes down from the node. 412 671 /// 413 672 /// Gives back the arc goes down from the node. If there is not 414 /// outgoing arc then it gives back \cINVALID.673 /// outgoing arc then it gives back INVALID. 415 674 Arc down(Node n) const { 416 Edge e = _down(n); 417 return e != INVALID ? direct(e, true) : INVALID; 418 } 419 420 /// \brief Gives back the arc goes up from the node. 421 /// 422 /// Gives back the arc goes up from the node. If there is not 423 /// outgoing arc then it gives back \c INVALID. 424 Arc up(Node n) const { 425 Edge e = _up(n); 426 return e != INVALID ? direct(e, false) : INVALID; 427 } 428 429 /// \brief Gives back the arc goes right from the node. 430 /// 431 /// Gives back the arc goes right from the node. If there is not 432 /// outgoing arc then it gives back \c INVALID. 433 Arc right(Node n) const { 434 Edge e = _right(n); 435 return e != INVALID ? direct(e, true) : INVALID; 436 } 437 438 /// \brief Gives back the arc goes left from the node. 439 /// 440 /// Gives back the arc goes left from the node. If there is not 441 /// outgoing arc then it gives back \c INVALID. 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 } 675 return Parent::down(n); 676 } 677 678 /// \brief Index map of the grid graph 679 /// 680 /// Just returns an IndexMap for the grid graph. 681 IndexMap indexMap() const { 682 return IndexMap(*this); 683 } 684 685 /// \brief Row map of the grid graph 686 /// 687 /// Just returns a RowMap for the grid graph. 688 RowMap rowMap() const { 689 return RowMap(*this); 690 } 691 692 /// \brief Column map of the grid graph 693 /// 694 /// Just returns a ColMap for the grid graph. 695 ColMap colMap() const { 696 return ColMap(*this); 697 } 698 699 }; 700 469 701 } 470 471 #endif // GRID_GRAPH_H 702 #endif
Note: See TracChangeset
for help on using the changeset viewer.