1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/grid_graph.h Wed Oct 22 22:14:00 2008 +0100
1.3 @@ -0,0 +1,703 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef GRID_GRAPH_H
1.23 +#define GRID_GRAPH_H
1.24 +
1.25 +#include <lemon/core.h>
1.26 +#include <lemon/bits/graph_extender.h>
1.27 +#include <lemon/dim2.h>
1.28 +#include <lemon/assert.h>
1.29 +
1.30 +///\ingroup graphs
1.31 +///\file
1.32 +///\brief GridGraph class.
1.33 +
1.34 +namespace lemon {
1.35 +
1.36 + class GridGraphBase {
1.37 +
1.38 + public:
1.39 +
1.40 + typedef GridGraphBase Graph;
1.41 +
1.42 + class Node;
1.43 + class Edge;
1.44 + class Arc;
1.45 +
1.46 + public:
1.47 +
1.48 + GridGraphBase() {}
1.49 +
1.50 + protected:
1.51 +
1.52 + void construct(int width, int height) {
1.53 + _width = width; _height = height;
1.54 + _node_num = width * height;
1.55 + _edge_num = 2 * _node_num - width - height;
1.56 + _edge_limit = _node_num - _width;
1.57 + }
1.58 +
1.59 + public:
1.60 +
1.61 + Node operator()(int i, int j) const {
1.62 + LEMON_DEBUG(0 <= i && i < _width &&
1.63 + 0 <= j && j < _height, "Index out of range");
1.64 + return Node(i + j * _width);
1.65 + }
1.66 +
1.67 + int col(Node n) const {
1.68 + return n._id % _width;
1.69 + }
1.70 +
1.71 + int row(Node n) const {
1.72 + return n._id / _width;
1.73 + }
1.74 +
1.75 + dim2::Point<int> pos(Node n) const {
1.76 + return dim2::Point<int>(col(n), row(n));
1.77 + }
1.78 +
1.79 + int width() const {
1.80 + return _width;
1.81 + }
1.82 +
1.83 + int height() const {
1.84 + return _height;
1.85 + }
1.86 +
1.87 + typedef True NodeNumTag;
1.88 + typedef True ArcNumTag;
1.89 +
1.90 + int nodeNum() const { return _node_num; }
1.91 + int edgeNum() const { return _edge_num; }
1.92 + int arcNum() const { return 2 * _edge_num; }
1.93 +
1.94 + Node u(Edge edge) const {
1.95 + if (edge._id < _edge_limit) {
1.96 + return edge._id;
1.97 + } else {
1.98 + return (edge._id - _edge_limit) % (_width - 1) +
1.99 + (edge._id - _edge_limit) / (_width - 1) * _width;
1.100 + }
1.101 + }
1.102 +
1.103 + Node v(Edge edge) const {
1.104 + if (edge._id < _edge_limit) {
1.105 + return edge._id + _width;
1.106 + } else {
1.107 + return (edge._id - _edge_limit) % (_width - 1) +
1.108 + (edge._id - _edge_limit) / (_width - 1) * _width + 1;
1.109 + }
1.110 + }
1.111 +
1.112 + Node source(Arc arc) const {
1.113 + return (arc._id & 1) == 1 ? u(arc) : v(arc);
1.114 + }
1.115 +
1.116 + Node target(Arc arc) const {
1.117 + return (arc._id & 1) == 1 ? v(arc) : u(arc);
1.118 + }
1.119 +
1.120 + static int id(Node node) { return node._id; }
1.121 + static int id(Edge edge) { return edge._id; }
1.122 + static int id(Arc arc) { return arc._id; }
1.123 +
1.124 + int maxNodeId() const { return _node_num - 1; }
1.125 + int maxEdgeId() const { return _edge_num - 1; }
1.126 + int maxArcId() const { return 2 * _edge_num - 1; }
1.127 +
1.128 + static Node nodeFromId(int id) { return Node(id);}
1.129 + static Edge edgeFromId(int id) { return Edge(id);}
1.130 + static Arc arcFromId(int id) { return Arc(id);}
1.131 +
1.132 + typedef True FindEdgeTag;
1.133 +
1.134 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.135 + if (prev != INVALID) return INVALID;
1.136 + if (v._id > u._id) {
1.137 + if (v._id - u._id == _width)
1.138 + return Edge(u._id);
1.139 + if (v._id - u._id == 1 && u._id % _width < _width - 1) {
1.140 + return Edge(u._id / _width * (_width - 1) +
1.141 + u._id % _width + _edge_limit);
1.142 + }
1.143 + } else {
1.144 + if (u._id - v._id == _width)
1.145 + return Edge(v._id);
1.146 + if (u._id - v._id == 1 && v._id % _width < _width - 1) {
1.147 + return Edge(v._id / _width * (_width - 1) +
1.148 + v._id % _width + _edge_limit);
1.149 + }
1.150 + }
1.151 + return INVALID;
1.152 + }
1.153 +
1.154 + Arc findArc(Node u, Node v, Arc prev = INVALID) const {
1.155 + if (prev != INVALID) return INVALID;
1.156 + if (v._id > u._id) {
1.157 + if (v._id - u._id == _width)
1.158 + return Arc((u._id << 1) | 1);
1.159 + if (v._id - u._id == 1 && u._id % _width < _width - 1) {
1.160 + return Arc(((u._id / _width * (_width - 1) +
1.161 + u._id % _width + _edge_limit) << 1) | 1);
1.162 + }
1.163 + } else {
1.164 + if (u._id - v._id == _width)
1.165 + return Arc(v._id << 1);
1.166 + if (u._id - v._id == 1 && v._id % _width < _width - 1) {
1.167 + return Arc((v._id / _width * (_width - 1) +
1.168 + v._id % _width + _edge_limit) << 1);
1.169 + }
1.170 + }
1.171 + return INVALID;
1.172 + }
1.173 +
1.174 + class Node {
1.175 + friend class GridGraphBase;
1.176 +
1.177 + protected:
1.178 + int _id;
1.179 + Node(int id) : _id(id) {}
1.180 + public:
1.181 + Node() {}
1.182 + Node (Invalid) : _id(-1) {}
1.183 + bool operator==(const Node node) const {return _id == node._id;}
1.184 + bool operator!=(const Node node) const {return _id != node._id;}
1.185 + bool operator<(const Node node) const {return _id < node._id;}
1.186 + };
1.187 +
1.188 + class Edge {
1.189 + friend class GridGraphBase;
1.190 + friend class Arc;
1.191 +
1.192 + protected:
1.193 + int _id;
1.194 +
1.195 + Edge(int id) : _id(id) {}
1.196 +
1.197 + public:
1.198 + Edge() {}
1.199 + Edge (Invalid) : _id(-1) {}
1.200 + bool operator==(const Edge edge) const {return _id == edge._id;}
1.201 + bool operator!=(const Edge edge) const {return _id != edge._id;}
1.202 + bool operator<(const Edge edge) const {return _id < edge._id;}
1.203 + };
1.204 +
1.205 + class Arc {
1.206 + friend class GridGraphBase;
1.207 +
1.208 + protected:
1.209 + int _id;
1.210 +
1.211 + Arc(int id) : _id(id) {}
1.212 +
1.213 + public:
1.214 + Arc() {}
1.215 + Arc (Invalid) : _id(-1) {}
1.216 + operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
1.217 + bool operator==(const Arc arc) const {return _id == arc._id;}
1.218 + bool operator!=(const Arc arc) const {return _id != arc._id;}
1.219 + bool operator<(const Arc arc) const {return _id < arc._id;}
1.220 + };
1.221 +
1.222 + static bool direction(Arc arc) {
1.223 + return (arc._id & 1) == 1;
1.224 + }
1.225 +
1.226 + static Arc direct(Edge edge, bool dir) {
1.227 + return Arc((edge._id << 1) | (dir ? 1 : 0));
1.228 + }
1.229 +
1.230 + void first(Node& node) const {
1.231 + node._id = _node_num - 1;
1.232 + }
1.233 +
1.234 + static void next(Node& node) {
1.235 + --node._id;
1.236 + }
1.237 +
1.238 + void first(Edge& edge) const {
1.239 + edge._id = _edge_num - 1;
1.240 + }
1.241 +
1.242 + static void next(Edge& edge) {
1.243 + --edge._id;
1.244 + }
1.245 +
1.246 + void first(Arc& arc) const {
1.247 + arc._id = 2 * _edge_num - 1;
1.248 + }
1.249 +
1.250 + static void next(Arc& arc) {
1.251 + --arc._id;
1.252 + }
1.253 +
1.254 + void firstOut(Arc& arc, const Node& node) const {
1.255 + if (node._id % _width < _width - 1) {
1.256 + arc._id = (_edge_limit + node._id % _width +
1.257 + (node._id / _width) * (_width - 1)) << 1 | 1;
1.258 + return;
1.259 + }
1.260 + if (node._id < _node_num - _width) {
1.261 + arc._id = node._id << 1 | 1;
1.262 + return;
1.263 + }
1.264 + if (node._id % _width > 0) {
1.265 + arc._id = (_edge_limit + node._id % _width +
1.266 + (node._id / _width) * (_width - 1) - 1) << 1;
1.267 + return;
1.268 + }
1.269 + if (node._id >= _width) {
1.270 + arc._id = (node._id - _width) << 1;
1.271 + return;
1.272 + }
1.273 + arc._id = -1;
1.274 + }
1.275 +
1.276 + void nextOut(Arc& arc) const {
1.277 + int nid = arc._id >> 1;
1.278 + if ((arc._id & 1) == 1) {
1.279 + if (nid >= _edge_limit) {
1.280 + nid = (nid - _edge_limit) % (_width - 1) +
1.281 + (nid - _edge_limit) / (_width - 1) * _width;
1.282 + if (nid < _node_num - _width) {
1.283 + arc._id = nid << 1 | 1;
1.284 + return;
1.285 + }
1.286 + }
1.287 + if (nid % _width > 0) {
1.288 + arc._id = (_edge_limit + nid % _width +
1.289 + (nid / _width) * (_width - 1) - 1) << 1;
1.290 + return;
1.291 + }
1.292 + if (nid >= _width) {
1.293 + arc._id = (nid - _width) << 1;
1.294 + return;
1.295 + }
1.296 + } else {
1.297 + if (nid >= _edge_limit) {
1.298 + nid = (nid - _edge_limit) % (_width - 1) +
1.299 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.300 + if (nid >= _width) {
1.301 + arc._id = (nid - _width) << 1;
1.302 + return;
1.303 + }
1.304 + }
1.305 + }
1.306 + arc._id = -1;
1.307 + }
1.308 +
1.309 + void firstIn(Arc& arc, const Node& node) const {
1.310 + if (node._id % _width < _width - 1) {
1.311 + arc._id = (_edge_limit + node._id % _width +
1.312 + (node._id / _width) * (_width - 1)) << 1;
1.313 + return;
1.314 + }
1.315 + if (node._id < _node_num - _width) {
1.316 + arc._id = node._id << 1;
1.317 + return;
1.318 + }
1.319 + if (node._id % _width > 0) {
1.320 + arc._id = (_edge_limit + node._id % _width +
1.321 + (node._id / _width) * (_width - 1) - 1) << 1 | 1;
1.322 + return;
1.323 + }
1.324 + if (node._id >= _width) {
1.325 + arc._id = (node._id - _width) << 1 | 1;
1.326 + return;
1.327 + }
1.328 + arc._id = -1;
1.329 + }
1.330 +
1.331 + void nextIn(Arc& arc) const {
1.332 + int nid = arc._id >> 1;
1.333 + if ((arc._id & 1) == 0) {
1.334 + if (nid >= _edge_limit) {
1.335 + nid = (nid - _edge_limit) % (_width - 1) +
1.336 + (nid - _edge_limit) / (_width - 1) * _width;
1.337 + if (nid < _node_num - _width) {
1.338 + arc._id = nid << 1;
1.339 + return;
1.340 + }
1.341 + }
1.342 + if (nid % _width > 0) {
1.343 + arc._id = (_edge_limit + nid % _width +
1.344 + (nid / _width) * (_width - 1) - 1) << 1 | 1;
1.345 + return;
1.346 + }
1.347 + if (nid >= _width) {
1.348 + arc._id = (nid - _width) << 1 | 1;
1.349 + return;
1.350 + }
1.351 + } else {
1.352 + if (nid >= _edge_limit) {
1.353 + nid = (nid - _edge_limit) % (_width - 1) +
1.354 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.355 + if (nid >= _width) {
1.356 + arc._id = (nid - _width) << 1 | 1;
1.357 + return;
1.358 + }
1.359 + }
1.360 + }
1.361 + arc._id = -1;
1.362 + }
1.363 +
1.364 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
1.365 + if (node._id % _width < _width - 1) {
1.366 + edge._id = _edge_limit + node._id % _width +
1.367 + (node._id / _width) * (_width - 1);
1.368 + dir = true;
1.369 + return;
1.370 + }
1.371 + if (node._id < _node_num - _width) {
1.372 + edge._id = node._id;
1.373 + dir = true;
1.374 + return;
1.375 + }
1.376 + if (node._id % _width > 0) {
1.377 + edge._id = _edge_limit + node._id % _width +
1.378 + (node._id / _width) * (_width - 1) - 1;
1.379 + dir = false;
1.380 + return;
1.381 + }
1.382 + if (node._id >= _width) {
1.383 + edge._id = node._id - _width;
1.384 + dir = false;
1.385 + return;
1.386 + }
1.387 + edge._id = -1;
1.388 + dir = true;
1.389 + }
1.390 +
1.391 + void nextInc(Edge& edge, bool& dir) const {
1.392 + int nid = edge._id;
1.393 + if (dir) {
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 + edge._id = nid;
1.399 + return;
1.400 + }
1.401 + }
1.402 + if (nid % _width > 0) {
1.403 + edge._id = _edge_limit + nid % _width +
1.404 + (nid / _width) * (_width - 1) - 1;
1.405 + dir = false;
1.406 + return;
1.407 + }
1.408 + if (nid >= _width) {
1.409 + edge._id = nid - _width;
1.410 + dir = false;
1.411 + return;
1.412 + }
1.413 + } else {
1.414 + if (nid >= _edge_limit) {
1.415 + nid = (nid - _edge_limit) % (_width - 1) +
1.416 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.417 + if (nid >= _width) {
1.418 + edge._id = nid - _width;
1.419 + return;
1.420 + }
1.421 + }
1.422 + }
1.423 + edge._id = -1;
1.424 + dir = true;
1.425 + }
1.426 +
1.427 + Arc right(Node n) const {
1.428 + if (n._id % _width < _width - 1) {
1.429 + return Arc(((_edge_limit + n._id % _width +
1.430 + (n._id / _width) * (_width - 1)) << 1) | 1);
1.431 + } else {
1.432 + return INVALID;
1.433 + }
1.434 + }
1.435 +
1.436 + Arc left(Node n) const {
1.437 + if (n._id % _width > 0) {
1.438 + return Arc((_edge_limit + n._id % _width +
1.439 + (n._id / _width) * (_width - 1) - 1) << 1);
1.440 + } else {
1.441 + return INVALID;
1.442 + }
1.443 + }
1.444 +
1.445 + Arc up(Node n) const {
1.446 + if (n._id < _edge_limit) {
1.447 + return Arc((n._id << 1) | 1);
1.448 + } else {
1.449 + return INVALID;
1.450 + }
1.451 + }
1.452 +
1.453 + Arc down(Node n) const {
1.454 + if (n._id >= _width) {
1.455 + return Arc((n._id - _width) << 1);
1.456 + } else {
1.457 + return INVALID;
1.458 + }
1.459 + }
1.460 +
1.461 + private:
1.462 + int _width, _height;
1.463 + int _node_num, _edge_num;
1.464 + int _edge_limit;
1.465 + };
1.466 +
1.467 +
1.468 + typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
1.469 +
1.470 + /// \ingroup graphs
1.471 + ///
1.472 + /// \brief Grid graph class
1.473 + ///
1.474 + /// This class implements a special graph type. The nodes of the
1.475 + /// graph can be indexed by two integer \c (i,j) value where \c i is
1.476 + /// in the \c [0..width()-1] range and j is in the \c
1.477 + /// [0..height()-1] range. Two nodes are connected in the graph if
1.478 + /// the indexes differ exactly on one position and exactly one is
1.479 + /// the difference. The nodes of the graph can be indexed by position
1.480 + /// with the \c operator()() function. The positions of the nodes can be
1.481 + /// get with \c pos(), \c col() and \c row() members. The outgoing
1.482 + /// arcs can be retrieved with the \c right(), \c up(), \c left()
1.483 + /// and \c down() functions, where the bottom-left corner is the
1.484 + /// origin.
1.485 + ///
1.486 + /// \image html grid_graph.png
1.487 + /// \image latex grid_graph.eps "Grid graph" row_num=\textrow_num
1.488 + ///
1.489 + /// A short example about the basic usage:
1.490 + ///\code
1.491 + /// GridGraph graph(rows, cols);
1.492 + /// GridGraph::NodeMap<int> val(graph);
1.493 + /// for (int i = 0; i < graph.width(); ++i) {
1.494 + /// for (int j = 0; j < graph.height(); ++j) {
1.495 + /// val[graph(i, j)] = i + j;
1.496 + /// }
1.497 + /// }
1.498 + ///\endcode
1.499 + ///
1.500 + /// This graph type is fully conform to the \ref concepts::Graph
1.501 + /// "Graph" concept, and it also has an important extra feature
1.502 + /// that its maps are real \ref concepts::ReferenceMap
1.503 + /// "reference map"s.
1.504 + class GridGraph : public ExtendedGridGraphBase {
1.505 + public:
1.506 +
1.507 + typedef ExtendedGridGraphBase Parent;
1.508 +
1.509 + /// \brief Map to get the indices of the nodes as dim2::Point<int>.
1.510 + ///
1.511 + /// Map to get the indices of the nodes as dim2::Point<int>.
1.512 + class IndexMap {
1.513 + public:
1.514 + /// \brief The key type of the map
1.515 + typedef GridGraph::Node Key;
1.516 + /// \brief The value type of the map
1.517 + typedef dim2::Point<int> Value;
1.518 +
1.519 + /// \brief Constructor
1.520 + ///
1.521 + /// Constructor
1.522 + IndexMap(const GridGraph& graph) : _graph(graph) {}
1.523 +
1.524 + /// \brief The subscript operator
1.525 + ///
1.526 + /// The subscript operator.
1.527 + Value operator[](Key key) const {
1.528 + return _graph.pos(key);
1.529 + }
1.530 +
1.531 + private:
1.532 + const GridGraph& _graph;
1.533 + };
1.534 +
1.535 + /// \brief Map to get the column of the nodes.
1.536 + ///
1.537 + /// Map to get the column of the nodes.
1.538 + class ColMap {
1.539 + public:
1.540 + /// \brief The key type of the map
1.541 + typedef GridGraph::Node Key;
1.542 + /// \brief The value type of the map
1.543 + typedef int Value;
1.544 +
1.545 + /// \brief Constructor
1.546 + ///
1.547 + /// Constructor
1.548 + ColMap(const GridGraph& graph) : _graph(graph) {}
1.549 +
1.550 + /// \brief The subscript operator
1.551 + ///
1.552 + /// The subscript operator.
1.553 + Value operator[](Key key) const {
1.554 + return _graph.col(key);
1.555 + }
1.556 +
1.557 + private:
1.558 + const GridGraph& _graph;
1.559 + };
1.560 +
1.561 + /// \brief Map to get the row of the nodes.
1.562 + ///
1.563 + /// Map to get the row of the nodes.
1.564 + class RowMap {
1.565 + public:
1.566 + /// \brief The key type of the map
1.567 + typedef GridGraph::Node Key;
1.568 + /// \brief The value type of the map
1.569 + typedef int Value;
1.570 +
1.571 + /// \brief Constructor
1.572 + ///
1.573 + /// Constructor
1.574 + RowMap(const GridGraph& graph) : _graph(graph) {}
1.575 +
1.576 + /// \brief The subscript operator
1.577 + ///
1.578 + /// The subscript operator.
1.579 + Value operator[](Key key) const {
1.580 + return _graph.row(key);
1.581 + }
1.582 +
1.583 + private:
1.584 + const GridGraph& _graph;
1.585 + };
1.586 +
1.587 + /// \brief Constructor
1.588 + ///
1.589 + /// Construct a grid graph with given size.
1.590 + GridGraph(int width, int height) { construct(width, height); }
1.591 +
1.592 + /// \brief Resize the graph
1.593 + ///
1.594 + /// Resize the graph. The function will fully destroy and rebuild
1.595 + /// the graph. This cause that the maps of the graph will
1.596 + /// reallocated automatically and the previous values will be
1.597 + /// lost.
1.598 + void resize(int width, int height) {
1.599 + Parent::notifier(Arc()).clear();
1.600 + Parent::notifier(Edge()).clear();
1.601 + Parent::notifier(Node()).clear();
1.602 + construct(width, height);
1.603 + Parent::notifier(Node()).build();
1.604 + Parent::notifier(Edge()).build();
1.605 + Parent::notifier(Arc()).build();
1.606 + }
1.607 +
1.608 + /// \brief The node on the given position.
1.609 + ///
1.610 + /// Gives back the node on the given position.
1.611 + Node operator()(int i, int j) const {
1.612 + return Parent::operator()(i, j);
1.613 + }
1.614 +
1.615 + /// \brief Gives back the column index of the node.
1.616 + ///
1.617 + /// Gives back the column index of the node.
1.618 + int col(Node n) const {
1.619 + return Parent::col(n);
1.620 + }
1.621 +
1.622 + /// \brief Gives back the row index of the node.
1.623 + ///
1.624 + /// Gives back the row index of the node.
1.625 + int row(Node n) const {
1.626 + return Parent::row(n);
1.627 + }
1.628 +
1.629 + /// \brief Gives back the position of the node.
1.630 + ///
1.631 + /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
1.632 + dim2::Point<int> pos(Node n) const {
1.633 + return Parent::pos(n);
1.634 + }
1.635 +
1.636 + /// \brief Gives back the number of the columns.
1.637 + ///
1.638 + /// Gives back the number of the columns.
1.639 + int width() const {
1.640 + return Parent::width();
1.641 + }
1.642 +
1.643 + /// \brief Gives back the number of the rows.
1.644 + ///
1.645 + /// Gives back the number of the rows.
1.646 + int height() const {
1.647 + return Parent::height();
1.648 + }
1.649 +
1.650 + /// \brief Gives back the arc goes right from the node.
1.651 + ///
1.652 + /// Gives back the arc goes right from the node. If there is not
1.653 + /// outgoing arc then it gives back INVALID.
1.654 + Arc right(Node n) const {
1.655 + return Parent::right(n);
1.656 + }
1.657 +
1.658 + /// \brief Gives back the arc goes left from the node.
1.659 + ///
1.660 + /// Gives back the arc goes left from the node. If there is not
1.661 + /// outgoing arc then it gives back INVALID.
1.662 + Arc left(Node n) const {
1.663 + return Parent::left(n);
1.664 + }
1.665 +
1.666 + /// \brief Gives back the arc goes up from the node.
1.667 + ///
1.668 + /// Gives back the arc goes up from the node. If there is not
1.669 + /// outgoing arc then it gives back INVALID.
1.670 + Arc up(Node n) const {
1.671 + return Parent::up(n);
1.672 + }
1.673 +
1.674 + /// \brief Gives back the arc goes down from the node.
1.675 + ///
1.676 + /// Gives back the arc goes down from the node. If there is not
1.677 + /// outgoing arc then it gives back INVALID.
1.678 + Arc down(Node n) const {
1.679 + return Parent::down(n);
1.680 + }
1.681 +
1.682 + /// \brief Index map of the grid graph
1.683 + ///
1.684 + /// Just returns an IndexMap for the grid graph.
1.685 + IndexMap indexMap() const {
1.686 + return IndexMap(*this);
1.687 + }
1.688 +
1.689 + /// \brief Row map of the grid graph
1.690 + ///
1.691 + /// Just returns a RowMap for the grid graph.
1.692 + RowMap rowMap() const {
1.693 + return RowMap(*this);
1.694 + }
1.695 +
1.696 + /// \brief Column map of the grid graph
1.697 + ///
1.698 + /// Just returns a ColMap for the grid graph.
1.699 + ColMap colMap() const {
1.700 + return ColMap(*this);
1.701 + }
1.702 +
1.703 + };
1.704 +
1.705 +}
1.706 +#endif