TGraphAnf< PGraph > Class Template Reference

List of all members.

Public Member Functions
	TGraphAnf (const PGraph &GraphPt, const int &Approx=32, const int &moreBits=5, const int &RndSeed=0)
uint64	GetNIdOffset (const int &NId) const
void	InitAnfBits (TAnfBitV &BitV)
void	Union (TAnfBitV &BitV1, const uint64 &NId1Offset, TAnfBitV &BitV2, const uint64 &NId2Offset) const
double	AvgLstZero (const TAnfBitV &BitV, const uint64 &NIdOffset) const
double	GetCount (const TAnfBitV &BitV, const uint64 &NIdOffset) const
void	GetNodeAnf (const int &SrcNId, TIntFltKdV &DistNbrsV, const int &MxDist, const bool &IsDir)
void	GetGraphAnf (TIntFltKdV &DistNbrsV, const int &MxDist, const bool &IsDir)

---

Detailed Description

template<class PGraph>
class TGraphAnf< PGraph >

Approximate Neighborhood Function. Implements the algorithm for computing the diameter of a given graph. The method is based on the approximate counting argument by Flajolet-Martin. For more details see C. R. Palmer, P. B. Gibbons and C. Faloutsos, ANF: A Fast and Scalable Tool for Data Mining in Massive Graphs, KDD 2002 (http://www.cs.cmu.edu/~christos/PUBLICATIONS/kdd02-anf.ps.gz) See TSnap::TestAnf() for example of how to use the class.

---

Constructor & Destructor Documentation

template<class PGraph>

TGraphAnf< PGraph >::TGraphAnf	(	const PGraph &	GraphPt,
		const int &	Approx = 32,
		const int &	moreBits = 5,
		const int &	RndSeed = 0
	)		[inline]

---

Member Function Documentation

template<class PGraph >

double TGraphAnf< PGraph >::AvgLstZero	(	const TAnfBitV &	BitV,
		const uint64 &	NIdOffset
	)		const

template<class PGraph>

double TGraphAnf< PGraph >::GetCount	(	const TAnfBitV &	BitV,
		const uint64 &	NIdOffset
	)		const [inline]

template<class PGraph >

void TGraphAnf< PGraph >::GetGraphAnf	(	TIntFltKdV &	DistNbrsV,
		const int &	MxDist,
		const bool &	IsDir
	)

Returns the number of pairs of nodes reachable in less than H hops. For example, DistNbrsV.GetDat(0) is the number of nodes in the graph, DistNbrsV.GetDat(1) is the number of nodes+edges and so on.

Parameters:

DistNbrsV	Maps between the distance H (in hops) and the number of nodes reachable in <=H hops.
MxDist	Maximum number of hops the algorithm spreads from SrcNId.
IsDir	false: consider links as undirected (drop link directions).

template<class PGraph>

uint64 TGraphAnf< PGraph >::GetNIdOffset

(

const int &

NId

)

const [inline]

template<class PGraph >

void TGraphAnf< PGraph >::GetNodeAnf	(	const int &	SrcNId,
		TIntFltKdV &	DistNbrsV,
		const int &	MxDist,
		const bool &	IsDir
	)

Returns the number of nodes reachable from SrcNId in less than H hops.

Parameters:

SrcNId	Starting node.
DistNbrsV	Maps between the distance H (in hops) and the number of nodes reachable in <=H hops.
MxDist	Maximum number of hops the algorithm spreads from SrcNId.
IsDir	false: consider links as undirected (drop link directions).

template<class PGraph >

void TGraphAnf< PGraph >::InitAnfBits

(

TAnfBitV &

BitV

)

template<class PGraph >

void TGraphAnf< PGraph >::Union	(	TAnfBitV &	BitV1,
		const uint64 &	NId1Offset,
		TAnfBitV &	BitV2,
		const uint64 &	NId2Offset
	)		const

---

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

• snap-core/anf.h