SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
TempMotifCounter Class Reference

#include <temporalmotifs.h>

Collaboration diagram for TempMotifCounter:

Public Member Functions

 TempMotifCounter (const TStr &filename)
 
void Count3TEdge2Node (double delta, Counter2D &counts)
 
void Count3TEdge2Node (int u, int v, double delta, Counter3D &counts)
 
void Count3TEdge3NodeStars (double delta, Counter3D &pre_counts, Counter3D &pos_counts, Counter3D &mid_counts)
 
void Count3TEdge3NodeStarsNaive (double delta, Counter3D &pre_counts, Counter3D &pos_counts, Counter3D &mid_counts)
 
void Count3TEdgeTriads (double delta, Counter3D &counts)
 
void Count3TEdgeTriadsNaive (double delta, Counter3D &counts)
 
void Count3TEdge23Node (double delta, Counter2D &counts)
 

Private Member Functions

void GetAllStaticTriangles (TIntV &Us, TIntV &Vs, TIntV &Ws)
 
void GetAllNeighbors (int node, TIntV &nbrs)
 
void GetAllNodes (TIntV &nodes)
 
bool HasEdges (int u, int v)
 
void AddTriadEdgeData (TVec< TriadEdgeData > &events, TVec< TIntPair > &ts_indices, int &index, int u, int v, int nbr, int key1, int key2)
 
void AddStarEdgeData (TVec< TIntPair > &ts_indices, TVec< StarEdgeData > &events, int &index, int u, int v, int nbr, int key)
 
void AddStarEdges (TVec< TIntPair > &combined, int u, int v, int key)
 

Private Attributes

PNGraph static_graph_
 
TVec< THash< TInt, TIntV > > temporal_data_
 

Detailed Description

Definition at line 94 of file temporalmotifs.h.

Constructor & Destructor Documentation

TempMotifCounter::TempMotifCounter ( const TStr filename)

Definition at line 6 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), atInt, TNGraph::GetMxNId(), TTable::LoadSS(), static_graph_, and temporal_data_.

6  {
7  // First load the static graph
8  static_graph_ = TSnap::LoadEdgeList<PNGraph>(filename, 0, 1);
9  int max_nodes = static_graph_->GetMxNId();
11 
12  // Formulate input File Format:
13  // source_node destination_node timestamp
14  TTableContext context;
15  Schema temp_graph_schema;
16  temp_graph_schema.Add(TPair<TStr,TAttrType>("source", atInt));
17  temp_graph_schema.Add(TPair<TStr,TAttrType>("destination", atInt));
18  temp_graph_schema.Add(TPair<TStr,TAttrType>("time", atInt));
19 
20  // Load the temporal graph
21  PTable data_ptr = TTable::LoadSS(temp_graph_schema, filename, &context, ' ');
22  TInt src_idx = data_ptr->GetColIdx("source");
23  TInt dst_idx = data_ptr->GetColIdx("destination");
24  TInt tim_idx = data_ptr->GetColIdx("time");
25  for (TRowIterator RI = data_ptr->BegRI(); RI < data_ptr->EndRI(); RI++) {
26  TInt row_idx = RI.GetRowIdx();
27  int src = data_ptr->GetIntValAtRowIdx(src_idx, row_idx).Val;
28  int dst = data_ptr->GetIntValAtRowIdx(dst_idx, row_idx).Val;
29  int tim = data_ptr->GetIntValAtRowIdx(tim_idx, row_idx).Val;
30  temporal_data_[src](dst).Add(tim);
31  }
32 }
Execution context.
Definition: table.h:180
Definition: gbase.h:23
Iterator class for TTable rows.
Definition: table.h:330
Definition: dt.h:1134
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:552
static PTable LoadSS(const Schema &S, const TStr &InFNm, TTableContext *Context, const char &Separator= '\t', TBool HasTitleLine=false)
Loads table from spread sheet (TSV, CSV, etc). Note: HasTitleLine = true is not supported. Please comment title lines instead.
Definition: table.cpp:795
Definition: bd.h:196
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVec< THash< TInt, TIntV > > temporal_data_
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430

Here is the call graph for this function:

Member Function Documentation

void TempMotifCounter::AddStarEdgeData ( TVec< TIntPair > &  ts_indices,
TVec< StarEdgeData > &  events,
int &  index,
int  u,
int  v,
int  nbr,
int  key 
)
private

Definition at line 284 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::GetDat(), HasEdges(), TVec< TVal, TSizeTy >::Len(), and temporal_data_.

Referenced by Count3TEdge3NodeStars().

286  {
287  if (HasEdges(u, v)) {
288  const TIntV& ts_vec = temporal_data_[u].GetDat(v);
289  for (int j = 0; j < ts_vec.Len(); ++j) {
290  ts_indices.Add(TIntPair(ts_vec[j], index));
291  events.Add(StarEdgeData(nbr, key));
292  index++;
293  }
294  }
295 }
bool HasEdges(int u, int v)
TKeyDat< TInt, TInt > TIntPair
Definition: temporalmotifs.h:6
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVec< THash< TInt, TIntV > > temporal_data_

Here is the call graph for this function:

Here is the caller graph for this function:

void TempMotifCounter::AddStarEdges ( TVec< TIntPair > &  combined,
int  u,
int  v,
int  key 
)
private

Definition at line 219 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::GetDat(), HasEdges(), TVec< TVal, TSizeTy >::Len(), and temporal_data_.

Referenced by Count3TEdge2Node(), Count3TEdge3NodeStarsNaive(), and Count3TEdgeTriadsNaive().

220  {
221  if (HasEdges(u, v)) {
222  const TIntV& timestamps = temporal_data_[u].GetDat(v);
223  for (int i = 0; i < timestamps.Len(); i++) {
224  combined.Add(TIntPair(timestamps[i], key));
225  }
226  }
227 }
bool HasEdges(int u, int v)
TKeyDat< TInt, TInt > TIntPair
Definition: temporalmotifs.h:6
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVec< THash< TInt, TIntV > > temporal_data_

Here is the call graph for this function:

Here is the caller graph for this function:

void TempMotifCounter::AddTriadEdgeData ( TVec< TriadEdgeData > &  events,
TVec< TIntPair > &  ts_indices,
int &  index,
int  u,
int  v,
int  nbr,
int  key1,
int  key2 
)
private

Definition at line 431 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::GetDat(), HasEdges(), TVec< TVal, TSizeTy >::Len(), and temporal_data_.

Referenced by Count3TEdgeTriads().

434  {
435  if (HasEdges(u, v)) {
436  const TIntV& timestamps = temporal_data_[u].GetDat(v);
437  for (int i = 0; i < timestamps.Len(); i++) {
438  ts_indices.Add(TIntPair(timestamps[i], index));
439  events.Add(TriadEdgeData(nbr, key1, key2));
440  ++index;
441  }
442  }
443 }
bool HasEdges(int u, int v)
TKeyDat< TInt, TInt > TIntPair
Definition: temporalmotifs.h:6
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVec< THash< TInt, TIntV > > temporal_data_

Here is the call graph for this function:

Here is the caller graph for this function:

void TempMotifCounter::Count3TEdge23Node ( double  delta,
Counter2D counts 
)

Definition at line 116 of file temporalmotifs.cpp.

References Count3TEdge2Node(), Count3TEdge3NodeStars(), and Count3TEdgeTriads().

116  {
117  // This is imply a wrapper function around the counting methods to produce
118  // counts in the same way that they were represented in the paper. This makes
119  // it easy to reproduce results and allow SNAP users to make the same
120  // measurements on their temporal network data.
121  counts = Counter2D(6, 6);
122 
123  Counter2D edge_counts;
124  Count3TEdge2Node(delta, edge_counts);
125  counts(4, 0) = edge_counts(0, 0);
126  counts(4, 1) = edge_counts(0, 1);
127  counts(5, 0) = edge_counts(1, 0);
128  counts(5, 1) = edge_counts(1, 1);
129 
130  Counter3D pre_counts, pos_counts, mid_counts;
131  Count3TEdge3NodeStars(delta, pre_counts, pos_counts, mid_counts);
132  counts(0, 0) = mid_counts(1, 1, 1);
133  counts(0, 1) = mid_counts(1, 1, 0);
134  counts(0, 4) = pos_counts(1, 1, 0);
135  counts(0, 5) = pos_counts(1, 1, 1);
136  counts(1, 0) = mid_counts(1, 0, 1);
137  counts(1, 1) = mid_counts(1, 0, 0);
138  counts(1, 4) = pos_counts(1, 0, 0);
139  counts(1, 5) = pos_counts(1, 0, 1);
140  counts(2, 0) = mid_counts(0, 0, 1);
141  counts(2, 1) = mid_counts(0, 1, 1);
142  counts(2, 2) = pos_counts(0, 1, 0);
143  counts(2, 3) = pos_counts(0, 1, 1);
144  counts(3, 0) = mid_counts(0, 0, 0);
145  counts(3, 1) = mid_counts(0, 0, 1);
146  counts(3, 2) = pos_counts(0, 0, 0);
147  counts(3, 3) = pos_counts(0, 0, 1);
148  counts(4, 2) = pre_counts(0, 1, 0);
149  counts(4, 3) = pre_counts(0, 1, 1);
150  counts(4, 4) = pre_counts(1, 0, 0);
151  counts(4, 5) = pre_counts(1, 0, 1);
152  counts(5, 2) = pre_counts(0, 0, 0);
153  counts(5, 3) = pre_counts(0, 0, 1);
154  counts(5, 4) = pre_counts(1, 1, 0);
155  counts(5, 5) = pre_counts(1, 1, 1);
156 
157  Counter3D triad_counts;
158  Count3TEdgeTriads(delta, triad_counts);
159  counts(0, 2) = triad_counts(0, 0, 0);
160  counts(0, 3) = triad_counts(0, 0, 1);
161  counts(1, 2) = triad_counts(0, 1, 0);
162  counts(1, 3) = triad_counts(0, 1, 1);
163  counts(2, 4) = triad_counts(1, 0, 0);
164  counts(2, 5) = triad_counts(1, 0, 1);
165  counts(3, 4) = triad_counts(1, 1, 0);
166  counts(3, 5) = triad_counts(1, 1, 1);
167 }
void Count3TEdge3NodeStars(double delta, Counter3D &pre_counts, Counter3D &pos_counts, Counter3D &mid_counts)
void Count3TEdge2Node(double delta, Counter2D &counts)
void Count3TEdgeTriads(double delta, Counter3D &counts)

Here is the call graph for this function:

void TempMotifCounter::Count3TEdge2Node ( double  delta,
Counter2D counts 
)

Definition at line 171 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegEI(), TKeyDat< TKey, TDat >::Dat, edge, TNGraph::EndEI(), TKeyDat< TKey, TDat >::Key, TVec< TVal, TSizeTy >::Len(), and static_graph_.

Referenced by Count3TEdge23Node(), and Count3TEdge3NodeStars().

171  {
172  // Get a vector of undirected edges (so we can use openmp parallel for over it)
173  TVec<TIntPair> undir_edges;
174  for (TNGraph::TEdgeI it = static_graph_->BegEI(); it < static_graph_->EndEI(); it++) {
175  int src = it.GetSrcNId();
176  int dst = it.GetDstNId();
177  // Only consider undirected edges
178  if (src < dst || (dst < src && !static_graph_->IsEdge(dst, src))) {
179  undir_edges.Add(TIntPair(src, dst));
180  }
181  }
182  counts = Counter2D(2, 2);
183  #pragma omp parallel for schedule(dynamic)
184  for (int i = 0; i < undir_edges.Len(); i++) {
185  TIntPair edge = undir_edges[i];
186  Counter3D local;
187  Count3TEdge2Node(edge.Key, edge.Dat, delta, local);
188  #pragma omp critical
189  {
190  counts(0, 0) += local(0, 1, 0) + local(1, 0, 1); // M_{5,1}
191  counts(0, 1) += local(1, 0, 0) + local(0, 1, 1); // M_{5,2}
192  counts(1, 0) += local(0, 0, 0) + local(1, 1, 1); // M_{6,1}
193  counts(1, 1) += local(0, 0, 1) + local(1, 1, 0); // M_{6,2}
194  }
195  }
196 }
Definition: ds.h:346
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:588
TKeyDat< TInt, TInt > TIntPair
Definition: temporalmotifs.h:6
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:586
TDat Dat
Definition: ds.h:349
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:426
TKey Key
Definition: ds.h:348
void Count3TEdge2Node(double delta, Counter2D &counts)
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430

Here is the call graph for this function:

Here is the caller graph for this function:

void TempMotifCounter::Count3TEdge2Node ( int  u,
int  v,
double  delta,
Counter3D counts 
)

Definition at line 198 of file temporalmotifs.cpp.

References AddStarEdges(), ThreeTEdgeMotifCounter::Count(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Sort().

199  {
200  // Sort event list by time
201  TVec<TIntPair> combined;
202  AddStarEdges(combined, u, v, 0);
203  AddStarEdges(combined, v, u, 1);
204  combined.Sort();
205 
206  // Get the counts
207  ThreeTEdgeMotifCounter counter(2);
208  TIntV in_out(combined.Len());
209  TIntV timestamps(combined.Len());
210  for (int k = 0; k < combined.Len(); k++) {
211  in_out[k] = combined[k].Dat;
212  timestamps[k] = combined[k].Key;
213  }
214  counter.Count(in_out, timestamps, delta, counts);
215 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TSizeTy Count(const TVal &Val) const
Counts the number of occurrences of Val in the vector.
Definition: ds.h:1511
void AddStarEdges(TVec< TIntPair > &combined, int u, int v, int key)
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430

Here is the call graph for this function:

void TempMotifCounter::Count3TEdge3NodeStars ( double  delta,
Counter3D pre_counts,
Counter3D pos_counts,
Counter3D mid_counts 
)

Definition at line 297 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), AddStarEdgeData(), StarTriad3TEdgeCounter< EdgeData >::Count(), Count3TEdge2Node(), GetAllNeighbors(), GetAllNodes(), TNGraph::GetNI(), TVec< TVal, TSizeTy >::Len(), ThreeTEdgeStarCounter::MidCount(), ThreeTEdgeStarCounter::PosCount(), ThreeTEdgeStarCounter::PreCount(), TVec< TVal, TSizeTy >::Sort(), and static_graph_.

Referenced by Count3TEdge23Node().

299  {
300  TIntV centers;
301  GetAllNodes(centers);
302  pre_counts = Counter3D(2, 2, 2);
303  pos_counts = Counter3D(2, 2, 2);
304  mid_counts = Counter3D(2, 2, 2);
305  // Get counts for each node as the center
306  #pragma omp parallel for schedule(dynamic)
307  for (int c = 0; c < centers.Len(); c++) {
308  // Gather all adjacent events
309  int center = centers[c];
310  TVec<TIntPair> ts_indices;
311  TVec<StarEdgeData> events;
312  TNGraph::TNodeI NI = static_graph_->GetNI(center);
313  int index = 0;
314  TIntV nbrs;
315  GetAllNeighbors(center, nbrs);
316  int nbr_index = 0;
317  for (int i = 0; i < nbrs.Len(); i++) {
318  int nbr = nbrs[i];
319  AddStarEdgeData(ts_indices, events, index, center, nbr, nbr_index, 0);
320  AddStarEdgeData(ts_indices, events, index, nbr, center, nbr_index, 1);
321  nbr_index++;
322  }
323  ts_indices.Sort();
324  TIntV timestamps;
325  TVec<StarEdgeData> ordered_events;
326  for (int j = 0; j < ts_indices.Len(); j++) {
327  timestamps.Add(ts_indices[j].Key);
328  ordered_events.Add(events[ts_indices[j].Dat]);
329  }
330 
331  ThreeTEdgeStarCounter tesc(nbr_index);
332  // dirs: outgoing --> 0, incoming --> 1
333  tesc.Count(ordered_events, timestamps, delta);
334  #pragma omp critical
335  { // Update counts
336  for (int dir1 = 0; dir1 < 2; ++dir1) {
337  for (int dir2 = 0; dir2 < 2; ++dir2) {
338  for (int dir3 = 0; dir3 < 2; ++dir3) {
339  pre_counts(dir1, dir2, dir3) += tesc.PreCount(dir1, dir2, dir3);
340  pos_counts(dir1, dir2, dir3) += tesc.PosCount(dir1, dir2, dir3);
341  mid_counts(dir1, dir2, dir3) += tesc.MidCount(dir1, dir2, dir3);
342  }
343  }
344  }
345  }
346 
347  // Subtract off edge-wise counts
348  for (int nbr_id = 0; nbr_id < nbrs.Len(); nbr_id++) {
349  int nbr = nbrs[nbr_id];
350  Counter3D edge_counts;
351  Count3TEdge2Node(center, nbr, delta, edge_counts);
352  #pragma omp critical
353  {
354  for (int dir1 = 0; dir1 < 2; ++dir1) {
355  for (int dir2 = 0; dir2 < 2; ++dir2) {
356  for (int dir3 = 0; dir3 < 2; ++dir3) {
357  pre_counts(dir1, dir2, dir3) -= edge_counts(dir1, dir2, dir3);
358  pos_counts(dir1, dir2, dir3) -= edge_counts(dir1, dir2, dir3);
359  mid_counts(dir1, dir2, dir3) -= edge_counts(dir1, dir2, dir3);
360  }
361  }
362  }
363  }
364  }
365  }
366 }
void GetAllNodes(TIntV &nodes)
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void AddStarEdgeData(TVec< TIntPair > &ts_indices, TVec< StarEdgeData > &events, int &index, int u, int v, int nbr, int key)
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void GetAllNeighbors(int node, TIntV &nbrs)
void Count3TEdge2Node(double delta, Counter2D &counts)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

void TempMotifCounter::Count3TEdge3NodeStarsNaive ( double  delta,
Counter3D pre_counts,
Counter3D pos_counts,
Counter3D mid_counts 
)

Definition at line 229 of file temporalmotifs.cpp.

References AddStarEdges(), ThreeTEdgeMotifCounter::Count(), GetAllNeighbors(), GetAllNodes(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Sort().

231  {
232  TIntV centers;
233  GetAllNodes(centers);
234  pre_counts = Counter3D(2, 2, 2);
235  pos_counts = Counter3D(2, 2, 2);
236  mid_counts = Counter3D(2, 2, 2);
237  // Get counts for each node as the center
238  #pragma omp parallel for schedule(dynamic)
239  for (int c = 0; c < centers.Len(); c++) {
240  // Gather all adjacent events
241  int center = centers[c];
242  TIntV nbrs;
243  GetAllNeighbors(center, nbrs);
244  for (int i = 0; i < nbrs.Len(); i++) {
245  for (int j = i + 1; j < nbrs.Len(); j++) {
246  int nbr1 = nbrs[i];
247  int nbr2 = nbrs[j];
248  TVec<TIntPair> combined;
249  AddStarEdges(combined, center, nbr1, 0);
250  AddStarEdges(combined, nbr1, center, 1);
251  AddStarEdges(combined, center, nbr2, 2);
252  AddStarEdges(combined, nbr2, center, 3);
253  combined.Sort();
254  ThreeTEdgeMotifCounter counter(4);
255  TIntV edge_id(combined.Len());
256  TIntV timestamps(combined.Len());
257  for (int k = 0; k < combined.Len(); k++) {
258  edge_id[k] = combined[k].Dat;
259  timestamps[k] = combined[k].Key;
260  }
261  Counter3D local;
262  counter.Count(edge_id, timestamps, delta, local);
263 
264  #pragma omp critical
265  { // Update with local counts
266  for (int dir1 = 0; dir1 < 2; ++dir1) {
267  for (int dir2 = 0; dir2 < 2; ++dir2) {
268  for (int dir3 = 0; dir3 < 2; ++dir3) {
269  pre_counts(dir1, dir2, dir3) +=
270  local(dir1, dir2, dir3 + 2) + local(dir1 + 2, dir2 + 2, dir3);
271  pos_counts(dir1, dir2, dir3) +=
272  local(dir1, dir2 + 2, dir3 + 2) + local(dir1 + 2, dir2, dir3);
273  mid_counts(dir1, dir2, dir3) +=
274  local(dir1, dir2 + 2, dir3) + local(dir1 + 2, dir2, dir3 + 2);
275  }
276  }
277  }
278  }
279  }
280  }
281  }
282 }
void GetAllNodes(TIntV &nodes)
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void GetAllNeighbors(int node, TIntV &nbrs)
void AddStarEdges(TVec< TIntPair > &combined, int u, int v, int key)

Here is the call graph for this function:

void TempMotifCounter::Count3TEdgeTriads ( double  delta,
Counter3D counts 
)

Definition at line 445 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), AddTriadEdgeData(), TNGraph::BegEI(), StarTriad3TEdgeCounter< EdgeData >::Count(), ThreeTEdgeTriadCounter::Counts(), TKeyDat< TKey, TDat >::Dat, edge, TNGraph::EndEI(), GetAllNeighbors(), GetAllNodes(), GetAllStaticTriangles(), TVec< TVal, TSizeTy >::GetDat(), TNGraph::GetMxNId(), TKeyDat< TKey, TDat >::Key, TVec< TVal, TSizeTy >::Len(), MAX, MIN, TVec< TVal, TSizeTy >::Sort(), static_graph_, and temporal_data_.

Referenced by Count3TEdge23Node().

445  {
446  counts = Counter3D(2, 2, 2);
447 
448  // Get the counts on each undirected edge
451  for (TNGraph::TEdgeI it = static_graph_->BegEI();
452  it < static_graph_->EndEI(); it++) {
453  int src = it.GetSrcNId();
454  int dst = it.GetDstNId();
455  int min_node = MIN(src, dst);
456  int max_node = MAX(src, dst);
457  edge_counts[min_node](max_node) += temporal_data_[src](dst).Len();
458  assignments[min_node](max_node) = TIntV();
459  }
460 
461  // Assign triangles to the edge with the most events
462  TIntV Us, Vs, Ws;
463  GetAllStaticTriangles(Us, Vs, Ws);
464  #pragma omp parallel for schedule(dynamic)
465  for (int i = 0; i < Us.Len(); i++) {
466  int u = Us[i];
467  int v = Vs[i];
468  int w = Ws[i];
469  int counts_uv = edge_counts[MIN(u, v)].GetDat(MAX(u, v));
470  int counts_uw = edge_counts[MIN(u, w)].GetDat(MAX(u, w));
471  int counts_vw = edge_counts[MIN(v, w)].GetDat(MAX(v, w));
472  if (counts_uv >= MAX(counts_uw, counts_vw)) {
473  #pragma omp critical
474  {
475  TIntV& assignment = assignments[MIN(u, v)].GetDat(MAX(u, v));
476  assignment.Add(w);
477  }
478  } else if (counts_uw >= MAX(counts_uv, counts_vw)) {
479  #pragma omp critical
480  {
481  TIntV& assignment = assignments[MIN(u, w)].GetDat(MAX(u, w));
482  assignment.Add(v);
483  }
484  } else if (counts_vw >= MAX(counts_uv, counts_uw)) {
485  #pragma omp critical
486  {
487  TIntV& assignment = assignments[MIN(v, w)].GetDat(MAX(v, w));
488  assignment.Add(u);
489  }
490  }
491  }
492 
493  TVec<TIntPair> all_edges;
494  TIntV all_nodes;
495  GetAllNodes(all_nodes);
496  for (int node_id = 0; node_id < all_nodes.Len(); node_id++) {
497  int u = all_nodes[node_id];
498  TIntV nbrs;
499  GetAllNeighbors(u, nbrs);
500  for (int nbr_id = 0; nbr_id < nbrs.Len(); nbr_id++) {
501  int v = nbrs[nbr_id];
502  if (assignments[u].IsKey(v) && assignments[u].GetDat(v).Len() > 0) {
503  all_edges.Add(TIntPair(u, v));
504  }
505  }
506  }
507 
508  // Count triangles on edges with the assigned neighbors
509  #pragma omp parallel for schedule(dynamic)
510  for (int edge_id = 0; edge_id < all_edges.Len(); edge_id++) {
511  TIntPair edge = all_edges[edge_id];
512  int u = edge.Key;
513  int v = edge.Dat;
514  // Continue if no assignment
515  if (!assignments[u].IsKey(v)) { continue; }
516  TIntV& uv_assignment = assignments[u].GetDat(v);
517  // Continue if no data
518  if (uv_assignment.Len() == 0) { continue; }
519  // Get all events on (u, v)
520  TVec<TriadEdgeData> events;
521  TVec<TIntPair> ts_indices;
522  int index = 0;
523  int nbr_index = 0;
524  // Assign indices from 0, 1, ..., num_nbrs + 2
525  AddTriadEdgeData(events, ts_indices, index, u, v, nbr_index, 0, 1);
526  nbr_index++;
527  AddTriadEdgeData(events, ts_indices, index, v, u, nbr_index, 0, 0);
528  nbr_index++;
529  // Get all events on triangles assigned to (u, v)
530  for (int w_id = 0; w_id < uv_assignment.Len(); w_id++) {
531  int w = uv_assignment[w_id];
532  AddTriadEdgeData(events, ts_indices, index, w, u, nbr_index, 0, 0);
533  AddTriadEdgeData(events, ts_indices, index, w, v, nbr_index, 0, 1);
534  AddTriadEdgeData(events, ts_indices, index, u, w, nbr_index, 1, 0);
535  AddTriadEdgeData(events, ts_indices, index, v, w, nbr_index, 1, 1);
536  nbr_index++;
537  }
538  // Put events in sorted order
539  ts_indices.Sort();
540  TIntV timestamps(ts_indices.Len());
541  TVec<TriadEdgeData> sorted_events(ts_indices.Len());
542  for (int i = 0; i < ts_indices.Len(); i++) {
543  timestamps[i] = ts_indices[i].Key;
544  sorted_events[i] = events[ts_indices[i].Dat];
545  }
546 
547  // Get the counts and update the counter
548  ThreeTEdgeTriadCounter tetc(nbr_index, 0, 1);
549  tetc.Count(sorted_events, timestamps, delta);
550  #pragma omp critical
551  {
552  for (int dir1 = 0; dir1 < 2; dir1++) {
553  for (int dir2 = 0; dir2 < 2; dir2++) {
554  for (int dir3 = 0; dir3 < 2; dir3++) {
555  counts(dir1, dir2, dir3) += tetc.Counts(dir1, dir2, dir3);
556  }
557  }
558  }
559  }
560  }
561 }
Definition: ds.h:346
void GetAllNodes(TIntV &nodes)
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:588
TKeyDat< TInt, TInt > TIntPair
Definition: temporalmotifs.h:6
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:586
TDat Dat
Definition: ds.h:349
void GetAllStaticTriangles(TIntV &Us, TIntV &Vs, TIntV &Ws)
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:426
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
#define MIN(a, b)
Definition: bd.h:346
void GetAllNeighbors(int node, TIntV &nbrs)
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:552
void AddTriadEdgeData(TVec< TriadEdgeData > &events, TVec< TIntPair > &ts_indices, int &index, int u, int v, int nbr, int key1, int key2)
TKey Key
Definition: ds.h:348
TVec< TInt > TIntV
Definition: ds.h:1594
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
#define MAX(a, b)
Definition: bd.h:350
TVec< THash< TInt, TIntV > > temporal_data_
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430

Here is the call graph for this function:

Here is the caller graph for this function:

void TempMotifCounter::Count3TEdgeTriadsNaive ( double  delta,
Counter3D counts 
)

Definition at line 370 of file temporalmotifs.cpp.

References AddStarEdges(), ThreeTEdgeMotifCounter::Count(), GetAllStaticTriangles(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Sort().

370  {
371  TIntV Us, Vs, Ws;
372  GetAllStaticTriangles(Us, Vs, Ws);
373  counts = Counter3D(2, 2, 2);
374  #pragma omp parallel for schedule(dynamic)
375  for (int i = 0; i < Us.Len(); i++) {
376  int u = Us[i];
377  int v = Vs[i];
378  int w = Ws[i];
379  // Gather all edges in triangle (u, v, w)
380  int uv = 0, vu = 1, uw = 2, wu = 3, vw = 4, wv = 5;
381  TVec<TIntPair> combined;
382  AddStarEdges(combined, u, v, uv);
383  AddStarEdges(combined, v, u, vu);
384  AddStarEdges(combined, u, w, uw);
385  AddStarEdges(combined, w, u, wu);
386  AddStarEdges(combined, v, w, vw);
387  AddStarEdges(combined, w, v, wv);
388  // Get the counts for this triangle
389  combined.Sort();
390  ThreeTEdgeMotifCounter counter(6);
391  TIntV edge_id(combined.Len());
392  TIntV timestamps(combined.Len());
393  for (int k = 0; k < combined.Len(); k++) {
394  edge_id[k] = combined[k].Dat;
395  timestamps[k] = combined[k].Key;
396  }
397  Counter3D local;
398  counter.Count(edge_id, timestamps, delta, local);
399 
400  // Update the global counter with the various symmetries
401  #pragma omp critical
402  {
403  // i --> j, k --> j, i --> k
404  counts(0, 0, 0) += local(uv, wv, uw) + local(vu, wu, vw) + local(uw, vw, uv)
405  + local(wu, vu, wv) + local(vw, uw, vu) + local(wv, uv, wu);
406  // i --> j, k --> j, k --> i
407  counts(0, 0, 1) += local(uv, wv, wu) + local(vu, wu, wv) + local(uw, vw, vu)
408  + local(wu, vu, vw) + local(vw, uw, uv) + local(wv, uv, uw);
409  // i --> j, j --> k, i --> k
410  counts(0, 1, 0) += local(uv, vw, uw) + local(vu, uw, vw) + local(uw, wv, uv)
411  + local(wu, uv, wv) + local(vw, wu, vu) + local(wv, vu, wu);
412  // i --> j, j --> k, k --> i
413  counts(0, 1, 1) += local(uv, vw, wu) + local(vu, uw, wv) + local(uw, wv, vu)
414  + local(wu, uv, vw) + local(vw, wu, uv) + local(wv, vu, uw);
415  // i --> j, k --> i, j --> k
416  counts(1, 0, 0) += local(uv, wu, vw) + local(vu, wv, uw) + local(uw, vu, wv)
417  + local(wu, vw, uv) + local(vw, uv, wu) + local(wv, uw, vu);
418  // i --> j, k --> i, k --> j
419  counts(1, 0, 1) += local(uv, wu, wv) + local(vu, wv, wu) + local(uw, vu, vw)
420  + local(wu, vw, vu) + local(vw, uv, uw) + local(wv, uw, uv);
421  // i --> j, i --> k, j --> k
422  counts(1, 1, 0) += local(uv, uw, vw) + local(vu, vw, uw) + local(uw, uv, wv)
423  + local(wu, wv, uv) + local(vw, vu, wu) + local(wv, wu, vu);
424  // i --> j, i --> k, k --> j
425  counts(1, 1, 1) += local(uv, uw, wv) + local(vu, vw, wu) + local(uw, uv, vw)
426  + local(wu, wv, vu) + local(vw, vu, uw) + local(wv, wu, uv);
427  }
428  }
429 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void GetAllStaticTriangles(TIntV &Us, TIntV &Vs, TIntV &Ws)
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void AddStarEdges(TVec< TIntPair > &combined, int u, int v, int key)

Here is the call graph for this function:

void TempMotifCounter::GetAllNeighbors ( int  node,
TIntV nbrs 
)
private

Definition at line 46 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TNGraph::TNodeI::IsOutNId(), and static_graph_.

Referenced by Count3TEdge3NodeStars(), Count3TEdge3NodeStarsNaive(), Count3TEdgeTriads(), and GetAllStaticTriangles().

46  {
47  nbrs = TIntV();
49  for (int i = 0; i < NI.GetOutDeg(); i++) { nbrs.Add(NI.GetOutNId(i)); }
50  for (int i = 0; i < NI.GetInDeg(); i++) {
51  int nbr = NI.GetInNId(i);
52  if (!NI.IsOutNId(nbr)) { nbrs.Add(nbr); }
53  }
54 }
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.h:420
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TVec< TInt > TIntV
Definition: ds.h:1594
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:400
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:408
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412

Here is the call graph for this function:

Here is the caller graph for this function:

void TempMotifCounter::GetAllNodes ( TIntV nodes)
private

Definition at line 34 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegNI(), TNGraph::EndNI(), and static_graph_.

Referenced by Count3TEdge3NodeStars(), Count3TEdge3NodeStarsNaive(), Count3TEdgeTriads(), and GetAllStaticTriangles().

34  {
35  nodes = TIntV();
36  for (TNGraph::TNodeI it = static_graph_->BegNI();
37  it < static_graph_->EndNI(); it++) {
38  nodes.Add(it.GetId());
39  }
40 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TVec< TInt > TIntV
Definition: ds.h:1594
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

void TempMotifCounter::GetAllStaticTriangles ( TIntV Us,
TIntV Vs,
TIntV Ws 
)
private

Definition at line 56 of file temporalmotifs.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), GetAllNeighbors(), GetAllNodes(), TNGraph::GetMxNId(), TNGraph::IsEdge(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::PutAll(), TVec< TVal, TSizeTy >::Sort(), and static_graph_.

Referenced by Count3TEdgeTriads(), and Count3TEdgeTriadsNaive().

56  {
57  Us.Clr();
58  Vs.Clr();
59  Ws.Clr();
60  // Get degree ordering of the graph
61  int max_nodes = static_graph_->GetMxNId();
62  TVec<TIntPair> degrees(max_nodes);
63  degrees.PutAll(TIntPair(0, 0));
64  // Set the degree of a node to be the number of nodes adjacent to the node in
65  // the undirected graph.
66  TIntV nodes;
67  GetAllNodes(nodes);
68  #pragma omp parallel for schedule(dynamic)
69  for (int node_id = 0; node_id < nodes.Len(); node_id++) {
70  int src = nodes[node_id];
71  TIntV nbrs;
72  GetAllNeighbors(src, nbrs);
73  degrees[src] = TIntPair(nbrs.Len(), src);
74  }
75  degrees.Sort();
76  TIntV order = TIntV(max_nodes);
77  #pragma omp parallel for schedule(dynamic)
78  for (int i = 0; i < order.Len(); i++) {
79  order[degrees[i].Dat] = i;
80  }
81 
82  // Get triangles centered at a given node where that node is the smallest in
83  // the degree ordering.
84  #pragma omp parallel for schedule(dynamic)
85  for (int node_id = 0; node_id < nodes.Len(); node_id++) {
86  int src = nodes[node_id];
87  int src_pos = order[src];
88 
89  // Get all neighbors who come later in the ordering
90  TIntV nbrs;
91  GetAllNeighbors(src, nbrs);
92  TIntV neighbors_higher;
93  for (int i = 0; i < nbrs.Len(); i++) {
94  int nbr = nbrs[i];
95  if (order[nbr] > src_pos) { neighbors_higher.Add(nbr); }
96  }
97 
98  for (int ind1 = 0; ind1 < neighbors_higher.Len(); ind1++) {
99  for (int ind2 = ind1 + 1; ind2 < neighbors_higher.Len(); ind2++) {
100  int dst1 = neighbors_higher[ind1];
101  int dst2 = neighbors_higher[ind2];
102  // Check for triangle formation
103  if (static_graph_->IsEdge(dst1, dst2) || static_graph_->IsEdge(dst2, dst1)) {
104  #pragma omp critical
105  {
106  Us.Add(src);
107  Vs.Add(dst1);
108  Ws.Add(dst2);
109  }
110  }
111  }
112  }
113  }
114 }
void GetAllNodes(TIntV &nodes)
TKeyDat< TInt, TInt > TIntPair
Definition: temporalmotifs.h:6
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
void GetAllNeighbors(int node, TIntV &nbrs)
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:552
TVec< TInt > TIntV
Definition: ds.h:1594
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430

Here is the call graph for this function:

Here is the caller graph for this function:

bool TempMotifCounter::HasEdges ( int  u,
int  v 
)
private

Definition at line 42 of file temporalmotifs.cpp.

References temporal_data_.

Referenced by AddStarEdgeData(), AddStarEdges(), and AddTriadEdgeData().

42  {
43  return temporal_data_[u].IsKey(v);
44 }
TVec< THash< TInt, TIntV > > temporal_data_

Here is the caller graph for this function:

Member Data Documentation

TVec< THash<TInt, TIntV> > TempMotifCounter::temporal_data_
private

The documentation for this class was generated from the following files: