SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
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
triad.h
Go to the documentation of this file.
1 #ifndef TRIAD_H
2 #define TRIAD_H
3 
4 namespace TSnap {
5 
7 // Triads and clustering coefficient
8 
10 
12 template <class PGraph> double GetClustCf(const PGraph& Graph, int SampleNodes=-1);
14 
18 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int SampleNodes=-1);
20 
26 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriads, int64& OpenTriads, int SampleNodes=-1);
28 
35 template <class PGraph> double GetClustCfAll(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriadsX, int64& OpenTriadsX, int SampleNodes=-1);
37 
39 template <class PGraph> double GetNodeClustCf(const PGraph& Graph, const int& NId);
41 
43 template <class PGraph> void GetNodeClustCf(const PGraph& Graph, TIntFltH& NIdCCfH);
44 
46 
50 template <class PGraph> int64 GetTriads(const PGraph& Graph, int SampleNodes=-1);
52 
55 template <class PGraph> int64 GetTriads(const PGraph& Graph, int64& ClosedTriadsX, int64& OpenTriadsX, int SampleNodes);
57 
61 template <class PGraph> int64 GetTriadsAll(const PGraph& Graph, int64& ClosedTriadsX, int64& OpenTriadsX, int SampleNodes=-1);
63 
67 template <class PGraph> void GetTriads(const PGraph& Graph, TIntTrV& NIdCOTriadV, int SampleNodes=-1);
69 
72 template <class PGraph> int GetTriadEdges(const PGraph& Graph, int SampleEdges=-1);
73 
75 
79 template <class PGraph> int GetNodeTriads(const PGraph& Graph, const int& NId);
81 
87 template <class PGraph> int GetNodeTriads(const PGraph& Graph, const int& NId, int& ClosedNTriadsX, int& OpenNTriadsX);
89 
96 template <class PGraph> int GetNodeTriadsAll(const PGraph& Graph, const int& NId, int& ClosedNTriadsX, int& OpenNTriadsX);
98 
106 template <class PGraph>
107 int GetNodeTriads(const PGraph& Graph, const int& NId, const TIntSet& GroupSet, int& InGroupEdgesX, int& InOutGroupEdgesX, int& OutGroupEdgesX);
109 
111 template <class PGraph> void GetTriadParticip(const PGraph& Graph, TIntPrV& TriadCntV);
112 
114 template<class PGraph> int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2);
116 template<class PGraph> int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV);
118 template<class PGraph> int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2);
120 
122 template<class PGraph> int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV);
124 template<class PGraph> int64 GetTriangleCnt(const PGraph& Graph);
126 template<class PGraph> void MergeNbrs(TIntV& NeighbourV, const typename PGraph::TObj::TNodeI& NI);
127 
129 template <class PGraph> void GetUniqueNbrV(const PGraph& Graph, const int& NId, TIntV& NbrV);
130 
132 int GetCommon(TIntV& A, TIntV& B);
133 
135 // Implementation
136 
137 template <class PGraph> double GetClustCf(const PGraph& Graph, int SampleNodes) {
138  TIntTrV NIdCOTriadV;
139  GetTriads(Graph, NIdCOTriadV, SampleNodes);
140  if (NIdCOTriadV.Empty()) { return 0.0; }
141  double SumCcf = 0.0;
142  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
143  const double OpenCnt = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
144  if (OpenCnt > 0) {
145  SumCcf += NIdCOTriadV[i].Val2() / OpenCnt; }
146  }
147  IAssert(SumCcf>=0);
148  return SumCcf / double(NIdCOTriadV.Len());
149 }
150 
151 template <class PGraph> double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int SampleNodes) {
152  TIntTrV NIdCOTriadV;
153  GetTriads(Graph, NIdCOTriadV, SampleNodes);
154  if (NIdCOTriadV.Empty()) {
155  DegToCCfV.Clr(false);
156  return 0.0;
157  }
158  THash<TInt, TFltPr> DegSumCnt;
159  double SumCcf = 0.0;
160  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
161  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
162  const double Ccf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
163  TFltPr& SumCnt = DegSumCnt.AddDat(Graph->GetNI(NIdCOTriadV[i].Val1).GetDeg());
164  SumCnt.Val1 += Ccf;
165  SumCnt.Val2 += 1;
166  SumCcf += Ccf;
167  }
168  // get average clustering coefficient for each degree
169  DegToCCfV.Gen(DegSumCnt.Len(), 0);
170  for (int d = 0; d < DegSumCnt.Len(); d++) {
171  DegToCCfV.Add(TFltPr(DegSumCnt.GetKey(d).Val, double(DegSumCnt[d].Val1()/DegSumCnt[d].Val2())));
172  }
173  DegToCCfV.Sort();
174  return SumCcf / double(NIdCOTriadV.Len());
175 }
176 
177 template <class PGraph>
178 double GetClustCf(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
179  TIntTrV NIdCOTriadV;
180  GetTriads(Graph, NIdCOTriadV, SampleNodes);
181  if (NIdCOTriadV.Empty()) {
182  DegToCCfV.Clr(false);
183  ClosedTriads = 0;
184  OpenTriads = 0;
185  return 0.0;
186  }
187  THash<TInt, TFltPr> DegSumCnt;
188  double SumCcf = 0.0;
189  int64 closedTriads = 0;
190  int64 openTriads = 0;
191  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
192  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
193  const double Ccf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
194  closedTriads += NIdCOTriadV[i].Val2;
195  openTriads += NIdCOTriadV[i].Val3;
196  TFltPr& SumCnt = DegSumCnt.AddDat(Graph->GetNI(NIdCOTriadV[i].Val1).GetDeg());
197  SumCnt.Val1 += Ccf;
198  SumCnt.Val2 += 1;
199  SumCcf += Ccf;
200  }
201  // get average clustering coefficient for each degree
202  DegToCCfV.Gen(DegSumCnt.Len(), 0);
203  for (int d = 0; d < DegSumCnt.Len(); d++) {
204  DegToCCfV.Add(TFltPr(DegSumCnt.GetKey(d).Val, DegSumCnt[d].Val1()/DegSumCnt[d].Val2()));
205  }
206  //if(closedTriads/3 > (uint64) TInt::Mx) { WarnNotify(TStr::Fmt("[%s line %d] %g closed triads.\n", __FILE__, __LINE__, float(closedTriads/3)).CStr()); }
207  //if(openTriads > (uint64) TInt::Mx) { WarnNotify(TStr::Fmt("[%s line %d] %g open triads.\n", __FILE__, __LINE__, float(openTriads/3)).CStr()); }
208  ClosedTriads = closedTriads/int64(3); // each triad is counted 3 times
209  OpenTriads = openTriads;
210  DegToCCfV.Sort();
211  return SumCcf / double(NIdCOTriadV.Len());
212 }
213 
214 template <class PGraph>
215 double GetClustCfAll(const PGraph& Graph, TFltPrV& DegToCCfV, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
216  return GetClustCf(Graph, DegToCCfV, ClosedTriads, OpenTriads, SampleNodes);
217 }
218 
219 template <class PGraph>
220 double GetNodeClustCf(const PGraph& Graph, const int& NId) {
221  int Open, Closed;
222  GetNodeTriads(Graph, NId, Open, Closed);
223  //const double Deg = Graph->GetNI(NId).GetDeg();
224  return (Open+Closed)==0 ? 0 : double(Open)/double(Open+Closed);
225 }
226 
227 template <class PGraph>
228 void GetNodeClustCf(const PGraph& Graph, TIntFltH& NIdCCfH) {
229  TIntTrV NIdCOTriadV;
230  GetTriads(Graph, NIdCOTriadV);
231  NIdCCfH.Clr(false);
232  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
233  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
234  const double CCf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
235  NIdCCfH.AddDat(NIdCOTriadV[i].Val1, CCf);
236  }
237 }
238 
239 template <class PGraph>
240 int64 GetTriads(const PGraph& Graph, int SampleNodes) {
241  int64 OpenTriads, ClosedTriads;
242  return GetTriads(Graph, ClosedTriads, OpenTriads, SampleNodes);
243 }
244 
245 template <class PGraph>
246 int64 GetTriads(const PGraph& Graph, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
247  TIntTrV NIdCOTriadV;
248  GetTriads(Graph, NIdCOTriadV, SampleNodes);
249  uint64 closedTriads = 0;
250  uint64 openTriads = 0;
251  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
252  closedTriads += NIdCOTriadV[i].Val2;
253  openTriads += NIdCOTriadV[i].Val3;
254  }
255  //IAssert(closedTriads/3 < (uint64) TInt::Mx);
256  //IAssert(openTriads < (uint64) TInt::Mx);
257  ClosedTriads = int64(closedTriads/3); // each triad is counted 3 times
258  OpenTriads = int64(openTriads);
259  return ClosedTriads;
260 }
261 
262 template <class PGraph>
263 int64 GetTriadsAll(const PGraph& Graph, int64& ClosedTriads, int64& OpenTriads, int SampleNodes) {
264  return GetTriads(Graph, ClosedTriads, OpenTriads, SampleNodes);
265 }
266 
267 // Function pretends that the graph is undirected (count unique connected triples of nodes)
268 // This implementation is slower, it uses hash tables directly
269 template <class PGraph>
270 void GetTriads_v0(const PGraph& Graph, TIntTrV& NIdCOTriadV, int SampleNodes) {
271  const bool IsDir = Graph->HasFlag(gfDirected);
272  TIntSet NbrH;
273  TIntV NIdV;
274  TRnd Rnd(0);
275 
276  Graph->GetNIdV(NIdV);
277  NIdV.Shuffle(Rnd);
278  if (SampleNodes == -1) {
279  SampleNodes = Graph->GetNodes(); }
280  NIdCOTriadV.Clr(false);
281  NIdCOTriadV.Reserve(SampleNodes);
282  for (int node = 0; node < SampleNodes; node++) {
283  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[node]);
284  if (NI.GetDeg() < 2) {
285  NIdCOTriadV.Add(TIntTr(NI.GetId(), 0, 0)); // zero triangles
286  continue;
287  }
288  // find neighborhood
289  NbrH.Clr(false);
290  for (int e = 0; e < NI.GetOutDeg(); e++) {
291  if (NI.GetOutNId(e) != NI.GetId()) {
292  NbrH.AddKey(NI.GetOutNId(e)); }
293  }
294  if (IsDir) {
295  for (int e = 0; e < NI.GetInDeg(); e++) {
296  if (NI.GetInNId(e) != NI.GetId()) {
297  NbrH.AddKey(NI.GetInNId(e)); }
298  }
299  }
300  // count connected neighbors
301  int OpenCnt=0, CloseCnt=0;
302  for (int srcNbr = 0; srcNbr < NbrH.Len(); srcNbr++) {
303  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrH.GetKey(srcNbr));
304  for (int dstNbr = srcNbr+1; dstNbr < NbrH.Len(); dstNbr++) {
305  const int dstNId = NbrH.GetKey(dstNbr);
306  if (SrcNode.IsNbrNId(dstNId)) { CloseCnt++; } // is edge
307  else { OpenCnt++; }
308  }
309  }
310  IAssert(2*(OpenCnt+CloseCnt) == NbrH.Len()*(NbrH.Len()-1));
311  NIdCOTriadV.Add(TIntTr(NI.GetId(), CloseCnt, OpenCnt));
312  }
313 }
314 
315 // Function pretends that the graph is undirected (count unique connected triples of nodes)
316 // This implementation is faster, it converts hash tables to vectors
317 template <class PGraph>
318 void GetTriads(const PGraph& Graph, TIntTrV& NIdCOTriadV, int SampleNodes) {
319  const bool IsDir = Graph->HasFlag(gfDirected);
320  TIntSet NbrH;
321  TIntV NIdV;
322  //TRnd Rnd(0);
323  TRnd Rnd(1);
324  int NNodes;
325  TIntV Nbrs;
326  int NId;
327 
328  int64 hcount;
329 
330  hcount = 0;
331 
332  NNodes = Graph->GetNodes();
333  Graph->GetNIdV(NIdV);
334  NIdV.Shuffle(Rnd);
335  if (SampleNodes == -1) {
336  SampleNodes = NNodes;
337  }
338 
339  int MxId = -1;
340  for (int i = 0; i < NNodes; i++) {
341  if (NIdV[i] > MxId) {
342  MxId = NIdV[i];
343  }
344  }
345 
346  TVec<TIntV> NbrV(MxId + 1);
347 
348  if (IsDir) {
349  // get in and out neighbors
350  for (int node = 0; node < NNodes; node++) {
351  int NId = NIdV[node];
352  NbrV[NId] = TIntV();
353  GetUniqueNbrV(Graph, NId, NbrV[NId]);
354  }
355  } else {
356  // get only out neighbors
357  for (int node = 0; node < NNodes; node++) {
358  int NId = NIdV[node];
359  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
360  NbrV[NId] = TIntV();
361  NbrV[NId].Reserve(NI.GetOutDeg());
362  NbrV[NId].Reduce(0);
363  for (int i = 0; i < NI.GetOutDeg(); i++) {
364  NbrV[NId].Add(NI.GetOutNId(i));
365  }
366  }
367  }
368 
369  NIdCOTriadV.Clr(false);
370  NIdCOTriadV.Reserve(SampleNodes);
371  for (int node = 0; node < SampleNodes; node++) {
372  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NIdV[node]);
373  int NLen;
374 
375  NId = NI.GetId();
376  hcount++;
377  if (NI.GetDeg() < 2) {
378  NIdCOTriadV.Add(TIntTr(NId, 0, 0)); // zero triangles
379  continue;
380  }
381 
382  Nbrs = NbrV[NId];
383  NLen = Nbrs.Len();
384 
385  // count connected neighbors
386  int OpenCnt1 = 0, CloseCnt1 = 0;
387  for (int srcNbr = 0; srcNbr < NLen; srcNbr++) {
388  int Count = GetCommon(NbrV[NbrV[NId][srcNbr]],Nbrs);
389  CloseCnt1 += Count;
390  }
391  CloseCnt1 /= 2;
392  OpenCnt1 = (NLen*(NLen-1))/2 - CloseCnt1;
393  NIdCOTriadV.Add(TIntTr(NId, CloseCnt1, OpenCnt1));
394  }
395 }
396 
397 #if 0
398 // OP RS 2016/08/25, this is an alternative implementation of GetTriangleCnt()
399 template<class PGraph>
400 int64 CountTriangles(const PGraph& Graph) {
402  TIntV MapV;
403 
404  int ind = 0;
405  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
406  H.AddDat(NI.GetId(), ind);
407  MapV.Add(NI.GetId());
408  ind += 1;
409  }
410 
411  TVec<TIntV> HigherDegNbrV(ind);
412 
413 #ifdef USE_OPENMP
414 #pragma omp parallel for schedule(dynamic)
415 #endif
416  for (int i = 0; i < ind; i++) {
417  typename PGraph::TObj::TNodeI NI = Graph->GetNI(MapV[i]);
418  TIntV NbrV;
419 
420  MergeNbrs<PGraph>(NbrV, NI);
421 
422  TIntV V;
423  for (int j = 0; j < NbrV.Len(); j++) {
424  TInt Vert = NbrV[j];
425  TInt Deg = Graph->GetNI(Vert).GetDeg();
426  if (Deg > NI.GetDeg() ||
427  (Deg == NI.GetDeg() && Vert > NI.GetId())) {
428  V.Add(Vert);
429  }
430  }
431 
432  HigherDegNbrV[i] = V;
433 
434  }
435 
436  int64 cnt = 0;
437 #ifdef USE_OPENMP
438 #pragma omp parallel for schedule(dynamic) reduction(+:cnt)
439 #endif
440  for (int i = 0; i < HigherDegNbrV.Len(); i++) {
441  for (int j = 0; j < HigherDegNbrV[i].Len(); j++) {
442  TInt NbrInd = H.GetDat(HigherDegNbrV[i][j]);
443 
444  int64 num = GetCommon(HigherDegNbrV[i], HigherDegNbrV[NbrInd]);
445  cnt += num;
446  }
447  }
448 
449  return cnt;
450 }
451 #endif
452 
453 template<class PGraph>
454 int64 GetTriangleCnt(const PGraph& Graph) {
455  const int NNodes = Graph->GetNodes();
456 
457  TIntV MapV(NNodes);
459  NV.Reduce(0);
460 
461  int MxId = -1;
462  int ind = 0;
463  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
464  NV.Add(NI);
465  int Id = NI.GetId();
466  if (Id > MxId) {
467  MxId = Id;
468  }
469  MapV[ind] = Id;
470  ind++;
471  }
472 
473  TIntV IndV(MxId+1);
474 
475  for (int j = 0; j < NNodes; j++) {
476  IndV[MapV[j]] = j;
477  }
478 
479  ind = MapV.Len();
480 
481  TVec<TIntV> HigherDegNbrV(ind);
482 
483  for (int i = 0; i < ind; i++) {
484  HigherDegNbrV[i] = TVec<TInt>();
485  HigherDegNbrV[i].Reserve(NV[i].GetDeg());
486  HigherDegNbrV[i].Reduce(0);
487  }
488 
489 #ifdef USE_OPENMP
490 #pragma omp parallel for schedule(dynamic)
491 #endif
492  for (int i = 0; i < ind; i++) {
493  typename PGraph::TObj::TNodeI NI = NV[i];
494  MergeNbrs<PGraph>(HigherDegNbrV[i], NI);
495 
496  int k = 0;
497  for (int j = 0; j < HigherDegNbrV[i].Len(); j++) {
498  TInt Vert = HigherDegNbrV[i][j];
499  TInt Deg = NV[IndV[Vert]].GetDeg();
500  if (Deg > NI.GetDeg() ||
501  (Deg == NI.GetDeg() && Vert > NI.GetId())) {
502  HigherDegNbrV[i][k] = Vert;
503  k++;
504  }
505  }
506  HigherDegNbrV[i].Reduce(k);
507  }
508 
509  int64 cnt = 0;
510 #ifdef USE_OPENMP
511 #pragma omp parallel for schedule(dynamic) reduction(+:cnt)
512 #endif
513  for (int i = 0; i < HigherDegNbrV.Len(); i++) {
514  for (int j = 0; j < HigherDegNbrV[i].Len(); j++) {
515  TInt NbrInd = IndV[HigherDegNbrV[i][j]];
516 
517  int64 num = GetCommon(HigherDegNbrV[i], HigherDegNbrV[NbrInd]);
518  cnt += num;
519  }
520  }
521 
522  return cnt;
523 }
524 
525 template<class PGraph>
526 void MergeNbrs(TIntV& NeighbourV, const typename PGraph::TObj::TNodeI& NI) {
527  int j = 0;
528  int k = 0;
529  int prev = -1;
530  int indeg = NI.GetInDeg();
531  int outdeg = NI.GetOutDeg();
532  if (indeg > 0 && outdeg > 0) {
533  int v1 = NI.GetInNId(j);
534  int v2 = NI.GetOutNId(k);
535  while (1) {
536  if (v1 <= v2) {
537  if (prev != v1) {
538  NeighbourV.Add(v1);
539  prev = v1;
540  }
541  j += 1;
542  if (j >= indeg) {
543  break;
544  }
545  v1 = NI.GetInNId(j);
546  } else {
547  if (prev != v2) {
548  NeighbourV.Add(v2);
549  prev = v2;
550  }
551  k += 1;
552  if (k >= outdeg) {
553  break;
554  }
555  v2 = NI.GetOutNId(k);
556  }
557  }
558  }
559  while (j < indeg) {
560  int v = NI.GetInNId(j);
561  if (prev != v) {
562  NeighbourV.Add(v);
563  prev = v;
564  }
565  j += 1;
566  }
567  while (k < outdeg) {
568  int v = NI.GetOutNId(k);
569  if (prev != v) {
570  NeighbourV.Add(v);
571  prev = v;
572  }
573  k += 1;
574  }
575 }
576 
577 // Count the number of edges that participate in at least one triad
578 template <class PGraph>
579 int GetTriadEdges(const PGraph& Graph, int SampleEdges) {
580  const bool IsDir = Graph->HasFlag(gfDirected);
581  TIntSet NbrH;
582  int TriadEdges = 0;
583  for(typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
584  NbrH.Clr(false);
585  for (int e = 0; e < NI.GetOutDeg(); e++) {
586  if (NI.GetOutNId(e) != NI.GetId()) {
587  NbrH.AddKey(NI.GetOutNId(e)); }
588  }
589  if (IsDir) {
590  for (int e = 0; e < NI.GetInDeg(); e++) {
591  if (NI.GetInNId(e) != NI.GetId()) {
592  NbrH.AddKey(NI.GetInNId(e)); }
593  }
594  }
595  for (int e = 0; e < NI.GetOutDeg(); e++) {
596  if (!IsDir && NI.GetId()<NI.GetOutNId(e)) { continue; } // for undirected graphs count each edge only once
597  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NI.GetOutNId(e));
598  bool Triad=false;
599  for (int e1 = 0; e1 < SrcNode.GetOutDeg(); e1++) {
600  if (NbrH.IsKey(SrcNode.GetOutNId(e1))) { Triad=true; break; }
601  }
602  if (IsDir && ! Triad) {
603  for (int e1 = 0; e1 < SrcNode.GetInDeg(); e1++) {
604  if (NbrH.IsKey(SrcNode.GetInNId(e1))) { Triad=true; break; }
605  }
606  }
607  if (Triad) { TriadEdges++; }
608  }
609  }
610  return TriadEdges;
611 }
612 
613 // Returns number of undirected triads a node participates in
614 template <class PGraph>
615 int GetNodeTriads(const PGraph& Graph, const int& NId) {
616  int ClosedTriads=0, OpenTriads=0;
617  return GetNodeTriads(Graph, NId, ClosedTriads, OpenTriads);
618 }
619 
620 // Return number of undirected triads a node participates in
621 template <class PGraph>
622 int GetNodeTriads(const PGraph& Graph, const int& NId, int& ClosedTriads, int& OpenTriads) {
623  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
624  ClosedTriads=0; OpenTriads=0;
625  if (NI.GetDeg() < 2) { return 0; }
626  // find neighborhood
627  TIntSet NbrSet(NI.GetDeg());
628  for (int e = 0; e < NI.GetOutDeg(); e++) {
629  if (NI.GetOutNId(e) != NI.GetId()) { // exclude self edges
630  NbrSet.AddKey(NI.GetOutNId(e)); }
631  }
632  if (Graph->HasFlag(gfDirected)) {
633  for (int e = 0; e < NI.GetInDeg(); e++) {
634  if (NI.GetInNId(e) != NI.GetId()) { // exclude self edges
635  NbrSet.AddKey(NI.GetInNId(e)); }
636  }
637  }
638  // count connected neighbors
639  for (int srcNbr = 0; srcNbr < NbrSet.Len(); srcNbr++) {
640  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrSet.GetKey(srcNbr));
641  for (int dstNbr = srcNbr+1; dstNbr < NbrSet.Len(); dstNbr++) {
642  const int dstNId = NbrSet.GetKey(dstNbr);
643  if (SrcNode.IsNbrNId(dstNId)) { ClosedTriads++; }
644  else { OpenTriads++; }
645  }
646  }
647  return ClosedTriads;
648 }
649 
650 template <class PGraph>
651 int GetNodeTriadsAll(const PGraph& Graph, const int& NId, int& ClosedTriads, int& OpenTriads) {
652  return GetNodeTriads(Graph, NId, ClosedTriads, OpenTriads);
653 }
654 
655 // Node NId and a subset of its neighbors GroupSet
656 // InGroupEdges ... triads (NId, g1, g2), where g1 and g2 are in GroupSet
657 // InOutGroupEdges ... triads (NId, g1, o1), where g1 in GroupSet and o1 not in GroupSet
658 // OutGroupEdges ... triads (NId, o1, o2), where o1 and o2 are not in GroupSet
659 template <class PGraph>
660 int GetNodeTriads(const PGraph& Graph, const int& NId, const TIntSet& GroupSet, int& InGroupEdges, int& InOutGroupEdges, int& OutGroupEdges) {
661  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
662  const bool IsDir = Graph->HasFlag(gfDirected);
663  InGroupEdges=0; InOutGroupEdges=0; OutGroupEdges=0;
664  if (NI.GetDeg() < 2) { return 0; }
665  // find neighborhood
666  TIntSet NbrSet(NI.GetDeg());
667  for (int e = 0; e < NI.GetOutDeg(); e++) {
668  if (NI.GetOutNId(e) != NI.GetId()) { // exclude self edges
669  NbrSet.AddKey(NI.GetOutNId(e)); }
670  }
671  if (IsDir) {
672  for (int e = 0; e < NI.GetInDeg(); e++) {
673  if (NI.GetInNId(e) != NI.GetId()) {
674  NbrSet.AddKey(NI.GetInNId(e)); }
675  }
676  }
677  // count connected neighbors
678  for (int srcNbr = 0; srcNbr < NbrSet.Len(); srcNbr++) {
679  const int NbrId = NbrSet.GetKey(srcNbr);
680  const bool NbrIn = GroupSet.IsKey(NbrId);
681  const typename PGraph::TObj::TNodeI SrcNode = Graph->GetNI(NbrId);
682  for (int dstNbr = srcNbr+1; dstNbr < NbrSet.Len(); dstNbr++) {
683  const int DstNId = NbrSet.GetKey(dstNbr);
684  if (SrcNode.IsNbrNId(DstNId)) { // triad (NId, NbrId, DstNid)
685  bool DstIn = GroupSet.IsKey(DstNId);
686  if (NbrIn && DstIn) { InGroupEdges++; }
687  else if (NbrIn || DstIn) { InOutGroupEdges++; }
688  else { OutGroupEdges++; }
689  }
690  }
691  }
692  return InGroupEdges;
693 }
694 
695 // For each node count how many triangles it participates in
696 template <class PGraph>
697 void GetTriadParticip(const PGraph& Graph, TIntPrV& TriadCntV) {
698  TIntH TriadCntH;
699  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
700  const int Triads = GetNodeTriads(Graph, NI.GetId());
701  TriadCntH.AddDat(Triads) += 1;
702  }
703  TriadCntH.GetKeyDatPrV(TriadCntV);
704  TriadCntV.Sort();
705 }
706 
707 template<class PGraph>
708 int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2) {
709  TIntV NbrV;
710  return GetCmnNbrs(Graph, NId1, NId2, NbrV);
711 }
712 
713 // Get common neighbors between a pair of nodes (undirected)
714 template<class PGraph>
715 int GetCmnNbrs(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
716  if (! Graph->IsNode(NId1) || ! Graph->IsNode(NId2)) { NbrV.Clr(false); return 0; }
717  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId1);
718  typename PGraph::TObj::TNodeI NI2 = Graph->GetNI(NId2);
719  NbrV.Clr(false);
720  NbrV.Reserve(TMath::Mn(NI1.GetDeg(), NI2.GetDeg()));
721  TIntSet NSet1(NI1.GetDeg()), NSet2(NI2.GetDeg());
722  for (int i = 0; i < NI1.GetDeg(); i++) {
723  const int nid = NI1.GetNbrNId(i);
724  if (nid!=NId1 && nid!=NId2) {
725  NSet1.AddKey(nid); }
726  }
727  for (int i = 0; i < NI2.GetDeg(); i++) {
728  const int nid = NI2.GetNbrNId(i);
729  if (NSet1.IsKey(nid)) {
730  NSet2.AddKey(nid);
731  }
732  }
733  NSet2.GetKeyV(NbrV);
734  return NbrV.Len();
735 }
736 
737 template<>
738 inline int GetCmnNbrs<PUNGraph>(const PUNGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
739  if (! Graph->IsNode(NId1) || ! Graph->IsNode(NId2)) { NbrV.Clr(false); return 0; }
740  const TUNGraph::TNodeI NI1 = Graph->GetNI(NId1);
741  const TUNGraph::TNodeI NI2 = Graph->GetNI(NId2);
742  int i=0, j=0;
743  NbrV.Clr(false);
744  NbrV.Reserve(TMath::Mn(NI1.GetDeg(), NI2.GetDeg()));
745  while (i < NI1.GetDeg() && j < NI2.GetDeg()) {
746  const int nid = NI1.GetNbrNId(i);
747  while (j < NI2.GetDeg() && NI2.GetNbrNId(j) < nid) { j++; }
748  if (j < NI2.GetDeg() && nid==NI2.GetNbrNId(j) && nid!=NId1 && nid!=NId2) {
749  IAssert(NbrV.Empty() || NbrV.Last() < nid);
750  NbrV.Add(nid);
751  j++;
752  }
753  i++;
754  }
755  return NbrV.Len();
756 }
757 
758 // get number of length 2 directed paths between a pair of nodes
759 // for a pair of nodes (i,j): |{u: (i,u) and (u,j) }|
760 template<class PGraph>
761 int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2) {
762  TIntV NbrV;
763  return GetLen2Paths(Graph, NId1, NId2, NbrV);
764 }
765 
766 // get number of length 2 directed paths between a pair of nodes
767 // for a pair of nodes (i,j): {u: (i,u) and (u,j) }
768 template<class PGraph>
769 int GetLen2Paths(const PGraph& Graph, const int& NId1, const int& NId2, TIntV& NbrV) {
770  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId1);
771  NbrV.Clr(false);
772  NbrV.Reserve(NI.GetOutDeg());
773  for (int e = 0; e < NI.GetOutDeg(); e++) {
774  const typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(NI.GetOutNId(e));
775  if (MidNI.IsOutNId(NId2)) {
776  NbrV.Add(MidNI.GetId());
777  }
778  }
779  return NbrV.Len();
780 }
781 
782 template <class PGraph>
783 void GetUniqueNbrV(const PGraph& Graph, const int& NId, TIntV& NbrV) {
784  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
785  NbrV.Reserve(NI.GetDeg());
786  NbrV.Reduce(0);
787 
788  int j = 0;
789  int k = 0;
790  int Prev = -1;
791  int InDeg = NI.GetInDeg();
792  int OutDeg = NI.GetOutDeg();
793  if (InDeg > 0 && OutDeg > 0) {
794  int v1 = NI.GetInNId(j);
795  int v2 = NI.GetOutNId(k);
796  while (1) {
797  if (v1 <= v2) {
798  if (Prev != v1) {
799  if (v1 != NId) {
800  NbrV.Add(v1);
801  Prev = v1;
802  }
803  }
804  j += 1;
805  if (j >= InDeg) {
806  break;
807  }
808  v1 = NI.GetInNId(j);
809  } else {
810  if (Prev != v2) {
811  if (v2 != NId) {
812  NbrV.Add(v2);
813  }
814  Prev = v2;
815  }
816  k += 1;
817  if (k >= OutDeg) {
818  break;
819  }
820  v2 = NI.GetOutNId(k);
821  }
822  }
823  }
824  while (j < InDeg) {
825  int v = NI.GetInNId(j);
826  if (Prev != v) {
827  if (v != NId) {
828  NbrV.Add(v);
829  }
830  Prev = v;
831  }
832  j += 1;
833  }
834  while (k < OutDeg) {
835  int v = NI.GetOutNId(k);
836  if (Prev != v) {
837  if (v != NId) {
838  NbrV.Add(v);
839  }
840  Prev = v;
841  }
842  k += 1;
843  }
844 }
845 
846 }; // mamespace TSnap
847 
849 // Node and Edge Network Constraint (by Ron Burt)
850 // works for directed and undirected graphs (but not for multigraphs)
851 template <class PGraph>
853 public:
854  PGraph Graph;
855  THash<TIntPr, TFlt> NodePrCH; // pairs of nodes that have non-zero network constraint
856 public:
857  TNetConstraint(const PGraph& GraphPt, const bool& CalcaAll=true);
858  int Len() const { return NodePrCH.Len(); }
859  double GetC(const int& ConstraintN) const { return NodePrCH[ConstraintN]; }
860  TIntPr GetNodePr(const int& ConstraintN) const { return NodePrCH.GetKey(ConstraintN); }
861  double GetEdgeC(const int& NId1, const int& NId2) const;
862  double GetNodeC(const int& NId) const;
863  void AddConstraint(const int& NId1, const int& NId2);
864  void CalcConstraints();
865  void CalcConstraints(const int& NId);
866  void Dump() const;
867  static void Test();
868 };
869 
870 template <class PGraph>
871 TNetConstraint<PGraph>::TNetConstraint(const PGraph& GraphPt, const bool& CalcaAll) : Graph(GraphPt) {
872  CAssert(! HasGraphFlag(typename PGraph::TObj, gfMultiGraph)); // must not be multigraph
873  if (CalcaAll) {
874  CalcConstraints();
875  }
876 }
877 
878 template <class PGraph>
879 double TNetConstraint<PGraph>::GetEdgeC(const int& NId1, const int& NId2) const {
880  if (NodePrCH.IsKey(TIntPr(NId1, NId2))) {
881  return NodePrCH.GetDat(TIntPr(NId1, NId2)); }
882  else {
883  return 0.0; }
884 }
885 
886 template <class PGraph>
887 double TNetConstraint<PGraph>::GetNodeC(const int& NId) const {
888  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId);
889  if (NI1.GetOutDeg() == 0) { return 0.0; }
890  int KeyId = -1;
891  for (int k = 0; k<NI1.GetOutDeg(); k++) {
892  KeyId = NodePrCH.GetKeyId(TIntPr(NI1.GetId(), NI1.GetOutNId(k)));
893  if (KeyId > -1) { break; }
894  }
895  if (KeyId < 0) { return 0.0; }
896  double Constraint = NodePrCH[KeyId];
897  for (int i = KeyId-1; i >-1 && NodePrCH.GetKey(i).Val1()==NId; i--) {
898  Constraint += NodePrCH[i];
899  }
900  for (int i = KeyId+1; i < NodePrCH.Len() && NodePrCH.GetKey(i).Val1()==NId; i++) {
901  Constraint += NodePrCH[i];
902  }
903  return Constraint;
904 }
905 
906 template <class PGraph>
907 void TNetConstraint<PGraph>::AddConstraint(const int& NId1, const int& NId2) {
908  if (NId1==NId2 || NodePrCH.IsKey(TIntPr(NId1, NId2))) {
909  return;
910  }
911  typename PGraph::TObj::TNodeI NI1 = Graph->GetNI(NId1);
912  double Constraint = 0.0;
913  if (NI1.IsOutNId(NId2)) { // is direct edge
914  Constraint += 1.0/(double) NI1.GetOutDeg();
915  }
916  const double SrcC = 1.0/(double) NI1.GetOutDeg();
917  for (int e = 0; e < NI1.GetOutDeg(); e++) {
918  const int MidNId = NI1.GetOutNId(e);
919  if (MidNId == NId1 || MidNId == NId2) { continue; }
920  const typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(MidNId);
921  if (MidNI.IsOutNId(NId2)) {
922  Constraint += SrcC * (1.0/(double)MidNI.GetOutDeg());
923  }
924  }
925  if (Constraint==0) { return; }
926  Constraint = TMath::Sqr(Constraint);
927  NodePrCH.AddDat(TIntPr(NId1, NId2), Constraint);
928 }
929 
930 template <class PGraph>
932  // add edges
933  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
934  AddConstraint(EI.GetSrcNId(), EI.GetDstNId());
935  AddConstraint(EI.GetDstNId(), EI.GetSrcNId());
936  }
937  // add open triads
938  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
939  for (int i = 0; i < NI.GetDeg(); i++) {
940  const int NId1 = NI.GetNbrNId(i);
941  for (int j = 0; j < NI.GetDeg(); j++) {
942  const int NId2 = NI.GetNbrNId(j);
943  AddConstraint(NId1, NId2);
944  }
945  }
946  }
947  NodePrCH.SortByKey();
948 }
949 
950 // calculate constraints around a node id
951 template <class PGraph>
953  typename PGraph::TObj::TNodeI StartNI = Graph->GetNI(NId);
954  TIntSet SeenSet;
955  for (int e = 0; e < StartNI.GetOutDeg(); e++) {
956  typename PGraph::TObj::TNodeI MidNI = Graph->GetNI(StartNI.GetOutNId(e));
957  AddConstraint(NId, MidNI.GetId());
958  for (int i = 0; i < MidNI.GetOutDeg(); i++) {
959  const int EndNId = MidNI.GetOutNId(i);
960  if (! SeenSet.IsKey(EndNId)) {
961  AddConstraint(NId, EndNId);
962  SeenSet.AddKey(EndNId);
963  }
964  }
965  }
966 }
967 
968 template <class PGraph>
970  printf("Edge network constraint: (%d, %d)\n", Graph->GetNodes(), Graph->GetEdges());
971  for (int e = 0; e < NodePrCH.Len(); e++) {
972  printf(" %4d %4d : %f\n", NodePrCH.GetKey(e).Val1(), NodePrCH.GetKey(e).Val2(), NodePrCH[e].Val);
973  }
974  printf("\n");
975 }
976 
977 // example from page 56 of Structural Holes by Ronald S. Burt
978 // (http://www.amazon.com/Structural-Holes-Social-Structure-Competition/dp/0674843711)
979 template <class PGraph>
981  PUNGraph G = TUNGraph::New();
982  G->AddNode(0); G->AddNode(1); G->AddNode(2); G->AddNode(3);
983  G->AddNode(4); G->AddNode(5); G->AddNode(6);
984  G->AddEdge(0,1); G->AddEdge(0,2); G->AddEdge(0,3); G->AddEdge(0,4); G->AddEdge(0,5); G->AddEdge(0,6);
985  G->AddEdge(1,2); G->AddEdge(1,5); G->AddEdge(1,6);
986  G->AddEdge(2,4);
987  TNetConstraint<PUNGraph> NetConstraint(G, true);
988  // NetConstraint.CalcConstraints(0);
989  NetConstraint.Dump();
990  printf("middle node network constraint: %f\n", NetConstraint.GetNodeC(0));
991 }
992 
993 #endif // TRIAD_H
994 
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
void GetUniqueNbrV(const PGraph &Graph, const int &NId, TIntV &NbrV)
Returns sorted vector NbrV containing unique in or out neighbors of node NId in graph Graph...
Definition: triad.h:783
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Main namespace for all the Snap global entities.
Definition: alg.h:1
int64 GetTriads(const PGraph &Graph, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:246
void CalcConstraints()
Definition: triad.h:931
Definition: dt.h:11
int64 GetTriangleCnt(const PGraph &Graph)
Returns the number of triangles in graph Graph.
Definition: triad.h:454
int Val
Definition: dt.h:1139
double GetNodeClustCf(const PGraph &Graph, const int &NId)
Returns clustering coefficient of a particular node.
Definition: triad.h:220
static void Test()
Definition: triad.h:980
int GetLen2Paths(const PGraph &Graph, const int &NId1, const int &NId2)
Returns the number of length 2 directed paths between a pair of nodes NId1, NId2 (NId1 –> U –> NId2...
Definition: triad.h:761
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
PGraph Graph
Definition: triad.h:854
int GetCmnNbrs< PUNGraph >(const PUNGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV)
Definition: triad.h:738
void MergeNbrs(TIntV &NeighbourV, const typename PGraph::TObj::TNodeI &NI)
Merges neighbors by removing duplicates and produces one sorted vector of neighbors.
Definition: triad.h:526
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
static double Sqr(const double &x)
Definition: xmath.h:12
TNetConstraint(const PGraph &GraphPt, const bool &CalcaAll=true)
Definition: triad.h:871
void Reduce(const TSizeTy &_Vals=-1)
Reduces the vector's length to _Vals elements, which must be less than the current length...
Definition: ds.h:556
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1141
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:90
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
unsigned long long uint64
Definition: bd.h:38
void GetTriads_v0(const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes)
Definition: triad.h:270
void AddConstraint(const int &NId1, const int &NId2)
Definition: triad.h:907
int GetNodeTriadsAll(const PGraph &Graph, const int &NId, int &ClosedNTriadsX, int &OpenNTriadsX)
Returns number of Open and Closed triads a node NId participates in.
Definition: triad.h:651
double GetNodeC(const int &NId) const
Definition: triad.h:887
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddKey(const TKey &Key)
Definition: shash.h:1254
int GetNodeTriads(const PGraph &Graph, const int &NId)
Returns the number of undirected triads a node NId participates in.
Definition: triad.h:615
double GetClustCfAll(const PGraph &Graph, TFltPrV &DegToCCfV, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes=-1)
Computes the distribution of average clustering coefficient as well as the number of open and closed ...
Definition: triad.h:215
int64 GetTriadsAll(const PGraph &Graph, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes=-1)
Computes the number of Closed and Open triads.
Definition: triad.h:263
double GetC(const int &ConstraintN) const
Definition: triad.h:859
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
void Dump() const
Definition: triad.h:969
Definition: dt.h:1137
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
double GetEdgeC(const int &NId1, const int &NId2) const
Definition: triad.h:879
#define CAssert(Cond)
Definition: bd.h:302
int Len() const
Definition: shash.h:1121
long long int64
Definition: bd.h:27
int GetTriadEdges(const PGraph &Graph, int SampleEdges=-1)
Counts the number of edges that participate in at least one triad.
Definition: triad.h:579
int GetCommon(TIntV &A, TIntV &B)
Returns the number of common elements in two sorted TInt vectors.
Definition: triad.cpp:59
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
void GetTriadParticip(const PGraph &Graph, TIntPrV &TriadCntV)
Triangle Participation Ratio: For each node counts how many triangles it participates in and then ret...
Definition: triad.h:697
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
double GetClustCf(const PGraph &Graph, int SampleNodes=-1)
Computes the average clustering coefficient as defined in Watts and Strogatz, Collective dynamics of ...
Definition: triad.h:137
TVal1 Val1
Definition: ds.h:34
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:111
TVec< TInt > TIntV
Definition: ds.h:1594
TVal2 Val2
Definition: ds.h:35
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TIntPr GetNodePr(const int &ConstraintN) const
Definition: triad.h:860
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:171
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
THash< TIntPr, TFlt > NodePrCH
Definition: triad.h:855
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
int GetCmnNbrs(const PGraph &Graph, const int &NId1, const int &NId2)
Returns a number of shared neighbors between a pair of nodes NId1 and NId2.
Definition: triad.h:708
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
int Len() const
Definition: triad.h:858
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430