COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/hypercube_graph.h @ 1981:81c8efe92706

Last change on this file since 1981:81c8efe92706 was 1979:c2992fd74dad, checked in by Balazs Dezso, 18 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

File size: 9.0 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 node(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.