COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/hypercube_graph.h @ 1909:2d806130e700

Last change on this file since 1909:2d806130e700 was 1909:2d806130e700, checked in by Mihaly Barasz, 14 years ago

Undir -> U transition

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