1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
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. |
|
12 * |
|
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 |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef GRID_GRAPH_H |
|
20 #define GRID_GRAPH_H |
|
21 |
|
22 #include <iostream> |
|
23 #include <lemon/invalid.h> |
|
24 #include <lemon/utility.h> |
|
25 |
|
26 #include <lemon/bits/iterable_graph_extender.h> |
|
27 #include <lemon/bits/alteration_notifier.h> |
|
28 #include <lemon/bits/static_map.h> |
|
29 #include <lemon/bits/graph_extender.h> |
|
30 |
|
31 #include <lemon/xy.h> |
|
32 |
|
33 ///\ingroup graphs |
|
34 ///\file |
|
35 ///\brief GridGraph class. |
|
36 |
|
37 namespace lemon { |
|
38 |
|
39 /// \brief Base graph for GridGraph. |
|
40 /// |
|
41 /// Base graph for grid graph. It describes some member functions |
|
42 /// which can be used in the GridGraph. |
|
43 /// |
|
44 /// \warning Always use the GridGraph instead of this. |
|
45 /// \see GridGraph |
|
46 class GridGraphBase { |
|
47 |
|
48 public: |
|
49 |
|
50 typedef GridGraphBase Graph; |
|
51 |
|
52 class Node; |
|
53 class Edge; |
|
54 |
|
55 public: |
|
56 |
|
57 GridGraphBase() {} |
|
58 |
|
59 protected: |
|
60 |
|
61 /// \brief Creates a grid graph with the given size. |
|
62 /// |
|
63 /// Creates a grid graph with the given size. |
|
64 void construct(int width, int height) { |
|
65 _height = height; _width = width; |
|
66 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; |
|
67 _edgeLimit = _nodeNum - width; |
|
68 } |
|
69 |
|
70 /// \brief Gives back the edge goes down from the node. |
|
71 /// |
|
72 /// Gives back the edge goes down from the node. If there is not |
|
73 /// outgoing edge then it gives back INVALID. |
|
74 Edge _down(Node n) const { |
|
75 if (n.id < _nodeNum - _width) { |
|
76 return Edge(n.id); |
|
77 } else { |
|
78 return INVALID; |
|
79 } |
|
80 } |
|
81 |
|
82 /// \brief Gives back the edge comes from up into the node. |
|
83 /// |
|
84 /// Gives back the edge comes from up into the node. If there is not |
|
85 /// incoming edge then it gives back INVALID. |
|
86 Edge _up(Node n) const { |
|
87 if (n.id >= _width) { |
|
88 return Edge(n.id - _width); |
|
89 } else { |
|
90 return INVALID; |
|
91 } |
|
92 } |
|
93 |
|
94 /// \brief Gives back the edge goes right from the node. |
|
95 /// |
|
96 /// Gives back the edge goes right from the node. If there is not |
|
97 /// outgoing edge then it gives back INVALID. |
|
98 Edge _right(Node n) const { |
|
99 if (n.id % _width < _width - 1) { |
|
100 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1); |
|
101 } else { |
|
102 return INVALID; |
|
103 } |
|
104 } |
|
105 |
|
106 /// \brief Gives back the edge comes from left into the node. |
|
107 /// |
|
108 /// Gives back the edge comes left up into the node. If there is not |
|
109 /// incoming edge then it gives back INVALID. |
|
110 Edge _left(Node n) const { |
|
111 if (n.id % _width > 0) { |
|
112 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; |
|
113 } else { |
|
114 return INVALID; |
|
115 } |
|
116 } |
|
117 |
|
118 |
|
119 public: |
|
120 |
|
121 /// \brief The node on the given position. |
|
122 /// |
|
123 /// Gives back the node on the given position. |
|
124 Node operator()(int i, int j) const { |
|
125 return Node(i + j * _width); |
|
126 } |
|
127 |
|
128 /// \brief Gives back the row index of the node. |
|
129 /// |
|
130 /// Gives back the row index of the node. |
|
131 int row(Node n) const { |
|
132 return n.id / _width; |
|
133 } |
|
134 |
|
135 /// \brief Gives back the coloumn index of the node. |
|
136 /// |
|
137 /// Gives back the coloumn index of the node. |
|
138 int col(Node n) const { |
|
139 return n.id % _width; |
|
140 } |
|
141 |
|
142 /// \brief Gives back the width of the graph. |
|
143 /// |
|
144 /// Gives back the width of the graph. |
|
145 int width() const { |
|
146 return _width; |
|
147 } |
|
148 |
|
149 /// \brief Gives back the height of the graph. |
|
150 /// |
|
151 /// Gives back the height of the graph. |
|
152 int height() const { |
|
153 return _height; |
|
154 } |
|
155 |
|
156 typedef True NodeNumTag; |
|
157 typedef True EdgeNumTag; |
|
158 |
|
159 ///Number of nodes. |
|
160 int nodeNum() const { return _nodeNum; } |
|
161 ///Number of edges. |
|
162 int edgeNum() const { return _edgeNum; } |
|
163 |
|
164 /// Maximum node ID. |
|
165 |
|
166 /// Maximum node ID. |
|
167 ///\sa id(Node) |
|
168 int maxNodeId() const { return nodeNum() - 1; } |
|
169 /// Maximum edge ID. |
|
170 |
|
171 /// Maximum edge ID. |
|
172 ///\sa id(Edge) |
|
173 int maxEdgeId() const { return edgeNum() - 1; } |
|
174 |
|
175 /// \brief Gives back the source node of an edge. |
|
176 /// |
|
177 /// Gives back the source node of an edge. |
|
178 Node source(Edge e) const { |
|
179 if (e.id < _edgeLimit) { |
|
180 return e.id; |
|
181 } else { |
|
182 return (e.id - _edgeLimit) % (_width - 1) + |
|
183 (e.id - _edgeLimit) / (_width - 1) * _width; |
|
184 } |
|
185 } |
|
186 |
|
187 /// \brief Gives back the target node of an edge. |
|
188 /// |
|
189 /// Gives back the target node of an edge. |
|
190 Node target(Edge e) const { |
|
191 if (e.id < _edgeLimit) { |
|
192 return e.id + _width; |
|
193 } else { |
|
194 return (e.id - _edgeLimit) % (_width - 1) + |
|
195 (e.id - _edgeLimit) / (_width - 1) * _width + 1; |
|
196 } |
|
197 } |
|
198 |
|
199 /// Node ID. |
|
200 |
|
201 /// The ID of a valid Node is a nonnegative integer not greater than |
|
202 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
203 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
204 /// |
|
205 /// The ID of the \ref INVALID node is -1. |
|
206 ///\return The ID of the node \c v. |
|
207 |
|
208 static int id(Node v) { return v.id; } |
|
209 /// Edge ID. |
|
210 |
|
211 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
212 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
213 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
214 /// |
|
215 /// The ID of the \ref INVALID edge is -1. |
|
216 ///\return The ID of the edge \c e. |
|
217 static int id(Edge e) { return e.id; } |
|
218 |
|
219 static Node nodeFromId(int id) { return Node(id);} |
|
220 |
|
221 static Edge edgeFromId(int id) { return Edge(id);} |
|
222 |
|
223 typedef True FindEdgeTag; |
|
224 |
|
225 /// Finds an edge between two nodes. |
|
226 |
|
227 /// Finds an edge from node \c u to node \c v. |
|
228 /// |
|
229 /// If \c prev is \ref INVALID (this is the default value), then |
|
230 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
231 /// the next edge from \c u to \c v after \c prev. |
|
232 /// \return The found edge or INVALID if there is no such an edge. |
|
233 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { |
|
234 if (prev != INVALID) return INVALID; |
|
235 if (v.id - u.id == _width) return Edge(u.id); |
|
236 if (v.id - u.id == 1 && u.id % _width < _width - 1) { |
|
237 return Edge(u.id / _width * (_width - 1) + |
|
238 u.id % _width + _edgeLimit); |
|
239 } |
|
240 return INVALID; |
|
241 } |
|
242 |
|
243 |
|
244 class Node { |
|
245 friend class GridGraphBase; |
|
246 |
|
247 protected: |
|
248 int id; |
|
249 Node(int _id) { id = _id;} |
|
250 public: |
|
251 Node() {} |
|
252 Node (Invalid) { id = -1; } |
|
253 bool operator==(const Node node) const {return id == node.id;} |
|
254 bool operator!=(const Node node) const {return id != node.id;} |
|
255 bool operator<(const Node node) const {return id < node.id;} |
|
256 }; |
|
257 |
|
258 |
|
259 |
|
260 class Edge { |
|
261 friend class GridGraphBase; |
|
262 |
|
263 protected: |
|
264 int id; |
|
265 |
|
266 Edge(int _id) : id(_id) {} |
|
267 |
|
268 public: |
|
269 Edge() { } |
|
270 Edge (Invalid) { id = -1; } |
|
271 bool operator==(const Edge edge) const {return id == edge.id;} |
|
272 bool operator!=(const Edge edge) const {return id != edge.id;} |
|
273 bool operator<(const Edge edge) const {return id < edge.id;} |
|
274 }; |
|
275 |
|
276 void first(Node& node) const { |
|
277 node.id = nodeNum() - 1; |
|
278 } |
|
279 |
|
280 static void next(Node& node) { |
|
281 --node.id; |
|
282 } |
|
283 |
|
284 void first(Edge& edge) const { |
|
285 edge.id = edgeNum() - 1; |
|
286 } |
|
287 |
|
288 static void next(Edge& edge) { |
|
289 --edge.id; |
|
290 } |
|
291 |
|
292 void firstOut(Edge& edge, const Node& node) const { |
|
293 if (node.id < _nodeNum - _width) { |
|
294 edge.id = node.id; |
|
295 } else if (node.id % _width < _width - 1) { |
|
296 edge.id = _edgeLimit + node.id % _width + |
|
297 (node.id / _width) * (_width - 1); |
|
298 } else { |
|
299 edge.id = -1; |
|
300 } |
|
301 } |
|
302 |
|
303 void nextOut(Edge& edge) const { |
|
304 if (edge.id >= _edgeLimit) { |
|
305 edge.id = -1; |
|
306 } else if (edge.id % _width < _width - 1) { |
|
307 edge.id = _edgeLimit + edge.id % _width + |
|
308 (edge.id / _width) * (_width - 1); |
|
309 } else { |
|
310 edge.id = -1; |
|
311 } |
|
312 } |
|
313 |
|
314 void firstIn(Edge& edge, const Node& node) const { |
|
315 if (node.id >= _width) { |
|
316 edge.id = node.id - _width; |
|
317 } else if (node.id % _width > 0) { |
|
318 edge.id = _edgeLimit + node.id % _width + |
|
319 (node.id / _width) * (_width - 1) - 1; |
|
320 } else { |
|
321 edge.id = -1; |
|
322 } |
|
323 } |
|
324 |
|
325 void nextIn(Edge& edge) const { |
|
326 if (edge.id >= _edgeLimit) { |
|
327 edge.id = -1; |
|
328 } else if (edge.id % _width > 0) { |
|
329 edge.id = _edgeLimit + edge.id % _width + |
|
330 (edge.id / _width + 1) * (_width - 1) - 1; |
|
331 } else { |
|
332 edge.id = -1; |
|
333 } |
|
334 } |
|
335 |
|
336 private: |
|
337 int _width, _height; |
|
338 int _nodeNum, _edgeNum; |
|
339 int _edgeLimit; |
|
340 }; |
|
341 |
|
342 |
|
343 typedef StaticMappableUGraphExtender< |
|
344 IterableUGraphExtender< |
|
345 AlterableUGraphExtender< |
|
346 UGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase; |
|
347 |
|
348 /// \ingroup graphs |
|
349 /// |
|
350 /// \brief Grid graph class |
|
351 /// |
|
352 /// This class implements a special graph type. The nodes of the |
|
353 /// graph can be indiced by two integer \c (i,j) value where \c i |
|
354 /// is in the \c [0,width) range and j is in the [0, height) range. |
|
355 /// Two nodes are connected in the graph if the indices differ only |
|
356 /// on one position and only one is the difference. |
|
357 /// |
|
358 /// The graph can be indiced in the following way: |
|
359 ///\code |
|
360 /// GridGraph graph(w, h); |
|
361 /// GridGraph::NodeMap<int> val(graph); |
|
362 /// for (int i = 0; i < graph.width(); ++i) { |
|
363 /// for (int j = 0; j < graph.height(); ++j) { |
|
364 /// val[graph(i, j)] = i + j; |
|
365 /// } |
|
366 /// } |
|
367 ///\endcode |
|
368 /// |
|
369 /// The graph type is fully conform to the \ref concept::UGraph |
|
370 /// "Undirected Graph" concept. |
|
371 /// |
|
372 /// \author Balazs Dezso |
|
373 /// \see GridGraphBase |
|
374 class GridGraph : public ExtendedGridGraphBase { |
|
375 public: |
|
376 |
|
377 /// \brief Map to get the indices of the nodes as xy<int>. |
|
378 /// |
|
379 /// Map to get the indices of the nodes as xy<int>. |
|
380 class IndexMap { |
|
381 public: |
|
382 typedef True NeedCopy; |
|
383 /// \brief The key type of the map |
|
384 typedef GridGraph::Node Key; |
|
385 /// \brief The value type of the map |
|
386 typedef xy<int> Value; |
|
387 |
|
388 /// \brief Constructor |
|
389 /// |
|
390 /// Constructor |
|
391 IndexMap(const GridGraph& _graph) : graph(_graph) {} |
|
392 |
|
393 /// \brief The subscript operator |
|
394 /// |
|
395 /// The subscript operator. |
|
396 Value operator[](Key key) const { |
|
397 return xy<int>(graph.row(key), graph.col(key)); |
|
398 } |
|
399 |
|
400 private: |
|
401 const GridGraph& graph; |
|
402 }; |
|
403 |
|
404 /// \brief Map to get the row of the nodes. |
|
405 /// |
|
406 /// Map to get the row of the nodes. |
|
407 class RowMap { |
|
408 public: |
|
409 typedef True NeedCopy; |
|
410 /// \brief The key type of the map |
|
411 typedef GridGraph::Node Key; |
|
412 /// \brief The value type of the map |
|
413 typedef int Value; |
|
414 |
|
415 /// \brief Constructor |
|
416 /// |
|
417 /// Constructor |
|
418 RowMap(const GridGraph& _graph) : graph(_graph) {} |
|
419 |
|
420 /// \brief The subscript operator |
|
421 /// |
|
422 /// The subscript operator. |
|
423 Value operator[](Key key) const { |
|
424 return graph.row(key); |
|
425 } |
|
426 |
|
427 private: |
|
428 const GridGraph& graph; |
|
429 }; |
|
430 |
|
431 /// \brief Map to get the column of the nodes. |
|
432 /// |
|
433 /// Map to get the column of the nodes. |
|
434 class ColMap { |
|
435 public: |
|
436 typedef True NeedCopy; |
|
437 /// \brief The key type of the map |
|
438 typedef GridGraph::Node Key; |
|
439 /// \brief The value type of the map |
|
440 typedef int Value; |
|
441 |
|
442 /// \brief Constructor |
|
443 /// |
|
444 /// Constructor |
|
445 ColMap(const GridGraph& _graph) : graph(_graph) {} |
|
446 |
|
447 /// \brief The subscript operator |
|
448 /// |
|
449 /// The subscript operator. |
|
450 Value operator[](Key key) const { |
|
451 return graph.col(key); |
|
452 } |
|
453 |
|
454 private: |
|
455 const GridGraph& graph; |
|
456 }; |
|
457 |
|
458 /// \brief Constructor |
|
459 /// |
|
460 /// |
|
461 GridGraph(int n, int m) { construct(n, m); } |
|
462 |
|
463 /// \brief Gives back the edge goes down from the node. |
|
464 /// |
|
465 /// Gives back the edge goes down from the node. If there is not |
|
466 /// outgoing edge then it gives back INVALID. |
|
467 Edge down(Node n) const { |
|
468 UEdge ue = _down(n); |
|
469 return ue != INVALID ? direct(ue, true) : INVALID; |
|
470 } |
|
471 |
|
472 /// \brief Gives back the edge goes up from the node. |
|
473 /// |
|
474 /// Gives back the edge goes up from the node. If there is not |
|
475 /// outgoing edge then it gives back INVALID. |
|
476 Edge up(Node n) const { |
|
477 UEdge ue = _up(n); |
|
478 return ue != INVALID ? direct(ue, false) : INVALID; |
|
479 } |
|
480 |
|
481 /// \brief Gives back the edge goes right from the node. |
|
482 /// |
|
483 /// Gives back the edge goes right from the node. If there is not |
|
484 /// outgoing edge then it gives back INVALID. |
|
485 Edge right(Node n) const { |
|
486 UEdge ue = _right(n); |
|
487 return ue != INVALID ? direct(ue, true) : INVALID; |
|
488 } |
|
489 |
|
490 /// \brief Gives back the edge goes left from the node. |
|
491 /// |
|
492 /// Gives back the edge goes left from the node. If there is not |
|
493 /// outgoing edge then it gives back INVALID. |
|
494 Edge left(Node n) const { |
|
495 UEdge ue = _left(n); |
|
496 return ue != INVALID ? direct(ue, false) : INVALID; |
|
497 } |
|
498 |
|
499 }; |
|
500 |
|
501 /// \brief Index map of the grid graph |
|
502 /// |
|
503 /// Just returns an IndexMap for the grid graph. |
|
504 GridGraph::IndexMap indexMap(const GridGraph& graph) { |
|
505 return GridGraph::IndexMap(graph); |
|
506 } |
|
507 |
|
508 /// \brief Row map of the grid graph |
|
509 /// |
|
510 /// Just returns a RowMap for the grid graph. |
|
511 GridGraph::RowMap rowMap(const GridGraph& graph) { |
|
512 return GridGraph::RowMap(graph); |
|
513 } |
|
514 |
|
515 /// \brief Column map of the grid graph |
|
516 /// |
|
517 /// Just returns a ColMap for the grid graph. |
|
518 GridGraph::ColMap colMap(const GridGraph& graph) { |
|
519 return GridGraph::ColMap(graph); |
|
520 } |
|
521 } |
|
522 #endif |
|