1.1 --- a/lemon/Makefile.am Tue Nov 04 10:25:47 2008 +0000
1.2 +++ b/lemon/Makefile.am Wed Nov 05 21:36:28 2008 +0100
1.3 @@ -31,6 +31,7 @@
1.4 lemon/full_graph.h \
1.5 lemon/graph_to_eps.h \
1.6 lemon/grid_graph.h \
1.7 + lemon/hypercube_graph.h \
1.8 lemon/kruskal.h \
1.9 lemon/lgf_reader.h \
1.10 lemon/lgf_writer.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/hypercube_graph.h Wed Nov 05 21:36:28 2008 +0100
2.3 @@ -0,0 +1,316 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef HYPERCUBE_GRAPH_H
2.23 +#define HYPERCUBE_GRAPH_H
2.24 +
2.25 +#include <iostream>
2.26 +#include <vector>
2.27 +#include <lemon/core.h>
2.28 +#include <lemon/error.h>
2.29 +
2.30 +#include <lemon/bits/base_extender.h>
2.31 +#include <lemon/bits/graph_extender.h>
2.32 +
2.33 +///\ingroup graphs
2.34 +///\file
2.35 +///\brief HypercubeDigraph class.
2.36 +
2.37 +namespace lemon {
2.38 +
2.39 + class HypercubeDigraphBase {
2.40 +
2.41 + public:
2.42 +
2.43 + typedef HypercubeDigraphBase Digraph;
2.44 +
2.45 + class Node;
2.46 + class Arc;
2.47 +
2.48 + public:
2.49 +
2.50 + HypercubeDigraphBase() {}
2.51 +
2.52 + protected:
2.53 +
2.54 + void construct(int dim) {
2.55 + _dim = dim;
2.56 + _nodeNum = 1 << dim;
2.57 + }
2.58 +
2.59 + public:
2.60 +
2.61 + typedef True NodeNumTag;
2.62 + typedef True ArcNumTag;
2.63 +
2.64 + int nodeNum() const { return _nodeNum; }
2.65 + int arcNum() const { return _nodeNum * _dim; }
2.66 +
2.67 + int maxNodeId() const { return nodeNum() - 1; }
2.68 + int maxArcId() const { return arcNum() - 1; }
2.69 +
2.70 + Node source(Arc e) const {
2.71 + return e.id / _dim;
2.72 + }
2.73 +
2.74 + Node target(Arc e) const {
2.75 + return (e.id / _dim) ^ (1 << (e.id % _dim));
2.76 + }
2.77 +
2.78 + static int id(Node v) { return v.id; }
2.79 + static int id(Arc e) { return e.id; }
2.80 +
2.81 + static Node nodeFromId(int id) { return Node(id); }
2.82 +
2.83 + static Arc arcFromId(int id) { return Arc(id); }
2.84 +
2.85 + class Node {
2.86 + friend class HypercubeDigraphBase;
2.87 + protected:
2.88 + int id;
2.89 + Node(int _id) { id = _id;}
2.90 + public:
2.91 + Node() {}
2.92 + Node (Invalid) { id = -1; }
2.93 + bool operator==(const Node node) const { return id == node.id; }
2.94 + bool operator!=(const Node node) const { return id != node.id; }
2.95 + bool operator<(const Node node) const { return id < node.id; }
2.96 + };
2.97 +
2.98 + class Arc {
2.99 + friend class HypercubeDigraphBase;
2.100 + protected:
2.101 + int id;
2.102 + Arc(int _id) : id(_id) {}
2.103 + public:
2.104 + Arc() { }
2.105 + Arc (Invalid) { id = -1; }
2.106 + bool operator==(const Arc arc) const { return id == arc.id; }
2.107 + bool operator!=(const Arc arc) const { return id != arc.id; }
2.108 + bool operator<(const Arc arc) const { return id < arc.id; }
2.109 + };
2.110 +
2.111 + void first(Node& node) const {
2.112 + node.id = nodeNum() - 1;
2.113 + }
2.114 +
2.115 + static void next(Node& node) {
2.116 + --node.id;
2.117 + }
2.118 +
2.119 + void first(Arc& arc) const {
2.120 + arc.id = arcNum() - 1;
2.121 + }
2.122 +
2.123 + static void next(Arc& arc) {
2.124 + --arc.id;
2.125 + }
2.126 +
2.127 + void firstOut(Arc& arc, const Node& node) const {
2.128 + arc.id = node.id * _dim;
2.129 + }
2.130 +
2.131 + void nextOut(Arc& arc) const {
2.132 + ++arc.id;
2.133 + if (arc.id % _dim == 0) arc.id = -1;
2.134 + }
2.135 +
2.136 + void firstIn(Arc& arc, const Node& node) const {
2.137 + arc.id = (node.id ^ 1) * _dim;
2.138 + }
2.139 +
2.140 + void nextIn(Arc& arc) const {
2.141 + int cnt = arc.id % _dim;
2.142 + if ((cnt + 1) % _dim == 0) {
2.143 + arc.id = -1;
2.144 + } else {
2.145 + arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
2.146 + }
2.147 + }
2.148 +
2.149 + int dimension() const {
2.150 + return _dim;
2.151 + }
2.152 +
2.153 + bool projection(Node node, int n) const {
2.154 + return static_cast<bool>(node.id & (1 << n));
2.155 + }
2.156 +
2.157 + int dimension(Arc arc) const {
2.158 + return arc.id % _dim;
2.159 + }
2.160 +
2.161 + int index(Node node) const {
2.162 + return node.id;
2.163 + }
2.164 +
2.165 + Node operator()(int ix) const {
2.166 + return Node(ix);
2.167 + }
2.168 +
2.169 + private:
2.170 + int _dim, _nodeNum;
2.171 + };
2.172 +
2.173 +
2.174 + typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;
2.175 +
2.176 + /// \ingroup digraphs
2.177 + ///
2.178 + /// \brief Hypercube digraph class
2.179 + ///
2.180 + /// This class implements a special digraph type. The nodes of the
2.181 + /// digraph are indiced with integers with at most \c dim binary digits.
2.182 + /// Two nodes are connected in the digraph if the indices differ only
2.183 + /// on one position in the binary form.
2.184 + ///
2.185 + /// \note The type of the \c ids is chosen to \c int because efficiency
2.186 + /// reasons. Thus the maximum dimension of this implementation is 26.
2.187 + ///
2.188 + /// The digraph type is fully conform to the \ref concepts::Digraph
2.189 + /// concept but it does not conform to \ref concepts::Graph.
2.190 + class HypercubeDigraph : public ExtendedHypercubeDigraphBase {
2.191 + public:
2.192 +
2.193 + typedef ExtendedHypercubeDigraphBase Parent;
2.194 +
2.195 + /// \brief Construct a hypercube digraph with \c dim dimension.
2.196 + ///
2.197 + /// Construct a hypercube digraph with \c dim dimension.
2.198 + HypercubeDigraph(int dim) { construct(dim); }
2.199 +
2.200 + /// \brief Gives back the number of the dimensions.
2.201 + ///
2.202 + /// Gives back the number of the dimensions.
2.203 + int dimension() const {
2.204 + return Parent::dimension();
2.205 + }
2.206 +
2.207 + /// \brief Returns true if the n'th bit of the node is one.
2.208 + ///
2.209 + /// Returns true if the n'th bit of the node is one.
2.210 + bool projection(Node node, int n) const {
2.211 + return Parent::projection(node, n);
2.212 + }
2.213 +
2.214 + /// \brief The dimension id of the arc.
2.215 + ///
2.216 + /// It returns the dimension id of the arc. It can
2.217 + /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval.
2.218 + int dimension(Arc arc) const {
2.219 + return Parent::dimension(arc);
2.220 + }
2.221 +
2.222 + /// \brief Gives back the index of the node.
2.223 + ///
2.224 + /// Gives back the index of the node. The lower bits of the
2.225 + /// integer describes the node.
2.226 + int index(Node node) const {
2.227 + return Parent::index(node);
2.228 + }
2.229 +
2.230 + /// \brief Gives back the node by its index.
2.231 + ///
2.232 + /// Gives back the node by its index.
2.233 + Node operator()(int ix) const {
2.234 + return Parent::operator()(ix);
2.235 + }
2.236 +
2.237 + /// \brief Number of nodes.
2.238 + int nodeNum() const { return Parent::nodeNum(); }
2.239 + /// \brief Number of arcs.
2.240 + int arcNum() const { return Parent::arcNum(); }
2.241 +
2.242 + /// \brief Linear combination map.
2.243 + ///
2.244 + /// It makes possible to give back a linear combination
2.245 + /// for each node. This function works like the \c std::accumulate
2.246 + /// so it accumulates the \c bf binary function with the \c fv
2.247 + /// first value. The map accumulates only on that dimensions where
2.248 + /// the node's index is one. The accumulated values should be
2.249 + /// given by the \c begin and \c end iterators and the length of this
2.250 + /// range should be equal to the dimension number of the digraph.
2.251 + ///
2.252 + ///\code
2.253 + /// const int DIM = 3;
2.254 + /// HypercubeDigraph digraph(DIM);
2.255 + /// dim2::Point<double> base[DIM];
2.256 + /// for (int k = 0; k < DIM; ++k) {
2.257 + /// base[k].x = rnd();
2.258 + /// base[k].y = rnd();
2.259 + /// }
2.260 + /// HypercubeDigraph::HyperMap<dim2::Point<double> >
2.261 + /// pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
2.262 + ///\endcode
2.263 + ///
2.264 + /// \see HypercubeDigraph
2.265 + template <typename T, typename BF = std::plus<T> >
2.266 + class HyperMap {
2.267 + public:
2.268 +
2.269 + typedef Node Key;
2.270 + typedef T Value;
2.271 +
2.272 +
2.273 + /// \brief Constructor for HyperMap.
2.274 + ///
2.275 + /// Construct a HyperMap for the given digraph. The accumulated values
2.276 + /// should be given by the \c begin and \c end iterators and the length
2.277 + /// of this range should be equal to the dimension number of the digraph.
2.278 + ///
2.279 + /// This function accumulates the \c bf binary function with
2.280 + /// the \c fv first value. The map accumulates only on that dimensions
2.281 + /// where the node's index is one.
2.282 + template <typename It>
2.283 + HyperMap(const Digraph& digraph, It begin, It end,
2.284 + T fv = 0.0, const BF& bf = BF())
2.285 + : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf)
2.286 + {
2.287 + LEMON_ASSERT(_values.size() == digraph.dimension(),
2.288 + "Wrong size of dimension");
2.289 + }
2.290 +
2.291 + /// \brief Gives back the partial accumulated value.
2.292 + ///
2.293 + /// Gives back the partial accumulated value.
2.294 + Value operator[](Key k) const {
2.295 + Value val = _first_value;
2.296 + int id = _graph.index(k);
2.297 + int n = 0;
2.298 + while (id != 0) {
2.299 + if (id & 1) {
2.300 + val = _bin_func(val, _values[n]);
2.301 + }
2.302 + id >>= 1;
2.303 + ++n;
2.304 + }
2.305 + return val;
2.306 + }
2.307 +
2.308 + private:
2.309 + const Digraph& _graph;
2.310 + std::vector<T> _values;
2.311 + T _first_value;
2.312 + BF _bin_func;
2.313 + };
2.314 +
2.315 + };
2.316 +
2.317 +}
2.318 +
2.319 +#endif
3.1 --- a/test/digraph_test.cc Tue Nov 04 10:25:47 2008 +0000
3.2 +++ b/test/digraph_test.cc Wed Nov 05 21:36:28 2008 +0100
3.3 @@ -20,7 +20,7 @@
3.4 #include <lemon/list_graph.h>
3.5 #include <lemon/smart_graph.h>
3.6 #include <lemon/full_graph.h>
3.7 -//#include <lemon/hypercube_graph.h>
3.8 +#include <lemon/hypercube_graph.h>
3.9
3.10 #include "test_tools.h"
3.11 #include "graph_test.h"
3.12 @@ -112,6 +112,35 @@
3.13
3.14 }
3.15
3.16 +void checkHypercubeDigraph(int dim) {
3.17 + DIGRAPH_TYPEDEFS(HypercubeDigraph);
3.18 +
3.19 + HypercubeDigraph G(dim);
3.20 + checkGraphNodeList(G, 1 << dim);
3.21 + checkGraphArcList(G, (1 << dim) * dim);
3.22 +
3.23 + Node n = G.nodeFromId(dim);
3.24 +
3.25 + checkGraphOutArcList(G, n, dim);
3.26 + for (OutArcIt a(G, n); a != INVALID; ++a)
3.27 + check(G.source(a) == n &&
3.28 + G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)),
3.29 + "Wrong arc");
3.30 +
3.31 + checkGraphInArcList(G, n, dim);
3.32 + for (InArcIt a(G, n); a != INVALID; ++a)
3.33 + check(G.target(a) == n &&
3.34 + G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)),
3.35 + "Wrong arc");
3.36 +
3.37 + checkGraphConArcList(G, (1 << dim) * dim);
3.38 +
3.39 + checkNodeIds(G);
3.40 + checkArcIds(G);
3.41 + checkGraphNodeMap(G);
3.42 + checkGraphArcMap(G);
3.43 +}
3.44 +
3.45
3.46 void checkConcepts() {
3.47 { // Checking digraph components
3.48 @@ -145,9 +174,9 @@
3.49 { // Checking FullDigraph
3.50 checkConcept<Digraph, FullDigraph>();
3.51 }
3.52 -// { // Checking HyperCubeDigraph
3.53 -// checkConcept<Digraph, HyperCubeDigraph>();
3.54 -// }
3.55 + { // Checking HypercubeDigraph
3.56 + checkConcept<Digraph, HypercubeDigraph>();
3.57 + }
3.58 }
3.59
3.60 template <typename Digraph>
3.61 @@ -212,6 +241,12 @@
3.62 { // Checking FullDigraph
3.63 checkFullDigraph(8);
3.64 }
3.65 + { // Checking HypercubeDigraph
3.66 + checkHypercubeDigraph(1);
3.67 + checkHypercubeDigraph(2);
3.68 + checkHypercubeDigraph(3);
3.69 + checkHypercubeDigraph(4);
3.70 + }
3.71 }
3.72
3.73 int main() {