deba@1693: /* -*- C++ -*-
deba@1693:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * 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 <iostream>
deba@1693: #include <vector>
deba@1993: #include <lemon/bits/invalid.h>
deba@1993: #include <lemon/bits/utility.h>
deba@1791: #include <lemon/error.h>
deba@1693: 
deba@1998: #include <lemon/bits/base_extender.h>
deba@1791: #include <lemon/bits/graph_extender.h>
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@1986:     Node operator()(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@1979:   typedef GraphExtender<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
klao@1909:   /// concept but it does not conform to the \ref concept::UGraph.
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:     /// 
alpar@1946:     ///\code
deba@1693:     /// const int DIM = 3;
deba@1693:     /// HyperCubeGraph graph(DIM);
deba@1693:     /// xy<double> 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<xy<double> > 
deba@1693:     ///   pos(graph, base, base + DIM, xy<double>(0.0, 0.0));
alpar@1946:     ///\endcode
deba@1693:     ///
deba@1693:     /// \see HyperCubeGraph
deba@1693:     template <typename T, typename BF = std::plus<T> >
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 <typename It>
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@1963: 	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@1998: 	    val = _bin_func(val, _values[n]);
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<T> _values;
deba@1693:       T _first_value;
deba@1693:       BF _bin_func;
deba@1693:     };    
deba@1693:   };
deba@1693: }
deba@1693: #endif
deba@1693: