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
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
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
TInt::Val
int Val
Definition: dt.h:1136
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
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
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
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:198
TSnapQueue::Empty
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:186
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
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
TNGraph::IsEdge
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
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:1134
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::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
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:201
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
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: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:412
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430