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
casc.cpp
Go to the documentation of this file.
1 namespace TSnap {
2 
3 PNGraph CascGraphSource(PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,const TInt W) {
4  // Attribute to Int mapping
5  TInt SIdx = P->GetColIdx(C1); //Source
6  TInt DIdx = P->GetColIdx(C2); //Dest
7  TInt StIdx = P->GetColIdx(C3); //Start
8  TInt DuIdx = P->GetColIdx(C4); //Duration
9  TIntV MapV;
10  TStrV SortBy;
11  SortBy.Add(C1);
12  P->Order(SortBy);
13  TIntV Source;
14  P->ReadIntCol(C1,Source);
15  PNGraph Graph = TNGraph::New();
16  //Add Nodes
17  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
18  Graph->AddNode(RI.GetRowIdx().Val);
19  MapV.Add(RI.GetRowIdx());
20  }
21  //Add Edges
22  for (TRowIterator OI = P->BegRI(); OI < P->EndRI(); OI++) {
23  int OIdx = OI.GetRowIdx().Val;
24  int ODest = P->GetIntValAtRowIdx(DIdx,OIdx).Val;
25  int OStart = P->GetIntValAtRowIdx(StIdx,OIdx).Val;
26  int ODur = P->GetIntValAtRowIdx(DuIdx,OIdx).Val;
27  // Inline binary Search
28  int val = ODest;
29  int lo = 0;
30  int hi = Source.Len() - 1;
31  int index = -1;
32  while (hi >= lo) {
33  int mid = lo + (hi - lo)/2;
34  if (Source.GetVal(mid) > val) { hi = mid - 1;}
35  else if (Source.GetVal(mid) < val) { lo = mid + 1;}
36  else { index = mid; hi = mid - 1;}
37  }
38  // End of binary Search
39  if (index < 0) {
40  continue;
41  }
42  int BIdx = index;
43  for(int i = BIdx; i < Source.Len(); i++) {
44  int InIdx = MapV.GetVal(i).Val;
45  if (InIdx == OIdx) {continue;}
46  int InSource = P->GetIntValAtRowIdx(SIdx,InIdx).Val;
47  int InStart = P->GetIntValAtRowIdx(StIdx,InIdx).Val;
48  if (InSource != ODest) { break;}
49  if (InStart >= (ODur + OStart) && InStart - (ODur + OStart) <= W.Val) {
50  if (!Graph->IsEdge(OIdx,InIdx)) {
51  Graph->AddEdge(OIdx,InIdx);
52  }
53  }
54  }
55  }
56  return Graph;
57 }
58 
59 PNGraph CascGraphTime(PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,const TInt W) {
60  // Attribute to Int mapping
61  TInt SIdx = P->GetColIdx(C1); //Source
62  TInt DIdx = P->GetColIdx(C2); //Dest
63  TInt StIdx = P->GetColIdx(C3); //Start
64  TInt DuIdx = P->GetColIdx(C4); //Duration
65  TIntV MapV;
66  TStrV SortBy;
67  SortBy.Add(C3);
68  P->Order(SortBy);
69  TIntV Start;
70  P->ReadIntCol(C3,Start);
71  PNGraph Graph = TNGraph::New();
72  //Add Nodes
73  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
74  Graph->AddNode(RI.GetRowIdx().Val);
75  MapV.Add(RI.GetRowIdx());
76  }
77  //Add Edges
78  for (TRowIterator OI = P->BegRI(); OI < P->EndRI(); OI++) {
79  int OIdx = OI.GetRowIdx().Val;
80  int ODest = P->GetIntValAtRowIdx(DIdx,OIdx).Val;
81  int OStart = P->GetIntValAtRowIdx(StIdx,OIdx).Val;
82  int ODur = P->GetIntValAtRowIdx(DuIdx,OIdx).Val;
83  // Inline binary Search
84  int val = OStart + ODur;
85  int lo = 0;
86  int hi = Start.Len() - 1;
87  int index = -1;
88  if (val >= Start.GetVal(hi)) { val = Start.GetVal(hi);}
89  while (hi >= lo) {
90  int mid = lo + (hi - lo)/2;
91  if (Start.GetVal(mid) > val) {
92  if ((mid-1) >= lo && Start.GetVal(mid - 1) < val) {
93  index = mid - 1;break;
94  }
95  hi = mid - 1;
96  }
97  else if (Start.GetVal(mid) < val) {
98  if (mid + 1 <= hi && Start.GetVal(mid + 1) > val) {
99  index = mid;break;
100  }
101  lo = mid + 1;
102  }
103  else { index = mid; hi = mid - 1;}
104  }
105  // End of binary Search
106  if (index < 0) {
107  continue;
108  }
109  int BIdx = index;
110  for(int i = BIdx; i < Start.Len(); i++) {
111  int InIdx = MapV.GetVal(i).Val;
112  if (InIdx == OIdx) {continue;}
113  int InSource = P->GetIntValAtRowIdx(SIdx,InIdx).Val;
114  int InStart = P->GetIntValAtRowIdx(StIdx,InIdx).Val;
115  if (InStart - (ODur + OStart) > W.Val) { break;}
116  if (InSource == ODest && InStart >= (ODur + OStart)) {
117  if (!Graph->IsEdge(OIdx,InIdx)) {
118  Graph->AddEdge(OIdx,InIdx);
119  }
120  }
121  }
122  }
123  return Graph;
124 }
125 
126 PNGraph CascGraph(PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,const TInt W,bool SortParam) {
127  if (SortParam) {
128  return CascGraphSource(P, C1, C2, C3, C4, W);
129  }
130  else {
131  return CascGraphTime(P, C1, C2, C3, C4, W);
132  }
133 }
134 
135 void CascFind(PNGraph Graph,PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,TVec<TIntV> &TopCascVV,bool Print) {
136  // Attribute to Int mapping
137  TInt SIdx = P->GetColIdx(C1);
138  TInt DIdx = P->GetColIdx(C2);
139  TInt StIdx = P->GetColIdx(C3);
140  TInt DuIdx = P->GetColIdx(C4);
141  TIntV MapV, PhyV;
142  TStrV SortBy;
143  SortBy.Add(C3);
144  P->Order(SortBy);
145  int count = 0;
146  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
147  MapV.Add(RI.GetRowIdx());
148  PhyV.Add(count++);
149  }
150  // After sort attach with each row a rank helpful for sorting
151  P->StoreIntCol("Physical",PhyV);
152  TInt PIdx = P->GetColIdx("Physical");
153  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
154  // Check for top cascades
155  if (NI.GetInDeg() != 0) { continue;}
156  TIntV CurCasc;
157  TSnapQueue<TInt> EventQ;
158  THashSet<TInt> VisitedH;
159  TInt NId = NI.GetId();
160  EventQ.Push(NId);
161  VisitedH.AddKey(NId);
162  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,NId));
163  while (! EventQ.Empty()) {
164  TNGraph::TNodeI CNI = Graph->GetNI(EventQ.Top().Val); //Get Current Node
165  EventQ.Pop();
166  // Go over the outdegree nodes of the currernt node
167  for (int e = 0; e < CNI.GetOutDeg(); e++) {
168  TInt CId = CNI.GetOutNId(e);
169  if ( !VisitedH.IsKey(CId)) {
170  EventQ.Push(CId);
171  VisitedH.AddKey(CId);
172  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,CId));
173  }
174  }
175  }
176  CurCasc.Sort();
177  TIntV ToAddV;
178  if (Print && VisitedH.Len() > 1) {
179  printf("__casacade__\t%d\n",VisitedH.Len());
180  }
181  for (TIntV::TIter VI = CurCasc.BegI(); VI < CurCasc.EndI(); VI++) {
182  ToAddV.Add(MapV.GetVal(VI->Val));
183  if (Print && VisitedH.Len() > 1) {
184  int PIdx = MapV.GetVal(VI->Val).Val;
185  int PSource = P->GetIntValAtRowIdx(SIdx,PIdx).Val;
186  int PDest = P->GetIntValAtRowIdx(DIdx,PIdx).Val;
187  int PStart = P->GetIntValAtRowIdx(StIdx,PIdx).Val;
188  int PDur = P->GetIntValAtRowIdx(DuIdx,PIdx).Val;
189  printf("%d\t%d\t%d\t%d\t%d\n",PIdx,PSource,PDest,PStart,PDur);
190  }
191  }
192  if (ToAddV.Len() > 1) {
193  TopCascVV.Add(ToAddV);
194  }
195  }
196  return;
197 }
198 
199 #ifdef USE_OPENMP
200 void CascFindMP(PNGraph Graph,PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,TVec<TIntV> &TopCascVV) {
201  // Attribute to Int mapping
202  TInt SIdx = P->GetColIdx(C1);
203  TInt DIdx = P->GetColIdx(C2);
204  TInt StIdx = P->GetColIdx(C3);
205  TInt DuIdx = P->GetColIdx(C4);
206  TIntV MapV, PhyV;
207  TStrV SortBy;
208  SortBy.Add(C3);
209  P->Order(SortBy);
210  int count = 0;
211  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
212  MapV.Add(RI.GetRowIdx());
213  PhyV.Add(count++);
214  }
215  P->StoreIntCol("Physical",PhyV);
216  TInt PIdx = P->GetColIdx("Physical");
217  TIntV GNodeV;
218  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
219  if (NI.GetInDeg() == 0) { GNodeV.Add(NI.GetId()); }
220  }
221  TVec<TIntV> ThTopCascVV; // for each thread
222  #pragma omp parallel private(ThTopCascVV) num_threads(10)
223  {
224  #pragma omp for schedule(dynamic,1000)
225  for (int i = 0; i < GNodeV.Len(); i++) {
226  TIntV CurCasc;
227  TSnapQueue<TInt> EventQ;
228  THashSet<TInt> VisitedH;
229  TInt NId = GNodeV[i];
230  EventQ.Push(NId);
231  VisitedH.AddKey(NId);
232  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,NId));
233  while (! EventQ.Empty()) {
234  TNGraph::TNodeI CNI = Graph->GetNI(EventQ.Top().Val); //Get Current Node
235  EventQ.Pop();
236  // Go over the outdegree nodes of the currernt node
237  for (int e = 0; e < CNI.GetOutDeg(); e++) {
238  TInt CId = CNI.GetOutNId(e);
239  if ( !VisitedH.IsKey(CId)) {
240  EventQ.Push(CId);
241  VisitedH.AddKey(CId);
242  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,CId));
243  }
244  }
245  }
246  CurCasc.Sort();
247  TIntV ToAddV;
248  for (TIntV::TIter VI = CurCasc.BegI(); VI < CurCasc.EndI(); VI++) {
249  ToAddV.Add(MapV.GetVal(VI->Val));
250  }
251  if (ToAddV.Len() > 1) { ThTopCascVV.Add(ToAddV);}
252  }
253  #pragma omp critical
254  {
255  for (int j = 0; j < ThTopCascVV.Len(); j++) {
256  TopCascVV.Add(ThTopCascVV[j]);
257  }
258  }
259  }
260  return;
261 }
262 #endif // USE_OPENMP
263 } //Namespace TSnap
TSnap
Main namespace for all the Snap global entities.
Definition: alg.h:1
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TInt::Val
int Val
Definition: dt.h:1139
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TSnap::CascFind
void CascFind(PNGraph Graph, PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, TVec< TIntV > &TopCascVV, bool Print)
Takes as input a directed graph and returns all the top cascades in TopCascVV.
Definition: casc.cpp:135
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
TSnapQueue::Pop
void Pop()
Removes the first element from the queue.
Definition: gbase.h:211
TSnapQueue::Empty
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:199
TRowIterator
Iterator class for TTable rows.
Definition: table.h:330
TSnap::CascGraphSource
PNGraph CascGraphSource(PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W)
Takes as input the column names of the PTable P as C1, C2,C3 and C4 and returns a directed graph of W...
Definition: casc.cpp:3
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TSnap::CascGraphTime
PNGraph CascGraphTime(PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W)
Takes as input the column names of the PTable P as C1, C2,C3 and C4 and returns a directed graph of W...
Definition: casc.cpp:59
TInt
Definition: dt.h:1137
TSnap::CascGraph
PNGraph CascGraph(PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W, bool SortParam)
Takes as input the column names of the PTable P as C1, C2, C3 and C4 and returns a directed graph of ...
Definition: casc.cpp:126
THashSet::Len
int Len() const
Definition: shash.h:1121
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
TSnap::CascFindMP
void CascFindMP(PNGraph Graph, PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, TVec< TIntV > &TopCascVV)
Parallel implementaion of CascFind takes as input a directed graph and returns all the top cascades i...
Definition: casc.cpp:200
TStr
Definition: dt.h:412
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TSnapQueue::Push
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:214
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TSnapQueue
Fast Queue used by the TBreathFS (uses memcpy to move objects TVal around).
Definition: gbase.h:158
TSnapQueue::Top
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:209
TPt
Definition: bd.h:196
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TNGraph::TNodeI::GetOutNId
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430