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;
192 Edge(int id) : _id(id) {}
196 Edge (Invalid) : _id(-1) {}
197 bool operator==(const Edge edge) const {return _id == edge._id;}
198 bool operator!=(const Edge edge) const {return _id != edge._id;}
199 bool operator<(const Edge edge) const {return _id < edge._id;}
203 friend class GridGraphBase;
208 Arc(int id) : _id(id) {}
212 Arc (Invalid) : _id(-1) {}
213 operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
214 bool operator==(const Arc arc) const {return _id == arc._id;}
215 bool operator!=(const Arc arc) const {return _id != arc._id;}
216 bool operator<(const Arc arc) const {return _id < arc._id;}
219 static bool direction(Arc arc) {
220 return (arc._id & 1) == 1;
223 static Arc direct(Edge edge, bool dir) {
224 return Arc((edge._id << 1) | (dir ? 1 : 0));
227 void first(Node& node) const {
228 node._id = _node_num - 1;
231 static void next(Node& node) {
235 void first(Edge& edge) const {
236 edge._id = _edge_num - 1;
239 static void next(Edge& edge) {
243 void first(Arc& arc) const {
244 arc._id = 2 * _edge_num - 1;
247 static void next(Arc& arc) {
251 void firstOut(Arc& arc, const Node& node) const {
252 if (node._id % _width < _width - 1) {
253 arc._id = (_edge_limit + node._id % _width +
254 (node._id / _width) * (_width - 1)) << 1 | 1;
257 if (node._id < _node_num - _width) {
258 arc._id = node._id << 1 | 1;
261 if (node._id % _width > 0) {
262 arc._id = (_edge_limit + node._id % _width +
263 (node._id / _width) * (_width - 1) - 1) << 1;
266 if (node._id >= _width) {
267 arc._id = (node._id - _width) << 1;
273 void nextOut(Arc& arc) const {
274 int nid = arc._id >> 1;
275 if ((arc._id & 1) == 1) {
276 if (nid >= _edge_limit) {
277 nid = (nid - _edge_limit) % (_width - 1) +
278 (nid - _edge_limit) / (_width - 1) * _width;
279 if (nid < _node_num - _width) {
280 arc._id = nid << 1 | 1;
284 if (nid % _width > 0) {
285 arc._id = (_edge_limit + nid % _width +
286 (nid / _width) * (_width - 1) - 1) << 1;
290 arc._id = (nid - _width) << 1;
294 if (nid >= _edge_limit) {
295 nid = (nid - _edge_limit) % (_width - 1) +
296 (nid - _edge_limit) / (_width - 1) * _width + 1;
298 arc._id = (nid - _width) << 1;
306 void firstIn(Arc& arc, const Node& node) const {
307 if (node._id % _width < _width - 1) {
308 arc._id = (_edge_limit + node._id % _width +
309 (node._id / _width) * (_width - 1)) << 1;
312 if (node._id < _node_num - _width) {
313 arc._id = node._id << 1;
316 if (node._id % _width > 0) {
317 arc._id = (_edge_limit + node._id % _width +
318 (node._id / _width) * (_width - 1) - 1) << 1 | 1;
321 if (node._id >= _width) {
322 arc._id = (node._id - _width) << 1 | 1;
328 void nextIn(Arc& arc) const {
329 int nid = arc._id >> 1;
330 if ((arc._id & 1) == 0) {
331 if (nid >= _edge_limit) {
332 nid = (nid - _edge_limit) % (_width - 1) +
333 (nid - _edge_limit) / (_width - 1) * _width;
334 if (nid < _node_num - _width) {
339 if (nid % _width > 0) {
340 arc._id = (_edge_limit + nid % _width +
341 (nid / _width) * (_width - 1) - 1) << 1 | 1;
345 arc._id = (nid - _width) << 1 | 1;
349 if (nid >= _edge_limit) {
350 nid = (nid - _edge_limit) % (_width - 1) +
351 (nid - _edge_limit) / (_width - 1) * _width + 1;
353 arc._id = (nid - _width) << 1 | 1;
361 void firstInc(Edge& edge, bool& dir, const Node& node) const {
362 if (node._id % _width < _width - 1) {
363 edge._id = _edge_limit + node._id % _width +
364 (node._id / _width) * (_width - 1);
368 if (node._id < _node_num - _width) {
373 if (node._id % _width > 0) {
374 edge._id = _edge_limit + node._id % _width +
375 (node._id / _width) * (_width - 1) - 1;
379 if (node._id >= _width) {
380 edge._id = node._id - _width;
388 void nextInc(Edge& edge, bool& dir) const {
391 if (nid >= _edge_limit) {
392 nid = (nid - _edge_limit) % (_width - 1) +
393 (nid - _edge_limit) / (_width - 1) * _width;
394 if (nid < _node_num - _width) {
399 if (nid % _width > 0) {
400 edge._id = _edge_limit + nid % _width +
401 (nid / _width) * (_width - 1) - 1;
406 edge._id = nid - _width;
411 if (nid >= _edge_limit) {
412 nid = (nid - _edge_limit) % (_width - 1) +
413 (nid - _edge_limit) / (_width - 1) * _width + 1;
415 edge._id = nid - _width;
424 Arc right(Node n) const {
425 if (n._id % _width < _width - 1) {
426 return Arc(((_edge_limit + n._id % _width +
427 (n._id / _width) * (_width - 1)) << 1) | 1);
433 Arc left(Node n) const {
434 if (n._id % _width > 0) {
435 return Arc((_edge_limit + n._id % _width +
436 (n._id / _width) * (_width - 1) - 1) << 1);
442 Arc up(Node n) const {
443 if (n._id < _edge_limit) {
444 return Arc((n._id << 1) | 1);
450 Arc down(Node n) const {
451 if (n._id >= _width) {
452 return Arc((n._id - _width) << 1);
460 int _node_num, _edge_num;
465 typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
469 /// \brief Grid graph class
471 /// This class implements a special graph type. The nodes of the
472 /// graph can be indexed by two integer \c (i,j) value where \c i is
473 /// in the \c [0..width()-1] range and j is in the \c
474 /// [0..height()-1] range. Two nodes are connected in the graph if
475 /// the indexes differ exactly on one position and exactly one is
476 /// the difference. The nodes of the graph can be indexed by position
477 /// with the \c operator()() function. The positions of the nodes can be
478 /// get with \c pos(), \c col() and \c row() members. The outgoing
479 /// arcs can be retrieved with the \c right(), \c up(), \c left()
480 /// and \c down() functions, where the bottom-left corner is the
483 /// \image html grid_graph.png
484 /// \image latex grid_graph.eps "Grid graph" row_num=\textrow_num
486 /// A short example about the basic usage:
488 /// GridGraph graph(rows, cols);
489 /// GridGraph::NodeMap<int> val(graph);
490 /// for (int i = 0; i < graph.width(); ++i) {
491 /// for (int j = 0; j < graph.height(); ++j) {
492 /// val[graph(i, j)] = i + j;
497 /// This graph type is fully conform to the \ref concepts::Graph
498 /// "Graph" concept, and it also has an important extra feature
499 /// that its maps are real \ref concepts::ReferenceMap
500 /// "reference map"s.
501 class GridGraph : public ExtendedGridGraphBase {
504 typedef ExtendedGridGraphBase Parent;
506 /// \brief Map to get the indices of the nodes as dim2::Point<int>.
508 /// Map to get the indices of the nodes as dim2::Point<int>.
511 /// \brief The key type of the map
512 typedef GridGraph::Node Key;
513 /// \brief The value type of the map
514 typedef dim2::Point<int> Value;
516 /// \brief Constructor
519 IndexMap(const GridGraph& graph) : _graph(graph) {}
521 /// \brief The subscript operator
523 /// The subscript operator.
524 Value operator[](Key key) const {
525 return _graph.pos(key);
529 const GridGraph& _graph;
532 /// \brief Map to get the column of the nodes.
534 /// Map to get the column of the nodes.
537 /// \brief The key type of the map
538 typedef GridGraph::Node Key;
539 /// \brief The value type of the map
542 /// \brief Constructor
545 ColMap(const GridGraph& graph) : _graph(graph) {}
547 /// \brief The subscript operator
549 /// The subscript operator.
550 Value operator[](Key key) const {
551 return _graph.col(key);
555 const GridGraph& _graph;
558 /// \brief Map to get the row of the nodes.
560 /// Map to get the row of the nodes.
563 /// \brief The key type of the map
564 typedef GridGraph::Node Key;
565 /// \brief The value type of the map
568 /// \brief Constructor
571 RowMap(const GridGraph& graph) : _graph(graph) {}
573 /// \brief The subscript operator
575 /// The subscript operator.
576 Value operator[](Key key) const {
577 return _graph.row(key);
581 const GridGraph& _graph;
584 /// \brief Constructor
586 /// Construct a grid graph with given size.
587 GridGraph(int width, int height) { construct(width, height); }
589 /// \brief Resize the graph
591 /// Resize the graph. The function will fully destroy and rebuild
592 /// the graph. This cause that the maps of the graph will
593 /// reallocated automatically and the previous values will be
595 void resize(int width, int height) {
596 Parent::notifier(Arc()).clear();
597 Parent::notifier(Edge()).clear();
598 Parent::notifier(Node()).clear();
599 construct(width, height);
600 Parent::notifier(Node()).build();
601 Parent::notifier(Edge()).build();
602 Parent::notifier(Arc()).build();
605 /// \brief The node on the given position.
607 /// Gives back the node on the given position.
608 Node operator()(int i, int j) const {
609 return Parent::operator()(i, j);
612 /// \brief Gives back the column index of the node.
614 /// Gives back the column index of the node.
615 int col(Node n) const {
616 return Parent::col(n);
619 /// \brief Gives back the row index of the node.
621 /// Gives back the row index of the node.
622 int row(Node n) const {
623 return Parent::row(n);
626 /// \brief Gives back the position of the node.
628 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
629 dim2::Point<int> pos(Node n) const {
630 return Parent::pos(n);
633 /// \brief Gives back the number of the columns.
635 /// Gives back the number of the columns.
637 return Parent::width();
640 /// \brief Gives back the number of the rows.
642 /// Gives back the number of the rows.
644 return Parent::height();
647 /// \brief Gives back the arc goes right from the node.
649 /// Gives back the arc goes right from the node. If there is not
650 /// outgoing arc then it gives back INVALID.
651 Arc right(Node n) const {
652 return Parent::right(n);
655 /// \brief Gives back the arc goes left from the node.
657 /// Gives back the arc goes left from the node. If there is not
658 /// outgoing arc then it gives back INVALID.
659 Arc left(Node n) const {
660 return Parent::left(n);
663 /// \brief Gives back the arc goes up from the node.
665 /// Gives back the arc goes up from the node. If there is not
666 /// outgoing arc then it gives back INVALID.
667 Arc up(Node n) const {
668 return Parent::up(n);
671 /// \brief Gives back the arc goes down from the node.
673 /// Gives back the arc goes down from the node. If there is not
674 /// outgoing arc then it gives back INVALID.
675 Arc down(Node n) const {
676 return Parent::down(n);
679 /// \brief Index map of the grid graph
681 /// Just returns an IndexMap for the grid graph.
682 IndexMap indexMap() const {
683 return IndexMap(*this);
686 /// \brief Row map of the grid graph
688 /// Just returns a RowMap for the grid graph.
689 RowMap rowMap() const {
690 return RowMap(*this);
693 /// \brief Column map of the grid graph
695 /// Just returns a ColMap for the grid graph.
696 ColMap colMap() const {
697 return ColMap(*this);