lemon/grid_graph.h
changeset 802 994c7df296c9
parent 582 7a28e215f715
child 735 853fcddcf282
     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