RhodeCode

  ///

  /// \brief Hypercube graph class

  ///

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

  /// reasons. Thus the maximum dimension of this implementation is 26

  /// (assuming that the size of \c int is 32 bit).

  public:

    /// \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();

    }

    /// \brief Returns \c true if the n'th bit of the node is one.

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

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

    checkGraphInArcList(G, n, num);

  }

  checkGraphArcList(G, 6);

}

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

    checkGraphIncEdgeList(G, n, num - 1);

  }

void checkGridGraph(int width, int height) {

  typedef GridGraph Graph;

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

    }

  }

  checkGraphEdgeMap(G);

}

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

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

    checkGraphIncEdgeList(G, n, dim);