1.1 --- a/lemon/grid_ugraph.h Fri Sep 29 11:23:54 2006 +0000
1.2 +++ b/lemon/grid_ugraph.h Fri Sep 29 11:25:27 2006 +0000
1.3 @@ -34,13 +34,6 @@
1.4
1.5 namespace lemon {
1.6
1.7 - /// \brief Base graph for GridUGraph.
1.8 - ///
1.9 - /// Base graph for grid graph. It describes some member functions
1.10 - /// which can be used in the GridUGraph.
1.11 - ///
1.12 - /// \warning Always use the GridUGraph instead of this.
1.13 - /// \see GridUGraph
1.14 class GridUGraphBase {
1.15
1.16 public:
1.17 @@ -56,19 +49,12 @@
1.18
1.19 protected:
1.20
1.21 - /// \brief Creates a grid graph with the given size.
1.22 - ///
1.23 - /// Creates a grid graph with the given size.
1.24 void construct(int width, int height) {
1.25 _height = height; _width = width;
1.26 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
1.27 _edgeLimit = _nodeNum - width;
1.28 }
1.29
1.30 - /// \brief Gives back the edge goes down from the node.
1.31 - ///
1.32 - /// Gives back the edge goes down from the node. If there is not
1.33 - /// outgoing edge then it gives back INVALID.
1.34 Edge _down(Node n) const {
1.35 if (n.id < _nodeNum - _width) {
1.36 return Edge(n.id);
1.37 @@ -77,10 +63,6 @@
1.38 }
1.39 }
1.40
1.41 - /// \brief Gives back the edge comes from up into the node.
1.42 - ///
1.43 - /// Gives back the edge comes from up into the node. If there is not
1.44 - /// incoming edge then it gives back INVALID.
1.45 Edge _up(Node n) const {
1.46 if (n.id >= _width) {
1.47 return Edge(n.id - _width);
1.48 @@ -89,10 +71,6 @@
1.49 }
1.50 }
1.51
1.52 - /// \brief Gives back the edge goes right from the node.
1.53 - ///
1.54 - /// Gives back the edge goes right from the node. If there is not
1.55 - /// outgoing edge then it gives back INVALID.
1.56 Edge _right(Node n) const {
1.57 if (n.id % _width < _width - 1) {
1.58 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
1.59 @@ -101,10 +79,6 @@
1.60 }
1.61 }
1.62
1.63 - /// \brief Gives back the edge comes from left into the node.
1.64 - ///
1.65 - /// Gives back the edge comes left up into the node. If there is not
1.66 - /// incoming edge then it gives back INVALID.
1.67 Edge _left(Node n) const {
1.68 if (n.id % _width > 0) {
1.69 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
1.70 @@ -123,39 +97,24 @@
1.71 };
1.72
1.73
1.74 - /// \brief The node on the given position.
1.75 - ///
1.76 - /// Gives back the node on the given position.
1.77 Node operator()(int i, int j) const {
1.78 LEMON_ASSERT(0 <= i && i < width() && 0 <= j &&
1.79 j < height(), IndexError());
1.80 return Node(i + j * _width);
1.81 }
1.82
1.83 - /// \brief Gives back the row index of the node.
1.84 - ///
1.85 - /// Gives back the row index of the node.
1.86 int row(Node n) const {
1.87 return n.id / _width;
1.88 }
1.89
1.90 - /// \brief Gives back the coloumn index of the node.
1.91 - ///
1.92 - /// Gives back the coloumn index of the node.
1.93 int col(Node n) const {
1.94 return n.id % _width;
1.95 }
1.96
1.97 - /// \brief Gives back the width of the graph.
1.98 - ///
1.99 - /// Gives back the width of the graph.
1.100 int width() const {
1.101 return _width;
1.102 }
1.103
1.104 - /// \brief Gives back the height of the graph.
1.105 - ///
1.106 - /// Gives back the height of the graph.
1.107 int height() const {
1.108 return _height;
1.109 }
1.110 @@ -163,25 +122,12 @@
1.111 typedef True NodeNumTag;
1.112 typedef True EdgeNumTag;
1.113
1.114 - ///Number of nodes.
1.115 int nodeNum() const { return _nodeNum; }
1.116 - ///Number of edges.
1.117 int edgeNum() const { return _edgeNum; }
1.118
1.119 - /// Maximum node ID.
1.120 -
1.121 - /// Maximum node ID.
1.122 - ///\sa id(Node)
1.123 int maxNodeId() const { return nodeNum() - 1; }
1.124 - /// Maximum edge ID.
1.125 -
1.126 - /// Maximum edge ID.
1.127 - ///\sa id(Edge)
1.128 int maxEdgeId() const { return edgeNum() - 1; }
1.129
1.130 - /// \brief Gives back the source node of an edge.
1.131 - ///
1.132 - /// Gives back the source node of an edge.
1.133 Node source(Edge e) const {
1.134 if (e.id < _edgeLimit) {
1.135 return e.id;
1.136 @@ -191,9 +137,6 @@
1.137 }
1.138 }
1.139
1.140 - /// \brief Gives back the target node of an edge.
1.141 - ///
1.142 - /// Gives back the target node of an edge.
1.143 Node target(Edge e) const {
1.144 if (e.id < _edgeLimit) {
1.145 return e.id + _width;
1.146 @@ -203,24 +146,7 @@
1.147 }
1.148 }
1.149
1.150 - /// Node ID.
1.151 -
1.152 - /// The ID of a valid Node is a nonnegative integer not greater than
1.153 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.154 - /// and the greatest node ID can be actually less then \ref maxNodeId().
1.155 - ///
1.156 - /// The ID of the \ref INVALID node is -1.
1.157 - ///\return The ID of the node \c v.
1.158 -
1.159 static int id(Node v) { return v.id; }
1.160 - /// Edge ID.
1.161 -
1.162 - /// The ID of a valid Edge is a nonnegative integer not greater than
1.163 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.164 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.165 - ///
1.166 - /// The ID of the \ref INVALID edge is -1.
1.167 - ///\return The ID of the edge \c e.
1.168 static int id(Edge e) { return e.id; }
1.169
1.170 static Node nodeFromId(int id) { return Node(id);}
1.171 @@ -229,14 +155,6 @@
1.172
1.173 typedef True FindEdgeTag;
1.174
1.175 - /// Finds an edge between two nodes.
1.176 -
1.177 - /// Finds an edge from node \c u to node \c v.
1.178 - ///
1.179 - /// If \c prev is \ref INVALID (this is the default value), then
1.180 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.181 - /// the next edge from \c u to \c v after \c prev.
1.182 - /// \return The found edge or INVALID if there is no such an edge.
1.183 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.184 if (prev != INVALID) return INVALID;
1.185 if (v.id - u.id == _width) return Edge(u.id);
1.186 @@ -360,6 +278,9 @@
1.187 /// Two nodes are connected in the graph if the indices differ only
1.188 /// on one position and only one is the difference.
1.189 ///
1.190 + /// \image html grid_ugraph.png
1.191 + /// \image latex grid_ugraph.eps "Grid graph" width=\textwidth
1.192 + ///
1.193 /// The graph can be indiced in the following way:
1.194 ///\code
1.195 /// GridUGraph graph(w, h);
1.196 @@ -375,7 +296,6 @@
1.197 /// "Undirected Graph" concept.
1.198 ///
1.199 /// \author Balazs Dezso
1.200 - /// \see GridUGraphBase
1.201 class GridUGraph : public ExtendedGridUGraphBase {
1.202 public:
1.203
1.204 @@ -476,6 +396,41 @@
1.205 Parent::getNotifier(Edge()).build();
1.206 }
1.207
1.208 + /// \brief The node on the given position.
1.209 + ///
1.210 + /// Gives back the node on the given position.
1.211 + Node operator()(int i, int j) const {
1.212 + return Parent::operator()(i, j);
1.213 + }
1.214 +
1.215 + /// \brief Gives back the row index of the node.
1.216 + ///
1.217 + /// Gives back the row index of the node.
1.218 + int row(Node n) const {
1.219 + return Parent::row(n);
1.220 + }
1.221 +
1.222 + /// \brief Gives back the coloumn index of the node.
1.223 + ///
1.224 + /// Gives back the coloumn index of the node.
1.225 + int col(Node n) const {
1.226 + return Parent::col(n);
1.227 + }
1.228 +
1.229 + /// \brief Gives back the width of the graph.
1.230 + ///
1.231 + /// Gives back the width of the graph.
1.232 + int width() const {
1.233 + return Parent::width();
1.234 + }
1.235 +
1.236 + /// \brief Gives back the height of the graph.
1.237 + ///
1.238 + /// Gives back the height of the graph.
1.239 + int height() const {
1.240 + return Parent::height();
1.241 + }
1.242 +
1.243 /// \brief Gives back the edge goes down from the node.
1.244 ///
1.245 /// Gives back the edge goes down from the node. If there is not