RhodeCode

  ///

  /// HypercubeGraph implements a special graph type. The nodes of the

  /// graph are indexed with integers having at most \c dim binary digits.

  /// Two nodes are connected in the graph if and only if their indices

  /// differ only on one position in the binary form.

  /// This class is completely static and it needs constant memory space.

  ///

  /// This type fully conforms to the \ref concepts::Graph "Graph concept".

  /// Most of its member functions and nested classes are documented

  /// only in the concept class.

  ///

  /// \note The type of the indices is chosen to \c int for efficiency

    /// \brief Constructs a hypercube graph with \c dim dimensions.

    ///

    /// Constructs a hypercube graph with \c dim dimensions.

    HypercubeGraph(int dim) { construct(dim); }

    /// \brief The number of dimensions.

    ///

    /// Gives back the number of dimensions.

    int dimension() const {

      return Parent::dimension();

    }

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

}

void checkFullDigraph(int num) {

  typedef FullDigraph Digraph;

  DIGRAPH_TYPEDEFS(Digraph);

  Digraph G(num);

  checkGraphNodeList(G, num);

  checkGraphArcList(G, num * num);

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

    checkGraphOutArcList(G, n, num);

void checkFullGraph(int num) {

  typedef FullGraph Graph;

  GRAPH_TYPEDEFS(Graph);

  Graph G(num);

  checkGraphNodeList(G, num);

  checkGraphEdgeList(G, num * (num - 1) / 2);

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

    checkGraphOutArcList(G, n, num - 1);

    checkGraphInArcList(G, n, num - 1);

  GRAPH_TYPEDEFS(Graph);

  Graph G(width, height);

  check(G.width() == width, "Wrong column number");

  check(G.height() == height, "Wrong row number");

  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");

}

void checkHypercubeGraph(int dim) {

  GRAPH_TYPEDEFS(HypercubeGraph);

  HypercubeGraph G(dim);

  checkGraphNodeList(G, 1 << dim);

  checkGraphEdgeList(G, dim * (1 << (dim-1)));

  checkGraphArcList(G, dim * (1 << dim));

  Node n = G.nodeFromId(dim);