|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef HYPERCUBE_GRAPH_H |
|
20 #define HYPERCUBE_GRAPH_H |
|
21 |
|
22 #include <iostream> |
|
23 #include <vector> |
|
24 #include <lemon/core.h> |
|
25 #include <lemon/error.h> |
|
26 |
|
27 #include <lemon/bits/base_extender.h> |
|
28 #include <lemon/bits/graph_extender.h> |
|
29 |
|
30 ///\ingroup graphs |
|
31 ///\file |
|
32 ///\brief HypercubeDigraph class. |
|
33 |
|
34 namespace lemon { |
|
35 |
|
36 class HypercubeDigraphBase { |
|
37 |
|
38 public: |
|
39 |
|
40 typedef HypercubeDigraphBase Digraph; |
|
41 |
|
42 class Node; |
|
43 class Arc; |
|
44 |
|
45 public: |
|
46 |
|
47 HypercubeDigraphBase() {} |
|
48 |
|
49 protected: |
|
50 |
|
51 void construct(int dim) { |
|
52 _dim = dim; |
|
53 _nodeNum = 1 << dim; |
|
54 } |
|
55 |
|
56 public: |
|
57 |
|
58 typedef True NodeNumTag; |
|
59 typedef True ArcNumTag; |
|
60 |
|
61 int nodeNum() const { return _nodeNum; } |
|
62 int arcNum() const { return _nodeNum * _dim; } |
|
63 |
|
64 int maxNodeId() const { return nodeNum() - 1; } |
|
65 int maxArcId() const { return arcNum() - 1; } |
|
66 |
|
67 Node source(Arc e) const { |
|
68 return e.id / _dim; |
|
69 } |
|
70 |
|
71 Node target(Arc e) const { |
|
72 return (e.id / _dim) ^ (1 << (e.id % _dim)); |
|
73 } |
|
74 |
|
75 static int id(Node v) { return v.id; } |
|
76 static int id(Arc e) { return e.id; } |
|
77 |
|
78 static Node nodeFromId(int id) { return Node(id); } |
|
79 |
|
80 static Arc arcFromId(int id) { return Arc(id); } |
|
81 |
|
82 class Node { |
|
83 friend class HypercubeDigraphBase; |
|
84 protected: |
|
85 int id; |
|
86 Node(int _id) { id = _id;} |
|
87 public: |
|
88 Node() {} |
|
89 Node (Invalid) { id = -1; } |
|
90 bool operator==(const Node node) const { return id == node.id; } |
|
91 bool operator!=(const Node node) const { return id != node.id; } |
|
92 bool operator<(const Node node) const { return id < node.id; } |
|
93 }; |
|
94 |
|
95 class Arc { |
|
96 friend class HypercubeDigraphBase; |
|
97 protected: |
|
98 int id; |
|
99 Arc(int _id) : id(_id) {} |
|
100 public: |
|
101 Arc() { } |
|
102 Arc (Invalid) { id = -1; } |
|
103 bool operator==(const Arc arc) const { return id == arc.id; } |
|
104 bool operator!=(const Arc arc) const { return id != arc.id; } |
|
105 bool operator<(const Arc arc) const { return id < arc.id; } |
|
106 }; |
|
107 |
|
108 void first(Node& node) const { |
|
109 node.id = nodeNum() - 1; |
|
110 } |
|
111 |
|
112 static void next(Node& node) { |
|
113 --node.id; |
|
114 } |
|
115 |
|
116 void first(Arc& arc) const { |
|
117 arc.id = arcNum() - 1; |
|
118 } |
|
119 |
|
120 static void next(Arc& arc) { |
|
121 --arc.id; |
|
122 } |
|
123 |
|
124 void firstOut(Arc& arc, const Node& node) const { |
|
125 arc.id = node.id * _dim; |
|
126 } |
|
127 |
|
128 void nextOut(Arc& arc) const { |
|
129 ++arc.id; |
|
130 if (arc.id % _dim == 0) arc.id = -1; |
|
131 } |
|
132 |
|
133 void firstIn(Arc& arc, const Node& node) const { |
|
134 arc.id = (node.id ^ 1) * _dim; |
|
135 } |
|
136 |
|
137 void nextIn(Arc& arc) const { |
|
138 int cnt = arc.id % _dim; |
|
139 if ((cnt + 1) % _dim == 0) { |
|
140 arc.id = -1; |
|
141 } else { |
|
142 arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1; |
|
143 } |
|
144 } |
|
145 |
|
146 int dimension() const { |
|
147 return _dim; |
|
148 } |
|
149 |
|
150 bool projection(Node node, int n) const { |
|
151 return static_cast<bool>(node.id & (1 << n)); |
|
152 } |
|
153 |
|
154 int dimension(Arc arc) const { |
|
155 return arc.id % _dim; |
|
156 } |
|
157 |
|
158 int index(Node node) const { |
|
159 return node.id; |
|
160 } |
|
161 |
|
162 Node operator()(int ix) const { |
|
163 return Node(ix); |
|
164 } |
|
165 |
|
166 private: |
|
167 int _dim, _nodeNum; |
|
168 }; |
|
169 |
|
170 |
|
171 typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase; |
|
172 |
|
173 /// \ingroup digraphs |
|
174 /// |
|
175 /// \brief Hypercube digraph class |
|
176 /// |
|
177 /// This class implements a special digraph type. The nodes of the |
|
178 /// digraph are indiced with integers with at most \c dim binary digits. |
|
179 /// Two nodes are connected in the digraph if the indices differ only |
|
180 /// on one position in the binary form. |
|
181 /// |
|
182 /// \note The type of the \c ids is chosen to \c int because efficiency |
|
183 /// reasons. Thus the maximum dimension of this implementation is 26. |
|
184 /// |
|
185 /// The digraph type is fully conform to the \ref concepts::Digraph |
|
186 /// concept but it does not conform to \ref concepts::Graph. |
|
187 class HypercubeDigraph : public ExtendedHypercubeDigraphBase { |
|
188 public: |
|
189 |
|
190 typedef ExtendedHypercubeDigraphBase Parent; |
|
191 |
|
192 /// \brief Construct a hypercube digraph with \c dim dimension. |
|
193 /// |
|
194 /// Construct a hypercube digraph with \c dim dimension. |
|
195 HypercubeDigraph(int dim) { construct(dim); } |
|
196 |
|
197 /// \brief Gives back the number of the dimensions. |
|
198 /// |
|
199 /// Gives back the number of the dimensions. |
|
200 int dimension() const { |
|
201 return Parent::dimension(); |
|
202 } |
|
203 |
|
204 /// \brief Returns true if the n'th bit of the node is one. |
|
205 /// |
|
206 /// Returns true if the n'th bit of the node is one. |
|
207 bool projection(Node node, int n) const { |
|
208 return Parent::projection(node, n); |
|
209 } |
|
210 |
|
211 /// \brief The dimension id of the arc. |
|
212 /// |
|
213 /// It returns the dimension id of the arc. It can |
|
214 /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval. |
|
215 int dimension(Arc arc) const { |
|
216 return Parent::dimension(arc); |
|
217 } |
|
218 |
|
219 /// \brief Gives back the index of the node. |
|
220 /// |
|
221 /// Gives back the index of the node. The lower bits of the |
|
222 /// integer describes the node. |
|
223 int index(Node node) const { |
|
224 return Parent::index(node); |
|
225 } |
|
226 |
|
227 /// \brief Gives back the node by its index. |
|
228 /// |
|
229 /// Gives back the node by its index. |
|
230 Node operator()(int ix) const { |
|
231 return Parent::operator()(ix); |
|
232 } |
|
233 |
|
234 /// \brief Number of nodes. |
|
235 int nodeNum() const { return Parent::nodeNum(); } |
|
236 /// \brief Number of arcs. |
|
237 int arcNum() const { return Parent::arcNum(); } |
|
238 |
|
239 /// \brief Linear combination map. |
|
240 /// |
|
241 /// It makes possible to give back a linear combination |
|
242 /// for each node. This function works like the \c std::accumulate |
|
243 /// so it accumulates the \c bf binary function with the \c fv |
|
244 /// first value. The map accumulates only on that dimensions where |
|
245 /// the node's index is one. The accumulated values should be |
|
246 /// given by the \c begin and \c end iterators and the length of this |
|
247 /// range should be equal to the dimension number of the digraph. |
|
248 /// |
|
249 ///\code |
|
250 /// const int DIM = 3; |
|
251 /// HypercubeDigraph digraph(DIM); |
|
252 /// dim2::Point<double> base[DIM]; |
|
253 /// for (int k = 0; k < DIM; ++k) { |
|
254 /// base[k].x = rnd(); |
|
255 /// base[k].y = rnd(); |
|
256 /// } |
|
257 /// HypercubeDigraph::HyperMap<dim2::Point<double> > |
|
258 /// pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0)); |
|
259 ///\endcode |
|
260 /// |
|
261 /// \see HypercubeDigraph |
|
262 template <typename T, typename BF = std::plus<T> > |
|
263 class HyperMap { |
|
264 public: |
|
265 |
|
266 typedef Node Key; |
|
267 typedef T Value; |
|
268 |
|
269 |
|
270 /// \brief Constructor for HyperMap. |
|
271 /// |
|
272 /// Construct a HyperMap for the given digraph. The accumulated values |
|
273 /// should be given by the \c begin and \c end iterators and the length |
|
274 /// of this range should be equal to the dimension number of the digraph. |
|
275 /// |
|
276 /// This function accumulates the \c bf binary function with |
|
277 /// the \c fv first value. The map accumulates only on that dimensions |
|
278 /// where the node's index is one. |
|
279 template <typename It> |
|
280 HyperMap(const Digraph& digraph, It begin, It end, |
|
281 T fv = 0.0, const BF& bf = BF()) |
|
282 : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf) |
|
283 { |
|
284 LEMON_ASSERT(_values.size() == digraph.dimension(), |
|
285 "Wrong size of dimension"); |
|
286 } |
|
287 |
|
288 /// \brief Gives back the partial accumulated value. |
|
289 /// |
|
290 /// Gives back the partial accumulated value. |
|
291 Value operator[](Key k) const { |
|
292 Value val = _first_value; |
|
293 int id = _graph.index(k); |
|
294 int n = 0; |
|
295 while (id != 0) { |
|
296 if (id & 1) { |
|
297 val = _bin_func(val, _values[n]); |
|
298 } |
|
299 id >>= 1; |
|
300 ++n; |
|
301 } |
|
302 return val; |
|
303 } |
|
304 |
|
305 private: |
|
306 const Digraph& _graph; |
|
307 std::vector<T> _values; |
|
308 T _first_value; |
|
309 BF _bin_func; |
|
310 }; |
|
311 |
|
312 }; |
|
313 |
|
314 } |
|
315 |
|
316 #endif |