RhodeCode

    Node u(Edge edge) const {

      if (edge._id < _edge_limit) {

        return edge._id;

      } else {

        return (edge._id - _edge_limit) % (_width - 1) +

          (edge._id - _edge_limit) / (_width - 1) * _width;

      }

    }

    Node v(Edge edge) const {

      if (edge._id < _edge_limit) {

        return edge._id + _width;

      } else {

        return (edge._id - _edge_limit) % (_width - 1) +

          (edge._id - _edge_limit) / (_width - 1) * _width + 1;

      }

    }

    Node source(Arc arc) const {

      return (arc._id & 1) == 1 ? u(arc) : v(arc);

    }

    Node target(Arc arc) const {

      return (arc._id & 1) == 1 ? v(arc) : u(arc);

    }

    static int id(Node node) { return node._id; }

    static int id(Edge edge) { return edge._id; }

    static int id(Arc arc) { return arc._id; }

    int maxNodeId() const { return _node_num - 1; }

    int maxEdgeId() const { return _edge_num - 1; }

    int maxArcId() const { return 2 * _edge_num - 1; }

    static Node nodeFromId(int id) { return Node(id);}

    static Edge edgeFromId(int id) { return Edge(id);}

    static Arc arcFromId(int id) { return Arc(id);}

    typedef True FindEdgeTag;

    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {

      if (prev != INVALID) return INVALID;

      if (v._id > u._id) {

        if (v._id - u._id == _width)

          return Edge(u._id);

        if (v._id - u._id == 1 && u._id % _width < _width - 1) {

          return Edge(u._id / _width * (_width - 1) +

                      u._id % _width + _edge_limit);

        }

      } else {

        if (u._id - v._id == _width)

          return Edge(v._id);

        if (u._id - v._id == 1 && v._id % _width < _width - 1) {

          return Edge(v._id / _width * (_width - 1) +

                      v._id % _width + _edge_limit);

        }

      }

      return INVALID;

    }

    Arc findArc(Node u, Node v, Arc prev = INVALID) const {

      if (prev != INVALID) return INVALID;

      if (v._id > u._id) {

        if (v._id - u._id == _width)

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

        if (v._id - u._id == 1 && u._id % _width < _width - 1) {

          return Arc(((u._id / _width * (_width - 1) +

                       u._id % _width + _edge_limit) << 1) | 1);

        }

      } else {

        if (u._id - v._id == _width)

          return Arc(v._id << 1);

        if (u._id - v._id == 1 && v._id % _width < _width - 1) {

          return Arc((v._id / _width * (_width - 1) +

                       v._id % _width + _edge_limit) << 1);

        }

      }

      return INVALID;

    }

    class Node {

      friend class GridGraphBase;

    protected:

      int _id;

      Node(int id) : _id(id) {}

    public:

      Node() {}

      Node (Invalid) : _id(-1) {}

      bool operator==(const Node node) const {return _id == node._id;}

      bool operator!=(const Node node) const {return _id != node._id;}

      bool operator<(const Node node) const {return _id < node._id;}

    };

    class Edge {

      friend class GridGraphBase;

    protected:

      int _id;

      Edge(int id) : _id(id) {}

    public:

      Edge() {}

      Edge (Invalid) : _id(-1) {}

      bool operator==(const Edge edge) const {return _id == edge._id;}

      bool operator!=(const Edge edge) const {return _id != edge._id;}

      bool operator<(const Edge edge) const {return _id < edge._id;}

    };

    class Arc {

      friend class GridGraphBase;

    protected:

      int _id;

      Arc(int id) : _id(id) {}

    public:

      Arc() {}

      Arc (Invalid) : _id(-1) {}

      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }

      bool operator==(const Arc arc) const {return _id == arc._id;}

      bool operator!=(const Arc arc) const {return _id != arc._id;}

      bool operator<(const Arc arc) const {return _id < arc._id;}

    };

    static bool direction(Arc arc) {

      return (arc._id & 1) == 1;

    }

    static Arc direct(Edge edge, bool dir) {

      return Arc((edge._id << 1) | (dir ? 1 : 0));

    }

    void first(Node& node) const {

      node._id = _node_num - 1;

    }

    static void next(Node& node) {

      --node._id;

    }

    void first(Edge& edge) const {

      edge._id = _edge_num - 1;

    }

    static void next(Edge& edge) {

      --edge._id;

    }

    void first(Arc& arc) const {

      arc._id = 2 * _edge_num - 1;

    }

    static void next(Arc& arc) {

      --arc._id;

    }

    void firstOut(Arc& arc, const Node& node) const {

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

        arc._id = (_edge_limit + node._id % _width +

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

        return;

      }

      if (node._id < _node_num - _width) {

        arc._id = node._id << 1 | 1;

        return;

      }

      if (node._id % _width > 0) {

        arc._id = (_edge_limit + node._id % _width +

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

        return;

      }

      if (node._id >= _width) {

        arc._id = (node._id - _width) << 1;

        return;

      }

      arc._id = -1;

    }

    void nextOut(Arc& arc) const {

      int nid = arc._id >> 1;

      if ((arc._id & 1) == 1) {

        if (nid >= _edge_limit) {

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

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

          if (nid < _node_num - _width) {

            arc._id = nid << 1 | 1;

            return;

          }

        }

        edge._id = node._id - _width;

        dir = false;

        return;

      }

      edge._id = -1;

      dir = true;

    }

    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

  /// 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

  ///

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

  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:

      const GridGraph& _graph;

    };

    /// \brief Constructor

    ///

    /// Construct a grid graph with given size.

    GridGraph(int width, int height) { construct(width, height); }

    /// \brief Resize the graph

    ///

    /// Resize the graph. The function will fully destroy and rebuild

    /// the graph.  This cause that the maps of the graph will

    /// reallocated automatically and the previous values will be

    /// lost.

    void resize(int width, int height) {

      Parent::notifier(Arc()).clear();

  { // Checking graph components

    checkConcept<BaseGraphComponent, BaseGraphComponent >();

    checkConcept<IDableGraphComponent<>,

      IDableGraphComponent<> >();

    checkConcept<IterableGraphComponent<>,

      IterableGraphComponent<> >();

    checkConcept<MappableGraphComponent<>,

      MappableGraphComponent<> >();

  }

  { // Checking skeleton graph

    checkConcept<Graph, Graph>();

  }

  { // Checking ListGraph

    checkConcept<Graph, ListGraph>();

    checkConcept<AlterableGraphComponent<>, ListGraph>();

    checkConcept<ExtendableGraphComponent<>, ListGraph>();

    checkConcept<ClearableGraphComponent<>, ListGraph>();

    checkConcept<ErasableGraphComponent<>, ListGraph>();

  }

  { // Checking SmartGraph

    checkConcept<Graph, SmartGraph>();

    checkConcept<AlterableGraphComponent<>, SmartGraph>();

    checkConcept<ExtendableGraphComponent<>, SmartGraph>();

    checkConcept<ClearableGraphComponent<>, SmartGraph>();

  }

//  { // Checking FullGraph

//    checkConcept<Graph, FullGraph>();

//    checkGraphIterators<FullGraph>();

//  }

  { // Checking GridGraph

    checkConcept<Graph, GridGraph>();

  }

}

template <typename Graph>

void checkGraphValidity() {

  TEMPLATE_GRAPH_TYPEDEFS(Graph);

  Graph g;

  Node

    n1 = g.addNode(),

    n2 = g.addNode(),

    n3 = g.addNode();

  Edge

    e1 = g.addEdge(n1, n2),

    e2 = g.addEdge(n2, n3);

  check(g.valid(n1), "Wrong validity check");

  check(g.valid(e1), "Wrong validity check");

  check(g.valid(g.direct(e1, true)), "Wrong validity check");

  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");

  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

}

template <typename Graph>

void checkGraphValidityErase() {

  TEMPLATE_GRAPH_TYPEDEFS(Graph);

  Graph g;

  Node

    n1 = g.addNode(),

    n2 = g.addNode(),

    n3 = g.addNode();

  Edge

    e1 = g.addEdge(n1, n2),

    e2 = g.addEdge(n2, n3);

  check(g.valid(n1), "Wrong validity check");

  check(g.valid(e1), "Wrong validity check");

  check(g.valid(g.direct(e1, true)), "Wrong validity check");

  g.erase(n1);

  check(!g.valid(n1), "Wrong validity check");

  check(g.valid(n2), "Wrong validity check");

  check(g.valid(n3), "Wrong validity check");

  check(!g.valid(e1), "Wrong validity check");

  check(g.valid(e2), "Wrong validity check");

  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");

  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

}

void checkGridGraph(int width, int height) {

  typedef GridGraph Graph;

  GRAPH_TYPEDEFS(Graph);

  Graph G(width, height);

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

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

      check(G.col(G(i, j)) == i, "Wrong column");

      check(G.row(G(i, j)) == j, "Wrong row");

      check(G.pos(G(i, j)).x == i, "Wrong column");

      check(G.pos(G(i, j)).y == j, "Wrong row");

    }

  }

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

    for (int i = 0; i < width - 1; ++i) {

      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");

      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");

    }

    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");

  }

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

    for (int i = 1; i < width; ++i) {

      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");

      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");

    }

    check(G.left(G(0, j)) == INVALID, "Wrong left");

  }

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

    for (int j = 0; j < height - 1; ++j) {

      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");

      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");

    }

    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");

  }

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

    for (int j = 1; j < height; ++j) {

      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");

      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");

    }

    check(G.down(G(i, 0)) == INVALID, "Wrong down");

  }

  checkGraphNodeList(G, width * height);

  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);

  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));

  for (NodeIt n(G); n != INVALID; ++n) {

    int nb = 4;

    if (G.col(n) == 0) --nb;

    if (G.col(n) == width - 1) --nb;

    if (G.row(n) == 0) --nb;

    if (G.row(n) == height - 1) --nb;

    checkGraphOutArcList(G, n, nb);

    checkGraphInArcList(G, n, nb);

    checkGraphIncEdgeList(G, n, nb);

  }

  checkArcDirections(G);

  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));

  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);

  checkNodeIds(G);

  checkArcIds(G);

  checkEdgeIds(G);

  checkGraphNodeMap(G);

  checkGraphArcMap(G);

  checkGraphEdgeMap(G);

}

void checkGraphs() {

  { // Checking ListGraph

    checkGraph<ListGraph>();

    checkGraphValidityErase<ListGraph>();

  }

  { // Checking SmartGraph

    checkGraph<SmartGraph>();

    checkGraphValidity<SmartGraph>();

  }

//   { // Checking FullGraph

//     FullGraph g(5);

//     checkGraphNodeList(g, 5);

//     checkGraphEdgeList(g, 10);

//   }

  { // Checking GridGraph

    checkGridGraph(5, 8);

    checkGridGraph(8, 5);

    checkGridGraph(5, 5);

    checkGridGraph(0, 0);

    checkGridGraph(1, 1);

  }

}

int main() {