Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Thu, 06 Nov 2008 14:40:32 +0000
changeset 378efbd0ab50a77
parent 375 a637fb9d457b
parent 377 a12eef1f82b2
child 379 9194a12c52e6
child 380 a7e8ad460d66
Merge
lemon/Makefile.am
tools/lemon-0.x-to-1.x.sh
     1.1 --- a/lemon/Makefile.am	Wed Nov 05 14:44:37 2008 +0000
     1.2 +++ b/lemon/Makefile.am	Thu Nov 06 14:40:32 2008 +0000
     1.3 @@ -31,6 +31,7 @@
     1.4  	lemon/full_graph.h \
     1.5          lemon/graph_to_eps.h \
     1.6          lemon/grid_graph.h \
     1.7 +	lemon/hypercube_graph.h \
     1.8  	lemon/kruskal.h \
     1.9  	lemon/lgf_reader.h \
    1.10  	lemon/lgf_writer.h \
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/lemon/hypercube_graph.h	Thu Nov 06 14:40:32 2008 +0000
     2.3 @@ -0,0 +1,439 @@
     2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library.
     2.7 + *
     2.8 + * Copyright (C) 2003-2008
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22 +#ifndef HYPERCUBE_GRAPH_H
    2.23 +#define HYPERCUBE_GRAPH_H
    2.24 +
    2.25 +#include <vector>
    2.26 +#include <lemon/core.h>
    2.27 +#include <lemon/assert.h>
    2.28 +#include <lemon/bits/graph_extender.h>
    2.29 +
    2.30 +///\ingroup graphs
    2.31 +///\file
    2.32 +///\brief HypercubeGraph class.
    2.33 +
    2.34 +namespace lemon {
    2.35 +
    2.36 +  class HypercubeGraphBase {
    2.37 +
    2.38 +  public:
    2.39 +
    2.40 +    typedef HypercubeGraphBase Graph;
    2.41 +
    2.42 +    class Node;
    2.43 +    class Edge;
    2.44 +    class Arc;
    2.45 +
    2.46 +  public:
    2.47 +
    2.48 +    HypercubeGraphBase() {}
    2.49 +
    2.50 +  protected:
    2.51 +
    2.52 +    void construct(int dim) {
    2.53 +      LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
    2.54 +      _dim = dim;
    2.55 +      _node_num = 1 << dim;
    2.56 +      _edge_num = dim * (1 << dim-1);
    2.57 +    }
    2.58 +
    2.59 +  public:
    2.60 +
    2.61 +    typedef True NodeNumTag;
    2.62 +    typedef True EdgeNumTag;
    2.63 +    typedef True ArcNumTag;
    2.64 +
    2.65 +    int nodeNum() const { return _node_num; }
    2.66 +    int edgeNum() const { return _edge_num; }
    2.67 +    int arcNum() const { return 2 * _edge_num; }
    2.68 +
    2.69 +    int maxNodeId() const { return _node_num - 1; }
    2.70 +    int maxEdgeId() const { return _edge_num - 1; }
    2.71 +    int maxArcId() const { return 2 * _edge_num - 1; }
    2.72 +
    2.73 +    static Node nodeFromId(int id) { return Node(id); }
    2.74 +    static Edge edgeFromId(int id) { return Edge(id); }
    2.75 +    static Arc arcFromId(int id) { return Arc(id); }
    2.76 +
    2.77 +    static int id(Node node) { return node._id; }
    2.78 +    static int id(Edge edge) { return edge._id; }
    2.79 +    static int id(Arc arc) { return arc._id; }
    2.80 +
    2.81 +    Node u(Edge edge) const {
    2.82 +      int base = edge._id & ((1 << _dim-1) - 1);
    2.83 +      int k = edge._id >> _dim-1;
    2.84 +      return ((base >> k) << k+1) | (base & ((1 << k) - 1));
    2.85 +    }
    2.86 +
    2.87 +    Node v(Edge edge) const {
    2.88 +      int base = edge._id & ((1 << _dim-1) - 1);
    2.89 +      int k = edge._id >> _dim-1;
    2.90 +      return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k);
    2.91 +    }
    2.92 +
    2.93 +    Node source(Arc arc) const {
    2.94 +      return (arc._id & 1) == 1 ? u(arc) : v(arc);
    2.95 +    }
    2.96 +
    2.97 +    Node target(Arc arc) const {
    2.98 +      return (arc._id & 1) == 1 ? v(arc) : u(arc);
    2.99 +    }
   2.100 +
   2.101 +    typedef True FindEdgeTag;
   2.102 +    typedef True FindArcTag;
   2.103 +
   2.104 +    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   2.105 +      if (prev != INVALID) return INVALID;
   2.106 +      int d = u._id ^ v._id;
   2.107 +      int k = 0;
   2.108 +      if (d == 0) return INVALID;
   2.109 +      for ( ; (d & 1) == 0; d >>= 1) ++k;
   2.110 +      if (d >> 1 != 0) return INVALID;
   2.111 +      return (k << _dim-1) | ((u._id >> k+1) << k) | (u._id & ((1 << k) - 1));
   2.112 +    }
   2.113 +
   2.114 +    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
   2.115 +      Edge edge = findEdge(u, v, prev);
   2.116 +      if (edge == INVALID) return INVALID;
   2.117 +      int k = edge._id >> _dim-1;
   2.118 +      return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
   2.119 +    }
   2.120 +
   2.121 +    class Node {
   2.122 +      friend class HypercubeGraphBase;
   2.123 +
   2.124 +    protected:
   2.125 +      int _id;
   2.126 +      Node(int id) : _id(id) {}
   2.127 +    public:
   2.128 +      Node() {}
   2.129 +      Node (Invalid) : _id(-1) {}
   2.130 +      bool operator==(const Node node) const {return _id == node._id;}
   2.131 +      bool operator!=(const Node node) const {return _id != node._id;}
   2.132 +      bool operator<(const Node node) const {return _id < node._id;}
   2.133 +    };
   2.134 +
   2.135 +    class Edge {
   2.136 +      friend class HypercubeGraphBase;
   2.137 +      friend class Arc;
   2.138 +
   2.139 +    protected:
   2.140 +      int _id;
   2.141 +
   2.142 +      Edge(int id) : _id(id) {}
   2.143 +
   2.144 +    public:
   2.145 +      Edge() {}
   2.146 +      Edge (Invalid) : _id(-1) {}
   2.147 +      bool operator==(const Edge edge) const {return _id == edge._id;}
   2.148 +      bool operator!=(const Edge edge) const {return _id != edge._id;}
   2.149 +      bool operator<(const Edge edge) const {return _id < edge._id;}
   2.150 +    };
   2.151 +
   2.152 +    class Arc {
   2.153 +      friend class HypercubeGraphBase;
   2.154 +
   2.155 +    protected:
   2.156 +      int _id;
   2.157 +
   2.158 +      Arc(int id) : _id(id) {}
   2.159 +
   2.160 +    public:
   2.161 +      Arc() {}
   2.162 +      Arc (Invalid) : _id(-1) {}
   2.163 +      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
   2.164 +      bool operator==(const Arc arc) const {return _id == arc._id;}
   2.165 +      bool operator!=(const Arc arc) const {return _id != arc._id;}
   2.166 +      bool operator<(const Arc arc) const {return _id < arc._id;}
   2.167 +    };
   2.168 +
   2.169 +    void first(Node& node) const {
   2.170 +      node._id = _node_num - 1;
   2.171 +    }
   2.172 +
   2.173 +    static void next(Node& node) {
   2.174 +      --node._id;
   2.175 +    }
   2.176 +
   2.177 +    void first(Edge& edge) const {
   2.178 +      edge._id = _edge_num - 1;
   2.179 +    }
   2.180 +
   2.181 +    static void next(Edge& edge) {
   2.182 +      --edge._id;
   2.183 +    }
   2.184 +
   2.185 +    void first(Arc& arc) const {
   2.186 +      arc._id = 2 * _edge_num - 1;
   2.187 +    }
   2.188 +
   2.189 +    static void next(Arc& arc) {
   2.190 +      --arc._id;
   2.191 +    }
   2.192 +
   2.193 +    void firstInc(Edge& edge, bool& dir, const Node& node) const {
   2.194 +      edge._id = node._id >> 1;
   2.195 +      dir = (node._id & 1) == 0;
   2.196 +    }
   2.197 +
   2.198 +    void nextInc(Edge& edge, bool& dir) const {
   2.199 +      Node n = dir ? u(edge) : v(edge);
   2.200 +      int k = (edge._id >> _dim-1) + 1;
   2.201 +      if (k < _dim) {
   2.202 +        edge._id = (k << _dim-1) |
   2.203 +                   ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   2.204 +        dir = ((n._id >> k) & 1) == 0;
   2.205 +      } else {
   2.206 +        edge._id = -1;
   2.207 +        dir = true;
   2.208 +      }
   2.209 +    }
   2.210 +
   2.211 +    void firstOut(Arc& arc, const Node& node) const {
   2.212 +      arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
   2.213 +    }
   2.214 +
   2.215 +    void nextOut(Arc& arc) const {
   2.216 +      Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
   2.217 +      int k = (arc._id >> _dim) + 1;
   2.218 +      if (k < _dim) {
   2.219 +        arc._id = (k << _dim-1) |
   2.220 +                  ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   2.221 +        arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
   2.222 +      } else {
   2.223 +        arc._id = -1;
   2.224 +      }
   2.225 +    }
   2.226 +
   2.227 +    void firstIn(Arc& arc, const Node& node) const {
   2.228 +      arc._id = ((node._id >> 1) << 1) | (node._id & 1);
   2.229 +    }
   2.230 +
   2.231 +    void nextIn(Arc& arc) const {
   2.232 +      Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
   2.233 +      int k = (arc._id >> _dim) + 1;
   2.234 +      if (k < _dim) {
   2.235 +        arc._id = (k << _dim-1) |
   2.236 +                  ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   2.237 +        arc._id = (arc._id << 1) | ((n._id >> k) & 1);
   2.238 +      } else {
   2.239 +        arc._id = -1;
   2.240 +      }
   2.241 +    }
   2.242 +
   2.243 +    static bool direction(Arc arc) {
   2.244 +      return (arc._id & 1) == 1;
   2.245 +    }
   2.246 +
   2.247 +    static Arc direct(Edge edge, bool dir) {
   2.248 +      return Arc((edge._id << 1) | (dir ? 1 : 0));
   2.249 +    }
   2.250 +
   2.251 +    int dimension() const {
   2.252 +      return _dim;
   2.253 +    }
   2.254 +
   2.255 +    bool projection(Node node, int n) const {
   2.256 +      return static_cast<bool>(node._id & (1 << n));
   2.257 +    }
   2.258 +
   2.259 +    int dimension(Edge edge) const {
   2.260 +      return edge._id >> _dim-1;
   2.261 +    }
   2.262 +
   2.263 +    int dimension(Arc arc) const {
   2.264 +      return arc._id >> _dim;
   2.265 +    }
   2.266 +
   2.267 +    int index(Node node) const {
   2.268 +      return node._id;
   2.269 +    }
   2.270 +
   2.271 +    Node operator()(int ix) const {
   2.272 +      return Node(ix);
   2.273 +    }
   2.274 +
   2.275 +  private:
   2.276 +    int _dim;
   2.277 +    int _node_num, _edge_num;
   2.278 +  };
   2.279 +
   2.280 +
   2.281 +  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
   2.282 +
   2.283 +  /// \ingroup graphs
   2.284 +  ///
   2.285 +  /// \brief Hypercube graph class
   2.286 +  ///
   2.287 +  /// This class implements a special graph type. The nodes of the graph
   2.288 +  /// are indiced with integers with at most \c dim binary digits.
   2.289 +  /// Two nodes are connected in the graph if and only if their indices
   2.290 +  /// differ only on one position in the binary form.
   2.291 +  ///
   2.292 +  /// \note The type of the indices is chosen to \c int for efficiency
   2.293 +  /// reasons. Thus the maximum dimension of this implementation is 26
   2.294 +  /// (assuming that the size of \c int is 32 bit).
   2.295 +  ///
   2.296 +  /// This graph type is fully conform to the \ref concepts::Graph
   2.297 +  /// "Graph" concept, and it also has an important extra feature
   2.298 +  /// that its maps are real \ref concepts::ReferenceMap
   2.299 +  /// "reference map"s.
   2.300 +  class HypercubeGraph : public ExtendedHypercubeGraphBase {
   2.301 +  public:
   2.302 +
   2.303 +    typedef ExtendedHypercubeGraphBase Parent;
   2.304 +
   2.305 +    /// \brief Constructs a hypercube graph with \c dim dimensions.
   2.306 +    ///
   2.307 +    /// Constructs a hypercube graph with \c dim dimensions.
   2.308 +    HypercubeGraph(int dim) { construct(dim); }
   2.309 +
   2.310 +    /// \brief The number of dimensions.
   2.311 +    ///
   2.312 +    /// Gives back the number of dimensions.
   2.313 +    int dimension() const {
   2.314 +      return Parent::dimension();
   2.315 +    }
   2.316 +
   2.317 +    /// \brief Returns \c true if the n'th bit of the node is one.
   2.318 +    ///
   2.319 +    /// Returns \c true if the n'th bit of the node is one.
   2.320 +    bool projection(Node node, int n) const {
   2.321 +      return Parent::projection(node, n);
   2.322 +    }
   2.323 +
   2.324 +    /// \brief The dimension id of an edge.
   2.325 +    ///
   2.326 +    /// Gives back the dimension id of the given edge.
   2.327 +    /// It is in the [0..dim-1] range.
   2.328 +    int dimension(Edge edge) const {
   2.329 +      return Parent::dimension(edge);
   2.330 +    }
   2.331 +
   2.332 +    /// \brief The dimension id of an arc.
   2.333 +    ///
   2.334 +    /// Gives back the dimension id of the given arc.
   2.335 +    /// It is in the [0..dim-1] range.
   2.336 +    int dimension(Arc arc) const {
   2.337 +      return Parent::dimension(arc);
   2.338 +    }
   2.339 +
   2.340 +    /// \brief The index of a node.
   2.341 +    ///
   2.342 +    /// Gives back the index of the given node.
   2.343 +    /// The lower bits of the integer describes the node.
   2.344 +    int index(Node node) const {
   2.345 +      return Parent::index(node);
   2.346 +    }
   2.347 +
   2.348 +    /// \brief Gives back a node by its index.
   2.349 +    ///
   2.350 +    /// Gives back a node by its index.
   2.351 +    Node operator()(int ix) const {
   2.352 +      return Parent::operator()(ix);
   2.353 +    }
   2.354 +
   2.355 +    /// \brief Number of nodes.
   2.356 +    int nodeNum() const { return Parent::nodeNum(); }
   2.357 +    /// \brief Number of edges.
   2.358 +    int edgeNum() const { return Parent::edgeNum(); }
   2.359 +    /// \brief Number of arcs.
   2.360 +    int arcNum() const { return Parent::arcNum(); }
   2.361 +
   2.362 +    /// \brief Linear combination map.
   2.363 +    ///
   2.364 +    /// This map makes possible to give back a linear combination
   2.365 +    /// for each node. It works like the \c std::accumulate function,
   2.366 +    /// so it accumulates the \c bf binary function with the \c fv first
   2.367 +    /// value. The map accumulates only on that positions (dimensions)
   2.368 +    /// where the index of the node is one. The values that have to be
   2.369 +    /// accumulated should be given by the \c begin and \c end iterators
   2.370 +    /// and the length of this range should be equal to the dimension
   2.371 +    /// number of the graph.
   2.372 +    ///
   2.373 +    ///\code
   2.374 +    /// const int DIM = 3;
   2.375 +    /// HypercubeGraph graph(DIM);
   2.376 +    /// dim2::Point<double> base[DIM];
   2.377 +    /// for (int k = 0; k < DIM; ++k) {
   2.378 +    ///   base[k].x = rnd();
   2.379 +    ///   base[k].y = rnd();
   2.380 +    /// }
   2.381 +    /// HypercubeGraph::HyperMap<dim2::Point<double> >
   2.382 +    ///   pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
   2.383 +    ///\endcode
   2.384 +    ///
   2.385 +    /// \see HypercubeGraph
   2.386 +    template <typename T, typename BF = std::plus<T> >
   2.387 +    class HyperMap {
   2.388 +    public:
   2.389 +
   2.390 +      /// \brief The key type of the map
   2.391 +      typedef Node Key;
   2.392 +      /// \brief The value type of the map
   2.393 +      typedef T Value;
   2.394 +
   2.395 +      /// \brief Constructor for HyperMap.
   2.396 +      ///
   2.397 +      /// Construct a HyperMap for the given graph. The values that have
   2.398 +      /// to be accumulated should be given by the \c begin and \c end
   2.399 +      /// iterators and the length of this range should be equal to the
   2.400 +      /// dimension number of the graph.
   2.401 +      ///
   2.402 +      /// This map accumulates the \c bf binary function with the \c fv
   2.403 +      /// first value on that positions (dimensions) where the index of
   2.404 +      /// the node is one.
   2.405 +      template <typename It>
   2.406 +      HyperMap(const Graph& graph, It begin, It end,
   2.407 +               T fv = 0, const BF& bf = BF())
   2.408 +        : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
   2.409 +      {
   2.410 +        LEMON_ASSERT(_values.size() == graph.dimension(),
   2.411 +                     "Wrong size of range");
   2.412 +      }
   2.413 +
   2.414 +      /// \brief The partial accumulated value.
   2.415 +      ///
   2.416 +      /// Gives back the partial accumulated value.
   2.417 +      Value operator[](const Key& k) const {
   2.418 +        Value val = _first_value;
   2.419 +        int id = _graph.index(k);
   2.420 +        int n = 0;
   2.421 +        while (id != 0) {
   2.422 +          if (id & 1) {
   2.423 +            val = _bin_func(val, _values[n]);
   2.424 +          }
   2.425 +          id >>= 1;
   2.426 +          ++n;
   2.427 +        }
   2.428 +        return val;
   2.429 +      }
   2.430 +
   2.431 +    private:
   2.432 +      const Graph& _graph;
   2.433 +      std::vector<T> _values;
   2.434 +      T _first_value;
   2.435 +      BF _bin_func;
   2.436 +    };
   2.437 +
   2.438 +  };
   2.439 +
   2.440 +}
   2.441 +
   2.442 +#endif
     3.1 --- a/test/digraph_test.cc	Wed Nov 05 14:44:37 2008 +0000
     3.2 +++ b/test/digraph_test.cc	Thu Nov 06 14:40:32 2008 +0000
     3.3 @@ -20,7 +20,6 @@
     3.4  #include <lemon/list_graph.h>
     3.5  #include <lemon/smart_graph.h>
     3.6  #include <lemon/full_graph.h>
     3.7 -//#include <lemon/hypercube_graph.h>
     3.8  
     3.9  #include "test_tools.h"
    3.10  #include "graph_test.h"
    3.11 @@ -112,7 +111,6 @@
    3.12  
    3.13  }
    3.14  
    3.15 -
    3.16  void checkConcepts() {
    3.17    { // Checking digraph components
    3.18      checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
    3.19 @@ -145,9 +143,6 @@
    3.20    { // Checking FullDigraph
    3.21      checkConcept<Digraph, FullDigraph>();
    3.22    }
    3.23 -//  { // Checking HyperCubeDigraph
    3.24 -//    checkConcept<Digraph, HyperCubeDigraph>();
    3.25 -//  }
    3.26  }
    3.27  
    3.28  template <typename Digraph>
     4.1 --- a/test/graph_test.cc	Wed Nov 05 14:44:37 2008 +0000
     4.2 +++ b/test/graph_test.cc	Thu Nov 06 14:40:32 2008 +0000
     4.3 @@ -21,6 +21,7 @@
     4.4  #include <lemon/smart_graph.h>
     4.5  #include <lemon/full_graph.h>
     4.6  #include <lemon/grid_graph.h>
     4.7 +#include <lemon/hypercube_graph.h>
     4.8  
     4.9  #include "test_tools.h"
    4.10  #include "graph_test.h"
    4.11 @@ -104,9 +105,9 @@
    4.12    checkGraphEdgeList(G, num * (num - 1) / 2);
    4.13  
    4.14    for (NodeIt n(G); n != INVALID; ++n) {
    4.15 -    checkGraphOutArcList(G, n, num - 1);    
    4.16 -    checkGraphInArcList(G, n, num - 1);    
    4.17 -    checkGraphIncEdgeList(G, n, num - 1);    
    4.18 +    checkGraphOutArcList(G, n, num - 1);
    4.19 +    checkGraphInArcList(G, n, num - 1);
    4.20 +    checkGraphIncEdgeList(G, n, num - 1);
    4.21    }
    4.22  
    4.23    checkGraphConArcList(G, num * (num - 1));
    4.24 @@ -121,7 +122,7 @@
    4.25    checkGraphArcMap(G);
    4.26    checkGraphEdgeMap(G);
    4.27  
    4.28 -  
    4.29 +
    4.30    for (int i = 0; i < G.nodeNum(); ++i) {
    4.31      check(G.index(G(i)) == i, "Wrong index");
    4.32    }
    4.33 @@ -177,6 +178,9 @@
    4.34    { // Checking GridGraph
    4.35      checkConcept<Graph, GridGraph>();
    4.36    }
    4.37 +  { // Checking HypercubeGraph
    4.38 +    checkConcept<Graph, HypercubeGraph>();
    4.39 +  }
    4.40  }
    4.41  
    4.42  template <typename Graph>
    4.43 @@ -312,6 +316,54 @@
    4.44  
    4.45  }
    4.46  
    4.47 +void checkHypercubeGraph(int dim) {
    4.48 +  GRAPH_TYPEDEFS(HypercubeGraph);
    4.49 +
    4.50 +  HypercubeGraph G(dim);
    4.51 +  checkGraphNodeList(G, 1 << dim);
    4.52 +  checkGraphEdgeList(G, dim * (1 << dim-1));
    4.53 +  checkGraphArcList(G, dim * (1 << dim));
    4.54 +
    4.55 +  Node n = G.nodeFromId(dim);
    4.56 +
    4.57 +  for (NodeIt n(G); n != INVALID; ++n) {
    4.58 +    checkGraphIncEdgeList(G, n, dim);
    4.59 +    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
    4.60 +      check( (G.u(e) == n &&
    4.61 +              G.id(G.v(e)) == G.id(n) ^ (1 << G.dimension(e))) ||
    4.62 +             (G.v(e) == n &&
    4.63 +              G.id(G.u(e)) == G.id(n) ^ (1 << G.dimension(e))),
    4.64 +             "Wrong edge or wrong dimension");
    4.65 +    }
    4.66 +
    4.67 +    checkGraphOutArcList(G, n, dim);
    4.68 +    for (OutArcIt a(G, n); a != INVALID; ++a) {
    4.69 +      check(G.source(a) == n &&
    4.70 +            G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)),
    4.71 +            "Wrong arc or wrong dimension");
    4.72 +    }
    4.73 +
    4.74 +    checkGraphInArcList(G, n, dim);
    4.75 +    for (InArcIt a(G, n); a != INVALID; ++a) {
    4.76 +      check(G.target(a) == n &&
    4.77 +            G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)),
    4.78 +            "Wrong arc or wrong dimension");
    4.79 +    }
    4.80 +  }
    4.81 +
    4.82 +  checkGraphConArcList(G, (1 << dim) * dim);
    4.83 +  checkGraphConEdgeList(G, dim * (1 << dim-1));
    4.84 +
    4.85 +  checkArcDirections(G);
    4.86 +
    4.87 +  checkNodeIds(G);
    4.88 +  checkArcIds(G);
    4.89 +  checkEdgeIds(G);
    4.90 +  checkGraphNodeMap(G);
    4.91 +  checkGraphArcMap(G);
    4.92 +  checkGraphEdgeMap(G);
    4.93 +}
    4.94 +
    4.95  void checkGraphs() {
    4.96    { // Checking ListGraph
    4.97      checkGraph<ListGraph>();
    4.98 @@ -321,7 +373,7 @@
    4.99      checkGraph<SmartGraph>();
   4.100      checkGraphValidity<SmartGraph>();
   4.101    }
   4.102 -  { // Checking FullGraph   
   4.103 +  { // Checking FullGraph
   4.104      checkFullGraph(7);
   4.105      checkFullGraph(8);
   4.106    }
   4.107 @@ -332,6 +384,12 @@
   4.108      checkGridGraph(0, 0);
   4.109      checkGridGraph(1, 1);
   4.110    }
   4.111 +  { // Checking HypercubeGraph
   4.112 +    checkHypercubeGraph(1);
   4.113 +    checkHypercubeGraph(2);
   4.114 +    checkHypercubeGraph(3);
   4.115 +    checkHypercubeGraph(4);
   4.116 +  }
   4.117  }
   4.118  
   4.119  int main() {
     5.1 --- a/tools/lemon-0.x-to-1.x.sh	Wed Nov 05 14:44:37 2008 +0000
     5.2 +++ b/tools/lemon-0.x-to-1.x.sh	Thu Nov 06 14:40:32 2008 +0000
     5.3 @@ -81,6 +81,7 @@
     5.4          -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\
     5.5          -e "s/\<copyGraph\>/graphCopy/g"\
     5.6          -e "s/\<copyDigraph\>/digraphCopy/g"\
     5.7 +        -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\
     5.8          -e "s/\<IntegerMap\>/RangeMap/g"\
     5.9          -e "s/\<integerMap\>/rangeMap/g"\
    5.10          -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\