54 |
47 |
55 GridUGraphBase() {} |
48 GridUGraphBase() {} |
56 |
49 |
57 protected: |
50 protected: |
58 |
51 |
59 /// \brief Creates a grid graph with the given size. |
|
60 /// |
|
61 /// Creates a grid graph with the given size. |
|
62 void construct(int width, int height) { |
52 void construct(int width, int height) { |
63 _height = height; _width = width; |
53 _height = height; _width = width; |
64 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; |
54 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; |
65 _edgeLimit = _nodeNum - width; |
55 _edgeLimit = _nodeNum - width; |
66 } |
56 } |
67 |
57 |
68 /// \brief Gives back the edge goes down from the node. |
|
69 /// |
|
70 /// Gives back the edge goes down from the node. If there is not |
|
71 /// outgoing edge then it gives back INVALID. |
|
72 Edge _down(Node n) const { |
58 Edge _down(Node n) const { |
73 if (n.id < _nodeNum - _width) { |
59 if (n.id < _nodeNum - _width) { |
74 return Edge(n.id); |
60 return Edge(n.id); |
75 } else { |
61 } else { |
76 return INVALID; |
62 return INVALID; |
77 } |
63 } |
78 } |
64 } |
79 |
65 |
80 /// \brief Gives back the edge comes from up into the node. |
|
81 /// |
|
82 /// Gives back the edge comes from up into the node. If there is not |
|
83 /// incoming edge then it gives back INVALID. |
|
84 Edge _up(Node n) const { |
66 Edge _up(Node n) const { |
85 if (n.id >= _width) { |
67 if (n.id >= _width) { |
86 return Edge(n.id - _width); |
68 return Edge(n.id - _width); |
87 } else { |
69 } else { |
88 return INVALID; |
70 return INVALID; |
89 } |
71 } |
90 } |
72 } |
91 |
73 |
92 /// \brief Gives back the edge goes right from the node. |
|
93 /// |
|
94 /// Gives back the edge goes right from the node. If there is not |
|
95 /// outgoing edge then it gives back INVALID. |
|
96 Edge _right(Node n) const { |
74 Edge _right(Node n) const { |
97 if (n.id % _width < _width - 1) { |
75 if (n.id % _width < _width - 1) { |
98 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1); |
76 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1); |
99 } else { |
77 } else { |
100 return INVALID; |
78 return INVALID; |
101 } |
79 } |
102 } |
80 } |
103 |
81 |
104 /// \brief Gives back the edge comes from left into the node. |
|
105 /// |
|
106 /// Gives back the edge comes left up into the node. If there is not |
|
107 /// incoming edge then it gives back INVALID. |
|
108 Edge _left(Node n) const { |
82 Edge _left(Node n) const { |
109 if (n.id % _width > 0) { |
83 if (n.id % _width > 0) { |
110 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; |
84 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; |
111 } else { |
85 } else { |
112 return INVALID; |
86 return INVALID; |
121 return "lemon::GridUGraph::IndexError"; |
95 return "lemon::GridUGraph::IndexError"; |
122 } |
96 } |
123 }; |
97 }; |
124 |
98 |
125 |
99 |
126 /// \brief The node on the given position. |
|
127 /// |
|
128 /// Gives back the node on the given position. |
|
129 Node operator()(int i, int j) const { |
100 Node operator()(int i, int j) const { |
130 LEMON_ASSERT(0 <= i && i < width() && 0 <= j && |
101 LEMON_ASSERT(0 <= i && i < width() && 0 <= j && |
131 j < height(), IndexError()); |
102 j < height(), IndexError()); |
132 return Node(i + j * _width); |
103 return Node(i + j * _width); |
133 } |
104 } |
134 |
105 |
135 /// \brief Gives back the row index of the node. |
|
136 /// |
|
137 /// Gives back the row index of the node. |
|
138 int row(Node n) const { |
106 int row(Node n) const { |
139 return n.id / _width; |
107 return n.id / _width; |
140 } |
108 } |
141 |
109 |
142 /// \brief Gives back the coloumn index of the node. |
|
143 /// |
|
144 /// Gives back the coloumn index of the node. |
|
145 int col(Node n) const { |
110 int col(Node n) const { |
146 return n.id % _width; |
111 return n.id % _width; |
147 } |
112 } |
148 |
113 |
149 /// \brief Gives back the width of the graph. |
|
150 /// |
|
151 /// Gives back the width of the graph. |
|
152 int width() const { |
114 int width() const { |
153 return _width; |
115 return _width; |
154 } |
116 } |
155 |
117 |
156 /// \brief Gives back the height of the graph. |
|
157 /// |
|
158 /// Gives back the height of the graph. |
|
159 int height() const { |
118 int height() const { |
160 return _height; |
119 return _height; |
161 } |
120 } |
162 |
121 |
163 typedef True NodeNumTag; |
122 typedef True NodeNumTag; |
164 typedef True EdgeNumTag; |
123 typedef True EdgeNumTag; |
165 |
124 |
166 ///Number of nodes. |
|
167 int nodeNum() const { return _nodeNum; } |
125 int nodeNum() const { return _nodeNum; } |
168 ///Number of edges. |
|
169 int edgeNum() const { return _edgeNum; } |
126 int edgeNum() const { return _edgeNum; } |
170 |
127 |
171 /// Maximum node ID. |
|
172 |
|
173 /// Maximum node ID. |
|
174 ///\sa id(Node) |
|
175 int maxNodeId() const { return nodeNum() - 1; } |
128 int maxNodeId() const { return nodeNum() - 1; } |
176 /// Maximum edge ID. |
|
177 |
|
178 /// Maximum edge ID. |
|
179 ///\sa id(Edge) |
|
180 int maxEdgeId() const { return edgeNum() - 1; } |
129 int maxEdgeId() const { return edgeNum() - 1; } |
181 |
130 |
182 /// \brief Gives back the source node of an edge. |
|
183 /// |
|
184 /// Gives back the source node of an edge. |
|
185 Node source(Edge e) const { |
131 Node source(Edge e) const { |
186 if (e.id < _edgeLimit) { |
132 if (e.id < _edgeLimit) { |
187 return e.id; |
133 return e.id; |
188 } else { |
134 } else { |
189 return (e.id - _edgeLimit) % (_width - 1) + |
135 return (e.id - _edgeLimit) % (_width - 1) + |
190 (e.id - _edgeLimit) / (_width - 1) * _width; |
136 (e.id - _edgeLimit) / (_width - 1) * _width; |
191 } |
137 } |
192 } |
138 } |
193 |
139 |
194 /// \brief Gives back the target node of an edge. |
|
195 /// |
|
196 /// Gives back the target node of an edge. |
|
197 Node target(Edge e) const { |
140 Node target(Edge e) const { |
198 if (e.id < _edgeLimit) { |
141 if (e.id < _edgeLimit) { |
199 return e.id + _width; |
142 return e.id + _width; |
200 } else { |
143 } else { |
201 return (e.id - _edgeLimit) % (_width - 1) + |
144 return (e.id - _edgeLimit) % (_width - 1) + |
202 (e.id - _edgeLimit) / (_width - 1) * _width + 1; |
145 (e.id - _edgeLimit) / (_width - 1) * _width + 1; |
203 } |
146 } |
204 } |
147 } |
205 |
148 |
206 /// Node ID. |
|
207 |
|
208 /// The ID of a valid Node is a nonnegative integer not greater than |
|
209 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
210 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
211 /// |
|
212 /// The ID of the \ref INVALID node is -1. |
|
213 ///\return The ID of the node \c v. |
|
214 |
|
215 static int id(Node v) { return v.id; } |
149 static int id(Node v) { return v.id; } |
216 /// Edge ID. |
|
217 |
|
218 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
219 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
220 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
221 /// |
|
222 /// The ID of the \ref INVALID edge is -1. |
|
223 ///\return The ID of the edge \c e. |
|
224 static int id(Edge e) { return e.id; } |
150 static int id(Edge e) { return e.id; } |
225 |
151 |
226 static Node nodeFromId(int id) { return Node(id);} |
152 static Node nodeFromId(int id) { return Node(id);} |
227 |
153 |
228 static Edge edgeFromId(int id) { return Edge(id);} |
154 static Edge edgeFromId(int id) { return Edge(id);} |
229 |
155 |
230 typedef True FindEdgeTag; |
156 typedef True FindEdgeTag; |
231 |
157 |
232 /// Finds an edge between two nodes. |
|
233 |
|
234 /// Finds an edge from node \c u to node \c v. |
|
235 /// |
|
236 /// If \c prev is \ref INVALID (this is the default value), then |
|
237 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
238 /// the next edge from \c u to \c v after \c prev. |
|
239 /// \return The found edge or INVALID if there is no such an edge. |
|
240 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { |
158 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { |
241 if (prev != INVALID) return INVALID; |
159 if (prev != INVALID) return INVALID; |
242 if (v.id - u.id == _width) return Edge(u.id); |
160 if (v.id - u.id == _width) return Edge(u.id); |
243 if (v.id - u.id == 1 && u.id % _width < _width - 1) { |
161 if (v.id - u.id == 1 && u.id % _width < _width - 1) { |
244 return Edge(u.id / _width * (_width - 1) + |
162 return Edge(u.id / _width * (_width - 1) + |
357 /// This class implements a special graph type. The nodes of the |
275 /// This class implements a special graph type. The nodes of the |
358 /// graph can be indiced by two integer \c (i,j) value where \c i |
276 /// graph can be indiced by two integer \c (i,j) value where \c i |
359 /// is in the \c [0,width) range and j is in the [0, height) range. |
277 /// is in the \c [0,width) range and j is in the [0, height) range. |
360 /// Two nodes are connected in the graph if the indices differ only |
278 /// Two nodes are connected in the graph if the indices differ only |
361 /// on one position and only one is the difference. |
279 /// on one position and only one is the difference. |
|
280 /// |
|
281 /// \image html grid_ugraph.png |
|
282 /// \image latex grid_ugraph.eps "Grid graph" width=\textwidth |
362 /// |
283 /// |
363 /// The graph can be indiced in the following way: |
284 /// The graph can be indiced in the following way: |
364 ///\code |
285 ///\code |
365 /// GridUGraph graph(w, h); |
286 /// GridUGraph graph(w, h); |
366 /// GridUGraph::NodeMap<int> val(graph); |
287 /// GridUGraph::NodeMap<int> val(graph); |
474 Parent::getNotifier(Node()).build(); |
394 Parent::getNotifier(Node()).build(); |
475 Parent::getNotifier(UEdge()).build(); |
395 Parent::getNotifier(UEdge()).build(); |
476 Parent::getNotifier(Edge()).build(); |
396 Parent::getNotifier(Edge()).build(); |
477 } |
397 } |
478 |
398 |
|
399 /// \brief The node on the given position. |
|
400 /// |
|
401 /// Gives back the node on the given position. |
|
402 Node operator()(int i, int j) const { |
|
403 return Parent::operator()(i, j); |
|
404 } |
|
405 |
|
406 /// \brief Gives back the row index of the node. |
|
407 /// |
|
408 /// Gives back the row index of the node. |
|
409 int row(Node n) const { |
|
410 return Parent::row(n); |
|
411 } |
|
412 |
|
413 /// \brief Gives back the coloumn index of the node. |
|
414 /// |
|
415 /// Gives back the coloumn index of the node. |
|
416 int col(Node n) const { |
|
417 return Parent::col(n); |
|
418 } |
|
419 |
|
420 /// \brief Gives back the width of the graph. |
|
421 /// |
|
422 /// Gives back the width of the graph. |
|
423 int width() const { |
|
424 return Parent::width(); |
|
425 } |
|
426 |
|
427 /// \brief Gives back the height of the graph. |
|
428 /// |
|
429 /// Gives back the height of the graph. |
|
430 int height() const { |
|
431 return Parent::height(); |
|
432 } |
|
433 |
479 /// \brief Gives back the edge goes down from the node. |
434 /// \brief Gives back the edge goes down from the node. |
480 /// |
435 /// |
481 /// Gives back the edge goes down from the node. If there is not |
436 /// Gives back the edge goes down from the node. If there is not |
482 /// outgoing edge then it gives back INVALID. |
437 /// outgoing edge then it gives back INVALID. |
483 Edge down(Node n) const { |
438 Edge down(Node n) const { |