1.1 --- a/lemon/hypercube_graph.h Fri Nov 07 07:18:37 2008 +0000
1.2 +++ b/lemon/hypercube_graph.h Fri Nov 07 13:04:54 2008 +0000
1.3 @@ -50,7 +50,7 @@
1.4 LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
1.5 _dim = dim;
1.6 _node_num = 1 << dim;
1.7 - _edge_num = dim * (1 << dim-1);
1.8 + _edge_num = dim * (1 << (dim-1));
1.9 }
1.10
1.11 public:
1.12 @@ -76,15 +76,15 @@
1.13 static int id(Arc arc) { return arc._id; }
1.14
1.15 Node u(Edge edge) const {
1.16 - int base = edge._id & ((1 << _dim-1) - 1);
1.17 - int k = edge._id >> _dim-1;
1.18 - return ((base >> k) << k+1) | (base & ((1 << k) - 1));
1.19 + int base = edge._id & ((1 << (_dim-1)) - 1);
1.20 + int k = edge._id >> (_dim-1);
1.21 + return ((base >> k) << (k+1)) | (base & ((1 << k) - 1));
1.22 }
1.23
1.24 Node v(Edge edge) const {
1.25 - int base = edge._id & ((1 << _dim-1) - 1);
1.26 - int k = edge._id >> _dim-1;
1.27 - return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k);
1.28 + int base = edge._id & ((1 << (_dim-1)) - 1);
1.29 + int k = edge._id >> (_dim-1);
1.30 + return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)) | (1 << k);
1.31 }
1.32
1.33 Node source(Arc arc) const {
1.34 @@ -105,13 +105,14 @@
1.35 if (d == 0) return INVALID;
1.36 for ( ; (d & 1) == 0; d >>= 1) ++k;
1.37 if (d >> 1 != 0) return INVALID;
1.38 - return (k << _dim-1) | ((u._id >> k+1) << k) | (u._id & ((1 << k) - 1));
1.39 + return (k << (_dim-1)) | ((u._id >> (k+1)) << k) |
1.40 + (u._id & ((1 << k) - 1));
1.41 }
1.42
1.43 Arc findArc(Node u, Node v, Arc prev = INVALID) const {
1.44 Edge edge = findEdge(u, v, prev);
1.45 if (edge == INVALID) return INVALID;
1.46 - int k = edge._id >> _dim-1;
1.47 + int k = edge._id >> (_dim-1);
1.48 return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
1.49 }
1.50
1.51 @@ -194,10 +195,10 @@
1.52
1.53 void nextInc(Edge& edge, bool& dir) const {
1.54 Node n = dir ? u(edge) : v(edge);
1.55 - int k = (edge._id >> _dim-1) + 1;
1.56 + int k = (edge._id >> (_dim-1)) + 1;
1.57 if (k < _dim) {
1.58 - edge._id = (k << _dim-1) |
1.59 - ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
1.60 + edge._id = (k << (_dim-1)) |
1.61 + ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
1.62 dir = ((n._id >> k) & 1) == 0;
1.63 } else {
1.64 edge._id = -1;
1.65 @@ -213,8 +214,8 @@
1.66 Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
1.67 int k = (arc._id >> _dim) + 1;
1.68 if (k < _dim) {
1.69 - arc._id = (k << _dim-1) |
1.70 - ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
1.71 + arc._id = (k << (_dim-1)) |
1.72 + ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
1.73 arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
1.74 } else {
1.75 arc._id = -1;
1.76 @@ -229,8 +230,8 @@
1.77 Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
1.78 int k = (arc._id >> _dim) + 1;
1.79 if (k < _dim) {
1.80 - arc._id = (k << _dim-1) |
1.81 - ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
1.82 + arc._id = (k << (_dim-1)) |
1.83 + ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
1.84 arc._id = (arc._id << 1) | ((n._id >> k) & 1);
1.85 } else {
1.86 arc._id = -1;
1.87 @@ -254,7 +255,7 @@
1.88 }
1.89
1.90 int dimension(Edge edge) const {
1.91 - return edge._id >> _dim-1;
1.92 + return edge._id >> (_dim-1);
1.93 }
1.94
1.95 int dimension(Arc arc) const {
2.1 --- a/test/graph_test.cc Fri Nov 07 07:18:37 2008 +0000
2.2 +++ b/test/graph_test.cc Fri Nov 07 13:04:54 2008 +0000
2.3 @@ -321,7 +321,7 @@
2.4
2.5 HypercubeGraph G(dim);
2.6 checkGraphNodeList(G, 1 << dim);
2.7 - checkGraphEdgeList(G, dim * (1 << dim-1));
2.8 + checkGraphEdgeList(G, dim * (1 << (dim-1)));
2.9 checkGraphArcList(G, dim * (1 << dim));
2.10
2.11 Node n = G.nodeFromId(dim);
2.12 @@ -330,29 +330,29 @@
2.13 checkGraphIncEdgeList(G, n, dim);
2.14 for (IncEdgeIt e(G, n); e != INVALID; ++e) {
2.15 check( (G.u(e) == n &&
2.16 - G.id(G.v(e)) == G.id(n) ^ (1 << G.dimension(e))) ||
2.17 + G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
2.18 (G.v(e) == n &&
2.19 - G.id(G.u(e)) == G.id(n) ^ (1 << G.dimension(e))),
2.20 + G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
2.21 "Wrong edge or wrong dimension");
2.22 }
2.23
2.24 checkGraphOutArcList(G, n, dim);
2.25 for (OutArcIt a(G, n); a != INVALID; ++a) {
2.26 check(G.source(a) == n &&
2.27 - G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)),
2.28 + G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
2.29 "Wrong arc or wrong dimension");
2.30 }
2.31
2.32 checkGraphInArcList(G, n, dim);
2.33 for (InArcIt a(G, n); a != INVALID; ++a) {
2.34 check(G.target(a) == n &&
2.35 - G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)),
2.36 + G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
2.37 "Wrong arc or wrong dimension");
2.38 }
2.39 }
2.40
2.41 checkGraphConArcList(G, (1 << dim) * dim);
2.42 - checkGraphConEdgeList(G, dim * (1 << dim-1));
2.43 + checkGraphConEdgeList(G, dim * (1 << (dim-1)));
2.44
2.45 checkArcDirections(G);
2.46