FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
FG_sparse_matrix.h
1 #ifndef __FG_SPARSE_MATRIX_H__
2 #define __FG_SPARSE_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 "graph_engine.h"
24 #include "FGlib.h"
25 
26 namespace fg
27 {
28 
29 class matrix_vertex: public compute_vertex
30 {
31 public:
32  matrix_vertex(vertex_id_t id): compute_vertex(id) {
33  }
34 
35  void run(vertex_program &prog) {
36  vertex_id_t id = prog.get_vertex_id(*this);
37  request_vertices(&id, 1);
38  }
39 
40  void run(vertex_program &prog, const page_vertex &vertex) {
41  }
42 
43  void run_on_message(vertex_program &prog, const vertex_message &msg) {
44  }
45 };
46 
47 /*
48  * The vertex program for sparse matrix vector multiplication
49  * on the general sparse matrix.
50  */
51 template<class ResType, class MatEntryType>
52 class SPMV_vertex_program: public vertex_program_impl<matrix_vertex>
53 {
54  edge_type type;
55  const FG_vector<ResType> &input;
56  FG_vector<ResType> &output;
57 
59  const page_vertex &v, edge_type type) {
60  if (v.is_directed())
61  return ((const page_directed_vertex &) v).get_data_seq_it<MatEntryType>(type);
62  else
63  return ((const page_undirected_vertex &) v).get_data_seq_it<MatEntryType>();
64  }
65 public:
66  SPMV_vertex_program(edge_type type, const FG_vector<ResType> &_input,
67  FG_vector<ResType> &_output): input(_input), output(_output) {
68  this->type = type;
69  }
70 
71  virtual void run(compute_vertex &, const page_vertex &vertex) {
72  edge_seq_iterator it = vertex.get_neigh_seq_it(type, 0,
73  vertex.get_num_edges(type));
75  = get_data_iterator(vertex, type);
76  ResType w = 0;
77  while (it.has_next()) {
78  vertex_id_t neigh_id = it.next();
79  MatEntryType val = d_it.next();
80  w += input.get(neigh_id) * val;
81  }
82  output.set(vertex.get_id(), w);
83  }
84 };
85 
86 /*
87  * The vertex program for sparse matrix vector multiplication
88  * on the adjacency matrix.
89  */
90 template<class ResType>
91 class SPMV_vertex_program<ResType, empty_data>: public vertex_program_impl<matrix_vertex>
92 {
93  edge_type type;
94  const FG_vector<ResType> &input;
95  FG_vector<ResType> &output;
96 public:
97  SPMV_vertex_program(edge_type type, const FG_vector<ResType> &_input,
98  FG_vector<ResType> &_output): input(_input), output(_output) {
99  this->type = type;
100  }
101 
102  virtual void run(compute_vertex &, const page_vertex &vertex) {
103  edge_seq_iterator it = vertex.get_neigh_seq_it(type, 0,
104  vertex.get_num_edges(type));
105  ResType w = 0;
106  while (it.has_next()) {
107  vertex_id_t neigh_id = it.next();
108  w += input.get(neigh_id);
109  }
110  output.set(vertex.get_id(), w);
111  }
112 };
113 
114 template<class ResType, class MatEntryType>
115 class SPMV_vertex_program_creater: public vertex_program_creater
116 {
117  const FG_vector<ResType> &input;
118  FG_vector<ResType> &output;
119  edge_type etype;
120 public:
121  SPMV_vertex_program_creater(edge_type etype, const FG_vector<ResType> &_input,
122  FG_vector<ResType> &_output): input(_input), output(_output) {
123  this->etype = etype;
124  }
125 
126  vertex_program::ptr create() const {
127  return vertex_program::ptr(
128  new SPMV_vertex_program<ResType, MatEntryType>(etype,
129  input, output));
130  }
131 };
132 
133 template<class EntryType>
134 class FG_sparse_matrix
135 {
136  size_t nrow;
137  size_t ncol;
138 
139  // The type of edges that specifies the rows of the matrix.
140  // For a symmetric matrix, the edge type does not matter.
141  edge_type etype;
142  graph_engine::ptr graph;
143 
144  FG_sparse_matrix() {
145  etype = edge_type::NONE;
146  nrow = 0;
147  ncol = 0;
148  }
149 
150 protected:
151  FG_sparse_matrix(FG_graph::ptr fg) {
152  graph_index::ptr index = NUMA_graph_index<matrix_vertex>::create(
153  fg->get_graph_header());
154  graph = fg->create_engine(index);
155  etype = edge_type::OUT_EDGE;
156  this->nrow = graph->get_num_vertices();
157  this->ncol = graph->get_num_vertices();
158  }
159 public:
160  typedef std::shared_ptr<FG_sparse_matrix<EntryType> > ptr;
161 
162  static ptr create(FG_graph::ptr fg) {
163  return ptr(new FG_sparse_matrix<EntryType>(fg));
164  }
165 
166  void resize(size_t nrow, size_t ncol) {
167  this->nrow = nrow;
168  this->ncol = ncol;
169  assert(nrow <= graph->get_num_vertices());
170  assert(ncol <= graph->get_num_vertices());
171  // TODO we need to check if we can resize like this.
172  }
173 
174  template<class T>
175  void multiply(const FG_vector<T> &input, FG_vector<T> &output) const {
176  assert(input.get_size() == get_num_cols());
177  assert(output.get_size() == get_num_rows());
178  graph->start_all(vertex_initializer::ptr(),
179  vertex_program_creater::ptr(
180  new SPMV_vertex_program_creater<T, EntryType>(
181  etype, input, output)));
182  graph->wait4complete();
183  }
184 
185  size_t get_num_rows() const {
186  return nrow;
187  }
188 
189  size_t get_num_cols() const {
190  return ncol;
191  }
192 
193  typename FG_sparse_matrix<EntryType>::ptr transpose() const {
194  typename FG_sparse_matrix<EntryType>::ptr t
195  = typename FG_sparse_matrix<EntryType>::ptr(
196  new FG_sparse_matrix<EntryType>());
197  if (this->etype == IN_EDGE)
198  t->etype = OUT_EDGE;
199  else if (this->etype == OUT_EDGE)
200  t->etype = IN_EDGE;
201  else
202  assert(0);
203  t->graph = this->graph;
204  t->nrow = this->ncol;
205  t->ncol = this->nrow;
206  return t;
207  }
208 };
209 
210 typedef FG_sparse_matrix<empty_data> FG_adj_matrix;
211 
212 }
213 
214 #endif
compute_vertex(vertex_id_t id)
The constructor called by graph_engine to create vertex state.
Definition: graph_engine.h:61
edge_type
Edge type of an edge in the graph.
Definition: vertex.h:43
void request_vertices(vertex_id_t ids[], size_t num)
This allows a vertex to request the adjacency lists of vertices in the graph.
virtual void run(compute_vertex &comp_v)
This is a pre-run before users get any information of adjacency list of vertices. This is commonly wh...
Definition: vertex_program.h:276
Definition: vertex.h:45
Definition: vertex.h:46