1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/hypercube_graph.h Wed Nov 05 21:36:28 2008 +0100
1.3 @@ -0,0 +1,316 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef HYPERCUBE_GRAPH_H
1.23 +#define HYPERCUBE_GRAPH_H
1.24 +
1.25 +#include <iostream>
1.26 +#include <vector>
1.27 +#include <lemon/core.h>
1.28 +#include <lemon/error.h>
1.29 +
1.30 +#include <lemon/bits/base_extender.h>
1.31 +#include <lemon/bits/graph_extender.h>
1.32 +
1.33 +///\ingroup graphs
1.34 +///\file
1.35 +///\brief HypercubeDigraph class.
1.36 +
1.37 +namespace lemon {
1.38 +
1.39 + class HypercubeDigraphBase {
1.40 +
1.41 + public:
1.42 +
1.43 + typedef HypercubeDigraphBase Digraph;
1.44 +
1.45 + class Node;
1.46 + class Arc;
1.47 +
1.48 + public:
1.49 +
1.50 + HypercubeDigraphBase() {}
1.51 +
1.52 + protected:
1.53 +
1.54 + void construct(int dim) {
1.55 + _dim = dim;
1.56 + _nodeNum = 1 << dim;
1.57 + }
1.58 +
1.59 + public:
1.60 +
1.61 + typedef True NodeNumTag;
1.62 + typedef True ArcNumTag;
1.63 +
1.64 + int nodeNum() const { return _nodeNum; }
1.65 + int arcNum() const { return _nodeNum * _dim; }
1.66 +
1.67 + int maxNodeId() const { return nodeNum() - 1; }
1.68 + int maxArcId() const { return arcNum() - 1; }
1.69 +
1.70 + Node source(Arc e) const {
1.71 + return e.id / _dim;
1.72 + }
1.73 +
1.74 + Node target(Arc e) const {
1.75 + return (e.id / _dim) ^ (1 << (e.id % _dim));
1.76 + }
1.77 +
1.78 + static int id(Node v) { return v.id; }
1.79 + static int id(Arc e) { return e.id; }
1.80 +
1.81 + static Node nodeFromId(int id) { return Node(id); }
1.82 +
1.83 + static Arc arcFromId(int id) { return Arc(id); }
1.84 +
1.85 + class Node {
1.86 + friend class HypercubeDigraphBase;
1.87 + protected:
1.88 + int id;
1.89 + Node(int _id) { id = _id;}
1.90 + public:
1.91 + Node() {}
1.92 + Node (Invalid) { id = -1; }
1.93 + bool operator==(const Node node) const { return id == node.id; }
1.94 + bool operator!=(const Node node) const { return id != node.id; }
1.95 + bool operator<(const Node node) const { return id < node.id; }
1.96 + };
1.97 +
1.98 + class Arc {
1.99 + friend class HypercubeDigraphBase;
1.100 + protected:
1.101 + int id;
1.102 + Arc(int _id) : id(_id) {}
1.103 + public:
1.104 + Arc() { }
1.105 + Arc (Invalid) { id = -1; }
1.106 + bool operator==(const Arc arc) const { return id == arc.id; }
1.107 + bool operator!=(const Arc arc) const { return id != arc.id; }
1.108 + bool operator<(const Arc arc) const { return id < arc.id; }
1.109 + };
1.110 +
1.111 + void first(Node& node) const {
1.112 + node.id = nodeNum() - 1;
1.113 + }
1.114 +
1.115 + static void next(Node& node) {
1.116 + --node.id;
1.117 + }
1.118 +
1.119 + void first(Arc& arc) const {
1.120 + arc.id = arcNum() - 1;
1.121 + }
1.122 +
1.123 + static void next(Arc& arc) {
1.124 + --arc.id;
1.125 + }
1.126 +
1.127 + void firstOut(Arc& arc, const Node& node) const {
1.128 + arc.id = node.id * _dim;
1.129 + }
1.130 +
1.131 + void nextOut(Arc& arc) const {
1.132 + ++arc.id;
1.133 + if (arc.id % _dim == 0) arc.id = -1;
1.134 + }
1.135 +
1.136 + void firstIn(Arc& arc, const Node& node) const {
1.137 + arc.id = (node.id ^ 1) * _dim;
1.138 + }
1.139 +
1.140 + void nextIn(Arc& arc) const {
1.141 + int cnt = arc.id % _dim;
1.142 + if ((cnt + 1) % _dim == 0) {
1.143 + arc.id = -1;
1.144 + } else {
1.145 + arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
1.146 + }
1.147 + }
1.148 +
1.149 + int dimension() const {
1.150 + return _dim;
1.151 + }
1.152 +
1.153 + bool projection(Node node, int n) const {
1.154 + return static_cast<bool>(node.id & (1 << n));
1.155 + }
1.156 +
1.157 + int dimension(Arc arc) const {
1.158 + return arc.id % _dim;
1.159 + }
1.160 +
1.161 + int index(Node node) const {
1.162 + return node.id;
1.163 + }
1.164 +
1.165 + Node operator()(int ix) const {
1.166 + return Node(ix);
1.167 + }
1.168 +
1.169 + private:
1.170 + int _dim, _nodeNum;
1.171 + };
1.172 +
1.173 +
1.174 + typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;
1.175 +
1.176 + /// \ingroup digraphs
1.177 + ///
1.178 + /// \brief Hypercube digraph class
1.179 + ///
1.180 + /// This class implements a special digraph type. The nodes of the
1.181 + /// digraph are indiced with integers with at most \c dim binary digits.
1.182 + /// Two nodes are connected in the digraph if the indices differ only
1.183 + /// on one position in the binary form.
1.184 + ///
1.185 + /// \note The type of the \c ids is chosen to \c int because efficiency
1.186 + /// reasons. Thus the maximum dimension of this implementation is 26.
1.187 + ///
1.188 + /// The digraph type is fully conform to the \ref concepts::Digraph
1.189 + /// concept but it does not conform to \ref concepts::Graph.
1.190 + class HypercubeDigraph : public ExtendedHypercubeDigraphBase {
1.191 + public:
1.192 +
1.193 + typedef ExtendedHypercubeDigraphBase Parent;
1.194 +
1.195 + /// \brief Construct a hypercube digraph with \c dim dimension.
1.196 + ///
1.197 + /// Construct a hypercube digraph with \c dim dimension.
1.198 + HypercubeDigraph(int dim) { construct(dim); }
1.199 +
1.200 + /// \brief Gives back the number of the dimensions.
1.201 + ///
1.202 + /// Gives back the number of the dimensions.
1.203 + int dimension() const {
1.204 + return Parent::dimension();
1.205 + }
1.206 +
1.207 + /// \brief Returns true if the n'th bit of the node is one.
1.208 + ///
1.209 + /// Returns true if the n'th bit of the node is one.
1.210 + bool projection(Node node, int n) const {
1.211 + return Parent::projection(node, n);
1.212 + }
1.213 +
1.214 + /// \brief The dimension id of the arc.
1.215 + ///
1.216 + /// It returns the dimension id of the arc. It can
1.217 + /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval.
1.218 + int dimension(Arc arc) const {
1.219 + return Parent::dimension(arc);
1.220 + }
1.221 +
1.222 + /// \brief Gives back the index of the node.
1.223 + ///
1.224 + /// Gives back the index of the node. The lower bits of the
1.225 + /// integer describes the node.
1.226 + int index(Node node) const {
1.227 + return Parent::index(node);
1.228 + }
1.229 +
1.230 + /// \brief Gives back the node by its index.
1.231 + ///
1.232 + /// Gives back the node by its index.
1.233 + Node operator()(int ix) const {
1.234 + return Parent::operator()(ix);
1.235 + }
1.236 +
1.237 + /// \brief Number of nodes.
1.238 + int nodeNum() const { return Parent::nodeNum(); }
1.239 + /// \brief Number of arcs.
1.240 + int arcNum() const { return Parent::arcNum(); }
1.241 +
1.242 + /// \brief Linear combination map.
1.243 + ///
1.244 + /// It makes possible to give back a linear combination
1.245 + /// for each node. This function works like the \c std::accumulate
1.246 + /// so it accumulates the \c bf binary function with the \c fv
1.247 + /// first value. The map accumulates only on that dimensions where
1.248 + /// the node's index is one. The accumulated values should be
1.249 + /// given by the \c begin and \c end iterators and the length of this
1.250 + /// range should be equal to the dimension number of the digraph.
1.251 + ///
1.252 + ///\code
1.253 + /// const int DIM = 3;
1.254 + /// HypercubeDigraph digraph(DIM);
1.255 + /// dim2::Point<double> base[DIM];
1.256 + /// for (int k = 0; k < DIM; ++k) {
1.257 + /// base[k].x = rnd();
1.258 + /// base[k].y = rnd();
1.259 + /// }
1.260 + /// HypercubeDigraph::HyperMap<dim2::Point<double> >
1.261 + /// pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
1.262 + ///\endcode
1.263 + ///
1.264 + /// \see HypercubeDigraph
1.265 + template <typename T, typename BF = std::plus<T> >
1.266 + class HyperMap {
1.267 + public:
1.268 +
1.269 + typedef Node Key;
1.270 + typedef T Value;
1.271 +
1.272 +
1.273 + /// \brief Constructor for HyperMap.
1.274 + ///
1.275 + /// Construct a HyperMap for the given digraph. The accumulated values
1.276 + /// should be given by the \c begin and \c end iterators and the length
1.277 + /// of this range should be equal to the dimension number of the digraph.
1.278 + ///
1.279 + /// This function accumulates the \c bf binary function with
1.280 + /// the \c fv first value. The map accumulates only on that dimensions
1.281 + /// where the node's index is one.
1.282 + template <typename It>
1.283 + HyperMap(const Digraph& digraph, It begin, It end,
1.284 + T fv = 0.0, const BF& bf = BF())
1.285 + : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf)
1.286 + {
1.287 + LEMON_ASSERT(_values.size() == digraph.dimension(),
1.288 + "Wrong size of dimension");
1.289 + }
1.290 +
1.291 + /// \brief Gives back the partial accumulated value.
1.292 + ///
1.293 + /// Gives back the partial accumulated value.
1.294 + Value operator[](Key k) const {
1.295 + Value val = _first_value;
1.296 + int id = _graph.index(k);
1.297 + int n = 0;
1.298 + while (id != 0) {
1.299 + if (id & 1) {
1.300 + val = _bin_func(val, _values[n]);
1.301 + }
1.302 + id >>= 1;
1.303 + ++n;
1.304 + }
1.305 + return val;
1.306 + }
1.307 +
1.308 + private:
1.309 + const Digraph& _graph;
1.310 + std::vector<T> _values;
1.311 + T _first_value;
1.312 + BF _bin_func;
1.313 + };
1.314 +
1.315 + };
1.316 +
1.317 +}
1.318 +
1.319 +#endif