Port grid graph structure from SVN 3503 (ticket #57)
authorPeter Kovacs <kpeter@inf.elte.hu>
Tue, 02 Sep 2008 22:32:04 +0200
changeset 346ada5f74d1c9e
parent 256 c760d691fe3c
child 347 160bf92c7cdc
Port grid graph structure from SVN 3503 (ticket #57)
lemon/Makefile.am
lemon/grid_graph.h
test/graph_test.cc
     1.1 --- a/lemon/Makefile.am	Tue Sep 02 22:27:19 2008 +0200
     1.2 +++ b/lemon/Makefile.am	Tue Sep 02 22:32:04 2008 +0200
     1.3 @@ -30,6 +30,7 @@
     1.4          lemon/dim2.h \
     1.5  	lemon/error.h \
     1.6          lemon/graph_to_eps.h \
     1.7 +        lemon/grid_graph.h \
     1.8  	lemon/kruskal.h \
     1.9  	lemon/lgf_reader.h \
    1.10  	lemon/lgf_writer.h \
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/lemon/grid_graph.h	Tue Sep 02 22:32:04 2008 +0200
     2.3 @@ -0,0 +1,471 @@
     2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library.
     2.7 + *
     2.8 + * Copyright (C) 2003-2008
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22 +#ifndef GRID_GRAPH_H
    2.23 +#define GRID_GRAPH_H
    2.24 +
    2.25 +#include <iostream>
    2.26 +#include <lemon/core.h>
    2.27 +#include <lemon/assert.h>
    2.28 +
    2.29 +#include <lemon/bits/base_extender.h>
    2.30 +#include <lemon/bits/graph_extender.h>
    2.31 +
    2.32 +#include <lemon/dim2.h>
    2.33 +
    2.34 +///\ingroup graphs
    2.35 +///\file
    2.36 +///\brief GridGraph class.
    2.37 +
    2.38 +namespace lemon {
    2.39 +
    2.40 +  class GridGraphBase {
    2.41 +
    2.42 +  public:
    2.43 +
    2.44 +    typedef GridGraphBase Graph;
    2.45 +
    2.46 +    class Node;
    2.47 +    class Arc;
    2.48 +
    2.49 +  public:
    2.50 +
    2.51 +    GridGraphBase() {}
    2.52 +
    2.53 +  protected:
    2.54 +
    2.55 +    void construct(int w, int h) {
    2.56 +      _height = h; _width = w;
    2.57 +      _nodeNum = h * w; _arcNum = 2 * _nodeNum - w - h;
    2.58 +      _arcLimit = _nodeNum - w;
    2.59 +    }
    2.60 +
    2.61 +    Arc _down(Node n) const {
    2.62 +      if (n.id < _nodeNum - _width) {
    2.63 +        return Arc(n.id);
    2.64 +      } else {
    2.65 +        return INVALID;
    2.66 +      }
    2.67 +    }
    2.68 +
    2.69 +    Arc _up(Node n) const {
    2.70 +      if (n.id >= _width) {
    2.71 +        return Arc(n.id - _width);
    2.72 +      } else {
    2.73 +        return INVALID;
    2.74 +      }
    2.75 +    }
    2.76 +
    2.77 +    Arc _right(Node n) const {
    2.78 +      if (n.id % _width < _width - 1) {
    2.79 +        return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1);
    2.80 +      } else {
    2.81 +        return INVALID;
    2.82 +      }
    2.83 +    }
    2.84 +
    2.85 +    Arc _left(Node n) const {
    2.86 +      if (n.id % _width > 0) {
    2.87 +        return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
    2.88 +      } else {
    2.89 +        return INVALID;
    2.90 +      }
    2.91 +    }
    2.92 +
    2.93 +  public:
    2.94 +
    2.95 +    Node operator()(int i, int j) const {
    2.96 +      LEMON_ASSERT(0 <= i && i < width() &&
    2.97 +                   0 <= j && j < height(), "lemon::GridGraph::IndexError");
    2.98 +      return Node(i + j * _width);
    2.99 +    }
   2.100 +
   2.101 +    int row(Node n) const {
   2.102 +      return n.id / _width;
   2.103 +    }
   2.104 +
   2.105 +    int col(Node n) const {
   2.106 +      return n.id % _width;
   2.107 +    }
   2.108 +
   2.109 +    int width() const {
   2.110 +      return _width;
   2.111 +    }
   2.112 +
   2.113 +    int height() const {
   2.114 +      return _height;
   2.115 +    }
   2.116 +
   2.117 +    typedef True NodeNumTag;
   2.118 +    typedef True ArcNumTag;
   2.119 +
   2.120 +    int nodeNum() const { return _nodeNum; }
   2.121 +    int arcNum() const { return _arcNum; }
   2.122 +
   2.123 +    int maxNodeId() const { return nodeNum() - 1; }
   2.124 +    int maxArcId() const { return arcNum() - 1; }
   2.125 +
   2.126 +    Node source(Arc e) const {
   2.127 +      if (e.id < _arcLimit) {
   2.128 +        return e.id;
   2.129 +      } else {
   2.130 +        return (e.id - _arcLimit) % (_width - 1) +
   2.131 +          (e.id - _arcLimit) / (_width - 1) * _width;
   2.132 +      }
   2.133 +    }
   2.134 +
   2.135 +    Node target(Arc e) const {
   2.136 +      if (e.id < _arcLimit) {
   2.137 +        return e.id + _width;
   2.138 +      } else {
   2.139 +        return (e.id - _arcLimit) % (_width - 1) +
   2.140 +          (e.id - _arcLimit) / (_width - 1) * _width + 1;
   2.141 +      }
   2.142 +    }
   2.143 +
   2.144 +    static int id(Node v) { return v.id; }
   2.145 +    static int id(Arc e) { return e.id; }
   2.146 +
   2.147 +    static Node nodeFromId(int id) { return Node(id);}
   2.148 +
   2.149 +    static Arc arcFromId(int id) { return Arc(id);}
   2.150 +
   2.151 +    typedef True FindArcTag;
   2.152 +
   2.153 +    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
   2.154 +      if (prev != INVALID) return INVALID;
   2.155 +      if (v.id - u.id == _width) return Arc(u.id);
   2.156 +      if (v.id - u.id == 1 && u.id % _width < _width - 1) {
   2.157 +        return Arc(u.id / _width * (_width - 1) +
   2.158 +                   u.id % _width + _arcLimit);
   2.159 +      }
   2.160 +      return INVALID;
   2.161 +    }
   2.162 +
   2.163 +    class Node {
   2.164 +      friend class GridGraphBase;
   2.165 +
   2.166 +    protected:
   2.167 +      int id;
   2.168 +      Node(int _id) : id(_id) {}
   2.169 +    public:
   2.170 +      Node() {}
   2.171 +      Node (Invalid) { id = -1; }
   2.172 +      bool operator==(const Node node) const { return id == node.id; }
   2.173 +      bool operator!=(const Node node) const { return id != node.id; }
   2.174 +      bool operator<(const Node node) const { return id < node.id; }
   2.175 +    };
   2.176 +
   2.177 +    class Arc {
   2.178 +      friend class GridGraphBase;
   2.179 +
   2.180 +    protected:
   2.181 +      int id;
   2.182 +      Arc(int _id) : id(_id) {}
   2.183 +    public:
   2.184 +      Arc() {}
   2.185 +      Arc (Invalid) { id = -1; }
   2.186 +      bool operator==(const Arc arc) const { return id == arc.id; }
   2.187 +      bool operator!=(const Arc arc) const { return id != arc.id; }
   2.188 +      bool operator<(const Arc arc) const { return id < arc.id; }
   2.189 +    };
   2.190 +
   2.191 +    void first(Node& node) const {
   2.192 +      node.id = nodeNum() - 1;
   2.193 +    }
   2.194 +
   2.195 +    static void next(Node& node) {
   2.196 +      --node.id;
   2.197 +    }
   2.198 +
   2.199 +    void first(Arc& arc) const {
   2.200 +      arc.id = arcNum() - 1;
   2.201 +    }
   2.202 +
   2.203 +    static void next(Arc& arc) {
   2.204 +      --arc.id;
   2.205 +    }
   2.206 +
   2.207 +    void firstOut(Arc& arc, const Node& node) const {
   2.208 +      if (node.id < _nodeNum - _width) {
   2.209 +        arc.id = node.id;
   2.210 +      } else if (node.id % _width < _width - 1) {
   2.211 +        arc.id = _arcLimit + node.id % _width +
   2.212 +          (node.id / _width) * (_width - 1);
   2.213 +      } else {
   2.214 +        arc.id = -1;
   2.215 +      }
   2.216 +    }
   2.217 +
   2.218 +    void nextOut(Arc& arc) const {
   2.219 +      if (arc.id >= _arcLimit) {
   2.220 +        arc.id = -1;
   2.221 +      } else if (arc.id % _width < _width - 1) {
   2.222 +        arc.id = _arcLimit + arc.id % _width +
   2.223 +          (arc.id / _width) * (_width - 1);
   2.224 +      } else {
   2.225 +        arc.id = -1;
   2.226 +      }
   2.227 +    }
   2.228 +
   2.229 +    void firstIn(Arc& arc, const Node& node) const {
   2.230 +      if (node.id >= _width) {
   2.231 +        arc.id = node.id - _width;
   2.232 +      } else if (node.id % _width > 0) {
   2.233 +        arc.id = _arcLimit + node.id % _width +
   2.234 +          (node.id / _width) * (_width - 1) - 1;
   2.235 +      } else {
   2.236 +        arc.id = -1;
   2.237 +      }
   2.238 +    }
   2.239 +
   2.240 +    void nextIn(Arc& arc) const {
   2.241 +      if (arc.id >= _arcLimit) {
   2.242 +        arc.id = -1;
   2.243 +      } else if (arc.id % _width > 0) {
   2.244 +        arc.id = _arcLimit + arc.id % _width +
   2.245 +          (arc.id / _width + 1) * (_width - 1) - 1;
   2.246 +      } else {
   2.247 +        arc.id = -1;
   2.248 +      }
   2.249 +    }
   2.250 +
   2.251 +  private:
   2.252 +    int _width, _height;
   2.253 +    int _nodeNum, _arcNum;
   2.254 +    int _arcLimit;
   2.255 +  };
   2.256 +
   2.257 +  typedef GraphExtender<UndirDigraphExtender<GridGraphBase> >
   2.258 +    ExtendedGridGraphBase;
   2.259 +
   2.260 +  /// \ingroup graphs
   2.261 +  ///
   2.262 +  /// \brief Grid graph class
   2.263 +  ///
   2.264 +  /// This class implements a special graph type. The nodes of the
   2.265 +  /// graph can be indiced by two integer \c (i,j) value where \c i
   2.266 +  /// is in the \c [0,width) range and j is in the [0, height) range.
   2.267 +  /// Two nodes are connected in the graph if the indices differ only
   2.268 +  /// on one position and only one is the difference.
   2.269 +  ///
   2.270 +  /// \image html grid_graph.png
   2.271 +  /// \image latex grid_graph.eps "Grid graph" width=\textwidth
   2.272 +  ///
   2.273 +  /// The graph can be indiced in the following way:
   2.274 +  ///\code
   2.275 +  /// GridGraph gr(w, h);
   2.276 +  /// GridGraph::NodeMap<int> val(gr);
   2.277 +  /// for (int i = 0; i < gr.width(); ++i) {
   2.278 +  ///   for (int j = 0; j < gr.height(); ++j) {
   2.279 +  ///     val[gr(i, j)] = i + j;
   2.280 +  ///   }
   2.281 +  /// }
   2.282 +  ///\endcode
   2.283 +  ///
   2.284 +  /// This graph type is fully conform to the \ref concepts::Graph
   2.285 +  /// "Undirected Graph" concept, and it also has an important extra
   2.286 +  /// feature that its maps are real \ref concepts::ReferenceMap
   2.287 +  /// "reference map"s.
   2.288 +  class GridGraph : public ExtendedGridGraphBase {
   2.289 +  public:
   2.290 +
   2.291 +    typedef ExtendedGridGraphBase Parent;
   2.292 +
   2.293 +    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
   2.294 +    ///
   2.295 +    /// Map to get the indices of the nodes as dim2::Point<int>.
   2.296 +    class IndexMap {
   2.297 +    public:
   2.298 +      /// The key type of the map
   2.299 +      typedef GridGraph::Node Key;
   2.300 +      /// The value type of the map
   2.301 +      typedef dim2::Point<int> Value;
   2.302 +
   2.303 +      /// Constructor
   2.304 +      IndexMap(const GridGraph& graph) : _graph(graph) {}
   2.305 +
   2.306 +      /// The subscript operator
   2.307 +      Value operator[](const Key& key) const {
   2.308 +        return dim2::Point<int>(_graph.row(key), _graph.col(key));
   2.309 +      }
   2.310 +
   2.311 +    private:
   2.312 +      const GridGraph& _graph;
   2.313 +    };
   2.314 +
   2.315 +    /// \brief Map to get the row of the nodes.
   2.316 +    ///
   2.317 +    /// Map to get the row of the nodes.
   2.318 +    class RowMap {
   2.319 +    public:
   2.320 +      /// The key type of the map
   2.321 +      typedef GridGraph::Node Key;
   2.322 +      /// The value type of the map
   2.323 +      typedef int Value;
   2.324 +
   2.325 +      /// Constructor
   2.326 +      RowMap(const GridGraph& graph) : _graph(graph) {}
   2.327 +
   2.328 +      /// The subscript operator
   2.329 +      Value operator[](const Key& key) const {
   2.330 +        return _graph.row(key);
   2.331 +      }
   2.332 +
   2.333 +    private:
   2.334 +      const GridGraph& _graph;
   2.335 +    };
   2.336 +
   2.337 +    /// \brief Map to get the column of the nodes.
   2.338 +    ///
   2.339 +    /// Map to get the column of the nodes.
   2.340 +    class ColMap {
   2.341 +    public:
   2.342 +      /// The key type of the map
   2.343 +      typedef GridGraph::Node Key;
   2.344 +      /// The value type of the map
   2.345 +      typedef int Value;
   2.346 +
   2.347 +      /// Constructor
   2.348 +      ColMap(const GridGraph& graph) : _graph(graph) {}
   2.349 +
   2.350 +      /// The subscript operator
   2.351 +      Value operator[](const Key& key) const {
   2.352 +        return _graph.col(key);
   2.353 +      }
   2.354 +
   2.355 +    private:
   2.356 +      const GridGraph& _graph;
   2.357 +    };
   2.358 +
   2.359 +    /// \brief Constructor
   2.360 +    ///
   2.361 +    /// Constructor.
   2.362 +    /// \param width The width of the grid.
   2.363 +    /// \param height The height of the grid.
   2.364 +    GridGraph(int width, int height) { construct(width, height); }
   2.365 +
   2.366 +    /// \brief Resize the graph
   2.367 +    ///
   2.368 +    /// Resize the grid.
   2.369 +    void resize(int width, int height) {
   2.370 +      Parent::notifier(Arc()).clear();
   2.371 +      Parent::notifier(Edge()).clear();
   2.372 +      Parent::notifier(Node()).clear();
   2.373 +      construct(width, height);
   2.374 +      Parent::notifier(Node()).build();
   2.375 +      Parent::notifier(Edge()).build();
   2.376 +      Parent::notifier(Arc()).build();
   2.377 +    }
   2.378 +
   2.379 +    /// \brief The node on the given position.
   2.380 +    ///
   2.381 +    /// Gives back the node on the given position.
   2.382 +    Node operator()(int i, int j) const {
   2.383 +      return Parent::operator()(i, j);
   2.384 +    }
   2.385 +
   2.386 +    /// \brief Gives back the row index of the node.
   2.387 +    ///
   2.388 +    /// Gives back the row index of the node.
   2.389 +    int row(Node n) const {
   2.390 +      return Parent::row(n);
   2.391 +    }
   2.392 +
   2.393 +    /// \brief Gives back the column index of the node.
   2.394 +    ///
   2.395 +    /// Gives back the column index of the node.
   2.396 +    int col(Node n) const {
   2.397 +      return Parent::col(n);
   2.398 +    }
   2.399 +
   2.400 +    /// \brief Gives back the width of the grid.
   2.401 +    ///
   2.402 +    /// Gives back the width of the grid.
   2.403 +    int width() const {
   2.404 +      return Parent::width();
   2.405 +    }
   2.406 +
   2.407 +    /// \brief Gives back the height of the grid.
   2.408 +    ///
   2.409 +    /// Gives back the height of the grid.
   2.410 +    int height() const {
   2.411 +      return Parent::height();
   2.412 +    }
   2.413 +
   2.414 +    /// \brief Gives back the arc goes down from the node.
   2.415 +    ///
   2.416 +    /// Gives back the arc goes down from the node. If there is not
   2.417 +    /// outgoing arc then it gives back \c INVALID.
   2.418 +    Arc down(Node n) const {
   2.419 +      Edge e = _down(n);
   2.420 +      return e != INVALID ? direct(e, true) : INVALID;
   2.421 +    }
   2.422 +
   2.423 +    /// \brief Gives back the arc goes up from the node.
   2.424 +    ///
   2.425 +    /// Gives back the arc goes up from the node. If there is not
   2.426 +    /// outgoing arc then it gives back \c INVALID.
   2.427 +    Arc up(Node n) const {
   2.428 +      Edge e = _up(n);
   2.429 +      return e != INVALID ? direct(e, false) : INVALID;
   2.430 +    }
   2.431 +
   2.432 +    /// \brief Gives back the arc goes right from the node.
   2.433 +    ///
   2.434 +    /// Gives back the arc goes right from the node. If there is not
   2.435 +    /// outgoing arc then it gives back \c INVALID.
   2.436 +    Arc right(Node n) const {
   2.437 +      Edge e = _right(n);
   2.438 +      return e != INVALID ? direct(e, true) : INVALID;
   2.439 +    }
   2.440 +
   2.441 +    /// \brief Gives back the arc goes left from the node.
   2.442 +    ///
   2.443 +    /// Gives back the arc goes left from the node. If there is not
   2.444 +    /// outgoing arc then it gives back \c INVALID.
   2.445 +    Arc left(Node n) const {
   2.446 +      Edge e = _left(n);
   2.447 +      return e != INVALID ? direct(e, false) : INVALID;
   2.448 +    }
   2.449 +
   2.450 +  }; // class GridGraph
   2.451 +
   2.452 +  /// \brief Index map of the grid graph
   2.453 +  ///
   2.454 +  /// Just returns an IndexMap for the grid graph.
   2.455 +  inline GridGraph::IndexMap indexMap(const GridGraph& graph) {
   2.456 +    return GridGraph::IndexMap(graph);
   2.457 +  }
   2.458 +
   2.459 +  /// \brief Row map of the grid graph
   2.460 +  ///
   2.461 +  /// Just returns a RowMap for the grid graph.
   2.462 +  inline GridGraph::RowMap rowMap(const GridGraph& graph) {
   2.463 +    return GridGraph::RowMap(graph);
   2.464 +  }
   2.465 +
   2.466 +  /// \brief Column map of the grid graph
   2.467 +  ///
   2.468 +  /// Just returns a ColMap for the grid graph.
   2.469 +  inline GridGraph::ColMap colMap(const GridGraph& graph) {
   2.470 +    return GridGraph::ColMap(graph);
   2.471 +  }
   2.472 +}
   2.473 +
   2.474 +#endif // GRID_GRAPH_H
     3.1 --- a/test/graph_test.cc	Tue Sep 02 22:27:19 2008 +0200
     3.2 +++ b/test/graph_test.cc	Tue Sep 02 22:32:04 2008 +0200
     3.3 @@ -20,7 +20,7 @@
     3.4  #include <lemon/list_graph.h>
     3.5  #include <lemon/smart_graph.h>
     3.6  // #include <lemon/full_graph.h>
     3.7 -// #include <lemon/grid_graph.h>
     3.8 +#include <lemon/grid_graph.h>
     3.9  
    3.10  #include "test_tools.h"
    3.11  #include "graph_test.h"
    3.12 @@ -126,12 +126,10 @@
    3.13    }
    3.14  //  { // Checking FullGraph
    3.15  //    checkConcept<Graph, FullGraph>();
    3.16 -//    checkGraphIterators<FullGraph>();
    3.17  //  }
    3.18 -//  { // Checking GridGraph
    3.19 -//    checkConcept<Graph, GridGraph>();
    3.20 -//    checkGraphIterators<GridGraph>();
    3.21 -//  }
    3.22 +  { // Checking GridGraph
    3.23 +    checkConcept<Graph, GridGraph>();
    3.24 +  }
    3.25  }
    3.26  
    3.27  template <typename Graph>
    3.28 @@ -188,49 +186,77 @@
    3.29    check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    3.30  }
    3.31  
    3.32 -// void checkGridGraph(const GridGraph& g, int w, int h) {
    3.33 -//   check(g.width() == w, "Wrong width");
    3.34 -//   check(g.height() == h, "Wrong height");
    3.35 +void checkGridGraph(const GridGraph& g, int w, int h) {
    3.36 +  check(g.width() == w, "Wrong width");
    3.37 +  check(g.height() == h, "Wrong height");
    3.38  
    3.39 -//   for (int i = 0; i < w; ++i) {
    3.40 -//     for (int j = 0; j < h; ++j) {
    3.41 -//       check(g.col(g(i, j)) == i, "Wrong col");
    3.42 -//       check(g.row(g(i, j)) == j, "Wrong row");
    3.43 -//     }
    3.44 -//   }
    3.45 +  for (int i = 0; i < w; ++i) {
    3.46 +    for (int j = 0; j < h; ++j) {
    3.47 +      check(g.col(g(i, j)) == i, "Wrong col");
    3.48 +      check(g.row(g(i, j)) == j, "Wrong row");
    3.49 +    }
    3.50 +  }
    3.51  
    3.52 -//   for (int i = 0; i < w; ++i) {
    3.53 -//     for (int j = 0; j < h - 1; ++j) {
    3.54 -//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
    3.55 -//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
    3.56 -//     }
    3.57 -//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
    3.58 -//   }
    3.59 +  for (int i = 0; i < w; ++i) {
    3.60 +    for (int j = 0; j < h - 1; ++j) {
    3.61 +      check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
    3.62 +      check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
    3.63 +    }
    3.64 +    check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
    3.65 +  }
    3.66  
    3.67 -//   for (int i = 0; i < w; ++i) {
    3.68 -//     for (int j = 1; j < h; ++j) {
    3.69 -//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
    3.70 -//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
    3.71 -//     }
    3.72 -//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
    3.73 -//   }
    3.74 +  for (int i = 0; i < w; ++i) {
    3.75 +    for (int j = 1; j < h; ++j) {
    3.76 +      check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
    3.77 +      check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
    3.78 +    }
    3.79 +    check(g.up(g(i, 0)) == INVALID, "Wrong up");
    3.80 +  }
    3.81  
    3.82 -//   for (int j = 0; j < h; ++j) {
    3.83 -//     for (int i = 0; i < w - 1; ++i) {
    3.84 -//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
    3.85 -//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
    3.86 -//     }
    3.87 -//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
    3.88 -//   }
    3.89 +  for (int j = 0; j < h; ++j) {
    3.90 +    for (int i = 0; i < w - 1; ++i) {
    3.91 +      check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
    3.92 +      check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
    3.93 +    }
    3.94 +    check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
    3.95 +  }
    3.96  
    3.97 -//   for (int j = 0; j < h; ++j) {
    3.98 -//     for (int i = 1; i < w; ++i) {
    3.99 -//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
   3.100 -//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
   3.101 -//     }
   3.102 -//     check(g.left(g(0, j)) == INVALID, "Wrong left");
   3.103 -//   }
   3.104 -// }
   3.105 +  for (int j = 0; j < h; ++j) {
   3.106 +    for (int i = 1; i < w; ++i) {
   3.107 +      check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
   3.108 +      check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
   3.109 +    }
   3.110 +    check(g.left(g(0, j)) == INVALID, "Wrong left");
   3.111 +  }
   3.112 +
   3.113 +  checkGraphNodeList(g, w*h);
   3.114 +  checkGraphArcList(g, 2*(2*w*h-w-h));
   3.115 +  checkGraphEdgeList(g, 2*w*h-w-h);
   3.116 +
   3.117 +  checkGraphOutArcList(g, g(0,0), 2);
   3.118 +  checkGraphOutArcList(g, g(0,1), 3);
   3.119 +  checkGraphOutArcList(g, g(w-2,h-2), 4);
   3.120 +
   3.121 +  checkGraphInArcList(g, g(0,0), 2);
   3.122 +  checkGraphInArcList(g, g(0,1), 3);
   3.123 +  checkGraphInArcList(g, g(w-2,h-2), 4);
   3.124 +
   3.125 +  checkGraphIncEdgeList(g, g(0,0), 2);
   3.126 +  checkGraphIncEdgeList(g, g(0,1), 3);
   3.127 +  checkGraphIncEdgeList(g, g(w-2,h-2), 4);
   3.128 +
   3.129 +  checkGraphConArcList(g, 2*(2*w*h-w-h));
   3.130 +  checkGraphConEdgeList(g, 2*w*h-w-h);
   3.131 +
   3.132 +  checkArcDirections(g);
   3.133 +
   3.134 +  checkNodeIds(g);
   3.135 +  checkArcIds(g);
   3.136 +  checkEdgeIds(g);
   3.137 +  checkGraphNodeMap(g);
   3.138 +  checkGraphArcMap(g);
   3.139 +  checkGraphEdgeMap(g);
   3.140 +}
   3.141  
   3.142  void checkGraphs() {
   3.143    { // Checking ListGraph
   3.144 @@ -246,12 +272,10 @@
   3.145  //     checkGraphNodeList(g, 5);
   3.146  //     checkGraphEdgeList(g, 10);
   3.147  //   }
   3.148 -//   { // Checking GridGraph
   3.149 -//     GridGraph g(5, 6);
   3.150 -//     checkGraphNodeList(g, 30);
   3.151 -//     checkGraphEdgeList(g, 49);
   3.152 -//     checkGridGraph(g, 5, 6);
   3.153 -//   }
   3.154 +  { // Checking GridGraph
   3.155 +    GridGraph g(5, 6);
   3.156 +    checkGridGraph(g, 5, 6);
   3.157 +  }
   3.158  }
   3.159  
   3.160  int main() {