bfsdfs.h File Reference

Go to the source code of this file.

Classes
class	TBreathFS< PGraph >
Namespaces
namespace	TSnap
	Main namespace for all the Snap global entities.
Functions
template<class PGraph >
PNGraph	TSnap::GetBfsTree (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn)
	Returns a directed Breadth-First-Search tree rooted at StartNId.
template<class PGraph >
int	TSnap::GetSubTreeSz (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, int &TreeSzX, int &TreeDepthX)
	Returns the BFS tree size (number of nodes) and depth (number of levels) by following in-links (parameter FollowIn = true) and/or out-links (parameter FollowOut = true) of node StartNId.
template<class PGraph >
int	TSnap::GetNodesAtHop (const PGraph &Graph, const int &StartNId, const int &Hop, TIntV &NIdV, const bool &IsDir=false)
	Finds IDs of all nodes that are at distance Hop from node StartNId.
template<class PGraph >
int	TSnap::GetNodesAtHops (const PGraph &Graph, const int &StartNId, TIntPrV &HopCntV, const bool &IsDir=false)
	Returns the number of nodes at each hop distance from the starting node StartNId.
template<class PGraph >
int	TSnap::GetShortPath (const PGraph &Graph, const int &SrcNId, const int &DstNId, const bool &IsDir=false)
	Returns the length of the shortest path from node SrcNId to node DstNId.
template<class PGraph >
int	TSnap::GetShortPath (const PGraph &Graph, const int &SrcNId, TIntH &NIdToDistH, const bool &IsDir=false, const int &MaxDist=TInt::Mx)
	Returns the length of the shortest path from node SrcNId to all other nodes in the network.
template<class PGraph >
int	TSnap::GetBfsFullDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false)
	Returns the (approximation of the) Diameter (maximum shortest path length) of a graph (by performing BFS from NTestNodes random starting nodes).
template<class PGraph >
double	TSnap::GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false)
	Returns the (approximation of the) Effective Diameter (90-th percentile of the distribution of shortest path lengths) of a graph (by performing BFS from NTestNodes random starting nodes).
template<class PGraph >
double	TSnap::GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir, double &EffDiamX, int &FullDiamX)
	Returns the (approximation of the) Effective Diameter and the Diameter of a graph (by performing BFS from NTestNodes random starting nodes).
template<class PGraph >
double	TSnap::GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir, double &EffDiamX, int &FullDiamX, double &AvgSPLX)
	Returns the (approximation of the) Effective Diameter, the Diameter and the Average Shortest Path length in a graph (by performing BFS from NTestNodes random starting nodes). GetBfsEffDiam3.
template<class PGraph >
double	TSnap::GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const TIntV &SubGraphNIdV, const bool &IsDir, double &EffDiamX, int &FullDiamX)
	Use the whole graph (all edges) to measure the shortest path lengths but only report the path lengths between nodes in the SubGraphNIdV. GetBfsEffDiam4.