1.1 --- a/lemon/hypercube_graph.h Wed Nov 05 21:36:28 2008 +0100
1.2 +++ b/lemon/hypercube_graph.h Thu Nov 06 15:16:37 2008 +0100
1.3 @@ -19,144 +19,250 @@
1.4 #ifndef HYPERCUBE_GRAPH_H
1.5 #define HYPERCUBE_GRAPH_H
1.6
1.7 -#include <iostream>
1.8 #include <vector>
1.9 #include <lemon/core.h>
1.10 -#include <lemon/error.h>
1.11 -
1.12 -#include <lemon/bits/base_extender.h>
1.13 +#include <lemon/assert.h>
1.14 #include <lemon/bits/graph_extender.h>
1.15
1.16 ///\ingroup graphs
1.17 ///\file
1.18 -///\brief HypercubeDigraph class.
1.19 +///\brief HypercubeGraph class.
1.20
1.21 namespace lemon {
1.22
1.23 - class HypercubeDigraphBase {
1.24 + class HypercubeGraphBase {
1.25
1.26 public:
1.27
1.28 - typedef HypercubeDigraphBase Digraph;
1.29 + typedef HypercubeGraphBase Graph;
1.30
1.31 class Node;
1.32 + class Edge;
1.33 class Arc;
1.34
1.35 public:
1.36
1.37 - HypercubeDigraphBase() {}
1.38 + HypercubeGraphBase() {}
1.39
1.40 protected:
1.41
1.42 void construct(int dim) {
1.43 + LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
1.44 _dim = dim;
1.45 - _nodeNum = 1 << dim;
1.46 + _node_num = 1 << dim;
1.47 + _edge_num = dim * (1 << dim-1);
1.48 }
1.49
1.50 public:
1.51
1.52 typedef True NodeNumTag;
1.53 + typedef True EdgeNumTag;
1.54 typedef True ArcNumTag;
1.55
1.56 - int nodeNum() const { return _nodeNum; }
1.57 - int arcNum() const { return _nodeNum * _dim; }
1.58 + int nodeNum() const { return _node_num; }
1.59 + int edgeNum() const { return _edge_num; }
1.60 + int arcNum() const { return 2 * _edge_num; }
1.61
1.62 - int maxNodeId() const { return nodeNum() - 1; }
1.63 - int maxArcId() const { return arcNum() - 1; }
1.64 + int maxNodeId() const { return _node_num - 1; }
1.65 + int maxEdgeId() const { return _edge_num - 1; }
1.66 + int maxArcId() const { return 2 * _edge_num - 1; }
1.67
1.68 - Node source(Arc e) const {
1.69 - return e.id / _dim;
1.70 + static Node nodeFromId(int id) { return Node(id); }
1.71 + static Edge edgeFromId(int id) { return Edge(id); }
1.72 + static Arc arcFromId(int id) { return Arc(id); }
1.73 +
1.74 + static int id(Node node) { return node._id; }
1.75 + static int id(Edge edge) { return edge._id; }
1.76 + static int id(Arc arc) { return arc._id; }
1.77 +
1.78 + Node u(Edge edge) const {
1.79 + int base = edge._id & ((1 << _dim-1) - 1);
1.80 + int k = edge._id >> _dim-1;
1.81 + return ((base >> k) << k+1) | (base & ((1 << k) - 1));
1.82 }
1.83
1.84 - Node target(Arc e) const {
1.85 - return (e.id / _dim) ^ (1 << (e.id % _dim));
1.86 + Node v(Edge edge) const {
1.87 + int base = edge._id & ((1 << _dim-1) - 1);
1.88 + int k = edge._id >> _dim-1;
1.89 + return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k);
1.90 }
1.91
1.92 - static int id(Node v) { return v.id; }
1.93 - static int id(Arc e) { return e.id; }
1.94 + Node source(Arc arc) const {
1.95 + return (arc._id & 1) == 1 ? u(arc) : v(arc);
1.96 + }
1.97
1.98 - static Node nodeFromId(int id) { return Node(id); }
1.99 + Node target(Arc arc) const {
1.100 + return (arc._id & 1) == 1 ? v(arc) : u(arc);
1.101 + }
1.102
1.103 - static Arc arcFromId(int id) { return Arc(id); }
1.104 + typedef True FindEdgeTag;
1.105 + typedef True FindArcTag;
1.106 +
1.107 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.108 + if (prev != INVALID) return INVALID;
1.109 + int d = u._id ^ v._id;
1.110 + int k = 0;
1.111 + if (d == 0) return INVALID;
1.112 + for ( ; (d & 1) == 0; d >>= 1) ++k;
1.113 + if (d >> 1 != 0) return INVALID;
1.114 + return (k << _dim-1) | ((u._id >> k+1) << k) | (u._id & ((1 << k) - 1));
1.115 + }
1.116 +
1.117 + Arc findArc(Node u, Node v, Arc prev = INVALID) const {
1.118 + Edge edge = findEdge(u, v, prev);
1.119 + if (edge == INVALID) return INVALID;
1.120 + int k = edge._id >> _dim-1;
1.121 + return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
1.122 + }
1.123
1.124 class Node {
1.125 - friend class HypercubeDigraphBase;
1.126 + friend class HypercubeGraphBase;
1.127 +
1.128 protected:
1.129 - int id;
1.130 - Node(int _id) { id = _id;}
1.131 + int _id;
1.132 + Node(int id) : _id(id) {}
1.133 public:
1.134 Node() {}
1.135 - Node (Invalid) { id = -1; }
1.136 - bool operator==(const Node node) const { return id == node.id; }
1.137 - bool operator!=(const Node node) const { return id != node.id; }
1.138 - bool operator<(const Node node) const { return id < node.id; }
1.139 + Node (Invalid) : _id(-1) {}
1.140 + bool operator==(const Node node) const {return _id == node._id;}
1.141 + bool operator!=(const Node node) const {return _id != node._id;}
1.142 + bool operator<(const Node node) const {return _id < node._id;}
1.143 + };
1.144 +
1.145 + class Edge {
1.146 + friend class HypercubeGraphBase;
1.147 + friend class Arc;
1.148 +
1.149 + protected:
1.150 + int _id;
1.151 +
1.152 + Edge(int id) : _id(id) {}
1.153 +
1.154 + public:
1.155 + Edge() {}
1.156 + Edge (Invalid) : _id(-1) {}
1.157 + bool operator==(const Edge edge) const {return _id == edge._id;}
1.158 + bool operator!=(const Edge edge) const {return _id != edge._id;}
1.159 + bool operator<(const Edge edge) const {return _id < edge._id;}
1.160 };
1.161
1.162 class Arc {
1.163 - friend class HypercubeDigraphBase;
1.164 + friend class HypercubeGraphBase;
1.165 +
1.166 protected:
1.167 - int id;
1.168 - Arc(int _id) : id(_id) {}
1.169 + int _id;
1.170 +
1.171 + Arc(int id) : _id(id) {}
1.172 +
1.173 public:
1.174 - Arc() { }
1.175 - Arc (Invalid) { id = -1; }
1.176 - bool operator==(const Arc arc) const { return id == arc.id; }
1.177 - bool operator!=(const Arc arc) const { return id != arc.id; }
1.178 - bool operator<(const Arc arc) const { return id < arc.id; }
1.179 + Arc() {}
1.180 + Arc (Invalid) : _id(-1) {}
1.181 + operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
1.182 + bool operator==(const Arc arc) const {return _id == arc._id;}
1.183 + bool operator!=(const Arc arc) const {return _id != arc._id;}
1.184 + bool operator<(const Arc arc) const {return _id < arc._id;}
1.185 };
1.186
1.187 void first(Node& node) const {
1.188 - node.id = nodeNum() - 1;
1.189 + node._id = _node_num - 1;
1.190 }
1.191
1.192 static void next(Node& node) {
1.193 - --node.id;
1.194 + --node._id;
1.195 + }
1.196 +
1.197 + void first(Edge& edge) const {
1.198 + edge._id = _edge_num - 1;
1.199 + }
1.200 +
1.201 + static void next(Edge& edge) {
1.202 + --edge._id;
1.203 }
1.204
1.205 void first(Arc& arc) const {
1.206 - arc.id = arcNum() - 1;
1.207 + arc._id = 2 * _edge_num - 1;
1.208 }
1.209
1.210 static void next(Arc& arc) {
1.211 - --arc.id;
1.212 + --arc._id;
1.213 + }
1.214 +
1.215 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
1.216 + edge._id = node._id >> 1;
1.217 + dir = (node._id & 1) == 0;
1.218 + }
1.219 +
1.220 + void nextInc(Edge& edge, bool& dir) const {
1.221 + Node n = dir ? u(edge) : v(edge);
1.222 + int k = (edge._id >> _dim-1) + 1;
1.223 + if (k < _dim) {
1.224 + edge._id = (k << _dim-1) |
1.225 + ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
1.226 + dir = ((n._id >> k) & 1) == 0;
1.227 + } else {
1.228 + edge._id = -1;
1.229 + dir = true;
1.230 + }
1.231 }
1.232
1.233 void firstOut(Arc& arc, const Node& node) const {
1.234 - arc.id = node.id * _dim;
1.235 + arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
1.236 }
1.237
1.238 void nextOut(Arc& arc) const {
1.239 - ++arc.id;
1.240 - if (arc.id % _dim == 0) arc.id = -1;
1.241 + Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
1.242 + int k = (arc._id >> _dim) + 1;
1.243 + if (k < _dim) {
1.244 + arc._id = (k << _dim-1) |
1.245 + ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
1.246 + arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
1.247 + } else {
1.248 + arc._id = -1;
1.249 + }
1.250 }
1.251
1.252 void firstIn(Arc& arc, const Node& node) const {
1.253 - arc.id = (node.id ^ 1) * _dim;
1.254 + arc._id = ((node._id >> 1) << 1) | (node._id & 1);
1.255 }
1.256
1.257 void nextIn(Arc& arc) const {
1.258 - int cnt = arc.id % _dim;
1.259 - if ((cnt + 1) % _dim == 0) {
1.260 - arc.id = -1;
1.261 + Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
1.262 + int k = (arc._id >> _dim) + 1;
1.263 + if (k < _dim) {
1.264 + arc._id = (k << _dim-1) |
1.265 + ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
1.266 + arc._id = (arc._id << 1) | ((n._id >> k) & 1);
1.267 } else {
1.268 - arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
1.269 + arc._id = -1;
1.270 }
1.271 }
1.272
1.273 + static bool direction(Arc arc) {
1.274 + return (arc._id & 1) == 1;
1.275 + }
1.276 +
1.277 + static Arc direct(Edge edge, bool dir) {
1.278 + return Arc((edge._id << 1) | (dir ? 1 : 0));
1.279 + }
1.280 +
1.281 int dimension() const {
1.282 return _dim;
1.283 }
1.284
1.285 bool projection(Node node, int n) const {
1.286 - return static_cast<bool>(node.id & (1 << n));
1.287 + return static_cast<bool>(node._id & (1 << n));
1.288 + }
1.289 +
1.290 + int dimension(Edge edge) const {
1.291 + return edge._id >> _dim-1;
1.292 }
1.293
1.294 int dimension(Arc arc) const {
1.295 - return arc.id % _dim;
1.296 + return arc._id >> _dim;
1.297 }
1.298
1.299 int index(Node node) const {
1.300 - return node.id;
1.301 + return node._id;
1.302 }
1.303
1.304 Node operator()(int ix) const {
1.305 @@ -164,131 +270,148 @@
1.306 }
1.307
1.308 private:
1.309 - int _dim, _nodeNum;
1.310 + int _dim;
1.311 + int _node_num, _edge_num;
1.312 };
1.313
1.314
1.315 - typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;
1.316 + typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
1.317
1.318 - /// \ingroup digraphs
1.319 + /// \ingroup graphs
1.320 ///
1.321 - /// \brief Hypercube digraph class
1.322 + /// \brief Hypercube graph class
1.323 ///
1.324 - /// This class implements a special digraph type. The nodes of the
1.325 - /// digraph are indiced with integers with at most \c dim binary digits.
1.326 - /// Two nodes are connected in the digraph if the indices differ only
1.327 - /// on one position in the binary form.
1.328 + /// This class implements a special graph type. The nodes of the graph
1.329 + /// are indiced with integers with at most \c dim binary digits.
1.330 + /// Two nodes are connected in the graph if and only if their indices
1.331 + /// differ only on one position in the binary form.
1.332 ///
1.333 - /// \note The type of the \c ids is chosen to \c int because efficiency
1.334 - /// reasons. Thus the maximum dimension of this implementation is 26.
1.335 + /// \note The type of the indices is chosen to \c int for efficiency
1.336 + /// reasons. Thus the maximum dimension of this implementation is 26
1.337 + /// (assuming that the size of \c int is 32 bit).
1.338 ///
1.339 - /// The digraph type is fully conform to the \ref concepts::Digraph
1.340 - /// concept but it does not conform to \ref concepts::Graph.
1.341 - class HypercubeDigraph : public ExtendedHypercubeDigraphBase {
1.342 + /// This graph type is fully conform to the \ref concepts::Graph
1.343 + /// "Graph" concept, and it also has an important extra feature
1.344 + /// that its maps are real \ref concepts::ReferenceMap
1.345 + /// "reference map"s.
1.346 + class HypercubeGraph : public ExtendedHypercubeGraphBase {
1.347 public:
1.348
1.349 - typedef ExtendedHypercubeDigraphBase Parent;
1.350 + typedef ExtendedHypercubeGraphBase Parent;
1.351
1.352 - /// \brief Construct a hypercube digraph with \c dim dimension.
1.353 + /// \brief Constructs a hypercube graph with \c dim dimensions.
1.354 ///
1.355 - /// Construct a hypercube digraph with \c dim dimension.
1.356 - HypercubeDigraph(int dim) { construct(dim); }
1.357 + /// Constructs a hypercube graph with \c dim dimensions.
1.358 + HypercubeGraph(int dim) { construct(dim); }
1.359
1.360 - /// \brief Gives back the number of the dimensions.
1.361 + /// \brief The number of dimensions.
1.362 ///
1.363 - /// Gives back the number of the dimensions.
1.364 + /// Gives back the number of dimensions.
1.365 int dimension() const {
1.366 return Parent::dimension();
1.367 }
1.368
1.369 - /// \brief Returns true if the n'th bit of the node is one.
1.370 + /// \brief Returns \c true if the n'th bit of the node is one.
1.371 ///
1.372 - /// Returns true if the n'th bit of the node is one.
1.373 + /// Returns \c true if the n'th bit of the node is one.
1.374 bool projection(Node node, int n) const {
1.375 return Parent::projection(node, n);
1.376 }
1.377
1.378 - /// \brief The dimension id of the arc.
1.379 + /// \brief The dimension id of an edge.
1.380 ///
1.381 - /// It returns the dimension id of the arc. It can
1.382 - /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval.
1.383 + /// Gives back the dimension id of the given edge.
1.384 + /// It is in the [0..dim-1] range.
1.385 + int dimension(Edge edge) const {
1.386 + return Parent::dimension(edge);
1.387 + }
1.388 +
1.389 + /// \brief The dimension id of an arc.
1.390 + ///
1.391 + /// Gives back the dimension id of the given arc.
1.392 + /// It is in the [0..dim-1] range.
1.393 int dimension(Arc arc) const {
1.394 return Parent::dimension(arc);
1.395 }
1.396
1.397 - /// \brief Gives back the index of the node.
1.398 + /// \brief The index of a node.
1.399 ///
1.400 - /// Gives back the index of the node. The lower bits of the
1.401 - /// integer describes the node.
1.402 + /// Gives back the index of the given node.
1.403 + /// The lower bits of the integer describes the node.
1.404 int index(Node node) const {
1.405 return Parent::index(node);
1.406 }
1.407
1.408 - /// \brief Gives back the node by its index.
1.409 + /// \brief Gives back a node by its index.
1.410 ///
1.411 - /// Gives back the node by its index.
1.412 + /// Gives back a node by its index.
1.413 Node operator()(int ix) const {
1.414 return Parent::operator()(ix);
1.415 }
1.416
1.417 /// \brief Number of nodes.
1.418 int nodeNum() const { return Parent::nodeNum(); }
1.419 + /// \brief Number of edges.
1.420 + int edgeNum() const { return Parent::edgeNum(); }
1.421 /// \brief Number of arcs.
1.422 int arcNum() const { return Parent::arcNum(); }
1.423
1.424 /// \brief Linear combination map.
1.425 ///
1.426 - /// It makes possible to give back a linear combination
1.427 - /// for each node. This function works like the \c std::accumulate
1.428 - /// so it accumulates the \c bf binary function with the \c fv
1.429 - /// first value. The map accumulates only on that dimensions where
1.430 - /// the node's index is one. The accumulated values should be
1.431 - /// given by the \c begin and \c end iterators and the length of this
1.432 - /// range should be equal to the dimension number of the digraph.
1.433 + /// This map makes possible to give back a linear combination
1.434 + /// for each node. It works like the \c std::accumulate function,
1.435 + /// so it accumulates the \c bf binary function with the \c fv first
1.436 + /// value. The map accumulates only on that positions (dimensions)
1.437 + /// where the index of the node is one. The values that have to be
1.438 + /// accumulated should be given by the \c begin and \c end iterators
1.439 + /// and the length of this range should be equal to the dimension
1.440 + /// number of the graph.
1.441 ///
1.442 ///\code
1.443 /// const int DIM = 3;
1.444 - /// HypercubeDigraph digraph(DIM);
1.445 + /// HypercubeGraph graph(DIM);
1.446 /// dim2::Point<double> base[DIM];
1.447 /// for (int k = 0; k < DIM; ++k) {
1.448 /// base[k].x = rnd();
1.449 /// base[k].y = rnd();
1.450 /// }
1.451 - /// HypercubeDigraph::HyperMap<dim2::Point<double> >
1.452 - /// pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
1.453 + /// HypercubeGraph::HyperMap<dim2::Point<double> >
1.454 + /// pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
1.455 ///\endcode
1.456 ///
1.457 - /// \see HypercubeDigraph
1.458 + /// \see HypercubeGraph
1.459 template <typename T, typename BF = std::plus<T> >
1.460 class HyperMap {
1.461 public:
1.462
1.463 + /// \brief The key type of the map
1.464 typedef Node Key;
1.465 + /// \brief The value type of the map
1.466 typedef T Value;
1.467
1.468 -
1.469 /// \brief Constructor for HyperMap.
1.470 ///
1.471 - /// Construct a HyperMap for the given digraph. The accumulated values
1.472 - /// should be given by the \c begin and \c end iterators and the length
1.473 - /// of this range should be equal to the dimension number of the digraph.
1.474 + /// Construct a HyperMap for the given graph. The values that have
1.475 + /// to be accumulated should be given by the \c begin and \c end
1.476 + /// iterators and the length of this range should be equal to the
1.477 + /// dimension number of the graph.
1.478 ///
1.479 - /// This function accumulates the \c bf binary function with
1.480 - /// the \c fv first value. The map accumulates only on that dimensions
1.481 - /// where the node's index is one.
1.482 + /// This map accumulates the \c bf binary function with the \c fv
1.483 + /// first value on that positions (dimensions) where the index of
1.484 + /// the node is one.
1.485 template <typename It>
1.486 - HyperMap(const Digraph& digraph, It begin, It end,
1.487 - T fv = 0.0, const BF& bf = BF())
1.488 - : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf)
1.489 + HyperMap(const Graph& graph, It begin, It end,
1.490 + T fv = 0, const BF& bf = BF())
1.491 + : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
1.492 {
1.493 - LEMON_ASSERT(_values.size() == digraph.dimension(),
1.494 - "Wrong size of dimension");
1.495 + LEMON_ASSERT(_values.size() == graph.dimension(),
1.496 + "Wrong size of range");
1.497 }
1.498
1.499 - /// \brief Gives back the partial accumulated value.
1.500 + /// \brief The partial accumulated value.
1.501 ///
1.502 /// Gives back the partial accumulated value.
1.503 - Value operator[](Key k) const {
1.504 + Value operator[](const Key& k) const {
1.505 Value val = _first_value;
1.506 int id = _graph.index(k);
1.507 int n = 0;
1.508 @@ -303,7 +426,7 @@
1.509 }
1.510
1.511 private:
1.512 - const Digraph& _graph;
1.513 + const Graph& _graph;
1.514 std::vector<T> _values;
1.515 T _first_value;
1.516 BF _bin_func;