OpenStructure
adjacency_bitmap.hh
Go to the documentation of this file.
1 #ifndef OST_MOL_ALG_ADJACENCY_BITMAP_HH
2 #define OST_MOL_ALG_ADJACENCY_BITMAP_HH
3 
4 #include <cstring>
5 #include <boost/shared_ptr.hpp>
7 #include <ost/tri_matrix.hh>
10 #include <ost/stdint.hh>
11 #include "similarity_matrix.hh"
12 #include "contact_overlap.hh"
13 #include "module_config.hh"
14 
15 namespace ost { namespace mol { namespace alg {
16 
17 
18 struct OverlapResult {
20  nominator(nom), denominator(denom), defined(def) {}
25 };
26 
27 // A highly optimized representation of the adjacency matrix
29 public:
30  explicit AdjacencyBitmap(size_t n_vertices):
31  num_vertices_(n_vertices),
32  storage_size_(StorageSize(n_vertices))
33  {
34  data_ = static_cast<uint64_t*>(malloc(this->num_bytes()));
35  end_ = data_+storage_size_*num_vertices_;
36  memset(data_, 0, this->num_bytes());
37  }
38 
40  const DistanceMatrix& dmat_b,
41  Real threshold, Real radius,
42  int start, int end):
43  num_vertices_(end-start),
44  storage_size_(StorageSize(end-start)),
45  data_(static_cast<uint64_t*>(malloc(this->num_bytes()))),
46  end_(data_+storage_size_*num_vertices_) {
47 
48  for (int i = start; i < end; ++i) {
49  this->set(i-start, i-start, false, false);
50  for (int j = i+1; j < end; ++j) {
51  Real da = dmat_a.Get(i, j);
52  Real db = dmat_b.Get(i, j);
53  bool defined = da>=0 && db>=0 && (db < radius || da < radius);
54  bool agree = false;
55  if (defined) {
56  agree = std::abs(da-db)<threshold;
57  }
58  this->set(i-start, j-start, agree, defined);
59  this->set(j-start, i-start, agree, defined);
60  }
61  }
62  }
63 
64  AdjacencyBitmap(const SimilarityMatrix& sim, Real threshold):
65  num_vertices_(sim.GetSize()),
66  storage_size_(StorageSize(sim.GetSize())),
67  data_(static_cast<uint64_t*>(malloc(this->num_bytes()))),
68  end_(data_+storage_size_*num_vertices_) {
69  memset(data_, 0, this->num_bytes());
70  for (int i = 0; i < sim.GetSize(); ++i) {
71  this->set(i, i, false, false);
72  for (int j = i+1; j < sim.GetSize(); ++j) {
73  this->set(i, j, sim.Get(i, j)>threshold, sim.Get(i, j)>=0.0);
74  this->set(j, i, sim.Get(i, j)>threshold, sim.Get(i, j)>=0.0);
75  }
76  }
77  }
78 
80  num_vertices_(rhs.num_vertices_),
81  storage_size_(rhs.storage_size_),
82  data_(static_cast<uint64_t*>(malloc(this->num_bytes()))),
83  end_(data_+storage_size_*num_vertices_) {
84  memcpy(data_, rhs.data_, this->num_bytes());
85  }
86 
88  if (data_)
89  free(data_);
90  }
91 
92  // calculates the overlap between the direct neighbours of vertex i
93  // and j using pure awesomeness and some bit trickery.
94  OverlapResult Overlap(size_t vert_i, size_t vert_j) const;
95 
96  void set(size_t i, size_t j, bool val, bool defined=true) {
97  size_t byte_index = i*storage_size_ + j/(4*sizeof(uint64_t));
98  assert(byte_index < this->num_bytes());
99  size_t bit_index = (2*j) % BITS;
100  // the following two variables are required to force use of
101  // 64 bit integer for bit operations.
102  uint64_t one = 1;
103  uint64_t two = 2;
104  assert(bit_index < sizeof(uint64_t)*8);
105 
106  if (val) {
107  data_[byte_index] |= (one << bit_index);
108  } else {
109  data_[byte_index] &= ~(one << bit_index);
110  }
111 
112  if (defined) {
113  data_[byte_index] |= (two << bit_index);
114  } else {
115  data_[byte_index] &= ~(two << bit_index);
116  }
117  }
118 
119  bool get(size_t i, size_t j) const {
120  uint64_t one = 1;
121  size_t byte_index = i*storage_size_ + j/(4*sizeof(uint64_t));
122  assert(byte_index < storage_size_*num_vertices_);
123  size_t bit_index = (2*j) % BITS;
124  assert(bit_index < sizeof(uint64_t)*8);
125  return data_[byte_index] & (one << bit_index);
126  }
127 
128  bool defined(size_t i, size_t j) const {
129  uint64_t two = 2;
130  size_t byte_index = i*storage_size_ + j/(4*sizeof(uint64_t));
131  assert(byte_index < storage_size_*num_vertices_);
132  size_t bit_index = (2*j) % BITS;
133  assert(bit_index < sizeof(uint64_t)*8);
134  return data_[byte_index] & (two << bit_index);
135  }
136 
137  size_t size() const {
138  return num_vertices_;
139  }
140 
141  size_t num_bytes() const {
142  return storage_size_*num_vertices_*sizeof(uint64_t);
143  }
144  void dump() const;
145 private:
146 
147  AdjacencyBitmap();
148  AdjacencyBitmap& operator=(const AdjacencyBitmap&);
149 
150  const static size_t BITS=sizeof(uint64_t)*8;
151  size_t num_vertices_;
152  size_t storage_size_;
153  uint64_t* data_;
154  uint64_t* end_;
155 
156  static const uint8_t NUMBER_OF_BITS_SET[];
157  static const uint8_t NUMBER_OF_EDGES_SET[];
158  static size_t StorageSize(size_t verts) {
159  return verts/(4*sizeof(uint64_t)) + (verts % (sizeof(uint64_t)*4) ? 1 : 0);
160  }
161 };
162 
163 
164 }}}
165 #endif
166 
const T & Get(int i, int j) const
Definition: tri_matrix.hh:24
int GetSize() const
Definition: tri_matrix.hh:39
bool defined(size_t i, size_t j) const
AdjacencyBitmap(const DistanceMatrix &dmat_a, const DistanceMatrix &dmat_b, Real threshold, Real radius, int start, int end)
void set(size_t i, size_t j, bool val, bool defined=true)
bool get(size_t i, size_t j) const
AdjacencyBitmap(size_t n_vertices)
OverlapResult Overlap(size_t vert_i, size_t vert_j) const
AdjacencyBitmap(const SimilarityMatrix &sim, Real threshold)
AdjacencyBitmap(const AdjacencyBitmap &rhs)
float Real
Definition: base.hh:44
pointer_it< T > end(const std::vector< T > &values)
Definition: base.dox:1
unsigned short uint16_t
Definition: stdint_msc.hh:79
unsigned char uint8_t
Definition: stdint_msc.hh:78
unsigned __int64 uint64_t
Definition: stdint_msc.hh:90
OverlapResult(uint16_t nom, uint16_t denom, uint16_t def)