COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/hypercube_graph.h @ 1963:f1ace6d02a32

Last change on this file since 1963:f1ace6d02a32 was 1963:f1ace6d02a32, checked in by Balazs Dezso, 14 years ago

Bug fix

File size: 9.3 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/invalid.h>
25#include <lemon/utility.h>
26#include <lemon/error.h>
27
28#include <lemon/bits/iterable_graph_extender.h>
29#include <lemon/bits/alteration_notifier.h>
30#include <lemon/bits/static_map.h>
31#include <lemon/bits/graph_extender.h>
32
33///\ingroup graphs
34///\file
35///\brief HyperCubeGraph class.
36
37namespace lemon {
38
39  /// \brief Base graph for HyperCubeGraph.
40  ///
41  /// Base graph for hyper-cube graph. It describes some member functions
42  /// which can be used in the HyperCubeGraph.
43  ///
44  /// \warning Always use the HyperCubeGraph instead of this.
45  /// \see HyperCubeGraph
46  class HyperCubeGraphBase {
47
48  public:
49
50    typedef HyperCubeGraphBase Graph;
51
52    class Node;
53    class Edge;
54
55  public:
56
57    HyperCubeGraphBase() {}
58
59  protected:
60
61    /// \brief Creates a hypercube graph with the given size.
62    ///
63    /// Creates a hypercube graph with the given size.
64    void construct(int dim) {
65      _dim = dim;
66      _nodeNum = 1 << dim;
67    }
68
69  public:
70   
71
72    typedef True NodeNumTag;
73    typedef True EdgeNumTag;
74
75    ///Number of nodes.
76    int nodeNum() const { return _nodeNum; }
77    ///Number of edges.
78    int edgeNum() const { return _nodeNum * _dim; }
79
80    /// Maximum node ID.
81   
82    /// Maximum node ID.
83    ///\sa id(Node)
84    int maxNodeId() const { return nodeNum() - 1; }
85    /// Maximum edge ID.
86   
87    /// Maximum edge ID.
88    ///\sa id(Edge)
89    int maxEdgeId() const { return edgeNum() - 1; }
90
91    /// \brief Gives back the source node of an edge.
92    ///   
93    /// Gives back the source node of an edge.
94    Node source(Edge e) const {
95      return e.id / _dim;
96    }
97
98    /// \brief Gives back the target node of an edge.
99    ///   
100    /// Gives back the target node of an edge.
101    Node target(Edge e) const {
102      return (e.id / _dim) ^ ( 1 << (e.id % _dim));
103    }
104
105    /// Node ID.
106   
107    /// The ID of a valid Node is a nonnegative integer not greater than
108    /// \ref maxNodeId(). The range of the ID's is not surely continuous
109    /// and the greatest node ID can be actually less then \ref maxNodeId().
110    ///
111    /// The ID of the \ref INVALID node is -1.
112    ///\return The ID of the node \c v.
113
114    static int id(Node v) { return v.id; }
115    /// Edge ID.
116   
117    /// The ID of a valid Edge is a nonnegative integer not greater than
118    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
119    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
120    ///
121    /// The ID of the \ref INVALID edge is -1.
122    ///\return The ID of the edge \c e.
123    static int id(Edge e) { return e.id; }
124
125    static Node nodeFromId(int id) { return Node(id);}
126   
127    static Edge edgeFromId(int id) { return Edge(id);}
128
129    class Node {
130      friend class HyperCubeGraphBase;
131
132    protected:
133      int id;
134      Node(int _id) { id = _id;}
135    public:
136      Node() {}
137      Node (Invalid) { id = -1; }
138      bool operator==(const Node node) const {return id == node.id;}
139      bool operator!=(const Node node) const {return id != node.id;}
140      bool operator<(const Node node) const {return id < node.id;}
141    };
142   
143    class Edge {
144      friend class HyperCubeGraphBase;
145     
146    protected:
147      int id;
148
149      Edge(int _id) : id(_id) {}
150
151    public:
152      Edge() { }
153      Edge (Invalid) { id = -1; }
154      bool operator==(const Edge edge) const {return id == edge.id;}
155      bool operator!=(const Edge edge) const {return id != edge.id;}
156      bool operator<(const Edge edge) const {return id < edge.id;}
157    };
158
159    void first(Node& node) const {
160      node.id = nodeNum() - 1;
161    }
162
163    static void next(Node& node) {
164      --node.id;
165    }
166
167    void first(Edge& edge) const {
168      edge.id = edgeNum() - 1;
169    }
170
171    static void next(Edge& edge) {
172      --edge.id;
173    }
174
175    void firstOut(Edge& edge, const Node& node) const {
176      edge.id = node.id * _dim;
177    }
178
179    void nextOut(Edge& edge) const {
180      ++edge.id;
181      if (edge.id % _dim == 0) edge.id = -1;
182    }
183
184    void firstIn(Edge& edge, const Node& node) const {
185      edge.id = (node.id ^ 1) * _dim;
186    }
187   
188    void nextIn(Edge& edge) const {
189      int cnt = edge.id % _dim;
190      if ((cnt + 1) % _dim == 0) {
191        edge.id = -1;
192      } else {
193        edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
194      }
195    }
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 _dim;
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 (bool)(node.id & (1 << n));
209    }
210
211    /// \brief The dimension id of the edge.
212    ///
213    /// It returns the dimension id of the edge. It can
214    /// be in the ${0, 1, dim-1}$ intervall.
215    int dimension(Edge edge) const {
216      return edge.id % _dim;
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 describe the node.
223    int index(Node node) const {
224      return node.id;
225    }
226
227    /// \brief Gives back the node by its index.
228    ///
229    ///  Gives back the node by its index.
230    Node node(int index) const {
231      return Node(index);
232    }
233   
234  private:
235    int _dim, _nodeNum;
236  };
237
238
239  typedef StaticMappableGraphExtender<
240    IterableGraphExtender<
241    AlterableGraphExtender<
242    GraphExtender<
243    HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase;
244
245  /// \ingroup graphs
246  ///
247  /// \brief HyperCube graph class
248  ///
249  /// This class implements a special graph type. The nodes of the
250  /// graph can be indiced with integers with at most \c dim binary length.
251  /// Two nodes are connected in the graph if the indices differ only
252  /// on one position in the binary form.
253  ///
254  /// \note The type of the \c ids is chosen to \c int because efficiency
255  /// reasons. This way the maximal dimension of this implementation
256  /// is 26.
257  ///
258  /// The graph type is fully conform to the \ref concept::StaticGraph
259  /// concept but it does not conform to the \ref concept::UGraph.
260  ///
261  /// \see HyperCubeGraphBase
262  /// \author Balazs Dezso
263  class HyperCubeGraph : public ExtendedHyperCubeGraphBase {
264  public:
265
266    /// \brief Construct a graph with \c dim dimension.
267    ///
268    /// Construct a graph with \c dim dimension.
269    HyperCubeGraph(int dim) { construct(dim); }
270
271    /// \brief Linear combination map.
272    ///
273    /// It makes possible to give back a linear combination
274    /// for each node. This function works like the \c std::accumulate
275    /// so it accumulates the \c bf binary function with the \c fv
276    /// first value. The map accumulates only on that dimensions where
277    /// the node's index is one. The accumulated values should be
278    /// given by the \c begin and \c end iterators and this range's length
279    /// should be the dimension number of the graph.
280    ///
281    ///\code
282    /// const int DIM = 3;
283    /// HyperCubeGraph graph(DIM);
284    /// xy<double> base[DIM];
285    /// for (int k = 0; k < DIM; ++k) {
286    ///   base[k].x = rand() / (RAND_MAX + 1.0);
287    ///   base[k].y = rand() / (RAND_MAX + 1.0);
288    /// }
289    /// HyperCubeGraph::HyperMap<xy<double> >
290    ///   pos(graph, base, base + DIM, xy<double>(0.0, 0.0));
291    ///\endcode
292    ///
293    /// \see HyperCubeGraph
294    template <typename T, typename BF = std::plus<T> >
295    class HyperMap {
296    public:
297
298      typedef Node Key;
299      typedef T Value;
300   
301     
302      /// \brief Constructor for HyperMap.
303      ///
304      /// Construct a HyperMap for the given graph. The accumulated values
305      /// should be given by the \c begin and \c end iterators and this
306      /// range's length should be the dimension number of the graph.
307      ///
308      /// This function accumulates the \c bf binary function with
309      /// the \c fv first value. The map accumulates only on that dimensions
310      /// where the node's index is one.           
311      template <typename It>
312      HyperMap(const Graph& graph, It begin, It end,
313                   T fv = 0.0, const BF& bf = BF())
314        : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) {
315        LEMON_ASSERT(_values.size() == graph.dimension(),
316                     "Wrong size of dimension");
317      }
318
319      /// \brief Gives back the partial accumulated value.
320      ///
321      /// Gives back the partial accumulated value.
322      Value operator[](Key k) const {
323        Value val = _first_value;
324        int id = _graph.index(k);
325        int n = 0;
326        while (id != 0) {
327          if (id & 1) {
328            val = _bin_func(_values[n], _first_value);
329          }
330          id >>= 1;
331          ++n;
332        }
333        return val;
334      }
335     
336    private:
337      const Graph& _graph;
338      std::vector<T> _values;
339      T _first_value;
340      BF _bin_func;
341    };   
342  };
343}
344#endif
345
Note: See TracBrowser for help on using the repository browser.