GraphChi  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Macros
graph_objects.hpp
Go to the documentation of this file.
1 
30 #ifndef DEF_GRAPHCHI_OBJECTS
31 #define DEF_GRAPHCHI_OBJECTS
32 
33 #include <vector>
34 #include <assert.h>
35 #include <omp.h>
36 #include <string.h>
37 
38 #include "graphchi_types.hpp"
39 #include "util/qsort.hpp"
40 
41 namespace graphchi {
42 
47 #ifdef __GNUC__
48 #define VARIABLE_IS_NOT_USED __attribute__ ((unused))
49 #else
50 #define VARIABLE_IS_NOT_USED
51 #endif
52 
53  template <typename EdgeDataType>
54  class graphchi_edge {
55 
56  public:
57  vid_t vertexid; // Source or Target vertex id. Clear from context.
58  EdgeDataType * data_ptr;
59 
60  graphchi_edge() {}
61  graphchi_edge(vid_t _vertexid, EdgeDataType * edata_ptr) : vertexid(_vertexid), data_ptr(edata_ptr) {
62  }
63 
64 
65  EdgeDataType get_data() {
66  return * data_ptr;
67  }
68 
69  void set_data(EdgeDataType x) {
70  *data_ptr = x;
71  }
72 
76  vid_t vertex_id() {
77  return vertexid;
78  }
79 
80 
81  };
82 
83  template <typename ET>
84  bool eptr_less(const graphchi_edge<ET> &a, const graphchi_edge<ET> &b) {
85  return a.vertexid < b.vertexid;
86  }
87 
88 
89  template <typename VertexDataType, typename EdgeDataType>
91 
92  public: // Todo, use friend
93  int inc;
94  volatile int outc;
95 
96  vid_t vertexid;
97 
98  protected:
99  graphchi_edge<EdgeDataType> * inedges_ptr;
100  graphchi_edge<EdgeDataType> * outedges_ptr;
101 
102 
103  public:
104  bool modified;
105  VertexDataType * dataptr;
106 
107 
108  /* Accessed directly by the engine */
109  bool scheduled;
110  bool parallel_safe;
111 
112 #ifdef SUPPORT_DELETIONS
113  int deleted_inc;
114  int deleted_outc;
115 #endif
116 
117 
118  internal_graphchi_vertex() : inc(0), outc(0) {
119 #ifdef SUPPORT_DELETIONS
120  deleted_outc = deleted_inc = 0;
121 #endif
122  dataptr = NULL;
123  }
124 
125 
128  int indeg,
129  int outdeg) :
130  vertexid(_id), inedges_ptr(iptr), outedges_ptr(optr) {
131  inc = 0;
132  outc = 0;
133  scheduled = false;
134  modified = false;
135  parallel_safe = true;
136  dataptr = NULL;
137 #ifdef SUPPORT_DELETIONS
138  deleted_inc = 0;
139  deleted_outc = 0;
140 #endif
141  }
142 
143  virtual ~internal_graphchi_vertex() {}
144 
145 
146  vid_t id() const {
147  return vertexid;
148  }
149 
150  int num_inedges() const {
151  return inc;
152 
153  }
154  int num_outedges() const {
155  return outc;
156  }
157  int num_edges() const {
158  return inc + outc;
159  }
160 
161 
162  // Optimization: as only memshard (not streaming shard) creates inedgers,
163  // we do not need atomic instructions here!
164  inline void add_inedge(vid_t src, EdgeDataType * ptr, bool special_edge) {
165 #ifdef SUPPORT_DELETIONS
166  if (inedges_ptr != NULL && is_deleted_edge_value(*ptr)) {
167  deleted_inc++;
168  return;
169  }
170 #endif
171  if (inedges_ptr != NULL) inedges_ptr[inc] = graphchi_edge<EdgeDataType>(src, ptr);
172  inc++;
173 
174  assert(src != vertexid);
175  }
176 
177  inline void add_outedge(vid_t dst, EdgeDataType * ptr, bool special_edge) {
178 #ifdef SUPPORT_DELETIONS
179  if (outedges_ptr != NULL && is_deleted_edge_value(*ptr)) {
180  deleted_outc++;
181  return;
182  }
183 #endif
184  int i = __sync_add_and_fetch(&outc, 1);
185  if (outedges_ptr != NULL) outedges_ptr[i-1] = graphchi_edge<EdgeDataType>(dst, ptr);
186  assert(dst != vertexid);
187  }
188 
189 
190  };
191 
192  template <typename VertexDataType, typename EdgeDataType >
193  class graphchi_vertex : public internal_graphchi_vertex<VertexDataType, EdgeDataType> {
194 
195  public:
196 
198 
199  graphchi_vertex(vid_t _id,
202  int indeg,
203  int outdeg) :
204  internal_graphchi_vertex<VertexDataType, EdgeDataType>(_id, iptr, optr, indeg, outdeg) {}
205 
206  virtual ~graphchi_vertex() {}
207 
213  if (i < this->inc) return inedge(i);
214  else return outedge(i - this->inc);
215  }
216 
217 
218  graphchi_edge<EdgeDataType> * inedge(int i) {
219  assert(i >= 0 && i < this->inc);
220  return &this->inedges_ptr[i];
221  }
222 
223  graphchi_edge<EdgeDataType> * outedge(int i) {
224  assert(i >= 0 && i < this->outc);
225  return &this->outedges_ptr[i];
226  }
227 
228 
229 
234  return *(this->dataptr);
235  }
236 
241  virtual void set_data(VertexDataType d) {
242  *(this->dataptr) = d;
243  this->modified = true;
244  }
245 
246  // TODO: rethink
247  static bool computational_edges() {
248  return false;
249  }
250  static bool read_outedges() {
251  return true;
252  }
253 
254 
261  // Check for deleted edges first...
262  if (this->inc != (this->outedges_ptr - this->inedges_ptr)) {
263  // Moving
264  memmove(&this->inedges_ptr[this->inc], this->outedges_ptr, this->outc * sizeof(graphchi_edge<EdgeDataType>));
265  this->outedges_ptr = &this->inedges_ptr[this->inc];
266  }
267  quickSort(this->inedges_ptr, (int) (this->inc + this->outc), eptr_less<EdgeDataType>);
268 
269  }
270 
271 
272 #ifdef SUPPORT_DELETIONS
273  void VARIABLE_IS_NOT_USED remove_edge(int i) {
274  remove_edgev(edge(i));
275  }
276 
277  void VARIABLE_IS_NOT_USED remove_inedge(int i) {
278  remove_edgev(inedge(i));
279  }
280 
281  void VARIABLE_IS_NOT_USED remove_outedge(int i) {
282  remove_edgev(outedge(i));
283  }
284 #endif
285 
286 
287  };
288 
293  // If highest order bit is set, the edge is "special". This is used
294  // to indicate - in the neighborhood model - that neighbor's value is
295  // cached in memory.
296 #define HIGHMASK (1 + (2147483647 >> 1))
297 #define CLEARMASK (2147483647 >> 1)
298  inline vid_t translate_edge(vid_t rawid, bool &is_special) {
299  is_special = (rawid & HIGHMASK) != 0;
300  return rawid & CLEARMASK;
301  }
302  inline vid_t make_special(vid_t rawid) {
303  return rawid | HIGHMASK;
304  }
305  inline bool is_special(vid_t rawid) {
306  return (rawid & HIGHMASK) != 0;
307  }
308 
309 #ifdef SUPPORT_DELETIONS
310 
311  /*
312  * Hacky support for edge deletions.
313  * Edges are deleted by setting the value of the edge to a special
314  * value that denotes it was deleted.
315  * In the future, a better system could be designed.
316  */
317 
318  // This is hacky...
319  static inline bool VARIABLE_IS_NOT_USED is_deleted_edge_value(bool val) {
320  return val;
321  }
322 
323  static inline bool VARIABLE_IS_NOT_USED is_deleted_edge_value(int val) {
324  return 0xffffffff == (unsigned int)val;
325  }
326 
327  static inline bool VARIABLE_IS_NOT_USED is_deleted_edge_value(vid_t val) {
328  return 0xffffffffu == val;
329  }
330 
331 
332  static inline bool VARIABLE_IS_NOT_USED is_deleted_edge_value(float val) {
333  return !(val < 0 || val > 0);
334  }
335 
336  static void VARIABLE_IS_NOT_USED remove_edgev(graphchi_edge<bool> * e);
337  static void VARIABLE_IS_NOT_USED remove_edgev(graphchi_edge<bool> * e) {
338  e->set_data(true);
339  }
340 
341  static void VARIABLE_IS_NOT_USED remove_edgev(graphchi_edge<vid_t> * e);
342  static void VARIABLE_IS_NOT_USED remove_edgev(graphchi_edge<vid_t> * e) {
343  e->set_data(0xffffffff);
344  }
345 
346  static void VARIABLE_IS_NOT_USED remove_edgev(graphchi_edge<int> * e);
347  static void VARIABLE_IS_NOT_USED remove_edgev(graphchi_edge<int> * e) {
348  e->set_data(0xffffffff);
349  }
350 
351 #endif
352 
353 
354 } // Namespace
355 
356 #endif