deba@1693: /* -*- C++ -*- deba@1693: * lemon/hypercube_graph.h - Part of LEMON, a generic C++ optimization library deba@1693: * alpar@1875: * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1693: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1693: * deba@1693: * Permission to use, modify and distribute this software is granted deba@1693: * provided that this copyright notice appears in all copies. For deba@1693: * precise terms see the accompanying LICENSE file. deba@1693: * deba@1693: * This software is provided "AS IS" with no warranty of any kind, deba@1693: * express or implied, and with no claim as to its suitability for any deba@1693: * purpose. deba@1693: * deba@1693: */ deba@1693: deba@1693: #ifndef HYPERCUBE_GRAPH_H deba@1693: #define HYPERCUBE_GRAPH_H deba@1693: deba@1693: #include deba@1693: #include deba@1693: #include deba@1693: #include deba@1791: #include deba@1693: deba@1693: #include deba@1693: #include deba@1693: #include deba@1791: #include deba@1693: deba@1693: ///\ingroup graphs deba@1693: ///\file deba@1693: ///\brief HyperCubeGraph class. deba@1693: deba@1693: namespace lemon { deba@1693: deba@1791: /// \brief Base graph for HyperCubeGraph. deba@1693: /// deba@1693: /// Base graph for hyper-cube graph. It describes some member functions deba@1693: /// which can be used in the HyperCubeGraph. deba@1693: /// deba@1693: /// \warning Always use the HyperCubeGraph instead of this. deba@1693: /// \see HyperCubeGraph deba@1693: class HyperCubeGraphBase { deba@1693: deba@1693: public: deba@1693: deba@1693: typedef HyperCubeGraphBase Graph; deba@1693: deba@1693: class Node; deba@1693: class Edge; deba@1693: deba@1693: public: deba@1693: deba@1693: HyperCubeGraphBase() {} deba@1693: deba@1693: protected: deba@1693: deba@1693: /// \brief Creates a hypercube graph with the given size. deba@1693: /// deba@1693: /// Creates a hypercube graph with the given size. deba@1693: void construct(int dim) { deba@1693: _dim = dim; deba@1693: _nodeNum = 1 << dim; deba@1693: } deba@1693: deba@1693: public: deba@1693: deba@1693: deba@1693: typedef True NodeNumTag; deba@1693: typedef True EdgeNumTag; deba@1693: deba@1693: ///Number of nodes. deba@1693: int nodeNum() const { return _nodeNum; } deba@1693: ///Number of edges. deba@1693: int edgeNum() const { return _nodeNum * _dim; } deba@1693: deba@1693: /// Maximum node ID. deba@1693: deba@1693: /// Maximum node ID. deba@1693: ///\sa id(Node) deba@1791: int maxNodeId() const { return nodeNum() - 1; } deba@1693: /// Maximum edge ID. deba@1693: deba@1693: /// Maximum edge ID. deba@1693: ///\sa id(Edge) deba@1791: int maxEdgeId() const { return edgeNum() - 1; } deba@1693: deba@1693: /// \brief Gives back the source node of an edge. deba@1693: /// deba@1693: /// Gives back the source node of an edge. deba@1693: Node source(Edge e) const { deba@1693: return e.id / _dim; deba@1693: } deba@1693: deba@1693: /// \brief Gives back the target node of an edge. deba@1693: /// deba@1693: /// Gives back the target node of an edge. deba@1693: Node target(Edge e) const { deba@1693: return (e.id / _dim) ^ ( 1 << (e.id % _dim)); deba@1693: } deba@1693: deba@1693: /// Node ID. deba@1693: deba@1693: /// The ID of a valid Node is a nonnegative integer not greater than deba@1693: /// \ref maxNodeId(). The range of the ID's is not surely continuous deba@1693: /// and the greatest node ID can be actually less then \ref maxNodeId(). deba@1693: /// deba@1693: /// The ID of the \ref INVALID node is -1. deba@1693: ///\return The ID of the node \c v. deba@1693: deba@1693: static int id(Node v) { return v.id; } deba@1693: /// Edge ID. deba@1693: deba@1693: /// The ID of a valid Edge is a nonnegative integer not greater than deba@1693: /// \ref maxEdgeId(). The range of the ID's is not surely continuous deba@1693: /// and the greatest edge ID can be actually less then \ref maxEdgeId(). deba@1693: /// deba@1693: /// The ID of the \ref INVALID edge is -1. deba@1693: ///\return The ID of the edge \c e. deba@1693: static int id(Edge e) { return e.id; } deba@1693: deba@1791: static Node nodeFromId(int id) { return Node(id);} deba@1693: deba@1791: static Edge edgeFromId(int id) { return Edge(id);} deba@1693: deba@1693: class Node { deba@1693: friend class HyperCubeGraphBase; deba@1693: deba@1693: protected: deba@1693: int id; deba@1693: Node(int _id) { id = _id;} deba@1693: public: deba@1693: Node() {} deba@1693: Node (Invalid) { id = -1; } deba@1693: bool operator==(const Node node) const {return id == node.id;} deba@1693: bool operator!=(const Node node) const {return id != node.id;} deba@1693: bool operator<(const Node node) const {return id < node.id;} deba@1693: }; deba@1693: deba@1693: class Edge { deba@1693: friend class HyperCubeGraphBase; deba@1693: deba@1693: protected: deba@1693: int id; deba@1693: deba@1693: Edge(int _id) : id(_id) {} deba@1693: deba@1693: public: deba@1693: Edge() { } deba@1693: Edge (Invalid) { id = -1; } deba@1693: bool operator==(const Edge edge) const {return id == edge.id;} deba@1693: bool operator!=(const Edge edge) const {return id != edge.id;} deba@1693: bool operator<(const Edge edge) const {return id < edge.id;} deba@1693: }; deba@1693: deba@1693: void first(Node& node) const { deba@1693: node.id = nodeNum() - 1; deba@1693: } deba@1693: deba@1693: static void next(Node& node) { deba@1693: --node.id; deba@1693: } deba@1693: deba@1693: void first(Edge& edge) const { deba@1693: edge.id = edgeNum() - 1; deba@1693: } deba@1693: deba@1693: static void next(Edge& edge) { deba@1693: --edge.id; deba@1693: } deba@1693: deba@1693: void firstOut(Edge& edge, const Node& node) const { deba@1693: edge.id = node.id * _dim; deba@1693: } deba@1693: deba@1693: void nextOut(Edge& edge) const { deba@1693: ++edge.id; deba@1693: if (edge.id % _dim == 0) edge.id = -1; deba@1693: } deba@1693: deba@1693: void firstIn(Edge& edge, const Node& node) const { deba@1693: edge.id = (node.id ^ 1) * _dim; deba@1693: } deba@1693: deba@1693: void nextIn(Edge& edge) const { deba@1693: int cnt = edge.id % _dim; deba@1693: if ((cnt + 1) % _dim == 0) { deba@1693: edge.id = -1; deba@1693: } else { deba@1693: edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1; deba@1693: } deba@1693: } deba@1693: deba@1693: /// \brief Gives back the number of the dimensions. deba@1693: /// deba@1693: /// Gives back the number of the dimensions. deba@1693: int dimension() const { deba@1693: return _dim; deba@1693: } deba@1693: deba@1693: /// \brief Returns true if the n'th bit of the node is one. deba@1693: /// deba@1693: /// Returns true if the n'th bit of the node is one. deba@1693: bool projection(Node node, int n) const { deba@1693: return (bool)(node.id & (1 << n)); deba@1693: } deba@1693: deba@1693: /// \brief The dimension id of the edge. deba@1693: /// deba@1693: /// It returns the dimension id of the edge. It can deba@1693: /// be in the ${0, 1, dim-1}$ intervall. deba@1693: int dimension(Edge edge) const { deba@1693: return edge.id % _dim; deba@1693: } deba@1693: deba@1693: /// \brief Gives back the index of the node. deba@1693: /// deba@1693: /// Gives back the index of the node. The lower bits of the deba@1693: /// integer describe the node. deba@1693: int index(Node node) const { deba@1693: return node.id; deba@1693: } deba@1693: deba@1693: /// \brief Gives back the node by its index. deba@1693: /// deba@1693: /// Gives back the node by its index. deba@1693: Node node(int index) const { deba@1693: return Node(index); deba@1693: } deba@1693: deba@1693: private: deba@1693: int _dim, _nodeNum; deba@1693: }; deba@1693: deba@1693: deba@1703: typedef StaticMappableGraphExtender< deba@1693: IterableGraphExtender< deba@1693: AlterableGraphExtender< deba@1791: GraphExtender< deba@1791: HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase; deba@1693: deba@1693: /// \ingroup graphs deba@1693: /// deba@1693: /// \brief HyperCube graph class deba@1693: /// deba@1693: /// This class implements a special graph type. The nodes of the deba@1693: /// graph can be indiced with integers with at most \c dim binary length. deba@1693: /// Two nodes are connected in the graph if the indices differ only deba@1693: /// on one position in the binary form. deba@1693: /// deba@1693: /// \note The type of the \c ids is chosen to \c int because efficiency deba@1693: /// reasons. This way the maximal dimension of this implementation deba@1693: /// is 26. deba@1693: /// deba@1693: /// The graph type is fully conform to the \ref concept::StaticGraph deba@1693: /// concept but it does not conform to the \ref concept::UndirGraph. deba@1693: /// deba@1693: /// \see HyperCubeGraphBase deba@1693: /// \author Balazs Dezso deba@1693: class HyperCubeGraph : public ExtendedHyperCubeGraphBase { deba@1693: public: deba@1693: deba@1693: /// \brief Construct a graph with \c dim dimension. deba@1693: /// deba@1693: /// Construct a graph with \c dim dimension. deba@1693: HyperCubeGraph(int dim) { construct(dim); } deba@1693: deba@1693: /// \brief Linear combination map. deba@1693: /// deba@1693: /// It makes possible to give back a linear combination deba@1693: /// for each node. This function works like the \c std::accumulate deba@1693: /// so it accumulates the \c bf binary function with the \c fv deba@1693: /// first value. The map accumulates only on that dimensions where deba@1693: /// the node's index is one. The accumulated values should be deba@1693: /// given by the \c begin and \c end iterators and this range's length deba@1693: /// should be the dimension number of the graph. deba@1693: /// deba@1693: /// \code deba@1693: /// const int DIM = 3; deba@1693: /// HyperCubeGraph graph(DIM); deba@1693: /// xy base[DIM]; deba@1693: /// for (int k = 0; k < DIM; ++k) { deba@1693: /// base[k].x = rand() / (RAND_MAX + 1.0); deba@1693: /// base[k].y = rand() / (RAND_MAX + 1.0); deba@1693: /// } deba@1693: /// HyperCubeGraph::HyperMap > deba@1693: /// pos(graph, base, base + DIM, xy(0.0, 0.0)); deba@1693: /// \endcode deba@1693: /// deba@1693: /// \see HyperCubeGraph deba@1693: template > deba@1693: class HyperMap { deba@1693: public: deba@1693: deba@1693: typedef Node Key; deba@1693: typedef T Value; deba@1693: deba@1693: deba@1693: /// \brief Constructor for HyperMap. deba@1693: /// deba@1693: /// Construct a HyperMap for the given graph. The accumulated values deba@1693: /// should be given by the \c begin and \c end iterators and this deba@1693: /// range's length should be the dimension number of the graph. deba@1693: /// deba@1693: /// This function accumulates the \c bf binary function with deba@1693: /// the \c fv first value. The map accumulates only on that dimensions deba@1693: /// where the node's index is one. deba@1693: template deba@1693: HyperMap(const Graph& graph, It begin, It end, deba@1693: T fv = 0.0, const BF& bf = BF()) deba@1693: : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) { deba@1791: LEMON_ASSERT(_values.size() != graph.dimension(), deba@1791: "Wrong size of dimension"); deba@1693: } deba@1693: deba@1693: /// \brief Gives back the partial accumulated value. deba@1693: /// deba@1693: /// Gives back the partial accumulated value. deba@1693: Value operator[](Key k) const { deba@1693: Value val = _first_value; deba@1693: int id = _graph.index(k); deba@1693: int n = 0; deba@1693: while (id != 0) { deba@1693: if (id & 1) { deba@1693: val = _bin_func(_values[n], _first_value); deba@1693: } deba@1693: id >>= 1; deba@1693: ++n; deba@1693: } deba@1693: return val; deba@1693: } deba@1693: deba@1693: private: deba@1693: const Graph& _graph; deba@1693: std::vector _values; deba@1693: T _first_value; deba@1693: BF _bin_func; deba@1693: }; deba@1693: }; deba@1693: } deba@1693: #endif deba@1693: