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
TNetInfBs Class Reference

#include <cascnetinf.h>

Public Member Functions

 TNetInfBs ()
 
 TNetInfBs (bool bo, bool cgt)
 
 TNetInfBs (TSIn &SIn)
 
void Save (TSOut &SOut) const
 
void LoadCascadesTxt (TSIn &SIn, const int &Model, const double &alpha)
 
void LoadGroundTruthTxt (TSIn &SIn)
 
void AddGroundTruth (PNGraph &gt)
 
void AddCasc (const TStr &CascStr, const int &Model=0, const double &alpha=1.0)
 
void AddCasc (const TCascade &Cascade)
 
void GenCascade (TCascade &C, const int &TModel, const double &window, TIntPrIntH &EdgesUsed, const double &delta, const double &std_waiting_time=0, const double &std_beta=0)
 
TCascadeGetCasc (int c)
 
int GetCascs ()
 
int GetNodes ()
 
void AddNodeNm (const int &NId, const TNodeInfo &Info)
 
TStr GetNodeNm (const int &NId) const
 
TNodeInfo GetNodeInfo (const int &NId) const
 
bool IsNodeNm (const int &NId) const
 
void Init ()
 
double GetAllCascProb (const int &EdgeN1, const int &EdgeN2)
 
TIntPr GetBestEdge (double &CurProb, double &LastGain, bool &msort, int &attempts)
 
double GetBound (const TIntPr &Edge, double &CurProb)
 
void GreedyOpt (const int &MxEdges)
 
void SavePajek (const TStr &OutFNm)
 
void SavePlaneTextNet (const TStr &OutFNm)
 
void SaveEdgeInfo (const TStr &OutFNm)
 
void SaveObjInfo (const TStr &OutFNm)
 
void SaveGroundTruth (const TStr &OutFNm)
 
void SaveCascades (const TStr &OutFNm)
 

Public Attributes

TVec< TCascadeCascV
 
THash< TInt, TNodeInfoNodeNmH
 
THash< TIntPr, TEdgeInfoEdgeInfoH
 
TVec< TPair< TFlt, TIntPr > > EdgeGainV
 
THash< TIntPr, TIntVCascPerEdge
 
PNGraph Graph
 
PNGraph GroundTruth
 
bool BoundOn
 
bool CompareGroundTruth
 
TFltPrV PrecisionRecall
 
TIntPrFltH Alphas
 
TIntPrFltH Betas
 

Detailed Description

Definition at line 82 of file cascnetinf.h.

Constructor & Destructor Documentation

TNetInfBs::TNetInfBs ( )
inline

Definition at line 97 of file cascnetinf.h.

97 { BoundOn = false; CompareGroundTruth=false; }
bool BoundOn
Definition: cascnetinf.h:91
bool CompareGroundTruth
Definition: cascnetinf.h:91
TNetInfBs::TNetInfBs ( bool  bo,
bool  cgt 
)
inline

Definition at line 98 of file cascnetinf.h.

98 { BoundOn=bo; CompareGroundTruth=cgt; }
bool BoundOn
Definition: cascnetinf.h:91
bool CompareGroundTruth
Definition: cascnetinf.h:91
TNetInfBs::TNetInfBs ( TSIn SIn)
inline

Definition at line 99 of file cascnetinf.h.

99 : CascV(SIn), NodeNmH(SIn) { }
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
TVec< TCascade > CascV
Definition: cascnetinf.h:84

Member Function Documentation

void TNetInfBs::AddCasc ( const TStr CascStr,
const int &  Model = 0,
const double &  alpha = 1.0 
)

Definition at line 98 of file cascnetinf.cpp.

98  {
99  TStrV NIdV; CascStr.SplitOnAllCh(',', NIdV);
100  TCascade C(alpha, Model);
101  for (int i = 0; i < NIdV.Len(); i+=2) {
102  int NId;
103  double Tm;
104  NId = NIdV[i].GetInt();
105  Tm = NIdV[i+1].GetFlt();
106  GetNodeInfo(NId).Vol = GetNodeInfo(NId).Vol + 1;
107  C.Add(NId, Tm);
108  }
109  C.Sort();
110  CascV.Add(C);
111 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TNodeInfo GetNodeInfo(const int &NId) const
Definition: cascnetinf.h:117
TVec< TCascade > CascV
Definition: cascnetinf.h:84
void SplitOnAllCh(const char &SplitCh, TStrV &StrV, const bool &SkipEmpty=true) const
Definition: dt.cpp:926
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
void TNetInfBs::AddCasc ( const TCascade Cascade)
inline

Definition at line 108 of file cascnetinf.h.

108 { CascV.Add(Cascade); }
TVec< TCascade > CascV
Definition: cascnetinf.h:84
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void TNetInfBs::AddGroundTruth ( PNGraph gt)
inline

Definition at line 105 of file cascnetinf.h.

105 { GroundTruth = gt; }
PNGraph GroundTruth
Definition: cascnetinf.h:90
void TNetInfBs::AddNodeNm ( const int &  NId,
const TNodeInfo Info 
)
inline

Definition at line 115 of file cascnetinf.h.

115 { NodeNmH.AddDat(NId, Info); }
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
void TNetInfBs::GenCascade ( TCascade C,
const int &  TModel,
const double &  window,
TIntPrIntH EdgesUsed,
const double &  delta,
const double &  std_waiting_time = 0,
const double &  std_beta = 0 
)

Definition at line 113 of file cascnetinf.cpp.

114  {
115  TIntFltH InfectedNIdH; TIntH InfectedBy;
116  double GlobalTime; int StartNId;
117  double alpha, beta;
118 
119  if (GroundTruth->GetNodes() == 0)
120  return;
121 
122  while (C.Len() < 2) {
123  C.Clr();
124  InfectedNIdH.Clr();
125  InfectedBy.Clr();
126  GlobalTime = 0;
127 
128  StartNId = GroundTruth->GetRndNId();
129  InfectedNIdH.AddDat(StartNId) = GlobalTime;
130 
131  while (true) {
132  // sort by time & get the oldest node that did not run infection
133  InfectedNIdH.SortByDat(true);
134  const int& NId = InfectedNIdH.BegI().GetKey();
135  GlobalTime = InfectedNIdH.BegI().GetDat();
136 
137  // all the nodes has run infection
138  if (GlobalTime >= window)
139  break;
140 
141  // add current oldest node to the network and set its time
142  C.Add(NId, GlobalTime);
143 
144  // run infection from the current oldest node
145  const TNGraph::TNodeI NI = GroundTruth->GetNI(NId);
146  for (int e = 0; e < NI.GetOutDeg(); e++) {
147  const int DstNId = NI.GetOutNId(e);
148 
149  beta = Betas.GetDat(TIntPr(NId, DstNId));
150 
151  // flip biased coin (set by beta)
152  if (TInt::Rnd.GetUniDev() > beta+std_beta*TFlt::Rnd.GetNrmDev())
153  continue;
154 
155  alpha = Alphas.GetDat(TIntPr(NId, DstNId));
156 
157  // not infecting the parent
158  if (InfectedBy.IsKey(NId) && InfectedBy.GetDat(NId).Val == DstNId)
159  continue;
160 
161  double sigmaT;
162  switch (TModel) {
163  case 0:
164  // exponential with alpha parameter
165  sigmaT = TInt::Rnd.GetExpDev(alpha);
166  break;
167  case 1:
168  // power-law with alpha parameter
169  sigmaT = TInt::Rnd.GetPowerDev(alpha);
170  while (sigmaT < delta) { sigmaT = TInt::Rnd.GetPowerDev(alpha); }
171  break;
172  case 2:
173  // rayleigh with alpha parameter
174  sigmaT = TInt::Rnd.GetRayleigh(1/sqrt(alpha));
175  break;
176  default:
177  sigmaT = 1;
178  break;
179  }
180 
181  // avoid negative time diffs in case of noise
182  if (std_waiting_time > 0)
183  sigmaT = TFlt::GetMx(0.0, sigmaT + std_waiting_time*TFlt::Rnd.GetNrmDev());
184 
185  double t1 = GlobalTime + sigmaT;
186 
187  if (InfectedNIdH.IsKey(DstNId)) {
188  double t2 = InfectedNIdH.GetDat(DstNId);
189  if (t2 > t1 && t2 != window) {
190  InfectedNIdH.GetDat(DstNId) = t1;
191  InfectedBy.GetDat(DstNId) = NId;
192  }
193  } else {
194  InfectedNIdH.AddDat(DstNId) = t1;
195  InfectedBy.AddDat(DstNId) = NId;
196  }
197  }
198 
199  // we cannot delete key (otherwise, we cannot sort), so we assign a big time (window cut-off)
200  InfectedNIdH.GetDat(NId) = window;
201  }
202 
203  }
204 
205  C.Sort();
206 
207  for (TIntH::TIter EI = InfectedBy.BegI(); EI < InfectedBy.EndI(); EI++) {
208  TIntPr Edge(EI.GetDat().Val, EI.GetKey().Val);
209 
210  if (!EdgesUsed.IsKey(Edge)) EdgesUsed.AddDat(Edge) = 0;
211 
212  EdgesUsed.GetDat(Edge) += 1;
213  }
214 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TIntPrFltH Alphas
Definition: cascnetinf.h:94
int Val
Definition: dt.h:1046
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
static double GetMx(const double &Flt1, const double &Flt2)
Definition: dt.h:1351
int Len() const
Definition: cascdynetinf.h:97
TIter BegI() const
Definition: hash.h:171
TModel
Definition: cascdynetinf.h:7
double GetRayleigh(const double &Sigma)
Definition: dt.h:50
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TIter EndI() const
Definition: hash.h:176
static TRnd Rnd
Definition: dt.h:1053
const TKey & GetKey() const
Definition: hash.h:71
const TDat & GetDat() const
Definition: hash.h:72
double GetExpDev()
Definition: dt.cpp:83
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:523
void Clr()
Definition: cascdynetinf.h:95
PNGraph GroundTruth
Definition: cascnetinf.h:90
Definition: ds.h:32
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:362
TIntPrFltH Betas
Definition: cascnetinf.h:94
void Add(const int &NId, const double &HitTm)
Definition: cascdynetinf.h:107
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:319
bool IsKey(const TKey &Key) const
Definition: hash.h:216
void Sort()
Definition: cascdynetinf.h:110
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:372
double GetPowerDev(const double &AlphaSlope)
Definition: dt.h:47
static TRnd Rnd
Definition: dt.h:1303
void SortByDat(const bool &Asc=true)
Definition: hash.h:250
double TNetInfBs::GetAllCascProb ( const int &  EdgeN1,
const int &  EdgeN2 
)

Definition at line 255 of file cascnetinf.cpp.

255  {
256  double P = 0.0;
257 
258  if (EdgeN1==-1 && EdgeN2==-1) {
259  for (int c = 0; c < CascV.Len(); c++) {
260  P += CascV[c].UpdateProb(EdgeN1, EdgeN2, false); } // initial log-likelihood
261  return P;
262  }
263 
264  TIntV &CascsEdge = CascPerEdge.GetDat(TIntPr(EdgeN1, EdgeN2)); // only check cascades that contain the edge
265 
266  for (int c = 0; c < CascsEdge.Len(); c++) {
267  P += (CascV[CascsEdge[c]].UpdateProb(EdgeN1, EdgeN2, false) - CascV[CascsEdge[c]].CurProb); } // marginal gain
268  return P;
269 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash< TIntPr, TIntV > CascPerEdge
Definition: cascnetinf.h:89
TVec< TCascade > CascV
Definition: cascnetinf.h:84
TIntPr TNetInfBs::GetBestEdge ( double &  CurProb,
double &  LastGain,
bool &  msort,
int &  attempts 
)

Definition at line 271 of file cascnetinf.cpp.

271  {
272  TIntPr BestE;
273  TVec<TInt> KeysV;
274  TVec<TPair<TFlt, TIntPr> > EdgeGainCopyToSortV;
275  TIntV EdgeZero;
276  double BestGain = TFlt::Mn;
277  int BestGainIndex = -1;
278 
279  if (msort) {
280  for (int i=0; i<TMath::Mn(attempts-1, EdgeGainV.Len()); i++)
281  EdgeGainCopyToSortV.Add(EdgeGainV[i]);
282 
283  // printf("Sorting sublist of size %d of marginal gains!\n", EdgeGainCopyToSortV.Len());
284 
285  // sort this list
286  EdgeGainCopyToSortV.Sort(false);
287 
288  // printf("Sublist sorted!\n");
289 
290  // clever way of resorting without need to copy (google interview question! :-))
291  for (int i=0, ii=0, j=0; ii < EdgeGainCopyToSortV.Len(); j++) {
292  if ( (i+EdgeGainCopyToSortV.Len() < EdgeGainV.Len()) && (EdgeGainCopyToSortV[ii].Val1 < EdgeGainV[i+EdgeGainCopyToSortV.Len()].Val1) ) {
293  EdgeGainV[j] = EdgeGainV[i+EdgeGainCopyToSortV.Len()];
294  i++;
295  } else {
296  EdgeGainV[j] = EdgeGainCopyToSortV[ii];
297  ii++;
298  }
299  }
300  }
301 
302  attempts = 0;
303 
304  for (int e = 0; e < EdgeGainV.Len(); e++) {
305  const TIntPr& Edge = EdgeGainV[e].Val2;
306  if (Graph->IsEdge(Edge.Val1, Edge.Val2)) { continue; } // if edge was already included in the graph
307 
308  const double EProb = GetAllCascProb(Edge.Val1, Edge.Val2);
309  EdgeGainV[e].Val1 = EProb; // update marginal gain
310  if (BestGain < EProb) {
311  BestGain = EProb;
312  BestGainIndex = e;
313  BestE = Edge;
314  }
315 
316  // if we only update one weight, we don't need to sort the list
317  attempts++;
318 
319  // keep track of zero edges after sorting once the full list
320  if (!Graph->IsEdge(Edge.Val1, Edge.Val2) && Graph->GetEdges() > 1) {
321  if (EProb == 0)
322  EdgeZero.Add(e);
323  }
324 
325  // lazy evaluation
326  if (e+1 == EdgeGainV.Len() || BestGain >= EdgeGainV[e+1].Val1) {
327  CurProb += BestGain;
328 
329  if (BestGain == 0)
330  return TIntPr(-1, -1);
331 
332  EdgeGainV.Del(BestGainIndex);
333 
334  // we know the edges in 0 will be in sorted order, so we start from the biggest
335  for (int i=EdgeZero.Len()-1; i>=0; i--) {
336  if (EdgeZero[i] > BestGainIndex)
337  EdgeGainV.Del(EdgeZero[i]-1);
338  else
339  EdgeGainV.Del(EdgeZero[i]);
340  }
341 
342  if (EdgeZero.Len() > 2) { attempts -= (EdgeZero.Len()-1); }
343 
344  msort = (attempts > 1);
345 
346  LastGain = BestGain;
347 
348  return BestE;
349  }
350  }
351 
352  printf("Edges exhausted!\n");
353  return TIntPr(-1, -1);
354 }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
PNGraph Graph
Definition: cascnetinf.h:90
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec< TPair< TFlt, TIntPr > > EdgeGainV
Definition: cascnetinf.h:87
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
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
Definition: ds.h:32
double GetAllCascProb(const int &EdgeN1, const int &EdgeN2)
Definition: cascnetinf.cpp:255
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
static const double Mn
Definition: dt.h:1297
double TNetInfBs::GetBound ( const TIntPr Edge,
double &  CurProb 
)

Definition at line 356 of file cascnetinf.cpp.

356  {
357  double Bound = 0;
358  TFltV Bounds;
359 
360  // bound could be computed faster (using lazy evaluation, as in the optimization procedure)
361  for (int e=0; e < EdgeGainV.Len(); e++) {
362  const TIntPr& EE = EdgeGainV[e].Val2;
363  if (EE != Edge && !Graph->IsEdge(EE.Val1, EE.Val2)) {
364  const double EProb = GetAllCascProb(EE.Val1, EE.Val2);
365  if (EProb > CurProb) Bounds.Add(EProb - CurProb); }
366  }
367 
368  Bounds.Sort(false);
369  for (int i=0; i<Graph->GetEdges() && i<Bounds.Len(); i++) Bound += Bounds[i];
370 
371  return Bound;
372 }
PNGraph Graph
Definition: cascnetinf.h:90
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec< TPair< TFlt, TIntPr > > EdgeGainV
Definition: cascnetinf.h:87
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
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
Definition: ds.h:32
double GetAllCascProb(const int &EdgeN1, const int &EdgeN2)
Definition: cascnetinf.cpp:255
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TCascade& TNetInfBs::GetCasc ( int  c)
inline

Definition at line 111 of file cascnetinf.h.

111 { return CascV[c]; }
TVec< TCascade > CascV
Definition: cascnetinf.h:84
int TNetInfBs::GetCascs ( )
inline

Definition at line 112 of file cascnetinf.h.

112 { return CascV.Len(); }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec< TCascade > CascV
Definition: cascnetinf.h:84
TNodeInfo TNetInfBs::GetNodeInfo ( const int &  NId) const
inline

Definition at line 117 of file cascnetinf.h.

117 { return NodeNmH.GetDat(NId); }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
TStr TNetInfBs::GetNodeNm ( const int &  NId) const
inline

Definition at line 116 of file cascnetinf.h.

116 { return NodeNmH.GetDat(NId).Name; }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
int TNetInfBs::GetNodes ( )
inline

Definition at line 114 of file cascnetinf.h.

114 { return Graph->GetNodes(); }
PNGraph Graph
Definition: cascnetinf.h:90
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
void TNetInfBs::GreedyOpt ( const int &  MxEdges)

Definition at line 374 of file cascnetinf.cpp.

374  {
375  double CurProb = GetAllCascProb(-1, -1);
376  double LastGain = TFlt::Mx;
377  int attempts = 0;
378  bool msort = false;
379 
380  for (int k = 0; k < MxEdges && EdgeGainV.Len() > 0; k++) {
381  const TIntPr BestE = GetBestEdge(CurProb, LastGain, msort, attempts);
382  if (BestE == TIntPr(-1, -1)) // if we cannot add more edges, we stop
383  break;
384 
385  if (CompareGroundTruth) {
386  double precision = 0, recall = 0;
387  if (PrecisionRecall.Len() > 1) {
388  precision = PrecisionRecall[PrecisionRecall.Len()-1].Val2.Val;
389  recall = PrecisionRecall[PrecisionRecall.Len()-1].Val1.Val;
390  }
391  if (GroundTruth->IsEdge(BestE.Val1, BestE.Val2)) {
392  recall++;
393  } else {
394  precision++;
395  }
396 
397  PrecisionRecall.Add(TPair<TFlt, TFlt>(recall, precision));
398  }
399 
400  Graph->AddEdge(BestE.Val1, BestE.Val2); // add edge to network
401 
402 
403  // localized update!
404  TIntV &CascsEdge = CascPerEdge.GetDat(BestE); // only check cascades that contain the edge
405  for (int c = 0; c < CascsEdge.Len(); c++) {
406  CascV[CascsEdge[c]].UpdateProb(BestE.Val1, BestE.Val2, true); // update probabilities
407  }
408 
409  // some extra info for the added edge
410  TInt Vol; TFlt AverageTimeDiff; TFltV TimeDiffs;
411  Vol = 0; AverageTimeDiff = 0;
412  for (int i=0; i< CascV.Len(); i++) {
413  if (CascV[i].IsNode(BestE.Val2) && CascV[i].GetParent(BestE.Val2) == BestE.Val1) {
414  Vol += 1; TimeDiffs.Add(CascV[i].GetTm(BestE.Val2)-CascV[i].GetTm(BestE.Val1));
415  AverageTimeDiff += TimeDiffs[TimeDiffs.Len()-1]; }
416  }
417  AverageTimeDiff /= Vol;
418  if (TimeDiffs.Len() > 0)
419  TimeDiffs.Sort();
420  else
421  TimeDiffs.Add(0);
422 
423  // compute bound only if explicitly required
424  EdgeInfoH.AddDat(BestE) = TEdgeInfo(Vol,
425  LastGain,
426  0.0,
427  TimeDiffs[(int)(TimeDiffs.Len()/2)],
428  AverageTimeDiff);
429  }
430 
431  if (CompareGroundTruth) {
432  for (int i=0; i<PrecisionRecall.Len(); i++) {
433  PrecisionRecall[i].Val2 = 1.0 - PrecisionRecall[i].Val2/(PrecisionRecall[i].Val2+PrecisionRecall[i].Val1);
434  PrecisionRecall[i].Val1 /= (double)GroundTruth->GetEdges();
435  }
436  }
437 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
PNGraph Graph
Definition: cascnetinf.h:90
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
static const double Mx
Definition: dt.h:1298
Definition: dt.h:1293
THash< TIntPr, TIntV > CascPerEdge
Definition: cascnetinf.h:89
bool CompareGroundTruth
Definition: cascnetinf.h:91
TVec< TPair< TFlt, TIntPr > > EdgeGainV
Definition: cascnetinf.h:87
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
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
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
THash< TIntPr, TEdgeInfo > EdgeInfoH
Definition: cascnetinf.h:86
Definition: dt.h:1044
PNGraph GroundTruth
Definition: cascnetinf.h:90
Definition: ds.h:32
TVec< TCascade > CascV
Definition: cascnetinf.h:84
double GetAllCascProb(const int &EdgeN1, const int &EdgeN2)
Definition: cascnetinf.cpp:255
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TFltPrV PrecisionRecall
Definition: cascnetinf.h:92
TIntPr GetBestEdge(double &CurProb, double &LastGain, bool &msort, int &attempts)
Definition: cascnetinf.cpp:271
void TNetInfBs::Init ( )

Definition at line 216 of file cascnetinf.cpp.

216  {
217  THash<TInt, TIntV> CascPN;
218  Graph = TNGraph::New();
219 
220  // reset vectors
221  EdgeGainV.Clr();
222  CascPerEdge.Clr();
224 
225  for (int c = 0; c < CascV.Len(); c++) {
226  for (int i = 0; i < CascV[c].Len(); i++) {
227  if (!Graph->IsNode(CascV[c].GetNode(i))) Graph->AddNode(CascV[c].GetNode(i));
228  if (!CascPN.IsKey(CascV[c].GetNode(i))) CascPN.AddDat(CascV[c].GetNode(i)) = TIntV();
229  CascPN.GetDat(CascV[c].GetNode(i)).Add(c);
230  }
231  CascV[c].InitProb();
232  }
233 
234  // only add edges that make sense (i.e., at least once coherent in time)
235  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
236  TIntV &Cascs = CascPN.GetDat(NI.GetId());
237  for (int c = 0; c < Cascs.Len(); c++) {
238  for (int i=0; i < CascV[Cascs[c]].Len(); i++) {
239  if (CascV[Cascs[c]].GetNode(i)==NI.GetId())
240  continue;
241 
242  if (CascV[Cascs[c]].GetTm(CascV[Cascs[c]].GetNode(i)) < CascV[Cascs[c]].GetTm(NI.GetId()) ) {
243  if (!CascPerEdge.IsKey(TIntPr(CascV[Cascs[c]].GetNode(i), NI.GetId()))) {
244  EdgeGainV.Add(TPair<TFlt, TIntPr>(TFlt::Mx, TIntPr(CascV[Cascs[c]].GetNode(i), NI.GetId())));
245  CascPerEdge.AddDat(TIntPr(CascV[Cascs[c]].GetNode(i), NI.GetId())) = TIntV();
246  }
247  // Add cascade to hash of cascades per edge (to implement localized update)
248  CascPerEdge.GetDat(TIntPr(CascV[Cascs[c]].GetNode(i), NI.GetId())).Add(Cascs[c]);
249  }
250  }
251  }
252  }
253 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
PNGraph Graph
Definition: cascnetinf.h:90
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:425
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
static const double Mx
Definition: dt.h:1298
THash< TIntPr, TIntV > CascPerEdge
Definition: cascnetinf.h:89
TVec< TPair< TFlt, TIntPr > > EdgeGainV
Definition: cascnetinf.h:87
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:477
Definition: ds.h:32
TVec< TCascade > CascV
Definition: cascnetinf.h:84
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
TVec< TInt > TIntV
Definition: ds.h:1529
bool IsKey(const TKey &Key) const
Definition: hash.h:216
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TFltPrV PrecisionRecall
Definition: cascnetinf.h:92
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
bool TNetInfBs::IsNodeNm ( const int &  NId) const
inline

Definition at line 118 of file cascnetinf.h.

118 { return NodeNmH.IsKey(NId); }
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
bool IsKey(const TKey &Key) const
Definition: hash.h:216
void TNetInfBs::LoadCascadesTxt ( TSIn SIn,
const int &  Model,
const double &  alpha 
)

Definition at line 62 of file cascnetinf.cpp.

62  {
63  TStr Line;
64  while (!SIn.Eof()) {
65  SIn.GetNextLn(Line);
66  if (Line=="") { break; }
67  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
68  AddNodeNm(NIdV[0].GetInt(), TNodeInfo(NIdV[1], 0));
69  }
70  printf("All nodes read!\n");
71  while (!SIn.Eof()) { SIn.GetNextLn(Line); AddCasc(Line, Model, alpha); }
72  printf("All cascades read!\n");
73 }
void AddNodeNm(const int &NId, const TNodeInfo &Info)
Definition: cascnetinf.h:115
virtual bool Eof()=0
void AddCasc(const TStr &CascStr, const int &Model=0, const double &alpha=1.0)
Definition: cascnetinf.cpp:98
Definition: dt.h:412
void SplitOnAllCh(const char &SplitCh, TStrV &StrV, const bool &SkipEmpty=true) const
Definition: dt.cpp:926
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
bool GetNextLn(TStr &LnStr)
Definition: fl.cpp:43
void TNetInfBs::LoadGroundTruthTxt ( TSIn SIn)

Definition at line 75 of file cascnetinf.cpp.

75  {
76  GroundTruth = TNGraph::New(); TStr Line;
77 
78  // add nodes
79  while (!SIn.Eof()) {
80  SIn.GetNextLn(Line);
81  if (Line=="") { break; }
82  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
83  GroundTruth->AddNode(NIdV[0].GetInt());
84  }
85 
86  // add edges
87  while (!SIn.Eof()) {
88  SIn.GetNextLn(Line);
89  TStrV NIdV; Line.SplitOnAllCh(',', NIdV);
90  GroundTruth->AddEdge(NIdV[0].GetInt(), NIdV[1].GetInt());
91  if (NIdV.Len()>2) { Alphas.AddDat(TIntPr(NIdV[0].GetInt(), NIdV[1].GetInt())) = NIdV[2].GetFlt(); }
92  else { Alphas.AddDat(TIntPr(NIdV[0].GetInt(), NIdV[1].GetInt())) = 1.0; }
93  }
94 
95  printf("groundtruth nodes:%d edges:%d\n", GroundTruth->GetNodes(), GroundTruth->GetEdges());
96 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TIntPrFltH Alphas
Definition: cascnetinf.h:94
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:425
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
virtual bool Eof()=0
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
PNGraph GroundTruth
Definition: cascnetinf.h:90
Definition: dt.h:412
void SplitOnAllCh(const char &SplitCh, TStrV &StrV, const bool &SkipEmpty=true) const
Definition: dt.cpp:926
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
bool GetNextLn(TStr &LnStr)
Definition: fl.cpp:43
void TNetInfBs::Save ( TSOut SOut) const
inline

Definition at line 100 of file cascnetinf.h.

100 { CascV.Save(SOut); NodeNmH.Save(SOut); }
void Save(TSOut &SOut) const
Definition: hash.h:141
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
void Save(TSOut &SOut) const
Definition: ds.h:903
TVec< TCascade > CascV
Definition: cascnetinf.h:84
void TNetInfBs::SaveCascades ( const TStr OutFNm)

Definition at line 524 of file cascnetinf.cpp.

524  {
525  TFOut FOut(OutFNm);
526 
527  // write nodes to file
528  for (TNGraph::TNodeI NI = GroundTruth->BegNI(); NI < GroundTruth->EndNI(); NI++) {
529  FOut.PutStr(TStr::Fmt("%d,%d\r\n", NI.GetId(), NI.GetId())); // nodes
530  }
531 
532  FOut.PutStr("\r\n");
533 
534  // write cascades to file
535  for (int i=0; i<CascV.Len(); i++) {
536  TCascade &C = CascV[i];
537  int j = 0;
538  for (THash<TInt, THitInfo>::TIter NI = C.NIdHitH.BegI(); NI < C.NIdHitH.EndI(); NI++, j++) {
539  if (j > 0)
540  FOut.PutStr(TStr::Fmt(",%d,%f", NI.GetDat().NId.Val, NI.GetDat().Tm.Val));
541  else
542  FOut.PutStr(TStr::Fmt("%d,%f", NI.GetDat().NId.Val, NI.GetDat().Tm.Val));
543  }
544 
545  if (C.Len() >= 1)
546  FOut.PutStr(TStr::Fmt("\r\n"));
547  }
548 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
int Len() const
Definition: cascdynetinf.h:97
TIter BegI() const
Definition: hash.h:171
Definition: fl.h:319
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash< TInt, THitInfo > NIdHitH
Definition: cascdynetinf.h:87
TIter EndI() const
Definition: hash.h:176
PNGraph GroundTruth
Definition: cascnetinf.h:90
TVec< TCascade > CascV
Definition: cascnetinf.h:84
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
Definition: hash.h:88
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
void TNetInfBs::SaveEdgeInfo ( const TStr OutFNm)

Definition at line 470 of file cascnetinf.cpp.

470  {
471  FILE *F = fopen(OutFNm.CStr(), "wt");
472 
473  fprintf(F, "src dst vol marginal_gain median_timediff average_timediff\n");
474  for (THash<TIntPr, TEdgeInfo>::TIter EI = EdgeInfoH.BegI(); EI < EdgeInfoH.EndI(); EI++) {
475  TEdgeInfo &EdgeInfo = EI.GetDat();
476  fprintf(F, "%s/%s/%d/%f/%f/%f\n",
477  NodeNmH.GetDat(EI.GetKey().Val1.Val).Name.CStr(), NodeNmH.GetDat(EI.GetKey().Val2.Val).Name.CStr(),
478  EdgeInfo.Vol.Val, EdgeInfo.MarginalGain.Val,
479  EdgeInfo.MedianTimeDiff.Val,
480  EdgeInfo.AverageTimeDiff.Val);
481  }
482  fclose(F);
483 }
TFlt MarginalGain
Definition: cascnetinf.h:65
int Val
Definition: dt.h:1046
TFlt MedianTimeDiff
Definition: cascnetinf.h:65
double Val
Definition: dt.h:1295
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
THash< TIntPr, TEdgeInfo > EdgeInfoH
Definition: cascnetinf.h:86
TFlt AverageTimeDiff
Definition: cascnetinf.h:65
TInt Vol
Definition: cascnetinf.h:64
char * CStr()
Definition: dt.h:476
void TNetInfBs::SaveGroundTruth ( const TStr OutFNm)

Definition at line 502 of file cascnetinf.cpp.

502  {
503  TFOut FOut(OutFNm);
504 
505  // write nodes to file
506  for (TNGraph::TNodeI NI = GroundTruth->BegNI(); NI < GroundTruth->EndNI(); NI++) {
507  FOut.PutStr(TStr::Fmt("%d,%d\r\n", NI.GetId(), NI.GetId())); // nodes
508  }
509 
510  FOut.PutStr("\r\n");
511 
512  // write edges to file (not allowing self loops in the network)
513  for (TNGraph::TEdgeI EI = GroundTruth->BegEI(); EI < GroundTruth->EndEI(); EI++) {
514  // not allowing self loops in the Kronecker network
515  if (EI.GetSrcNId() != EI.GetDstNId()) {
516  if (Alphas.IsKey(TIntPr(EI.GetSrcNId(), EI.GetDstNId())))
517  FOut.PutStr(TStr::Fmt("%d,%d,%f\r\n", EI.GetSrcNId(), EI.GetDstNId(), Alphas.GetDat(TIntPr(EI.GetSrcNId(), EI.GetDstNId())).Val));
518  else
519  FOut.PutStr(TStr::Fmt("%d,%d,1\r\n", EI.GetSrcNId(), EI.GetDstNId()));
520  }
521  }
522 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TIntPrFltH Alphas
Definition: cascnetinf.h:94
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:516
double Val
Definition: dt.h:1295
Definition: fl.h:319
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:514
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:386
PNGraph GroundTruth
Definition: cascnetinf.h:90
Definition: ds.h:32
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
bool IsKey(const TKey &Key) const
Definition: hash.h:216
void TNetInfBs::SaveObjInfo ( const TStr OutFNm)

Definition at line 485 of file cascnetinf.cpp.

485  {
486  TGnuPlot GnuPlot(OutFNm);
487 
488  TFltV Objective;
489 
490  for (THash<TIntPr, TEdgeInfo>::TIter EI = EdgeInfoH.BegI(); EI < EdgeInfoH.EndI(); EI++) {
491  if (Objective.Len()==0) { Objective.Add(EI.GetDat().MarginalGain);
492  } else {
493  Objective.Add(Objective[Objective.Len()-1]+EI.GetDat().MarginalGain);
494  }
495  }
496 
497  GnuPlot.AddPlot(Objective, gpwLinesPoints);
498 
499  GnuPlot.SavePng();
500 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:807
THash< TIntPr, TEdgeInfo > EdgeInfoH
Definition: cascnetinf.h:86
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void TNetInfBs::SavePajek ( const TStr OutFNm)

Definition at line 439 of file cascnetinf.cpp.

439  {
440  TIntSet NIdSet;
441  FILE *F = fopen(OutFNm.CStr(), "wt");
442  fprintf(F, "*Vertices %d\r\n", NIdSet.Len());
443  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
444  const TNodeInfo& I = NI.GetDat();
445  fprintf(F, "%d \"%s\" ic Blue x_fact %f y_fact %f\r\n", NI.GetKey().Val,
446  I.Name.CStr(), TMath::Mx<double>(log((double)I.Vol)-5,1), TMath::Mx<double>(log((double)I.Vol)-5,1));
447  }
448  fprintf(F, "*Arcs\r\n");
449  for (TNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
450  fprintf(F, "%d %d 1\r\n", EI.GetSrcNId(), EI.GetDstNId());
451  }
452  fclose(F);
453 }
PNGraph Graph
Definition: cascnetinf.h:90
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:516
TIter BegI() const
Definition: hash.h:171
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:514
TIter EndI() const
Definition: hash.h:176
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:386
int Len() const
Definition: shash.h:1121
Definition: hash.h:88
char * CStr()
Definition: dt.h:476
void TNetInfBs::SavePlaneTextNet ( const TStr OutFNm)

Definition at line 455 of file cascnetinf.cpp.

455  {
456  TIntSet NIdSet;
457  FILE *F = fopen(OutFNm.CStr(), "wt");
458  for (THash<TInt, TNodeInfo>::TIter NI = NodeNmH.BegI(); NI < NodeNmH.EndI(); NI++) {
459  fprintf(F, "%d,%d\r\n", NI.GetKey().Val, NI.GetKey().Val);
460  }
461 
462  fprintf(F, "\r\n");
463 
464  for (TNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
465  fprintf(F, "%d,%d\r\n", EI.GetSrcNId(), EI.GetDstNId());
466  }
467  fclose(F);
468 }
PNGraph Graph
Definition: cascnetinf.h:90
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:516
TIter BegI() const
Definition: hash.h:171
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:514
TIter EndI() const
Definition: hash.h:176
THash< TInt, TNodeInfo > NodeNmH
Definition: cascnetinf.h:85
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:386
Definition: hash.h:88
char * CStr()
Definition: dt.h:476

Member Data Documentation

TIntPrFltH TNetInfBs::Alphas

Definition at line 94 of file cascnetinf.h.

TIntPrFltH TNetInfBs::Betas

Definition at line 94 of file cascnetinf.h.

bool TNetInfBs::BoundOn

Definition at line 91 of file cascnetinf.h.

THash<TIntPr, TIntV> TNetInfBs::CascPerEdge

Definition at line 89 of file cascnetinf.h.

TVec<TCascade> TNetInfBs::CascV

Definition at line 84 of file cascnetinf.h.

bool TNetInfBs::CompareGroundTruth

Definition at line 91 of file cascnetinf.h.

TVec<TPair<TFlt, TIntPr> > TNetInfBs::EdgeGainV

Definition at line 87 of file cascnetinf.h.

THash<TIntPr, TEdgeInfo> TNetInfBs::EdgeInfoH

Definition at line 86 of file cascnetinf.h.

PNGraph TNetInfBs::Graph

Definition at line 90 of file cascnetinf.h.

PNGraph TNetInfBs::GroundTruth

Definition at line 90 of file cascnetinf.h.

THash<TInt, TNodeInfo> TNetInfBs::NodeNmH

Definition at line 85 of file cascnetinf.h.

TFltPrV TNetInfBs::PrecisionRecall

Definition at line 92 of file cascnetinf.h.


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