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