1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/grid_graph.h Thu Dec 10 17:05:35 2009 +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-2009
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 EdgeNumTag;
1.89 + typedef True ArcNumTag;
1.90 +
1.91 + int nodeNum() const { return _node_num; }
1.92 + int edgeNum() const { return _edge_num; }
1.93 + int arcNum() const { return 2 * _edge_num; }
1.94 +
1.95 + Node u(Edge edge) const {
1.96 + if (edge._id < _edge_limit) {
1.97 + return edge._id;
1.98 + } else {
1.99 + return (edge._id - _edge_limit) % (_width - 1) +
1.100 + (edge._id - _edge_limit) / (_width - 1) * _width;
1.101 + }
1.102 + }
1.103 +
1.104 + Node v(Edge edge) const {
1.105 + if (edge._id < _edge_limit) {
1.106 + return edge._id + _width;
1.107 + } else {
1.108 + return (edge._id - _edge_limit) % (_width - 1) +
1.109 + (edge._id - _edge_limit) / (_width - 1) * _width + 1;
1.110 + }
1.111 + }
1.112 +
1.113 + Node source(Arc arc) const {
1.114 + return (arc._id & 1) == 1 ? u(arc) : v(arc);
1.115 + }
1.116 +
1.117 + Node target(Arc arc) const {
1.118 + return (arc._id & 1) == 1 ? v(arc) : u(arc);
1.119 + }
1.120 +
1.121 + static int id(Node node) { return node._id; }
1.122 + static int id(Edge edge) { return edge._id; }
1.123 + static int id(Arc arc) { return arc._id; }
1.124 +
1.125 + int maxNodeId() const { return _node_num - 1; }
1.126 + int maxEdgeId() const { return _edge_num - 1; }
1.127 + int maxArcId() const { return 2 * _edge_num - 1; }
1.128 +
1.129 + static Node nodeFromId(int id) { return Node(id);}
1.130 + static Edge edgeFromId(int id) { return Edge(id);}
1.131 + static Arc arcFromId(int id) { return Arc(id);}
1.132 +
1.133 + typedef True FindEdgeTag;
1.134 + typedef True FindArcTag;
1.135 +
1.136 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.137 + if (prev != INVALID) return INVALID;
1.138 + if (v._id > u._id) {
1.139 + if (v._id - u._id == _width)
1.140 + return Edge(u._id);
1.141 + if (v._id - u._id == 1 && u._id % _width < _width - 1) {
1.142 + return Edge(u._id / _width * (_width - 1) +
1.143 + u._id % _width + _edge_limit);
1.144 + }
1.145 + } else {
1.146 + if (u._id - v._id == _width)
1.147 + return Edge(v._id);
1.148 + if (u._id - v._id == 1 && v._id % _width < _width - 1) {
1.149 + return Edge(v._id / _width * (_width - 1) +
1.150 + v._id % _width + _edge_limit);
1.151 + }
1.152 + }
1.153 + return INVALID;
1.154 + }
1.155 +
1.156 + Arc findArc(Node u, Node v, Arc prev = INVALID) const {
1.157 + if (prev != INVALID) return INVALID;
1.158 + if (v._id > u._id) {
1.159 + if (v._id - u._id == _width)
1.160 + return Arc((u._id << 1) | 1);
1.161 + if (v._id - u._id == 1 && u._id % _width < _width - 1) {
1.162 + return Arc(((u._id / _width * (_width - 1) +
1.163 + u._id % _width + _edge_limit) << 1) | 1);
1.164 + }
1.165 + } else {
1.166 + if (u._id - v._id == _width)
1.167 + return Arc(v._id << 1);
1.168 + if (u._id - v._id == 1 && v._id % _width < _width - 1) {
1.169 + return Arc((v._id / _width * (_width - 1) +
1.170 + v._id % _width + _edge_limit) << 1);
1.171 + }
1.172 + }
1.173 + return INVALID;
1.174 + }
1.175 +
1.176 + class Node {
1.177 + friend class GridGraphBase;
1.178 +
1.179 + protected:
1.180 + int _id;
1.181 + Node(int id) : _id(id) {}
1.182 + public:
1.183 + Node() {}
1.184 + Node (Invalid) : _id(-1) {}
1.185 + bool operator==(const Node node) const {return _id == node._id;}
1.186 + bool operator!=(const Node node) const {return _id != node._id;}
1.187 + bool operator<(const Node node) const {return _id < node._id;}
1.188 + };
1.189 +
1.190 + class Edge {
1.191 + friend class GridGraphBase;
1.192 + friend class Arc;
1.193 +
1.194 + protected:
1.195 + int _id;
1.196 +
1.197 + Edge(int id) : _id(id) {}
1.198 +
1.199 + public:
1.200 + Edge() {}
1.201 + Edge (Invalid) : _id(-1) {}
1.202 + bool operator==(const Edge edge) const {return _id == edge._id;}
1.203 + bool operator!=(const Edge edge) const {return _id != edge._id;}
1.204 + bool operator<(const Edge edge) const {return _id < edge._id;}
1.205 + };
1.206 +
1.207 + class Arc {
1.208 + friend class GridGraphBase;
1.209 +
1.210 + protected:
1.211 + int _id;
1.212 +
1.213 + Arc(int id) : _id(id) {}
1.214 +
1.215 + public:
1.216 + Arc() {}
1.217 + Arc (Invalid) : _id(-1) {}
1.218 + operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
1.219 + bool operator==(const Arc arc) const {return _id == arc._id;}
1.220 + bool operator!=(const Arc arc) const {return _id != arc._id;}
1.221 + bool operator<(const Arc arc) const {return _id < arc._id;}
1.222 + };
1.223 +
1.224 + static bool direction(Arc arc) {
1.225 + return (arc._id & 1) == 1;
1.226 + }
1.227 +
1.228 + static Arc direct(Edge edge, bool dir) {
1.229 + return Arc((edge._id << 1) | (dir ? 1 : 0));
1.230 + }
1.231 +
1.232 + void first(Node& node) const {
1.233 + node._id = _node_num - 1;
1.234 + }
1.235 +
1.236 + static void next(Node& node) {
1.237 + --node._id;
1.238 + }
1.239 +
1.240 + void first(Edge& edge) const {
1.241 + edge._id = _edge_num - 1;
1.242 + }
1.243 +
1.244 + static void next(Edge& edge) {
1.245 + --edge._id;
1.246 + }
1.247 +
1.248 + void first(Arc& arc) const {
1.249 + arc._id = 2 * _edge_num - 1;
1.250 + }
1.251 +
1.252 + static void next(Arc& arc) {
1.253 + --arc._id;
1.254 + }
1.255 +
1.256 + void firstOut(Arc& arc, const Node& node) const {
1.257 + if (node._id % _width < _width - 1) {
1.258 + arc._id = (_edge_limit + node._id % _width +
1.259 + (node._id / _width) * (_width - 1)) << 1 | 1;
1.260 + return;
1.261 + }
1.262 + if (node._id < _node_num - _width) {
1.263 + arc._id = node._id << 1 | 1;
1.264 + return;
1.265 + }
1.266 + if (node._id % _width > 0) {
1.267 + arc._id = (_edge_limit + node._id % _width +
1.268 + (node._id / _width) * (_width - 1) - 1) << 1;
1.269 + return;
1.270 + }
1.271 + if (node._id >= _width) {
1.272 + arc._id = (node._id - _width) << 1;
1.273 + return;
1.274 + }
1.275 + arc._id = -1;
1.276 + }
1.277 +
1.278 + void nextOut(Arc& arc) const {
1.279 + int nid = arc._id >> 1;
1.280 + if ((arc._id & 1) == 1) {
1.281 + if (nid >= _edge_limit) {
1.282 + nid = (nid - _edge_limit) % (_width - 1) +
1.283 + (nid - _edge_limit) / (_width - 1) * _width;
1.284 + if (nid < _node_num - _width) {
1.285 + arc._id = nid << 1 | 1;
1.286 + return;
1.287 + }
1.288 + }
1.289 + if (nid % _width > 0) {
1.290 + arc._id = (_edge_limit + nid % _width +
1.291 + (nid / _width) * (_width - 1) - 1) << 1;
1.292 + return;
1.293 + }
1.294 + if (nid >= _width) {
1.295 + arc._id = (nid - _width) << 1;
1.296 + return;
1.297 + }
1.298 + } else {
1.299 + if (nid >= _edge_limit) {
1.300 + nid = (nid - _edge_limit) % (_width - 1) +
1.301 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.302 + if (nid >= _width) {
1.303 + arc._id = (nid - _width) << 1;
1.304 + return;
1.305 + }
1.306 + }
1.307 + }
1.308 + arc._id = -1;
1.309 + }
1.310 +
1.311 + void firstIn(Arc& arc, const Node& node) const {
1.312 + if (node._id % _width < _width - 1) {
1.313 + arc._id = (_edge_limit + node._id % _width +
1.314 + (node._id / _width) * (_width - 1)) << 1;
1.315 + return;
1.316 + }
1.317 + if (node._id < _node_num - _width) {
1.318 + arc._id = node._id << 1;
1.319 + return;
1.320 + }
1.321 + if (node._id % _width > 0) {
1.322 + arc._id = (_edge_limit + node._id % _width +
1.323 + (node._id / _width) * (_width - 1) - 1) << 1 | 1;
1.324 + return;
1.325 + }
1.326 + if (node._id >= _width) {
1.327 + arc._id = (node._id - _width) << 1 | 1;
1.328 + return;
1.329 + }
1.330 + arc._id = -1;
1.331 + }
1.332 +
1.333 + void nextIn(Arc& arc) const {
1.334 + int nid = arc._id >> 1;
1.335 + if ((arc._id & 1) == 0) {
1.336 + if (nid >= _edge_limit) {
1.337 + nid = (nid - _edge_limit) % (_width - 1) +
1.338 + (nid - _edge_limit) / (_width - 1) * _width;
1.339 + if (nid < _node_num - _width) {
1.340 + arc._id = nid << 1;
1.341 + return;
1.342 + }
1.343 + }
1.344 + if (nid % _width > 0) {
1.345 + arc._id = (_edge_limit + nid % _width +
1.346 + (nid / _width) * (_width - 1) - 1) << 1 | 1;
1.347 + return;
1.348 + }
1.349 + if (nid >= _width) {
1.350 + arc._id = (nid - _width) << 1 | 1;
1.351 + return;
1.352 + }
1.353 + } else {
1.354 + if (nid >= _edge_limit) {
1.355 + nid = (nid - _edge_limit) % (_width - 1) +
1.356 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.357 + if (nid >= _width) {
1.358 + arc._id = (nid - _width) << 1 | 1;
1.359 + return;
1.360 + }
1.361 + }
1.362 + }
1.363 + arc._id = -1;
1.364 + }
1.365 +
1.366 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
1.367 + if (node._id % _width < _width - 1) {
1.368 + edge._id = _edge_limit + node._id % _width +
1.369 + (node._id / _width) * (_width - 1);
1.370 + dir = true;
1.371 + return;
1.372 + }
1.373 + if (node._id < _node_num - _width) {
1.374 + edge._id = node._id;
1.375 + dir = true;
1.376 + return;
1.377 + }
1.378 + if (node._id % _width > 0) {
1.379 + edge._id = _edge_limit + node._id % _width +
1.380 + (node._id / _width) * (_width - 1) - 1;
1.381 + dir = false;
1.382 + return;
1.383 + }
1.384 + if (node._id >= _width) {
1.385 + edge._id = node._id - _width;
1.386 + dir = false;
1.387 + return;
1.388 + }
1.389 + edge._id = -1;
1.390 + dir = true;
1.391 + }
1.392 +
1.393 + void nextInc(Edge& edge, bool& dir) const {
1.394 + int nid = edge._id;
1.395 + if (dir) {
1.396 + if (nid >= _edge_limit) {
1.397 + nid = (nid - _edge_limit) % (_width - 1) +
1.398 + (nid - _edge_limit) / (_width - 1) * _width;
1.399 + if (nid < _node_num - _width) {
1.400 + edge._id = nid;
1.401 + return;
1.402 + }
1.403 + }
1.404 + if (nid % _width > 0) {
1.405 + edge._id = _edge_limit + nid % _width +
1.406 + (nid / _width) * (_width - 1) - 1;
1.407 + dir = false;
1.408 + return;
1.409 + }
1.410 + if (nid >= _width) {
1.411 + edge._id = nid - _width;
1.412 + dir = false;
1.413 + return;
1.414 + }
1.415 + } else {
1.416 + if (nid >= _edge_limit) {
1.417 + nid = (nid - _edge_limit) % (_width - 1) +
1.418 + (nid - _edge_limit) / (_width - 1) * _width + 1;
1.419 + if (nid >= _width) {
1.420 + edge._id = nid - _width;
1.421 + return;
1.422 + }
1.423 + }
1.424 + }
1.425 + edge._id = -1;
1.426 + dir = true;
1.427 + }
1.428 +
1.429 + Arc right(Node n) const {
1.430 + if (n._id % _width < _width - 1) {
1.431 + return Arc(((_edge_limit + n._id % _width +
1.432 + (n._id / _width) * (_width - 1)) << 1) | 1);
1.433 + } else {
1.434 + return INVALID;
1.435 + }
1.436 + }
1.437 +
1.438 + Arc left(Node n) const {
1.439 + if (n._id % _width > 0) {
1.440 + return Arc((_edge_limit + n._id % _width +
1.441 + (n._id / _width) * (_width - 1) - 1) << 1);
1.442 + } else {
1.443 + return INVALID;
1.444 + }
1.445 + }
1.446 +
1.447 + Arc up(Node n) const {
1.448 + if (n._id < _edge_limit) {
1.449 + return Arc((n._id << 1) | 1);
1.450 + } else {
1.451 + return INVALID;
1.452 + }
1.453 + }
1.454 +
1.455 + Arc down(Node n) const {
1.456 + if (n._id >= _width) {
1.457 + return Arc((n._id - _width) << 1);
1.458 + } else {
1.459 + return INVALID;
1.460 + }
1.461 + }
1.462 +
1.463 + private:
1.464 + int _width, _height;
1.465 + int _node_num, _edge_num;
1.466 + int _edge_limit;
1.467 + };
1.468 +
1.469 +
1.470 + typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
1.471 +
1.472 + /// \ingroup graphs
1.473 + ///
1.474 + /// \brief Grid graph class
1.475 + ///
1.476 + /// This class implements a special graph type. The nodes of the
1.477 + /// graph can be indexed by two integer \c (i,j) value where \c i is
1.478 + /// in the \c [0..width()-1] range and j is in the \c
1.479 + /// [0..height()-1] range. Two nodes are connected in the graph if
1.480 + /// the indexes differ exactly on one position and exactly one is
1.481 + /// the difference. The nodes of the graph can be indexed by position
1.482 + /// with the \c operator()() function. The positions of the nodes can be
1.483 + /// get with \c pos(), \c col() and \c row() members. The outgoing
1.484 + /// arcs can be retrieved with the \c right(), \c up(), \c left()
1.485 + /// and \c down() functions, where the bottom-left corner is the
1.486 + /// origin.
1.487 + ///
1.488 + /// \image html grid_graph.png
1.489 + /// \image latex grid_graph.eps "Grid graph" width=\textwidth
1.490 + ///
1.491 + /// A short example about the basic usage:
1.492 + ///\code
1.493 + /// GridGraph graph(rows, cols);
1.494 + /// GridGraph::NodeMap<int> val(graph);
1.495 + /// for (int i = 0; i < graph.width(); ++i) {
1.496 + /// for (int j = 0; j < graph.height(); ++j) {
1.497 + /// val[graph(i, j)] = i + j;
1.498 + /// }
1.499 + /// }
1.500 + ///\endcode
1.501 + ///
1.502 + /// This graph type fully conforms to the \ref concepts::Graph
1.503 + /// "Graph concept".
1.504 + class GridGraph : public ExtendedGridGraphBase {
1.505 + typedef ExtendedGridGraphBase Parent;
1.506 +
1.507 + public:
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