RhodeCode

    void nextInc(Edge& edge, bool& dir) const {

      int nid = edge._id;

      if (dir) {

        if (nid >= _edge_limit) {

          nid = (nid - _edge_limit) % (_width - 1) +

            (nid - _edge_limit) / (_width - 1) * _width;

          if (nid < _node_num - _width) {

            edge._id = nid;

            return;

          }

        }

        if (nid % _width > 0) {

          edge._id = _edge_limit + nid % _width +

            (nid / _width) * (_width - 1) - 1;

          dir = false;

          return;

        }

        if (nid >= _width) {

          edge._id = nid - _width;

          dir = false;

          return;

        }

      } else {

        if (nid >= _edge_limit) {

          nid = (nid - _edge_limit) % (_width - 1) +

            (nid - _edge_limit) / (_width - 1) * _width + 1;

          if (nid >= _width) {

            edge._id = nid - _width;

            return;

          }

        }

      }

      edge._id = -1;

      dir = true;

    }

    Arc right(Node n) const {

      if (n._id % _width < _width - 1) {

        return Arc(((_edge_limit + n._id % _width +

                    (n._id / _width) * (_width - 1)) << 1) | 1);

      } else {

        return INVALID;

      }

    }

    Arc left(Node n) const {

      if (n._id % _width > 0) {

        return Arc((_edge_limit + n._id % _width +

                     (n._id / _width) * (_width - 1) - 1) << 1);

      } else {

        return INVALID;

      }

    }

    Arc up(Node n) const {

      if (n._id < _edge_limit) {

        return Arc((n._id << 1) | 1);

      } else {

        return INVALID;

      }

    }

    Arc down(Node n) const {

      if (n._id >= _width) {

        return Arc((n._id - _width) << 1);

      } else {

        return INVALID;

      }

    }

  private:

    int _width, _height;

    int _node_num, _edge_num;

    int _edge_limit;

  };

  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;

  /// \ingroup graphs

  ///

  /// \brief Grid graph class

  ///

  /// This class implements a special graph type. The nodes of the

  /// graph can be indexed by two integer \c (i,j) value where \c i is

  /// in the \c [0..width()-1] range and j is in the \c

  /// [0..height()-1] range.  Two nodes are connected in the graph if

  /// the indexes differ exactly on one position and exactly one is

  /// the difference. The nodes of the graph can be indexed by position

  /// with the \c operator()() function. The positions of the nodes can be

  /// get with \c pos(), \c col() and \c row() members. The outgoing

  /// arcs can be retrieved with the \c right(), \c up(), \c left()

  /// and \c down() functions, where the bottom-left corner is the

  /// origin.

  ///

  /// \image html grid_graph.png

  ///

  /// A short example about the basic usage:

  ///\code

  /// GridGraph graph(rows, cols);

  /// GridGraph::NodeMap<int> val(graph);

  /// for (int i = 0; i < graph.width(); ++i) {

  ///   for (int j = 0; j < graph.height(); ++j) {

  ///     val[graph(i, j)] = i + j;

  ///   }

  /// }

  ///\endcode

  ///

  /// This graph type is fully conform to the \ref concepts::Graph

  /// "Graph" concept, and it also has an important extra feature

  /// that its maps are real \ref concepts::ReferenceMap

  /// "reference map"s.

  class GridGraph : public ExtendedGridGraphBase {

  public:

    typedef ExtendedGridGraphBase Parent;

    /// \brief Map to get the indices of the nodes as dim2::Point<int>.

    ///

    /// Map to get the indices of the nodes as dim2::Point<int>.

    class IndexMap {

    public:

      /// \brief The key type of the map

      typedef GridGraph::Node Key;

      /// \brief The value type of the map

      typedef dim2::Point<int> Value;

      /// \brief Constructor

      ///

      /// Constructor

      IndexMap(const GridGraph& graph) : _graph(graph) {}

      /// \brief The subscript operator

      ///

      /// The subscript operator.

      Value operator[](Key key) const {

        return _graph.pos(key);

      }

    private:

      const GridGraph& _graph;

    };

    /// \brief Map to get the column of the nodes.

    ///

    /// Map to get the column of the nodes.

    class ColMap {

    public:

      /// \brief The key type of the map

      typedef GridGraph::Node Key;

      /// \brief The value type of the map

      typedef int Value;

      /// \brief Constructor

      ///

      /// Constructor

      ColMap(const GridGraph& graph) : _graph(graph) {}

      /// \brief The subscript operator

      ///

      /// The subscript operator.

      Value operator[](Key key) const {

        return _graph.col(key);

      }

    private:

      const GridGraph& _graph;

    };

    /// \brief Map to get the row of the nodes.

    ///

    /// Map to get the row of the nodes.

    class RowMap {

    public:

      /// \brief The key type of the map

      typedef GridGraph::Node Key;

      /// \brief The value type of the map

      typedef int Value;

      /// \brief Constructor

      ///

      /// Constructor

      RowMap(const GridGraph& graph) : _graph(graph) {}

      /// \brief The subscript operator

      ///

      /// The subscript operator.

      Value operator[](Key key) const {

        return _graph.row(key);

      }

    private: