r372:7b6466ed488a
Fri, 07 Nov 2008 14:04:54
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -50,7 +50,7 @@ |
| 50 | 50 |
LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1."); |
| 51 | 51 |
_dim = dim; |
| 52 | 52 |
_node_num = 1 << dim; |
| 53 |
_edge_num = dim * (1 << dim-1); |
|
| 53 |
_edge_num = dim * (1 << (dim-1)); |
|
| 54 | 54 |
} |
| 55 | 55 |
|
| 56 | 56 |
public: |
| ... | ... |
@@ -76,15 +76,15 @@ |
| 76 | 76 |
static int id(Arc arc) { return arc._id; }
|
| 77 | 77 |
|
| 78 | 78 |
Node u(Edge edge) const {
|
| 79 |
int base = edge._id & ((1 << _dim-1) - 1); |
|
| 80 |
int k = edge._id >> _dim-1; |
|
| 81 |
|
|
| 79 |
int base = edge._id & ((1 << (_dim-1)) - 1); |
|
| 80 |
int k = edge._id >> (_dim-1); |
|
| 81 |
return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)); |
|
| 82 | 82 |
} |
| 83 | 83 |
|
| 84 | 84 |
Node v(Edge edge) const {
|
| 85 |
int base = edge._id & ((1 << _dim-1) - 1); |
|
| 86 |
int k = edge._id >> _dim-1; |
|
| 87 |
|
|
| 85 |
int base = edge._id & ((1 << (_dim-1)) - 1); |
|
| 86 |
int k = edge._id >> (_dim-1); |
|
| 87 |
return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)) | (1 << k); |
|
| 88 | 88 |
} |
| 89 | 89 |
|
| 90 | 90 |
Node source(Arc arc) const {
|
| ... | ... |
@@ -105,13 +105,14 @@ |
| 105 | 105 |
if (d == 0) return INVALID; |
| 106 | 106 |
for ( ; (d & 1) == 0; d >>= 1) ++k; |
| 107 | 107 |
if (d >> 1 != 0) return INVALID; |
| 108 |
return (k << _dim-1) | ((u._id >> k+1) << k) | |
|
| 108 |
return (k << (_dim-1)) | ((u._id >> (k+1)) << k) | |
|
| 109 |
(u._id & ((1 << k) - 1)); |
|
| 109 | 110 |
} |
| 110 | 111 |
|
| 111 | 112 |
Arc findArc(Node u, Node v, Arc prev = INVALID) const {
|
| 112 | 113 |
Edge edge = findEdge(u, v, prev); |
| 113 | 114 |
if (edge == INVALID) return INVALID; |
| 114 |
int k = edge._id >> _dim-1; |
|
| 115 |
int k = edge._id >> (_dim-1); |
|
| 115 | 116 |
return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1; |
| 116 | 117 |
} |
| 117 | 118 |
|
| ... | ... |
@@ -194,10 +195,10 @@ |
| 194 | 195 |
|
| 195 | 196 |
void nextInc(Edge& edge, bool& dir) const {
|
| 196 | 197 |
Node n = dir ? u(edge) : v(edge); |
| 197 |
int k = (edge._id >> _dim-1) + 1; |
|
| 198 |
int k = (edge._id >> (_dim-1)) + 1; |
|
| 198 | 199 |
if (k < _dim) {
|
| 199 |
edge._id = (k << _dim-1) | |
|
| 200 |
((n._id >> k+1) << k) | (n._id & ((1 << k) - 1)); |
|
| 200 |
edge._id = (k << (_dim-1)) | |
|
| 201 |
((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1)); |
|
| 201 | 202 |
dir = ((n._id >> k) & 1) == 0; |
| 202 | 203 |
} else {
|
| 203 | 204 |
edge._id = -1; |
| ... | ... |
@@ -213,8 +214,8 @@ |
| 213 | 214 |
Node n = (arc._id & 1) == 1 ? u(arc) : v(arc); |
| 214 | 215 |
int k = (arc._id >> _dim) + 1; |
| 215 | 216 |
if (k < _dim) {
|
| 216 |
arc._id = (k << _dim-1) | |
|
| 217 |
((n._id >> k+1) << k) | (n._id & ((1 << k) - 1)); |
|
| 217 |
arc._id = (k << (_dim-1)) | |
|
| 218 |
((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1)); |
|
| 218 | 219 |
arc._id = (arc._id << 1) | (~(n._id >> k) & 1); |
| 219 | 220 |
} else {
|
| 220 | 221 |
arc._id = -1; |
| ... | ... |
@@ -229,8 +230,8 @@ |
| 229 | 230 |
Node n = (arc._id & 1) == 1 ? v(arc) : u(arc); |
| 230 | 231 |
int k = (arc._id >> _dim) + 1; |
| 231 | 232 |
if (k < _dim) {
|
| 232 |
arc._id = (k << _dim-1) | |
|
| 233 |
((n._id >> k+1) << k) | (n._id & ((1 << k) - 1)); |
|
| 233 |
arc._id = (k << (_dim-1)) | |
|
| 234 |
((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1)); |
|
| 234 | 235 |
arc._id = (arc._id << 1) | ((n._id >> k) & 1); |
| 235 | 236 |
} else {
|
| 236 | 237 |
arc._id = -1; |
| ... | ... |
@@ -254,7 +255,7 @@ |
| 254 | 255 |
} |
| 255 | 256 |
|
| 256 | 257 |
int dimension(Edge edge) const {
|
| 257 |
return edge._id >> _dim-1; |
|
| 258 |
return edge._id >> (_dim-1); |
|
| 258 | 259 |
} |
| 259 | 260 |
|
| 260 | 261 |
int dimension(Arc arc) const {
|
| ... | ... |
@@ -321,7 +321,7 @@ |
| 321 | 321 |
|
| 322 | 322 |
HypercubeGraph G(dim); |
| 323 | 323 |
checkGraphNodeList(G, 1 << dim); |
| 324 |
checkGraphEdgeList(G, dim * (1 << dim-1)); |
|
| 324 |
checkGraphEdgeList(G, dim * (1 << (dim-1))); |
|
| 325 | 325 |
checkGraphArcList(G, dim * (1 << dim)); |
| 326 | 326 |
|
| 327 | 327 |
Node n = G.nodeFromId(dim); |
| ... | ... |
@@ -330,29 +330,29 @@ |
| 330 | 330 |
checkGraphIncEdgeList(G, n, dim); |
| 331 | 331 |
for (IncEdgeIt e(G, n); e != INVALID; ++e) {
|
| 332 | 332 |
check( (G.u(e) == n && |
| 333 |
G.id(G.v(e)) == G.id(n) ^ (1 << G.dimension(e))) || |
|
| 333 |
G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) || |
|
| 334 | 334 |
(G.v(e) == n && |
| 335 |
G.id(G.u(e)) == G.id(n) ^ (1 << G.dimension(e))), |
|
| 335 |
G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))), |
|
| 336 | 336 |
"Wrong edge or wrong dimension"); |
| 337 | 337 |
} |
| 338 | 338 |
|
| 339 | 339 |
checkGraphOutArcList(G, n, dim); |
| 340 | 340 |
for (OutArcIt a(G, n); a != INVALID; ++a) {
|
| 341 | 341 |
check(G.source(a) == n && |
| 342 |
G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)), |
|
| 342 |
G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))), |
|
| 343 | 343 |
"Wrong arc or wrong dimension"); |
| 344 | 344 |
} |
| 345 | 345 |
|
| 346 | 346 |
checkGraphInArcList(G, n, dim); |
| 347 | 347 |
for (InArcIt a(G, n); a != INVALID; ++a) {
|
| 348 | 348 |
check(G.target(a) == n && |
| 349 |
G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)), |
|
| 349 |
G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))), |
|
| 350 | 350 |
"Wrong arc or wrong dimension"); |
| 351 | 351 |
} |
| 352 | 352 |
} |
| 353 | 353 |
|
| 354 | 354 |
checkGraphConArcList(G, (1 << dim) * dim); |
| 355 |
checkGraphConEdgeList(G, dim * (1 << dim-1)); |
|
| 355 |
checkGraphConEdgeList(G, dim * (1 << (dim-1))); |
|
| 356 | 356 |
|
| 357 | 357 |
checkArcDirections(G); |
| 358 | 358 |
|
0 comments (0 inline)