GraphChi 0.1

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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>
90 class internal_graphchi_vertex {
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
126 internal_graphchi_vertex(vid_t _id, graphchi_edge<EdgeDataType> * iptr,
127 graphchi_edge<EdgeDataType> * optr,
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
197 graphchi_vertex() : internal_graphchi_vertex<VertexDataType, EdgeDataType>() { }
198
199 graphchi_vertex(vid_t _id,
200 graphchi_edge<EdgeDataType> * iptr,
201 graphchi_edge<EdgeDataType> * optr,
202 int indeg,
203 int outdeg) :
204 internal_graphchi_vertex<VertexDataType, EdgeDataType>(_id, iptr, optr, indeg, outdeg) {}
205
206 virtual ~graphchi_vertex() {}
207
212 graphchi_edge<EdgeDataType> * edge(int i) {
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
233 VertexDataType get_data() {
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
260 void VARIABLE_IS_NOT_USED sort_edges_indirect() {
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