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
22 #include <lemon/core.h>
23 #include <lemon/bits/graph_extender.h>
24 #include <lemon/dim2.h>
25 #include <lemon/assert.h>
29 ///\brief GridGraph class.
37 typedef GridGraphBase Graph;
49 void construct(int width, int height) {
50 _width = width; _height = height;
51 _node_num = width * height;
52 _edge_num = 2 * _node_num - width - height;
53 _edge_limit = _node_num - _width;
58 Node operator()(int i, int j) const {
59 LEMON_DEBUG(0 <= i && i < _width &&
60 0 <= j && j < _height, "Index out of range");
61 return Node(i + j * _width);
64 int col(Node n) const {
65 return n._id % _width;
68 int row(Node n) const {
69 return n._id / _width;
72 dim2::Point<int> pos(Node n) const {
73 return dim2::Point<int>(col(n), row(n));
84 typedef True NodeNumTag;
85 typedef True ArcNumTag;
87 int nodeNum() const { return _node_num; }
88 int edgeNum() const { return _edge_num; }
89 int arcNum() const { return 2 * _edge_num; }
91 Node u(Edge edge) const {
92 if (edge._id < _edge_limit) {
95 return (edge._id - _edge_limit) % (_width - 1) +
96 (edge._id - _edge_limit) / (_width - 1) * _width;
100 Node v(Edge edge) const {
101 if (edge._id < _edge_limit) {
102 return edge._id + _width;
104 return (edge._id - _edge_limit) % (_width - 1) +
105 (edge._id - _edge_limit) / (_width - 1) * _width + 1;
109 Node source(Arc arc) const {
110 return (arc._id & 1) == 1 ? u(arc) : v(arc);
113 Node target(Arc arc) const {
114 return (arc._id & 1) == 1 ? v(arc) : u(arc);
117 static int id(Node node) { return node._id; }
118 static int id(Edge edge) { return edge._id; }
119 static int id(Arc arc) { return arc._id; }
121 int maxNodeId() const { return _node_num - 1; }
122 int maxEdgeId() const { return _edge_num - 1; }
123 int maxArcId() const { return 2 * _edge_num - 1; }
125 static Node nodeFromId(int id) { return Node(id);}
126 static Edge edgeFromId(int id) { return Edge(id);}
127 static Arc arcFromId(int id) { return Arc(id);}
129 typedef True FindEdgeTag;
131 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
132 if (prev != INVALID) return INVALID;
134 if (v._id - u._id == _width)
136 if (v._id - u._id == 1 && u._id % _width < _width - 1) {
137 return Edge(u._id / _width * (_width - 1) +
138 u._id % _width + _edge_limit);
141 if (u._id - v._id == _width)
143 if (u._id - v._id == 1 && v._id % _width < _width - 1) {
144 return Edge(v._id / _width * (_width - 1) +
145 v._id % _width + _edge_limit);
151 Arc findArc(Node u, Node v, Arc prev = INVALID) const {
152 if (prev != INVALID) return INVALID;
154 if (v._id - u._id == _width)
155 return Arc((u._id << 1) | 1);
156 if (v._id - u._id == 1 && u._id % _width < _width - 1) {
157 return Arc(((u._id / _width * (_width - 1) +
158 u._id % _width + _edge_limit) << 1) | 1);
161 if (u._id - v._id == _width)
162 return Arc(v._id << 1);
163 if (u._id - v._id == 1 && v._id % _width < _width - 1) {
164 return Arc((v._id / _width * (_width - 1) +
165 v._id % _width + _edge_limit) << 1);
172 friend class GridGraphBase;
176 Node(int id) : _id(id) {}
179 Node (Invalid) : _id(-1) {}
180 bool operator==(const Node node) const {return _id == node._id;}
181 bool operator!=(const Node node) const {return _id != node._id;}
182 bool operator<(const Node node) const {return _id < node._id;}
186 friend class GridGraphBase;
191 Edge(int id) : _id(id) {}
195 Edge (Invalid) : _id(-1) {}
196 bool operator==(const Edge edge) const {return _id == edge._id;}
197 bool operator!=(const Edge edge) const {return _id != edge._id;}
198 bool operator<(const Edge edge) const {return _id < edge._id;}
202 friend class GridGraphBase;
207 Arc(int id) : _id(id) {}
211 Arc (Invalid) : _id(-1) {}
212 operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
213 bool operator==(const Arc arc) const {return _id == arc._id;}
214 bool operator!=(const Arc arc) const {return _id != arc._id;}
215 bool operator<(const Arc arc) const {return _id < arc._id;}
218 static bool direction(Arc arc) {
219 return (arc._id & 1) == 1;
222 static Arc direct(Edge edge, bool dir) {
223 return Arc((edge._id << 1) | (dir ? 1 : 0));
226 void first(Node& node) const {
227 node._id = _node_num - 1;
230 static void next(Node& node) {
234 void first(Edge& edge) const {
235 edge._id = _edge_num - 1;
238 static void next(Edge& edge) {
242 void first(Arc& arc) const {
243 arc._id = 2 * _edge_num - 1;
246 static void next(Arc& arc) {
250 void firstOut(Arc& arc, const Node& node) const {
251 if (node._id % _width < _width - 1) {
252 arc._id = (_edge_limit + node._id % _width +
253 (node._id / _width) * (_width - 1)) << 1 | 1;
256 if (node._id < _node_num - _width) {
257 arc._id = node._id << 1 | 1;
260 if (node._id % _width > 0) {
261 arc._id = (_edge_limit + node._id % _width +
262 (node._id / _width) * (_width - 1) - 1) << 1;
265 if (node._id >= _width) {
266 arc._id = (node._id - _width) << 1;
272 void nextOut(Arc& arc) const {
273 int nid = arc._id >> 1;
274 if ((arc._id & 1) == 1) {
275 if (nid >= _edge_limit) {
276 nid = (nid - _edge_limit) % (_width - 1) +
277 (nid - _edge_limit) / (_width - 1) * _width;
278 if (nid < _node_num - _width) {
279 arc._id = nid << 1 | 1;
283 if (nid % _width > 0) {
284 arc._id = (_edge_limit + nid % _width +
285 (nid / _width) * (_width - 1) - 1) << 1;
289 arc._id = (nid - _width) << 1;
293 if (nid >= _edge_limit) {
294 nid = (nid - _edge_limit) % (_width - 1) +
295 (nid - _edge_limit) / (_width - 1) * _width + 1;
297 arc._id = (nid - _width) << 1;
305 void firstIn(Arc& arc, const Node& node) const {
306 if (node._id % _width < _width - 1) {
307 arc._id = (_edge_limit + node._id % _width +
308 (node._id / _width) * (_width - 1)) << 1;
311 if (node._id < _node_num - _width) {
312 arc._id = node._id << 1;
315 if (node._id % _width > 0) {
316 arc._id = (_edge_limit + node._id % _width +
317 (node._id / _width) * (_width - 1) - 1) << 1 | 1;
320 if (node._id >= _width) {
321 arc._id = (node._id - _width) << 1 | 1;
327 void nextIn(Arc& arc) const {
328 int nid = arc._id >> 1;
329 if ((arc._id & 1) == 0) {
330 if (nid >= _edge_limit) {
331 nid = (nid - _edge_limit) % (_width - 1) +
332 (nid - _edge_limit) / (_width - 1) * _width;
333 if (nid < _node_num - _width) {
338 if (nid % _width > 0) {
339 arc._id = (_edge_limit + nid % _width +
340 (nid / _width) * (_width - 1) - 1) << 1 | 1;
344 arc._id = (nid - _width) << 1 | 1;
348 if (nid >= _edge_limit) {
349 nid = (nid - _edge_limit) % (_width - 1) +
350 (nid - _edge_limit) / (_width - 1) * _width + 1;
352 arc._id = (nid - _width) << 1 | 1;
360 void firstInc(Edge& edge, bool& dir, const Node& node) const {
361 if (node._id % _width < _width - 1) {
362 edge._id = _edge_limit + node._id % _width +
363 (node._id / _width) * (_width - 1);
367 if (node._id < _node_num - _width) {
372 if (node._id % _width > 0) {
373 edge._id = _edge_limit + node._id % _width +
374 (node._id / _width) * (_width - 1) - 1;
378 if (node._id >= _width) {
379 edge._id = node._id - _width;
387 void nextInc(Edge& edge, bool& dir) const {
390 if (nid >= _edge_limit) {
391 nid = (nid - _edge_limit) % (_width - 1) +
392 (nid - _edge_limit) / (_width - 1) * _width;
393 if (nid < _node_num - _width) {
398 if (nid % _width > 0) {
399 edge._id = _edge_limit + nid % _width +
400 (nid / _width) * (_width - 1) - 1;
405 edge._id = nid - _width;
410 if (nid >= _edge_limit) {
411 nid = (nid - _edge_limit) % (_width - 1) +
412 (nid - _edge_limit) / (_width - 1) * _width + 1;
414 edge._id = nid - _width;
423 Arc right(Node n) const {
424 if (n._id % _width < _width - 1) {
425 return Arc(((_edge_limit + n._id % _width +
426 (n._id / _width) * (_width - 1)) << 1) | 1);
432 Arc left(Node n) const {
433 if (n._id % _width > 0) {
434 return Arc((_edge_limit + n._id % _width +
435 (n._id / _width) * (_width - 1) - 1) << 1);
441 Arc up(Node n) const {
442 if (n._id < _edge_limit) {
443 return Arc((n._id << 1) | 1);
449 Arc down(Node n) const {
450 if (n._id >= _width) {
451 return Arc((n._id - _width) << 1);
459 int _node_num, _edge_num;
464 typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
468 /// \brief Grid graph class
470 /// This class implements a special graph type. The nodes of the
471 /// graph can be indexed by two integer \c (i,j) value where \c i is
472 /// in the \c [0..width()-1] range and j is in the \c
473 /// [0..height()-1] range. Two nodes are connected in the graph if
474 /// the indexes differ exactly on one position and exactly one is
475 /// the difference. The nodes of the graph be indexed by position
476 /// with \c operator()() function. The positions of the nodes can be
477 /// get with \c pos(), \c col() and \c row() members. The outgoing
478 /// arcs can be retrieved with the \c right(), \c up(), \c left()
479 /// and \c down() functions, where the bottom-left corner is the
482 /// \image html grid_graph.png
483 /// \image latex grid_graph.eps "Grid digraph" row_num=\textrow_num
485 /// A short example about the basic usage:
487 /// GridGraph graph(rows, cols);
488 /// GridGraph::NodeMap<int> val(graph);
489 /// for (int i = 0; i < graph.width(); ++i) {
490 /// for (int j = 0; j < graph.height(); ++j) {
491 /// val[graph(i, j)] = i + j;
496 /// The graph type is fully conform to the \ref concepts::Graph
497 /// "Graph" concept, and it also has an important extra feature
498 /// that its maps are real \ref concepts::ReferenceMap "reference
500 class GridGraph : public ExtendedGridGraphBase {
503 typedef ExtendedGridGraphBase Parent;
505 /// \brief Map to get the indices of the nodes as dim2::Point<int>.
507 /// Map to get the indices of the nodes as dim2::Point<int>.
510 /// \brief The key type of the map
511 typedef GridGraph::Node Key;
512 /// \brief The value type of the map
513 typedef dim2::Point<int> Value;
515 /// \brief Constructor
518 IndexMap(const GridGraph& graph) : _graph(graph) {}
520 /// \brief The subscript operator
522 /// The subscript operator.
523 Value operator[](Key key) const {
524 return _graph.pos(key);
528 const GridGraph& _graph;
531 /// \brief Map to get the column of the nodes.
533 /// Map to get the column of the nodes.
536 /// \brief The key type of the map
537 typedef GridGraph::Node Key;
538 /// \brief The value type of the map
541 /// \brief Constructor
544 ColMap(const GridGraph& graph) : _graph(graph) {}
546 /// \brief The subscript operator
548 /// The subscript operator.
549 Value operator[](Key key) const {
550 return _graph.col(key);
554 const GridGraph& _graph;
557 /// \brief Map to get the row of the nodes.
559 /// Map to get the row of the nodes.
562 /// \brief The key type of the map
563 typedef GridGraph::Node Key;
564 /// \brief The value type of the map
567 /// \brief Constructor
570 RowMap(const GridGraph& graph) : _graph(graph) {}
572 /// \brief The subscript operator
574 /// The subscript operator.
575 Value operator[](Key key) const {
576 return _graph.row(key);
580 const GridGraph& _graph;
583 /// \brief Constructor
585 /// Construct a grid graph with given size.
586 GridGraph(int width, int height) { construct(width, height); }
588 /// \brief Resize the graph
590 /// Resize the graph. The function will fully destroy and rebuild
591 /// the graph. This cause that the maps of the graph will
592 /// reallocated automatically and the previous values will be
594 void resize(int width, int height) {
595 Parent::notifier(Arc()).clear();
596 Parent::notifier(Edge()).clear();
597 Parent::notifier(Node()).clear();
598 construct(width, height);
599 Parent::notifier(Node()).build();
600 Parent::notifier(Edge()).build();
601 Parent::notifier(Arc()).build();
604 /// \brief The node on the given position.
606 /// Gives back the node on the given position.
607 Node operator()(int i, int j) const {
608 return Parent::operator()(i, j);
611 /// \brief Gives back the column index of the node.
613 /// Gives back the column index of the node.
614 int col(Node n) const {
615 return Parent::col(n);
618 /// \brief Gives back the row index of the node.
620 /// Gives back the row index of the node.
621 int row(Node n) const {
622 return Parent::row(n);
625 /// \brief Gives back the position of the node.
627 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
628 dim2::Point<int> pos(Node n) const {
629 return Parent::pos(n);
632 /// \brief Gives back the number of the columns.
634 /// Gives back the number of the columns.
636 return Parent::width();
639 /// \brief Gives back the number of the rows.
641 /// Gives back the number of the rows.
643 return Parent::height();
646 /// \brief Gives back the arc goes right from the node.
648 /// Gives back the arc goes right from the node. If there is not
649 /// outgoing arc then it gives back INVALID.
650 Arc right(Node n) const {
651 return Parent::right(n);
654 /// \brief Gives back the arc goes left from the node.
656 /// Gives back the arc goes left from the node. If there is not
657 /// outgoing arc then it gives back INVALID.
658 Arc left(Node n) const {
659 return Parent::left(n);
662 /// \brief Gives back the arc goes up from the node.
664 /// Gives back the arc goes up from the node. If there is not
665 /// outgoing arc then it gives back INVALID.
666 Arc up(Node n) const {
667 return Parent::up(n);
670 /// \brief Gives back the arc goes down from the node.
672 /// Gives back the arc goes down from the node. If there is not
673 /// outgoing arc then it gives back INVALID.
674 Arc down(Node n) const {
675 return Parent::down(n);
678 /// \brief Index map of the grid graph
680 /// Just returns an IndexMap for the grid graph.
681 IndexMap indexMap() const {
682 return IndexMap(*this);
685 /// \brief Row map of the grid graph
687 /// Just returns a RowMap for the grid graph.
688 RowMap rowMap() const {
689 return RowMap(*this);
692 /// \brief Column map of the grid graph
694 /// Just returns a ColMap for the grid graph.
695 ColMap colMap() const {
696 return ColMap(*this);