SNAP Library 4.1, User Reference  2018-07-26 16:30:42
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
biasedrandomwalk.h File Reference

Go to the source code of this file.

Typedefs

typedef TNodeEDatNet
< TIntIntVFltVPrH, TFlt
TWNet
 
typedef TPt< TWNetPWNet
 

Functions

void PreprocessTransitionProbs (PWNet &InNet, const double &ParamP, const double &ParamQ, const bool &verbose)
 Preprocesses transition probabilities for random walks. Has to be called once before SimulateWalk calls. More...
 
void SimulateWalk (PWNet &InNet, int64 StartNId, const int &WalkLen, TRnd &Rnd, TIntV &Walk)
 Simulates one walk and writes it into Walk vector. More...
 
int64 PredictMemoryRequirements (PWNet &InNet)
 

Typedef Documentation

typedef TPt<TWNet> PWNet

Definition at line 5 of file biasedrandomwalk.h.

Definition at line 4 of file biasedrandomwalk.h.

Function Documentation

int64 PredictMemoryRequirements ( PWNet InNet)

Definition at line 119 of file biasedrandomwalk.cpp.

119  {
120  int64 MemNeeded = 0;
121  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
122  for (int64 i = 0; i < NI.GetOutDeg(); i++) {
123  TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));
124  MemNeeded += CurrI.GetOutDeg()*(sizeof(TInt) + sizeof(TFlt));
125  }
126  }
127  return MemNeeded;
128 }
Definition: dt.h:1383
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:559
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:537
Definition: dt.h:1134
long long int64
Definition: bd.h:27
void PreprocessTransitionProbs ( PWNet InNet,
const double &  ParamP,
const double &  ParamQ,
const bool &  verbose 
)

Preprocesses transition probabilities for random walks. Has to be called once before SimulateWalk calls.

Definition at line 97 of file biasedrandomwalk.cpp.

97  {
98  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
99  InNet->SetNDat(NI.GetId(),TIntIntVFltVPrH());
100  }
101  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
102  for (int64 i = 0; i < NI.GetOutDeg(); i++) { //allocating space in advance to avoid issues with multithreading
103  TWNet::TNodeI CurrI = InNet->GetNI(NI.GetNbrNId(i));
104  CurrI.GetDat().AddDat(NI.GetId(),TPair<TIntV,TFltV>(TIntV(CurrI.GetOutDeg()),TFltV(CurrI.GetOutDeg())));
105  }
106  }
107  int64 NCnt = 0;
108  TIntV NIds;
109  for (TWNet::TNodeI NI = InNet->BegNI(); NI < InNet->EndNI(); NI++) {
110  NIds.Add(NI.GetId());
111  }
112 #pragma omp parallel for schedule(dynamic)
113  for (int64 i = 0; i < NIds.Len(); i++) {
114  PreprocessNode(InNet, ParamP, ParamQ, InNet->GetNI(NIds[i]), NCnt, Verbose);
115  }
116  if(Verbose){ printf("\n"); }
117 }
THash< TInt, TIntVFltVPr > TIntIntVFltVPrH
Definition: hash.h:625
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:559
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:537
Definition: ds.h:32
TVec< TFlt > TFltV
Definition: ds.h:1596
long long int64
Definition: bd.h:27
void PreprocessNode(PWNet &InNet, const double &ParamP, const double &ParamQ, TWNet::TNodeI NI, int64 &NCnt, const bool &Verbose)
TVec< TInt > TIntV
Definition: ds.h:1594
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
const TNodeData & GetDat() const
Definition: network.h:581
void SimulateWalk ( PWNet InNet,
int64  StartNId,
const int &  WalkLen,
TRnd Rnd,
TIntV Walk 
)

Simulates one walk and writes it into Walk vector.

Definition at line 131 of file biasedrandomwalk.cpp.

131  {
132  WalkV.Add(StartNId);
133  if (WalkLen == 1) { return; }
134  if (InNet->GetNI(StartNId).GetOutDeg() == 0) { return; }
135  WalkV.Add(InNet->GetNI(StartNId).GetNbrNId(Rnd.GetUniDevInt(InNet->GetNI(StartNId).GetOutDeg())));
136  while (WalkV.Len() < WalkLen) {
137  int64 Dst = WalkV.Last();
138  int64 Src = WalkV.LastLast();
139  if (InNet->GetNI(Dst).GetOutDeg() == 0) { return; }
140  int64 Next = AliasDrawInt(InNet->GetNDat(Dst).GetDat(Src),Rnd);
141  WalkV.Add(InNet->GetNI(Dst).GetNbrNId(Next));
142  }
143 }
int64 AliasDrawInt(TIntVFltVPr &NTTable, TRnd &Rnd)
long long int64
Definition: bd.h:27
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39