#include <lemon/error.h>

 #include <lemon/assert.h>

 #include <lemon/bits/base_extender.h>

 ///\brief HypercubeDigraph class.

 ///\brief HypercubeGraph class.

   class HypercubeDigraphBase {

   class HypercubeGraphBase {

     typedef HypercubeDigraphBase Digraph;

     typedef HypercubeGraphBase Graph;

     HypercubeDigraphBase() {}

     HypercubeGraphBase() {}

       _nodeNum = 1 << dim;

       _node_num = 1 << dim;

       _edge_num = dim * (1 << dim-1);

     int nodeNum() const { return _nodeNum; }

     int nodeNum() const { return _node_num; }

     int arcNum() const { return _nodeNum * _dim; }

     int edgeNum() const { return _edge_num; }

     int arcNum() const { return 2 * _edge_num; }

     int maxNodeId() const { return nodeNum() - 1; }

     int maxArcId() const { return arcNum() - 1; }

     int maxNodeId() const { return _node_num - 1; }

     int maxEdgeId() const { return _edge_num - 1; }

     Node source(Arc e) const {

     int maxArcId() const { return 2 * _edge_num - 1; }

       return e.id / _dim;

     }

     Node target(Arc e) const {

       return (e.id / _dim) ^ (1 << (e.id % _dim));

     }

     static int id(Node v) { return v.id; }

     static int id(Arc e) { return e.id; }

     static Edge edgeFromId(int id) { return Edge(id); }

       friend class HypercubeDigraphBase;

       friend class HypercubeGraphBase;

       int id;

       int _id;

       Node(int _id) { id = _id;}

       Node(int id) : _id(id) {}

       Node (Invalid) { id = -1; }

       Node (Invalid) : _id(-1) {}

       bool operator==(const Node node) const { return id == node.id; }

       bool operator==(const Node node) const {return _id == node._id;}

       bool operator!=(const Node node) const { return id != node.id; }

       bool operator!=(const Node node) const {return _id != node._id;}

       bool operator<(const Node node) const { return id < node.id; }

       bool operator<(const Node node) const {return _id < node._id;}

       friend class HypercubeDigraphBase;

       friend class HypercubeGraphBase;

       int id;

       int _id;

       Arc(int _id) : id(_id) {}

       Arc(int id) : _id(id) {}

       Arc() { }

       Arc() {}

       Arc (Invalid) { id = -1; }

       Arc (Invalid) : _id(-1) {}

       bool operator==(const Arc arc) const { return id == arc.id; }

       operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }

       bool operator!=(const Arc arc) const { return id != arc.id; }

       bool operator==(const Arc arc) const {return _id == arc._id;}

       bool operator<(const Arc arc) const { return id < arc.id; }

       bool operator!=(const Arc arc) const {return _id != arc._id;}

       bool operator<(const Arc arc) const {return _id < arc._id;}

       node.id = nodeNum() - 1;

       node._id = _node_num - 1;

       --node.id;

       --node._id;

     }

     void first(Edge& edge) const {

       edge._id = _edge_num - 1;

     }

     static void next(Edge& edge) {

       --edge._id;

       arc.id = arcNum() - 1;

       arc._id = 2 * _edge_num - 1;

       --arc.id;

       --arc._id;

     }

     void firstInc(Edge& edge, bool& dir, const Node& node) const {

       edge._id = node._id >> 1;

       dir = (node._id & 1) == 0;

     }

     void nextInc(Edge& edge, bool& dir) const {

       Node n = dir ? u(edge) : v(edge);

       int k = (edge._id >> _dim-1) + 1;

       if (k < _dim) {

         edge._id = (k << _dim-1) |

                    ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));

         dir = ((n._id >> k) & 1) == 0;

       } else {

         edge._id = -1;

         dir = true;

       }

       arc.id = node.id * _dim;

       arc._id = ((node._id >> 1) << 1) | (~node._id & 1);

       ++arc.id;

       Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);

       if (arc.id % _dim == 0) arc.id = -1;

       int k = (arc._id >> _dim) + 1;

       if (k < _dim) {

         arc._id = (k << _dim-1) |

                   ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));

         arc._id = (arc._id << 1) | (~(n._id >> k) & 1);

       } else {

         arc._id = -1;

       }

       arc.id = (node.id ^ 1) * _dim;

       arc._id = ((node._id >> 1) << 1) | (node._id & 1);

       int cnt = arc.id % _dim;

       Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);

       if ((cnt + 1) % _dim == 0) {

       int k = (arc._id >> _dim) + 1;

         arc.id = -1;

       if (k < _dim) {

         arc._id = (k << _dim-1) |

                   ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));

         arc._id = (arc._id << 1) | ((n._id >> k) & 1);

         arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;

         arc._id = -1;

       return static_cast<bool>(node.id & (1 << n));

       return static_cast<bool>(node._id & (1 << n));

     }

     int dimension(Edge edge) const {

       return edge._id >> _dim-1;

       return arc.id % _dim;

       return arc._id >> _dim;

       return node.id;

       return node._id;

     int _dim, _nodeNum;

     int _dim;

     int _node_num, _edge_num;

   typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;

   typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;

   /// \ingroup digraphs

   /// \ingroup graphs

   /// \brief Hypercube digraph class

   /// \brief Hypercube graph class

   /// This class implements a special digraph type. The nodes of the

   /// This class implements a special graph type. The nodes of the graph

   /// digraph are indiced with integers with at most \c dim binary digits.

   /// are indiced with integers with at most \c dim binary digits.

   /// Two nodes are connected in the digraph if the indices differ only

   /// Two nodes are connected in the graph if and only if their indices

   /// on one position in the binary form.

   /// differ only on one position in the binary form.

   /// \note The type of the \c ids is chosen to \c int because efficiency

   /// \note The type of the indices is chosen to \c int for efficiency

   /// reasons. Thus the maximum dimension of this implementation is 26.

   /// reasons. Thus the maximum dimension of this implementation is 26

   /// (assuming that the size of \c int is 32 bit).

   /// The digraph type is fully conform to the \ref concepts::Digraph

   /// This graph type is fully conform to the \ref concepts::Graph

   /// concept but it does not conform to \ref concepts::Graph.

   /// "Graph" concept, and it also has an important extra feature

   class HypercubeDigraph : public ExtendedHypercubeDigraphBase {

   /// that its maps are real \ref concepts::ReferenceMap

   /// "reference map"s.

   class HypercubeGraph : public ExtendedHypercubeGraphBase {

     typedef ExtendedHypercubeDigraphBase Parent;

     typedef ExtendedHypercubeGraphBase Parent;

     /// \brief Construct a hypercube digraph with \c dim dimension.

     /// \brief Constructs a hypercube graph with \c dim dimensions.

     ///

     ///

     /// Construct a hypercube digraph with \c dim dimension.

     /// Constructs a hypercube graph with \c dim dimensions.

     HypercubeDigraph(int dim) { construct(dim); }

     HypercubeGraph(int dim) { construct(dim); }

     /// \brief Gives back the number of the dimensions.

     /// \brief The number of dimensions.

     ///

     ///

     /// Gives back the number of the dimensions.

     /// Gives back the number of dimensions.

     /// \brief Returns true if the n'th bit of the node is one.

     /// \brief Returns \c true if the n'th bit of the node is one.

     ///

     ///

     /// Returns true if the n'th bit of the node is one.

     /// Returns \c true if the n'th bit of the node is one.

     /// \brief The dimension id of the arc.

     /// \brief The dimension id of an edge.

     ///

     ///

     /// It returns the dimension id of the arc. It can

     /// Gives back the dimension id of the given edge.

     /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval.

     /// It is in the [0..dim-1] range.

     int dimension(Edge edge) const {

       return Parent::dimension(edge);

     }

     /// \brief The dimension id of an arc.

     ///

     /// Gives back the dimension id of the given arc.

     /// It is in the [0..dim-1] range.

     /// \brief Gives back the index of the node.

     /// \brief The index of a node.

     ///

     ///

     /// Gives back the index of the node. The lower bits of the

     /// Gives back the index of the given node.

     /// integer describes the node.

     /// The lower bits of the integer describes the node.

     /// \brief Gives back the node by its index.

     /// \brief Gives back a node by its index.

     ///

     ///

     /// Gives back the node by its index.

     /// Gives back a node by its index.

     /// It makes possible to give back a linear combination

     /// This map makes possible to give back a linear combination

     /// for each node. This function works like the \c std::accumulate

     /// for each node. It works like the \c std::accumulate function,

     /// so it accumulates the \c bf binary function with the \c fv

     /// so it accumulates the \c bf binary function with the \c fv first

     /// first value. The map accumulates only on that dimensions where

     /// value. The map accumulates only on that positions (dimensions)

     /// the node's index is one. The accumulated values should be

     /// where the index of the node is one. The values that have to be

     /// given by the \c begin and \c end iterators and the length of this

     /// accumulated should be given by the \c begin and \c end iterators

     /// range should be equal to the dimension number of the digraph.

     /// and the length of this range should be equal to the dimension

     /// number of the graph.

     /// HypercubeDigraph digraph(DIM);

     /// HypercubeGraph graph(DIM);

     /// HypercubeDigraph::HyperMap<dim2::Point<double> >

     /// HypercubeGraph::HyperMap<dim2::Point<double> >

     ///   pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));

     ///   pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));

     /// \see HypercubeDigraph

     /// \see HypercubeGraph

       /// Construct a HyperMap for the given digraph. The accumulated values

       /// Construct a HyperMap for the given graph. The values that have

       /// should be given by the \c begin and \c end iterators and the length

       /// to be accumulated should be given by the \c begin and \c end

       /// of this range should be equal to the dimension number of the digraph.

       /// iterators and the length of this range should be equal to the

       /// dimension number of the graph.

       /// This function accumulates the \c bf binary function with

       /// This map accumulates the \c bf binary function with the \c fv

       /// the \c fv first value. The map accumulates only on that dimensions

       /// first value on that positions (dimensions) where the index of

       /// where the node's index is one.

       /// the node is one.

       HyperMap(const Digraph& digraph, It begin, It end,

       HyperMap(const Graph& graph, It begin, It end,

                T fv = 0.0, const BF& bf = BF())

                T fv = 0, const BF& bf = BF())

         : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf)

         : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)

         LEMON_ASSERT(_values.size() == digraph.dimension(),

         LEMON_ASSERT(_values.size() == graph.dimension(),

                      "Wrong size of dimension");

                      "Wrong size of range");

       /// \brief Gives back the partial accumulated value.

       /// \brief The partial accumulated value.

       Value operator[](Key k) const {

       Value operator[](const Key& k) const {

       const Digraph& _graph;

       const Graph& _graph;