00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef HYPERCUBE_GRAPH_H
00020 #define HYPERCUBE_GRAPH_H
00021
00022 #include <iostream>
00023 #include <vector>
00024 #include <lemon/invalid.h>
00025 #include <lemon/utility.h>
00026 #include <lemon/error.h>
00027
00028 #include <lemon/bits/iterable_graph_extender.h>
00029 #include <lemon/bits/alteration_notifier.h>
00030 #include <lemon/bits/default_map.h>
00031 #include <lemon/bits/graph_extender.h>
00032
00036
00037 namespace lemon {
00038
00046 class HyperCubeGraphBase {
00047
00048 public:
00049
00050 typedef HyperCubeGraphBase Graph;
00051
00052 class Node;
00053 class Edge;
00054
00055 public:
00056
00057 HyperCubeGraphBase() {}
00058
00059 protected:
00060
00064 void construct(int dim) {
00065 _dim = dim;
00066 _nodeNum = 1 << dim;
00067 }
00068
00069 public:
00070
00071
00072 typedef True NodeNumTag;
00073 typedef True EdgeNumTag;
00074
00076 int nodeNum() const { return _nodeNum; }
00078 int edgeNum() const { return _nodeNum * _dim; }
00079
00081
00084 int maxNodeId() const { return nodeNum() - 1; }
00086
00089 int maxEdgeId() const { return edgeNum() - 1; }
00090
00094 Node source(Edge e) const {
00095 return e.id / _dim;
00096 }
00097
00101 Node target(Edge e) const {
00102 return (e.id / _dim) ^ ( 1 << (e.id % _dim));
00103 }
00104
00106
00113
00114 static int id(Node v) { return v.id; }
00116
00123 static int id(Edge e) { return e.id; }
00124
00125 static Node nodeFromId(int id) { return Node(id);}
00126
00127 static Edge edgeFromId(int id) { return Edge(id);}
00128
00129 class Node {
00130 friend class HyperCubeGraphBase;
00131
00132 protected:
00133 int id;
00134 Node(int _id) { id = _id;}
00135 public:
00136 Node() {}
00137 Node (Invalid) { id = -1; }
00138 bool operator==(const Node node) const {return id == node.id;}
00139 bool operator!=(const Node node) const {return id != node.id;}
00140 bool operator<(const Node node) const {return id < node.id;}
00141 };
00142
00143 class Edge {
00144 friend class HyperCubeGraphBase;
00145
00146 protected:
00147 int id;
00148
00149 Edge(int _id) : id(_id) {}
00150
00151 public:
00152 Edge() { }
00153 Edge (Invalid) { id = -1; }
00154 bool operator==(const Edge edge) const {return id == edge.id;}
00155 bool operator!=(const Edge edge) const {return id != edge.id;}
00156 bool operator<(const Edge edge) const {return id < edge.id;}
00157 };
00158
00159 void first(Node& node) const {
00160 node.id = nodeNum() - 1;
00161 }
00162
00163 static void next(Node& node) {
00164 --node.id;
00165 }
00166
00167 void first(Edge& edge) const {
00168 edge.id = edgeNum() - 1;
00169 }
00170
00171 static void next(Edge& edge) {
00172 --edge.id;
00173 }
00174
00175 void firstOut(Edge& edge, const Node& node) const {
00176 edge.id = node.id * _dim;
00177 }
00178
00179 void nextOut(Edge& edge) const {
00180 ++edge.id;
00181 if (edge.id % _dim == 0) edge.id = -1;
00182 }
00183
00184 void firstIn(Edge& edge, const Node& node) const {
00185 edge.id = (node.id ^ 1) * _dim;
00186 }
00187
00188 void nextIn(Edge& edge) const {
00189 int cnt = edge.id % _dim;
00190 if ((cnt + 1) % _dim == 0) {
00191 edge.id = -1;
00192 } else {
00193 edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
00194 }
00195 }
00196
00200 int dimension() const {
00201 return _dim;
00202 }
00203
00207 bool projection(Node node, int n) const {
00208 return (bool)(node.id & (1 << n));
00209 }
00210
00215 int dimension(Edge edge) const {
00216 return edge.id % _dim;
00217 }
00218
00223 int index(Node node) const {
00224 return node.id;
00225 }
00226
00230 Node node(int index) const {
00231 return Node(index);
00232 }
00233
00234 private:
00235 int _dim, _nodeNum;
00236 };
00237
00238
00239 typedef StaticMappableGraphExtender<
00240 IterableGraphExtender<
00241 AlterableGraphExtender<
00242 GraphExtender<
00243 HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase;
00244
00263 class HyperCubeGraph : public ExtendedHyperCubeGraphBase {
00264 public:
00265
00269 HyperCubeGraph(int dim) { construct(dim); }
00270
00294 template <typename T, typename BF = std::plus<T> >
00295 class HyperMap {
00296 public:
00297
00298 typedef Node Key;
00299 typedef T Value;
00300
00301
00311 template <typename It>
00312 HyperMap(const Graph& graph, It begin, It end,
00313 T fv = 0.0, const BF& bf = BF())
00314 : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) {
00315 LEMON_ASSERT(_values.size() != graph.dimension(),
00316 "Wrong size of dimension");
00317 }
00318
00322 Value operator[](Key k) const {
00323 Value val = _first_value;
00324 int id = _graph.index(k);
00325 int n = 0;
00326 while (id != 0) {
00327 if (id & 1) {
00328 val = _bin_func(_values[n], _first_value);
00329 }
00330 id >>= 1;
00331 ++n;
00332 }
00333 return val;
00334 }
00335
00336 private:
00337 const Graph& _graph;
00338 std::vector<T> _values;
00339 T _first_value;
00340 BF _bin_func;
00341 };
00342 };
00343 }
00344 #endif
00345