1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef HYPERCUBE_GRAPH_H
20 #define HYPERCUBE_GRAPH_H
24 #include <lemon/core.h>
25 #include <lemon/error.h>
27 #include <lemon/bits/base_extender.h>
28 #include <lemon/bits/graph_extender.h>
32 ///\brief HypercubeDigraph class.
36 class HypercubeDigraphBase {
40 typedef HypercubeDigraphBase Digraph;
47 HypercubeDigraphBase() {}
51 void construct(int dim) {
58 typedef True NodeNumTag;
59 typedef True ArcNumTag;
61 int nodeNum() const { return _nodeNum; }
62 int arcNum() const { return _nodeNum * _dim; }
64 int maxNodeId() const { return nodeNum() - 1; }
65 int maxArcId() const { return arcNum() - 1; }
67 Node source(Arc e) const {
71 Node target(Arc e) const {
72 return (e.id / _dim) ^ (1 << (e.id % _dim));
75 static int id(Node v) { return v.id; }
76 static int id(Arc e) { return e.id; }
78 static Node nodeFromId(int id) { return Node(id); }
80 static Arc arcFromId(int id) { return Arc(id); }
83 friend class HypercubeDigraphBase;
86 Node(int _id) { id = _id;}
89 Node (Invalid) { id = -1; }
90 bool operator==(const Node node) const { return id == node.id; }
91 bool operator!=(const Node node) const { return id != node.id; }
92 bool operator<(const Node node) const { return id < node.id; }
96 friend class HypercubeDigraphBase;
99 Arc(int _id) : id(_id) {}
102 Arc (Invalid) { id = -1; }
103 bool operator==(const Arc arc) const { return id == arc.id; }
104 bool operator!=(const Arc arc) const { return id != arc.id; }
105 bool operator<(const Arc arc) const { return id < arc.id; }
108 void first(Node& node) const {
109 node.id = nodeNum() - 1;
112 static void next(Node& node) {
116 void first(Arc& arc) const {
117 arc.id = arcNum() - 1;
120 static void next(Arc& arc) {
124 void firstOut(Arc& arc, const Node& node) const {
125 arc.id = node.id * _dim;
128 void nextOut(Arc& arc) const {
130 if (arc.id % _dim == 0) arc.id = -1;
133 void firstIn(Arc& arc, const Node& node) const {
134 arc.id = (node.id ^ 1) * _dim;
137 void nextIn(Arc& arc) const {
138 int cnt = arc.id % _dim;
139 if ((cnt + 1) % _dim == 0) {
142 arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
146 int dimension() const {
150 bool projection(Node node, int n) const {
151 return static_cast<bool>(node.id & (1 << n));
154 int dimension(Arc arc) const {
155 return arc.id % _dim;
158 int index(Node node) const {
162 Node operator()(int ix) const {
171 typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;
173 /// \ingroup digraphs
175 /// \brief Hypercube digraph class
177 /// This class implements a special digraph type. The nodes of the
178 /// digraph are indiced with integers with at most \c dim binary digits.
179 /// Two nodes are connected in the digraph if the indices differ only
180 /// on one position in the binary form.
182 /// \note The type of the \c ids is chosen to \c int because efficiency
183 /// reasons. Thus the maximum dimension of this implementation is 26.
185 /// The digraph type is fully conform to the \ref concepts::Digraph
186 /// concept but it does not conform to \ref concepts::Graph.
187 class HypercubeDigraph : public ExtendedHypercubeDigraphBase {
190 typedef ExtendedHypercubeDigraphBase Parent;
192 /// \brief Construct a hypercube digraph with \c dim dimension.
194 /// Construct a hypercube digraph with \c dim dimension.
195 HypercubeDigraph(int dim) { construct(dim); }
197 /// \brief Gives back the number of the dimensions.
199 /// Gives back the number of the dimensions.
200 int dimension() const {
201 return Parent::dimension();
204 /// \brief Returns true if the n'th bit of the node is one.
206 /// Returns true if the n'th bit of the node is one.
207 bool projection(Node node, int n) const {
208 return Parent::projection(node, n);
211 /// \brief The dimension id of the arc.
213 /// It returns the dimension id of the arc. It can
214 /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval.
215 int dimension(Arc arc) const {
216 return Parent::dimension(arc);
219 /// \brief Gives back the index of the node.
221 /// Gives back the index of the node. The lower bits of the
222 /// integer describes the node.
223 int index(Node node) const {
224 return Parent::index(node);
227 /// \brief Gives back the node by its index.
229 /// Gives back the node by its index.
230 Node operator()(int ix) const {
231 return Parent::operator()(ix);
234 /// \brief Number of nodes.
235 int nodeNum() const { return Parent::nodeNum(); }
236 /// \brief Number of arcs.
237 int arcNum() const { return Parent::arcNum(); }
239 /// \brief Linear combination map.
241 /// It makes possible to give back a linear combination
242 /// for each node. This function works like the \c std::accumulate
243 /// so it accumulates the \c bf binary function with the \c fv
244 /// first value. The map accumulates only on that dimensions where
245 /// the node's index is one. The accumulated values should be
246 /// given by the \c begin and \c end iterators and the length of this
247 /// range should be equal to the dimension number of the digraph.
250 /// const int DIM = 3;
251 /// HypercubeDigraph digraph(DIM);
252 /// dim2::Point<double> base[DIM];
253 /// for (int k = 0; k < DIM; ++k) {
254 /// base[k].x = rnd();
255 /// base[k].y = rnd();
257 /// HypercubeDigraph::HyperMap<dim2::Point<double> >
258 /// pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
261 /// \see HypercubeDigraph
262 template <typename T, typename BF = std::plus<T> >
270 /// \brief Constructor for HyperMap.
272 /// Construct a HyperMap for the given digraph. The accumulated values
273 /// should be given by the \c begin and \c end iterators and the length
274 /// of this range should be equal to the dimension number of the digraph.
276 /// This function accumulates the \c bf binary function with
277 /// the \c fv first value. The map accumulates only on that dimensions
278 /// where the node's index is one.
279 template <typename It>
280 HyperMap(const Digraph& digraph, It begin, It end,
281 T fv = 0.0, const BF& bf = BF())
282 : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf)
284 LEMON_ASSERT(_values.size() == digraph.dimension(),
285 "Wrong size of dimension");
288 /// \brief Gives back the partial accumulated value.
290 /// Gives back the partial accumulated value.
291 Value operator[](Key k) const {
292 Value val = _first_value;
293 int id = _graph.index(k);
297 val = _bin_func(val, _values[n]);
306 const Digraph& _graph;
307 std::vector<T> _values;