FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
FG_dense_matrix.h
1 #ifndef __FG_DENSE_MATRIX_H__
2 #define __FG_DENSE_MATRIX_H__
3 
4 /*
5  * Copyright 2014 Open Connectome Project (http://openconnecto.me)
6  * Written by Da Zheng (zhengda1936@gmail.com)
7  *
8  * This file is part of FlashGraph.
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License");
11  * you may not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS,
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  */
22 
23 #include <vector>
24 #include <memory>
25 
26 #ifdef USE_EIGEN
27 #include <eigen3/Eigen/Dense>
28 #endif
29 
30 #include "FG_vector.h"
31 #include "graph.h"
32 
33 namespace fg
34 {
35 
36 template<class T>
37 class col_wise_matrix_store
38 {
39  std::vector<typename FG_vector<T>::ptr> cols;
40 public:
41  col_wise_matrix_store(size_t nrow, size_t ncol) {
42  cols.resize(ncol);
43  for (size_t i = 0; i < ncol; i++)
44  cols[i] = FG_vector<T>::create(nrow);
45  }
46 
47  void set(size_t row, size_t col, const T &v) {
48  return cols[col]->set(row, v);
49  }
50 
51  const T &get(size_t row, size_t col) const {
52  return cols[col]->get(row);
53  }
54 
55  typename FG_vector<T>::ptr get(size_t col) {
56  return cols[col];
57  }
58 
59  const std::vector<typename FG_vector<T>::ptr> &get_cols() const {
60  return cols;
61  }
62 
63  void set_cols(const std::vector<typename FG_vector<T>::ptr> &cols) {
64  this->cols = cols;
65  }
66 
67  size_t get_num_rows() const {
68  return cols[0]->get_size();
69  }
70 
71  size_t get_num_cols() const {
72  return cols.size();
73  }
74 };
75 
76 template<class T>
77 class row_wise_matrix_store
78 {
79  std::vector<typename FG_vector<T>::ptr> rows;
80 public:
81  row_wise_matrix_store(size_t nrow, size_t ncol) {
82  rows.resize(nrow);
83  for (size_t i = 0; i < nrow; i++)
84  rows[i] = FG_vector<T>::create(ncol);
85  }
86 
87  void set(size_t row, size_t col, const T &v) {
88  return rows[row]->set(col, v);
89  }
90 
91  const T &get(size_t row, size_t col) const {
92  return rows[row]->get(col);
93  }
94 
95  typename FG_vector<T>::ptr get(size_t row) {
96  return rows[row];
97  }
98 
99  const std::vector<typename FG_vector<T>::ptr> &get_rows() const {
100  return rows;
101  }
102 
103  void set_rows(const std::vector<typename FG_vector<T>::ptr> &rows) {
104  this->rows = rows;
105  }
106 
107  size_t get_num_rows() const {
108  return rows.size();
109  }
110 
111  size_t get_num_cols() const {
112  return rows[0]->get_size();
113  }
114 };
115 
116 #ifdef USE_EIGEN
117 template<class T>
118 class Eigen_matrix_store
119 {
120  Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> mat;
121 public:
122  typename Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> matrix_type;
123 
124  Eigen_matrix_store(size_t nrow, size_t ncol) {
125  mat.resize(nrow, ncol);
126  assert((size_t) mat.rows() == nrow);
127  assert((size_t) mat.cols() == ncol);
128  }
129 
130  Eigen_matrix_store(
131  const Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> &mat) {
132  this->mat = mat;
133  }
134 
135  void set(size_t row, size_t col, const T &v) {
136  mat(row, col) = v;
137  }
138 
139  const T &get(size_t row, size_t col) const {
140  return mat(row, col);
141  }
142 
143  size_t get_num_rows() const {
144  return mat.rows();
145  }
146 
147  size_t get_num_cols() const {
148  return mat.cols();
149  }
150 
151  const Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> &get_matrix() const {
152  return mat;
153  }
154 
155  Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> &get_matrix() {
156  return mat;
157  }
158 };
159 #endif
160 
161 template<class T, class MatrixStore>
162 class FG_dense_matrix
163 {
164 protected:
165  // The number of rows and columns used by the matrix.
166  size_t nrow;
167  size_t ncol;
168  // The data structure storing the matrix. Its space needs to be allocated
169  // in advance.
170  MatrixStore matrix_store;
171 
172  FG_dense_matrix(): matrix_store(0, 0) {
173  nrow = 0;
174  ncol = 0;
175  }
176 
177  FG_dense_matrix(size_t nrow, size_t ncol): matrix_store(nrow, ncol) {
178  this->nrow = 0;
179  this->ncol = 0;
180  }
181 public:
182  typedef std::shared_ptr<FG_dense_matrix<T, MatrixStore> > ptr;
183 
184  /*
185  * Create a dense matrix.
186  * `nrow' and `ncol' specify the reserved space for the matrix.
187  */
188  static ptr create(size_t nrow, size_t ncol) {
189  return ptr(new FG_dense_matrix<T, MatrixStore>(nrow, ncol));
190  }
191 
198  void set(size_t row, size_t col, T value) {
199  matrix_store.set(row, col, value);
200  }
201 
207  void set_col(size_t idx, const typename FG_vector<T>::ptr vec) {
208  assert(vec->get_size() == this->get_num_rows());
209  for (size_t i = 0; i < vec->get_size(); i++)
210  this->matrix_store.set(i, idx, vec->get(i));
211  }
212 
213 
219  void set_row(size_t idx, const typename FG_vector<T>::ptr vec) {
220  assert(vec->get_size() == this->get_num_cols());
221  for (size_t i = 0; i < vec->get_size(); i++)
222  this->matrix_store.set(idx, i, vec->get(i));
223  }
224 
225  /*
226  * Resize the matrix.
227  * `nrow' and `ncol' defined the size of the matrix. They must be smaller
228  * than or equal to the space reserved for the matrix.
229  */
230  void resize(size_t nrow, size_t ncol) {
231  assert(matrix_store.get_num_rows() >= nrow);
232  assert(matrix_store.get_num_cols() >= ncol);
233  this->nrow = nrow;
234  this->ncol = ncol;
235  }
236 
237  /*
238  * Multiply the matrix by a vector and return the result vector.
239  */
240  typename FG_vector<T>::ptr multiply(FG_vector<T> &vec) const {
241  typename FG_vector<T>::ptr ret = FG_vector<T>::create(nrow);
242 
243  struct {
244  typename FG_vector<T>::ptr fg_vec;
245  void operator()(size_t i, const T &v) {
246  this->fg_vec->set(i, v);
247  }
248  } identity_store;
249  identity_store.fg_vec = ret;
250  multiply(vec, identity_store);
251  return ret;
252  }
253 
254  /*
255  * Multiply the matrix by a vector and the user can specify how the result
256  * is stored.
257  */
258  template<class Store>
259  void multiply(FG_vector<T> &vec, Store store) const {
260  assert(vec.get_size() == ncol);
261 #pragma omp parallel for
262  for (size_t i = 0; i < nrow; i++) {
263  T res = 0;
264  for (size_t j = 0; j < ncol; j++)
265  res += get(i, j) * vec.get(j);
266  store(i, res);
267  }
268  }
269 
270  /*
271  * Multiply the matrix by another matrix.
272  * The other matrix needs to have fewer columns so that the result can be
273  * stored in the same matrix. The multiplication also changes the number
274  * of columns of the current matrix.
275  */
276  template<class MatrixStore1>
277  void multiply_in_place(FG_dense_matrix<T, MatrixStore1> &matrix) {
278  assert(ncol == matrix.get_num_rows());
279  assert(ncol >= matrix.get_num_cols());
280  std::vector<T> buf(matrix.get_num_cols());
281 #pragma omp parallel for private(buf)
282  for (size_t i = 0; i < nrow; i++) {
283  buf.resize(matrix.get_num_cols());
284  for (size_t j = 0; j < matrix.get_num_cols(); j++) {
285  T res = 0;
286  for (size_t k = 0; k < ncol; k++)
287  res += get(i, k) * matrix.get(k, j);
288  buf[j] = res;
289  }
290  for (size_t j = 0; j < matrix.get_num_cols(); j++)
291  matrix_store.set(i, j, buf[j]);
292  }
293  ncol = matrix.get_num_cols();
294  }
295 
296  const T &get(size_t row, size_t col) const {
297  return matrix_store.get(row, col);
298  }
299 
300  size_t get_num_rows() const {
301  return nrow;
302  }
303 
304  size_t get_num_cols() const {
305  return ncol;
306  }
307 };
308 
309 template<class T> class FG_col_wise_matrix;
310 template<class T> class FG_row_wise_matrix;
311 
312 template<class T>
313 class FG_row_wise_matrix: public FG_dense_matrix<T, row_wise_matrix_store<T> >
314 {
315  FG_row_wise_matrix(size_t nrow,
316  size_t ncol): FG_dense_matrix<T, row_wise_matrix_store<T> >(
317  nrow, ncol) {
318  // We assume the row-wise matrix has more columns than rows.
319  // assert(nrow < ncol); // FIXME: DM commented
320  }
321 
322  FG_row_wise_matrix(const FG_col_wise_matrix<T> &mat, bool transpose) {
323  if (transpose) {
324  this->nrow = mat.get_num_cols();
325  this->ncol = mat.get_num_rows();
326  this->matrix_store.set_rows(mat.matrix_store.get_cols());
327  }
328  else {
329  // TODO
330  assert(0);
331  }
332  // We assume the row-wise matrix has more columns than rows.
333  assert(this->nrow < this->ncol);
334  }
335 public:
336  typedef std::shared_ptr<FG_row_wise_matrix<T> > ptr;
337 
338  static ptr create(size_t nrow, size_t ncol) {
339  return ptr(new FG_row_wise_matrix<T>(nrow, ncol));
340  }
341 
342  typename FG_vector<T>::ptr get_row_ref(size_t row) {
343  assert(row < this->get_num_rows());
344  return this->matrix_store.get(row);
345  }
346 
347  /*
348  * \brief Assign all values in the matrix a single value
349  * \param val The value a user wishes to assign.
350  */
351  // TODO: DM Test
352  void assign_all(T val) {
353  #pragma omp parallel for
354  for (size_t row = 0; row < this->get_num_rows(); row++) {
355  this->matrix_store.get(row)->assign(this->get_num_cols(), val);
356  }
357  }
358 
359  template<class T1>
360  friend class FG_col_wise_matrix;
361 };
362 
363 template<class T>
364 class FG_col_wise_matrix: public FG_dense_matrix<T, col_wise_matrix_store<T> >
365 {
366  FG_col_wise_matrix(size_t nrow,
367  size_t ncol): FG_dense_matrix<T, col_wise_matrix_store<T> >(
368  nrow, ncol) {
369  }
370 public:
371  typedef std::shared_ptr<FG_col_wise_matrix<T> > ptr;
372 
373  static ptr create(size_t nrow, size_t ncol) {
374  return ptr(new FG_col_wise_matrix<T>(nrow, ncol));
375  }
376 
377  typename FG_vector<T>::ptr get_col_ref(size_t col) {
378  assert(col < this->get_num_cols());
379  return this->matrix_store.get(col);
380  }
381 
382  typename FG_row_wise_matrix<T>::ptr transpose_ref() {
383  return typename FG_row_wise_matrix<T>::ptr(
384  new FG_row_wise_matrix<T>(*this, true));
385  }
386 
387  template<class T1>
388  friend class FG_row_wise_matrix;
389 };
390 
391 #ifdef USE_EIGEN
392 template<class T>
393 class FG_eigen_matrix: public FG_dense_matrix<T, Eigen_matrix_store<T> >
394 {
395  FG_eigen_matrix(size_t nrow,
396  size_t ncol): FG_dense_matrix<T, Eigen_matrix_store<T> >(nrow, ncol) {
397  }
398 public:
399  typedef std::shared_ptr<FG_eigen_matrix<T> > ptr;
400 
401  FG_eigen_matrix(const Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic> &mat,
402  size_t nrow, size_t ncol): FG_dense_matrix<T, Eigen_matrix_store<T> >(
403  nrow, ncol) {
404  this->matrix_store = Eigen_matrix_store<T>(mat);
405  assert(nrow <= this->matrix_store.get_num_rows());
406  assert(ncol <= this->matrix_store.get_num_cols());
407  this->nrow = nrow;
408  this->ncol = ncol;
409  }
410 
411  static ptr create(size_t nrow, size_t ncol) {
412  return ptr(new FG_eigen_matrix<T>(nrow, ncol));
413  }
414 
415  void set_col(size_t idx, const FG_vector<T> &vec) {
416  assert(vec.get_size() == this->get_num_rows());
417  for (size_t i = 0; i < vec.get_size(); i++)
418  this->matrix_store.set(i, idx, vec.get(i));
419  }
420 
421  void set_row(size_t idx, const FG_vector<T> &vec) {
422  assert(vec.get_size() == this->get_num_cols());
423  for (size_t i = 0; i < vec.get_size(); i++)
424  this->matrix_store.set(idx, i, vec.get(i));
425  }
426 
427  typename FG_eigen_matrix<T>::ptr householderQ() const {
428  size_t nrows = this->matrix_store.get_num_rows();
429  size_t ncols = this->matrix_store.get_num_cols();
430  typename FG_eigen_matrix<T>::ptr ret = FG_eigen_matrix<T>::ptr(
431  new FG_eigen_matrix(nrows, ncols));
432  ret->matrix_store.get_matrix()
433  = this->matrix_store.get_matrix().householderQr().householderQ(
434  ) * Eigen::MatrixXd::Identity(nrows, ncols);
435  ret->nrow = ret->matrix_store.get_num_rows();
436  ret->ncol = ret->matrix_store.get_num_cols();
437  return ret;
438  }
439 
440  typename FG_vector<T>::ptr get_col(size_t col) const {
441  assert(col < this->ncol);
442  typename FG_vector<T>::ptr vec
443  = FG_vector<T>::create(this->get_num_rows());
444  for (size_t i = 0; i < this->get_num_rows(); i++)
445  vec->set(i, this->get(i, col));
446  return vec;
447  }
448 
449  typename FG_vector<T>::ptr get_row(size_t row) const {
450  assert(row < this->nrow);
451  typename FG_vector<T>::ptr vec
452  = FG_vector<T>::create(this->get_num_cols());
453  for (size_t i = 0; i < this->get_num_cols(); i++)
454  vec->set(i, this->get(row, i));
455  return vec;
456  }
457 
458  FG_eigen_matrix<T>::ptr transpose() const {
459  return FG_eigen_matrix<T>::ptr(new FG_eigen_matrix<T>(
460  this->matrix_store.get_matrix().transpose(),
461  this->get_num_cols(), this->get_num_rows()));
462  }
463 };
464 #endif
465 
466 }
467 
468 #endif
static ptr create(graph_engine::ptr graph)
Create a vector of the length the same as the number of vertices in the graph. An object of this clas...
Definition: FG_vector.h:65