1.1 --- a/lemon/grid_graph.h Tue Sep 02 22:32:04 2008 +0200
1.2 +++ b/lemon/grid_graph.h Mon Oct 20 12:36:02 2008 +0200
1.3 @@ -19,15 +19,11 @@
1.4 #ifndef GRID_GRAPH_H
1.5 #define GRID_GRAPH_H
1.6
1.7 -#include <iostream>
1.8 #include <lemon/core.h>
1.9 +#include <lemon/bits/graph_extender.h>
1.10 +#include <lemon/dim2.h>
1.11 #include <lemon/assert.h>
1.12
1.13 -#include <lemon/bits/base_extender.h>
1.14 -#include <lemon/bits/graph_extender.h>
1.15 -
1.16 -#include <lemon/dim2.h>
1.17 -
1.18 ///\ingroup graphs
1.19 ///\file
1.20 ///\brief GridGraph class.
1.21 @@ -41,6 +37,7 @@
1.22 typedef GridGraphBase Graph;
1.23
1.24 class Node;
1.25 + class Edge;
1.26 class Arc;
1.27
1.28 public:
1.29 @@ -49,58 +46,31 @@
1.30
1.31 protected:
1.32
1.33 - void construct(int w, int h) {
1.34 - _height = h; _width = w;
1.35 - _nodeNum = h * w; _arcNum = 2 * _nodeNum - w - h;
1.36 - _arcLimit = _nodeNum - w;
1.37 - }
1.38 -
1.39 - Arc _down(Node n) const {
1.40 - if (n.id < _nodeNum - _width) {
1.41 - return Arc(n.id);
1.42 - } else {
1.43 - return INVALID;
1.44 - }
1.45 - }
1.46 -
1.47 - Arc _up(Node n) const {
1.48 - if (n.id >= _width) {
1.49 - return Arc(n.id - _width);
1.50 - } else {
1.51 - return INVALID;
1.52 - }
1.53 - }
1.54 -
1.55 - Arc _right(Node n) const {
1.56 - if (n.id % _width < _width - 1) {
1.57 - return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1);
1.58 - } else {
1.59 - return INVALID;
1.60 - }
1.61 - }
1.62 -
1.63 - Arc _left(Node n) const {
1.64 - if (n.id % _width > 0) {
1.65 - return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
1.66 - } else {
1.67 - return INVALID;
1.68 - }
1.69 + void construct(int width, int height) {
1.70 + _width = width; _height = height;
1.71 + _node_num = width * height;
1.72 + _edge_num = 2 * _node_num - width - height;
1.73 + _edge_limit = _node_num - _width;
1.74 }
1.75
1.76 public:
1.77
1.78 Node operator()(int i, int j) const {
1.79 - LEMON_ASSERT(0 <= i && i < width() &&
1.80 - 0 <= j && j < height(), "lemon::GridGraph::IndexError");
1.81 + LEMON_DEBUG(0 <= i && i < _width &&
1.82 + 0 <= j && j < _height, "Index out of range");
1.83 return Node(i + j * _width);
1.84 }
1.85
1.86 - int row(Node n) const {
1.87 - return n.id / _width;
1.88 + int col(Node n) const {
1.89 + return n._id % _width;
1.90 }
1.91
1.92 - int col(Node n) const {
1.93 - return n.id % _width;
1.94 + int row(Node n) const {
1.95 + return n._id / _width;
1.96 + }
1.97 +
1.98 + dim2::Point<int> pos(Node n) const {
1.99 + return dim2::Point<int>(col(n), row(n));
1.100 }
1.101
1.102 int width() const {
1.103 @@ -114,45 +84,86 @@
1.104 typedef True NodeNumTag;
1.105 typedef True ArcNumTag;
1.106
1.107 - int nodeNum() const { return _nodeNum; }
1.108 - int arcNum() const { return _arcNum; }
1.109 + int nodeNum() const { return _node_num; }
1.110 + int edgeNum() const { return _edge_num; }
1.111 + int arcNum() const { return 2 * _edge_num; }
1.112
1.113 - int maxNodeId() const { return nodeNum() - 1; }
1.114 - int maxArcId() const { return arcNum() - 1; }
1.115 -
1.116 - Node source(Arc e) const {
1.117 - if (e.id < _arcLimit) {
1.118 - return e.id;
1.119 + Node u(Edge edge) const {
1.120 + if (edge._id < _edge_limit) {
1.121 + return edge._id;
1.122 } else {
1.123 - return (e.id - _arcLimit) % (_width - 1) +
1.124 - (e.id - _arcLimit) / (_width - 1) * _width;
1.125 + return (edge._id - _edge_limit) % (_width - 1) +
1.126 + (edge._id - _edge_limit) / (_width - 1) * _width;
1.127 }
1.128 }
1.129
1.130 - Node target(Arc e) const {
1.131 - if (e.id < _arcLimit) {
1.132 - return e.id + _width;
1.133 + Node v(Edge edge) const {
1.134 + if (edge._id < _edge_limit) {
1.135 + return edge._id + _width;
1.136 } else {
1.137 - return (e.id - _arcLimit) % (_width - 1) +
1.138 - (e.id - _arcLimit) / (_width - 1) * _width + 1;
1.139 + return (edge._id - _edge_limit) % (_width - 1) +
1.140 + (edge._id - _edge_limit) / (_width - 1) * _width + 1;
1.141 }
1.142 }
1.143
1.144 - static int id(Node v) { return v.id; }
1.145 - static int id(Arc e) { return e.id; }
1.146 + Node source(Arc arc) const {
1.147 + return (arc._id & 1) == 1 ? u(arc) : v(arc);
1.148 + }
1.149 +
1.150 + Node target(Arc arc) const {
1.151 + return (arc._id & 1) == 1 ? v(arc) : u(arc);
1.152 + }
1.153 +
1.154 + static int id(Node node) { return node._id; }
1.155 + static int id(Edge edge) { return edge._id; }
1.156 + static int id(Arc arc) { return arc._id; }
1.157 +
1.158 + int maxNodeId() const { return _node_num - 1; }
1.159 + int maxEdgeId() const { return _edge_num - 1; }
1.160 + int maxArcId() const { return 2 * _edge_num - 1; }
1.161
1.162 static Node nodeFromId(int id) { return Node(id);}
1.163 -
1.164 + static Edge edgeFromId(int id) { return Edge(id);}
1.165 static Arc arcFromId(int id) { return Arc(id);}
1.166
1.167 - typedef True FindArcTag;
1.168 + typedef True FindEdgeTag;
1.169 +
1.170 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.171 + if (prev != INVALID) return INVALID;
1.172 + if (v._id > u._id) {
1.173 + if (v._id - u._id == _width)
1.174 + return Edge(u._id);
1.175 + if (v._id - u._id == 1 && u._id % _width < _width - 1) {
1.176 + return Edge(u._id / _width * (_width - 1) +
1.177 + u._id % _width + _edge_limit);
1.178 + }
1.179 + } else {
1.180 + if (u._id - v._id == _width)
1.181 + return Edge(v._id);
1.182 + if (u._id - v._id == 1 && v._id % _width < _width - 1) {
1.183 + return Edge(v._id / _width * (_width - 1) +
1.184 + v._id % _width + _edge_limit);
1.185 + }
1.186 + }
1.187 + return INVALID;
1.188 + }
1.189
1.190 Arc findArc(Node u, Node v, Arc prev = INVALID) const {
1.191 if (prev != INVALID) return INVALID;
1.192 - if (v.id - u.id == _width) return Arc(u.id);
1.193 - if (v.id - u.id == 1 && u.id % _width < _width - 1) {
1.194 - return Arc(u.id / _width * (_width - 1) +
1.195 - u.id % _width + _arcLimit);
1.196 + if (v._id > u._id) {
1.197 + if (v._id - u._id == _width)
1.198 + return Arc((u._id << 1) | 1);
1.199 + if (v._id - u._id == 1 && u._id % _width < _width - 1) {
1.200 + return Arc(((u._id / _width * (_width - 1) +
1.201 + u._id % _width + _edge_limit) << 1) | 1);
1.202 + }
1.203 + } else {
1.204 + if (u._id - v._id == _width)
1.205 + return Arc(v._id << 1);
1.206 + if (u._id - v._id == 1 && v._id % _width < _width - 1) {
1.207 + return Arc((v._id / _width * (_width - 1) +
1.208 + v._id % _width + _edge_limit) << 1);
1.209 + }
1.210 }
1.211 return INVALID;
1.212 }
1.213 @@ -161,127 +172,331 @@
1.214 friend class GridGraphBase;
1.215
1.216 protected:
1.217 - int id;
1.218 - Node(int _id) : id(_id) {}
1.219 + int _id;
1.220 + Node(int id) : _id(id) {}
1.221 public:
1.222 Node() {}
1.223 - Node (Invalid) { id = -1; }
1.224 - bool operator==(const Node node) const { return id == node.id; }
1.225 - bool operator!=(const Node node) const { return id != node.id; }
1.226 - bool operator<(const Node node) const { return id < node.id; }
1.227 + Node (Invalid) : _id(-1) {}
1.228 + bool operator==(const Node node) const {return _id == node._id;}
1.229 + bool operator!=(const Node node) const {return _id != node._id;}
1.230 + bool operator<(const Node node) const {return _id < node._id;}
1.231 + };
1.232 +
1.233 + class Edge {
1.234 + friend class GridGraphBase;
1.235 +
1.236 + protected:
1.237 + int _id;
1.238 +
1.239 + Edge(int id) : _id(id) {}
1.240 +
1.241 + public:
1.242 + Edge() {}
1.243 + Edge (Invalid) : _id(-1) {}
1.244 + bool operator==(const Edge edge) const {return _id == edge._id;}
1.245 + bool operator!=(const Edge edge) const {return _id != edge._id;}
1.246 + bool operator<(const Edge edge) const {return _id < edge._id;}
1.247 };
1.248
1.249 class Arc {
1.250 friend class GridGraphBase;
1.251
1.252 protected:
1.253 - int id;
1.254 - Arc(int _id) : id(_id) {}
1.255 + int _id;
1.256 +
1.257 + Arc(int id) : _id(id) {}
1.258 +
1.259 public:
1.260 Arc() {}
1.261 - Arc (Invalid) { id = -1; }
1.262 - bool operator==(const Arc arc) const { return id == arc.id; }
1.263 - bool operator!=(const Arc arc) const { return id != arc.id; }
1.264 - bool operator<(const Arc arc) const { return id < arc.id; }
1.265 + Arc (Invalid) : _id(-1) {}
1.266 + operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
1.267 + bool operator==(const Arc arc) const {return _id == arc._id;}
1.268 + bool operator!=(const Arc arc) const {return _id != arc._id;}
1.269 + bool operator<(const Arc arc) const {return _id < arc._id;}
1.270 };
1.271
1.272 + static bool direction(Arc arc) {
1.273 + return (arc._id & 1) == 1;
1.274 + }
1.275 +
1.276 + static Arc direct(Edge edge, bool dir) {
1.277 + return Arc((edge._id << 1) | (dir ? 1 : 0));
1.278 + }
1.279 +
1.280 void first(Node& node) const {
1.281 - node.id = nodeNum() - 1;
1.282 + node._id = _node_num - 1;
1.283 }
1.284
1.285 static void next(Node& node) {
1.286 - --node.id;
1.287 + --node._id;
1.288 + }
1.289 +
1.290 + void first(Edge& edge) const {
1.291 + edge._id = _edge_num - 1;
1.292 + }
1.293 +
1.294 + static void next(Edge& edge) {
1.295 + --edge._id;
1.296 }
1.297
1.298 void first(Arc& arc) const {
1.299 - arc.id = arcNum() - 1;
1.300 + arc._id = 2 * _edge_num - 1;
1.301 }
1.302
1.303 static void next(Arc& arc) {
1.304 - --arc.id;
1.305 + --arc._id;
1.306 }
1.307
1.308 void firstOut(Arc& arc, const Node& node) const {
1.309 - if (node.id < _nodeNum - _width) {
1.310 - arc.id = node.id;
1.311 - } else if (node.id % _width < _width - 1) {
1.312 - arc.id = _arcLimit + node.id % _width +
1.313 - (node.id / _width) * (_width - 1);
1.314 + if (node._id % _width < _width - 1) {
1.315 + arc._id = (_edge_limit + node._id % _width +
1.316 + (node._id / _width) * (_width - 1)) << 1 | 1;
1.317 + return;
1.318 + }
1.319 + if (node._id < _node_num - _width) {
1.320 + arc._id = node._id << 1 | 1;
1.321 + return;
1.322 + }
1.323 + if (node._id % _width > 0) {
1.324 + arc._id = (_edge_limit + node._id % _width +
1.325 + (node._id / _width) * (_width - 1) - 1) << 1;
1.326 + return;
1.327 + }
1.328 + if (node._id >= _width) {
1.329 + arc._id = (node._id - _width) << 1;
1.330 + return;
1.331 + }
1.332 + arc._id = -1;
1.333 + }
1.334 +
1.335 + void nextOut(Arc& arc) const {
1.336 + int nid = arc._id >> 1;
1.337 + if ((arc._id & 1) == 1) {
1.338 + if (nid >= _edge_limit) {
1.339 + nid = (nid - _edge_limit) % (_width - 1) +
1.340 + (nid - _edge_limit) / (_width - 1) * _width;
1.341 + if (nid < _node_num - _width) {
1.342 + arc._id = nid << 1 | 1;
1.343 + return;
1.344 + }
1.345 + }
1.346 + if (nid % _width > 0) {
1.347 + arc._id = (_edge_limit + nid % _width +
1.348 + (nid / _width) * (_width - 1) - 1) << 1;
1.349 + return;
1.350 + }
1.351 + if (nid >= _width) {
1.352 + arc._id = (nid - _width) << 1;
1.353 + return;
1.354 + }
1.355 } else {
1.356 - arc.id = -1;
1.357 + if (nid >= _edge_limit) {
1.358 + nid = (nid - _edge_limit) % (_width - 1) +
1.359 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.360 + if (nid >= _width) {
1.361 + arc._id = (nid - _width) << 1;
1.362 + return;
1.363 + }
1.364 + }
1.365 + }
1.366 + arc._id = -1;
1.367 + }
1.368 +
1.369 + void firstIn(Arc& arc, const Node& node) const {
1.370 + if (node._id % _width < _width - 1) {
1.371 + arc._id = (_edge_limit + node._id % _width +
1.372 + (node._id / _width) * (_width - 1)) << 1;
1.373 + return;
1.374 + }
1.375 + if (node._id < _node_num - _width) {
1.376 + arc._id = node._id << 1;
1.377 + return;
1.378 + }
1.379 + if (node._id % _width > 0) {
1.380 + arc._id = (_edge_limit + node._id % _width +
1.381 + (node._id / _width) * (_width - 1) - 1) << 1 | 1;
1.382 + return;
1.383 + }
1.384 + if (node._id >= _width) {
1.385 + arc._id = (node._id - _width) << 1 | 1;
1.386 + return;
1.387 + }
1.388 + arc._id = -1;
1.389 + }
1.390 +
1.391 + void nextIn(Arc& arc) const {
1.392 + int nid = arc._id >> 1;
1.393 + if ((arc._id & 1) == 0) {
1.394 + if (nid >= _edge_limit) {
1.395 + nid = (nid - _edge_limit) % (_width - 1) +
1.396 + (nid - _edge_limit) / (_width - 1) * _width;
1.397 + if (nid < _node_num - _width) {
1.398 + arc._id = nid << 1;
1.399 + return;
1.400 + }
1.401 + }
1.402 + if (nid % _width > 0) {
1.403 + arc._id = (_edge_limit + nid % _width +
1.404 + (nid / _width) * (_width - 1) - 1) << 1 | 1;
1.405 + return;
1.406 + }
1.407 + if (nid >= _width) {
1.408 + arc._id = (nid - _width) << 1 | 1;
1.409 + return;
1.410 + }
1.411 + } else {
1.412 + if (nid >= _edge_limit) {
1.413 + nid = (nid - _edge_limit) % (_width - 1) +
1.414 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.415 + if (nid >= _width) {
1.416 + arc._id = (nid - _width) << 1 | 1;
1.417 + return;
1.418 + }
1.419 + }
1.420 + }
1.421 + arc._id = -1;
1.422 + }
1.423 +
1.424 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
1.425 + if (node._id % _width < _width - 1) {
1.426 + edge._id = _edge_limit + node._id % _width +
1.427 + (node._id / _width) * (_width - 1);
1.428 + dir = true;
1.429 + return;
1.430 + }
1.431 + if (node._id < _node_num - _width) {
1.432 + edge._id = node._id;
1.433 + dir = true;
1.434 + return;
1.435 + }
1.436 + if (node._id % _width > 0) {
1.437 + edge._id = _edge_limit + node._id % _width +
1.438 + (node._id / _width) * (_width - 1) - 1;
1.439 + dir = false;
1.440 + return;
1.441 + }
1.442 + if (node._id >= _width) {
1.443 + edge._id = node._id - _width;
1.444 + dir = false;
1.445 + return;
1.446 + }
1.447 + edge._id = -1;
1.448 + dir = true;
1.449 + }
1.450 +
1.451 + void nextInc(Edge& edge, bool& dir) const {
1.452 + int nid = edge._id;
1.453 + if (dir) {
1.454 + if (nid >= _edge_limit) {
1.455 + nid = (nid - _edge_limit) % (_width - 1) +
1.456 + (nid - _edge_limit) / (_width - 1) * _width;
1.457 + if (nid < _node_num - _width) {
1.458 + edge._id = nid;
1.459 + return;
1.460 + }
1.461 + }
1.462 + if (nid % _width > 0) {
1.463 + edge._id = _edge_limit + nid % _width +
1.464 + (nid / _width) * (_width - 1) - 1;
1.465 + dir = false;
1.466 + return;
1.467 + }
1.468 + if (nid >= _width) {
1.469 + edge._id = nid - _width;
1.470 + dir = false;
1.471 + return;
1.472 + }
1.473 + } else {
1.474 + if (nid >= _edge_limit) {
1.475 + nid = (nid - _edge_limit) % (_width - 1) +
1.476 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.477 + if (nid >= _width) {
1.478 + edge._id = nid - _width;
1.479 + return;
1.480 + }
1.481 + }
1.482 + }
1.483 + edge._id = -1;
1.484 + dir = true;
1.485 + }
1.486 +
1.487 + Arc right(Node n) const {
1.488 + if (n._id % _width < _width - 1) {
1.489 + return Arc(((_edge_limit + n._id % _width +
1.490 + (n._id / _width) * (_width - 1)) << 1) | 1);
1.491 + } else {
1.492 + return INVALID;
1.493 }
1.494 }
1.495
1.496 - void nextOut(Arc& arc) const {
1.497 - if (arc.id >= _arcLimit) {
1.498 - arc.id = -1;
1.499 - } else if (arc.id % _width < _width - 1) {
1.500 - arc.id = _arcLimit + arc.id % _width +
1.501 - (arc.id / _width) * (_width - 1);
1.502 + Arc left(Node n) const {
1.503 + if (n._id % _width > 0) {
1.504 + return Arc((_edge_limit + n._id % _width +
1.505 + (n._id / _width) * (_width - 1) - 1) << 1);
1.506 } else {
1.507 - arc.id = -1;
1.508 + return INVALID;
1.509 }
1.510 }
1.511
1.512 - void firstIn(Arc& arc, const Node& node) const {
1.513 - if (node.id >= _width) {
1.514 - arc.id = node.id - _width;
1.515 - } else if (node.id % _width > 0) {
1.516 - arc.id = _arcLimit + node.id % _width +
1.517 - (node.id / _width) * (_width - 1) - 1;
1.518 + Arc up(Node n) const {
1.519 + if (n._id < _edge_limit) {
1.520 + return Arc((n._id << 1) | 1);
1.521 } else {
1.522 - arc.id = -1;
1.523 + return INVALID;
1.524 }
1.525 }
1.526
1.527 - void nextIn(Arc& arc) const {
1.528 - if (arc.id >= _arcLimit) {
1.529 - arc.id = -1;
1.530 - } else if (arc.id % _width > 0) {
1.531 - arc.id = _arcLimit + arc.id % _width +
1.532 - (arc.id / _width + 1) * (_width - 1) - 1;
1.533 + Arc down(Node n) const {
1.534 + if (n._id >= _width) {
1.535 + return Arc((n._id - _width) << 1);
1.536 } else {
1.537 - arc.id = -1;
1.538 + return INVALID;
1.539 }
1.540 }
1.541
1.542 private:
1.543 int _width, _height;
1.544 - int _nodeNum, _arcNum;
1.545 - int _arcLimit;
1.546 + int _node_num, _edge_num;
1.547 + int _edge_limit;
1.548 };
1.549
1.550 - typedef GraphExtender<UndirDigraphExtender<GridGraphBase> >
1.551 - ExtendedGridGraphBase;
1.552 +
1.553 + typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
1.554
1.555 /// \ingroup graphs
1.556 ///
1.557 /// \brief Grid graph class
1.558 ///
1.559 /// This class implements a special graph type. The nodes of the
1.560 - /// graph can be indiced by two integer \c (i,j) value where \c i
1.561 - /// is in the \c [0,width) range and j is in the [0, height) range.
1.562 - /// Two nodes are connected in the graph if the indices differ only
1.563 - /// on one position and only one is the difference.
1.564 + /// graph can be indexed by two integer \c (i,j) value where \c i is
1.565 + /// in the \c [0..width()-1] range and j is in the \c
1.566 + /// [0..height()-1] range. Two nodes are connected in the graph if
1.567 + /// the indexes differ exactly on one position and exactly one is
1.568 + /// the difference. The nodes of the graph be indexed by position
1.569 + /// with \c operator()() function. The positions of the nodes can be
1.570 + /// get with \c pos(), \c col() and \c row() members. The outgoing
1.571 + /// arcs can be retrieved with the \c right(), \c up(), \c left()
1.572 + /// and \c down() functions, where the bottom-left corner is the
1.573 + /// origin.
1.574 ///
1.575 /// \image html grid_graph.png
1.576 - /// \image latex grid_graph.eps "Grid graph" width=\textwidth
1.577 + /// \image latex grid_graph.eps "Grid digraph" row_num=\textrow_num
1.578 ///
1.579 - /// The graph can be indiced in the following way:
1.580 + /// A short example about the basic usage:
1.581 ///\code
1.582 - /// GridGraph gr(w, h);
1.583 - /// GridGraph::NodeMap<int> val(gr);
1.584 - /// for (int i = 0; i < gr.width(); ++i) {
1.585 - /// for (int j = 0; j < gr.height(); ++j) {
1.586 - /// val[gr(i, j)] = i + j;
1.587 + /// GridGraph graph(rows, cols);
1.588 + /// GridGraph::NodeMap<int> val(graph);
1.589 + /// for (int i = 0; i < graph.width(); ++i) {
1.590 + /// for (int j = 0; j < graph.height(); ++j) {
1.591 + /// val[graph(i, j)] = i + j;
1.592 /// }
1.593 /// }
1.594 ///\endcode
1.595 ///
1.596 - /// This graph type is fully conform to the \ref concepts::Graph
1.597 - /// "Undirected Graph" concept, and it also has an important extra
1.598 - /// feature that its maps are real \ref concepts::ReferenceMap
1.599 - /// "reference map"s.
1.600 + /// The graph type is fully conform to the \ref concepts::Graph
1.601 + /// "Graph" concept, and it also has an important extra feature
1.602 + /// that its maps are real \ref concepts::ReferenceMap "reference
1.603 + /// map"s.
1.604 class GridGraph : public ExtendedGridGraphBase {
1.605 public:
1.606
1.607 @@ -292,17 +507,47 @@
1.608 /// Map to get the indices of the nodes as dim2::Point<int>.
1.609 class IndexMap {
1.610 public:
1.611 - /// The key type of the map
1.612 + /// \brief The key type of the map
1.613 typedef GridGraph::Node Key;
1.614 - /// The value type of the map
1.615 + /// \brief The value type of the map
1.616 typedef dim2::Point<int> Value;
1.617
1.618 + /// \brief Constructor
1.619 + ///
1.620 /// Constructor
1.621 IndexMap(const GridGraph& graph) : _graph(graph) {}
1.622
1.623 - /// The subscript operator
1.624 - Value operator[](const Key& key) const {
1.625 - return dim2::Point<int>(_graph.row(key), _graph.col(key));
1.626 + /// \brief The subscript operator
1.627 + ///
1.628 + /// The subscript operator.
1.629 + Value operator[](Key key) const {
1.630 + return _graph.pos(key);
1.631 + }
1.632 +
1.633 + private:
1.634 + const GridGraph& _graph;
1.635 + };
1.636 +
1.637 + /// \brief Map to get the column of the nodes.
1.638 + ///
1.639 + /// Map to get the column of the nodes.
1.640 + class ColMap {
1.641 + public:
1.642 + /// \brief The key type of the map
1.643 + typedef GridGraph::Node Key;
1.644 + /// \brief The value type of the map
1.645 + typedef int Value;
1.646 +
1.647 + /// \brief Constructor
1.648 + ///
1.649 + /// Constructor
1.650 + ColMap(const GridGraph& graph) : _graph(graph) {}
1.651 +
1.652 + /// \brief The subscript operator
1.653 + ///
1.654 + /// The subscript operator.
1.655 + Value operator[](Key key) const {
1.656 + return _graph.col(key);
1.657 }
1.658
1.659 private:
1.660 @@ -314,16 +559,20 @@
1.661 /// Map to get the row of the nodes.
1.662 class RowMap {
1.663 public:
1.664 - /// The key type of the map
1.665 + /// \brief The key type of the map
1.666 typedef GridGraph::Node Key;
1.667 - /// The value type of the map
1.668 + /// \brief The value type of the map
1.669 typedef int Value;
1.670
1.671 + /// \brief Constructor
1.672 + ///
1.673 /// Constructor
1.674 RowMap(const GridGraph& graph) : _graph(graph) {}
1.675
1.676 - /// The subscript operator
1.677 - Value operator[](const Key& key) const {
1.678 + /// \brief The subscript operator
1.679 + ///
1.680 + /// The subscript operator.
1.681 + Value operator[](Key key) const {
1.682 return _graph.row(key);
1.683 }
1.684
1.685 @@ -331,38 +580,17 @@
1.686 const GridGraph& _graph;
1.687 };
1.688
1.689 - /// \brief Map to get the column of the nodes.
1.690 - ///
1.691 - /// Map to get the column of the nodes.
1.692 - class ColMap {
1.693 - public:
1.694 - /// The key type of the map
1.695 - typedef GridGraph::Node Key;
1.696 - /// The value type of the map
1.697 - typedef int Value;
1.698 -
1.699 - /// Constructor
1.700 - ColMap(const GridGraph& graph) : _graph(graph) {}
1.701 -
1.702 - /// The subscript operator
1.703 - Value operator[](const Key& key) const {
1.704 - return _graph.col(key);
1.705 - }
1.706 -
1.707 - private:
1.708 - const GridGraph& _graph;
1.709 - };
1.710 -
1.711 /// \brief Constructor
1.712 ///
1.713 - /// Constructor.
1.714 - /// \param width The width of the grid.
1.715 - /// \param height The height of the grid.
1.716 + /// Construct a grid graph with given size.
1.717 GridGraph(int width, int height) { construct(width, height); }
1.718
1.719 /// \brief Resize the graph
1.720 ///
1.721 - /// Resize the grid.
1.722 + /// Resize the graph. The function will fully destroy and rebuild
1.723 + /// the graph. This cause that the maps of the graph will
1.724 + /// reallocated automatically and the previous values will be
1.725 + /// lost.
1.726 void resize(int width, int height) {
1.727 Parent::notifier(Arc()).clear();
1.728 Parent::notifier(Edge()).clear();
1.729 @@ -380,6 +608,13 @@
1.730 return Parent::operator()(i, j);
1.731 }
1.732
1.733 + /// \brief Gives back the column index of the node.
1.734 + ///
1.735 + /// Gives back the column index of the node.
1.736 + int col(Node n) const {
1.737 + return Parent::col(n);
1.738 + }
1.739 +
1.740 /// \brief Gives back the row index of the node.
1.741 ///
1.742 /// Gives back the row index of the node.
1.743 @@ -387,85 +622,81 @@
1.744 return Parent::row(n);
1.745 }
1.746
1.747 - /// \brief Gives back the column index of the node.
1.748 + /// \brief Gives back the position of the node.
1.749 ///
1.750 - /// Gives back the column index of the node.
1.751 - int col(Node n) const {
1.752 - return Parent::col(n);
1.753 + /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
1.754 + dim2::Point<int> pos(Node n) const {
1.755 + return Parent::pos(n);
1.756 }
1.757
1.758 - /// \brief Gives back the width of the grid.
1.759 + /// \brief Gives back the number of the columns.
1.760 ///
1.761 - /// Gives back the width of the grid.
1.762 + /// Gives back the number of the columns.
1.763 int width() const {
1.764 return Parent::width();
1.765 }
1.766
1.767 - /// \brief Gives back the height of the grid.
1.768 + /// \brief Gives back the number of the rows.
1.769 ///
1.770 - /// Gives back the height of the grid.
1.771 + /// Gives back the number of the rows.
1.772 int height() const {
1.773 return Parent::height();
1.774 }
1.775
1.776 + /// \brief Gives back the arc goes right from the node.
1.777 + ///
1.778 + /// Gives back the arc goes right from the node. If there is not
1.779 + /// outgoing arc then it gives back INVALID.
1.780 + Arc right(Node n) const {
1.781 + return Parent::right(n);
1.782 + }
1.783 +
1.784 + /// \brief Gives back the arc goes left from the node.
1.785 + ///
1.786 + /// Gives back the arc goes left from the node. If there is not
1.787 + /// outgoing arc then it gives back INVALID.
1.788 + Arc left(Node n) const {
1.789 + return Parent::left(n);
1.790 + }
1.791 +
1.792 + /// \brief Gives back the arc goes up from the node.
1.793 + ///
1.794 + /// Gives back the arc goes up from the node. If there is not
1.795 + /// outgoing arc then it gives back INVALID.
1.796 + Arc up(Node n) const {
1.797 + return Parent::up(n);
1.798 + }
1.799 +
1.800 /// \brief Gives back the arc goes down from the node.
1.801 ///
1.802 /// Gives back the arc goes down from the node. If there is not
1.803 - /// outgoing arc then it gives back \c INVALID.
1.804 + /// outgoing arc then it gives back INVALID.
1.805 Arc down(Node n) const {
1.806 - Edge e = _down(n);
1.807 - return e != INVALID ? direct(e, true) : INVALID;
1.808 + return Parent::down(n);
1.809 }
1.810
1.811 - /// \brief Gives back the arc goes up from the node.
1.812 + /// \brief Index map of the grid graph
1.813 ///
1.814 - /// Gives back the arc goes up from the node. If there is not
1.815 - /// outgoing arc then it gives back \c INVALID.
1.816 - Arc up(Node n) const {
1.817 - Edge e = _up(n);
1.818 - return e != INVALID ? direct(e, false) : INVALID;
1.819 + /// Just returns an IndexMap for the grid graph.
1.820 + IndexMap indexMap() const {
1.821 + return IndexMap(*this);
1.822 }
1.823
1.824 - /// \brief Gives back the arc goes right from the node.
1.825 + /// \brief Row map of the grid graph
1.826 ///
1.827 - /// Gives back the arc goes right from the node. If there is not
1.828 - /// outgoing arc then it gives back \c INVALID.
1.829 - Arc right(Node n) const {
1.830 - Edge e = _right(n);
1.831 - return e != INVALID ? direct(e, true) : INVALID;
1.832 + /// Just returns a RowMap for the grid graph.
1.833 + RowMap rowMap() const {
1.834 + return RowMap(*this);
1.835 }
1.836
1.837 - /// \brief Gives back the arc goes left from the node.
1.838 + /// \brief Column map of the grid graph
1.839 ///
1.840 - /// Gives back the arc goes left from the node. If there is not
1.841 - /// outgoing arc then it gives back \c INVALID.
1.842 - Arc left(Node n) const {
1.843 - Edge e = _left(n);
1.844 - return e != INVALID ? direct(e, false) : INVALID;
1.845 + /// Just returns a ColMap for the grid graph.
1.846 + ColMap colMap() const {
1.847 + return ColMap(*this);
1.848 }
1.849
1.850 - }; // class GridGraph
1.851 + };
1.852
1.853 - /// \brief Index map of the grid graph
1.854 - ///
1.855 - /// Just returns an IndexMap for the grid graph.
1.856 - inline GridGraph::IndexMap indexMap(const GridGraph& graph) {
1.857 - return GridGraph::IndexMap(graph);
1.858 - }
1.859 -
1.860 - /// \brief Row map of the grid graph
1.861 - ///
1.862 - /// Just returns a RowMap for the grid graph.
1.863 - inline GridGraph::RowMap rowMap(const GridGraph& graph) {
1.864 - return GridGraph::RowMap(graph);
1.865 - }
1.866 -
1.867 - /// \brief Column map of the grid graph
1.868 - ///
1.869 - /// Just returns a ColMap for the grid graph.
1.870 - inline GridGraph::ColMap colMap(const GridGraph& graph) {
1.871 - return GridGraph::ColMap(graph);
1.872 - }
1.873 }
1.874 -
1.875 -#endif // GRID_GRAPH_H
1.876 +#endif