COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/hypercube_graph.h @ 2260:4274224f8a7d

Last change on this file since 2260:4274224f8a7d was 2260:4274224f8a7d, checked in by Alpar Juttner, 13 years ago

concept -> concepts (namespace & directory)

File size: 8.2 KB
Line 
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
35namespace 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 concepts::Graph
193  /// concept but it does not conform to the \ref concepts::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 = rnd();
264    ///   base[k].y = rnd();
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
Note: See TracBrowser for help on using the repository browser.