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.

References TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), TMaxPriorityQueue< TVal >::GetMaxPriority(), TNGraph::TNodeI::GetOutDeg(), TMaxPriorityQueue< TVal >::GetPriorities(), TMaxPriorityQueue< TVal >::GetPriority(), TMaxPriorityQueue< TVal >::Insert(), TMaxPriorityQueue< TVal >::IsEmpty(), TMaxPriorityQueue< TVal >::PopMax(), TMaxPriorityQueue< TVal >::SetPriority(), and WallClockTime().

Referenced by TSnap::GetPersonalizedPageRankBidirectional().

                                                             {
    double startTime = WallClockTime();
    TMaxPriorityQueue<TInt> nodesByResidual;
    nodesByResidual.Insert(TargetNId, 1.0f);
    while (!nodesByResidual.IsEmpty() &&
           WallClockTime() - startTime < ForwardSecondsRMaxRatio * nodesByResidual.GetMaxPriority()) {
      float vPriority = nodesByResidual.GetMaxPriority();
      int vId = nodesByResidual.PopMax();
      ResultEstimates(vId) = ResultEstimates(vId) + JumpProb * vPriority;
      //printf("set estimate(%d) to %g\n", vId, double(ResultEstimates(vId)));
      TNGraph::TNodeI v = Graph->GetNI(vId);
      for (int i = 0; i < v.GetInDeg(); i++) {
        int uId = v.GetInNId(i);
        TNGraph::TNodeI u = Graph->GetNI(uId);
        float residualChange = (1.0 - JumpProb) * vPriority / u.GetOutDeg();
        nodesByResidual.SetPriority(uId, nodesByResidual.GetPriority(uId) + residualChange);
        //printf("set priority(%d) to %g\n", uId, double(nodesByResidual.GetPriority(uId)));
      }
    }
    
    // Copy residuals from nodesByResidual to ResultResiduals
    nodesByResidual.GetPriorities(ResultResiduals);
    ResultMaxResidual = nodesByResidual.IsEmpty() ? 0.0f : nodesByResidual.GetMaxPriority();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

double anonymous_namespace{randwalk.h}::WallClockTime

(

)

Definition at line 17 of file randwalk.h.

Referenced by ApproxContributionsBalanced(), and TSnap::GetPersonalizedPageRankBidirectional().

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

Here is the caller graph for this function: