SNAP Library 3.0, User Reference  2016-07-20 17:56:49
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  int BIdx = index;
40  for(int i = BIdx; i < Source.Len(); i++) {
41  int InIdx = MapV.GetVal(i).Val;
42  if (InIdx == OIdx) {continue;}
43  int InSource = P->GetIntValAtRowIdx(SIdx,InIdx).Val;
44  int InStart = P->GetIntValAtRowIdx(StIdx,InIdx).Val;
45  if (InSource != ODest) { break;}
46  if (InStart >= (ODur + OStart) && InStart - (ODur + OStart) <= W.Val) {
47  if (!Graph->IsEdge(OIdx,InIdx)) {
48  Graph->AddEdge(OIdx,InIdx);
49  }
50  }
51  }
52  }
53  return Graph;
54 }
55 
56 PNGraph CascGraphTime(PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,const TInt W) {
57  // Attribute to Int mapping
58  TInt SIdx = P->GetColIdx(C1); //Source
59  TInt DIdx = P->GetColIdx(C2); //Dest
60  TInt StIdx = P->GetColIdx(C3); //Start
61  TInt DuIdx = P->GetColIdx(C4); //Duration
62  TIntV MapV;
63  TStrV SortBy;
64  SortBy.Add(C3);
65  P->Order(SortBy);
66  TIntV Start;
67  P->ReadIntCol(C3,Start);
68  PNGraph Graph = TNGraph::New();
69  //Add Nodes
70  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
71  Graph->AddNode(RI.GetRowIdx().Val);
72  MapV.Add(RI.GetRowIdx());
73  }
74  //Add Edges
75  for (TRowIterator OI = P->BegRI(); OI < P->EndRI(); OI++) {
76  int OIdx = OI.GetRowIdx().Val;
77  int ODest = P->GetIntValAtRowIdx(DIdx,OIdx).Val;
78  int OStart = P->GetIntValAtRowIdx(StIdx,OIdx).Val;
79  int ODur = P->GetIntValAtRowIdx(DuIdx,OIdx).Val;
80  // Inline binary Search
81  int val = OStart + ODur;
82  int lo = 0;
83  int hi = Start.Len() - 1;
84  int index = -1;
85  if (val >= Start.GetVal(hi)) { val = Start.GetVal(hi);}
86  while (hi >= lo) {
87  int mid = lo + (hi - lo)/2;
88  if (Start.GetVal(mid) > val) {
89  if ((mid-1) >= lo && Start.GetVal(mid - 1) < val) {
90  index = mid - 1;break;
91  }
92  hi = mid - 1;
93  }
94  else if (Start.GetVal(mid) < val) {
95  if (mid + 1 <= hi && Start.GetVal(mid + 1) > val) {
96  index = mid;break;
97  }
98  lo = mid + 1;
99  }
100  else { index = mid; hi = mid - 1;}
101  }
102  // End of binary Search
103  int BIdx = index;
104  for(int i = BIdx; i < Start.Len(); i++) {
105  int InIdx = MapV.GetVal(i).Val;
106  if (InIdx == OIdx) {continue;}
107  int InSource = P->GetIntValAtRowIdx(SIdx,InIdx).Val;
108  int InStart = P->GetIntValAtRowIdx(StIdx,InIdx).Val;
109  if (InStart - (ODur + OStart) > W.Val) { break;}
110  if (InSource == ODest && InStart >= (ODur + OStart)) {
111  if (!Graph->IsEdge(OIdx,InIdx)) {
112  Graph->AddEdge(OIdx,InIdx);
113  }
114  }
115  }
116  }
117  return Graph;
118 }
119 
120 PNGraph CascGraph(PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,const TInt W,bool SortParam) {
121  if (SortParam) {
122  return CascGraphSource(P, C1, C2, C3, C4, W);
123  }
124  else {
125  return CascGraphTime(P, C1, C2, C3, C4, W);
126  }
127 }
128 
129 void CascFind(PNGraph Graph,PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,TVec<TIntV> &TopCascVV,bool Print) {
130  // Attribute to Int mapping
131  TInt SIdx = P->GetColIdx(C1);
132  TInt DIdx = P->GetColIdx(C2);
133  TInt StIdx = P->GetColIdx(C3);
134  TInt DuIdx = P->GetColIdx(C4);
135  TIntV MapV, PhyV;
136  TStrV SortBy;
137  SortBy.Add(C3);
138  P->Order(SortBy);
139  int count = 0;
140  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
141  MapV.Add(RI.GetRowIdx());
142  PhyV.Add(count++);
143  }
144  // After sort attach with each row a rank helpful for sorting
145  P->StoreIntCol("Physical",PhyV);
146  TInt PIdx = P->GetColIdx("Physical");
147  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
148  // Check for top cascades
149  if (NI.GetInDeg() != 0) { continue;}
150  TIntV CurCasc;
151  TSnapQueue<TInt> EventQ;
152  THashSet<TInt> VisitedH;
153  TInt NId = NI.GetId();
154  EventQ.Push(NId);
155  VisitedH.AddKey(NId);
156  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,NId));
157  while (! EventQ.Empty()) {
158  TNGraph::TNodeI CNI = Graph->GetNI(EventQ.Top().Val); //Get Current Node
159  EventQ.Pop();
160  // Go over the outdegree nodes of the currernt node
161  for (int e = 0; e < CNI.GetOutDeg(); e++) {
162  TInt CId = CNI.GetOutNId(e);
163  if ( !VisitedH.IsKey(CId)) {
164  EventQ.Push(CId);
165  VisitedH.AddKey(CId);
166  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,CId));
167  }
168  }
169  }
170  CurCasc.Sort();
171  TIntV ToAddV;
172  if (Print && VisitedH.Len() > 1) {
173  printf("__casacade__\t%d\n",VisitedH.Len());
174  }
175  for (TIntV::TIter VI = CurCasc.BegI(); VI < CurCasc.EndI(); VI++) {
176  ToAddV.Add(MapV.GetVal(VI->Val));
177  if (Print && VisitedH.Len() > 1) {
178  int PIdx = MapV.GetVal(VI->Val).Val;
179  int PSource = P->GetIntValAtRowIdx(SIdx,PIdx).Val;
180  int PDest = P->GetIntValAtRowIdx(DIdx,PIdx).Val;
181  int PStart = P->GetIntValAtRowIdx(StIdx,PIdx).Val;
182  int PDur = P->GetIntValAtRowIdx(DuIdx,PIdx).Val;
183  printf("%d\t%d\t%d\t%d\t%d\n",PIdx,PSource,PDest,PStart,PDur);
184  }
185  }
186  if (ToAddV.Len() > 1) {
187  TopCascVV.Add(ToAddV);
188  }
189  }
190  return;
191 }
192 
193 #ifdef USE_OPENMP
194 void CascFindMP(PNGraph Graph,PTable P,const TStr C1,const TStr C2,const TStr C3,const TStr C4,TVec<TIntV> &TopCascVV) {
195  // Attribute to Int mapping
196  TInt SIdx = P->GetColIdx(C1);
197  TInt DIdx = P->GetColIdx(C2);
198  TInt StIdx = P->GetColIdx(C3);
199  TInt DuIdx = P->GetColIdx(C4);
200  TIntV MapV, PhyV;
201  TStrV SortBy;
202  SortBy.Add(C3);
203  P->Order(SortBy);
204  int count = 0;
205  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
206  MapV.Add(RI.GetRowIdx());
207  PhyV.Add(count++);
208  }
209  P->StoreIntCol("Physical",PhyV);
210  TInt PIdx = P->GetColIdx("Physical");
211  TIntV GNodeV;
212  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
213  if (NI.GetInDeg() == 0) { GNodeV.Add(NI.GetId()); }
214  }
215  TVec<TIntV> ThTopCascVV; // for each thread
216  #pragma omp parallel private(ThTopCascVV) num_threads(10)
217  {
218  #pragma omp for schedule(dynamic,1000)
219  for (int i = 0; i < GNodeV.Len(); i++) {
220  TIntV CurCasc;
221  TSnapQueue<TInt> EventQ;
222  THashSet<TInt> VisitedH;
223  TInt NId = GNodeV[i];
224  EventQ.Push(NId);
225  VisitedH.AddKey(NId);
226  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,NId));
227  while (! EventQ.Empty()) {
228  TNGraph::TNodeI CNI = Graph->GetNI(EventQ.Top().Val); //Get Current Node
229  EventQ.Pop();
230  // Go over the outdegree nodes of the currernt node
231  for (int e = 0; e < CNI.GetOutDeg(); e++) {
232  TInt CId = CNI.GetOutNId(e);
233  if ( !VisitedH.IsKey(CId)) {
234  EventQ.Push(CId);
235  VisitedH.AddKey(CId);
236  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,CId));
237  }
238  }
239  }
240  CurCasc.Sort();
241  TIntV ToAddV;
242  for (TIntV::TIter VI = CurCasc.BegI(); VI < CurCasc.EndI(); VI++) {
243  ToAddV.Add(MapV.GetVal(VI->Val));
244  }
245  if (ToAddV.Len() > 1) { ThTopCascVV.Add(ToAddV);}
246  }
247  #pragma omp critical
248  {
249  for (int j = 0; j < ThTopCascVV.Len(); j++) {
250  TopCascVV.Add(ThTopCascVV[j]);
251  }
252  }
253  }
254  return;
255 }
256 #endif // USE_OPENMP
257 } //Namespace TSnap
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:567
TNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
TInt::Val
int Val
Definition: dt.h:1046
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:425
TNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
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:129
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
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:339
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:621
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs 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:56
TInt
Definition: dt.h:1044
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:120
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:481
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:362
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:194
TStr
Definition: dt.h:412
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:565
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:339
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:574
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:372