1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
23 #include <lemon/core.h>
24 #include <lemon/assert.h>
26 #include <lemon/bits/base_extender.h>
27 #include <lemon/bits/graph_extender.h>
29 #include <lemon/dim2.h>
33 ///\brief GridGraph class.
41 typedef GridGraphBase Graph;
52 void construct(int w, int h) {
53 _height = h; _width = w;
54 _nodeNum = h * w; _arcNum = 2 * _nodeNum - w - h;
55 _arcLimit = _nodeNum - w;
58 Arc _down(Node n) const {
59 if (n.id < _nodeNum - _width) {
66 Arc _up(Node n) const {
68 return Arc(n.id - _width);
74 Arc _right(Node n) const {
75 if (n.id % _width < _width - 1) {
76 return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1);
82 Arc _left(Node n) const {
83 if (n.id % _width > 0) {
84 return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
92 Node operator()(int i, int j) const {
93 LEMON_ASSERT(0 <= i && i < width() &&
94 0 <= j && j < height(), "lemon::GridGraph::IndexError");
95 return Node(i + j * _width);
98 int row(Node n) const {
102 int col(Node n) const {
103 return n.id % _width;
114 typedef True NodeNumTag;
115 typedef True ArcNumTag;
117 int nodeNum() const { return _nodeNum; }
118 int arcNum() const { return _arcNum; }
120 int maxNodeId() const { return nodeNum() - 1; }
121 int maxArcId() const { return arcNum() - 1; }
123 Node source(Arc e) const {
124 if (e.id < _arcLimit) {
127 return (e.id - _arcLimit) % (_width - 1) +
128 (e.id - _arcLimit) / (_width - 1) * _width;
132 Node target(Arc e) const {
133 if (e.id < _arcLimit) {
134 return e.id + _width;
136 return (e.id - _arcLimit) % (_width - 1) +
137 (e.id - _arcLimit) / (_width - 1) * _width + 1;
141 static int id(Node v) { return v.id; }
142 static int id(Arc e) { return e.id; }
144 static Node nodeFromId(int id) { return Node(id);}
146 static Arc arcFromId(int id) { return Arc(id);}
148 typedef True FindArcTag;
150 Arc findArc(Node u, Node v, Arc prev = INVALID) const {
151 if (prev != INVALID) return INVALID;
152 if (v.id - u.id == _width) return Arc(u.id);
153 if (v.id - u.id == 1 && u.id % _width < _width - 1) {
154 return Arc(u.id / _width * (_width - 1) +
155 u.id % _width + _arcLimit);
161 friend class GridGraphBase;
165 Node(int _id) : id(_id) {}
168 Node (Invalid) { id = -1; }
169 bool operator==(const Node node) const { return id == node.id; }
170 bool operator!=(const Node node) const { return id != node.id; }
171 bool operator<(const Node node) const { return id < node.id; }
175 friend class GridGraphBase;
179 Arc(int _id) : id(_id) {}
182 Arc (Invalid) { id = -1; }
183 bool operator==(const Arc arc) const { return id == arc.id; }
184 bool operator!=(const Arc arc) const { return id != arc.id; }
185 bool operator<(const Arc arc) const { return id < arc.id; }
188 void first(Node& node) const {
189 node.id = nodeNum() - 1;
192 static void next(Node& node) {
196 void first(Arc& arc) const {
197 arc.id = arcNum() - 1;
200 static void next(Arc& arc) {
204 void firstOut(Arc& arc, const Node& node) const {
205 if (node.id < _nodeNum - _width) {
207 } else if (node.id % _width < _width - 1) {
208 arc.id = _arcLimit + node.id % _width +
209 (node.id / _width) * (_width - 1);
215 void nextOut(Arc& arc) const {
216 if (arc.id >= _arcLimit) {
218 } else if (arc.id % _width < _width - 1) {
219 arc.id = _arcLimit + arc.id % _width +
220 (arc.id / _width) * (_width - 1);
226 void firstIn(Arc& arc, const Node& node) const {
227 if (node.id >= _width) {
228 arc.id = node.id - _width;
229 } else if (node.id % _width > 0) {
230 arc.id = _arcLimit + node.id % _width +
231 (node.id / _width) * (_width - 1) - 1;
237 void nextIn(Arc& arc) const {
238 if (arc.id >= _arcLimit) {
240 } else if (arc.id % _width > 0) {
241 arc.id = _arcLimit + arc.id % _width +
242 (arc.id / _width + 1) * (_width - 1) - 1;
250 int _nodeNum, _arcNum;
254 typedef GraphExtender<UndirDigraphExtender<GridGraphBase> >
255 ExtendedGridGraphBase;
259 /// \brief Grid graph class
261 /// This class implements a special graph type. The nodes of the
262 /// graph can be indiced by two integer \c (i,j) value where \c i
263 /// is in the \c [0,width) range and j is in the [0, height) range.
264 /// Two nodes are connected in the graph if the indices differ only
265 /// on one position and only one is the difference.
267 /// \image html grid_graph.png
268 /// \image latex grid_graph.eps "Grid graph" width=\textwidth
270 /// The graph can be indiced in the following way:
272 /// GridGraph gr(w, h);
273 /// GridGraph::NodeMap<int> val(gr);
274 /// for (int i = 0; i < gr.width(); ++i) {
275 /// for (int j = 0; j < gr.height(); ++j) {
276 /// val[gr(i, j)] = i + j;
281 /// This graph type is fully conform to the \ref concepts::Graph
282 /// "Undirected Graph" concept, and it also has an important extra
283 /// feature that its maps are real \ref concepts::ReferenceMap
284 /// "reference map"s.
285 class GridGraph : public ExtendedGridGraphBase {
288 typedef ExtendedGridGraphBase Parent;
290 /// \brief Map to get the indices of the nodes as dim2::Point<int>.
292 /// Map to get the indices of the nodes as dim2::Point<int>.
295 /// The key type of the map
296 typedef GridGraph::Node Key;
297 /// The value type of the map
298 typedef dim2::Point<int> Value;
301 IndexMap(const GridGraph& graph) : _graph(graph) {}
303 /// The subscript operator
304 Value operator[](const Key& key) const {
305 return dim2::Point<int>(_graph.row(key), _graph.col(key));
309 const GridGraph& _graph;
312 /// \brief Map to get the row of the nodes.
314 /// Map to get the row of the nodes.
317 /// The key type of the map
318 typedef GridGraph::Node Key;
319 /// The value type of the map
323 RowMap(const GridGraph& graph) : _graph(graph) {}
325 /// The subscript operator
326 Value operator[](const Key& key) const {
327 return _graph.row(key);
331 const GridGraph& _graph;
334 /// \brief Map to get the column of the nodes.
336 /// Map to get the column of the nodes.
339 /// The key type of the map
340 typedef GridGraph::Node Key;
341 /// The value type of the map
345 ColMap(const GridGraph& graph) : _graph(graph) {}
347 /// The subscript operator
348 Value operator[](const Key& key) const {
349 return _graph.col(key);
353 const GridGraph& _graph;
356 /// \brief Constructor
359 /// \param width The width of the grid.
360 /// \param height The height of the grid.
361 GridGraph(int width, int height) { construct(width, height); }
363 /// \brief Resize the graph
366 void resize(int width, int height) {
367 Parent::notifier(Arc()).clear();
368 Parent::notifier(Edge()).clear();
369 Parent::notifier(Node()).clear();
370 construct(width, height);
371 Parent::notifier(Node()).build();
372 Parent::notifier(Edge()).build();
373 Parent::notifier(Arc()).build();
376 /// \brief The node on the given position.
378 /// Gives back the node on the given position.
379 Node operator()(int i, int j) const {
380 return Parent::operator()(i, j);
383 /// \brief Gives back the row index of the node.
385 /// Gives back the row index of the node.
386 int row(Node n) const {
387 return Parent::row(n);
390 /// \brief Gives back the column index of the node.
392 /// Gives back the column index of the node.
393 int col(Node n) const {
394 return Parent::col(n);
397 /// \brief Gives back the width of the grid.
399 /// Gives back the width of the grid.
401 return Parent::width();
404 /// \brief Gives back the height of the grid.
406 /// Gives back the height of the grid.
408 return Parent::height();
411 /// \brief Gives back the arc goes down from the node.
413 /// Gives back the arc goes down from the node. If there is not
414 /// outgoing arc then it gives back \c INVALID.
415 Arc down(Node n) const {
417 return e != INVALID ? direct(e, true) : INVALID;
420 /// \brief Gives back the arc goes up from the node.
422 /// Gives back the arc goes up from the node. If there is not
423 /// outgoing arc then it gives back \c INVALID.
424 Arc up(Node n) const {
426 return e != INVALID ? direct(e, false) : INVALID;
429 /// \brief Gives back the arc goes right from the node.
431 /// Gives back the arc goes right from the node. If there is not
432 /// outgoing arc then it gives back \c INVALID.
433 Arc right(Node n) const {
435 return e != INVALID ? direct(e, true) : INVALID;
438 /// \brief Gives back the arc goes left from the node.
440 /// Gives back the arc goes left from the node. If there is not
441 /// outgoing arc then it gives back \c INVALID.
442 Arc left(Node n) const {
444 return e != INVALID ? direct(e, false) : INVALID;
447 }; // class GridGraph
449 /// \brief Index map of the grid graph
451 /// Just returns an IndexMap for the grid graph.
452 inline GridGraph::IndexMap indexMap(const GridGraph& graph) {
453 return GridGraph::IndexMap(graph);
456 /// \brief Row map of the grid graph
458 /// Just returns a RowMap for the grid graph.
459 inline GridGraph::RowMap rowMap(const GridGraph& graph) {
460 return GridGraph::RowMap(graph);
463 /// \brief Column map of the grid graph
465 /// Just returns a ColMap for the grid graph.
466 inline GridGraph::ColMap colMap(const GridGraph& graph) {
467 return GridGraph::ColMap(graph);
471 #endif // GRID_GRAPH_H