diff -r a24939ee343c -r 590c1b663a27 lemon/grid_ugraph.h --- a/lemon/grid_ugraph.h Fri Sep 29 11:23:54 2006 +0000 +++ b/lemon/grid_ugraph.h Fri Sep 29 11:25:27 2006 +0000 @@ -34,13 +34,6 @@ namespace lemon { - /// \brief Base graph for GridUGraph. - /// - /// Base graph for grid graph. It describes some member functions - /// which can be used in the GridUGraph. - /// - /// \warning Always use the GridUGraph instead of this. - /// \see GridUGraph class GridUGraphBase { public: @@ -56,19 +49,12 @@ protected: - /// \brief Creates a grid graph with the given size. - /// - /// Creates a grid graph with the given size. void construct(int width, int height) { _height = height; _width = width; _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; _edgeLimit = _nodeNum - width; } - /// \brief Gives back the edge goes down from the node. - /// - /// Gives back the edge goes down from the node. If there is not - /// outgoing edge then it gives back INVALID. Edge _down(Node n) const { if (n.id < _nodeNum - _width) { return Edge(n.id); @@ -77,10 +63,6 @@ } } - /// \brief Gives back the edge comes from up into the node. - /// - /// Gives back the edge comes from up into the node. If there is not - /// incoming edge then it gives back INVALID. Edge _up(Node n) const { if (n.id >= _width) { return Edge(n.id - _width); @@ -89,10 +71,6 @@ } } - /// \brief Gives back the edge goes right from the node. - /// - /// Gives back the edge goes right from the node. If there is not - /// outgoing edge then it gives back INVALID. Edge _right(Node n) const { if (n.id % _width < _width - 1) { return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1); @@ -101,10 +79,6 @@ } } - /// \brief Gives back the edge comes from left into the node. - /// - /// Gives back the edge comes left up into the node. If there is not - /// incoming edge then it gives back INVALID. Edge _left(Node n) const { if (n.id % _width > 0) { return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; @@ -123,39 +97,24 @@ }; - /// \brief The node on the given position. - /// - /// Gives back the node on the given position. Node operator()(int i, int j) const { LEMON_ASSERT(0 <= i && i < width() && 0 <= j && j < height(), IndexError()); return Node(i + j * _width); } - /// \brief Gives back the row index of the node. - /// - /// Gives back the row index of the node. int row(Node n) const { return n.id / _width; } - /// \brief Gives back the coloumn index of the node. - /// - /// Gives back the coloumn index of the node. int col(Node n) const { return n.id % _width; } - /// \brief Gives back the width of the graph. - /// - /// Gives back the width of the graph. int width() const { return _width; } - /// \brief Gives back the height of the graph. - /// - /// Gives back the height of the graph. int height() const { return _height; } @@ -163,25 +122,12 @@ typedef True NodeNumTag; typedef True EdgeNumTag; - ///Number of nodes. int nodeNum() const { return _nodeNum; } - ///Number of edges. int edgeNum() const { return _edgeNum; } - /// Maximum node ID. - - /// Maximum node ID. - ///\sa id(Node) int maxNodeId() const { return nodeNum() - 1; } - /// Maximum edge ID. - - /// Maximum edge ID. - ///\sa id(Edge) int maxEdgeId() const { return edgeNum() - 1; } - /// \brief Gives back the source node of an edge. - /// - /// Gives back the source node of an edge. Node source(Edge e) const { if (e.id < _edgeLimit) { return e.id; @@ -191,9 +137,6 @@ } } - /// \brief Gives back the target node of an edge. - /// - /// Gives back the target node of an edge. Node target(Edge e) const { if (e.id < _edgeLimit) { return e.id + _width; @@ -203,24 +146,7 @@ } } - /// Node ID. - - /// The ID of a valid Node is a nonnegative integer not greater than - /// \ref maxNodeId(). The range of the ID's is not surely continuous - /// and the greatest node ID can be actually less then \ref maxNodeId(). - /// - /// The ID of the \ref INVALID node is -1. - ///\return The ID of the node \c v. - static int id(Node v) { return v.id; } - /// Edge ID. - - /// The ID of a valid Edge is a nonnegative integer not greater than - /// \ref maxEdgeId(). The range of the ID's is not surely continuous - /// and the greatest edge ID can be actually less then \ref maxEdgeId(). - /// - /// The ID of the \ref INVALID edge is -1. - ///\return The ID of the edge \c e. static int id(Edge e) { return e.id; } static Node nodeFromId(int id) { return Node(id);} @@ -229,14 +155,6 @@ typedef True FindEdgeTag; - /// Finds an edge between two nodes. - - /// Finds an edge from node \c u to node \c v. - /// - /// If \c prev is \ref INVALID (this is the default value), then - /// It finds the first edge from \c u to \c v. Otherwise it looks for - /// the next edge from \c u to \c v after \c prev. - /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u, Node v, Edge prev = INVALID) const { if (prev != INVALID) return INVALID; if (v.id - u.id == _width) return Edge(u.id); @@ -360,6 +278,9 @@ /// Two nodes are connected in the graph if the indices differ only /// on one position and only one is the difference. /// + /// \image html grid_ugraph.png + /// \image latex grid_ugraph.eps "Grid graph" width=\textwidth + /// /// The graph can be indiced in the following way: ///\code /// GridUGraph graph(w, h); @@ -375,7 +296,6 @@ /// "Undirected Graph" concept. /// /// \author Balazs Dezso - /// \see GridUGraphBase class GridUGraph : public ExtendedGridUGraphBase { public: @@ -476,6 +396,41 @@ Parent::getNotifier(Edge()).build(); } + /// \brief The node on the given position. + /// + /// Gives back the node on the given position. + Node operator()(int i, int j) const { + return Parent::operator()(i, j); + } + + /// \brief Gives back the row index of the node. + /// + /// Gives back the row index of the node. + int row(Node n) const { + return Parent::row(n); + } + + /// \brief Gives back the coloumn index of the node. + /// + /// Gives back the coloumn index of the node. + int col(Node n) const { + return Parent::col(n); + } + + /// \brief Gives back the width of the graph. + /// + /// Gives back the width of the graph. + int width() const { + return Parent::width(); + } + + /// \brief Gives back the height of the graph. + /// + /// Gives back the height of the graph. + int height() const { + return Parent::height(); + } + /// \brief Gives back the edge goes down from the node. /// /// Gives back the edge goes down from the node. If there is not