SNAP Library 4.0, User 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
anonymous_namespace{randwalk.h} Namespace Reference

Functions

double WallClockTime ()
 
template<class PGraph >
void ApproxContributionsBalanced (const PGraph &Graph, double JumpProb, int TargetNId, float ForwardSecondsRMaxRatio, TIntFltH &ResultEstimates, TIntFltH &ResultResiduals, float &ResultMaxResidual)
 

Function Documentation

template<class PGraph >
void anonymous_namespace{randwalk.h}::ApproxContributionsBalanced ( const PGraph &  Graph,
double  JumpProb,
int  TargetNId,
float  ForwardSecondsRMaxRatio,
TIntFltH ResultEstimates,
TIntFltH ResultResiduals,
float &  ResultMaxResidual 
)

Definition at line 32 of file randwalk.h.

38  {
39  double startTime = WallClockTime();
40  TMaxPriorityQueue<TInt> nodesByResidual;
41  nodesByResidual.Insert(TargetNId, 1.0f);
42  while (!nodesByResidual.IsEmpty() &&
43  WallClockTime() - startTime < ForwardSecondsRMaxRatio * nodesByResidual.GetMaxPriority()) {
44  float vPriority = nodesByResidual.GetMaxPriority();
45  int vId = nodesByResidual.PopMax();
46  ResultEstimates(vId) = ResultEstimates(vId) + JumpProb * vPriority;
47  //printf("set estimate(%d) to %g\n", vId, double(ResultEstimates(vId)));
48  TNGraph::TNodeI v = Graph->GetNI(vId);
49  for (int i = 0; i < v.GetInDeg(); i++) {
50  int uId = v.GetInNId(i);
51  TNGraph::TNodeI u = Graph->GetNI(uId);
52  float residualChange = (1.0 - JumpProb) * vPriority / u.GetOutDeg();
53  nodesByResidual.SetPriority(uId, nodesByResidual.GetPriority(uId) + residualChange);
54  //printf("set priority(%d) to %g\n", uId, double(nodesByResidual.GetPriority(uId)));
55  }
56  }
57 
58  // Copy residuals from nodesByResidual to ResultResiduals
59  nodesByResidual.GetPriorities(ResultResiduals);
60  ResultMaxResidual = nodesByResidual.IsEmpty() ? 0.0f : nodesByResidual.GetMaxPriority();
61  }
float GetPriority(const TVal &X)
Definition: priorityqueue.h:49
void GetPriorities(THash< TVal, TFlt > &Result)
Definition: priorityqueue.h:83
void SetPriority(const TVal &X, float NewPriority)
Definition: priorityqueue.h:31
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
void Insert(const TVal &X, float Priority)
Definition: priorityqueue.h:23
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:400
float GetMaxPriority()
Definition: priorityqueue.h:57
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:408
double anonymous_namespace{randwalk.h}::WallClockTime ( )

Definition at line 17 of file randwalk.h.

17  {
18  // from http://stackoverflow.com/questions/588307/c-obtaining-milliseconds-time-on-linux-clock-doesnt-seem-to-work-properl/
19  struct timeval t;
20  gettimeofday(&t, NULL);
21  return t.tv_sec + t.tv_usec / 1.0e6;
22  }