Changeset 377:a12eef1f82b2 in lemon for lemon/hypercube_graph.h
 Timestamp:
 11/06/08 15:16:37 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/hypercube_graph.h
r376 r377 20 20 #define HYPERCUBE_GRAPH_H 21 21 22 #include <iostream>23 22 #include <vector> 24 23 #include <lemon/core.h> 25 #include <lemon/error.h> 26 27 #include <lemon/bits/base_extender.h> 24 #include <lemon/assert.h> 28 25 #include <lemon/bits/graph_extender.h> 29 26 30 27 ///\ingroup graphs 31 28 ///\file 32 ///\brief Hypercube Digraph class.29 ///\brief HypercubeGraph class. 33 30 34 31 namespace lemon { 35 32 36 class Hypercube DigraphBase {33 class HypercubeGraphBase { 37 34 38 35 public: 39 36 40 typedef Hypercube DigraphBase Digraph;37 typedef HypercubeGraphBase Graph; 41 38 42 39 class Node; 40 class Edge; 43 41 class Arc; 44 42 45 43 public: 46 44 47 Hypercube DigraphBase() {}45 HypercubeGraphBase() {} 48 46 49 47 protected: 50 48 51 49 void construct(int dim) { 50 LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1."); 52 51 _dim = dim; 53 _nodeNum = 1 << dim; 52 _node_num = 1 << dim; 53 _edge_num = dim * (1 << dim1); 54 54 } 55 55 … … 57 57 58 58 typedef True NodeNumTag; 59 typedef True EdgeNumTag; 59 60 typedef True ArcNumTag; 60 61 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; } 62 int nodeNum() const { return _node_num; } 63 int edgeNum() const { return _edge_num; } 64 int arcNum() const { return 2 * _edge_num; } 65 66 int maxNodeId() const { return _node_num  1; } 67 int maxEdgeId() const { return _edge_num  1; } 68 int maxArcId() const { return 2 * _edge_num  1; } 77 69 78 70 static Node nodeFromId(int id) { return Node(id); } 79 71 static Edge edgeFromId(int id) { return Edge(id); } 80 72 static Arc arcFromId(int id) { return Arc(id); } 81 73 74 static int id(Node node) { return node._id; } 75 static int id(Edge edge) { return edge._id; } 76 static int id(Arc arc) { return arc._id; } 77 78 Node u(Edge edge) const { 79 int base = edge._id & ((1 << _dim1)  1); 80 int k = edge._id >> _dim1; 81 return ((base >> k) << k+1)  (base & ((1 << k)  1)); 82 } 83 84 Node v(Edge edge) const { 85 int base = edge._id & ((1 << _dim1)  1); 86 int k = edge._id >> _dim1; 87 return ((base >> k) << k+1)  (base & ((1 << k)  1))  (1 << k); 88 } 89 90 Node source(Arc arc) const { 91 return (arc._id & 1) == 1 ? u(arc) : v(arc); 92 } 93 94 Node target(Arc arc) const { 95 return (arc._id & 1) == 1 ? v(arc) : u(arc); 96 } 97 98 typedef True FindEdgeTag; 99 typedef True FindArcTag; 100 101 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { 102 if (prev != INVALID) return INVALID; 103 int d = u._id ^ v._id; 104 int k = 0; 105 if (d == 0) return INVALID; 106 for ( ; (d & 1) == 0; d >>= 1) ++k; 107 if (d >> 1 != 0) return INVALID; 108 return (k << _dim1)  ((u._id >> k+1) << k)  (u._id & ((1 << k)  1)); 109 } 110 111 Arc findArc(Node u, Node v, Arc prev = INVALID) const { 112 Edge edge = findEdge(u, v, prev); 113 if (edge == INVALID) return INVALID; 114 int k = edge._id >> _dim1; 115 return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1)  1; 116 } 117 82 118 class Node { 83 friend class HypercubeDigraphBase; 119 friend class HypercubeGraphBase; 120 84 121 protected: 85 int id;86 Node(int _id) { id = _id;}122 int _id; 123 Node(int id) : _id(id) {} 87 124 public: 88 125 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;}126 Node (Invalid) : _id(1) {} 127 bool operator==(const Node node) const {return _id == node._id;} 128 bool operator!=(const Node node) const {return _id != node._id;} 129 bool operator<(const Node node) const {return _id < node._id;} 93 130 }; 94 131 132 class Edge { 133 friend class HypercubeGraphBase; 134 friend class Arc; 135 136 protected: 137 int _id; 138 139 Edge(int id) : _id(id) {} 140 141 public: 142 Edge() {} 143 Edge (Invalid) : _id(1) {} 144 bool operator==(const Edge edge) const {return _id == edge._id;} 145 bool operator!=(const Edge edge) const {return _id != edge._id;} 146 bool operator<(const Edge edge) const {return _id < edge._id;} 147 }; 148 95 149 class Arc { 96 friend class HypercubeDigraphBase; 150 friend class HypercubeGraphBase; 151 97 152 protected: 98 int id; 99 Arc(int _id) : id(_id) {} 153 int _id; 154 155 Arc(int id) : _id(id) {} 156 100 157 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; } 158 Arc() {} 159 Arc (Invalid) : _id(1) {} 160 operator Edge() const { return _id != 1 ? Edge(_id >> 1) : INVALID; } 161 bool operator==(const Arc arc) const {return _id == arc._id;} 162 bool operator!=(const Arc arc) const {return _id != arc._id;} 163 bool operator<(const Arc arc) const {return _id < arc._id;} 106 164 }; 107 165 108 166 void first(Node& node) const { 109 node. id = nodeNum() 1;167 node._id = _node_num  1; 110 168 } 111 169 112 170 static void next(Node& node) { 113 node.id; 171 node._id; 172 } 173 174 void first(Edge& edge) const { 175 edge._id = _edge_num  1; 176 } 177 178 static void next(Edge& edge) { 179 edge._id; 114 180 } 115 181 116 182 void first(Arc& arc) const { 117 arc. id = arcNum() 1;183 arc._id = 2 * _edge_num  1; 118 184 } 119 185 120 186 static void next(Arc& arc) { 121 arc.id; 187 arc._id; 188 } 189 190 void firstInc(Edge& edge, bool& dir, const Node& node) const { 191 edge._id = node._id >> 1; 192 dir = (node._id & 1) == 0; 193 } 194 195 void nextInc(Edge& edge, bool& dir) const { 196 Node n = dir ? u(edge) : v(edge); 197 int k = (edge._id >> _dim1) + 1; 198 if (k < _dim) { 199 edge._id = (k << _dim1)  200 ((n._id >> k+1) << k)  (n._id & ((1 << k)  1)); 201 dir = ((n._id >> k) & 1) == 0; 202 } else { 203 edge._id = 1; 204 dir = true; 205 } 122 206 } 123 207 124 208 void firstOut(Arc& arc, const Node& node) const { 125 arc. id = node.id * _dim;209 arc._id = ((node._id >> 1) << 1)  (~node._id & 1); 126 210 } 127 211 128 212 void nextOut(Arc& arc) const { 129 ++arc.id; 130 if (arc.id % _dim == 0) arc.id = 1; 213 Node n = (arc._id & 1) == 1 ? u(arc) : v(arc); 214 int k = (arc._id >> _dim) + 1; 215 if (k < _dim) { 216 arc._id = (k << _dim1)  217 ((n._id >> k+1) << k)  (n._id & ((1 << k)  1)); 218 arc._id = (arc._id << 1)  (~(n._id >> k) & 1); 219 } else { 220 arc._id = 1; 221 } 131 222 } 132 223 133 224 void firstIn(Arc& arc, const Node& node) const { 134 arc. id = (node.id ^ 1) * _dim;225 arc._id = ((node._id >> 1) << 1)  (node._id & 1); 135 226 } 136 227 137 228 void nextIn(Arc& arc) const { 138 int cnt = arc.id % _dim; 139 if ((cnt + 1) % _dim == 0) { 140 arc.id = 1; 229 Node n = (arc._id & 1) == 1 ? v(arc) : u(arc); 230 int k = (arc._id >> _dim) + 1; 231 if (k < _dim) { 232 arc._id = (k << _dim1)  233 ((n._id >> k+1) << k)  (n._id & ((1 << k)  1)); 234 arc._id = (arc._id << 1)  ((n._id >> k) & 1); 141 235 } else { 142 arc. id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt +1;236 arc._id = 1; 143 237 } 238 } 239 240 static bool direction(Arc arc) { 241 return (arc._id & 1) == 1; 242 } 243 244 static Arc direct(Edge edge, bool dir) { 245 return Arc((edge._id << 1)  (dir ? 1 : 0)); 144 246 } 145 247 … … 149 251 150 252 bool projection(Node node, int n) const { 151 return static_cast<bool>(node.id & (1 << n)); 253 return static_cast<bool>(node._id & (1 << n)); 254 } 255 256 int dimension(Edge edge) const { 257 return edge._id >> _dim1; 152 258 } 153 259 154 260 int dimension(Arc arc) const { 155 return arc. id %_dim;261 return arc._id >> _dim; 156 262 } 157 263 158 264 int index(Node node) const { 159 return node. id;265 return node._id; 160 266 } 161 267 … … 165 271 166 272 private: 167 int _dim, _nodeNum; 273 int _dim; 274 int _node_num, _edge_num; 168 275 }; 169 276 170 277 171 typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;172 173 /// \ingroup digraphs278 typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase; 279 280 /// \ingroup graphs 174 281 /// 175 /// \brief Hypercube digraph class282 /// \brief Hypercube graph class 176 283 /// 177 /// This class implements a special digraph type. The nodes of the178 /// digraphare indiced with integers with at most \c dim binary digits.179 /// Two nodes are connected in the digraph if the indices differ only180 /// on one position in the binary form.284 /// This class implements a special graph type. The nodes of the graph 285 /// are indiced with integers with at most \c dim binary digits. 286 /// Two nodes are connected in the graph if and only if their indices 287 /// differ only on one position in the binary form. 181 288 /// 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. 289 /// \note The type of the indices is chosen to \c int for efficiency 290 /// reasons. Thus the maximum dimension of this implementation is 26 291 /// (assuming that the size of \c int is 32 bit). 184 292 /// 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 { 293 /// This graph type is fully conform to the \ref concepts::Graph 294 /// "Graph" concept, and it also has an important extra feature 295 /// that its maps are real \ref concepts::ReferenceMap 296 /// "reference map"s. 297 class HypercubeGraph : public ExtendedHypercubeGraphBase { 188 298 public: 189 299 190 typedef ExtendedHypercube DigraphBase Parent;191 192 /// \brief Construct a hypercube digraph with \c dim dimension.193 /// 194 /// Construct a hypercube digraph with \c dim dimension.195 Hypercube Digraph(int dim) { construct(dim); }196 197 /// \brief Gives back the number of thedimensions.198 /// 199 /// Gives back the number of thedimensions.300 typedef ExtendedHypercubeGraphBase Parent; 301 302 /// \brief Constructs a hypercube graph with \c dim dimensions. 303 /// 304 /// Constructs a hypercube graph with \c dim dimensions. 305 HypercubeGraph(int dim) { construct(dim); } 306 307 /// \brief The number of dimensions. 308 /// 309 /// Gives back the number of dimensions. 200 310 int dimension() const { 201 311 return Parent::dimension(); 202 312 } 203 313 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.314 /// \brief Returns \c true if the n'th bit of the node is one. 315 /// 316 /// Returns \c true if the n'th bit of the node is one. 207 317 bool projection(Node node, int n) const { 208 318 return Parent::projection(node, n); 209 319 } 210 320 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, dim1\} \f$ interval. 321 /// \brief The dimension id of an edge. 322 /// 323 /// Gives back the dimension id of the given edge. 324 /// It is in the [0..dim1] range. 325 int dimension(Edge edge) const { 326 return Parent::dimension(edge); 327 } 328 329 /// \brief The dimension id of an arc. 330 /// 331 /// Gives back the dimension id of the given arc. 332 /// It is in the [0..dim1] range. 215 333 int dimension(Arc arc) const { 216 334 return Parent::dimension(arc); 217 335 } 218 336 219 /// \brief Gives back the index of thenode.220 /// 221 /// Gives back the index of the node. The lower bits of the222 /// integer describes the node.337 /// \brief The index of a node. 338 /// 339 /// Gives back the index of the given node. 340 /// The lower bits of the integer describes the node. 223 341 int index(Node node) const { 224 342 return Parent::index(node); 225 343 } 226 344 227 /// \brief Gives back thenode by its index.228 /// 229 /// Gives back thenode by its index.345 /// \brief Gives back a node by its index. 346 /// 347 /// Gives back a node by its index. 230 348 Node operator()(int ix) const { 231 349 return Parent::operator()(ix); … … 234 352 /// \brief Number of nodes. 235 353 int nodeNum() const { return Parent::nodeNum(); } 354 /// \brief Number of edges. 355 int edgeNum() const { return Parent::edgeNum(); } 236 356 /// \brief Number of arcs. 237 357 int arcNum() const { return Parent::arcNum(); } … … 239 359 /// \brief Linear combination map. 240 360 /// 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. 361 /// This map makes possible to give back a linear combination 362 /// for each node. It works like the \c std::accumulate function, 363 /// so it accumulates the \c bf binary function with the \c fv first 364 /// value. The map accumulates only on that positions (dimensions) 365 /// where the index of the node is one. The values that have to be 366 /// accumulated should be given by the \c begin and \c end iterators 367 /// and the length of this range should be equal to the dimension 368 /// number of the graph. 248 369 /// 249 370 ///\code 250 371 /// const int DIM = 3; 251 /// Hypercube Digraph digraph(DIM);372 /// HypercubeGraph graph(DIM); 252 373 /// dim2::Point<double> base[DIM]; 253 374 /// for (int k = 0; k < DIM; ++k) { … … 255 376 /// base[k].y = rnd(); 256 377 /// } 257 /// Hypercube Digraph::HyperMap<dim2::Point<double> >258 /// pos( digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));378 /// HypercubeGraph::HyperMap<dim2::Point<double> > 379 /// pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0)); 259 380 ///\endcode 260 381 /// 261 /// \see Hypercube Digraph382 /// \see HypercubeGraph 262 383 template <typename T, typename BF = std::plus<T> > 263 384 class HyperMap { 264 385 public: 265 386 387 /// \brief The key type of the map 266 388 typedef Node Key; 389 /// \brief The value type of the map 267 390 typedef T Value; 268 269 391 270 392 /// \brief Constructor for HyperMap. 271 393 /// 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. 394 /// Construct a HyperMap for the given graph. The values that have 395 /// to be accumulated should be given by the \c begin and \c end 396 /// iterators and the length of this range should be equal to the 397 /// dimension number of the graph. 275 398 /// 276 /// This function accumulates the \c bf binary function with277 /// the \c fv first value. The map accumulates only on that dimensions278 /// where the node's indexis one.399 /// This map accumulates the \c bf binary function with the \c fv 400 /// first value on that positions (dimensions) where the index of 401 /// the node is one. 279 402 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)403 HyperMap(const Graph& graph, It begin, It end, 404 T fv = 0, const BF& bf = BF()) 405 : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) 283 406 { 284 LEMON_ASSERT(_values.size() == digraph.dimension(),285 "Wrong size of dimension");407 LEMON_ASSERT(_values.size() == graph.dimension(), 408 "Wrong size of range"); 286 409 } 287 410 288 /// \brief Gives back the partial accumulated value.411 /// \brief The partial accumulated value. 289 412 /// 290 413 /// Gives back the partial accumulated value. 291 Value operator[]( Keyk) const {414 Value operator[](const Key& k) const { 292 415 Value val = _first_value; 293 416 int id = _graph.index(k); … … 304 427 305 428 private: 306 const Digraph& _graph;429 const Graph& _graph; 307 430 std::vector<T> _values; 308 431 T _first_value;
Note: See TracChangeset
for help on using the changeset viewer.