kpeter@334
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
kpeter@334
|
2 |
*
|
kpeter@334
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
kpeter@334
|
4 |
*
|
kpeter@334
|
5 |
* Copyright (C) 2003-2008
|
kpeter@334
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
kpeter@334
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
kpeter@334
|
8 |
*
|
kpeter@334
|
9 |
* Permission to use, modify and distribute this software is granted
|
kpeter@334
|
10 |
* provided that this copyright notice appears in all copies. For
|
kpeter@334
|
11 |
* precise terms see the accompanying LICENSE file.
|
kpeter@334
|
12 |
*
|
kpeter@334
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
kpeter@334
|
14 |
* express or implied, and with no claim as to its suitability for any
|
kpeter@334
|
15 |
* purpose.
|
kpeter@334
|
16 |
*
|
kpeter@334
|
17 |
*/
|
kpeter@334
|
18 |
|
kpeter@334
|
19 |
#ifndef GRID_GRAPH_H
|
kpeter@334
|
20 |
#define GRID_GRAPH_H
|
kpeter@334
|
21 |
|
kpeter@334
|
22 |
#include <lemon/core.h>
|
deba@335
|
23 |
#include <lemon/bits/graph_extender.h>
|
deba@335
|
24 |
#include <lemon/dim2.h>
|
kpeter@334
|
25 |
#include <lemon/assert.h>
|
kpeter@334
|
26 |
|
kpeter@334
|
27 |
///\ingroup graphs
|
kpeter@334
|
28 |
///\file
|
kpeter@334
|
29 |
///\brief GridGraph class.
|
kpeter@334
|
30 |
|
kpeter@334
|
31 |
namespace lemon {
|
kpeter@334
|
32 |
|
kpeter@334
|
33 |
class GridGraphBase {
|
kpeter@334
|
34 |
|
kpeter@334
|
35 |
public:
|
kpeter@334
|
36 |
|
kpeter@334
|
37 |
typedef GridGraphBase Graph;
|
kpeter@334
|
38 |
|
kpeter@334
|
39 |
class Node;
|
deba@335
|
40 |
class Edge;
|
kpeter@334
|
41 |
class Arc;
|
kpeter@334
|
42 |
|
kpeter@334
|
43 |
public:
|
kpeter@334
|
44 |
|
kpeter@334
|
45 |
GridGraphBase() {}
|
kpeter@334
|
46 |
|
kpeter@334
|
47 |
protected:
|
kpeter@334
|
48 |
|
deba@335
|
49 |
void construct(int width, int height) {
|
deba@335
|
50 |
_width = width; _height = height;
|
deba@335
|
51 |
_node_num = width * height;
|
deba@335
|
52 |
_edge_num = 2 * _node_num - width - height;
|
deba@335
|
53 |
_edge_limit = _node_num - _width;
|
kpeter@334
|
54 |
}
|
kpeter@334
|
55 |
|
kpeter@334
|
56 |
public:
|
kpeter@334
|
57 |
|
kpeter@334
|
58 |
Node operator()(int i, int j) const {
|
deba@335
|
59 |
LEMON_DEBUG(0 <= i && i < _width &&
|
deba@335
|
60 |
0 <= j && j < _height, "Index out of range");
|
kpeter@334
|
61 |
return Node(i + j * _width);
|
kpeter@334
|
62 |
}
|
kpeter@334
|
63 |
|
deba@335
|
64 |
int col(Node n) const {
|
deba@335
|
65 |
return n._id % _width;
|
kpeter@334
|
66 |
}
|
kpeter@334
|
67 |
|
deba@335
|
68 |
int row(Node n) const {
|
deba@335
|
69 |
return n._id / _width;
|
deba@335
|
70 |
}
|
deba@335
|
71 |
|
deba@335
|
72 |
dim2::Point<int> pos(Node n) const {
|
deba@335
|
73 |
return dim2::Point<int>(col(n), row(n));
|
kpeter@334
|
74 |
}
|
kpeter@334
|
75 |
|
kpeter@334
|
76 |
int width() const {
|
kpeter@334
|
77 |
return _width;
|
kpeter@334
|
78 |
}
|
kpeter@334
|
79 |
|
kpeter@334
|
80 |
int height() const {
|
kpeter@334
|
81 |
return _height;
|
kpeter@334
|
82 |
}
|
kpeter@334
|
83 |
|
kpeter@334
|
84 |
typedef True NodeNumTag;
|
kpeter@334
|
85 |
typedef True ArcNumTag;
|
kpeter@334
|
86 |
|
deba@335
|
87 |
int nodeNum() const { return _node_num; }
|
deba@335
|
88 |
int edgeNum() const { return _edge_num; }
|
deba@335
|
89 |
int arcNum() const { return 2 * _edge_num; }
|
kpeter@334
|
90 |
|
deba@335
|
91 |
Node u(Edge edge) const {
|
deba@335
|
92 |
if (edge._id < _edge_limit) {
|
deba@335
|
93 |
return edge._id;
|
kpeter@334
|
94 |
} else {
|
deba@335
|
95 |
return (edge._id - _edge_limit) % (_width - 1) +
|
deba@335
|
96 |
(edge._id - _edge_limit) / (_width - 1) * _width;
|
kpeter@334
|
97 |
}
|
kpeter@334
|
98 |
}
|
kpeter@334
|
99 |
|
deba@335
|
100 |
Node v(Edge edge) const {
|
deba@335
|
101 |
if (edge._id < _edge_limit) {
|
deba@335
|
102 |
return edge._id + _width;
|
kpeter@334
|
103 |
} else {
|
deba@335
|
104 |
return (edge._id - _edge_limit) % (_width - 1) +
|
deba@335
|
105 |
(edge._id - _edge_limit) / (_width - 1) * _width + 1;
|
kpeter@334
|
106 |
}
|
kpeter@334
|
107 |
}
|
kpeter@334
|
108 |
|
deba@335
|
109 |
Node source(Arc arc) const {
|
deba@335
|
110 |
return (arc._id & 1) == 1 ? u(arc) : v(arc);
|
deba@335
|
111 |
}
|
deba@335
|
112 |
|
deba@335
|
113 |
Node target(Arc arc) const {
|
deba@335
|
114 |
return (arc._id & 1) == 1 ? v(arc) : u(arc);
|
deba@335
|
115 |
}
|
deba@335
|
116 |
|
deba@335
|
117 |
static int id(Node node) { return node._id; }
|
deba@335
|
118 |
static int id(Edge edge) { return edge._id; }
|
deba@335
|
119 |
static int id(Arc arc) { return arc._id; }
|
deba@335
|
120 |
|
deba@335
|
121 |
int maxNodeId() const { return _node_num - 1; }
|
deba@335
|
122 |
int maxEdgeId() const { return _edge_num - 1; }
|
deba@335
|
123 |
int maxArcId() const { return 2 * _edge_num - 1; }
|
kpeter@334
|
124 |
|
kpeter@334
|
125 |
static Node nodeFromId(int id) { return Node(id);}
|
deba@335
|
126 |
static Edge edgeFromId(int id) { return Edge(id);}
|
kpeter@334
|
127 |
static Arc arcFromId(int id) { return Arc(id);}
|
kpeter@334
|
128 |
|
deba@335
|
129 |
typedef True FindEdgeTag;
|
deba@335
|
130 |
|
deba@335
|
131 |
Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
|
deba@335
|
132 |
if (prev != INVALID) return INVALID;
|
deba@335
|
133 |
if (v._id > u._id) {
|
deba@335
|
134 |
if (v._id - u._id == _width)
|
deba@335
|
135 |
return Edge(u._id);
|
deba@335
|
136 |
if (v._id - u._id == 1 && u._id % _width < _width - 1) {
|
deba@335
|
137 |
return Edge(u._id / _width * (_width - 1) +
|
deba@335
|
138 |
u._id % _width + _edge_limit);
|
deba@335
|
139 |
}
|
deba@335
|
140 |
} else {
|
deba@335
|
141 |
if (u._id - v._id == _width)
|
deba@335
|
142 |
return Edge(v._id);
|
deba@335
|
143 |
if (u._id - v._id == 1 && v._id % _width < _width - 1) {
|
deba@335
|
144 |
return Edge(v._id / _width * (_width - 1) +
|
deba@335
|
145 |
v._id % _width + _edge_limit);
|
deba@335
|
146 |
}
|
deba@335
|
147 |
}
|
deba@335
|
148 |
return INVALID;
|
deba@335
|
149 |
}
|
kpeter@334
|
150 |
|
kpeter@334
|
151 |
Arc findArc(Node u, Node v, Arc prev = INVALID) const {
|
kpeter@334
|
152 |
if (prev != INVALID) return INVALID;
|
deba@335
|
153 |
if (v._id > u._id) {
|
deba@335
|
154 |
if (v._id - u._id == _width)
|
deba@335
|
155 |
return Arc((u._id << 1) | 1);
|
deba@335
|
156 |
if (v._id - u._id == 1 && u._id % _width < _width - 1) {
|
deba@335
|
157 |
return Arc(((u._id / _width * (_width - 1) +
|
deba@335
|
158 |
u._id % _width + _edge_limit) << 1) | 1);
|
deba@335
|
159 |
}
|
deba@335
|
160 |
} else {
|
deba@335
|
161 |
if (u._id - v._id == _width)
|
deba@335
|
162 |
return Arc(v._id << 1);
|
deba@335
|
163 |
if (u._id - v._id == 1 && v._id % _width < _width - 1) {
|
deba@335
|
164 |
return Arc((v._id / _width * (_width - 1) +
|
deba@335
|
165 |
v._id % _width + _edge_limit) << 1);
|
deba@335
|
166 |
}
|
kpeter@334
|
167 |
}
|
kpeter@334
|
168 |
return INVALID;
|
kpeter@334
|
169 |
}
|
kpeter@334
|
170 |
|
kpeter@334
|
171 |
class Node {
|
kpeter@334
|
172 |
friend class GridGraphBase;
|
kpeter@334
|
173 |
|
kpeter@334
|
174 |
protected:
|
deba@335
|
175 |
int _id;
|
deba@335
|
176 |
Node(int id) : _id(id) {}
|
kpeter@334
|
177 |
public:
|
kpeter@334
|
178 |
Node() {}
|
deba@335
|
179 |
Node (Invalid) : _id(-1) {}
|
deba@335
|
180 |
bool operator==(const Node node) const {return _id == node._id;}
|
deba@335
|
181 |
bool operator!=(const Node node) const {return _id != node._id;}
|
deba@335
|
182 |
bool operator<(const Node node) const {return _id < node._id;}
|
deba@335
|
183 |
};
|
deba@335
|
184 |
|
deba@335
|
185 |
class Edge {
|
deba@335
|
186 |
friend class GridGraphBase;
|
kpeter@336
|
187 |
friend class Arc;
|
deba@335
|
188 |
|
deba@335
|
189 |
protected:
|
deba@335
|
190 |
int _id;
|
deba@335
|
191 |
|
deba@335
|
192 |
Edge(int id) : _id(id) {}
|
deba@335
|
193 |
|
deba@335
|
194 |
public:
|
deba@335
|
195 |
Edge() {}
|
deba@335
|
196 |
Edge (Invalid) : _id(-1) {}
|
deba@335
|
197 |
bool operator==(const Edge edge) const {return _id == edge._id;}
|
deba@335
|
198 |
bool operator!=(const Edge edge) const {return _id != edge._id;}
|
deba@335
|
199 |
bool operator<(const Edge edge) const {return _id < edge._id;}
|
kpeter@334
|
200 |
};
|
kpeter@334
|
201 |
|
kpeter@334
|
202 |
class Arc {
|
kpeter@334
|
203 |
friend class GridGraphBase;
|
kpeter@334
|
204 |
|
kpeter@334
|
205 |
protected:
|
deba@335
|
206 |
int _id;
|
deba@335
|
207 |
|
deba@335
|
208 |
Arc(int id) : _id(id) {}
|
deba@335
|
209 |
|
kpeter@334
|
210 |
public:
|
kpeter@334
|
211 |
Arc() {}
|
deba@335
|
212 |
Arc (Invalid) : _id(-1) {}
|
deba@335
|
213 |
operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
|
deba@335
|
214 |
bool operator==(const Arc arc) const {return _id == arc._id;}
|
deba@335
|
215 |
bool operator!=(const Arc arc) const {return _id != arc._id;}
|
deba@335
|
216 |
bool operator<(const Arc arc) const {return _id < arc._id;}
|
kpeter@334
|
217 |
};
|
kpeter@334
|
218 |
|
deba@335
|
219 |
static bool direction(Arc arc) {
|
deba@335
|
220 |
return (arc._id & 1) == 1;
|
deba@335
|
221 |
}
|
deba@335
|
222 |
|
deba@335
|
223 |
static Arc direct(Edge edge, bool dir) {
|
deba@335
|
224 |
return Arc((edge._id << 1) | (dir ? 1 : 0));
|
deba@335
|
225 |
}
|
deba@335
|
226 |
|
kpeter@334
|
227 |
void first(Node& node) const {
|
deba@335
|
228 |
node._id = _node_num - 1;
|
kpeter@334
|
229 |
}
|
kpeter@334
|
230 |
|
kpeter@334
|
231 |
static void next(Node& node) {
|
deba@335
|
232 |
--node._id;
|
deba@335
|
233 |
}
|
deba@335
|
234 |
|
deba@335
|
235 |
void first(Edge& edge) const {
|
deba@335
|
236 |
edge._id = _edge_num - 1;
|
deba@335
|
237 |
}
|
deba@335
|
238 |
|
deba@335
|
239 |
static void next(Edge& edge) {
|
deba@335
|
240 |
--edge._id;
|
kpeter@334
|
241 |
}
|
kpeter@334
|
242 |
|
kpeter@334
|
243 |
void first(Arc& arc) const {
|
deba@335
|
244 |
arc._id = 2 * _edge_num - 1;
|
kpeter@334
|
245 |
}
|
kpeter@334
|
246 |
|
kpeter@334
|
247 |
static void next(Arc& arc) {
|
deba@335
|
248 |
--arc._id;
|
kpeter@334
|
249 |
}
|
kpeter@334
|
250 |
|
kpeter@334
|
251 |
void firstOut(Arc& arc, const Node& node) const {
|
deba@335
|
252 |
if (node._id % _width < _width - 1) {
|
deba@335
|
253 |
arc._id = (_edge_limit + node._id % _width +
|
deba@335
|
254 |
(node._id / _width) * (_width - 1)) << 1 | 1;
|
deba@335
|
255 |
return;
|
deba@335
|
256 |
}
|
deba@335
|
257 |
if (node._id < _node_num - _width) {
|
deba@335
|
258 |
arc._id = node._id << 1 | 1;
|
deba@335
|
259 |
return;
|
deba@335
|
260 |
}
|
deba@335
|
261 |
if (node._id % _width > 0) {
|
deba@335
|
262 |
arc._id = (_edge_limit + node._id % _width +
|
deba@335
|
263 |
(node._id / _width) * (_width - 1) - 1) << 1;
|
deba@335
|
264 |
return;
|
deba@335
|
265 |
}
|
deba@335
|
266 |
if (node._id >= _width) {
|
deba@335
|
267 |
arc._id = (node._id - _width) << 1;
|
deba@335
|
268 |
return;
|
deba@335
|
269 |
}
|
deba@335
|
270 |
arc._id = -1;
|
deba@335
|
271 |
}
|
deba@335
|
272 |
|
deba@335
|
273 |
void nextOut(Arc& arc) const {
|
deba@335
|
274 |
int nid = arc._id >> 1;
|
deba@335
|
275 |
if ((arc._id & 1) == 1) {
|
deba@335
|
276 |
if (nid >= _edge_limit) {
|
deba@335
|
277 |
nid = (nid - _edge_limit) % (_width - 1) +
|
deba@335
|
278 |
(nid - _edge_limit) / (_width - 1) * _width;
|
deba@335
|
279 |
if (nid < _node_num - _width) {
|
deba@335
|
280 |
arc._id = nid << 1 | 1;
|
deba@335
|
281 |
return;
|
deba@335
|
282 |
}
|
deba@335
|
283 |
}
|
deba@335
|
284 |
if (nid % _width > 0) {
|
deba@335
|
285 |
arc._id = (_edge_limit + nid % _width +
|
deba@335
|
286 |
(nid / _width) * (_width - 1) - 1) << 1;
|
deba@335
|
287 |
return;
|
deba@335
|
288 |
}
|
deba@335
|
289 |
if (nid >= _width) {
|
deba@335
|
290 |
arc._id = (nid - _width) << 1;
|
deba@335
|
291 |
return;
|
deba@335
|
292 |
}
|
kpeter@334
|
293 |
} else {
|
deba@335
|
294 |
if (nid >= _edge_limit) {
|
deba@335
|
295 |
nid = (nid - _edge_limit) % (_width - 1) +
|
deba@335
|
296 |
(nid - _edge_limit) / (_width - 1) * _width + 1;
|
deba@335
|
297 |
if (nid >= _width) {
|
deba@335
|
298 |
arc._id = (nid - _width) << 1;
|
deba@335
|
299 |
return;
|
deba@335
|
300 |
}
|
deba@335
|
301 |
}
|
deba@335
|
302 |
}
|
deba@335
|
303 |
arc._id = -1;
|
deba@335
|
304 |
}
|
deba@335
|
305 |
|
deba@335
|
306 |
void firstIn(Arc& arc, const Node& node) const {
|
deba@335
|
307 |
if (node._id % _width < _width - 1) {
|
deba@335
|
308 |
arc._id = (_edge_limit + node._id % _width +
|
deba@335
|
309 |
(node._id / _width) * (_width - 1)) << 1;
|
deba@335
|
310 |
return;
|
deba@335
|
311 |
}
|
deba@335
|
312 |
if (node._id < _node_num - _width) {
|
deba@335
|
313 |
arc._id = node._id << 1;
|
deba@335
|
314 |
return;
|
deba@335
|
315 |
}
|
deba@335
|
316 |
if (node._id % _width > 0) {
|
deba@335
|
317 |
arc._id = (_edge_limit + node._id % _width +
|
deba@335
|
318 |
(node._id / _width) * (_width - 1) - 1) << 1 | 1;
|
deba@335
|
319 |
return;
|
deba@335
|
320 |
}
|
deba@335
|
321 |
if (node._id >= _width) {
|
deba@335
|
322 |
arc._id = (node._id - _width) << 1 | 1;
|
deba@335
|
323 |
return;
|
deba@335
|
324 |
}
|
deba@335
|
325 |
arc._id = -1;
|
deba@335
|
326 |
}
|
deba@335
|
327 |
|
deba@335
|
328 |
void nextIn(Arc& arc) const {
|
deba@335
|
329 |
int nid = arc._id >> 1;
|
deba@335
|
330 |
if ((arc._id & 1) == 0) {
|
deba@335
|
331 |
if (nid >= _edge_limit) {
|
deba@335
|
332 |
nid = (nid - _edge_limit) % (_width - 1) +
|
deba@335
|
333 |
(nid - _edge_limit) / (_width - 1) * _width;
|
deba@335
|
334 |
if (nid < _node_num - _width) {
|
deba@335
|
335 |
arc._id = nid << 1;
|
deba@335
|
336 |
return;
|
deba@335
|
337 |
}
|
deba@335
|
338 |
}
|
deba@335
|
339 |
if (nid % _width > 0) {
|
deba@335
|
340 |
arc._id = (_edge_limit + nid % _width +
|
deba@335
|
341 |
(nid / _width) * (_width - 1) - 1) << 1 | 1;
|
deba@335
|
342 |
return;
|
deba@335
|
343 |
}
|
deba@335
|
344 |
if (nid >= _width) {
|
deba@335
|
345 |
arc._id = (nid - _width) << 1 | 1;
|
deba@335
|
346 |
return;
|
deba@335
|
347 |
}
|
deba@335
|
348 |
} else {
|
deba@335
|
349 |
if (nid >= _edge_limit) {
|
deba@335
|
350 |
nid = (nid - _edge_limit) % (_width - 1) +
|
deba@335
|
351 |
(nid - _edge_limit) / (_width - 1) * _width + 1;
|
deba@335
|
352 |
if (nid >= _width) {
|
deba@335
|
353 |
arc._id = (nid - _width) << 1 | 1;
|
deba@335
|
354 |
return;
|
deba@335
|
355 |
}
|
deba@335
|
356 |
}
|
deba@335
|
357 |
}
|
deba@335
|
358 |
arc._id = -1;
|
deba@335
|
359 |
}
|
deba@335
|
360 |
|
deba@335
|
361 |
void firstInc(Edge& edge, bool& dir, const Node& node) const {
|
deba@335
|
362 |
if (node._id % _width < _width - 1) {
|
deba@335
|
363 |
edge._id = _edge_limit + node._id % _width +
|
deba@335
|
364 |
(node._id / _width) * (_width - 1);
|
deba@335
|
365 |
dir = true;
|
deba@335
|
366 |
return;
|
deba@335
|
367 |
}
|
deba@335
|
368 |
if (node._id < _node_num - _width) {
|
deba@335
|
369 |
edge._id = node._id;
|
deba@335
|
370 |
dir = true;
|
deba@335
|
371 |
return;
|
deba@335
|
372 |
}
|
deba@335
|
373 |
if (node._id % _width > 0) {
|
deba@335
|
374 |
edge._id = _edge_limit + node._id % _width +
|
deba@335
|
375 |
(node._id / _width) * (_width - 1) - 1;
|
deba@335
|
376 |
dir = false;
|
deba@335
|
377 |
return;
|
deba@335
|
378 |
}
|
deba@335
|
379 |
if (node._id >= _width) {
|
deba@335
|
380 |
edge._id = node._id - _width;
|
deba@335
|
381 |
dir = false;
|
deba@335
|
382 |
return;
|
deba@335
|
383 |
}
|
deba@335
|
384 |
edge._id = -1;
|
deba@335
|
385 |
dir = true;
|
deba@335
|
386 |
}
|
deba@335
|
387 |
|
deba@335
|
388 |
void nextInc(Edge& edge, bool& dir) const {
|
deba@335
|
389 |
int nid = edge._id;
|
deba@335
|
390 |
if (dir) {
|
deba@335
|
391 |
if (nid >= _edge_limit) {
|
deba@335
|
392 |
nid = (nid - _edge_limit) % (_width - 1) +
|
deba@335
|
393 |
(nid - _edge_limit) / (_width - 1) * _width;
|
deba@335
|
394 |
if (nid < _node_num - _width) {
|
deba@335
|
395 |
edge._id = nid;
|
deba@335
|
396 |
return;
|
deba@335
|
397 |
}
|
deba@335
|
398 |
}
|
deba@335
|
399 |
if (nid % _width > 0) {
|
deba@335
|
400 |
edge._id = _edge_limit + nid % _width +
|
deba@335
|
401 |
(nid / _width) * (_width - 1) - 1;
|
deba@335
|
402 |
dir = false;
|
deba@335
|
403 |
return;
|
deba@335
|
404 |
}
|
deba@335
|
405 |
if (nid >= _width) {
|
deba@335
|
406 |
edge._id = nid - _width;
|
deba@335
|
407 |
dir = false;
|
deba@335
|
408 |
return;
|
deba@335
|
409 |
}
|
deba@335
|
410 |
} else {
|
deba@335
|
411 |
if (nid >= _edge_limit) {
|
deba@335
|
412 |
nid = (nid - _edge_limit) % (_width - 1) +
|
deba@335
|
413 |
(nid - _edge_limit) / (_width - 1) * _width + 1;
|
deba@335
|
414 |
if (nid >= _width) {
|
deba@335
|
415 |
edge._id = nid - _width;
|
deba@335
|
416 |
return;
|
deba@335
|
417 |
}
|
deba@335
|
418 |
}
|
deba@335
|
419 |
}
|
deba@335
|
420 |
edge._id = -1;
|
deba@335
|
421 |
dir = true;
|
deba@335
|
422 |
}
|
deba@335
|
423 |
|
deba@335
|
424 |
Arc right(Node n) const {
|
deba@335
|
425 |
if (n._id % _width < _width - 1) {
|
deba@335
|
426 |
return Arc(((_edge_limit + n._id % _width +
|
deba@335
|
427 |
(n._id / _width) * (_width - 1)) << 1) | 1);
|
deba@335
|
428 |
} else {
|
deba@335
|
429 |
return INVALID;
|
kpeter@334
|
430 |
}
|
kpeter@334
|
431 |
}
|
kpeter@334
|
432 |
|
deba@335
|
433 |
Arc left(Node n) const {
|
deba@335
|
434 |
if (n._id % _width > 0) {
|
deba@335
|
435 |
return Arc((_edge_limit + n._id % _width +
|
deba@335
|
436 |
(n._id / _width) * (_width - 1) - 1) << 1);
|
kpeter@334
|
437 |
} else {
|
deba@335
|
438 |
return INVALID;
|
kpeter@334
|
439 |
}
|
kpeter@334
|
440 |
}
|
kpeter@334
|
441 |
|
deba@335
|
442 |
Arc up(Node n) const {
|
deba@335
|
443 |
if (n._id < _edge_limit) {
|
deba@335
|
444 |
return Arc((n._id << 1) | 1);
|
kpeter@334
|
445 |
} else {
|
deba@335
|
446 |
return INVALID;
|
kpeter@334
|
447 |
}
|
kpeter@334
|
448 |
}
|
kpeter@334
|
449 |
|
deba@335
|
450 |
Arc down(Node n) const {
|
deba@335
|
451 |
if (n._id >= _width) {
|
deba@335
|
452 |
return Arc((n._id - _width) << 1);
|
kpeter@334
|
453 |
} else {
|
deba@335
|
454 |
return INVALID;
|
kpeter@334
|
455 |
}
|
kpeter@334
|
456 |
}
|
kpeter@334
|
457 |
|
kpeter@334
|
458 |
private:
|
kpeter@334
|
459 |
int _width, _height;
|
deba@335
|
460 |
int _node_num, _edge_num;
|
deba@335
|
461 |
int _edge_limit;
|
kpeter@334
|
462 |
};
|
kpeter@334
|
463 |
|
deba@335
|
464 |
|
deba@335
|
465 |
typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
|
kpeter@334
|
466 |
|
kpeter@334
|
467 |
/// \ingroup graphs
|
kpeter@334
|
468 |
///
|
kpeter@334
|
469 |
/// \brief Grid graph class
|
kpeter@334
|
470 |
///
|
kpeter@334
|
471 |
/// This class implements a special graph type. The nodes of the
|
deba@335
|
472 |
/// graph can be indexed by two integer \c (i,j) value where \c i is
|
deba@335
|
473 |
/// in the \c [0..width()-1] range and j is in the \c
|
deba@335
|
474 |
/// [0..height()-1] range. Two nodes are connected in the graph if
|
deba@335
|
475 |
/// the indexes differ exactly on one position and exactly one is
|
kpeter@336
|
476 |
/// the difference. The nodes of the graph can be indexed by position
|
kpeter@336
|
477 |
/// with the \c operator()() function. The positions of the nodes can be
|
deba@335
|
478 |
/// get with \c pos(), \c col() and \c row() members. The outgoing
|
deba@335
|
479 |
/// arcs can be retrieved with the \c right(), \c up(), \c left()
|
deba@335
|
480 |
/// and \c down() functions, where the bottom-left corner is the
|
deba@335
|
481 |
/// origin.
|
kpeter@334
|
482 |
///
|
kpeter@334
|
483 |
/// \image html grid_graph.png
|
kpeter@336
|
484 |
/// \image latex grid_graph.eps "Grid graph" row_num=\textrow_num
|
kpeter@334
|
485 |
///
|
deba@335
|
486 |
/// A short example about the basic usage:
|
kpeter@334
|
487 |
///\code
|
deba@335
|
488 |
/// GridGraph graph(rows, cols);
|
deba@335
|
489 |
/// GridGraph::NodeMap<int> val(graph);
|
deba@335
|
490 |
/// for (int i = 0; i < graph.width(); ++i) {
|
deba@335
|
491 |
/// for (int j = 0; j < graph.height(); ++j) {
|
deba@335
|
492 |
/// val[graph(i, j)] = i + j;
|
kpeter@334
|
493 |
/// }
|
kpeter@334
|
494 |
/// }
|
kpeter@334
|
495 |
///\endcode
|
kpeter@334
|
496 |
///
|
kpeter@336
|
497 |
/// This graph type is fully conform to the \ref concepts::Graph
|
deba@335
|
498 |
/// "Graph" concept, and it also has an important extra feature
|
kpeter@336
|
499 |
/// that its maps are real \ref concepts::ReferenceMap
|
kpeter@336
|
500 |
/// "reference map"s.
|
kpeter@334
|
501 |
class GridGraph : public ExtendedGridGraphBase {
|
kpeter@334
|
502 |
public:
|
kpeter@334
|
503 |
|
kpeter@334
|
504 |
typedef ExtendedGridGraphBase Parent;
|
kpeter@334
|
505 |
|
kpeter@334
|
506 |
/// \brief Map to get the indices of the nodes as dim2::Point<int>.
|
kpeter@334
|
507 |
///
|
kpeter@334
|
508 |
/// Map to get the indices of the nodes as dim2::Point<int>.
|
kpeter@334
|
509 |
class IndexMap {
|
kpeter@334
|
510 |
public:
|
deba@335
|
511 |
/// \brief The key type of the map
|
kpeter@334
|
512 |
typedef GridGraph::Node Key;
|
deba@335
|
513 |
/// \brief The value type of the map
|
kpeter@334
|
514 |
typedef dim2::Point<int> Value;
|
kpeter@334
|
515 |
|
deba@335
|
516 |
/// \brief Constructor
|
deba@335
|
517 |
///
|
kpeter@334
|
518 |
/// Constructor
|
kpeter@334
|
519 |
IndexMap(const GridGraph& graph) : _graph(graph) {}
|
kpeter@334
|
520 |
|
deba@335
|
521 |
/// \brief The subscript operator
|
deba@335
|
522 |
///
|
deba@335
|
523 |
/// The subscript operator.
|
deba@335
|
524 |
Value operator[](Key key) const {
|
deba@335
|
525 |
return _graph.pos(key);
|
deba@335
|
526 |
}
|
deba@335
|
527 |
|
deba@335
|
528 |
private:
|
deba@335
|
529 |
const GridGraph& _graph;
|
deba@335
|
530 |
};
|
deba@335
|
531 |
|
deba@335
|
532 |
/// \brief Map to get the column of the nodes.
|
deba@335
|
533 |
///
|
deba@335
|
534 |
/// Map to get the column of the nodes.
|
deba@335
|
535 |
class ColMap {
|
deba@335
|
536 |
public:
|
deba@335
|
537 |
/// \brief The key type of the map
|
deba@335
|
538 |
typedef GridGraph::Node Key;
|
deba@335
|
539 |
/// \brief The value type of the map
|
deba@335
|
540 |
typedef int Value;
|
deba@335
|
541 |
|
deba@335
|
542 |
/// \brief Constructor
|
deba@335
|
543 |
///
|
deba@335
|
544 |
/// Constructor
|
deba@335
|
545 |
ColMap(const GridGraph& graph) : _graph(graph) {}
|
deba@335
|
546 |
|
deba@335
|
547 |
/// \brief The subscript operator
|
deba@335
|
548 |
///
|
deba@335
|
549 |
/// The subscript operator.
|
deba@335
|
550 |
Value operator[](Key key) const {
|
deba@335
|
551 |
return _graph.col(key);
|
kpeter@334
|
552 |
}
|
kpeter@334
|
553 |
|
kpeter@334
|
554 |
private:
|
kpeter@334
|
555 |
const GridGraph& _graph;
|
kpeter@334
|
556 |
};
|
kpeter@334
|
557 |
|
kpeter@334
|
558 |
/// \brief Map to get the row of the nodes.
|
kpeter@334
|
559 |
///
|
kpeter@334
|
560 |
/// Map to get the row of the nodes.
|
kpeter@334
|
561 |
class RowMap {
|
kpeter@334
|
562 |
public:
|
deba@335
|
563 |
/// \brief The key type of the map
|
kpeter@334
|
564 |
typedef GridGraph::Node Key;
|
deba@335
|
565 |
/// \brief The value type of the map
|
kpeter@334
|
566 |
typedef int Value;
|
kpeter@334
|
567 |
|
deba@335
|
568 |
/// \brief Constructor
|
deba@335
|
569 |
///
|
kpeter@334
|
570 |
/// Constructor
|
kpeter@334
|
571 |
RowMap(const GridGraph& graph) : _graph(graph) {}
|
kpeter@334
|
572 |
|
deba@335
|
573 |
/// \brief The subscript operator
|
deba@335
|
574 |
///
|
deba@335
|
575 |
/// The subscript operator.
|
deba@335
|
576 |
Value operator[](Key key) const {
|
kpeter@334
|
577 |
return _graph.row(key);
|
kpeter@334
|
578 |
}
|
kpeter@334
|
579 |
|
kpeter@334
|
580 |
private:
|
kpeter@334
|
581 |
const GridGraph& _graph;
|
kpeter@334
|
582 |
};
|
kpeter@334
|
583 |
|
kpeter@334
|
584 |
/// \brief Constructor
|
kpeter@334
|
585 |
///
|
deba@335
|
586 |
/// Construct a grid graph with given size.
|
kpeter@334
|
587 |
GridGraph(int width, int height) { construct(width, height); }
|
kpeter@334
|
588 |
|
kpeter@334
|
589 |
/// \brief Resize the graph
|
kpeter@334
|
590 |
///
|
deba@335
|
591 |
/// Resize the graph. The function will fully destroy and rebuild
|
deba@335
|
592 |
/// the graph. This cause that the maps of the graph will
|
deba@335
|
593 |
/// reallocated automatically and the previous values will be
|
deba@335
|
594 |
/// lost.
|
kpeter@334
|
595 |
void resize(int width, int height) {
|
kpeter@334
|
596 |
Parent::notifier(Arc()).clear();
|
kpeter@334
|
597 |
Parent::notifier(Edge()).clear();
|
kpeter@334
|
598 |
Parent::notifier(Node()).clear();
|
kpeter@334
|
599 |
construct(width, height);
|
kpeter@334
|
600 |
Parent::notifier(Node()).build();
|
kpeter@334
|
601 |
Parent::notifier(Edge()).build();
|
kpeter@334
|
602 |
Parent::notifier(Arc()).build();
|
kpeter@334
|
603 |
}
|
kpeter@334
|
604 |
|
kpeter@334
|
605 |
/// \brief The node on the given position.
|
kpeter@334
|
606 |
///
|
kpeter@334
|
607 |
/// Gives back the node on the given position.
|
kpeter@334
|
608 |
Node operator()(int i, int j) const {
|
kpeter@334
|
609 |
return Parent::operator()(i, j);
|
kpeter@334
|
610 |
}
|
kpeter@334
|
611 |
|
deba@335
|
612 |
/// \brief Gives back the column index of the node.
|
deba@335
|
613 |
///
|
deba@335
|
614 |
/// Gives back the column index of the node.
|
deba@335
|
615 |
int col(Node n) const {
|
deba@335
|
616 |
return Parent::col(n);
|
deba@335
|
617 |
}
|
deba@335
|
618 |
|
kpeter@334
|
619 |
/// \brief Gives back the row index of the node.
|
kpeter@334
|
620 |
///
|
kpeter@334
|
621 |
/// Gives back the row index of the node.
|
kpeter@334
|
622 |
int row(Node n) const {
|
kpeter@334
|
623 |
return Parent::row(n);
|
kpeter@334
|
624 |
}
|
kpeter@334
|
625 |
|
deba@335
|
626 |
/// \brief Gives back the position of the node.
|
kpeter@334
|
627 |
///
|
deba@335
|
628 |
/// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
|
deba@335
|
629 |
dim2::Point<int> pos(Node n) const {
|
deba@335
|
630 |
return Parent::pos(n);
|
kpeter@334
|
631 |
}
|
kpeter@334
|
632 |
|
deba@335
|
633 |
/// \brief Gives back the number of the columns.
|
kpeter@334
|
634 |
///
|
deba@335
|
635 |
/// Gives back the number of the columns.
|
kpeter@334
|
636 |
int width() const {
|
kpeter@334
|
637 |
return Parent::width();
|
kpeter@334
|
638 |
}
|
kpeter@334
|
639 |
|
deba@335
|
640 |
/// \brief Gives back the number of the rows.
|
kpeter@334
|
641 |
///
|
deba@335
|
642 |
/// Gives back the number of the rows.
|
kpeter@334
|
643 |
int height() const {
|
kpeter@334
|
644 |
return Parent::height();
|
kpeter@334
|
645 |
}
|
kpeter@334
|
646 |
|
deba@335
|
647 |
/// \brief Gives back the arc goes right from the node.
|
deba@335
|
648 |
///
|
deba@335
|
649 |
/// Gives back the arc goes right from the node. If there is not
|
deba@335
|
650 |
/// outgoing arc then it gives back INVALID.
|
deba@335
|
651 |
Arc right(Node n) const {
|
deba@335
|
652 |
return Parent::right(n);
|
deba@335
|
653 |
}
|
deba@335
|
654 |
|
deba@335
|
655 |
/// \brief Gives back the arc goes left from the node.
|
deba@335
|
656 |
///
|
deba@335
|
657 |
/// Gives back the arc goes left from the node. If there is not
|
deba@335
|
658 |
/// outgoing arc then it gives back INVALID.
|
deba@335
|
659 |
Arc left(Node n) const {
|
deba@335
|
660 |
return Parent::left(n);
|
deba@335
|
661 |
}
|
deba@335
|
662 |
|
deba@335
|
663 |
/// \brief Gives back the arc goes up from the node.
|
deba@335
|
664 |
///
|
deba@335
|
665 |
/// Gives back the arc goes up from the node. If there is not
|
deba@335
|
666 |
/// outgoing arc then it gives back INVALID.
|
deba@335
|
667 |
Arc up(Node n) const {
|
deba@335
|
668 |
return Parent::up(n);
|
deba@335
|
669 |
}
|
deba@335
|
670 |
|
kpeter@334
|
671 |
/// \brief Gives back the arc goes down from the node.
|
kpeter@334
|
672 |
///
|
kpeter@334
|
673 |
/// Gives back the arc goes down from the node. If there is not
|
deba@335
|
674 |
/// outgoing arc then it gives back INVALID.
|
kpeter@334
|
675 |
Arc down(Node n) const {
|
deba@335
|
676 |
return Parent::down(n);
|
kpeter@334
|
677 |
}
|
kpeter@334
|
678 |
|
deba@335
|
679 |
/// \brief Index map of the grid graph
|
kpeter@334
|
680 |
///
|
deba@335
|
681 |
/// Just returns an IndexMap for the grid graph.
|
deba@335
|
682 |
IndexMap indexMap() const {
|
deba@335
|
683 |
return IndexMap(*this);
|
kpeter@334
|
684 |
}
|
kpeter@334
|
685 |
|
deba@335
|
686 |
/// \brief Row map of the grid graph
|
kpeter@334
|
687 |
///
|
deba@335
|
688 |
/// Just returns a RowMap for the grid graph.
|
deba@335
|
689 |
RowMap rowMap() const {
|
deba@335
|
690 |
return RowMap(*this);
|
kpeter@334
|
691 |
}
|
kpeter@334
|
692 |
|
deba@335
|
693 |
/// \brief Column map of the grid graph
|
kpeter@334
|
694 |
///
|
deba@335
|
695 |
/// Just returns a ColMap for the grid graph.
|
deba@335
|
696 |
ColMap colMap() const {
|
deba@335
|
697 |
return ColMap(*this);
|
kpeter@334
|
698 |
}
|
kpeter@334
|
699 |
|
deba@335
|
700 |
};
|
kpeter@334
|
701 |
|
kpeter@334
|
702 |
}
|
deba@335
|
703 |
#endif
|