In algorithm window maps can be selected and reated through MapSelector widget.
2 * lemon/hypercube_graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
17 #ifndef HYPERCUBE_GRAPH_H
18 #define HYPERCUBE_GRAPH_H
22 #include <lemon/invalid.h>
23 #include <lemon/utility.h>
24 #include <lemon/error.h>
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>
33 ///\brief HyperCubeGraph class.
37 /// \brief Base graph for HyperCubeGraph.
39 /// Base graph for hyper-cube graph. It describes some member functions
40 /// which can be used in the HyperCubeGraph.
42 /// \warning Always use the HyperCubeGraph instead of this.
43 /// \see HyperCubeGraph
44 class HyperCubeGraphBase {
48 typedef HyperCubeGraphBase Graph;
55 HyperCubeGraphBase() {}
59 /// \brief Creates a hypercube graph with the given size.
61 /// Creates a hypercube graph with the given size.
62 void construct(int dim) {
70 typedef True NodeNumTag;
71 typedef True EdgeNumTag;
74 int nodeNum() const { return _nodeNum; }
76 int edgeNum() const { return _nodeNum * _dim; }
82 int maxNodeId() const { return nodeNum() - 1; }
87 int maxEdgeId() const { return edgeNum() - 1; }
89 /// \brief Gives back the source node of an edge.
91 /// Gives back the source node of an edge.
92 Node source(Edge e) const {
96 /// \brief Gives back the target node of an edge.
98 /// Gives back the target node of an edge.
99 Node target(Edge e) const {
100 return (e.id / _dim) ^ ( 1 << (e.id % _dim));
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().
109 /// The ID of the \ref INVALID node is -1.
110 ///\return The ID of the node \c v.
112 static int id(Node v) { return v.id; }
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().
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; }
123 static Node nodeFromId(int id) { return Node(id);}
125 static Edge edgeFromId(int id) { return Edge(id);}
128 friend class HyperCubeGraphBase;
132 Node(int _id) { id = _id;}
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;}
142 friend class HyperCubeGraphBase;
147 Edge(int _id) : id(_id) {}
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;}
157 void first(Node& node) const {
158 node.id = nodeNum() - 1;
161 static void next(Node& node) {
165 void first(Edge& edge) const {
166 edge.id = edgeNum() - 1;
169 static void next(Edge& edge) {
173 void firstOut(Edge& edge, const Node& node) const {
174 edge.id = node.id * _dim;
177 void nextOut(Edge& edge) const {
179 if (edge.id % _dim == 0) edge.id = -1;
182 void firstIn(Edge& edge, const Node& node) const {
183 edge.id = (node.id ^ 1) * _dim;
186 void nextIn(Edge& edge) const {
187 int cnt = edge.id % _dim;
188 if ((cnt + 1) % _dim == 0) {
191 edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
195 /// \brief Gives back the number of the dimensions.
197 /// Gives back the number of the dimensions.
198 int dimension() const {
202 /// \brief Returns true if the n'th bit of the node is one.
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));
209 /// \brief The dimension id of the edge.
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;
217 /// \brief Gives back the index of the node.
219 /// Gives back the index of the node. The lower bits of the
220 /// integer describe the node.
221 int index(Node node) const {
225 /// \brief Gives back the node by its index.
227 /// Gives back the node by its index.
228 Node node(int index) const {
237 typedef StaticMappableGraphExtender<
238 IterableGraphExtender<
239 AlterableGraphExtender<
241 HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase;
245 /// \brief HyperCube graph class
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.
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
256 /// The graph type is fully conform to the \ref concept::StaticGraph
257 /// concept but it does not conform to the \ref concept::UndirGraph.
259 /// \see HyperCubeGraphBase
260 /// \author Balazs Dezso
261 class HyperCubeGraph : public ExtendedHyperCubeGraphBase {
264 /// \brief Construct a graph with \c dim dimension.
266 /// Construct a graph with \c dim dimension.
267 HyperCubeGraph(int dim) { construct(dim); }
269 /// \brief Linear combination map.
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.
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);
287 /// HyperCubeGraph::HyperMap<xy<double> >
288 /// pos(graph, base, base + DIM, xy<double>(0.0, 0.0));
291 /// \see HyperCubeGraph
292 template <typename T, typename BF = std::plus<T> >
300 /// \brief Constructor for HyperMap.
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.
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");
317 /// \brief Gives back the partial accumulated value.
319 /// Gives back the partial accumulated value.
320 Value operator[](Key k) const {
321 Value val = _first_value;
322 int id = _graph.index(k);
326 val = _bin_func(_values[n], _first_value);
336 std::vector<T> _values;