lemon/hypercube_graph.h
author deba
Tue, 07 Feb 2006 09:20:47 +0000
changeset 1965 71b3bc042c47
parent 1956 a055123339d5
child 1979 c2992fd74dad
permissions -rw-r--r--
Compilation with G++ -ansi
deba@1693
     1
/* -*- C++ -*-
deba@1693
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@1956
     5
 * Copyright (C) 2003-2006
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1693
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1693
     8
 *
deba@1693
     9
 * Permission to use, modify and distribute this software is granted
deba@1693
    10
 * provided that this copyright notice appears in all copies. For
deba@1693
    11
 * precise terms see the accompanying LICENSE file.
deba@1693
    12
 *
deba@1693
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@1693
    14
 * express or implied, and with no claim as to its suitability for any
deba@1693
    15
 * purpose.
deba@1693
    16
 *
deba@1693
    17
 */
deba@1693
    18
deba@1693
    19
#ifndef HYPERCUBE_GRAPH_H
deba@1693
    20
#define HYPERCUBE_GRAPH_H
deba@1693
    21
deba@1693
    22
#include <iostream>
deba@1693
    23
#include <vector>
deba@1693
    24
#include <lemon/invalid.h>
deba@1693
    25
#include <lemon/utility.h>
deba@1791
    26
#include <lemon/error.h>
deba@1693
    27
deba@1693
    28
#include <lemon/bits/iterable_graph_extender.h>
deba@1693
    29
#include <lemon/bits/alteration_notifier.h>
deba@1963
    30
#include <lemon/bits/static_map.h>
deba@1791
    31
#include <lemon/bits/graph_extender.h>
deba@1693
    32
deba@1693
    33
///\ingroup graphs
deba@1693
    34
///\file
deba@1693
    35
///\brief HyperCubeGraph class.
deba@1693
    36
deba@1693
    37
namespace lemon {
deba@1693
    38
deba@1791
    39
  /// \brief Base graph for HyperCubeGraph.
deba@1693
    40
  ///
deba@1693
    41
  /// Base graph for hyper-cube graph. It describes some member functions
deba@1693
    42
  /// which can be used in the HyperCubeGraph.
deba@1693
    43
  ///
deba@1693
    44
  /// \warning Always use the HyperCubeGraph instead of this.
deba@1693
    45
  /// \see HyperCubeGraph
deba@1693
    46
  class HyperCubeGraphBase {
deba@1693
    47
deba@1693
    48
  public:
deba@1693
    49
deba@1693
    50
    typedef HyperCubeGraphBase Graph;
deba@1693
    51
deba@1693
    52
    class Node;
deba@1693
    53
    class Edge;
deba@1693
    54
deba@1693
    55
  public:
deba@1693
    56
deba@1693
    57
    HyperCubeGraphBase() {}
deba@1693
    58
deba@1693
    59
  protected:
deba@1693
    60
deba@1693
    61
    /// \brief Creates a hypercube graph with the given size.
deba@1693
    62
    ///
deba@1693
    63
    /// Creates a hypercube graph with the given size.
deba@1693
    64
    void construct(int dim) {
deba@1693
    65
      _dim = dim;
deba@1693
    66
      _nodeNum = 1 << dim;
deba@1693
    67
    }
deba@1693
    68
deba@1693
    69
  public:
deba@1693
    70
    
deba@1693
    71
deba@1693
    72
    typedef True NodeNumTag;
deba@1693
    73
    typedef True EdgeNumTag;
deba@1693
    74
deba@1693
    75
    ///Number of nodes.
deba@1693
    76
    int nodeNum() const { return _nodeNum; }
deba@1693
    77
    ///Number of edges.
deba@1693
    78
    int edgeNum() const { return _nodeNum * _dim; }
deba@1693
    79
deba@1693
    80
    /// Maximum node ID.
deba@1693
    81
    
deba@1693
    82
    /// Maximum node ID.
deba@1693
    83
    ///\sa id(Node)
deba@1791
    84
    int maxNodeId() const { return nodeNum() - 1; }
deba@1693
    85
    /// Maximum edge ID.
deba@1693
    86
    
deba@1693
    87
    /// Maximum edge ID.
deba@1693
    88
    ///\sa id(Edge)
deba@1791
    89
    int maxEdgeId() const { return edgeNum() - 1; }
deba@1693
    90
deba@1693
    91
    /// \brief Gives back the source node of an edge.
deba@1693
    92
    ///    
deba@1693
    93
    /// Gives back the source node of an edge.
deba@1693
    94
    Node source(Edge e) const {
deba@1693
    95
      return e.id / _dim;
deba@1693
    96
    }
deba@1693
    97
deba@1693
    98
    /// \brief Gives back the target node of an edge.
deba@1693
    99
    ///    
deba@1693
   100
    /// Gives back the target node of an edge.
deba@1693
   101
    Node target(Edge e) const {
deba@1693
   102
      return (e.id / _dim) ^ ( 1 << (e.id % _dim));
deba@1693
   103
    }
deba@1693
   104
deba@1693
   105
    /// Node ID.
deba@1693
   106
    
deba@1693
   107
    /// The ID of a valid Node is a nonnegative integer not greater than
deba@1693
   108
    /// \ref maxNodeId(). The range of the ID's is not surely continuous
deba@1693
   109
    /// and the greatest node ID can be actually less then \ref maxNodeId().
deba@1693
   110
    ///
deba@1693
   111
    /// The ID of the \ref INVALID node is -1.
deba@1693
   112
    ///\return The ID of the node \c v. 
deba@1693
   113
deba@1693
   114
    static int id(Node v) { return v.id; }
deba@1693
   115
    /// Edge ID.
deba@1693
   116
    
deba@1693
   117
    /// The ID of a valid Edge is a nonnegative integer not greater than
deba@1693
   118
    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
deba@1693
   119
    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
deba@1693
   120
    ///
deba@1693
   121
    /// The ID of the \ref INVALID edge is -1.
deba@1693
   122
    ///\return The ID of the edge \c e. 
deba@1693
   123
    static int id(Edge e) { return e.id; }
deba@1693
   124
deba@1791
   125
    static Node nodeFromId(int id) { return Node(id);}
deba@1693
   126
    
deba@1791
   127
    static Edge edgeFromId(int id) { return Edge(id);}
deba@1693
   128
deba@1693
   129
    class Node {
deba@1693
   130
      friend class HyperCubeGraphBase;
deba@1693
   131
deba@1693
   132
    protected:
deba@1693
   133
      int id;
deba@1693
   134
      Node(int _id) { id = _id;}
deba@1693
   135
    public:
deba@1693
   136
      Node() {}
deba@1693
   137
      Node (Invalid) { id = -1; }
deba@1693
   138
      bool operator==(const Node node) const {return id == node.id;}
deba@1693
   139
      bool operator!=(const Node node) const {return id != node.id;}
deba@1693
   140
      bool operator<(const Node node) const {return id < node.id;}
deba@1693
   141
    };
deba@1693
   142
    
deba@1693
   143
    class Edge {
deba@1693
   144
      friend class HyperCubeGraphBase;
deba@1693
   145
      
deba@1693
   146
    protected:
deba@1693
   147
      int id; 
deba@1693
   148
deba@1693
   149
      Edge(int _id) : id(_id) {}
deba@1693
   150
deba@1693
   151
    public:
deba@1693
   152
      Edge() { }
deba@1693
   153
      Edge (Invalid) { id = -1; }
deba@1693
   154
      bool operator==(const Edge edge) const {return id == edge.id;}
deba@1693
   155
      bool operator!=(const Edge edge) const {return id != edge.id;}
deba@1693
   156
      bool operator<(const Edge edge) const {return id < edge.id;}
deba@1693
   157
    };
deba@1693
   158
deba@1693
   159
    void first(Node& node) const {
deba@1693
   160
      node.id = nodeNum() - 1;
deba@1693
   161
    }
deba@1693
   162
deba@1693
   163
    static void next(Node& node) {
deba@1693
   164
      --node.id;
deba@1693
   165
    }
deba@1693
   166
deba@1693
   167
    void first(Edge& edge) const {
deba@1693
   168
      edge.id = edgeNum() - 1;
deba@1693
   169
    }
deba@1693
   170
deba@1693
   171
    static void next(Edge& edge) {
deba@1693
   172
      --edge.id;
deba@1693
   173
    }
deba@1693
   174
deba@1693
   175
    void firstOut(Edge& edge, const Node& node) const {
deba@1693
   176
      edge.id = node.id * _dim;
deba@1693
   177
    }
deba@1693
   178
deba@1693
   179
    void nextOut(Edge& edge) const {
deba@1693
   180
      ++edge.id;
deba@1693
   181
      if (edge.id % _dim == 0) edge.id = -1;
deba@1693
   182
    }
deba@1693
   183
deba@1693
   184
    void firstIn(Edge& edge, const Node& node) const {
deba@1693
   185
      edge.id = (node.id ^ 1) * _dim;
deba@1693
   186
    }
deba@1693
   187
    
deba@1693
   188
    void nextIn(Edge& edge) const {
deba@1693
   189
      int cnt = edge.id % _dim;
deba@1693
   190
      if ((cnt + 1) % _dim == 0) {
deba@1693
   191
	edge.id = -1;
deba@1693
   192
      } else {
deba@1693
   193
	edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1; 
deba@1693
   194
      }
deba@1693
   195
    }
deba@1693
   196
deba@1693
   197
    /// \brief Gives back the number of the dimensions.
deba@1693
   198
    ///
deba@1693
   199
    /// Gives back the number of the dimensions.
deba@1693
   200
    int dimension() const {
deba@1693
   201
      return _dim;
deba@1693
   202
    }
deba@1693
   203
deba@1693
   204
    /// \brief Returns true if the n'th bit of the node is one.
deba@1693
   205
    ///
deba@1693
   206
    /// Returns true if the n'th bit of the node is one. 
deba@1693
   207
    bool projection(Node node, int n) const {
deba@1693
   208
      return (bool)(node.id & (1 << n));
deba@1693
   209
    }
deba@1693
   210
deba@1693
   211
    /// \brief The dimension id of the edge.
deba@1693
   212
    ///
deba@1693
   213
    /// It returns the dimension id of the edge. It can
deba@1693
   214
    /// be in the ${0, 1, dim-1}$ intervall.
deba@1693
   215
    int dimension(Edge edge) const {
deba@1693
   216
      return edge.id % _dim;
deba@1693
   217
    }
deba@1693
   218
deba@1693
   219
    /// \brief Gives back the index of the node.
deba@1693
   220
    ///
deba@1693
   221
    /// Gives back the index of the node. The lower bits of the
deba@1693
   222
    /// integer describe the node.
deba@1693
   223
    int index(Node node) const {
deba@1693
   224
      return node.id;
deba@1693
   225
    }
deba@1693
   226
deba@1693
   227
    /// \brief Gives back the node by its index.
deba@1693
   228
    ///
deba@1693
   229
    ///  Gives back the node by its index.
deba@1693
   230
    Node node(int index) const {
deba@1693
   231
      return Node(index);
deba@1693
   232
    }
deba@1693
   233
    
deba@1693
   234
  private:
deba@1693
   235
    int _dim, _nodeNum;
deba@1693
   236
  };
deba@1693
   237
deba@1693
   238
deba@1703
   239
  typedef StaticMappableGraphExtender<
deba@1693
   240
    IterableGraphExtender<
deba@1693
   241
    AlterableGraphExtender<
deba@1791
   242
    GraphExtender<
deba@1791
   243
    HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase;
deba@1693
   244
deba@1693
   245
  /// \ingroup graphs
deba@1693
   246
  ///
deba@1693
   247
  /// \brief HyperCube graph class
deba@1693
   248
  ///
deba@1693
   249
  /// This class implements a special graph type. The nodes of the
deba@1693
   250
  /// graph can be indiced with integers with at most \c dim binary length.
deba@1693
   251
  /// Two nodes are connected in the graph if the indices differ only
deba@1693
   252
  /// on one position in the binary form. 
deba@1693
   253
  ///
deba@1693
   254
  /// \note The type of the \c ids is chosen to \c int because efficiency
deba@1693
   255
  /// reasons. This way the maximal dimension of this implementation
deba@1693
   256
  /// is 26. 
deba@1693
   257
  ///
deba@1693
   258
  /// The graph type is fully conform to the \ref concept::StaticGraph
klao@1909
   259
  /// concept but it does not conform to the \ref concept::UGraph.
deba@1693
   260
  ///
deba@1693
   261
  /// \see HyperCubeGraphBase
deba@1693
   262
  /// \author Balazs Dezso
deba@1693
   263
  class HyperCubeGraph : public ExtendedHyperCubeGraphBase {
deba@1693
   264
  public:
deba@1693
   265
deba@1693
   266
    /// \brief Construct a graph with \c dim dimension.
deba@1693
   267
    ///
deba@1693
   268
    /// Construct a graph with \c dim dimension.
deba@1693
   269
    HyperCubeGraph(int dim) { construct(dim); }
deba@1693
   270
deba@1693
   271
    /// \brief Linear combination map.
deba@1693
   272
    ///
deba@1693
   273
    /// It makes possible to give back a linear combination
deba@1693
   274
    /// for each node. This function works like the \c std::accumulate
deba@1693
   275
    /// so it accumulates the \c bf binary function with the \c fv
deba@1693
   276
    /// first value. The map accumulates only on that dimensions where
deba@1693
   277
    /// the node's index is one. The accumulated values should be
deba@1693
   278
    /// given by the \c begin and \c end iterators and this range's length
deba@1693
   279
    /// should be the dimension number of the graph.
deba@1693
   280
    /// 
alpar@1946
   281
    ///\code
deba@1693
   282
    /// const int DIM = 3;
deba@1693
   283
    /// HyperCubeGraph graph(DIM);
deba@1693
   284
    /// xy<double> base[DIM];
deba@1693
   285
    /// for (int k = 0; k < DIM; ++k) {
deba@1693
   286
    ///   base[k].x = rand() / (RAND_MAX + 1.0);
deba@1693
   287
    ///   base[k].y = rand() / (RAND_MAX + 1.0);
deba@1693
   288
    /// } 
deba@1693
   289
    /// HyperCubeGraph::HyperMap<xy<double> > 
deba@1693
   290
    ///   pos(graph, base, base + DIM, xy<double>(0.0, 0.0));
alpar@1946
   291
    ///\endcode
deba@1693
   292
    ///
deba@1693
   293
    /// \see HyperCubeGraph
deba@1693
   294
    template <typename T, typename BF = std::plus<T> >
deba@1693
   295
    class HyperMap {
deba@1693
   296
    public:
deba@1693
   297
deba@1693
   298
      typedef Node Key;
deba@1693
   299
      typedef T Value;
deba@1693
   300
    
deba@1693
   301
      
deba@1693
   302
      /// \brief Constructor for HyperMap. 
deba@1693
   303
      ///
deba@1693
   304
      /// Construct a HyperMap for the given graph. The accumulated values 
deba@1693
   305
      /// should be given by the \c begin and \c end iterators and this 
deba@1693
   306
      /// range's length should be the dimension number of the graph.
deba@1693
   307
      ///
deba@1693
   308
      /// This function accumulates the \c bf binary function with 
deba@1693
   309
      /// the \c fv first value. The map accumulates only on that dimensions 
deba@1693
   310
      /// where the node's index is one.           
deba@1693
   311
      template <typename It>
deba@1693
   312
      HyperMap(const Graph& graph, It begin, It end, 
deba@1693
   313
		   T fv = 0.0, const BF& bf = BF()) 
deba@1693
   314
	: _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) {
deba@1963
   315
	LEMON_ASSERT(_values.size() == graph.dimension(), 
deba@1791
   316
		     "Wrong size of dimension");
deba@1693
   317
      }
deba@1693
   318
deba@1693
   319
      /// \brief Gives back the partial accumulated value.
deba@1693
   320
      ///
deba@1693
   321
      /// Gives back the partial accumulated value.
deba@1693
   322
      Value operator[](Key k) const {
deba@1693
   323
	Value val = _first_value;
deba@1693
   324
	int id = _graph.index(k); 
deba@1693
   325
	int n = 0;
deba@1693
   326
	while (id != 0) {
deba@1693
   327
	  if (id & 1) {
deba@1693
   328
	    val = _bin_func(_values[n], _first_value);
deba@1693
   329
	  }
deba@1693
   330
	  id >>= 1;
deba@1693
   331
	  ++n;
deba@1693
   332
	}
deba@1693
   333
	return val;
deba@1693
   334
      }
deba@1693
   335
      
deba@1693
   336
    private:
deba@1693
   337
      const Graph& _graph;
deba@1693
   338
      std::vector<T> _values;
deba@1693
   339
      T _first_value;
deba@1693
   340
      BF _bin_func;
deba@1693
   341
    };    
deba@1693
   342
  };
deba@1693
   343
}
deba@1693
   344
#endif
deba@1693
   345