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() {