kpeter@346: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@346:  *
kpeter@346:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@346:  *
kpeter@346:  * Copyright (C) 2003-2008
kpeter@346:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@346:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@346:  *
kpeter@346:  * Permission to use, modify and distribute this software is granted
kpeter@346:  * provided that this copyright notice appears in all copies. For
kpeter@346:  * precise terms see the accompanying LICENSE file.
kpeter@346:  *
kpeter@346:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@346:  * express or implied, and with no claim as to its suitability for any
kpeter@346:  * purpose.
kpeter@346:  *
kpeter@346:  */
kpeter@346: 
kpeter@346: #ifndef GRID_GRAPH_H
kpeter@346: #define GRID_GRAPH_H
kpeter@346: 
kpeter@346: #include <lemon/core.h>
deba@347: #include <lemon/bits/graph_extender.h>
deba@347: #include <lemon/dim2.h>
kpeter@346: #include <lemon/assert.h>
kpeter@346: 
kpeter@346: ///\ingroup graphs
kpeter@346: ///\file
kpeter@346: ///\brief GridGraph class.
kpeter@346: 
kpeter@346: namespace lemon {
kpeter@346: 
kpeter@346:   class GridGraphBase {
kpeter@346: 
kpeter@346:   public:
kpeter@346: 
kpeter@346:     typedef GridGraphBase Graph;
kpeter@346: 
kpeter@346:     class Node;
deba@347:     class Edge;
kpeter@346:     class Arc;
kpeter@346: 
kpeter@346:   public:
kpeter@346: 
kpeter@346:     GridGraphBase() {}
kpeter@346: 
kpeter@346:   protected:
kpeter@346: 
deba@347:     void construct(int width, int height) {
deba@347:        _width = width; _height = height;
deba@347:       _node_num = width * height;
deba@347:       _edge_num = 2 * _node_num - width - height;
deba@347:       _edge_limit = _node_num - _width;
kpeter@346:     }
kpeter@346: 
kpeter@346:   public:
kpeter@346: 
kpeter@346:     Node operator()(int i, int j) const {
deba@347:       LEMON_DEBUG(0 <= i && i < _width &&
deba@347:                   0 <= j  && j < _height, "Index out of range");
kpeter@346:       return Node(i + j * _width);
kpeter@346:     }
kpeter@346: 
deba@347:     int col(Node n) const {
deba@347:       return n._id % _width;
kpeter@346:     }
kpeter@346: 
deba@347:     int row(Node n) const {
deba@347:       return n._id / _width;
deba@347:     }
deba@347: 
deba@347:     dim2::Point<int> pos(Node n) const {
deba@347:       return dim2::Point<int>(col(n), row(n));
kpeter@346:     }
kpeter@346: 
kpeter@346:     int width() const {
kpeter@346:       return _width;
kpeter@346:     }
kpeter@346: 
kpeter@346:     int height() const {
kpeter@346:       return _height;
kpeter@346:     }
kpeter@346: 
kpeter@346:     typedef True NodeNumTag;
kpeter@372:     typedef True EdgeNumTag;
kpeter@346:     typedef True ArcNumTag;
kpeter@346: 
deba@347:     int nodeNum() const { return _node_num; }
deba@347:     int edgeNum() const { return _edge_num; }
deba@347:     int arcNum() const { return 2 * _edge_num; }
kpeter@346: 
deba@347:     Node u(Edge edge) const {
deba@347:       if (edge._id < _edge_limit) {
deba@347:         return edge._id;
kpeter@346:       } else {
deba@347:         return (edge._id - _edge_limit) % (_width - 1) +
deba@347:           (edge._id - _edge_limit) / (_width - 1) * _width;
kpeter@346:       }
kpeter@346:     }
kpeter@346: 
deba@347:     Node v(Edge edge) const {
deba@347:       if (edge._id < _edge_limit) {
deba@347:         return edge._id + _width;
kpeter@346:       } else {
deba@347:         return (edge._id - _edge_limit) % (_width - 1) +
deba@347:           (edge._id - _edge_limit) / (_width - 1) * _width + 1;
kpeter@346:       }
kpeter@346:     }
kpeter@346: 
deba@347:     Node source(Arc arc) const {
deba@347:       return (arc._id & 1) == 1 ? u(arc) : v(arc);
deba@347:     }
deba@347: 
deba@347:     Node target(Arc arc) const {
deba@347:       return (arc._id & 1) == 1 ? v(arc) : u(arc);
deba@347:     }
deba@347: 
deba@347:     static int id(Node node) { return node._id; }
deba@347:     static int id(Edge edge) { return edge._id; }
deba@347:     static int id(Arc arc) { return arc._id; }
deba@347: 
deba@347:     int maxNodeId() const { return _node_num - 1; }
deba@347:     int maxEdgeId() const { return _edge_num - 1; }
deba@347:     int maxArcId() const { return 2 * _edge_num - 1; }
kpeter@346: 
kpeter@346:     static Node nodeFromId(int id) { return Node(id);}
deba@347:     static Edge edgeFromId(int id) { return Edge(id);}
kpeter@346:     static Arc arcFromId(int id) { return Arc(id);}
kpeter@346: 
deba@347:     typedef True FindEdgeTag;
kpeter@372:     typedef True FindArcTag;
deba@347: 
deba@347:     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
deba@347:       if (prev != INVALID) return INVALID;
deba@347:       if (v._id > u._id) {
deba@347:         if (v._id - u._id == _width)
deba@347:           return Edge(u._id);
deba@347:         if (v._id - u._id == 1 && u._id % _width < _width - 1) {
deba@347:           return Edge(u._id / _width * (_width - 1) +
deba@347:                       u._id % _width + _edge_limit);
deba@347:         }
deba@347:       } else {
deba@347:         if (u._id - v._id == _width)
deba@347:           return Edge(v._id);
deba@347:         if (u._id - v._id == 1 && v._id % _width < _width - 1) {
deba@347:           return Edge(v._id / _width * (_width - 1) +
deba@347:                       v._id % _width + _edge_limit);
deba@347:         }
deba@347:       }
deba@347:       return INVALID;
deba@347:     }
kpeter@346: 
kpeter@346:     Arc findArc(Node u, Node v, Arc prev = INVALID) const {
kpeter@346:       if (prev != INVALID) return INVALID;
deba@347:       if (v._id > u._id) {
deba@347:         if (v._id - u._id == _width)
deba@347:           return Arc((u._id << 1) | 1);
deba@347:         if (v._id - u._id == 1 && u._id % _width < _width - 1) {
deba@347:           return Arc(((u._id / _width * (_width - 1) +
deba@347:                        u._id % _width + _edge_limit) << 1) | 1);
deba@347:         }
deba@347:       } else {
deba@347:         if (u._id - v._id == _width)
deba@347:           return Arc(v._id << 1);
deba@347:         if (u._id - v._id == 1 && v._id % _width < _width - 1) {
deba@347:           return Arc((v._id / _width * (_width - 1) +
deba@347:                        v._id % _width + _edge_limit) << 1);
deba@347:         }
kpeter@346:       }
kpeter@346:       return INVALID;
kpeter@346:     }
kpeter@346: 
kpeter@346:     class Node {
kpeter@346:       friend class GridGraphBase;
kpeter@346: 
kpeter@346:     protected:
deba@347:       int _id;
deba@347:       Node(int id) : _id(id) {}
kpeter@346:     public:
kpeter@346:       Node() {}
deba@347:       Node (Invalid) : _id(-1) {}
deba@347:       bool operator==(const Node node) const {return _id == node._id;}
deba@347:       bool operator!=(const Node node) const {return _id != node._id;}
deba@347:       bool operator<(const Node node) const {return _id < node._id;}
deba@347:     };
deba@347: 
deba@347:     class Edge {
deba@347:       friend class GridGraphBase;
kpeter@348:       friend class Arc;
deba@347: 
deba@347:     protected:
deba@347:       int _id;
deba@347: 
deba@347:       Edge(int id) : _id(id) {}
deba@347: 
deba@347:     public:
deba@347:       Edge() {}
deba@347:       Edge (Invalid) : _id(-1) {}
deba@347:       bool operator==(const Edge edge) const {return _id == edge._id;}
deba@347:       bool operator!=(const Edge edge) const {return _id != edge._id;}
deba@347:       bool operator<(const Edge edge) const {return _id < edge._id;}
kpeter@346:     };
kpeter@346: 
kpeter@346:     class Arc {
kpeter@346:       friend class GridGraphBase;
kpeter@346: 
kpeter@346:     protected:
deba@347:       int _id;
deba@347: 
deba@347:       Arc(int id) : _id(id) {}
deba@347: 
kpeter@346:     public:
kpeter@346:       Arc() {}
deba@347:       Arc (Invalid) : _id(-1) {}
deba@347:       operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
deba@347:       bool operator==(const Arc arc) const {return _id == arc._id;}
deba@347:       bool operator!=(const Arc arc) const {return _id != arc._id;}
deba@347:       bool operator<(const Arc arc) const {return _id < arc._id;}
kpeter@346:     };
kpeter@346: 
deba@347:     static bool direction(Arc arc) {
deba@347:       return (arc._id & 1) == 1;
deba@347:     }
deba@347: 
deba@347:     static Arc direct(Edge edge, bool dir) {
deba@347:       return Arc((edge._id << 1) | (dir ? 1 : 0));
deba@347:     }
deba@347: 
kpeter@346:     void first(Node& node) const {
deba@347:       node._id = _node_num - 1;
kpeter@346:     }
kpeter@346: 
kpeter@346:     static void next(Node& node) {
deba@347:       --node._id;
deba@347:     }
deba@347: 
deba@347:     void first(Edge& edge) const {
deba@347:       edge._id = _edge_num - 1;
deba@347:     }
deba@347: 
deba@347:     static void next(Edge& edge) {
deba@347:       --edge._id;
kpeter@346:     }
kpeter@346: 
kpeter@346:     void first(Arc& arc) const {
deba@347:       arc._id = 2 * _edge_num - 1;
kpeter@346:     }
kpeter@346: 
kpeter@346:     static void next(Arc& arc) {
deba@347:       --arc._id;
kpeter@346:     }
kpeter@346: 
kpeter@346:     void firstOut(Arc& arc, const Node& node) const {
deba@347:       if (node._id % _width < _width - 1) {
deba@347:         arc._id = (_edge_limit + node._id % _width +
deba@347:                    (node._id / _width) * (_width - 1)) << 1 | 1;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id < _node_num - _width) {
deba@347:         arc._id = node._id << 1 | 1;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id % _width > 0) {
deba@347:         arc._id = (_edge_limit + node._id % _width +
deba@347:                    (node._id / _width) * (_width - 1) - 1) << 1;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id >= _width) {
deba@347:         arc._id = (node._id - _width) << 1;
deba@347:         return;
deba@347:       }
deba@347:       arc._id = -1;
deba@347:     }
deba@347: 
deba@347:     void nextOut(Arc& arc) const {
deba@347:       int nid = arc._id >> 1;
deba@347:       if ((arc._id & 1) == 1) {
deba@347:         if (nid >= _edge_limit) {
deba@347:           nid = (nid - _edge_limit) % (_width - 1) +
deba@347:             (nid - _edge_limit) / (_width - 1) * _width;
deba@347:           if (nid < _node_num - _width) {
deba@347:             arc._id = nid << 1 | 1;
deba@347:             return;
deba@347:           }
deba@347:         }
deba@347:         if (nid % _width > 0) {
deba@347:           arc._id = (_edge_limit + nid % _width +
deba@347:                      (nid / _width) * (_width - 1) - 1) << 1;
deba@347:           return;
deba@347:         }
deba@347:         if (nid >= _width) {
deba@347:           arc._id = (nid - _width) << 1;
deba@347:           return;
deba@347:         }
kpeter@346:       } else {
deba@347:         if (nid >= _edge_limit) {
deba@347:           nid = (nid - _edge_limit) % (_width - 1) +
deba@347:             (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@347:           if (nid >= _width) {
deba@347:             arc._id = (nid - _width) << 1;
deba@347:             return;
deba@347:           }
deba@347:         }
deba@347:       }
deba@347:       arc._id = -1;
deba@347:     }
deba@347: 
deba@347:     void firstIn(Arc& arc, const Node& node) const {
deba@347:       if (node._id % _width < _width - 1) {
deba@347:         arc._id = (_edge_limit + node._id % _width +
deba@347:                    (node._id / _width) * (_width - 1)) << 1;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id < _node_num - _width) {
deba@347:         arc._id = node._id << 1;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id % _width > 0) {
deba@347:         arc._id = (_edge_limit + node._id % _width +
deba@347:                    (node._id / _width) * (_width - 1) - 1) << 1 | 1;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id >= _width) {
deba@347:         arc._id = (node._id - _width) << 1 | 1;
deba@347:         return;
deba@347:       }
deba@347:       arc._id = -1;
deba@347:     }
deba@347: 
deba@347:     void nextIn(Arc& arc) const {
deba@347:       int nid = arc._id >> 1;
deba@347:       if ((arc._id & 1) == 0) {
deba@347:         if (nid >= _edge_limit) {
deba@347:           nid = (nid - _edge_limit) % (_width - 1) +
deba@347:             (nid - _edge_limit) / (_width - 1) * _width;
deba@347:           if (nid < _node_num - _width) {
deba@347:             arc._id = nid << 1;
deba@347:             return;
deba@347:           }
deba@347:         }
deba@347:         if (nid % _width > 0) {
deba@347:           arc._id = (_edge_limit + nid % _width +
deba@347:                      (nid / _width) * (_width - 1) - 1) << 1 | 1;
deba@347:           return;
deba@347:         }
deba@347:         if (nid >= _width) {
deba@347:           arc._id = (nid - _width) << 1 | 1;
deba@347:           return;
deba@347:         }
deba@347:       } else {
deba@347:         if (nid >= _edge_limit) {
deba@347:           nid = (nid - _edge_limit) % (_width - 1) +
deba@347:             (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@347:           if (nid >= _width) {
deba@347:             arc._id = (nid - _width) << 1 | 1;
deba@347:             return;
deba@347:           }
deba@347:         }
deba@347:       }
deba@347:       arc._id = -1;
deba@347:     }
deba@347: 
deba@347:     void firstInc(Edge& edge, bool& dir, const Node& node) const {
deba@347:       if (node._id % _width < _width - 1) {
deba@347:         edge._id = _edge_limit + node._id % _width +
deba@347:           (node._id / _width) * (_width - 1);
deba@347:         dir = true;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id < _node_num - _width) {
deba@347:         edge._id = node._id;
deba@347:         dir = true;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id % _width > 0) {
deba@347:         edge._id = _edge_limit + node._id % _width +
deba@347:           (node._id / _width) * (_width - 1) - 1;
deba@347:         dir = false;
deba@347:         return;
deba@347:       }
deba@347:       if (node._id >= _width) {
deba@347:         edge._id = node._id - _width;
deba@347:         dir = false;
deba@347:         return;
deba@347:       }
deba@347:       edge._id = -1;
deba@347:       dir = true;
deba@347:     }
deba@347: 
deba@347:     void nextInc(Edge& edge, bool& dir) const {
deba@347:       int nid = edge._id;
deba@347:       if (dir) {
deba@347:         if (nid >= _edge_limit) {
deba@347:           nid = (nid - _edge_limit) % (_width - 1) +
deba@347:             (nid - _edge_limit) / (_width - 1) * _width;
deba@347:           if (nid < _node_num - _width) {
deba@347:             edge._id = nid;
deba@347:             return;
deba@347:           }
deba@347:         }
deba@347:         if (nid % _width > 0) {
deba@347:           edge._id = _edge_limit + nid % _width +
deba@347:             (nid / _width) * (_width - 1) - 1;
deba@347:           dir = false;
deba@347:           return;
deba@347:         }
deba@347:         if (nid >= _width) {
deba@347:           edge._id = nid - _width;
deba@347:           dir = false;
deba@347:           return;
deba@347:         }
deba@347:       } else {
deba@347:         if (nid >= _edge_limit) {
deba@347:           nid = (nid - _edge_limit) % (_width - 1) +
deba@347:             (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@347:           if (nid >= _width) {
deba@347:             edge._id = nid - _width;
deba@347:             return;
deba@347:           }
deba@347:         }
deba@347:       }
deba@347:       edge._id = -1;
deba@347:       dir = true;
deba@347:     }
deba@347: 
deba@347:     Arc right(Node n) const {
deba@347:       if (n._id % _width < _width - 1) {
deba@347:         return Arc(((_edge_limit + n._id % _width +
deba@347:                     (n._id / _width) * (_width - 1)) << 1) | 1);
deba@347:       } else {
deba@347:         return INVALID;
kpeter@346:       }
kpeter@346:     }
kpeter@346: 
deba@347:     Arc left(Node n) const {
deba@347:       if (n._id % _width > 0) {
deba@347:         return Arc((_edge_limit + n._id % _width +
deba@347:                      (n._id / _width) * (_width - 1) - 1) << 1);
kpeter@346:       } else {
deba@347:         return INVALID;
kpeter@346:       }
kpeter@346:     }
kpeter@346: 
deba@347:     Arc up(Node n) const {
deba@347:       if (n._id < _edge_limit) {
deba@347:         return Arc((n._id << 1) | 1);
kpeter@346:       } else {
deba@347:         return INVALID;
kpeter@346:       }
kpeter@346:     }
kpeter@346: 
deba@347:     Arc down(Node n) const {
deba@347:       if (n._id >= _width) {
deba@347:         return Arc((n._id - _width) << 1);
kpeter@346:       } else {
deba@347:         return INVALID;
kpeter@346:       }
kpeter@346:     }
kpeter@346: 
kpeter@346:   private:
kpeter@346:     int _width, _height;
deba@347:     int _node_num, _edge_num;
deba@347:     int _edge_limit;
kpeter@346:   };
kpeter@346: 
deba@347: 
deba@347:   typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
kpeter@346: 
kpeter@346:   /// \ingroup graphs
kpeter@346:   ///
kpeter@346:   /// \brief Grid graph class
kpeter@346:   ///
kpeter@346:   /// This class implements a special graph type. The nodes of the
deba@347:   /// graph can be indexed by two integer \c (i,j) value where \c i is
deba@347:   /// in the \c [0..width()-1] range and j is in the \c
deba@347:   /// [0..height()-1] range.  Two nodes are connected in the graph if
deba@347:   /// the indexes differ exactly on one position and exactly one is
kpeter@348:   /// the difference. The nodes of the graph can be indexed by position
kpeter@348:   /// with the \c operator()() function. The positions of the nodes can be
deba@347:   /// get with \c pos(), \c col() and \c row() members. The outgoing
deba@347:   /// arcs can be retrieved with the \c right(), \c up(), \c left()
deba@347:   /// and \c down() functions, where the bottom-left corner is the
deba@347:   /// origin.
kpeter@346:   ///
kpeter@346:   /// \image html grid_graph.png
deba@350:   /// \image latex grid_graph.eps "Grid graph" width=\textwidth
kpeter@346:   ///
deba@347:   /// A short example about the basic usage:
kpeter@346:   ///\code
deba@347:   /// GridGraph graph(rows, cols);
deba@347:   /// GridGraph::NodeMap<int> val(graph);
deba@347:   /// for (int i = 0; i < graph.width(); ++i) {
deba@347:   ///   for (int j = 0; j < graph.height(); ++j) {
deba@347:   ///     val[graph(i, j)] = i + j;
kpeter@346:   ///   }
kpeter@346:   /// }
kpeter@346:   ///\endcode
kpeter@346:   ///
kpeter@348:   /// This graph type is fully conform to the \ref concepts::Graph
deba@347:   /// "Graph" concept, and it also has an important extra feature
kpeter@348:   /// that its maps are real \ref concepts::ReferenceMap
kpeter@348:   /// "reference map"s.
kpeter@346:   class GridGraph : public ExtendedGridGraphBase {
kpeter@346:   public:
kpeter@346: 
kpeter@346:     typedef ExtendedGridGraphBase Parent;
kpeter@346: 
kpeter@346:     /// \brief Map to get the indices of the nodes as dim2::Point<int>.
kpeter@346:     ///
kpeter@346:     /// Map to get the indices of the nodes as dim2::Point<int>.
kpeter@346:     class IndexMap {
kpeter@346:     public:
deba@347:       /// \brief The key type of the map
kpeter@346:       typedef GridGraph::Node Key;
deba@347:       /// \brief The value type of the map
kpeter@346:       typedef dim2::Point<int> Value;
kpeter@346: 
deba@347:       /// \brief Constructor
deba@347:       ///
kpeter@346:       /// Constructor
kpeter@346:       IndexMap(const GridGraph& graph) : _graph(graph) {}
kpeter@346: 
deba@347:       /// \brief The subscript operator
deba@347:       ///
deba@347:       /// The subscript operator.
deba@347:       Value operator[](Key key) const {
deba@347:         return _graph.pos(key);
deba@347:       }
deba@347: 
deba@347:     private:
deba@347:       const GridGraph& _graph;
deba@347:     };
deba@347: 
deba@347:     /// \brief Map to get the column of the nodes.
deba@347:     ///
deba@347:     /// Map to get the column of the nodes.
deba@347:     class ColMap {
deba@347:     public:
deba@347:       /// \brief The key type of the map
deba@347:       typedef GridGraph::Node Key;
deba@347:       /// \brief The value type of the map
deba@347:       typedef int Value;
deba@347: 
deba@347:       /// \brief Constructor
deba@347:       ///
deba@347:       /// Constructor
deba@347:       ColMap(const GridGraph& graph) : _graph(graph) {}
deba@347: 
deba@347:       /// \brief The subscript operator
deba@347:       ///
deba@347:       /// The subscript operator.
deba@347:       Value operator[](Key key) const {
deba@347:         return _graph.col(key);
kpeter@346:       }
kpeter@346: 
kpeter@346:     private:
kpeter@346:       const GridGraph& _graph;
kpeter@346:     };
kpeter@346: 
kpeter@346:     /// \brief Map to get the row of the nodes.
kpeter@346:     ///
kpeter@346:     /// Map to get the row of the nodes.
kpeter@346:     class RowMap {
kpeter@346:     public:
deba@347:       /// \brief The key type of the map
kpeter@346:       typedef GridGraph::Node Key;
deba@347:       /// \brief The value type of the map
kpeter@346:       typedef int Value;
kpeter@346: 
deba@347:       /// \brief Constructor
deba@347:       ///
kpeter@346:       /// Constructor
kpeter@346:       RowMap(const GridGraph& graph) : _graph(graph) {}
kpeter@346: 
deba@347:       /// \brief The subscript operator
deba@347:       ///
deba@347:       /// The subscript operator.
deba@347:       Value operator[](Key key) const {
kpeter@346:         return _graph.row(key);
kpeter@346:       }
kpeter@346: 
kpeter@346:     private:
kpeter@346:       const GridGraph& _graph;
kpeter@346:     };
kpeter@346: 
kpeter@346:     /// \brief Constructor
kpeter@346:     ///
deba@347:     /// Construct a grid graph with given size.
kpeter@346:     GridGraph(int width, int height) { construct(width, height); }
kpeter@346: 
kpeter@346:     /// \brief Resize the graph
kpeter@346:     ///
deba@347:     /// Resize the graph. The function will fully destroy and rebuild
deba@347:     /// the graph.  This cause that the maps of the graph will
deba@347:     /// reallocated automatically and the previous values will be
deba@347:     /// lost.
kpeter@346:     void resize(int width, int height) {
kpeter@346:       Parent::notifier(Arc()).clear();
kpeter@346:       Parent::notifier(Edge()).clear();
kpeter@346:       Parent::notifier(Node()).clear();
kpeter@346:       construct(width, height);
kpeter@346:       Parent::notifier(Node()).build();
kpeter@346:       Parent::notifier(Edge()).build();
kpeter@346:       Parent::notifier(Arc()).build();
kpeter@346:     }
kpeter@346: 
kpeter@346:     /// \brief The node on the given position.
kpeter@346:     ///
kpeter@346:     /// Gives back the node on the given position.
kpeter@346:     Node operator()(int i, int j) const {
kpeter@346:       return Parent::operator()(i, j);
kpeter@346:     }
kpeter@346: 
deba@347:     /// \brief Gives back the column index of the node.
deba@347:     ///
deba@347:     /// Gives back the column index of the node.
deba@347:     int col(Node n) const {
deba@347:       return Parent::col(n);
deba@347:     }
deba@347: 
kpeter@346:     /// \brief Gives back the row index of the node.
kpeter@346:     ///
kpeter@346:     /// Gives back the row index of the node.
kpeter@346:     int row(Node n) const {
kpeter@346:       return Parent::row(n);
kpeter@346:     }
kpeter@346: 
deba@347:     /// \brief Gives back the position of the node.
kpeter@346:     ///
deba@347:     /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
deba@347:     dim2::Point<int> pos(Node n) const {
deba@347:       return Parent::pos(n);
kpeter@346:     }
kpeter@346: 
deba@347:     /// \brief Gives back the number of the columns.
kpeter@346:     ///
deba@347:     /// Gives back the number of the columns.
kpeter@346:     int width() const {
kpeter@346:       return Parent::width();
kpeter@346:     }
kpeter@346: 
deba@347:     /// \brief Gives back the number of the rows.
kpeter@346:     ///
deba@347:     /// Gives back the number of the rows.
kpeter@346:     int height() const {
kpeter@346:       return Parent::height();
kpeter@346:     }
kpeter@346: 
deba@347:     /// \brief Gives back the arc goes right from the node.
deba@347:     ///
deba@347:     /// Gives back the arc goes right from the node. If there is not
deba@347:     /// outgoing arc then it gives back INVALID.
deba@347:     Arc right(Node n) const {
deba@347:       return Parent::right(n);
deba@347:     }
deba@347: 
deba@347:     /// \brief Gives back the arc goes left from the node.
deba@347:     ///
deba@347:     /// Gives back the arc goes left from the node. If there is not
deba@347:     /// outgoing arc then it gives back INVALID.
deba@347:     Arc left(Node n) const {
deba@347:       return Parent::left(n);
deba@347:     }
deba@347: 
deba@347:     /// \brief Gives back the arc goes up from the node.
deba@347:     ///
deba@347:     /// Gives back the arc goes up from the node. If there is not
deba@347:     /// outgoing arc then it gives back INVALID.
deba@347:     Arc up(Node n) const {
deba@347:       return Parent::up(n);
deba@347:     }
deba@347: 
kpeter@346:     /// \brief Gives back the arc goes down from the node.
kpeter@346:     ///
kpeter@346:     /// Gives back the arc goes down from the node. If there is not
deba@347:     /// outgoing arc then it gives back INVALID.
kpeter@346:     Arc down(Node n) const {
deba@347:       return Parent::down(n);
kpeter@346:     }
kpeter@346: 
deba@347:     /// \brief Index map of the grid graph
kpeter@346:     ///
deba@347:     /// Just returns an IndexMap for the grid graph.
deba@347:     IndexMap indexMap() const {
deba@347:       return IndexMap(*this);
kpeter@346:     }
kpeter@346: 
deba@347:     /// \brief Row map of the grid graph
kpeter@346:     ///
deba@347:     /// Just returns a RowMap for the grid graph.
deba@347:     RowMap rowMap() const {
deba@347:       return RowMap(*this);
kpeter@346:     }
kpeter@346: 
deba@347:     /// \brief Column map of the grid graph
kpeter@346:     ///
deba@347:     /// Just returns a ColMap for the grid graph.
deba@347:     ColMap colMap() const {
deba@347:       return ColMap(*this);
kpeter@346:     }
kpeter@346: 
deba@347:   };
kpeter@346: 
kpeter@346: }
deba@347: #endif