lemon/hypercube_graph.h
author alpar
Thu, 12 Oct 2006 10:56:26 +0000
changeset 2237 5674a5983e1e
parent 2223 590c1b663a27
child 2242 16523135943d
permissions -rw-r--r--
Improve the configuration environment / repository layout:
- Update README
- svn-head -> svnhead version tag change (in favor of rpm build)
- rpmbuild-glpk: a script to build glpk rpm.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef HYPERCUBE_GRAPH_H
    20 #define HYPERCUBE_GRAPH_H
    21 
    22 #include <iostream>
    23 #include <vector>
    24 #include <lemon/bits/invalid.h>
    25 #include <lemon/bits/utility.h>
    26 #include <lemon/error.h>
    27 
    28 #include <lemon/bits/base_extender.h>
    29 #include <lemon/bits/graph_extender.h>
    30 
    31 ///\ingroup graphs
    32 ///\file
    33 ///\brief HyperCubeGraph class.
    34 
    35 namespace lemon {
    36 
    37   class HyperCubeGraphBase {
    38 
    39   public:
    40 
    41     typedef HyperCubeGraphBase Graph;
    42 
    43     class Node;
    44     class Edge;
    45 
    46   public:
    47 
    48     HyperCubeGraphBase() {}
    49 
    50   protected:
    51 
    52     void construct(int dim) {
    53       _dim = dim;
    54       _nodeNum = 1 << dim;
    55     }
    56 
    57   public:
    58     
    59 
    60     typedef True NodeNumTag;
    61     typedef True EdgeNumTag;
    62 
    63     int nodeNum() const { return _nodeNum; }
    64     int edgeNum() const { return _nodeNum * _dim; }
    65 
    66     int maxNodeId() const { return nodeNum() - 1; }
    67     int maxEdgeId() const { return edgeNum() - 1; }
    68 
    69     Node source(Edge e) const {
    70       return e.id / _dim;
    71     }
    72 
    73     Node target(Edge e) const {
    74       return (e.id / _dim) ^ ( 1 << (e.id % _dim));
    75     }
    76 
    77     static int id(Node v) { return v.id; }
    78     static int id(Edge e) { return e.id; }
    79 
    80     static Node nodeFromId(int id) { return Node(id);}
    81     
    82     static Edge edgeFromId(int id) { return Edge(id);}
    83 
    84     class Node {
    85       friend class HyperCubeGraphBase;
    86 
    87     protected:
    88       int id;
    89       Node(int _id) { id = _id;}
    90     public:
    91       Node() {}
    92       Node (Invalid) { id = -1; }
    93       bool operator==(const Node node) const {return id == node.id;}
    94       bool operator!=(const Node node) const {return id != node.id;}
    95       bool operator<(const Node node) const {return id < node.id;}
    96     };
    97     
    98     class Edge {
    99       friend class HyperCubeGraphBase;
   100       
   101     protected:
   102       int id; 
   103 
   104       Edge(int _id) : id(_id) {}
   105 
   106     public:
   107       Edge() { }
   108       Edge (Invalid) { id = -1; }
   109       bool operator==(const Edge edge) const {return id == edge.id;}
   110       bool operator!=(const Edge edge) const {return id != edge.id;}
   111       bool operator<(const Edge edge) const {return id < edge.id;}
   112     };
   113 
   114     void first(Node& node) const {
   115       node.id = nodeNum() - 1;
   116     }
   117 
   118     static void next(Node& node) {
   119       --node.id;
   120     }
   121 
   122     void first(Edge& edge) const {
   123       edge.id = edgeNum() - 1;
   124     }
   125 
   126     static void next(Edge& edge) {
   127       --edge.id;
   128     }
   129 
   130     void firstOut(Edge& edge, const Node& node) const {
   131       edge.id = node.id * _dim;
   132     }
   133 
   134     void nextOut(Edge& edge) const {
   135       ++edge.id;
   136       if (edge.id % _dim == 0) edge.id = -1;
   137     }
   138 
   139     void firstIn(Edge& edge, const Node& node) const {
   140       edge.id = (node.id ^ 1) * _dim;
   141     }
   142     
   143     void nextIn(Edge& edge) const {
   144       int cnt = edge.id % _dim;
   145       if ((cnt + 1) % _dim == 0) {
   146 	edge.id = -1;
   147       } else {
   148 	edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1; 
   149       }
   150     }
   151 
   152     int dimension() const {
   153       return _dim;
   154     }
   155 
   156     bool projection(Node node, int n) const {
   157       return (bool)(node.id & (1 << n));
   158     }
   159 
   160     int dimension(Edge edge) const {
   161       return edge.id % _dim;
   162     }
   163 
   164     int index(Node node) const {
   165       return node.id;
   166     }
   167 
   168     Node operator()(int index) const {
   169       return Node(index);
   170     }
   171     
   172   private:
   173     int _dim, _nodeNum;
   174   };
   175 
   176 
   177   typedef GraphExtender<HyperCubeGraphBase> ExtendedHyperCubeGraphBase;
   178 
   179   /// \ingroup graphs
   180   ///
   181   /// \brief HyperCube graph class
   182   ///
   183   /// This class implements a special graph type. The nodes of the
   184   /// graph can be indiced with integers with at most \c dim binary length.
   185   /// Two nodes are connected in the graph if the indices differ only
   186   /// on one position in the binary form. 
   187   ///
   188   /// \note The type of the \c ids is chosen to \c int because efficiency
   189   /// reasons. This way the maximal dimension of this implementation
   190   /// is 26. 
   191   ///
   192   /// The graph type is fully conform to the \ref concept::Graph
   193   /// concept but it does not conform to the \ref concept::UGraph.
   194   ///
   195   /// \author Balazs Dezso
   196   class HyperCubeGraph : public ExtendedHyperCubeGraphBase {
   197   public:
   198 
   199     typedef ExtendedHyperCubeGraphBase Parent;
   200 
   201     /// \brief Construct a graph with \c dim dimension.
   202     ///
   203     /// Construct a graph with \c dim dimension.
   204     HyperCubeGraph(int dim) { construct(dim); }
   205 
   206     /// \brief Gives back the number of the dimensions.
   207     ///
   208     /// Gives back the number of the dimensions.
   209     int dimension() const {
   210       return Parent::dimension();
   211     }
   212 
   213     /// \brief Returns true if the n'th bit of the node is one.
   214     ///
   215     /// Returns true if the n'th bit of the node is one. 
   216     bool projection(Node node, int n) const {
   217       return Parent::projection(node, n);
   218     }
   219 
   220     /// \brief The dimension id of the edge.
   221     ///
   222     /// It returns the dimension id of the edge. It can
   223     /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ intervall.
   224     int dimension(Edge edge) const {
   225       return Parent::dimension(edge);
   226     }
   227 
   228     /// \brief Gives back the index of the node.
   229     ///
   230     /// Gives back the index of the node. The lower bits of the
   231     /// integer describes the node.
   232     int index(Node node) const {
   233       return Parent::index(node);
   234     }
   235 
   236     /// \brief Gives back the node by its index.
   237     ///
   238     /// Gives back the node by its index.
   239     Node operator()(int index) const {
   240       return Parent::operator()(index);
   241     }
   242 
   243     /// \brief Number of nodes.
   244     int nodeNum() const { return Parent::nodeNum(); }
   245     /// \brief Number of edges.
   246     int edgeNum() const { return Parent::edgeNum(); }
   247 
   248     /// \brief Linear combination map.
   249     ///
   250     /// It makes possible to give back a linear combination
   251     /// for each node. This function works like the \c std::accumulate
   252     /// so it accumulates the \c bf binary function with the \c fv
   253     /// first value. The map accumulates only on that dimensions where
   254     /// the node's index is one. The accumulated values should be
   255     /// given by the \c begin and \c end iterators and this range's length
   256     /// should be the dimension number of the graph.
   257     /// 
   258     ///\code
   259     /// const int DIM = 3;
   260     /// HyperCubeGraph graph(DIM);
   261     /// dim2::Point<double> base[DIM];
   262     /// for (int k = 0; k < DIM; ++k) {
   263     ///   base[k].x = random.getReal();
   264     ///   base[k].y = random.getReal();
   265     /// } 
   266     /// HyperCubeGraph::HyperMap<dim2::Point<double> > 
   267     ///   pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
   268     ///\endcode
   269     ///
   270     /// \see HyperCubeGraph
   271     template <typename T, typename BF = std::plus<T> >
   272     class HyperMap {
   273     public:
   274 
   275       typedef Node Key;
   276       typedef T Value;
   277     
   278       
   279       /// \brief Constructor for HyperMap. 
   280       ///
   281       /// Construct a HyperMap for the given graph. The accumulated values 
   282       /// should be given by the \c begin and \c end iterators and this 
   283       /// range's length should be the dimension number of the graph.
   284       ///
   285       /// This function accumulates the \c bf binary function with 
   286       /// the \c fv first value. The map accumulates only on that dimensions 
   287       /// where the node's index is one.           
   288       template <typename It>
   289       HyperMap(const Graph& graph, It begin, It end, 
   290 		   T fv = 0.0, const BF& bf = BF()) 
   291 	: _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) {
   292 	LEMON_ASSERT(_values.size() == graph.dimension(), 
   293 		     "Wrong size of dimension");
   294       }
   295 
   296       /// \brief Gives back the partial accumulated value.
   297       ///
   298       /// Gives back the partial accumulated value.
   299       Value operator[](Key k) const {
   300 	Value val = _first_value;
   301 	int id = _graph.index(k); 
   302 	int n = 0;
   303 	while (id != 0) {
   304 	  if (id & 1) {
   305 	    val = _bin_func(val, _values[n]);
   306 	  }
   307 	  id >>= 1;
   308 	  ++n;
   309 	}
   310 	return val;
   311       }
   312       
   313     private:
   314       const Graph& _graph;
   315       std::vector<T> _values;
   316       T _first_value;
   317       BF _bin_func;
   318     };    
   319   };
   320 }
   321 #endif
   322