1.1 --- a/lemon/grid_graph.h Sun Oct 04 10:15:32 2009 +0200
1.2 +++ b/lemon/grid_graph.h Wed Dec 09 11:14:06 2009 +0100
1.3 @@ -470,18 +470,22 @@
1.4 ///
1.5 /// \brief Grid graph class
1.6 ///
1.7 - /// This class implements a special graph type. The nodes of the
1.8 - /// graph can be indexed by two integer \c (i,j) value where \c i is
1.9 - /// in the \c [0..width()-1] range and j is in the \c
1.10 - /// [0..height()-1] range. Two nodes are connected in the graph if
1.11 - /// the indexes differ exactly on one position and exactly one is
1.12 - /// the difference. The nodes of the graph can be indexed by position
1.13 - /// with the \c operator()() function. The positions of the nodes can be
1.14 - /// get with \c pos(), \c col() and \c row() members. The outgoing
1.15 + /// GridGraph implements a special graph type. The nodes of the
1.16 + /// graph can be indexed by two integer values \c (i,j) where \c i is
1.17 + /// in the range <tt>[0..width()-1]</tt> and j is in the range
1.18 + /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if
1.19 + /// the indices differ exactly on one position and the difference is
1.20 + /// also exactly one. The nodes of the graph can be obtained by position
1.21 + /// using the \c operator()() function and the indices of the nodes can
1.22 + /// be obtained using \c pos(), \c col() and \c row() members. The outgoing
1.23 /// arcs can be retrieved with the \c right(), \c up(), \c left()
1.24 /// and \c down() functions, where the bottom-left corner is the
1.25 /// origin.
1.26 ///
1.27 + /// This class is completely static and it needs constant memory space.
1.28 + /// Thus you can neither add nor delete nodes or edges, however
1.29 + /// the structure can be resized using resize().
1.30 + ///
1.31 /// \image html grid_graph.png
1.32 /// \image latex grid_graph.eps "Grid graph" width=\textwidth
1.33 ///
1.34 @@ -496,16 +500,21 @@
1.35 /// }
1.36 ///\endcode
1.37 ///
1.38 - /// This graph type fully conforms to the \ref concepts::Graph
1.39 - /// "Graph concept".
1.40 + /// This type fully conforms to the \ref concepts::Graph "Graph concept".
1.41 + /// Most of its member functions and nested classes are documented
1.42 + /// only in the concept class.
1.43 + ///
1.44 + /// This class provides constant time counting for nodes, edges and arcs.
1.45 class GridGraph : public ExtendedGridGraphBase {
1.46 typedef ExtendedGridGraphBase Parent;
1.47
1.48 public:
1.49
1.50 - /// \brief Map to get the indices of the nodes as dim2::Point<int>.
1.51 + /// \brief Map to get the indices of the nodes as \ref dim2::Point
1.52 + /// "dim2::Point<int>".
1.53 ///
1.54 - /// Map to get the indices of the nodes as dim2::Point<int>.
1.55 + /// Map to get the indices of the nodes as \ref dim2::Point
1.56 + /// "dim2::Point<int>".
1.57 class IndexMap {
1.58 public:
1.59 /// \brief The key type of the map
1.60 @@ -514,13 +523,9 @@
1.61 typedef dim2::Point<int> Value;
1.62
1.63 /// \brief Constructor
1.64 - ///
1.65 - /// Constructor
1.66 IndexMap(const GridGraph& graph) : _graph(graph) {}
1.67
1.68 /// \brief The subscript operator
1.69 - ///
1.70 - /// The subscript operator.
1.71 Value operator[](Key key) const {
1.72 return _graph.pos(key);
1.73 }
1.74 @@ -540,13 +545,9 @@
1.75 typedef int Value;
1.76
1.77 /// \brief Constructor
1.78 - ///
1.79 - /// Constructor
1.80 ColMap(const GridGraph& graph) : _graph(graph) {}
1.81
1.82 /// \brief The subscript operator
1.83 - ///
1.84 - /// The subscript operator.
1.85 Value operator[](Key key) const {
1.86 return _graph.col(key);
1.87 }
1.88 @@ -566,13 +567,9 @@
1.89 typedef int Value;
1.90
1.91 /// \brief Constructor
1.92 - ///
1.93 - /// Constructor
1.94 RowMap(const GridGraph& graph) : _graph(graph) {}
1.95
1.96 /// \brief The subscript operator
1.97 - ///
1.98 - /// The subscript operator.
1.99 Value operator[](Key key) const {
1.100 return _graph.row(key);
1.101 }
1.102 @@ -583,15 +580,14 @@
1.103
1.104 /// \brief Constructor
1.105 ///
1.106 - /// Construct a grid graph with given size.
1.107 + /// Construct a grid graph with the given size.
1.108 GridGraph(int width, int height) { construct(width, height); }
1.109
1.110 - /// \brief Resize the graph
1.111 + /// \brief Resizes the graph
1.112 ///
1.113 - /// Resize the graph. The function will fully destroy and rebuild
1.114 - /// the graph. This cause that the maps of the graph will
1.115 - /// reallocated automatically and the previous values will be
1.116 - /// lost.
1.117 + /// This function resizes the graph. It fully destroys and
1.118 + /// rebuilds the structure, therefore the maps of the graph will be
1.119 + /// reallocated automatically and the previous values will be lost.
1.120 void resize(int width, int height) {
1.121 Parent::notifier(Arc()).clear();
1.122 Parent::notifier(Edge()).clear();
1.123 @@ -609,42 +605,42 @@
1.124 return Parent::operator()(i, j);
1.125 }
1.126
1.127 - /// \brief Gives back the column index of the node.
1.128 + /// \brief The column index of the node.
1.129 ///
1.130 /// Gives back the column index of the node.
1.131 int col(Node n) const {
1.132 return Parent::col(n);
1.133 }
1.134
1.135 - /// \brief Gives back the row index of the node.
1.136 + /// \brief The row index of the node.
1.137 ///
1.138 /// Gives back the row index of the node.
1.139 int row(Node n) const {
1.140 return Parent::row(n);
1.141 }
1.142
1.143 - /// \brief Gives back the position of the node.
1.144 + /// \brief The position of the node.
1.145 ///
1.146 /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
1.147 dim2::Point<int> pos(Node n) const {
1.148 return Parent::pos(n);
1.149 }
1.150
1.151 - /// \brief Gives back the number of the columns.
1.152 + /// \brief The number of the columns.
1.153 ///
1.154 /// Gives back the number of the columns.
1.155 int width() const {
1.156 return Parent::width();
1.157 }
1.158
1.159 - /// \brief Gives back the number of the rows.
1.160 + /// \brief The number of the rows.
1.161 ///
1.162 /// Gives back the number of the rows.
1.163 int height() const {
1.164 return Parent::height();
1.165 }
1.166
1.167 - /// \brief Gives back the arc goes right from the node.
1.168 + /// \brief The arc goes right from the node.
1.169 ///
1.170 /// Gives back the arc goes right from the node. If there is not
1.171 /// outgoing arc then it gives back INVALID.
1.172 @@ -652,7 +648,7 @@
1.173 return Parent::right(n);
1.174 }
1.175
1.176 - /// \brief Gives back the arc goes left from the node.
1.177 + /// \brief The arc goes left from the node.
1.178 ///
1.179 /// Gives back the arc goes left from the node. If there is not
1.180 /// outgoing arc then it gives back INVALID.
1.181 @@ -660,7 +656,7 @@
1.182 return Parent::left(n);
1.183 }
1.184
1.185 - /// \brief Gives back the arc goes up from the node.
1.186 + /// \brief The arc goes up from the node.
1.187 ///
1.188 /// Gives back the arc goes up from the node. If there is not
1.189 /// outgoing arc then it gives back INVALID.
1.190 @@ -668,7 +664,7 @@
1.191 return Parent::up(n);
1.192 }
1.193
1.194 - /// \brief Gives back the arc goes down from the node.
1.195 + /// \brief The arc goes down from the node.
1.196 ///
1.197 /// Gives back the arc goes down from the node. If there is not
1.198 /// outgoing arc then it gives back INVALID.