COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/hypercube_graph.h @ 1989:d276e88aa48a

Last change on this file since 1989:d276e88aa48a was 1986:9b56cca61e2e, checked in by Balazs Dezso, 14 years ago

An additional simplier interface for static size graphs.
Node operator()(int) for getting node by index
int index(Node node) for getting index by node

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