Changeset 2223:590c1b663a27 in lemon-0.x for lemon/grid_ugraph.h
- Timestamp:
- 09/29/06 13:25:27 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2963
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/grid_ugraph.h
r2207 r2223 35 35 namespace lemon { 36 36 37 /// \brief Base graph for GridUGraph.38 ///39 /// Base graph for grid graph. It describes some member functions40 /// which can be used in the GridUGraph.41 ///42 /// \warning Always use the GridUGraph instead of this.43 /// \see GridUGraph44 37 class GridUGraphBase { 45 38 … … 57 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 52 void construct(int width, int height) { 63 53 _height = height; _width = 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 not71 /// outgoing edge then it gives back INVALID.72 58 Edge _down(Node n) const { 73 59 if (n.id < _nodeNum - _width) { … … 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 not83 /// incoming edge then it gives back INVALID.84 66 Edge _up(Node n) const { 85 67 if (n.id >= _width) { … … 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 not95 /// outgoing edge then it gives back INVALID.96 74 Edge _right(Node n) const { 97 75 if (n.id % _width < _width - 1) { … … 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 not107 /// incoming edge then it gives back INVALID.108 82 Edge _left(Node n) const { 109 83 if (n.id % _width > 0) { … … 124 98 125 99 126 /// \brief The node on the given position.127 ///128 /// Gives back the node on the given position.129 100 Node operator()(int i, int j) const { 130 101 LEMON_ASSERT(0 <= i && i < width() && 0 <= j && … … 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 106 int row(Node n) const { 139 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 110 int col(Node n) const { 146 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 114 int width() const { 153 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 118 int height() const { 160 119 return _height; … … 164 123 typedef True EdgeNumTag; 165 124 166 ///Number of nodes.167 125 int nodeNum() const { return _nodeNum; } 168 ///Number of edges.169 126 int edgeNum() const { return _edgeNum; } 170 127 171 /// Maximum node ID.172 173 /// Maximum node ID.174 ///\sa id(Node)175 128 int maxNodeId() const { return nodeNum() - 1; } 176 /// Maximum edge ID.177 178 /// Maximum edge ID.179 ///\sa id(Edge)180 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 131 Node source(Edge e) const { 186 132 if (e.id < _edgeLimit) { … … 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 140 Node target(Edge e) const { 198 141 if (e.id < _edgeLimit) { … … 204 147 } 205 148 206 /// Node ID.207 208 /// The ID of a valid Node is a nonnegative integer not greater than209 /// \ref maxNodeId(). The range of the ID's is not surely continuous210 /// 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 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 than219 /// \ref maxEdgeId(). The range of the ID's is not surely continuous220 /// 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 150 static int id(Edge e) { return e.id; } 225 151 … … 230 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), then237 /// It finds the first edge from \c u to \c v. Otherwise it looks for238 /// 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 158 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { 241 159 if (prev != INVALID) return INVALID; … … 360 278 /// Two nodes are connected in the graph if the indices differ only 361 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 284 /// The graph can be indiced in the following way: … … 376 297 /// 377 298 /// \author Balazs Dezso 378 /// \see GridUGraphBase379 299 class GridUGraph : public ExtendedGridUGraphBase { 380 300 public: … … 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 434 /// \brief Gives back the edge goes down from the node. 480 435 ///
Note: See TracChangeset
for help on using the changeset viewer.