RhodeCode

  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;

  /// \ingroup graphs

  ///

  /// \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).

  class HypercubeGraph : public ExtendedHypercubeGraphBase {

    typedef ExtendedHypercubeGraphBase Parent;

  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.

    ///

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

    bool projection(Node node, int n) const {

      return Parent::projection(node, n);

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

  }

  checkGraphConArcList(G, num * num);

  checkNodeIds(G);

  snapshot.restore();

  checkGraphNodeList(G, 4);

  checkGraphEdgeList(G, 3);

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

  }

  checkGraphConArcList(G, num * (num - 1));

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

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

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

    }

  }

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

  checkArcIds(G);

  checkEdgeIds(G);

  checkGraphNodeMap(G);

  checkGraphArcMap(G);

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

    for (IncEdgeIt e(G, n); e != INVALID; ++e) {

      check( (G.u(e) == n &&

              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||

             (G.v(e) == n &&