1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/grid_graph.h Tue Sep 02 22:32:04 2008 +0200
1.3 @@ -0,0 +1,471 @@
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 <iostream>
1.26 +#include <lemon/core.h>
1.27 +#include <lemon/assert.h>
1.28 +
1.29 +#include <lemon/bits/base_extender.h>
1.30 +#include <lemon/bits/graph_extender.h>
1.31 +
1.32 +#include <lemon/dim2.h>
1.33 +
1.34 +///\ingroup graphs
1.35 +///\file
1.36 +///\brief GridGraph class.
1.37 +
1.38 +namespace lemon {
1.39 +
1.40 + class GridGraphBase {
1.41 +
1.42 + public:
1.43 +
1.44 + typedef GridGraphBase Graph;
1.45 +
1.46 + class Node;
1.47 + class Arc;
1.48 +
1.49 + public:
1.50 +
1.51 + GridGraphBase() {}
1.52 +
1.53 + protected:
1.54 +
1.55 + void construct(int w, int h) {
1.56 + _height = h; _width = w;
1.57 + _nodeNum = h * w; _arcNum = 2 * _nodeNum - w - h;
1.58 + _arcLimit = _nodeNum - w;
1.59 + }
1.60 +
1.61 + Arc _down(Node n) const {
1.62 + if (n.id < _nodeNum - _width) {
1.63 + return Arc(n.id);
1.64 + } else {
1.65 + return INVALID;
1.66 + }
1.67 + }
1.68 +
1.69 + Arc _up(Node n) const {
1.70 + if (n.id >= _width) {
1.71 + return Arc(n.id - _width);
1.72 + } else {
1.73 + return INVALID;
1.74 + }
1.75 + }
1.76 +
1.77 + Arc _right(Node n) const {
1.78 + if (n.id % _width < _width - 1) {
1.79 + return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1);
1.80 + } else {
1.81 + return INVALID;
1.82 + }
1.83 + }
1.84 +
1.85 + Arc _left(Node n) const {
1.86 + if (n.id % _width > 0) {
1.87 + return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
1.88 + } else {
1.89 + return INVALID;
1.90 + }
1.91 + }
1.92 +
1.93 + public:
1.94 +
1.95 + Node operator()(int i, int j) const {
1.96 + LEMON_ASSERT(0 <= i && i < width() &&
1.97 + 0 <= j && j < height(), "lemon::GridGraph::IndexError");
1.98 + return Node(i + j * _width);
1.99 + }
1.100 +
1.101 + int row(Node n) const {
1.102 + return n.id / _width;
1.103 + }
1.104 +
1.105 + int col(Node n) const {
1.106 + return n.id % _width;
1.107 + }
1.108 +
1.109 + int width() const {
1.110 + return _width;
1.111 + }
1.112 +
1.113 + int height() const {
1.114 + return _height;
1.115 + }
1.116 +
1.117 + typedef True NodeNumTag;
1.118 + typedef True ArcNumTag;
1.119 +
1.120 + int nodeNum() const { return _nodeNum; }
1.121 + int arcNum() const { return _arcNum; }
1.122 +
1.123 + int maxNodeId() const { return nodeNum() - 1; }
1.124 + int maxArcId() const { return arcNum() - 1; }
1.125 +
1.126 + Node source(Arc e) const {
1.127 + if (e.id < _arcLimit) {
1.128 + return e.id;
1.129 + } else {
1.130 + return (e.id - _arcLimit) % (_width - 1) +
1.131 + (e.id - _arcLimit) / (_width - 1) * _width;
1.132 + }
1.133 + }
1.134 +
1.135 + Node target(Arc e) const {
1.136 + if (e.id < _arcLimit) {
1.137 + return e.id + _width;
1.138 + } else {
1.139 + return (e.id - _arcLimit) % (_width - 1) +
1.140 + (e.id - _arcLimit) / (_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 +
1.147 + static Node nodeFromId(int id) { return Node(id);}
1.148 +
1.149 + static Arc arcFromId(int id) { return Arc(id);}
1.150 +
1.151 + typedef True FindArcTag;
1.152 +
1.153 + Arc findArc(Node u, Node v, Arc prev = INVALID) const {
1.154 + if (prev != INVALID) return INVALID;
1.155 + if (v.id - u.id == _width) return Arc(u.id);
1.156 + if (v.id - u.id == 1 && u.id % _width < _width - 1) {
1.157 + return Arc(u.id / _width * (_width - 1) +
1.158 + u.id % _width + _arcLimit);
1.159 + }
1.160 + return INVALID;
1.161 + }
1.162 +
1.163 + class Node {
1.164 + friend class GridGraphBase;
1.165 +
1.166 + protected:
1.167 + int id;
1.168 + Node(int _id) : id(_id) {}
1.169 + public:
1.170 + Node() {}
1.171 + Node (Invalid) { id = -1; }
1.172 + bool operator==(const Node node) const { return id == node.id; }
1.173 + bool operator!=(const Node node) const { return id != node.id; }
1.174 + bool operator<(const Node node) const { return id < node.id; }
1.175 + };
1.176 +
1.177 + class Arc {
1.178 + friend class GridGraphBase;
1.179 +
1.180 + protected:
1.181 + int id;
1.182 + Arc(int _id) : id(_id) {}
1.183 + public:
1.184 + Arc() {}
1.185 + Arc (Invalid) { id = -1; }
1.186 + bool operator==(const Arc arc) const { return id == arc.id; }
1.187 + bool operator!=(const Arc arc) const { return id != arc.id; }
1.188 + bool operator<(const Arc arc) const { return id < arc.id; }
1.189 + };
1.190 +
1.191 + void first(Node& node) const {
1.192 + node.id = nodeNum() - 1;
1.193 + }
1.194 +
1.195 + static void next(Node& node) {
1.196 + --node.id;
1.197 + }
1.198 +
1.199 + void first(Arc& arc) const {
1.200 + arc.id = arcNum() - 1;
1.201 + }
1.202 +
1.203 + static void next(Arc& arc) {
1.204 + --arc.id;
1.205 + }
1.206 +
1.207 + void firstOut(Arc& arc, const Node& node) const {
1.208 + if (node.id < _nodeNum - _width) {
1.209 + arc.id = node.id;
1.210 + } else if (node.id % _width < _width - 1) {
1.211 + arc.id = _arcLimit + node.id % _width +
1.212 + (node.id / _width) * (_width - 1);
1.213 + } else {
1.214 + arc.id = -1;
1.215 + }
1.216 + }
1.217 +
1.218 + void nextOut(Arc& arc) const {
1.219 + if (arc.id >= _arcLimit) {
1.220 + arc.id = -1;
1.221 + } else if (arc.id % _width < _width - 1) {
1.222 + arc.id = _arcLimit + arc.id % _width +
1.223 + (arc.id / _width) * (_width - 1);
1.224 + } else {
1.225 + arc.id = -1;
1.226 + }
1.227 + }
1.228 +
1.229 + void firstIn(Arc& arc, const Node& node) const {
1.230 + if (node.id >= _width) {
1.231 + arc.id = node.id - _width;
1.232 + } else if (node.id % _width > 0) {
1.233 + arc.id = _arcLimit + node.id % _width +
1.234 + (node.id / _width) * (_width - 1) - 1;
1.235 + } else {
1.236 + arc.id = -1;
1.237 + }
1.238 + }
1.239 +
1.240 + void nextIn(Arc& arc) const {
1.241 + if (arc.id >= _arcLimit) {
1.242 + arc.id = -1;
1.243 + } else if (arc.id % _width > 0) {
1.244 + arc.id = _arcLimit + arc.id % _width +
1.245 + (arc.id / _width + 1) * (_width - 1) - 1;
1.246 + } else {
1.247 + arc.id = -1;
1.248 + }
1.249 + }
1.250 +
1.251 + private:
1.252 + int _width, _height;
1.253 + int _nodeNum, _arcNum;
1.254 + int _arcLimit;
1.255 + };
1.256 +
1.257 + typedef GraphExtender<UndirDigraphExtender<GridGraphBase> >
1.258 + ExtendedGridGraphBase;
1.259 +
1.260 + /// \ingroup graphs
1.261 + ///
1.262 + /// \brief Grid graph class
1.263 + ///
1.264 + /// This class implements a special graph type. The nodes of the
1.265 + /// graph can be indiced by two integer \c (i,j) value where \c i
1.266 + /// is in the \c [0,width) range and j is in the [0, height) range.
1.267 + /// Two nodes are connected in the graph if the indices differ only
1.268 + /// on one position and only one is the difference.
1.269 + ///
1.270 + /// \image html grid_graph.png
1.271 + /// \image latex grid_graph.eps "Grid graph" width=\textwidth
1.272 + ///
1.273 + /// The graph can be indiced in the following way:
1.274 + ///\code
1.275 + /// GridGraph gr(w, h);
1.276 + /// GridGraph::NodeMap<int> val(gr);
1.277 + /// for (int i = 0; i < gr.width(); ++i) {
1.278 + /// for (int j = 0; j < gr.height(); ++j) {
1.279 + /// val[gr(i, j)] = i + j;
1.280 + /// }
1.281 + /// }
1.282 + ///\endcode
1.283 + ///
1.284 + /// This graph type is fully conform to the \ref concepts::Graph
1.285 + /// "Undirected Graph" concept, and it also has an important extra
1.286 + /// feature that its maps are real \ref concepts::ReferenceMap
1.287 + /// "reference map"s.
1.288 + class GridGraph : public ExtendedGridGraphBase {
1.289 + public:
1.290 +
1.291 + typedef ExtendedGridGraphBase Parent;
1.292 +
1.293 + /// \brief Map to get the indices of the nodes as dim2::Point<int>.
1.294 + ///
1.295 + /// Map to get the indices of the nodes as dim2::Point<int>.
1.296 + class IndexMap {
1.297 + public:
1.298 + /// The key type of the map
1.299 + typedef GridGraph::Node Key;
1.300 + /// The value type of the map
1.301 + typedef dim2::Point<int> Value;
1.302 +
1.303 + /// Constructor
1.304 + IndexMap(const GridGraph& graph) : _graph(graph) {}
1.305 +
1.306 + /// The subscript operator
1.307 + Value operator[](const Key& key) const {
1.308 + return dim2::Point<int>(_graph.row(key), _graph.col(key));
1.309 + }
1.310 +
1.311 + private:
1.312 + const GridGraph& _graph;
1.313 + };
1.314 +
1.315 + /// \brief Map to get the row of the nodes.
1.316 + ///
1.317 + /// Map to get the row of the nodes.
1.318 + class RowMap {
1.319 + public:
1.320 + /// The key type of the map
1.321 + typedef GridGraph::Node Key;
1.322 + /// The value type of the map
1.323 + typedef int Value;
1.324 +
1.325 + /// Constructor
1.326 + RowMap(const GridGraph& graph) : _graph(graph) {}
1.327 +
1.328 + /// The subscript operator
1.329 + Value operator[](const Key& key) const {
1.330 + return _graph.row(key);
1.331 + }
1.332 +
1.333 + private:
1.334 + const GridGraph& _graph;
1.335 + };
1.336 +
1.337 + /// \brief Map to get the column of the nodes.
1.338 + ///
1.339 + /// Map to get the column of the nodes.
1.340 + class ColMap {
1.341 + public:
1.342 + /// The key type of the map
1.343 + typedef GridGraph::Node Key;
1.344 + /// The value type of the map
1.345 + typedef int Value;
1.346 +
1.347 + /// Constructor
1.348 + ColMap(const GridGraph& graph) : _graph(graph) {}
1.349 +
1.350 + /// The subscript operator
1.351 + Value operator[](const Key& key) const {
1.352 + return _graph.col(key);
1.353 + }
1.354 +
1.355 + private:
1.356 + const GridGraph& _graph;
1.357 + };
1.358 +
1.359 + /// \brief Constructor
1.360 + ///
1.361 + /// Constructor.
1.362 + /// \param width The width of the grid.
1.363 + /// \param height The height of the grid.
1.364 + GridGraph(int width, int height) { construct(width, height); }
1.365 +
1.366 + /// \brief Resize the graph
1.367 + ///
1.368 + /// Resize the grid.
1.369 + void resize(int width, int height) {
1.370 + Parent::notifier(Arc()).clear();
1.371 + Parent::notifier(Edge()).clear();
1.372 + Parent::notifier(Node()).clear();
1.373 + construct(width, height);
1.374 + Parent::notifier(Node()).build();
1.375 + Parent::notifier(Edge()).build();
1.376 + Parent::notifier(Arc()).build();
1.377 + }
1.378 +
1.379 + /// \brief The node on the given position.
1.380 + ///
1.381 + /// Gives back the node on the given position.
1.382 + Node operator()(int i, int j) const {
1.383 + return Parent::operator()(i, j);
1.384 + }
1.385 +
1.386 + /// \brief Gives back the row index of the node.
1.387 + ///
1.388 + /// Gives back the row index of the node.
1.389 + int row(Node n) const {
1.390 + return Parent::row(n);
1.391 + }
1.392 +
1.393 + /// \brief Gives back the column index of the node.
1.394 + ///
1.395 + /// Gives back the column index of the node.
1.396 + int col(Node n) const {
1.397 + return Parent::col(n);
1.398 + }
1.399 +
1.400 + /// \brief Gives back the width of the grid.
1.401 + ///
1.402 + /// Gives back the width of the grid.
1.403 + int width() const {
1.404 + return Parent::width();
1.405 + }
1.406 +
1.407 + /// \brief Gives back the height of the grid.
1.408 + ///
1.409 + /// Gives back the height of the grid.
1.410 + int height() const {
1.411 + return Parent::height();
1.412 + }
1.413 +
1.414 + /// \brief Gives back the arc goes down from the node.
1.415 + ///
1.416 + /// Gives back the arc goes down from the node. If there is not
1.417 + /// outgoing arc then it gives back \c INVALID.
1.418 + Arc down(Node n) const {
1.419 + Edge e = _down(n);
1.420 + return e != INVALID ? direct(e, true) : INVALID;
1.421 + }
1.422 +
1.423 + /// \brief Gives back the arc goes up from the node.
1.424 + ///
1.425 + /// Gives back the arc goes up from the node. If there is not
1.426 + /// outgoing arc then it gives back \c INVALID.
1.427 + Arc up(Node n) const {
1.428 + Edge e = _up(n);
1.429 + return e != INVALID ? direct(e, false) : INVALID;
1.430 + }
1.431 +
1.432 + /// \brief Gives back the arc goes right from the node.
1.433 + ///
1.434 + /// Gives back the arc goes right from the node. If there is not
1.435 + /// outgoing arc then it gives back \c INVALID.
1.436 + Arc right(Node n) const {
1.437 + Edge e = _right(n);
1.438 + return e != INVALID ? direct(e, true) : INVALID;
1.439 + }
1.440 +
1.441 + /// \brief Gives back the arc goes left from the node.
1.442 + ///
1.443 + /// Gives back the arc goes left from the node. If there is not
1.444 + /// outgoing arc then it gives back \c INVALID.
1.445 + Arc left(Node n) const {
1.446 + Edge e = _left(n);
1.447 + return e != INVALID ? direct(e, false) : INVALID;
1.448 + }
1.449 +
1.450 + }; // class GridGraph
1.451 +
1.452 + /// \brief Index map of the grid graph
1.453 + ///
1.454 + /// Just returns an IndexMap for the grid graph.
1.455 + inline GridGraph::IndexMap indexMap(const GridGraph& graph) {
1.456 + return GridGraph::IndexMap(graph);
1.457 + }
1.458 +
1.459 + /// \brief Row map of the grid graph
1.460 + ///
1.461 + /// Just returns a RowMap for the grid graph.
1.462 + inline GridGraph::RowMap rowMap(const GridGraph& graph) {
1.463 + return GridGraph::RowMap(graph);
1.464 + }
1.465 +
1.466 + /// \brief Column map of the grid graph
1.467 + ///
1.468 + /// Just returns a ColMap for the grid graph.
1.469 + inline GridGraph::ColMap colMap(const GridGraph& graph) {
1.470 + return GridGraph::ColMap(graph);
1.471 + }
1.472 +}
1.473 +
1.474 +#endif // GRID_GRAPH_H