COIN-OR::LEMON - Graph Library

source: lemon/lemon/hypercube_graph.h @ 376:b4a01426c0d9

Last change on this file since 376:b4a01426c0d9 was 376:b4a01426c0d9, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Port hypercube digraph structure from SVN 3503 (#57)

File size: 8.3 KB
Line 
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 <iostream>
23#include <vector>
24#include <lemon/core.h>
25#include <lemon/error.h>
26
27#include <lemon/bits/base_extender.h>
28#include <lemon/bits/graph_extender.h>
29
30///\ingroup graphs
31///\file
32///\brief HypercubeDigraph class.
33
34namespace lemon {
35
36  class HypercubeDigraphBase {
37
38  public:
39
40    typedef HypercubeDigraphBase Digraph;
41
42    class Node;
43    class Arc;
44
45  public:
46
47    HypercubeDigraphBase() {}
48
49  protected:
50
51    void construct(int dim) {
52      _dim = dim;
53      _nodeNum = 1 << dim;
54    }
55
56  public:
57
58    typedef True NodeNumTag;
59    typedef True ArcNumTag;
60
61    int nodeNum() const { return _nodeNum; }
62    int arcNum() const { return _nodeNum * _dim; }
63
64    int maxNodeId() const { return nodeNum() - 1; }
65    int maxArcId() const { return arcNum() - 1; }
66
67    Node source(Arc e) const {
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
78    static Node nodeFromId(int id) { return Node(id); }
79
80    static Arc arcFromId(int id) { return Arc(id); }
81
82    class Node {
83      friend class HypercubeDigraphBase;
84    protected:
85      int id;
86      Node(int _id) { id = _id;}
87    public:
88      Node() {}
89      Node (Invalid) { id = -1; }
90      bool operator==(const Node node) const { return id == node.id; }
91      bool operator!=(const Node node) const { return id != node.id; }
92      bool operator<(const Node node) const { return id < node.id; }
93    };
94
95    class Arc {
96      friend class HypercubeDigraphBase;
97    protected:
98      int id;
99      Arc(int _id) : id(_id) {}
100    public:
101      Arc() { }
102      Arc (Invalid) { id = -1; }
103      bool operator==(const Arc arc) const { return id == arc.id; }
104      bool operator!=(const Arc arc) const { return id != arc.id; }
105      bool operator<(const Arc arc) const { return id < arc.id; }
106    };
107
108    void first(Node& node) const {
109      node.id = nodeNum() - 1;
110    }
111
112    static void next(Node& node) {
113      --node.id;
114    }
115
116    void first(Arc& arc) const {
117      arc.id = arcNum() - 1;
118    }
119
120    static void next(Arc& arc) {
121      --arc.id;
122    }
123
124    void firstOut(Arc& arc, const Node& node) const {
125      arc.id = node.id * _dim;
126    }
127
128    void nextOut(Arc& arc) const {
129      ++arc.id;
130      if (arc.id % _dim == 0) arc.id = -1;
131    }
132
133    void firstIn(Arc& arc, const Node& node) const {
134      arc.id = (node.id ^ 1) * _dim;
135    }
136
137    void nextIn(Arc& arc) const {
138      int cnt = arc.id % _dim;
139      if ((cnt + 1) % _dim == 0) {
140        arc.id = -1;
141      } else {
142        arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
143      }
144    }
145
146    int dimension() const {
147      return _dim;
148    }
149
150    bool projection(Node node, int n) const {
151      return static_cast<bool>(node.id & (1 << n));
152    }
153
154    int dimension(Arc arc) const {
155      return arc.id % _dim;
156    }
157
158    int index(Node node) const {
159      return node.id;
160    }
161
162    Node operator()(int ix) const {
163      return Node(ix);
164    }
165
166  private:
167    int _dim, _nodeNum;
168  };
169
170
171  typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;
172
173  /// \ingroup digraphs
174  ///
175  /// \brief Hypercube digraph class
176  ///
177  /// This class implements a special digraph type. The nodes of the
178  /// digraph are indiced with integers with at most \c dim binary digits.
179  /// Two nodes are connected in the digraph if the indices differ only
180  /// on one position in the binary form.
181  ///
182  /// \note The type of the \c ids is chosen to \c int because efficiency
183  /// reasons. Thus the maximum dimension of this implementation is 26.
184  ///
185  /// The digraph type is fully conform to the \ref concepts::Digraph
186  /// concept but it does not conform to \ref concepts::Graph.
187  class HypercubeDigraph : public ExtendedHypercubeDigraphBase {
188  public:
189
190    typedef ExtendedHypercubeDigraphBase Parent;
191
192    /// \brief Construct a hypercube digraph with \c dim dimension.
193    ///
194    /// Construct a hypercube digraph with \c dim dimension.
195    HypercubeDigraph(int dim) { construct(dim); }
196
197    /// \brief Gives back the number of the dimensions.
198    ///
199    /// Gives back the number of the dimensions.
200    int dimension() const {
201      return Parent::dimension();
202    }
203
204    /// \brief Returns true if the n'th bit of the node is one.
205    ///
206    /// Returns true if the n'th bit of the node is one.
207    bool projection(Node node, int n) const {
208      return Parent::projection(node, n);
209    }
210
211    /// \brief The dimension id of the arc.
212    ///
213    /// It returns the dimension id of the arc. It can
214    /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval.
215    int dimension(Arc arc) const {
216      return Parent::dimension(arc);
217    }
218
219    /// \brief Gives back the index of the node.
220    ///
221    /// Gives back the index of the node. The lower bits of the
222    /// integer describes the node.
223    int index(Node node) const {
224      return Parent::index(node);
225    }
226
227    /// \brief Gives back the node by its index.
228    ///
229    /// Gives back the node by its index.
230    Node operator()(int ix) const {
231      return Parent::operator()(ix);
232    }
233
234    /// \brief Number of nodes.
235    int nodeNum() const { return Parent::nodeNum(); }
236    /// \brief Number of arcs.
237    int arcNum() const { return Parent::arcNum(); }
238
239    /// \brief Linear combination map.
240    ///
241    /// It makes possible to give back a linear combination
242    /// for each node. This function works like the \c std::accumulate
243    /// so it accumulates the \c bf binary function with the \c fv
244    /// first value. The map accumulates only on that dimensions where
245    /// the node's index is one. The accumulated values should be
246    /// given by the \c begin and \c end iterators and the length of this
247    /// range should be equal to the dimension number of the digraph.
248    ///
249    ///\code
250    /// const int DIM = 3;
251    /// HypercubeDigraph digraph(DIM);
252    /// dim2::Point<double> base[DIM];
253    /// for (int k = 0; k < DIM; ++k) {
254    ///   base[k].x = rnd();
255    ///   base[k].y = rnd();
256    /// }
257    /// HypercubeDigraph::HyperMap<dim2::Point<double> >
258    ///   pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
259    ///\endcode
260    ///
261    /// \see HypercubeDigraph
262    template <typename T, typename BF = std::plus<T> >
263    class HyperMap {
264    public:
265
266      typedef Node Key;
267      typedef T Value;
268
269
270      /// \brief Constructor for HyperMap.
271      ///
272      /// Construct a HyperMap for the given digraph. The accumulated values
273      /// should be given by the \c begin and \c end iterators and the length
274      /// of this range should be equal to the dimension number of the digraph.
275      ///
276      /// This function accumulates the \c bf binary function with
277      /// the \c fv first value. The map accumulates only on that dimensions
278      /// where the node's index is one.
279      template <typename It>
280      HyperMap(const Digraph& digraph, It begin, It end,
281               T fv = 0.0, const BF& bf = BF())
282        : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf)
283      {
284        LEMON_ASSERT(_values.size() == digraph.dimension(),
285                     "Wrong size of dimension");
286      }
287
288      /// \brief Gives back the partial accumulated value.
289      ///
290      /// Gives back the partial accumulated value.
291      Value operator[](Key k) const {
292        Value val = _first_value;
293        int id = _graph.index(k);
294        int n = 0;
295        while (id != 0) {
296          if (id & 1) {
297            val = _bin_func(val, _values[n]);
298          }
299          id >>= 1;
300          ++n;
301        }
302        return val;
303      }
304
305    private:
306      const Digraph& _graph;
307      std::vector<T> _values;
308      T _first_value;
309      BF _bin_func;
310    };
311
312  };
313
314}
315
316#endif
Note: See TracBrowser for help on using the repository browser.