32 ///\file |
32 ///\file |
33 ///\brief HyperCubeGraph class. |
33 ///\brief HyperCubeGraph class. |
34 |
34 |
35 namespace lemon { |
35 namespace lemon { |
36 |
36 |
37 /// \brief Base graph for HyperCubeGraph. |
|
38 /// |
|
39 /// Base graph for hyper-cube graph. It describes some member functions |
|
40 /// which can be used in the HyperCubeGraph. |
|
41 /// |
|
42 /// \warning Always use the HyperCubeGraph instead of this. |
|
43 /// \see HyperCubeGraph |
|
44 class HyperCubeGraphBase { |
37 class HyperCubeGraphBase { |
45 |
38 |
46 public: |
39 public: |
47 |
40 |
48 typedef HyperCubeGraphBase Graph; |
41 typedef HyperCubeGraphBase Graph; |
68 |
58 |
69 |
59 |
70 typedef True NodeNumTag; |
60 typedef True NodeNumTag; |
71 typedef True EdgeNumTag; |
61 typedef True EdgeNumTag; |
72 |
62 |
73 ///Number of nodes. |
|
74 int nodeNum() const { return _nodeNum; } |
63 int nodeNum() const { return _nodeNum; } |
75 ///Number of edges. |
|
76 int edgeNum() const { return _nodeNum * _dim; } |
64 int edgeNum() const { return _nodeNum * _dim; } |
77 |
65 |
78 /// Maximum node ID. |
|
79 |
|
80 /// Maximum node ID. |
|
81 ///\sa id(Node) |
|
82 int maxNodeId() const { return nodeNum() - 1; } |
66 int maxNodeId() const { return nodeNum() - 1; } |
83 /// Maximum edge ID. |
|
84 |
|
85 /// Maximum edge ID. |
|
86 ///\sa id(Edge) |
|
87 int maxEdgeId() const { return edgeNum() - 1; } |
67 int maxEdgeId() const { return edgeNum() - 1; } |
88 |
68 |
89 /// \brief Gives back the source node of an edge. |
|
90 /// |
|
91 /// Gives back the source node of an edge. |
|
92 Node source(Edge e) const { |
69 Node source(Edge e) const { |
93 return e.id / _dim; |
70 return e.id / _dim; |
94 } |
71 } |
95 |
72 |
96 /// \brief Gives back the target node of an edge. |
|
97 /// |
|
98 /// Gives back the target node of an edge. |
|
99 Node target(Edge e) const { |
73 Node target(Edge e) const { |
100 return (e.id / _dim) ^ ( 1 << (e.id % _dim)); |
74 return (e.id / _dim) ^ ( 1 << (e.id % _dim)); |
101 } |
75 } |
102 |
76 |
103 /// Node ID. |
|
104 |
|
105 /// The ID of a valid Node is a nonnegative integer not greater than |
|
106 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
107 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
108 /// |
|
109 /// The ID of the \ref INVALID node is -1. |
|
110 ///\return The ID of the node \c v. |
|
111 |
|
112 static int id(Node v) { return v.id; } |
77 static int id(Node v) { return v.id; } |
113 /// Edge ID. |
|
114 |
|
115 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
116 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
117 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
118 /// |
|
119 /// The ID of the \ref INVALID edge is -1. |
|
120 ///\return The ID of the edge \c e. |
|
121 static int id(Edge e) { return e.id; } |
78 static int id(Edge e) { return e.id; } |
122 |
79 |
123 static Node nodeFromId(int id) { return Node(id);} |
80 static Node nodeFromId(int id) { return Node(id);} |
124 |
81 |
125 static Edge edgeFromId(int id) { return Edge(id);} |
82 static Edge edgeFromId(int id) { return Edge(id);} |
190 } else { |
147 } else { |
191 edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1; |
148 edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1; |
192 } |
149 } |
193 } |
150 } |
194 |
151 |
195 /// \brief Gives back the number of the dimensions. |
|
196 /// |
|
197 /// Gives back the number of the dimensions. |
|
198 int dimension() const { |
152 int dimension() const { |
199 return _dim; |
153 return _dim; |
200 } |
154 } |
201 |
155 |
202 /// \brief Returns true if the n'th bit of the node is one. |
|
203 /// |
|
204 /// Returns true if the n'th bit of the node is one. |
|
205 bool projection(Node node, int n) const { |
156 bool projection(Node node, int n) const { |
206 return (bool)(node.id & (1 << n)); |
157 return (bool)(node.id & (1 << n)); |
207 } |
158 } |
208 |
159 |
209 /// \brief The dimension id of the edge. |
|
210 /// |
|
211 /// It returns the dimension id of the edge. It can |
|
212 /// be in the ${0, 1, dim-1}$ intervall. |
|
213 int dimension(Edge edge) const { |
160 int dimension(Edge edge) const { |
214 return edge.id % _dim; |
161 return edge.id % _dim; |
215 } |
162 } |
216 |
163 |
217 /// \brief Gives back the index of the node. |
|
218 /// |
|
219 /// Gives back the index of the node. The lower bits of the |
|
220 /// integer describe the node. |
|
221 int index(Node node) const { |
164 int index(Node node) const { |
222 return node.id; |
165 return node.id; |
223 } |
166 } |
224 |
167 |
225 /// \brief Gives back the node by its index. |
|
226 /// |
|
227 /// Gives back the node by its index. |
|
228 Node operator()(int index) const { |
168 Node operator()(int index) const { |
229 return Node(index); |
169 return Node(index); |
230 } |
170 } |
231 |
171 |
232 private: |
172 private: |
250 /// is 26. |
190 /// is 26. |
251 /// |
191 /// |
252 /// The graph type is fully conform to the \ref concept::Graph |
192 /// The graph type is fully conform to the \ref concept::Graph |
253 /// concept but it does not conform to the \ref concept::UGraph. |
193 /// concept but it does not conform to the \ref concept::UGraph. |
254 /// |
194 /// |
255 /// \see HyperCubeGraphBase |
|
256 /// \author Balazs Dezso |
195 /// \author Balazs Dezso |
257 class HyperCubeGraph : public ExtendedHyperCubeGraphBase { |
196 class HyperCubeGraph : public ExtendedHyperCubeGraphBase { |
258 public: |
197 public: |
259 |
198 |
|
199 typedef ExtendedHyperCubeGraphBase Parent; |
|
200 |
260 /// \brief Construct a graph with \c dim dimension. |
201 /// \brief Construct a graph with \c dim dimension. |
261 /// |
202 /// |
262 /// Construct a graph with \c dim dimension. |
203 /// Construct a graph with \c dim dimension. |
263 HyperCubeGraph(int dim) { construct(dim); } |
204 HyperCubeGraph(int dim) { construct(dim); } |
|
205 |
|
206 /// \brief Gives back the number of the dimensions. |
|
207 /// |
|
208 /// Gives back the number of the dimensions. |
|
209 int dimension() const { |
|
210 return Parent::dimension(); |
|
211 } |
|
212 |
|
213 /// \brief Returns true if the n'th bit of the node is one. |
|
214 /// |
|
215 /// Returns true if the n'th bit of the node is one. |
|
216 bool projection(Node node, int n) const { |
|
217 return Parent::projection(node, n); |
|
218 } |
|
219 |
|
220 /// \brief The dimension id of the edge. |
|
221 /// |
|
222 /// It returns the dimension id of the edge. It can |
|
223 /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ intervall. |
|
224 int dimension(Edge edge) const { |
|
225 return Parent::dimension(edge); |
|
226 } |
|
227 |
|
228 /// \brief Gives back the index of the node. |
|
229 /// |
|
230 /// Gives back the index of the node. The lower bits of the |
|
231 /// integer describes the node. |
|
232 int index(Node node) const { |
|
233 return Parent::index(node); |
|
234 } |
|
235 |
|
236 /// \brief Gives back the node by its index. |
|
237 /// |
|
238 /// Gives back the node by its index. |
|
239 Node operator()(int index) const { |
|
240 return Parent::operator()(index); |
|
241 } |
|
242 |
|
243 /// \brief Number of nodes. |
|
244 int nodeNum() const { return Parent::nodeNum(); } |
|
245 /// \brief Number of edges. |
|
246 int edgeNum() const { return Parent::edgeNum(); } |
264 |
247 |
265 /// \brief Linear combination map. |
248 /// \brief Linear combination map. |
266 /// |
249 /// |
267 /// It makes possible to give back a linear combination |
250 /// It makes possible to give back a linear combination |
268 /// for each node. This function works like the \c std::accumulate |
251 /// for each node. This function works like the \c std::accumulate |