hypercube_graph.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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 

Generated on Fri Feb 3 18:37:45 2006 for LEMON by  doxygen 1.4.6