Changeset 372:7b6466ed488a in lemon-1.2
- Timestamp:
- 11/07/08 14:04:54 (16 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/hypercube_graph.h
r365 r372 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 … … 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 return ((base >> k) << k+1) | (base & ((1 << k) - 1));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 return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k);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 … … 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) | (u._id & ((1 << k) - 1)); 108 return (k << (_dim-1)) | ((u._id >> (k+1)) << k) | 109 (u._id & ((1 << k) - 1)); 109 110 } 110 111 … … 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 } … … 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 { … … 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 { … … 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 { … … 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 -
test/graph_test.cc
r365 r372 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 … … 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 } … … 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 } … … 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 } … … 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);
Note: See TracChangeset
for help on using the changeset viewer.