FlashGraph-ng
A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
triangle_shared.h
1 /*
2  * Copyright 2014 Open Connectome Project (http://openconnecto.me)
3  * Written by Da Zheng (zhengda1936@gmail.com)
4  *
5  * This file is part of FlashGraph.
6  *
7  * Licensed under the Apache License, Version 2.0 (the "License");
8  * you may not use this file except in compliance with the License.
9  * You may obtain a copy of the License at
10  *
11  * http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing, software
14  * distributed under the License is distributed on an "AS IS" BASIS,
15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16  * See the License for the specific language governing permissions and
17  * limitations under the License.
18  */
19 
20 #include "thread.h"
21 
22 #include "graph_engine.h"
23 #include "graph_config.h"
24 #include "graphlab/cuckoo_set_pow2.hpp"
25 #include "FG_vector.h"
26 #include "FGlib.h"
27 
28 /*
29  * This contains the data structures shared directed triangle counting
30  * and undirected triangle counting.
31  */
32 
33 const double BIN_SEARCH_RATIO = 100;
34 const int HASH_SEARCH_RATIO = 16;
35 const int hash_threshold = 1000;
36 
37 static atomic_number<long> num_working_vertices;
38 static atomic_number<long> num_completed_vertices;
39 
40 class count_msg: public fg::vertex_message
41 {
42  int num;
43 public:
44  count_msg(int num): fg::vertex_message(sizeof(count_msg), false) {
45  this->num = num;
46  }
47 
48  int get_num() const {
49  return num;
50  }
51 };
52 
53 struct runtime_data_t
54 {
55  class index_entry
56  {
57  fg::vertex_id_t id;
58  uint32_t idx;
59  public:
60  index_entry() {
61  id = -1;
62  idx = -1;
63  }
64 
65  index_entry(fg::vertex_id_t id) {
66  this->id = id;
67  this->idx = -1;
68  }
69 
70  index_entry(fg::vertex_id_t id, uint32_t idx) {
71  this->id = id;
72  this->idx = idx;
73  }
74 
75  fg::vertex_id_t get_id() const {
76  return id;
77  }
78 
79  uint32_t get_idx() const {
80  return idx;
81  }
82 
83  bool operator==(const index_entry &e) const {
84  return id == e.get_id();
85  }
86  };
87 
88  class index_hash
89  {
90  boost::hash<fg::vertex_id_t> id_hash;
91  public:
92  size_t operator()(const index_entry &e) const {
93  return id_hash(e.get_id());
94  }
95  };
96  typedef graphlab::cuckoo_set_pow2<index_entry, 3, size_t,
97  index_hash> edge_set_t;
98  // It contains part of the edge list.
99  // We only use the neighbors whose ID is smaller than this vertex.
100  std::vector<fg::vertex_id_t> edges;
101  // The vector contains the number of the neighbors' triangles shared
102  // with this vertex. It only keeps the triangles of neighbors in the
103  // in-edges.
104  std::vector<int> triangles;
105  // The number of vertices that have joined with the vertex.
106  size_t num_joined;
107  size_t num_required;
108  size_t num_triangles;
109 
110  edge_set_t edge_set;
111 public:
112  runtime_data_t(size_t num_edges, size_t num_triangles): edge_set(
113  index_entry(), 0, 2 * num_edges) {
114  num_joined = 0;
115  this->num_required = 0;
116  this->num_triangles = num_triangles;
117  }
118 
119  void finalize_init() {
120  // We only build a hash table on large vertices
121  if (edges.size() > (size_t) hash_threshold)
122  for (size_t i = 0; i < edges.size(); i++)
123  edge_set.insert(index_entry(edges[i], i));
124  triangles.resize(edges.size());
125  }
126 };
127 
128 enum multi_func_flags
129 {
130  NUM_TRIANGLES,
131  POINTER,
132  NUM_FLAGS,
133 };
134 
135 class triangle_multi_func_value
136 {
137  static const int VALUE_BITS = sizeof(size_t) * 8 - NUM_FLAGS;
138  static const size_t FLAGS_MASK = ((1UL << VALUE_BITS) - 1);
139  size_t value;
140 
141  void set_flag(int flag) {
142  value |= 1UL << (VALUE_BITS + flag);
143  }
144 
145  bool has_flag(int flag) const {
146  return value & (1UL << (VALUE_BITS + flag));
147  }
148 public:
149  triangle_multi_func_value() {
150  value = 0;
151  // By default, it stores the number of triangles.
152  set_flag(NUM_TRIANGLES);
153  }
154 
155  void set_num_triangles(size_t num) {
156  value = num;
157  set_flag(NUM_TRIANGLES);
158  }
159 
160  bool has_num_triangles() const {
161  return has_flag(NUM_TRIANGLES);
162  }
163 
164  size_t get_num_triangles() const {
165  assert(has_flag(NUM_TRIANGLES));
166  return value & FLAGS_MASK;
167  }
168 
169  void inc_num_triangles(size_t num) {
170  assert(has_flag(NUM_TRIANGLES));
171  value += num;
172  }
173 
174  /*
175  * Pointer to the runtime data.
176  */
177 
178  void set_runtime_data(runtime_data_t *data) {
179  value = (size_t) data;
180  set_flag(POINTER);
181  }
182 
183  bool has_runtime_data() const {
184  return has_flag(POINTER);
185  }
186 
187  runtime_data_t *get_runtime_data() const {
188  assert(has_flag(POINTER));
189  return (runtime_data_t *) (value & FLAGS_MASK);
190  }
191 };
Definition: messaging.h:292