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