226 /// |
226 /// |
227 /// If \c prev is \ref INVALID (this is the default value), then |
227 /// If \c prev is \ref INVALID (this is the default value), then |
228 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
228 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
229 /// the next edge from \c u to \c v after \c prev. |
229 /// the next edge from \c u to \c v after \c prev. |
230 /// \return The found edge or INVALID if there is no such an edge. |
230 /// \return The found edge or INVALID if there is no such an edge. |
231 Edge findEdge(Node u, Node v, Edge prev = INVALID) { |
231 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { |
232 if (prev != INVALID) return INVALID; |
232 if (prev != INVALID) return INVALID; |
233 if (v.id - u.id == _width) return Edge(u.id); |
233 if (v.id - u.id == _width) return Edge(u.id); |
234 if (v.id - u.id == 1 && u.id % _width < _width - 1) { |
234 if (v.id - u.id == 1 && u.id % _width < _width - 1) { |
235 return Edge(u.id / _width * (_width - 1) + |
235 return Edge(u.id / _width * (_width - 1) + |
236 u.id % _width + _edgeLimit); |
236 u.id % _width + _edgeLimit); |
347 /// |
347 /// |
348 /// \brief Grid graph class |
348 /// \brief Grid graph class |
349 /// |
349 /// |
350 /// This class implements a special graph type. The nodes of the |
350 /// This class implements a special graph type. The nodes of the |
351 /// graph can be indiced by two integer \c (i,j) value where \c i |
351 /// graph can be indiced by two integer \c (i,j) value where \c i |
352 /// is in the \c [0,height) range and j is in the [0, width) range. |
352 /// is in the \c [0,width) range and j is in the [0, height) range. |
353 /// Two nodes are connected in the graph if the indices differ only |
353 /// Two nodes are connected in the graph if the indices differ only |
354 /// on one position and only one is the difference. |
354 /// on one position and only one is the difference. |
355 /// |
355 /// |
356 /// The graph can be indiced in the following way: |
356 /// The graph can be indiced in the following way: |
357 /// \code |
357 /// \code |
358 /// GridGraph graph(h, w); |
358 /// GridGraph graph(w, h); |
359 /// GridGraph::NodeMap<int> val(graph); |
359 /// GridGraph::NodeMap<int> val(graph); |
360 /// for (int i = 0; i < graph.width(); ++i) { |
360 /// for (int i = 0; i < graph.width(); ++i) { |
361 /// for (int j = 0; j < graph.height(); ++j) { |
361 /// for (int j = 0; j < graph.height(); ++j) { |
362 /// val[graph(i, j)] = i + j; |
362 /// val[graph(i, j)] = i + j; |
363 /// } |
363 /// } |
451 |
451 |
452 private: |
452 private: |
453 const GridGraph& graph; |
453 const GridGraph& graph; |
454 }; |
454 }; |
455 |
455 |
|
456 /// \brief Constructor |
|
457 /// |
|
458 /// |
456 GridGraph(int n, int m) { construct(n, m); } |
459 GridGraph(int n, int m) { construct(n, m); } |
457 |
460 |
458 /// \brief Gives back the edge goes down from the node. |
461 /// \brief Gives back the edge goes down from the node. |
459 /// |
462 /// |
460 /// Gives back the edge goes down from the node. If there is not |
463 /// Gives back the edge goes down from the node. If there is not |