74 static int id(Node node) { return node._id; } |
74 static int id(Node node) { return node._id; } |
75 static int id(Edge edge) { return edge._id; } |
75 static int id(Edge edge) { return edge._id; } |
76 static int id(Arc arc) { return arc._id; } |
76 static int id(Arc arc) { return arc._id; } |
77 |
77 |
78 Node u(Edge edge) const { |
78 Node u(Edge edge) const { |
79 int base = edge._id & ((1 << _dim-1) - 1); |
79 int base = edge._id & ((1 << (_dim-1)) - 1); |
80 int k = edge._id >> _dim-1; |
80 int k = edge._id >> (_dim-1); |
81 return ((base >> k) << k+1) | (base & ((1 << k) - 1)); |
81 return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)); |
82 } |
82 } |
83 |
83 |
84 Node v(Edge edge) const { |
84 Node v(Edge edge) const { |
85 int base = edge._id & ((1 << _dim-1) - 1); |
85 int base = edge._id & ((1 << (_dim-1)) - 1); |
86 int k = edge._id >> _dim-1; |
86 int k = edge._id >> (_dim-1); |
87 return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k); |
87 return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)) | (1 << k); |
88 } |
88 } |
89 |
89 |
90 Node source(Arc arc) const { |
90 Node source(Arc arc) const { |
91 return (arc._id & 1) == 1 ? u(arc) : v(arc); |
91 return (arc._id & 1) == 1 ? u(arc) : v(arc); |
92 } |
92 } |
103 int d = u._id ^ v._id; |
103 int d = u._id ^ v._id; |
104 int k = 0; |
104 int k = 0; |
105 if (d == 0) return INVALID; |
105 if (d == 0) return INVALID; |
106 for ( ; (d & 1) == 0; d >>= 1) ++k; |
106 for ( ; (d & 1) == 0; d >>= 1) ++k; |
107 if (d >> 1 != 0) return INVALID; |
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 |
111 Arc findArc(Node u, Node v, Arc prev = INVALID) const { |
112 Arc findArc(Node u, Node v, Arc prev = INVALID) const { |
112 Edge edge = findEdge(u, v, prev); |
113 Edge edge = findEdge(u, v, prev); |
113 if (edge == INVALID) return INVALID; |
114 if (edge == INVALID) return INVALID; |
114 int k = edge._id >> _dim-1; |
115 int k = edge._id >> (_dim-1); |
115 return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1; |
116 return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1; |
116 } |
117 } |
117 |
118 |
118 class Node { |
119 class Node { |
119 friend class HypercubeGraphBase; |
120 friend class HypercubeGraphBase; |
192 dir = (node._id & 1) == 0; |
193 dir = (node._id & 1) == 0; |
193 } |
194 } |
194 |
195 |
195 void nextInc(Edge& edge, bool& dir) const { |
196 void nextInc(Edge& edge, bool& dir) const { |
196 Node n = dir ? u(edge) : v(edge); |
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 if (k < _dim) { |
199 if (k < _dim) { |
199 edge._id = (k << _dim-1) | |
200 edge._id = (k << (_dim-1)) | |
200 ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1)); |
201 ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1)); |
201 dir = ((n._id >> k) & 1) == 0; |
202 dir = ((n._id >> k) & 1) == 0; |
202 } else { |
203 } else { |
203 edge._id = -1; |
204 edge._id = -1; |
204 dir = true; |
205 dir = true; |
205 } |
206 } |
211 |
212 |
212 void nextOut(Arc& arc) const { |
213 void nextOut(Arc& arc) const { |
213 Node n = (arc._id & 1) == 1 ? u(arc) : v(arc); |
214 Node n = (arc._id & 1) == 1 ? u(arc) : v(arc); |
214 int k = (arc._id >> _dim) + 1; |
215 int k = (arc._id >> _dim) + 1; |
215 if (k < _dim) { |
216 if (k < _dim) { |
216 arc._id = (k << _dim-1) | |
217 arc._id = (k << (_dim-1)) | |
217 ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1)); |
218 ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1)); |
218 arc._id = (arc._id << 1) | (~(n._id >> k) & 1); |
219 arc._id = (arc._id << 1) | (~(n._id >> k) & 1); |
219 } else { |
220 } else { |
220 arc._id = -1; |
221 arc._id = -1; |
221 } |
222 } |
222 } |
223 } |
227 |
228 |
228 void nextIn(Arc& arc) const { |
229 void nextIn(Arc& arc) const { |
229 Node n = (arc._id & 1) == 1 ? v(arc) : u(arc); |
230 Node n = (arc._id & 1) == 1 ? v(arc) : u(arc); |
230 int k = (arc._id >> _dim) + 1; |
231 int k = (arc._id >> _dim) + 1; |
231 if (k < _dim) { |
232 if (k < _dim) { |
232 arc._id = (k << _dim-1) | |
233 arc._id = (k << (_dim-1)) | |
233 ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1)); |
234 ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1)); |
234 arc._id = (arc._id << 1) | ((n._id >> k) & 1); |
235 arc._id = (arc._id << 1) | ((n._id >> k) & 1); |
235 } else { |
236 } else { |
236 arc._id = -1; |
237 arc._id = -1; |
237 } |
238 } |
238 } |
239 } |
252 bool projection(Node node, int n) const { |
253 bool projection(Node node, int n) const { |
253 return static_cast<bool>(node._id & (1 << n)); |
254 return static_cast<bool>(node._id & (1 << n)); |
254 } |
255 } |
255 |
256 |
256 int dimension(Edge edge) const { |
257 int dimension(Edge edge) const { |
257 return edge._id >> _dim-1; |
258 return edge._id >> (_dim-1); |
258 } |
259 } |
259 |
260 |
260 int dimension(Arc arc) const { |
261 int dimension(Arc arc) const { |
261 return arc._id >> _dim; |
262 return arc._id >> _dim; |
262 } |
263 } |