COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/hypercube_graph.h @ 1703:eb90e3d6bddc

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

Proper sized map type

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