lemon/hypercube_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 06 Nov 2008 18:35:38 +0100
changeset 368 a7e8ad460d66
parent 364 b4a01426c0d9
child 372 7b6466ed488a
permissions -rw-r--r--
Add missing tags and functions for item counting in SmartGraph (#3)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     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 <vector>
    23 #include <lemon/core.h>
    24 #include <lemon/assert.h>
    25 #include <lemon/bits/graph_extender.h>
    26 
    27 ///\ingroup graphs
    28 ///\file
    29 ///\brief HypercubeGraph class.
    30 
    31 namespace lemon {
    32 
    33   class HypercubeGraphBase {
    34 
    35   public:
    36 
    37     typedef HypercubeGraphBase Graph;
    38 
    39     class Node;
    40     class Edge;
    41     class Arc;
    42 
    43   public:
    44 
    45     HypercubeGraphBase() {}
    46 
    47   protected:
    48 
    49     void construct(int dim) {
    50       LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
    51       _dim = dim;
    52       _node_num = 1 << dim;
    53       _edge_num = dim * (1 << dim-1);
    54     }
    55 
    56   public:
    57 
    58     typedef True NodeNumTag;
    59     typedef True EdgeNumTag;
    60     typedef True ArcNumTag;
    61 
    62     int nodeNum() const { return _node_num; }
    63     int edgeNum() const { return _edge_num; }
    64     int arcNum() const { return 2 * _edge_num; }
    65 
    66     int maxNodeId() const { return _node_num - 1; }
    67     int maxEdgeId() const { return _edge_num - 1; }
    68     int maxArcId() const { return 2 * _edge_num - 1; }
    69 
    70     static Node nodeFromId(int id) { return Node(id); }
    71     static Edge edgeFromId(int id) { return Edge(id); }
    72     static Arc arcFromId(int id) { return Arc(id); }
    73 
    74     static int id(Node node) { return node._id; }
    75     static int id(Edge edge) { return edge._id; }
    76     static int id(Arc arc) { return arc._id; }
    77 
    78     Node u(Edge edge) const {
    79       int base = edge._id & ((1 << _dim-1) - 1);
    80       int k = edge._id >> _dim-1;
    81       return ((base >> k) << k+1) | (base & ((1 << k) - 1));
    82     }
    83 
    84     Node v(Edge edge) const {
    85       int base = edge._id & ((1 << _dim-1) - 1);
    86       int k = edge._id >> _dim-1;
    87       return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k);
    88     }
    89 
    90     Node source(Arc arc) const {
    91       return (arc._id & 1) == 1 ? u(arc) : v(arc);
    92     }
    93 
    94     Node target(Arc arc) const {
    95       return (arc._id & 1) == 1 ? v(arc) : u(arc);
    96     }
    97 
    98     typedef True FindEdgeTag;
    99     typedef True FindArcTag;
   100 
   101     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   102       if (prev != INVALID) return INVALID;
   103       int d = u._id ^ v._id;
   104       int k = 0;
   105       if (d == 0) return INVALID;
   106       for ( ; (d & 1) == 0; d >>= 1) ++k;
   107       if (d >> 1 != 0) return INVALID;
   108       return (k << _dim-1) | ((u._id >> k+1) << k) | (u._id & ((1 << k) - 1));
   109     }
   110 
   111     Arc findArc(Node u, Node v, Arc prev = INVALID) const {
   112       Edge edge = findEdge(u, v, prev);
   113       if (edge == INVALID) return INVALID;
   114       int k = edge._id >> _dim-1;
   115       return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
   116     }
   117 
   118     class Node {
   119       friend class HypercubeGraphBase;
   120 
   121     protected:
   122       int _id;
   123       Node(int id) : _id(id) {}
   124     public:
   125       Node() {}
   126       Node (Invalid) : _id(-1) {}
   127       bool operator==(const Node node) const {return _id == node._id;}
   128       bool operator!=(const Node node) const {return _id != node._id;}
   129       bool operator<(const Node node) const {return _id < node._id;}
   130     };
   131 
   132     class Edge {
   133       friend class HypercubeGraphBase;
   134       friend class Arc;
   135 
   136     protected:
   137       int _id;
   138 
   139       Edge(int id) : _id(id) {}
   140 
   141     public:
   142       Edge() {}
   143       Edge (Invalid) : _id(-1) {}
   144       bool operator==(const Edge edge) const {return _id == edge._id;}
   145       bool operator!=(const Edge edge) const {return _id != edge._id;}
   146       bool operator<(const Edge edge) const {return _id < edge._id;}
   147     };
   148 
   149     class Arc {
   150       friend class HypercubeGraphBase;
   151 
   152     protected:
   153       int _id;
   154 
   155       Arc(int id) : _id(id) {}
   156 
   157     public:
   158       Arc() {}
   159       Arc (Invalid) : _id(-1) {}
   160       operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
   161       bool operator==(const Arc arc) const {return _id == arc._id;}
   162       bool operator!=(const Arc arc) const {return _id != arc._id;}
   163       bool operator<(const Arc arc) const {return _id < arc._id;}
   164     };
   165 
   166     void first(Node& node) const {
   167       node._id = _node_num - 1;
   168     }
   169 
   170     static void next(Node& node) {
   171       --node._id;
   172     }
   173 
   174     void first(Edge& edge) const {
   175       edge._id = _edge_num - 1;
   176     }
   177 
   178     static void next(Edge& edge) {
   179       --edge._id;
   180     }
   181 
   182     void first(Arc& arc) const {
   183       arc._id = 2 * _edge_num - 1;
   184     }
   185 
   186     static void next(Arc& arc) {
   187       --arc._id;
   188     }
   189 
   190     void firstInc(Edge& edge, bool& dir, const Node& node) const {
   191       edge._id = node._id >> 1;
   192       dir = (node._id & 1) == 0;
   193     }
   194 
   195     void nextInc(Edge& edge, bool& dir) const {
   196       Node n = dir ? u(edge) : v(edge);
   197       int k = (edge._id >> _dim-1) + 1;
   198       if (k < _dim) {
   199         edge._id = (k << _dim-1) |
   200                    ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   201         dir = ((n._id >> k) & 1) == 0;
   202       } else {
   203         edge._id = -1;
   204         dir = true;
   205       }
   206     }
   207 
   208     void firstOut(Arc& arc, const Node& node) const {
   209       arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
   210     }
   211 
   212     void nextOut(Arc& arc) const {
   213       Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
   214       int k = (arc._id >> _dim) + 1;
   215       if (k < _dim) {
   216         arc._id = (k << _dim-1) |
   217                   ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   218         arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
   219       } else {
   220         arc._id = -1;
   221       }
   222     }
   223 
   224     void firstIn(Arc& arc, const Node& node) const {
   225       arc._id = ((node._id >> 1) << 1) | (node._id & 1);
   226     }
   227 
   228     void nextIn(Arc& arc) const {
   229       Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
   230       int k = (arc._id >> _dim) + 1;
   231       if (k < _dim) {
   232         arc._id = (k << _dim-1) |
   233                   ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   234         arc._id = (arc._id << 1) | ((n._id >> k) & 1);
   235       } else {
   236         arc._id = -1;
   237       }
   238     }
   239 
   240     static bool direction(Arc arc) {
   241       return (arc._id & 1) == 1;
   242     }
   243 
   244     static Arc direct(Edge edge, bool dir) {
   245       return Arc((edge._id << 1) | (dir ? 1 : 0));
   246     }
   247 
   248     int dimension() const {
   249       return _dim;
   250     }
   251 
   252     bool projection(Node node, int n) const {
   253       return static_cast<bool>(node._id & (1 << n));
   254     }
   255 
   256     int dimension(Edge edge) const {
   257       return edge._id >> _dim-1;
   258     }
   259 
   260     int dimension(Arc arc) const {
   261       return arc._id >> _dim;
   262     }
   263 
   264     int index(Node node) const {
   265       return node._id;
   266     }
   267 
   268     Node operator()(int ix) const {
   269       return Node(ix);
   270     }
   271 
   272   private:
   273     int _dim;
   274     int _node_num, _edge_num;
   275   };
   276 
   277 
   278   typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
   279 
   280   /// \ingroup graphs
   281   ///
   282   /// \brief Hypercube graph class
   283   ///
   284   /// This class implements a special graph type. The nodes of the graph
   285   /// are indiced with integers with at most \c dim binary digits.
   286   /// Two nodes are connected in the graph if and only if their indices
   287   /// differ only on one position in the binary form.
   288   ///
   289   /// \note The type of the indices is chosen to \c int for efficiency
   290   /// reasons. Thus the maximum dimension of this implementation is 26
   291   /// (assuming that the size of \c int is 32 bit).
   292   ///
   293   /// This graph type is fully conform to the \ref concepts::Graph
   294   /// "Graph" concept, and it also has an important extra feature
   295   /// that its maps are real \ref concepts::ReferenceMap
   296   /// "reference map"s.
   297   class HypercubeGraph : public ExtendedHypercubeGraphBase {
   298   public:
   299 
   300     typedef ExtendedHypercubeGraphBase Parent;
   301 
   302     /// \brief Constructs a hypercube graph with \c dim dimensions.
   303     ///
   304     /// Constructs a hypercube graph with \c dim dimensions.
   305     HypercubeGraph(int dim) { construct(dim); }
   306 
   307     /// \brief The number of dimensions.
   308     ///
   309     /// Gives back the number of dimensions.
   310     int dimension() const {
   311       return Parent::dimension();
   312     }
   313 
   314     /// \brief Returns \c true if the n'th bit of the node is one.
   315     ///
   316     /// Returns \c true if the n'th bit of the node is one.
   317     bool projection(Node node, int n) const {
   318       return Parent::projection(node, n);
   319     }
   320 
   321     /// \brief The dimension id of an edge.
   322     ///
   323     /// Gives back the dimension id of the given edge.
   324     /// It is in the [0..dim-1] range.
   325     int dimension(Edge edge) const {
   326       return Parent::dimension(edge);
   327     }
   328 
   329     /// \brief The dimension id of an arc.
   330     ///
   331     /// Gives back the dimension id of the given arc.
   332     /// It is in the [0..dim-1] range.
   333     int dimension(Arc arc) const {
   334       return Parent::dimension(arc);
   335     }
   336 
   337     /// \brief The index of a node.
   338     ///
   339     /// Gives back the index of the given node.
   340     /// The lower bits of the integer describes the node.
   341     int index(Node node) const {
   342       return Parent::index(node);
   343     }
   344 
   345     /// \brief Gives back a node by its index.
   346     ///
   347     /// Gives back a node by its index.
   348     Node operator()(int ix) const {
   349       return Parent::operator()(ix);
   350     }
   351 
   352     /// \brief Number of nodes.
   353     int nodeNum() const { return Parent::nodeNum(); }
   354     /// \brief Number of edges.
   355     int edgeNum() const { return Parent::edgeNum(); }
   356     /// \brief Number of arcs.
   357     int arcNum() const { return Parent::arcNum(); }
   358 
   359     /// \brief Linear combination map.
   360     ///
   361     /// This map makes possible to give back a linear combination
   362     /// for each node. It works like the \c std::accumulate function,
   363     /// so it accumulates the \c bf binary function with the \c fv first
   364     /// value. The map accumulates only on that positions (dimensions)
   365     /// where the index of the node is one. The values that have to be
   366     /// accumulated should be given by the \c begin and \c end iterators
   367     /// and the length of this range should be equal to the dimension
   368     /// number of the graph.
   369     ///
   370     ///\code
   371     /// const int DIM = 3;
   372     /// HypercubeGraph graph(DIM);
   373     /// dim2::Point<double> base[DIM];
   374     /// for (int k = 0; k < DIM; ++k) {
   375     ///   base[k].x = rnd();
   376     ///   base[k].y = rnd();
   377     /// }
   378     /// HypercubeGraph::HyperMap<dim2::Point<double> >
   379     ///   pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
   380     ///\endcode
   381     ///
   382     /// \see HypercubeGraph
   383     template <typename T, typename BF = std::plus<T> >
   384     class HyperMap {
   385     public:
   386 
   387       /// \brief The key type of the map
   388       typedef Node Key;
   389       /// \brief The value type of the map
   390       typedef T Value;
   391 
   392       /// \brief Constructor for HyperMap.
   393       ///
   394       /// Construct a HyperMap for the given graph. The values that have
   395       /// to be accumulated should be given by the \c begin and \c end
   396       /// iterators and the length of this range should be equal to the
   397       /// dimension number of the graph.
   398       ///
   399       /// This map accumulates the \c bf binary function with the \c fv
   400       /// first value on that positions (dimensions) where the index of
   401       /// the node is one.
   402       template <typename It>
   403       HyperMap(const Graph& graph, It begin, It end,
   404                T fv = 0, const BF& bf = BF())
   405         : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
   406       {
   407         LEMON_ASSERT(_values.size() == graph.dimension(),
   408                      "Wrong size of range");
   409       }
   410 
   411       /// \brief The partial accumulated value.
   412       ///
   413       /// Gives back the partial accumulated value.
   414       Value operator[](const Key& k) const {
   415         Value val = _first_value;
   416         int id = _graph.index(k);
   417         int n = 0;
   418         while (id != 0) {
   419           if (id & 1) {
   420             val = _bin_func(val, _values[n]);
   421           }
   422           id >>= 1;
   423           ++n;
   424         }
   425         return val;
   426       }
   427 
   428     private:
   429       const Graph& _graph;
   430       std::vector<T> _values;
   431       T _first_value;
   432       BF _bin_func;
   433     };
   434 
   435   };
   436 
   437 }
   438 
   439 #endif