kpeter@364: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@364:  *
kpeter@364:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@364:  *
kpeter@364:  * Copyright (C) 2003-2008
kpeter@364:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@364:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@364:  *
kpeter@364:  * Permission to use, modify and distribute this software is granted
kpeter@364:  * provided that this copyright notice appears in all copies. For
kpeter@364:  * precise terms see the accompanying LICENSE file.
kpeter@364:  *
kpeter@364:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@364:  * express or implied, and with no claim as to its suitability for any
kpeter@364:  * purpose.
kpeter@364:  *
kpeter@364:  */
kpeter@364: 
kpeter@364: #ifndef HYPERCUBE_GRAPH_H
kpeter@364: #define HYPERCUBE_GRAPH_H
kpeter@364: 
kpeter@364: #include <iostream>
kpeter@364: #include <vector>
kpeter@364: #include <lemon/core.h>
kpeter@364: #include <lemon/error.h>
kpeter@364: 
kpeter@364: #include <lemon/bits/base_extender.h>
kpeter@364: #include <lemon/bits/graph_extender.h>
kpeter@364: 
kpeter@364: ///\ingroup graphs
kpeter@364: ///\file
kpeter@364: ///\brief HypercubeDigraph class.
kpeter@364: 
kpeter@364: namespace lemon {
kpeter@364: 
kpeter@364:   class HypercubeDigraphBase {
kpeter@364: 
kpeter@364:   public:
kpeter@364: 
kpeter@364:     typedef HypercubeDigraphBase Digraph;
kpeter@364: 
kpeter@364:     class Node;
kpeter@364:     class Arc;
kpeter@364: 
kpeter@364:   public:
kpeter@364: 
kpeter@364:     HypercubeDigraphBase() {}
kpeter@364: 
kpeter@364:   protected:
kpeter@364: 
kpeter@364:     void construct(int dim) {
kpeter@364:       _dim = dim;
kpeter@364:       _nodeNum = 1 << dim;
kpeter@364:     }
kpeter@364: 
kpeter@364:   public:
kpeter@364: 
kpeter@364:     typedef True NodeNumTag;
kpeter@364:     typedef True ArcNumTag;
kpeter@364: 
kpeter@364:     int nodeNum() const { return _nodeNum; }
kpeter@364:     int arcNum() const { return _nodeNum * _dim; }
kpeter@364: 
kpeter@364:     int maxNodeId() const { return nodeNum() - 1; }
kpeter@364:     int maxArcId() const { return arcNum() - 1; }
kpeter@364: 
kpeter@364:     Node source(Arc e) const {
kpeter@364:       return e.id / _dim;
kpeter@364:     }
kpeter@364: 
kpeter@364:     Node target(Arc e) const {
kpeter@364:       return (e.id / _dim) ^ (1 << (e.id % _dim));
kpeter@364:     }
kpeter@364: 
kpeter@364:     static int id(Node v) { return v.id; }
kpeter@364:     static int id(Arc e) { return e.id; }
kpeter@364: 
kpeter@364:     static Node nodeFromId(int id) { return Node(id); }
kpeter@364: 
kpeter@364:     static Arc arcFromId(int id) { return Arc(id); }
kpeter@364: 
kpeter@364:     class Node {
kpeter@364:       friend class HypercubeDigraphBase;
kpeter@364:     protected:
kpeter@364:       int id;
kpeter@364:       Node(int _id) { id = _id;}
kpeter@364:     public:
kpeter@364:       Node() {}
kpeter@364:       Node (Invalid) { id = -1; }
kpeter@364:       bool operator==(const Node node) const { return id == node.id; }
kpeter@364:       bool operator!=(const Node node) const { return id != node.id; }
kpeter@364:       bool operator<(const Node node) const { return id < node.id; }
kpeter@364:     };
kpeter@364: 
kpeter@364:     class Arc {
kpeter@364:       friend class HypercubeDigraphBase;
kpeter@364:     protected:
kpeter@364:       int id;
kpeter@364:       Arc(int _id) : id(_id) {}
kpeter@364:     public:
kpeter@364:       Arc() { }
kpeter@364:       Arc (Invalid) { id = -1; }
kpeter@364:       bool operator==(const Arc arc) const { return id == arc.id; }
kpeter@364:       bool operator!=(const Arc arc) const { return id != arc.id; }
kpeter@364:       bool operator<(const Arc arc) const { return id < arc.id; }
kpeter@364:     };
kpeter@364: 
kpeter@364:     void first(Node& node) const {
kpeter@364:       node.id = nodeNum() - 1;
kpeter@364:     }
kpeter@364: 
kpeter@364:     static void next(Node& node) {
kpeter@364:       --node.id;
kpeter@364:     }
kpeter@364: 
kpeter@364:     void first(Arc& arc) const {
kpeter@364:       arc.id = arcNum() - 1;
kpeter@364:     }
kpeter@364: 
kpeter@364:     static void next(Arc& arc) {
kpeter@364:       --arc.id;
kpeter@364:     }
kpeter@364: 
kpeter@364:     void firstOut(Arc& arc, const Node& node) const {
kpeter@364:       arc.id = node.id * _dim;
kpeter@364:     }
kpeter@364: 
kpeter@364:     void nextOut(Arc& arc) const {
kpeter@364:       ++arc.id;
kpeter@364:       if (arc.id % _dim == 0) arc.id = -1;
kpeter@364:     }
kpeter@364: 
kpeter@364:     void firstIn(Arc& arc, const Node& node) const {
kpeter@364:       arc.id = (node.id ^ 1) * _dim;
kpeter@364:     }
kpeter@364: 
kpeter@364:     void nextIn(Arc& arc) const {
kpeter@364:       int cnt = arc.id % _dim;
kpeter@364:       if ((cnt + 1) % _dim == 0) {
kpeter@364:         arc.id = -1;
kpeter@364:       } else {
kpeter@364:         arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
kpeter@364:       }
kpeter@364:     }
kpeter@364: 
kpeter@364:     int dimension() const {
kpeter@364:       return _dim;
kpeter@364:     }
kpeter@364: 
kpeter@364:     bool projection(Node node, int n) const {
kpeter@364:       return static_cast<bool>(node.id & (1 << n));
kpeter@364:     }
kpeter@364: 
kpeter@364:     int dimension(Arc arc) const {
kpeter@364:       return arc.id % _dim;
kpeter@364:     }
kpeter@364: 
kpeter@364:     int index(Node node) const {
kpeter@364:       return node.id;
kpeter@364:     }
kpeter@364: 
kpeter@364:     Node operator()(int ix) const {
kpeter@364:       return Node(ix);
kpeter@364:     }
kpeter@364: 
kpeter@364:   private:
kpeter@364:     int _dim, _nodeNum;
kpeter@364:   };
kpeter@364: 
kpeter@364: 
kpeter@364:   typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;
kpeter@364: 
kpeter@364:   /// \ingroup digraphs
kpeter@364:   ///
kpeter@364:   /// \brief Hypercube digraph class
kpeter@364:   ///
kpeter@364:   /// This class implements a special digraph type. The nodes of the
kpeter@364:   /// digraph are indiced with integers with at most \c dim binary digits.
kpeter@364:   /// Two nodes are connected in the digraph if the indices differ only
kpeter@364:   /// on one position in the binary form.
kpeter@364:   ///
kpeter@364:   /// \note The type of the \c ids is chosen to \c int because efficiency
kpeter@364:   /// reasons. Thus the maximum dimension of this implementation is 26.
kpeter@364:   ///
kpeter@364:   /// The digraph type is fully conform to the \ref concepts::Digraph
kpeter@364:   /// concept but it does not conform to \ref concepts::Graph.
kpeter@364:   class HypercubeDigraph : public ExtendedHypercubeDigraphBase {
kpeter@364:   public:
kpeter@364: 
kpeter@364:     typedef ExtendedHypercubeDigraphBase Parent;
kpeter@364: 
kpeter@364:     /// \brief Construct a hypercube digraph with \c dim dimension.
kpeter@364:     ///
kpeter@364:     /// Construct a hypercube digraph with \c dim dimension.
kpeter@364:     HypercubeDigraph(int dim) { construct(dim); }
kpeter@364: 
kpeter@364:     /// \brief Gives back the number of the dimensions.
kpeter@364:     ///
kpeter@364:     /// Gives back the number of the dimensions.
kpeter@364:     int dimension() const {
kpeter@364:       return Parent::dimension();
kpeter@364:     }
kpeter@364: 
kpeter@364:     /// \brief Returns true if the n'th bit of the node is one.
kpeter@364:     ///
kpeter@364:     /// Returns true if the n'th bit of the node is one.
kpeter@364:     bool projection(Node node, int n) const {
kpeter@364:       return Parent::projection(node, n);
kpeter@364:     }
kpeter@364: 
kpeter@364:     /// \brief The dimension id of the arc.
kpeter@364:     ///
kpeter@364:     /// It returns the dimension id of the arc. It can
kpeter@364:     /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval.
kpeter@364:     int dimension(Arc arc) const {
kpeter@364:       return Parent::dimension(arc);
kpeter@364:     }
kpeter@364: 
kpeter@364:     /// \brief Gives back the index of the node.
kpeter@364:     ///
kpeter@364:     /// Gives back the index of the node. The lower bits of the
kpeter@364:     /// integer describes the node.
kpeter@364:     int index(Node node) const {
kpeter@364:       return Parent::index(node);
kpeter@364:     }
kpeter@364: 
kpeter@364:     /// \brief Gives back the node by its index.
kpeter@364:     ///
kpeter@364:     /// Gives back the node by its index.
kpeter@364:     Node operator()(int ix) const {
kpeter@364:       return Parent::operator()(ix);
kpeter@364:     }
kpeter@364: 
kpeter@364:     /// \brief Number of nodes.
kpeter@364:     int nodeNum() const { return Parent::nodeNum(); }
kpeter@364:     /// \brief Number of arcs.
kpeter@364:     int arcNum() const { return Parent::arcNum(); }
kpeter@364: 
kpeter@364:     /// \brief Linear combination map.
kpeter@364:     ///
kpeter@364:     /// It makes possible to give back a linear combination
kpeter@364:     /// for each node. This function works like the \c std::accumulate
kpeter@364:     /// so it accumulates the \c bf binary function with the \c fv
kpeter@364:     /// first value. The map accumulates only on that dimensions where
kpeter@364:     /// the node's index is one. The accumulated values should be
kpeter@364:     /// given by the \c begin and \c end iterators and the length of this
kpeter@364:     /// range should be equal to the dimension number of the digraph.
kpeter@364:     ///
kpeter@364:     ///\code
kpeter@364:     /// const int DIM = 3;
kpeter@364:     /// HypercubeDigraph digraph(DIM);
kpeter@364:     /// dim2::Point<double> base[DIM];
kpeter@364:     /// for (int k = 0; k < DIM; ++k) {
kpeter@364:     ///   base[k].x = rnd();
kpeter@364:     ///   base[k].y = rnd();
kpeter@364:     /// }
kpeter@364:     /// HypercubeDigraph::HyperMap<dim2::Point<double> >
kpeter@364:     ///   pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
kpeter@364:     ///\endcode
kpeter@364:     ///
kpeter@364:     /// \see HypercubeDigraph
kpeter@364:     template <typename T, typename BF = std::plus<T> >
kpeter@364:     class HyperMap {
kpeter@364:     public:
kpeter@364: 
kpeter@364:       typedef Node Key;
kpeter@364:       typedef T Value;
kpeter@364: 
kpeter@364: 
kpeter@364:       /// \brief Constructor for HyperMap.
kpeter@364:       ///
kpeter@364:       /// Construct a HyperMap for the given digraph. The accumulated values
kpeter@364:       /// should be given by the \c begin and \c end iterators and the length
kpeter@364:       /// of this range should be equal to the dimension number of the digraph.
kpeter@364:       ///
kpeter@364:       /// This function accumulates the \c bf binary function with
kpeter@364:       /// the \c fv first value. The map accumulates only on that dimensions
kpeter@364:       /// where the node's index is one.
kpeter@364:       template <typename It>
kpeter@364:       HyperMap(const Digraph& digraph, It begin, It end,
kpeter@364:                T fv = 0.0, const BF& bf = BF())
kpeter@364:         : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf)
kpeter@364:       {
kpeter@364:         LEMON_ASSERT(_values.size() == digraph.dimension(),
kpeter@364:                      "Wrong size of dimension");
kpeter@364:       }
kpeter@364: 
kpeter@364:       /// \brief Gives back the partial accumulated value.
kpeter@364:       ///
kpeter@364:       /// Gives back the partial accumulated value.
kpeter@364:       Value operator[](Key k) const {
kpeter@364:         Value val = _first_value;
kpeter@364:         int id = _graph.index(k);
kpeter@364:         int n = 0;
kpeter@364:         while (id != 0) {
kpeter@364:           if (id & 1) {
kpeter@364:             val = _bin_func(val, _values[n]);
kpeter@364:           }
kpeter@364:           id >>= 1;
kpeter@364:           ++n;
kpeter@364:         }
kpeter@364:         return val;
kpeter@364:       }
kpeter@364: 
kpeter@364:     private:
kpeter@364:       const Digraph& _graph;
kpeter@364:       std::vector<T> _values;
kpeter@364:       T _first_value;
kpeter@364:       BF _bin_func;
kpeter@364:     };
kpeter@364: 
kpeter@364:   };
kpeter@364: 
kpeter@364: }
kpeter@364: 
kpeter@364: #endif