lemon/hypercube_graph.h
changeset 784 1a7fe3bef514
parent 778 a143f19f465b
parent 737 9d6c3e8b2421
child 787 c2230649a493
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/hypercube_graph.h	Thu Nov 05 15:50:01 2009 +0100
     1.3 @@ -0,0 +1,457 @@
     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-2009
     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 <vector>
    1.26 +#include <lemon/core.h>
    1.27 +#include <lemon/assert.h>
    1.28 +#include <lemon/bits/graph_extender.h>
    1.29 +
    1.30 +///\ingroup graphs
    1.31 +///\file
    1.32 +///\brief HypercubeGraph class.
    1.33 +
    1.34 +namespace lemon {
    1.35 +
    1.36 +  class HypercubeGraphBase {
    1.37 +
    1.38 +  public:
    1.39 +
    1.40 +    typedef HypercubeGraphBase Graph;
    1.41 +
    1.42 +    class Node;
    1.43 +    class Edge;
    1.44 +    class Arc;
    1.45 +
    1.46 +  public:
    1.47 +
    1.48 +    HypercubeGraphBase() {}
    1.49 +
    1.50 +  protected:
    1.51 +
    1.52 +    void construct(int dim) {
    1.53 +      LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
    1.54 +      _dim = dim;
    1.55 +      _node_num = 1 << dim;
    1.56 +      _edge_num = dim * (1 << (dim-1));
    1.57 +    }
    1.58 +
    1.59 +  public:
    1.60 +
    1.61 +    typedef True NodeNumTag;
    1.62 +    typedef True EdgeNumTag;
    1.63 +    typedef True ArcNumTag;
    1.64 +
    1.65 +    int nodeNum() const { return _node_num; }
    1.66 +    int edgeNum() const { return _edge_num; }
    1.67 +    int arcNum() const { return 2 * _edge_num; }
    1.68 +
    1.69 +    int maxNodeId() const { return _node_num - 1; }
    1.70 +    int maxEdgeId() const { return _edge_num - 1; }
    1.71 +    int maxArcId() const { return 2 * _edge_num - 1; }
    1.72 +
    1.73 +    static Node nodeFromId(int id) { return Node(id); }
    1.74 +    static Edge edgeFromId(int id) { return Edge(id); }
    1.75 +    static Arc arcFromId(int id) { return Arc(id); }
    1.76 +
    1.77 +    static int id(Node node) { return node._id; }
    1.78 +    static int id(Edge edge) { return edge._id; }
    1.79 +    static int id(Arc arc) { return arc._id; }
    1.80 +
    1.81 +    Node u(Edge edge) const {
    1.82 +      int base = edge._id & ((1 << (_dim-1)) - 1);
    1.83 +      int k = edge._id >> (_dim-1);
    1.84 +      return ((base >> k) << (k+1)) | (base & ((1 << k) - 1));
    1.85 +    }
    1.86 +
    1.87 +    Node v(Edge edge) const {
    1.88 +      int base = edge._id & ((1 << (_dim-1)) - 1);
    1.89 +      int k = edge._id >> (_dim-1);
    1.90 +      return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)) | (1 << k);
    1.91 +    }
    1.92 +
    1.93 +    Node source(Arc arc) const {
    1.94 +      return (arc._id & 1) == 1 ? u(arc) : v(arc);
    1.95 +    }
    1.96 +
    1.97 +    Node target(Arc arc) const {
    1.98 +      return (arc._id & 1) == 1 ? v(arc) : u(arc);
    1.99 +    }
   1.100 +
   1.101 +    typedef True FindEdgeTag;
   1.102 +    typedef True FindArcTag;
   1.103 +
   1.104 +    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   1.105 +      if (prev != INVALID) return INVALID;
   1.106 +      int d = u._id ^ v._id;
   1.107 +      int k = 0;
   1.108 +      if (d == 0) return INVALID;
   1.109 +      for ( ; (d & 1) == 0; d >>= 1) ++k;
   1.110 +      if (d >> 1 != 0) return INVALID;
   1.111 +      return (k << (_dim-1)) | ((u._id >> (k+1)) << k) |
   1.112 +        (u._id & ((1 << k) - 1));
   1.113 +    }
   1.114 +
   1.115 +    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
   1.116 +      Edge edge = findEdge(u, v, prev);
   1.117 +      if (edge == INVALID) return INVALID;
   1.118 +      int k = edge._id >> (_dim-1);
   1.119 +      return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
   1.120 +    }
   1.121 +
   1.122 +    class Node {
   1.123 +      friend class HypercubeGraphBase;
   1.124 +
   1.125 +    protected:
   1.126 +      int _id;
   1.127 +      Node(int id) : _id(id) {}
   1.128 +    public:
   1.129 +      Node() {}
   1.130 +      Node (Invalid) : _id(-1) {}
   1.131 +      bool operator==(const Node node) const {return _id == node._id;}
   1.132 +      bool operator!=(const Node node) const {return _id != node._id;}
   1.133 +      bool operator<(const Node node) const {return _id < node._id;}
   1.134 +    };
   1.135 +
   1.136 +    class Edge {
   1.137 +      friend class HypercubeGraphBase;
   1.138 +      friend class Arc;
   1.139 +
   1.140 +    protected:
   1.141 +      int _id;
   1.142 +
   1.143 +      Edge(int id) : _id(id) {}
   1.144 +
   1.145 +    public:
   1.146 +      Edge() {}
   1.147 +      Edge (Invalid) : _id(-1) {}
   1.148 +      bool operator==(const Edge edge) const {return _id == edge._id;}
   1.149 +      bool operator!=(const Edge edge) const {return _id != edge._id;}
   1.150 +      bool operator<(const Edge edge) const {return _id < edge._id;}
   1.151 +    };
   1.152 +
   1.153 +    class Arc {
   1.154 +      friend class HypercubeGraphBase;
   1.155 +
   1.156 +    protected:
   1.157 +      int _id;
   1.158 +
   1.159 +      Arc(int id) : _id(id) {}
   1.160 +
   1.161 +    public:
   1.162 +      Arc() {}
   1.163 +      Arc (Invalid) : _id(-1) {}
   1.164 +      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
   1.165 +      bool operator==(const Arc arc) const {return _id == arc._id;}
   1.166 +      bool operator!=(const Arc arc) const {return _id != arc._id;}
   1.167 +      bool operator<(const Arc arc) const {return _id < arc._id;}
   1.168 +    };
   1.169 +
   1.170 +    void first(Node& node) const {
   1.171 +      node._id = _node_num - 1;
   1.172 +    }
   1.173 +
   1.174 +    static void next(Node& node) {
   1.175 +      --node._id;
   1.176 +    }
   1.177 +
   1.178 +    void first(Edge& edge) const {
   1.179 +      edge._id = _edge_num - 1;
   1.180 +    }
   1.181 +
   1.182 +    static void next(Edge& edge) {
   1.183 +      --edge._id;
   1.184 +    }
   1.185 +
   1.186 +    void first(Arc& arc) const {
   1.187 +      arc._id = 2 * _edge_num - 1;
   1.188 +    }
   1.189 +
   1.190 +    static void next(Arc& arc) {
   1.191 +      --arc._id;
   1.192 +    }
   1.193 +
   1.194 +    void firstInc(Edge& edge, bool& dir, const Node& node) const {
   1.195 +      edge._id = node._id >> 1;
   1.196 +      dir = (node._id & 1) == 0;
   1.197 +    }
   1.198 +
   1.199 +    void nextInc(Edge& edge, bool& dir) const {
   1.200 +      Node n = dir ? u(edge) : v(edge);
   1.201 +      int k = (edge._id >> (_dim-1)) + 1;
   1.202 +      if (k < _dim) {
   1.203 +        edge._id = (k << (_dim-1)) |
   1.204 +          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
   1.205 +        dir = ((n._id >> k) & 1) == 0;
   1.206 +      } else {
   1.207 +        edge._id = -1;
   1.208 +        dir = true;
   1.209 +      }
   1.210 +    }
   1.211 +
   1.212 +    void firstOut(Arc& arc, const Node& node) const {
   1.213 +      arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
   1.214 +    }
   1.215 +
   1.216 +    void nextOut(Arc& arc) const {
   1.217 +      Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
   1.218 +      int k = (arc._id >> _dim) + 1;
   1.219 +      if (k < _dim) {
   1.220 +        arc._id = (k << (_dim-1)) |
   1.221 +          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
   1.222 +        arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
   1.223 +      } else {
   1.224 +        arc._id = -1;
   1.225 +      }
   1.226 +    }
   1.227 +
   1.228 +    void firstIn(Arc& arc, const Node& node) const {
   1.229 +      arc._id = ((node._id >> 1) << 1) | (node._id & 1);
   1.230 +    }
   1.231 +
   1.232 +    void nextIn(Arc& arc) const {
   1.233 +      Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
   1.234 +      int k = (arc._id >> _dim) + 1;
   1.235 +      if (k < _dim) {
   1.236 +        arc._id = (k << (_dim-1)) |
   1.237 +          ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
   1.238 +        arc._id = (arc._id << 1) | ((n._id >> k) & 1);
   1.239 +      } else {
   1.240 +        arc._id = -1;
   1.241 +      }
   1.242 +    }
   1.243 +
   1.244 +    static bool direction(Arc arc) {
   1.245 +      return (arc._id & 1) == 1;
   1.246 +    }
   1.247 +
   1.248 +    static Arc direct(Edge edge, bool dir) {
   1.249 +      return Arc((edge._id << 1) | (dir ? 1 : 0));
   1.250 +    }
   1.251 +
   1.252 +    int dimension() const {
   1.253 +      return _dim;
   1.254 +    }
   1.255 +
   1.256 +    bool projection(Node node, int n) const {
   1.257 +      return static_cast<bool>(node._id & (1 << n));
   1.258 +    }
   1.259 +
   1.260 +    int dimension(Edge edge) const {
   1.261 +      return edge._id >> (_dim-1);
   1.262 +    }
   1.263 +
   1.264 +    int dimension(Arc arc) const {
   1.265 +      return arc._id >> _dim;
   1.266 +    }
   1.267 +
   1.268 +    static int index(Node node) {
   1.269 +      return node._id;
   1.270 +    }
   1.271 +
   1.272 +    Node operator()(int ix) const {
   1.273 +      return Node(ix);
   1.274 +    }
   1.275 +
   1.276 +  private:
   1.277 +    int _dim;
   1.278 +    int _node_num, _edge_num;
   1.279 +  };
   1.280 +
   1.281 +
   1.282 +  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
   1.283 +
   1.284 +  /// \ingroup graphs
   1.285 +  ///
   1.286 +  /// \brief Hypercube graph class
   1.287 +  ///
   1.288 +  /// HypercubeGraph implements a special graph type. The nodes of the
   1.289 +  /// graph are indexed with integers having at most \c dim binary digits.
   1.290 +  /// Two nodes are connected in the graph if and only if their indices
   1.291 +  /// differ only on one position in the binary form.
   1.292 +  /// This class is completely static and it needs constant memory space.
   1.293 +  /// Thus you can neither add nor delete nodes or edges, however 
   1.294 +  /// the structure can be resized using resize().
   1.295 +  ///
   1.296 +  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
   1.297 +  /// Most of its member functions and nested classes are documented
   1.298 +  /// only in the concept class.
   1.299 +  ///
   1.300 +  /// \note The type of the indices is chosen to \c int for efficiency
   1.301 +  /// reasons. Thus the maximum dimension of this implementation is 26
   1.302 +  /// (assuming that the size of \c int is 32 bit).
   1.303 +  class HypercubeGraph : public ExtendedHypercubeGraphBase {
   1.304 +    typedef ExtendedHypercubeGraphBase Parent;
   1.305 +
   1.306 +  public:
   1.307 +
   1.308 +    /// \brief Constructs a hypercube graph with \c dim dimensions.
   1.309 +    ///
   1.310 +    /// Constructs a hypercube graph with \c dim dimensions.
   1.311 +    HypercubeGraph(int dim) { construct(dim); }
   1.312 +
   1.313 +    /// \brief Resizes the graph
   1.314 +    ///
   1.315 +    /// This function resizes the graph. It fully destroys and
   1.316 +    /// rebuilds the structure, therefore the maps of the graph will be
   1.317 +    /// reallocated automatically and the previous values will be lost.
   1.318 +    void resize(int dim) {
   1.319 +      Parent::notifier(Arc()).clear();
   1.320 +      Parent::notifier(Edge()).clear();
   1.321 +      Parent::notifier(Node()).clear();
   1.322 +      construct(dim);
   1.323 +      Parent::notifier(Node()).build();
   1.324 +      Parent::notifier(Edge()).build();
   1.325 +      Parent::notifier(Arc()).build();
   1.326 +    }
   1.327 +
   1.328 +    /// \brief The number of dimensions.
   1.329 +    ///
   1.330 +    /// Gives back the number of dimensions.
   1.331 +    int dimension() const {
   1.332 +      return Parent::dimension();
   1.333 +    }
   1.334 +
   1.335 +    /// \brief Returns \c true if the n'th bit of the node is one.
   1.336 +    ///
   1.337 +    /// Returns \c true if the n'th bit of the node is one.
   1.338 +    bool projection(Node node, int n) const {
   1.339 +      return Parent::projection(node, n);
   1.340 +    }
   1.341 +
   1.342 +    /// \brief The dimension id of an edge.
   1.343 +    ///
   1.344 +    /// Gives back the dimension id of the given edge.
   1.345 +    /// It is in the range <tt>[0..dim-1]</tt>.
   1.346 +    int dimension(Edge edge) const {
   1.347 +      return Parent::dimension(edge);
   1.348 +    }
   1.349 +
   1.350 +    /// \brief The dimension id of an arc.
   1.351 +    ///
   1.352 +    /// Gives back the dimension id of the given arc.
   1.353 +    /// It is in the range <tt>[0..dim-1]</tt>.
   1.354 +    int dimension(Arc arc) const {
   1.355 +      return Parent::dimension(arc);
   1.356 +    }
   1.357 +
   1.358 +    /// \brief The index of a node.
   1.359 +    ///
   1.360 +    /// Gives back the index of the given node.
   1.361 +    /// The lower bits of the integer describes the node.
   1.362 +    static int index(Node node) {
   1.363 +      return Parent::index(node);
   1.364 +    }
   1.365 +
   1.366 +    /// \brief Gives back a node by its index.
   1.367 +    ///
   1.368 +    /// Gives back a node by its index.
   1.369 +    Node operator()(int ix) const {
   1.370 +      return Parent::operator()(ix);
   1.371 +    }
   1.372 +
   1.373 +    /// \brief Number of nodes.
   1.374 +    int nodeNum() const { return Parent::nodeNum(); }
   1.375 +    /// \brief Number of edges.
   1.376 +    int edgeNum() const { return Parent::edgeNum(); }
   1.377 +    /// \brief Number of arcs.
   1.378 +    int arcNum() const { return Parent::arcNum(); }
   1.379 +
   1.380 +    /// \brief Linear combination map.
   1.381 +    ///
   1.382 +    /// This map makes possible to give back a linear combination
   1.383 +    /// for each node. It works like the \c std::accumulate function,
   1.384 +    /// so it accumulates the \c bf binary function with the \c fv first
   1.385 +    /// value. The map accumulates only on that positions (dimensions)
   1.386 +    /// where the index of the node is one. The values that have to be
   1.387 +    /// accumulated should be given by the \c begin and \c end iterators
   1.388 +    /// and the length of this range should be equal to the dimension
   1.389 +    /// number of the graph.
   1.390 +    ///
   1.391 +    ///\code
   1.392 +    /// const int DIM = 3;
   1.393 +    /// HypercubeGraph graph(DIM);
   1.394 +    /// dim2::Point<double> base[DIM];
   1.395 +    /// for (int k = 0; k < DIM; ++k) {
   1.396 +    ///   base[k].x = rnd();
   1.397 +    ///   base[k].y = rnd();
   1.398 +    /// }
   1.399 +    /// HypercubeGraph::HyperMap<dim2::Point<double> >
   1.400 +    ///   pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
   1.401 +    ///\endcode
   1.402 +    ///
   1.403 +    /// \see HypercubeGraph
   1.404 +    template <typename T, typename BF = std::plus<T> >
   1.405 +    class HyperMap {
   1.406 +    public:
   1.407 +
   1.408 +      /// \brief The key type of the map
   1.409 +      typedef Node Key;
   1.410 +      /// \brief The value type of the map
   1.411 +      typedef T Value;
   1.412 +
   1.413 +      /// \brief Constructor for HyperMap.
   1.414 +      ///
   1.415 +      /// Construct a HyperMap for the given graph. The values that have
   1.416 +      /// to be accumulated should be given by the \c begin and \c end
   1.417 +      /// iterators and the length of this range should be equal to the
   1.418 +      /// dimension number of the graph.
   1.419 +      ///
   1.420 +      /// This map accumulates the \c bf binary function with the \c fv
   1.421 +      /// first value on that positions (dimensions) where the index of
   1.422 +      /// the node is one.
   1.423 +      template <typename It>
   1.424 +      HyperMap(const Graph& graph, It begin, It end,
   1.425 +               T fv = 0, const BF& bf = BF())
   1.426 +        : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
   1.427 +      {
   1.428 +        LEMON_ASSERT(_values.size() == graph.dimension(),
   1.429 +                     "Wrong size of range");
   1.430 +      }
   1.431 +
   1.432 +      /// \brief The partial accumulated value.
   1.433 +      ///
   1.434 +      /// Gives back the partial accumulated value.
   1.435 +      Value operator[](const Key& k) const {
   1.436 +        Value val = _first_value;
   1.437 +        int id = _graph.index(k);
   1.438 +        int n = 0;
   1.439 +        while (id != 0) {
   1.440 +          if (id & 1) {
   1.441 +            val = _bin_func(val, _values[n]);
   1.442 +          }
   1.443 +          id >>= 1;
   1.444 +          ++n;
   1.445 +        }
   1.446 +        return val;
   1.447 +      }
   1.448 +
   1.449 +    private:
   1.450 +      const Graph& _graph;
   1.451 +      std::vector<T> _values;
   1.452 +      T _first_value;
   1.453 +      BF _bin_func;
   1.454 +    };
   1.455 +
   1.456 +  };
   1.457 +
   1.458 +}
   1.459 +
   1.460 +#endif