Main namespace for all the Snap global entities. More...

Namespaces
namespace	TSnapDetail
Classes
struct	IsDirected< TBigNet< TNodeData, IsDir > >
struct	IsDirected< TBigNet< TNodeData, true > >
struct	IsNodeDat< TBigNet< TNodeData, IsDir > >
struct	IsDirected
	Tests (at compile time) if the graph is directed. More...
struct	IsMultiGraph
	Tests (at compile time) if the graph is a multigraph with multiple edges between the same nodes. More...
struct	IsNodeDat
	Tests (at compile time) if the graph is a network with data on nodes. More...
struct	IsEdgeDat
	Tests (at compile time) if the graph is a network with data on edges. More...
struct	IsSources
	Tests (at compile time) if the nodes store only out-edges, but not in-edges. More...
struct	IsBipart
	Tests (at compile time) if the graph is a bipartite graph type. More...
class	IsDerivedFrom
	Tests (at complile time) whether TDerivClass is derived from TBaseClass. More...
struct	IsDirected< TNGraph >
struct	IsMultiGraph< TNEGraph >
struct	IsDirected< TNEGraph >
struct	IsBipart< TBPGraph >
struct	IsDirected< TNodeNet< TNodeData > >
struct	IsNodeDat< TNodeNet< TNodeData > >
struct	IsDirected< TNodeEDatNet< TNodeData, TEdgeData > >
struct	IsNodeDat< TNodeEDatNet< TNodeData, TEdgeData > >
struct	IsEdgeDat< TNodeEDatNet< TNodeData, TEdgeData > >
struct	IsMultiGraph< TNodeEdgeNet< TNodeData, TEdgeData > >
struct	IsDirected< TNodeEdgeNet< TNodeData, TEdgeData > >
struct	IsNodeDat< TNodeEdgeNet< TNodeData, TEdgeData > >
struct	IsEdgeDat< TNodeEdgeNet< TNodeData, TEdgeData > >
struct	IsDirected< TTimeNet >
struct	IsNodeDat< TTimeNet >
struct	IsMultiGraph< TTimeNENet >
struct	IsDirected< TTimeNENet >
struct	IsNodeDat< TTimeNENet >
struct	IsEdgeDat< TTimeNENet >
Functions
template<class PGraph >
int	CntInDegNodes (const PGraph &Graph, const int &NodeInDeg)
	Returns the number of nodes with in-degree NodeInDeg.
template<class PGraph >
int	CntOutDegNodes (const PGraph &Graph, const int &NodeOutDeg)
	Returns the number of nodes with out-degree NodeOutDeg.
template<class PGraph >
int	CntDegNodes (const PGraph &Graph, const int &NodeDeg)
	Returns the number of nodes with degree NodeDeg.
template<class PGraph >
int	CntNonZNodes (const PGraph &Graph)
	Returns the number of nodes with degree greater than 0.
template<class PGraph >
int	CntEdgesToSet (const PGraph &Graph, const int &NId, const TIntSet &NodeSet)
	TODO ROK document CntEdgesToSet()
template<class PGraph >
int	GetMxDegNId (const PGraph &Graph)
	Returns a randomly chosen node from all the nodes with the maximum degree.
template<class PGraph >
int	GetMxInDegNId (const PGraph &Graph)
	Returns a randomly chosen node from all the nodes with the maximum in-degree.
template<class PGraph >
int	GetMxOutDegNId (const PGraph &Graph)
	Returns a randomly chosen node from all the nodes with the maximum out-degree.
template<class PGraph >
void	GetInDegCnt (const PGraph &Graph, TIntPrV &DegToCntV)
	TODO ROK document GetInDegCnt()
template<class PGraph >
void	GetOutDegCnt (const PGraph &Graph, TIntPrV &DegToCntV)
	TODO ROK document GetOutDegCnt()
template<class PGraph >
void	GetDegCnt (const PGraph &Graph, TIntPrV &DegToCntV)
	TODO ROK document GetDegCnt()
template<class PGraph >
void	GetDegSeqV (const PGraph &Graph, TIntV &DegV)
	TODO ROK document GetDegSeqV()
template<class PGraph >
void	GetDegSeqV (const PGraph &Graph, TIntV &InDegV, TIntV &OutDegV)
	TODO ROK document GetDegSeqV()
template<class PGraph >
void	GetNodeInDegV (const PGraph &Graph, TIntPrV &NIdInDegV)
template<class PGraph >
void	GetNodeOutDegV (const PGraph &Graph, TIntPrV &NIdOutDegV)
template<class PGraph >
int	CntUniqUndirEdges (const PGraph &Graph)
	Counts unique undirected edges in the graph Graph.
template<class PGraph >
int	CntUniqDirEdges (const PGraph &Graph)
	Counts unique directed edges in the graph Graph.
template<class PGraph >
int	CntUniqBiDirEdges (const PGraph &Graph)
	Counts unique bidirectional edges in the graph Graph.
template<class PGraph >
int	CntSelfEdges (const PGraph &Graph)
template<class PGraph >
PGraph	GetUnDir (const PGraph &Graph)
template<class PGraph >
void	MakeUnDir (const PGraph &Graph)
template<class PGraph >
void	AddSelfEdges (const PGraph &Graph)
template<class PGraph >
void	DelSelfEdges (const PGraph &Graph)
template<class PGraph >
void	DelBiDirEdges (const PGraph &Graph)
template<class PGraph >
void	DelNodes (PGraph &Graph, const TIntV &NIdV)
template<class PGraph >
void	DelZeroDegNodes (PGraph &Graph)
template<class PGraph >
void	DelDegKNodes (PGraph &Graph, const int &OutDegK, const int &InDegK)
template<class PGraph >
bool	IsTree (const PGraph &Graph, int &RootNId)
template<class PGraph >
int	GetTreeRootNId (const PGraph &Graph)
template<class PGraph >
void	GetTreeSig (const PGraph &Graph, const int &RootNId, TIntV &Sig)
template<class PGraph >
void	GetTreeSig (const PGraph &Graph, const int &RootNId, TIntV &Sig, TIntPrV &NodeMap)
template<class PGraph >
void	GetAnf (const PGraph &Graph, const int &SrcNId, TIntFltKdV &DistNbrsV, const int &MxDist, const bool &IsDir, const int &NApprox=32)
template<class PGraph >
void	GetAnf (const PGraph &Graph, TIntFltKdV &DistNbrsV, const int &MxDist, const bool &IsDir, const int &NApprox=32)
template<class PGraph >
double	GetAnfEffDiam (const PGraph &Graph, const bool &IsDir, const double &Percentile, const int &NApprox)
template<class PGraph >
double	GetAnfEffDiam (const PGraph &Graph, const int NRuns=1, int NApprox=-1)
template<class PGraph >
void	TestAnf ()
template<class PGraph >
PNGraph	GetBfsTree (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn)
template<class PGraph >
int	GetSubTreeSz (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, int &TreeSz, int &TreeDepth)
	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	GetNodesAtHop (const PGraph &Graph, const int &StartNId, const int &Hop, TIntV &NIdV, const bool &IsDir=false)
template<class PGraph >
int	GetNodesAtHops (const PGraph &Graph, const int &StartNId, TIntPrV &HopCntV, const bool &IsDir=false)
template<class PGraph >
int	GetShortPath (const PGraph &Graph, const int &SrcNId, const int &DstNId, const bool &IsDir=false)
template<class PGraph >
int	GetShortPath (const PGraph &Graph, const int &SrcNId, TIntH &NIdToDistH, const bool &IsDir=false, const int &MaxDist=TInt::Mx)
template<class PGraph >
int	GetBfsFullDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false)
template<class PGraph >
double	GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false)
template<class PGraph >
double	GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir, double &EffDiam, int &FullDiam)
template<class PGraph >
double	GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir, double &EffDiam, int &FullDiam, double &AvgDiam)
template<class PGraph >
double	GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const TIntV &SubGraphNIdV, const bool &IsDir, double &EffDiam, int &FullDiam)
double	GetDegreeCentr (const PUNGraph &Graph, const int &NId)
double	GetFarnessCentr (const PUNGraph &Graph, const int &NId)
double	GetClosenessCentr (const PUNGraph &Graph, const int &NId)
void	GetBetweennessCentr (const PUNGraph &Graph, const TIntV &BtwNIdV, TIntFltH &NodeBtwH, const bool &DoNodeCent, TIntPrFltH &EdgeBtwH, const bool &DoEdgeCent)
void	GetBetweennessCentr (const PUNGraph &Graph, TIntFltH &NodeBtwH, const double &NodeFrac)
void	GetBetweennessCentr (const PUNGraph &Graph, TIntFltH &NodeBtwH, TIntPrFltH &EdgeBtwH, const double &NodeFrac)
void	GetEigenVectorCentr (const PUNGraph &Graph, TIntFltH &NIdEigenH, const double &Eps, const int &MaxIter)
template<class PGraph >
int	GetNodeEcc (const PGraph &Graph, const int &NId, const bool &IsDir=false)
template<class PGraph >
void	GetPageRank (const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
template<class PGraph >
void	GetHits (const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20)
double	CommunityGirvanNewman (PUNGraph &Graph, TCnComV &CmtyV)
double	CommunityCNM (const PUNGraph &Graph, TCnComV &CmtyV)
template<typename PGraph >
double	GetModularity (const PGraph &G, const TIntV &NIdV, int GEdges=-1)
template<typename PGraph >
void	GetEdgesInOut (const PGraph &Graph, const TIntV &NIdV, int &EdgesIn, int &EdgesOut)
void	GetBiConSzCnt (const PUNGraph &Graph, TIntPrV &SzCntV)
void	GetBiCon (const PUNGraph &Graph, TCnComV &BiCnComV)
void	GetArtPoints (const PUNGraph &Graph, TIntV &ArtNIdV)
void	GetEdgeBridges (const PUNGraph &Graph, TIntPrV &EdgeV)
void	Get1CnComSzCnt (const PUNGraph &Graph, TIntPrV &SzCntV)
void	Get1CnCom (const PUNGraph &Graph, TCnComV &Cn1ComV)
PUNGraph	GetMxBiCon (const PUNGraph &Graph, const bool &RenumberNodes)
template<class PGraph >
void	GetNodeWcc (const PGraph &Graph, const int &NId, TIntV &CnCom)
	Returns (via output parameter CnCom) all nodes that are in the same connected component as node NId.
template<class PGraph >
bool	IsConnected (const PGraph &Graph)
	Tests whether the Graph is (weakly) connected.
template<class PGraph >
bool	IsWeaklyConn (const PGraph &Graph)
	Tests whether the Graph is weakly connected.
template<class PGraph >
void	GetWccSzCnt (const PGraph &Graph, TIntPrV &WccSzCnt)
template<class PGraph >
void	GetWccs (const PGraph &Graph, TCnComV &CnComV)
template<class PGraph >
void	GetSccSzCnt (const PGraph &Graph, TIntPrV &SccSzCnt)
template<class PGraph >
void	GetSccs (const PGraph &Graph, TCnComV &CnComV)
template<class PGraph >
double	GetMxWccSz (const PGraph &Graph)
	Returns the fraction of nodes in the largest weakly connected component of a Graph.
template<class PGraph >
PGraph	GetMxWcc (const PGraph &Graph)
template<class PGraph >
PGraph	GetMxScc (const PGraph &Graph)
template<class PGraph >
PGraph	GetMxBiCon (const PGraph &Graph)
TStr	GetFlagStr (const TGraphFlag &GraphFlag)
	Returns a string representation of a flag.
template<class PGraph >
void	PrintInfo (const PGraph &Graph, const TStr &Desc="", const TStr &OutFNm="", const bool &Fast=true)
template<class PGraph >
int	GetTriads (const PGraph &Graph, int &ClosedTriads, int &OpenTriads, int SampleNodes=-1)
PBPGraph	GenRndBipart (const int &LeftNodes, const int &RightNodes, const int &Edges, TRnd &Rnd=TInt::Rnd)
	Generates a random bipartite graph.
PUNGraph	GenRndDegK (const int &Nodes, const int &NodeDeg, const int &NSwitch=100, TRnd &Rnd=TInt::Rnd)
	Generates a random graph where each node has degree exactly NodeDeg.
PUNGraph	GenRndPowerLaw (const int &Nodes, const double &PowerExp, const bool &ConfModel, TRnd &Rnd)
PUNGraph	GenDegSeq (const TIntV &DegSeqV, TRnd &Rnd)
PUNGraph	GenConfModel (const TIntV &DegSeqV, TRnd &Rnd)
PUNGraph	GenRewire (const PUNGraph &OrigGraph, const int &NSwitch, TRnd &Rnd)
PUNGraph	GenPrefAttach (const int &Nodes, const int &NodeOutDeg, TRnd &Rnd)
PUNGraph	GenGeoPrefAttach (const int &Nodes, const int &OutDeg, const double &Beta, TRnd &Rnd)
PUNGraph	GenSmallWorld (const int &Nodes, const int &NodeOutDeg, const double &RewireProb, TRnd &Rnd)
PNGraph	GenForestFire (const int &Nodes, const double &FwdProb, const double &BckProb)
PNGraph	GenCopyModel (const int &Nodes, const double &Beta, TRnd &Rnd)
PNGraph	GenRMat (const int &Nodes, const int &Edges, const double &A, const double &B, const double &C, TRnd &Rnd)
PNGraph	GenRMatEpinions ()
template<class PGraph >
PGraph	GenGrid (const int &Rows, const int &Cols, const bool &IsDir=true)
	Generates a 2D-grid graph of Rows rows and Cols columns.
template<class PGraph >
PGraph	GenStar (const int &Nodes, const bool &IsDir=true)
	Generates a graph with star topology. Node id 0 is in the center and then links to all other nodes.
template<class PGraph >
PGraph	GenCircle (const int &Nodes, const int &NodeOutDeg=1, const bool &IsDir=true)
	Generates a circle graph where every node creates out-links to NodeOutDeg forward nodes.
template<class PGraph >
PGraph	GenFull (const int &Nodes)
	Generates a complete graph on Nodes nodes. Graph has no self-loops.
template<class PGraph >
PGraph	GenTree (const int &Fanout, const int &Levels, const bool &IsDir=true, const bool &ChildPointsToParent=true)
	Generates a tree graph of Levels levels with every parent having Fanout children.
template<class PGraph >
PGraph	GenBaraHierar (const int &Levels, const bool &IsDir=true)
	Generates a Ravasz-Barabasi deterministic scale-free graph.
template<class PGraph >
PGraph	GenRndGnm (const int &Nodes, const int &Edges, const bool &IsDir=true, TRnd &Rnd=TInt::Rnd)
	Generates an Erdos-Renyi random graph.
PNGraph	LoadDyNet (const TStr &FNm)
	For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php)
TVec< PNGraph >	LoadDyNetGraphV (const TStr &FNm)
	For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php)
template<class PGraph >
PGraph	LoadEdgeList (const TStr &InFNm, const int &SrcColId=0, const int &DstColId=1)
	Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, integer node ids).
template<class PGraph >
PGraph	LoadEdgeList (const TStr &InFNm, const int &SrcColId, const int &DstColId, const char &Separator)
	Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line ('Separator' separated columns, integer node ids).
template<class PGraph >
PGraph	LoadEdgeListStr (const TStr &InFNm, const int &SrcColId=0, const int &DstColId=1)
	Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, arbitrary string node ids).
template<class PGraph >
PGraph	LoadEdgeListStr (const TStr &InFNm, const int &SrcColId, const int &DstColId, TStrHash< TInt > &StrToNIdH)
	Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, arbitrary string node ids).
template<class PGraph >
PGraph	LoadConnList (const TStr &InFNm)
	Loads a (directed, undirected or multi) graph from a text file InFNm with 1 node and all its edges in a single line.
template<class PGraph >
PGraph	LoadConnListStr (const TStr &InFNm, TStrHash< TInt > &StrToNIdH)
	Loads a (directed, undirected or multi) graph from a text file InFNm with 1 node and all its edges in a single line.
template<class PGraph >
PGraph	LoadPajek (const TStr &InFNm)
template<class PGraph >
void	SaveEdgeList (const PGraph &Graph, const TStr &OutFNm, const TStr &Desc=TStr())
	Saves a graph into a text file. Each line contains two columsn and encodes a single edge: <source node="" id>=""><tab><destination node="" id>="">
template<class PGraph >
void	SavePajek (const PGraph &Graph, const TStr &OutFNm)
	Saves a graph in a Pajek .NET format.
template<class PGraph >
void	SavePajek (const PGraph &Graph, const TStr &OutFNm, const TIntStrH &NIdColorH)
	Saves a graph in a Pajek .NET format.
template<class PGraph >
void	SavePajek (const PGraph &Graph, const TStr &OutFNm, const TIntStrH &NIdColorH, const TIntStrH &NIdLabelH)
	Saves a graph in a Pajek .NET format.
template<class PGraph >
void	SavePajek (const PGraph &Graph, const TStr &OutFNm, const TIntStrH &NIdColorH, const TIntStrH &NIdLabelH, const TIntStrH &EIdColorH)
	Saves a graph in a Pajek .NET format.
template<class PGraph >
void	SaveMatlabSparseMtx (const PGraph &Graph, const TStr &OutFNm)
	Saves a graph in a MATLAB sparse matrix format.
template<class PGraph >
void	SaveGViz (const PGraph &Graph, const TStr &OutFNm, const TStr &Desc=TStr(), const bool &NodeLabels=false, const TIntStrH &NIdColorH=TIntStrH())
template<class PGraph >
void	SaveGViz (const PGraph &Graph, const TStr &OutFNm, const TStr &Desc, const TIntStrH &NIdLabelH)
void	SetAllInvertSign (TFltV &ValV, const double &Val)
bool	IsAllValVNeg (TFltV &ValV, const bool &InvertSign)
void	GetSngVals (const PNGraph &Graph, const int &SngVals, TFltV &SngValV)
	Computes largest SngVals singular values of the adjacency matrix representing a directed Graph.
void	GetSngVec (const PNGraph &Graph, TFltV &LeftSV, TFltV &RightSV)
	Computes the leading left and right singular vector of the adjacency matrix representing a directed Graph.
void	GetSngVec (const PNGraph &Graph, const int &SngVecs, TFltV &SngValV, TVec< TFltV > &LeftSV, TVec< TFltV > &RightSV)
void	GetEigVals (const PUNGraph &Graph, const int &EigVals, TFltV &EigValV)
	Computes top EigVals eigenvalues of the adjacency matrix representing a given undirected Graph.
void	GetEigVec (const PUNGraph &Graph, TFltV &EigVecV)
	Computes the leading eigenvector of the adjacency matrix representing a given undirected Graph.
void	GetEigVec (const PUNGraph &Graph, const int &EigVecs, TFltV &EigValV, TVec< TFltV > &EigVecV)
	Computes top EigVecs eigenvalues and eigenvectors of the adjacency matrix representing a given undirected Graph.
void	GetInvParticipRat (const PUNGraph &Graph, int MaxEigVecs, int TimeLimit, TFltPrV &EigValIprV)
template<class PGraph >
void	DrawGViz (const PGraph &Graph, const TGVizLayout &Layout, const TStr &PltFNm, const TStr &Desc=TStr(), const bool &NodeLabels=false, const TIntStrH &NIdColorH=TIntStrH())
template<class PGraph >
void	DrawGViz (const PGraph &Graph, const TGVizLayout &Layout, const TStr &PltFNm, const TStr &Desc, const TIntStrH &NIdColorH)
template<class PGraph >
PGraph	GetKCore (const PGraph &Graph, const int &K)
void	PlotEigValRank (const PUNGraph &Graph, const int &EigVals, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the eigen-value rank distribution of the Graph adjacency matrix. Plots first EigVals eigenvalues.
void	PlotEigValDistr (const PUNGraph &Graph, const int &EigVals, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the distribution of components of the leading eigen-vector of the Graph adjacency matrix. Plots first EigVals values.
void	PlotInvParticipRat (const PUNGraph &Graph, const int &MaxEigVecs, const int &TimeLimit, const TStr &FNmPref, TStr DescStr)
void	PlotSngValRank (const PNGraph &Graph, const int &SngVals, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the rank distribution of singular values of the Graph adjacency matrix. Plots first SngVals values.
void	PlotSngValDistr (const PNGraph &Graph, const int &SngVals, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the rank distribution of singular values of the Graph adjacency matrix. Plots first SngVals values.
void	PlotSngVec (const PNGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the distribution of the values of the leading left singular vector of the Graph adjacency matrix. Plots first SngVals values.
template<class PGraph >
void	PlotInDegDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr(), const bool &PlotCCdf=false, const bool &PowerFit=false)
template<class PGraph >
void	PlotOutDegDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr(), const bool &PlotCCdf=false, const bool &PowerFit=false)
template<class PGraph >
void	PlotWccDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the distribution of sizes of weakly connected components of a Graph.
template<class PGraph >
void	PlotSccDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the distribution of sizes of strongly connected components of a Graph.
template<class PGraph >
void	PlotClustCf (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the distribution of clustering coefficient of a Graph.
template<class PGraph >
void	PlotHops (const PGraph &Graph, const TStr &FNmPref, const TStr &DescStr, const bool &IsDir=false, const int &NApprox=32)
template<class PGraph >
void	PlotShortPathDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr(), int TestNodes=TInt::Mx)
	Plots the distribution of the shortest path lengths of a Graph. Implementation is based on BFS.
PUNGraph	GetSubGraph (const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes=false)
	Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumbering.
template<class PGraph >
PGraph	GetSubGraph (const PGraph &Graph, const TIntV &NIdV)
	Returns an induced subgraph of graph Graph with NIdV nodes.
template<class PGraph >
PGraph	GetESubGraph (const PGraph &Graph, const TIntV &EIdV)
	Returns a subgraph of graph Graph with EIdV edges.
template<class PGraph , class TEdgeDat >
PGraph	GetEDatSubGraph (const PGraph &Graph, const TEdgeDat &EDat, const int &Cmp)
	Returns a subgraph of graph Graph with edges where edge data matches the parameters.
template<class PGraph , class TEdgeDat >
PGraph	GetEDatSubGraph (const PGraph &Graph, const TIntV &NIdV, const TEdgeDat &EDat, const int &Cmp)
	Returns a subgraph of graph Graph with NIdV nodes and edges where edge data matches the parameters.
template<class POutGraph , class PInGraph >
POutGraph	ConvertGraph (const PInGraph &InGraph, const bool &RenumberNodes=false)
	Performs conversion of graph InGraph with an optional node renumbering.
template<class POutGraph , class PInGraph >
POutGraph	ConvertSubGraph (const PInGraph &InGraph, const TIntV &NIdV, const bool &RenumberNodes=false)
	Returns an induced subgraph of graph InGraph with NIdV nodes with an optional node renumbering.
template<class POutGraph , class PInGraph >
POutGraph	ConvertESubGraph (const PInGraph &InGraph, const TIntV &EIdV, const bool &RenumberNodes=false)
	Returns a subgraph of graph InGraph with EIdV edges with an optional node renumbering.
template<class PGraph >
PGraph	GetRndSubGraph (const PGraph &Graph, const int &NNodes)
	Returns an induced random subgraph of graph Graph with NNodes nodes.
template<class PGraph >
PGraph	GetRndESubGraph (const PGraph &Graph, const int &NEdges)
	Returns a random subgraph of graph Graph with NEdges edges.
template<class PGraph >
double	GetClustCf (const PGraph &Graph, int SampleNodes=-1)
	Computes the average clustering coefficient as defined in Watts and Strogatz, Collective dynamics of 'small-world' networks.
template<class PGraph >
double	GetClustCf (const PGraph &Graph, TFltPrV &DegToCCfV, int SampleNodes=-1)
template<class PGraph >
double	GetClustCf (const PGraph &Graph, TFltPrV &DegToCCfV, int &ClosedTriads, int &OpenTriads, int SampleNodes=-1)
template<class PGraph >
double	GetNodeClustCf (const PGraph &Graph, const int &NId)
	Returns clustering coefficient of a particular node.
template<class PGraph >
void	GetNodeClustCf (const PGraph &Graph, TIntFltH &NIdCCfH)
	Computes clustering coefficient of each node of the Graph.
template<class PGraph >
int	GetTriads (const PGraph &Graph, int SampleNodes=-1)
template<class PGraph >
void	GetTriads (const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes=-1)
template<class PGraph >
int	GetTriadEdges (const PGraph &Graph, int SampleEdges=-1)
template<class PGraph >
int	GetNodeTriads (const PGraph &Graph, const int &NId)
	Returns number of undirected triads a node NId participates in.
template<class PGraph >
int	GetNodeTriads (const PGraph &Graph, const int &NId, int &ClosedTriads, int &OpenTriads)
	Returns number of undirected Open and Closed triads a node NId participates in.
template<class PGraph >
int	GetNodeTriads (const PUNGraph &Graph, const int &NId, const TIntSet &GroupSet, int &InGroupEdges, int &InOutGroupEdges)
template<class PGraph >
int	GetNodeTriads (const PUNGraph &Graph, const int &NId, const TIntSet &GroupSet, int &InGroupEdges, int &InOutGroupEdges, int &OutGroup)
template<class PGraph >
void	GetTriadParticip (const PGraph &Graph, TIntPrV &TriadCntV)
	Triangle Participation Ratio: For each node counts how many triangles it participates in and then returns a set of pairs (number of triangles, number of such nodes).
template<class PGraph >
int	GetCmnNbrs (const PGraph &Graph, const int &NId1, const int &NId2)
	Returns a number of shared neighbors between a pair of nodes NId1 and NId2.
template<class PGraph >
int	GetCmnNbrs (const PGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV)
	Returns the shared neighbors between a pair of nodes NId1 and NId2.
template<class PGraph >
int	GetLen2Paths (const PGraph &Graph, const int &NId1, const int &NId2)
	Returns the number of length 2 directed paths between a pair of nodes NId1, NId2 (NId1 --> U --> NId2).
template<class PGraph >
int	GetLen2Paths (const PGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV)
	Returns the 2 directed paths between a pair of nodes NId1, NId2 (NId1 --> U --> NId2). NbrV intermediary stores nodes U.
template<class PGraph >
int	GetNodeTriads (const PGraph &Graph, const int &NId, const TIntSet &GroupSet, int &InGroupEdges, int &InOutGroupEdges)
template<class PGraph >
int	GetNodeTriads (const PGraph &Graph, const int &NId, const TIntSet &GroupSet, int &InGroupEdges, int &InOutGroupEdges, int &OutGroupEdges)
template<>
int	GetCmnNbrs< PUNGraph > (const PUNGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV)

Detailed Description

Main namespace for all the Snap global entities.

Function Documentation

template<class PGraph >

void TSnap::AddSelfEdges ( const PGraph & Graph )

template<class PGraph >

int TSnap::CntDegNodes	(	const PGraph &	Graph,
		const int &	NodeDeg
	)

Returns the number of nodes with degree NodeDeg.

template<class PGraph >

int TSnap::CntEdgesToSet	(	const PGraph &	Graph,
		const int &	NId,
		const TIntSet &	NodeSet
	)

TODO ROK document CntEdgesToSet()

template<class PGraph >

int TSnap::CntInDegNodes	(	const PGraph &	Graph,
		const int &	NodeInDeg
	)

Returns the number of nodes with in-degree NodeInDeg.

template<class PGraph >

int TSnap::CntNonZNodes ( const PGraph & Graph )

Returns the number of nodes with degree greater than 0.

template<class PGraph >

int TSnap::CntOutDegNodes	(	const PGraph &	Graph,
		const int &	NodeOutDeg
	)

Returns the number of nodes with out-degree NodeOutDeg.

template<class PGraph >

int TSnap::CntSelfEdges ( const PGraph & Graph )

template<class PGraph >

int TSnap::CntUniqBiDirEdges ( const PGraph & Graph )

Counts unique bidirectional edges in the graph Graph.

template<class PGraph >

int TSnap::CntUniqDirEdges ( const PGraph & Graph )

Counts unique directed edges in the graph Graph.

template<class PGraph >

int TSnap::CntUniqUndirEdges ( const PGraph & Graph )

Counts unique undirected edges in the graph Graph.

double TSnap::CommunityCNM	(	const PUNGraph &	Graph,
		TCnComV &	CmtyV
	)

Clauset-Newman-Moore community detection method for large networks. At every step of the algorithm two communities that contribute maximum positive value to global modularity are merged. See: Finding community structure in very large networks, A. Clauset, M.E.J. Newman, C. Moore, 2004

double TSnap::CommunityGirvanNewman	(	PUNGraph &	Graph,
		TCnComV &	CmtyV
	)

Girvan-Newman community detection algorithm based on Betweenness centrality. See: Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002)

template<class POutGraph , class PInGraph >

POutGraph TSnap::ConvertESubGraph	(	const PInGraph &	InGraph,
		const TIntV &	EIdV,
		const bool &	RenumberNodes = `false`
	)

Returns a subgraph of graph InGraph with EIdV edges with an optional node renumbering.

Creates a subgraph of the input graph InGraph on EIdV edges and returns an output graph. Input and output graphs can have different types. Node and edge data is not copied, but it is shared by input and output graphs.

Parameter RenumberNodes determines, whether the node IDs are preserved or not. If RenumberNodes is false, then nodes in the resulting graph have the same node IDs as nodes in InGraph. If RenumberNodes is true, then nodes in the resulting graph are renumbered sequentially from 0 to N-1. By default, the nodes are not renumbered.

template<class POutGraph , class PInGraph >

POutGraph TSnap::ConvertGraph	(	const PInGraph &	InGraph,
		const bool &	RenumberNodes = `false`
	)

Performs conversion of graph InGraph with an optional node renumbering.

Takes an input graph InGraph and returns an output graph. Input and output graphs can have different types. Node and edge data is not copied, but it is shared by input and output graphs.

Parameter RenumberNodes determines, whether the node IDs are preserved or not. If RenumberNodes is false, then nodes in the resulting graph have the same node IDs as nodes in InGraph. If RenumberNodes is true, then nodes in the resulting graph are renumbered sequentially from 0 to N-1. By default, the nodes are not renumbered.

template<class POutGraph , class PInGraph >

POutGraph TSnap::ConvertSubGraph	(	const PInGraph &	InGraph,
		const TIntV &	NIdV,
		const bool &	RenumberNodes = `false`
	)

Returns an induced subgraph of graph InGraph with NIdV nodes with an optional node renumbering.

Creates a subgraph of the input graph InGraph on NIdV nodes and returns an output graph. Input and output graphs can have different types. Node and edge data is not copied, but it is shared by input and output graphs.

Parameter RenumberNodes determines, whether the node IDs are preserved or not. If RenumberNodes is false, then nodes in the resulting graph have the same node IDs as nodes in InGraph. If RenumberNodes is true, then nodes in the resulting graph are renumbered sequentially from 0 to N-1. By default, the nodes are not renumbered.

template<class PGraph >

void TSnap::DelBiDirEdges ( const PGraph & Graph )

template<class PGraph >

void TSnap::DelDegKNodes	(	PGraph &	Graph,
		const int &	OutDegK,
		const int &	InDegK
	)

template<class PGraph >

void TSnap::DelNodes	(	PGraph &	Graph,
		const TIntV &	NIdV
	)

template<class PGraph >

void TSnap::DelSelfEdges ( const PGraph & Graph )

template<class PGraph >

void TSnap::DelZeroDegNodes ( PGraph & Graph )

template<class PGraph >

void TSnap::DrawGViz	(	const PGraph &	Graph,
		const TGVizLayout &	Layout,
		const TStr &	PltFNm,
		const TStr &	Desc = `TStr()`,
		const bool &	NodeLabels = `false`,
		const TIntStrH &	NIdColorH = `TIntStrH()`
	)

Draws a given Graph using a selected GraphViz Layout engine. Useful for drawing small (<100 node) graphs.

Parameters:

PltFNm	Output filename (extension .ps, .png, .gif) determines the output format.
NIdColorH	Maps node ids to node colors (see GraphViz documentation for more details).

template<class PGraph >

void TSnap::DrawGViz	(	const PGraph &	Graph,
		const TGVizLayout &	Layout,
		const TStr &	PltFNm,
		const TStr &	Desc,
		const TIntStrH &	NIdColorH
	)

Draws a given Graph using a selected GraphViz Layout engine. Useful for drawing small (<100 node) graphs.

Parameters:

PltFNm	Output filename (extension .ps, .png, .gif) determines the output format.
NIdColorH	Maps node ids to node colors (see GraphViz documentation for more details).

template<class PGraph >

PGraph TSnap::GenBaraHierar	(	const int &	Levels,
		const bool &	IsDir
	)

Generates a Ravasz-Barabasi deterministic scale-free graph.

Corners of the graph are recursively expanded with miniature copies of the base graph (below). The graph has power-law degree distribution with the exponent 1+ln(5)/ln(4) and clustering coefficient with power-law decay exponent -1. Base graph:

  *   o---o
  *   |\ /|
  *   | o |
  *   |/ \|
  *   o---o
  *

See: Hierarchical organization in complex networks. Ravasz and Barabasi. URL: http://arxiv.org/abs/cond-mat/0206130

template<class PGraph >

PGraph TSnap::GenCircle	(	const int &	Nodes,
		const int &	NodeOutDeg = `1`,
		const bool &	IsDir = `true`
	)

Generates a circle graph where every node creates out-links to NodeOutDeg forward nodes.

PUNGraph TSnap::GenConfModel	(	const TIntV &	DegSeqV,
		TRnd &	Rnd
	)

Generates a random undirect graph with a given degree sequence DegSeqV. Configuration model operates as follows. For each node N, of degree DeqSeqV[N] we create DeqSeqV[N] spokes (half-edges). We then pick two spokes at random, and connect the spokes endpoints. We continue this process until no spokes are left. Generally this generates a multigraph (i.e., spokes out of same nodes can be chosen multiple times).We ignore (discard) self-loops and multiple edges. Thus, the generated graph will only approximate follow the given degree sequence. The method is very fast!

PNGraph TSnap::GenCopyModel	(	const int &	Nodes,
		const double &	Beta,
		TRnd &	Rnd
	)

Generates a random scale-free network using the Copying Model. The generating process operates as follows: Node u is added to a graph, it selects a random node v, and with prob Beta it links to v, with 1-Beta links u links to neighbor of v. The power-law degree exponent is -1/(1-Beta). See: Stochastic models for the web graph. Kumar, Raghavan, Rajagopalan, Sivakumar, Tomkins, Upfal. URL: http://snap.stanford.edu/class/cs224w-readings/kumar00stochastic.pdf

PUNGraph TSnap::GenDegSeq	(	const TIntV &	DegSeqV,
		TRnd &	Rnd
	)

Generates a random graph with exact degree sequence DegSeqV. The generated graph has no self loops. The graph generation process simulates the Configuration Model but if a duplicate edge occurs, we find a random edge, break it and reconnect it with the duplicate.

PNGraph TSnap::GenForestFire	(	const int &	Nodes,
		const double &	FwdProb,
		const double &	BckProb
	)

template<class PGraph >

PGraph TSnap::GenFull ( const int & Nodes )

Generates a complete graph on Nodes nodes. Graph has no self-loops.

PUNGraph TSnap::GenGeoPrefAttach	(	const int &	Nodes,
		const int &	OutDeg,
		const double &	Beta,
		TRnd &	Rnd
	)

Generates a random scale-free graph using the Geometric Preferential Attachment model by Flexman, Frieze and Vera. See: A geometric preferential attachment model of networks by Flexman, Frieze and Vera. WAW 2004. URL: http://math.cmu.edu/~af1p/Texfiles/GeoWeb.pdf

template<class PGraph >

PGraph TSnap::GenGrid	(	const int &	Rows,
		const int &	Cols,
		const bool &	IsDir = `true`
	)

Generates a 2D-grid graph of Rows rows and Cols columns.

PUNGraph TSnap::GenPrefAttach	(	const int &	Nodes,
		const int &	NodeOutDeg,
		TRnd &	Rnd
	)

Barabasi-Albert model of scale-free graphs. The graph has power-law degree distribution. See: Emergence of scaling in random networks by Barabasi and Albert. URL: http://arxiv.org/abs/cond-mat/9910332

PUNGraph TSnap::GenRewire	(	const PUNGraph &	OrigGraph,
		const int &	NSwitch,
		TRnd &	Rnd
	)

Rewire the network. Keeps node degrees as is but randomly rewires the edges. Use this function to generate a random graph with the same degree sequence as the OrigGraph. See: On the uniform generation of random graphs with prescribed degree sequences by R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon URL: http://arxiv.org/abs/cond-mat/0312028

Rewire the network. Keeps node degrees as is but randomly rewires the edges. Use this function to generate a random graph with the same degree sequence as the OrigGraph. See: On the uniform generation of random graphs with prescribed degree sequences by R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon. URL: http://arxiv.org/abs/cond-mat/0312028

Rewire a bipartite graph. Keeps node degrees as is but randomly rewires the edges. Use this function to generate a random graph with the same degree sequence as the OrigGraph. See: On the uniform generation of random graphs with prescribed degree sequences by R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon URL: http://arxiv.org/abs/cond-mat/0312028

PNGraph TSnap::GenRMat	(	const int &	Nodes,
		const int &	Edges,
		const double &	A,
		const double &	B,
		const double &	C,
		TRnd &	Rnd
	)

R-MAT Generator. The modes is based on the recursive descent into a 2x2 matrix [A,B; C, 1-(A+B+C)]. See: R-MAT Generator: A Recursive Model for Graph Mining. D. Chakrabarti, Y. Zhan and C. Faloutsos, in SIAM Data Mining 2004. URL: http://www.cs.cmu.edu/~deepay/mywww/papers/siam04.pdf

PNGraph TSnap::GenRMatEpinions ( )

R-Mat generator with parameters set so that it generates a synthetic copy of the Epinions social network. The original Epinions social network can be downloaded at http://snap.stanford.edu/data/soc-Epinions1.html

PBPGraph TSnap::GenRndBipart	(	const int &	LeftNodes,
		const int &	RightNodes,
		const int &	Edges,
		TRnd &	Rnd
	)

Generates a random bipartite graph.

PUNGraph TSnap::GenRndDegK	(	const int &	Nodes,
		const int &	NodeDeg,
		const int &	NSwitch,
		TRnd &	Rnd
	)

Generates a random graph where each node has degree exactly NodeDeg.

template<class PGraph >

PGraph TSnap::GenRndGnm	(	const int &	Nodes,
		const int &	Edges,
		const bool &	IsDir = `true`,
		TRnd &	Rnd = `TInt::Rnd`
	)

Generates an Erdos-Renyi random graph.

PUNGraph TSnap::GenRndPowerLaw	(	const int &	Nodes,
		const double &	PowerExp,
		const bool &	ConfModel,
		TRnd &	Rnd
	)

Generates a random scale-free graph with power-law degree distribution with exponent PowerExp. The method uses either the Configuration model (fast but the the result is approximate) or the Edge Rewiring method (slow but exact).

PUNGraph TSnap::GenSmallWorld	(	const int &	Nodes,
		const int &	NodeOutDeg,
		const double &	RewireProb,
		TRnd &	Rnd
	)

Generates a small-world graph using the Watts-Strogatz model. We assume a circle where each node creates links to NodeOutDeg other nodes. This way at the end each node is connected to 2*NodeOutDeg other nodes. See: Collective dynamics of 'small-world' networks. Watts and Strogatz. URL: http://research.yahoo.com/files/w_s_NATURE_0.pdf

template<class PGraph >

PGraph TSnap::GenStar	(	const int &	Nodes,
		const bool &	IsDir = `true`
	)

Generates a graph with star topology. Node id 0 is in the center and then links to all other nodes.

template<class PGraph >

PGraph TSnap::GenTree	(	const int &	Fanout,
		const int &	Levels,
		const bool &	IsDir = `true`,
		const bool &	ChildPointsToParent = `true`
	)

Generates a tree graph of Levels levels with every parent having Fanout children.

void TSnap::Get1CnCom	(	const PUNGraph &	Graph,
		TCnComV &	Cn1ComV
	)

Returns 1-components: maximal connected components of that can be disconnected from the Graph by removing a single edge. We find such components as follows: Find all bridge edges, remove them from the Graph, find largest component K and add back all bridges that do not touch K. Now, find the connected components of this graph.

void TSnap::Get1CnComSzCnt	(	const PUNGraph &	Graph,
		TIntPrV &	SzCntV
	)

Distribution of sizes of 1-components, maximal components of that can be disconnected from the Graph by removing a single edge. We find such components as follows: Find all bridge edges, remove them from the Graph, find largest component K and add back all bridges that do not touch K. Now, find the connected components of this graph.

template<class PGraph >

void TSnap::GetAnf	(	const PGraph &	Graph,
		const int &	SrcNId,
		TIntFltKdV &	DistNbrsV,
		const int &	MxDist,
		const bool &	IsDir,
		const int &	NApprox = `32`
	)

Approximate Neighborhood Function of a node: Returns the (approximate) 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).
NApprox	Quality of approximation. See the ANF paper.

template<class PGraph >

void TSnap::GetAnf	(	const PGraph &	Graph,
		TIntFltKdV &	DistNbrsV,
		const int &	MxDist,
		const bool &	IsDir,
		const int &	NApprox = `32`
	)

Approximate Neighborhood Function of a Graph: 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).
NApprox	Quality of approximation. See the ANF paper.

template<class PGraph >

double TSnap::GetAnfEffDiam	(	const PGraph &	Graph,
		const bool &	IsDir,
		const double &	Percentile,
		const int &	NApprox
	)

Returns a given Percentile of the shortest path length distribution of a Graph (based on a single run of ANF of approximation quality NApprox).

Parameters:

IsDir false: consider links as undirected (drop link directions).

template<class PGraph >

double TSnap::GetAnfEffDiam	(	const PGraph &	Graph,
		const int	NRuns = `1`,
		int	NApprox = `-1`
	)

Returns a 90-th percentile of the shortest path length distribution of a Graph (based on a NRuns runs of ANF of approximation quality NApprox).

Parameters:

IsDir false: consider links as undirected (drop link directions).

void TSnap::GetArtPoints	(	const PUNGraph &	Graph,
		TIntV &	ArtNIdV
	)

Returns articulartion points of a Graph. Articulation point (or a cut vertex) is any node that when removed increases the number of connected components.

void TSnap::GetBetweennessCentr	(	const PUNGraph &	Graph,
		const TIntV &	BtwNIdV,
		TIntFltH &	NodeBtwH,
		const bool &	DoNodeCent,
		TIntPrFltH &	EdgeBtwH,
		const bool &	DoEdgeCent
	)

Computes (approximate) Beetweenness Centrality of all nodes and all edges of the network. To obtain exact betweenness values one needs to solve single-source shortest-path problem for every node. To speed up the algorithm we solve the shortest-path problem for the BtwNIdV subset of nodes. This gives centrality values that are about Graph->GetNodes()/BtwNIdV.Len() times lower than the exact betweenness centrality valus. See "A Faster Algorithm for Beetweenness Centrality", Ulrik Brandes, Journal of Mathematical Sociology, 2001, and "Centrality Estimation in Large Networks", Urlik Brandes and Christian Pich, 2006 for more details.

void TSnap::GetBetweennessCentr	(	const PUNGraph &	Graph,
		TIntFltH &	NIdBtwH,
		const double &	NodeFrac = `1.0`
	)

Computes (approximate) Node Beetweenness Centrality based on a sample of NodeFrac nodes.

Parameters:

NIdBtwH	hash table mapping node ids to their corresponding betweenness centrality values.
NodeFrac	quality of approximation. NodeFrac=1.0 gives exact betweenness values.

Computes (approximate) Edge Beetweenness Centrality based on a sample of NodeFrac nodes.

Parameters:

EdgeBtwH	hash table mapping edges (pairs of node ids) to their corresponding betweenness centrality values.
NodeFrac	quality of approximation. NodeFrac=1.0 gives exact betweenness values.

void TSnap::GetBetweennessCentr	(	const PUNGraph &	Graph,
		TIntFltH &	NIdBtwH,
		TIntPrFltH &	EdgeBtwH,
		const double &	NodeFrac = `1.0`
	)

Computes (approximate) Node and Edge Beetweenness Centrality based on a sample of NodeFrac nodes.

Parameters:

NIdBtwH	hash table mapping node ids to their corresponding betweenness centrality values.
EdgeBtwH	hash table mapping edges (pairs of node ids) to their corresponding betweenness centrality values.
NodeFrac	quality of approximation. NodeFrac=1.0 gives exact betweenness values.

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 lenghts) of a graph (by performing BFS from NTestNodes random starting nodes).

Parameters:

IsDir false: ignore edge directions and consider edges/paths as undirected (in case they are directed).

template<class PGraph >

double TSnap::GetBfsEffDiam	(	const PGraph &	Graph,
		const int &	NTestNodes,
		const bool &	IsDir,
		double &	EffDiam,
		int &	FullDiam
	)

Returns the (approximation of the) Effective Diameter and the Diameter of a graph (by performing BFS from NTestNodes random starting nodes).

Parameters:

IsDir false: ignore edge directions and consider edges/paths as undirected (in case they are directed).

template<class PGraph >

double TSnap::GetBfsEffDiam	(	const PGraph &	Graph,
		const int &	NTestNodes,
		const bool &	IsDir,
		double &	EffDiam,
		int &	FullDiam,
		double &	AvgDiam
	)

Returns the (approximation of the) Effective Diameter, the Diameter and the Average Shortest Path lenght in a graph (by performing BFS from NTestNodes random starting nodes).

Parameters:

IsDir false: ignore edge directions and consider edges/paths as undirected (in case they are directed).

template<class PGraph >

double TSnap::GetBfsEffDiam	(	const PGraph &	Graph,
		const int &	NTestNodes,
		const TIntV &	SubGraphNIdV,
		const bool &	IsDir,
		double &	EffDiam,
		int &	FullDiam
	)

Use the whole graph (all edges) to measure the shortest path lenghts but report the path lengths only between nodes in the SubGraphNIdV.

Parameters:

IsDir false: ignore edge directions and consider edges/paths as undirected (in case they are directed).

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).

Parameters:

IsDir false: ignore edge directions and consider edges/paths as undirected (in case they are directed).

template<class PGraph >

PNGraph TSnap::GetBfsTree	(	const PGraph &	Graph,
		const int &	StartNId,
		const bool &	FollowOut,
		const bool &	FollowIn
	)

Returns a directed Breath-First-Search tree rooted at StardNId. Returns a directed graph where a parent points to its childer. Tree is created by following in-links (parameter FollowIn = true) and/or out-links (parameter FollowOut = true).

void TSnap::GetBiCon	(	const PUNGraph &	Graph,
		TCnComV &	BiCnComV
	)

Returns all bi-connected components of a Graph.

Parameters:

BiCnComV is a vector of bi-connected components. Each component is defined by the IDs of its member nodes.

void TSnap::GetBiConSzCnt	(	const PUNGraph &	Graph,
		TIntPrV &	SzCntV
	)

Returns a distribution of bi-connected component sizes.

Parameters:

SzCntV returns a set of pairs (number of nodes in the bi-component, number of such components)

double TSnap::GetClosenessCentr	(	const PUNGraph &	Graph,
		const int &	NId
	)

Returns Closeness centrality of a given node NId. Closeness centrality of a node is defined as 1/FarnessCentrality.

template<class PGraph >

double TSnap::GetClustCf	(	const PGraph &	Graph,
		int	SampleNodes = `-1`
	)

Computes the average clustering coefficient as defined in Watts and Strogatz, Collective dynamics of 'small-world' networks.

template<class PGraph >

double TSnap::GetClustCf	(	const PGraph &	Graph,
		TFltPrV &	DegToCCfV,
		int	SampleNodes = `-1`
	)

Computes the distribution of average clustering coefficient.

Parameters:

DegToCCfV	Vector of pairs (degree, avg. clustering coefficient of nodes of that degree).
SampleNodes	If !=-1 then compute clustering coefficient only for a random sample of SampleNodes nodes. Useful for approximate but quick computations.

template<class PGraph >

double TSnap::GetClustCf	(	const PGraph &	Graph,
		TFltPrV &	DegToCCfV,
		int &	ClosedTriads,
		int &	OpenTriads,
		int	SampleNodes = `-1`
	)

Computes the distribution of average clustering coefficient as well as the number of open and closed triads in the graph.

Parameters:

DegToCCfV	Vector of pairs (degree, avg. clustering coefficient of nodes of that degree).
SampleNodes	If !=-1 then compute clustering coefficient only for a random sample of SampleNodes nodes. Useful for approximate but quick computations.

template<class PGraph >

int TSnap::GetCmnNbrs	(	const PGraph &	Graph,
		const int &	NId1,
		const int &	NId2
	)

Returns a number of shared neighbors between a pair of nodes NId1 and NId2.

template<class PGraph >

int TSnap::GetCmnNbrs	(	const PGraph &	Graph,
		const int &	NId1,
		const int &	NId2,
		TIntV &	NbrV
	)

Returns the shared neighbors between a pair of nodes NId1 and NId2.

template<>

int TSnap::GetCmnNbrs< PUNGraph >	(	const PUNGraph &	Graph,
		const int &	NId1,
		const int &	NId2,
		TIntV &	NbrV
	)		`[inline]`

template<class PGraph >

void TSnap::GetDegCnt	(	const PGraph &	Graph,
		TIntPrV &	DegToCntV
	)

TODO ROK document GetDegCnt()

double TSnap::GetDegreeCentr	(	const PUNGraph &	Graph,
		const int &	NId
	)

Returns Degree centrality of a given node NId. Degree centrality if a node is defined as its degree/(N-1), where N is the number of nodes in the network.

template<class PGraph >

void TSnap::GetDegSeqV	(	const PGraph &	Graph,
		TIntV &	DegV
	)

TODO ROK document GetDegSeqV()

template<class PGraph >

void TSnap::GetDegSeqV	(	const PGraph &	Graph,
		TIntV &	InDegV,
		TIntV &	OutDegV
	)

TODO ROK document GetDegSeqV()

template<class PGraph , class TEdgeDat >

PGraph TSnap::GetEDatSubGraph	(	const PGraph &	Graph,
		const TEdgeDat &	EDat,
		const int &	Cmp
	)

Returns a subgraph of graph Graph with edges where edge data matches the parameters.

EDat provides the value for edge data matching. Cmp determines the comparison function. Edges whose edge data matches EDat are included in the resulting subgraph as well as all the nodes which connect to at least one edge in the subgraph. Node IDs are preserved. Nodes in the resulting subgraph have the same node IDs as nodes in Graph.

Values of Cmp can be -1, 0, or +1. If Cmp is -1, edges with edge data less than EDat are included in the resulting subgraph. If Cmp equals 0, the values of edge data and EDat have to match. If Cmp is +1, edge data has to be greater than EDat.

template<class PGraph , class TEdgeDat >

PGraph TSnap::GetEDatSubGraph	(	const PGraph &	Graph,
		const TIntV &	NIdV,
		const TEdgeDat &	EDat,
		const int &	Cmp
	)

Returns a subgraph of graph Graph with NIdV nodes and edges where edge data matches the parameters.

The resulting subgraph contains all the nodes from Graph, which have node IDs in the NIdV vector and edges with both nodes in NIdV and whose edge data matches the parameters. Node IDs are preserved. Nodes in the resulting subgraph have the same node IDs as nodes in Graph.

EDat provides the value for edge data matching. Cmp determines the comparison function. Values of Cmp can be -1, 0, or +1. If Cmp is -1, edges with edge data less than EDat are included in the resulting subgraph. If Cmp equals 0, the values of edge data and EDat have to match. If Cmp is +1, edge data has to be greater than EDat.

void TSnap::GetEdgeBridges	(	const PUNGraph &	Graph,
		TIntPrV &	EdgeV
	)

Returns bridge edges of a Graph. Edge is a bridge if when removed increases the number of connected components. See http://en.wikipedia.org/wiki/Bridge_(graph_theory)

template<typename PGraph >

void TSnap::GetEdgesInOut	(	const PGraph &	Graph,
		const TIntV &	NIdV,
		int &	EdgesIn,
		int &	EdgesOut
	)

Returns the number of edges between the nodes NIdV and the edges pointing outside the set NIdV.

Parameters:

EdgesIn	Number of edges between the nodes NIdV.
EdgesOut	Number of edges between the nodes in NIdV and the rest of the graph.

void TSnap::GetEigenVectorCentr	(	const PUNGraph &	Graph,
		TIntFltH &	NIdEigenH,
		const double &	Eps = `1e-4`,
		const int &	MaxIter = `100`
	)

Computes Eigenvector Centrality of all nodes in the network Eigenvector Centrality of a node N is defined recursively as the average of centrality values of N's neighbors in the network.

void TSnap::GetEigVals	(	const PUNGraph &	Graph,
		const int &	EigVals,
		TFltV &	EigValV
	)

Computes top EigVals eigenvalues of the adjacency matrix representing a given undirected Graph.

void TSnap::GetEigVec	(	const PUNGraph &	Graph,
		TFltV &	EigVecV
	)

Computes the leading eigenvector of the adjacency matrix representing a given undirected Graph.

void TSnap::GetEigVec	(	const PUNGraph &	Graph,
		const int &	EigVecs,
		TFltV &	EigValV,
		TVec< TFltV > &	EigVecV
	)

Computes top EigVecs eigenvalues and eigenvectors of the adjacency matrix representing a given undirected Graph.

template<class PGraph >

PGraph TSnap::GetESubGraph	(	const PGraph &	Graph,
		const TIntV &	EIdV
	)

Returns a subgraph of graph Graph with EIdV edges.

The resulting subgraph contains all the edges from Graph, which have edge IDs in the EIdV vector and all the nodes which connect to at least one edge in EIdV. Node and edge IDs are preserved. Nodes and edges in the resulting subgraph have the same IDs as in Graph.

Use this function for multi-graphs, where the edges have edge IDs.

double TSnap::GetFarnessCentr	(	const PUNGraph &	Graph,
		const int &	NId
	)

Returns Farness centrality of a given node NId. Farness centrality of a node is the average shortest path length to all other nodes that reside is the same connected component as the given node.

TStr TSnap::GetFlagStr ( const TGraphFlag & GraphFlag )

Returns a string representation of a flag.

template<class PGraph >

void TSnap::GetHits	(	const PGraph &	Graph,
		TIntFltH &	NIdHubH,
		TIntFltH &	NIdAuthH,
		const int &	MaxIter = `20`
	)

HITS: Hubs and Authorities For more info see: http://en.wikipedia.org/wiki/HITS_algorithm)

template<class PGraph >

void TSnap::GetInDegCnt	(	const PGraph &	Graph,
		TIntPrV &	DegToCntV
	)

TODO ROK document GetInDegCnt()

void TSnap::GetInvParticipRat	(	const PUNGraph &	Graph,
		int	MaxEigVecs,
		int	TimeLimit,
		TFltPrV &	EigValIprV
	)

Computes Inverse participation ratio of a given graph. See Spectra of "real-world" graphs: Beyond the semicircle law by Farkas, Derenyi, Barabasi and Vicsek

template<class PGraph >

PGraph TSnap::GetKCore	(	const PGraph &	Graph,
		const int &	K
	)

Returns the K-core of a graph. If the core of order K does not exist the function returns an empty graph.

template<class PGraph >

int TSnap::GetLen2Paths	(	const PGraph &	Graph,
		const int &	NId1,
		const int &	NId2
	)

Returns the number of length 2 directed paths between a pair of nodes NId1, NId2 (NId1 --> U --> NId2).

template<class PGraph >

int TSnap::GetLen2Paths	(	const PGraph &	Graph,
		const int &	NId1,
		const int &	NId2,
		TIntV &	NbrV
	)

Returns the 2 directed paths between a pair of nodes NId1, NId2 (NId1 --> U --> NId2). NbrV intermediary stores nodes U.

template<typename PGraph >

double TSnap::GetModularity	(	const PGraph &	G,
		const TIntV &	NIdV,
		int	GEdges = `-1`
	)

Computes Modularity score of a set of nodes NIdV in a graph G. The function runs much faster if the number of edges in graph G is given (GEdges parameter).

Computes Modularity score of a set of communities (each community is defined by its member nodes) in a graph G. The function runs much faster if the number of edges in graph G is given (GEdges parameter).

template<class PGraph >

PGraph TSnap::GetMxBiCon ( const PGraph & Graph )

Returns a graph representing the largest bi-connected component on an input Graph. An undirected graph is bi-connected if by removing any single node does not disconnect the graph. http://en.wikipedia.org/wiki/Biconnected_component

PUNGraph TSnap::GetMxBiCon	(	const PUNGraph &	Graph,
		const bool &	RenumberNodes = `false`
	)

Returns a graph representing the largest bi-connected component on an undirected Graph. An undirected graph is bi-connected if by removing any single node does not disconnect the graph. http://en.wikipedia.org/wiki/Biconnected_component

Parameters:

RenumberNodes if true, then node IDs of the returned graph will not match those of Graph, instead they will have a range 0...N-1.

template<class PGraph >

int TSnap::GetMxDegNId ( const PGraph & Graph )

Returns a randomly chosen node from all the nodes with the maximum degree.

template<class PGraph >

int TSnap::GetMxInDegNId ( const PGraph & Graph )

Returns a randomly chosen node from all the nodes with the maximum in-degree.

template<class PGraph >

int TSnap::GetMxOutDegNId ( const PGraph & Graph )

Returns a randomly chosen node from all the nodes with the maximum out-degree.

template<class PGraph >

PGraph TSnap::GetMxScc ( const PGraph & Graph )

Returns a graph representing the largest strongly connected component on an input Graph. A directed graph is strongly connected if there exists a directed path from any vertex to any other vertex in the graph. See http://en.wikipedia.org/wiki/Strongly_connected_component

template<class PGraph >

PGraph TSnap::GetMxWcc ( const PGraph & Graph )

Returns a graph representing the largest weakly connected component on an input Graph. A directed/undirected graph is connected if there exist an undirected path between any pair of nodes. See http://en.wikipedia.org/wiki/Connected_component_(graph_theory)

template<class PGraph >

double TSnap::GetMxWccSz ( const PGraph & Graph )

Returns the fraction of nodes in the largest weakly connected component of a Graph.

template<class PGraph >

double TSnap::GetNodeClustCf	(	const PGraph &	Graph,
		const int &	NId
	)

Returns clustering coefficient of a particular node.

template<class PGraph >

void TSnap::GetNodeClustCf	(	const PGraph &	Graph,
		TIntFltH &	NIdCCfH
	)

Computes clustering coefficient of each node of the Graph.

template<class PGraph >

int TSnap::GetNodeEcc	(	const PGraph &	Graph,
		const int &	NId,
		const bool &	IsDir = `false`
	)

Returns node Eccentricity, the largest shortest-path distance from the node NId to any other node in the Graph.

Parameters:

IsDir false: ignore edge directions and consider edges as undirected (in case they are directed).

template<class PGraph >

void TSnap::GetNodeInDegV	(	const PGraph &	Graph,
		TIntPrV &	NIdInDegV
	)

template<class PGraph >

void TSnap::GetNodeOutDegV	(	const PGraph &	Graph,
		TIntPrV &	NIdOutDegV
	)

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. false: ignore edge directions and consider edges/paths as undirected (in case they are directed).

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. false: ignore edge directions and consider edges/paths as undirected (in case they are directed).

template<class PGraph >

int TSnap::GetNodeTriads	(	const PGraph &	Graph,
		const int &	NId
	)

Returns number of undirected triads a node NId participates in.

template<class PGraph >

int TSnap::GetNodeTriads	(	const PGraph &	Graph,
		const int &	NId,
		int &	ClosedTriads,
		int &	OpenTriads
	)

Returns number of undirected Open and Closed triads a node NId participates in.

template<class PGraph >

int TSnap::GetNodeTriads	(	const PUNGraph &	Graph,
		const int &	NId,
		const TIntSet &	GroupSet,
		int &	InGroupEdges,
		int &	InOutGroupEdges
	)

Returns the number of triads between a node NId and a subset of its neighbors GroupSet.

Parameters:

InGroupEdges	Number of triads triads (NId, g1, g2), where g1 and g2 are in GroupSet
InOutGroupEdges	Number of triads (NId, g1, o1), where g1 in GroupSet and o1 not in GroupSet

template<class PGraph >

int TSnap::GetNodeTriads	(	const PUNGraph &	Graph,
		const int &	NId,
		const TIntSet &	GroupSet,
		int &	InGroupEdges,
		int &	InOutGroupEdges,
		int &	OutGroup
	)

Returns the number of triads between a node NId and a subset of its neighbors GroupSet.

Parameters:

InGroupEdges	Number of triads (NId, g1, g2), where g1 and g2 are in GroupSet
InOutGroupEdges	Number of triads (NId, g1, o1), where g1 in GroupSet and o1 not in GroupSet
OutGroupEdges	Number of triads (NId, p1, o1), where o1 and o2 are not in GroupSet

template<class PGraph >

int TSnap::GetNodeTriads	(	const PGraph &	Graph,
		const int &	NId,
		const TIntSet &	GroupSet,
		int &	InGroupEdges,
		int &	InOutGroupEdges
	)

template<class PGraph >

int TSnap::GetNodeTriads	(	const PGraph &	Graph,
		const int &	NId,
		const TIntSet &	GroupSet,
		int &	InGroupEdges,
		int &	InOutGroupEdges,
		int &	OutGroupEdges
	)

template<class PGraph >

void TSnap::GetNodeWcc	(	const PGraph &	Graph,
		const int &	NId,
		TIntV &	CnCom
	)

Returns (via output parameter CnCom) all nodes that are in the same connected component as node NId.

template<class PGraph >

void TSnap::GetOutDegCnt	(	const PGraph &	Graph,
		TIntPrV &	DegToCntV
	)

TODO ROK document GetOutDegCnt()

template<class PGraph >

void TSnap::GetPageRank	(	const PGraph &	Graph,
		TIntFltH &	PRankH,
		const double &	C = `0.85`,
		const double &	Eps = `1e-4`,
		const int &	MaxIter = `100`
	)

PageRank For more info see: http://en.wikipedia.org/wiki/PageRank

template<class PGraph >

PGraph TSnap::GetRndESubGraph	(	const PGraph &	Graph,
		const int &	NEdges
	)

Returns a random subgraph of graph Graph with NEdges edges.

Randomly selects NEdges edges from the input graph and returns a subgraph on those edges.

template<class PGraph >

PGraph TSnap::GetRndSubGraph	(	const PGraph &	Graph,
		const int &	NNodes
	)

Returns an induced random subgraph of graph Graph with NNodes nodes.

Randomly selects NNodes nodes from the input graph and returns an induced graph on those nodes.

template<class PGraph >

void TSnap::GetSccs	(	const PGraph &	Graph,
		TCnComV &	CnComV
	)

Returns all strongly connected components in a Graph.

Parameters:

CnComV is a vector of connected components. Each component is defined by the IDs of its member nodes.

template<class PGraph >

void TSnap::GetSccSzCnt	(	const PGraph &	Graph,
		TIntPrV &	SccSzCnt
	)

Returns a distribution of strongly connected component sizes.

Parameters:

SccSzCnt returns a set of pairs (number of nodes in the component, number of such components)

template<class PGraph >

int TSnap::GetShortPath	(	const PGraph &	Graph,
		const int &	SrcNId,
		const int &	DstNId,
		const bool &	IsDir = `false`
	)

Returns the lenght of the shortest path from node SrcNId to node DstNId.

Parameters:

IsDir false: ignore edge directions and consider edges/paths as undirected (in case they are directed).

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 lenght of the shortest path from node SrcNId to all other nodes in the network.

Parameters:

IsDir	false: ignore edge directions and consider edges/paths as undirected (in case they are directed).
MaxDist	Maximum number of hops that BFS expands to. This is helpful for speeding-up the code if one in interested only in nodes less than MaxDist away from SrcNId.
NIdToDistH	Maps node ID to shortest path distance. NIdToDistH contains only nodes that are reachable from SrcNId.

void TSnap::GetSngVals	(	const PNGraph &	Graph,
		const int &	SngVals,
		TFltV &	SngValV
	)

Computes largest SngVals singular values of the adjacency matrix representing a directed Graph.

void TSnap::GetSngVec	(	const PNGraph &	Graph,
		TFltV &	LeftSV,
		TFltV &	RightSV
	)

Computes the leading left and right singular vector of the adjacency matrix representing a directed Graph.

void TSnap::GetSngVec	(	const PNGraph &	Graph,
		const int &	SngVecs,
		TFltV &	SngValV,
		TVec< TFltV > &	LeftSV,
		TVec< TFltV > &	RightSV
	)

Computes the singular values and left and right singular vectors of the adjacency matrix representing a directed Graph.

Parameters:

SngVecs Number of singular values/vectors to compute.

PUNGraph TSnap::GetSubGraph	(	const PUNGraph &	Graph,
		const TIntV &	NIdV,
		const bool &	RenumberNodes = `false`
	)

Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumbering.

The resulting subgraph contains all the nodes from Graph, which have node IDs in the NIdV vector and all the edges with both nodes in NIdV. Parameter RenumberNodes determines, whether the node IDs are preserved or not. If RenumberNodes is false, then nodes in the resulting subgraph have the same node IDs as nodes in Graph. If RenumberNodes is true, then nodes in the resulting subgraph are renumbered sequentially from 0 to N-1. By default, the nodes are not renumbered.

template<class PGraph >

PGraph TSnap::GetSubGraph	(	const PGraph &	Graph,
		const TIntV &	NIdV
	)

Returns an induced subgraph of graph Graph with NIdV nodes.

The resulting subgraph contains all the nodes from Graph, which have node IDs in the NIdV vector and all the edges with both nodes in NIdV. Node IDs are preserved. Nodes in the resulting subgraph have the same node IDs as nodes in Graph.

template<class PGraph >

int TSnap::GetSubTreeSz	(	const PGraph &	Graph,
		const int &	StartNId,
		const bool &	FollowOut,
		const bool &	FollowIn,
		int &	TreeSz,
		int &	TreeDepth
	)

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::GetTreeRootNId ( const PGraph & Graph )

template<class PGraph >

void TSnap::GetTreeSig	(	const PGraph &	Graph,
		const int &	RootNId,
		TIntV &	Sig
	)

template<class PGraph >

void TSnap::GetTreeSig	(	const PGraph &	Graph,
		const int &	RootNId,
		TIntV &	Sig,
		TIntPrV &	NodeMap
	)

template<class PGraph >

int TSnap::GetTriadEdges	(	const PGraph &	Graph,
		int	SampleEdges = `-1`
	)

Counts the number of edges that participate in at least one triad

Parameters:

SampleNodes If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations.

template<class PGraph >

void TSnap::GetTriadParticip	(	const PGraph &	Graph,
		TIntPrV &	TriadCntV
	)

Triangle Participation Ratio: For each node counts how many triangles it participates in and then returns a set of pairs (number of triangles, number of such nodes).

template<class PGraph >

int TSnap::GetTriads	(	const PGraph &	Graph,
		int	SampleNodes = `-1`
	)

Returns the number of triangles in a graph. Function returns the number of unique triples of connected nodes (regardless of the number of edges between each pair of nodes).

Parameters:

SampleNodes If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations.

template<class PGraph >

void TSnap::GetTriads	(	const PGraph &	Graph,
		TIntTrV &	NIdCOTriadV,
		int	SampleNodes = `-1`
	)

Computes the number of open and close triads for every node of the network.

Parameters:

NIdCOTriadV	Triple (node id, open triads: number of pairs of node's neighbors that are not connected, closed triads: number of pairs of node's neighbors that are connected between themselves).
SampleNodes	If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations.

template<class PGraph >

int TSnap::GetTriads	(	const PGraph &	Graph,
		int &	ClosedTriads,
		int &	OpenTriads,
		int	SampleNodes = `-1`
	)

Computes the number of Closed and Open triads.

Parameters:

SampleNodes If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations.

template<class PGraph >

PGraph TSnap::GetUnDir ( const PGraph & Graph )

template<class PGraph >

void TSnap::GetWccs	(	const PGraph &	Graph,
		TCnComV &	CnComV
	)

Returns all weakly connected components in a Graph.

Parameters:

CnComV is a vector of connected components. Each component is defined by the IDs of its member nodes.

template<class PGraph >

void TSnap::GetWccSzCnt	(	const PGraph &	Graph,
		TIntPrV &	WccSzCnt
	)

Returns a distribution of weakly connected component sizes.

Parameters:

WccSzCnt returns a set of pairs (number of nodes in the component, number of such components)

bool TSnap::IsAllValVNeg	(	TFltV &	ValV,
		const bool &	InvertSign
	)

template<class PGraph >

bool TSnap::IsConnected ( const PGraph & Graph )

Tests whether the Graph is (weakly) connected.

template<class PGraph >

bool TSnap::IsTree	(	const PGraph &	Graph,
		int &	RootNId
	)

template<class PGraph >

bool TSnap::IsWeaklyConn ( const PGraph & Graph )

Tests whether the Graph is weakly connected.

template<class PGraph >

PGraph TSnap::LoadConnList ( const TStr & InFNm )

Loads a (directed, undirected or multi) graph from a text file InFNm with 1 node and all its edges in a single line.

Whitespace separated file of several columns: <source node="" id>=""> <destination node="" id1>=""> <destination node="" id2>=""> ... First colum of each line contains a source node id followed by ids of the destination nodes. For example, '1 2 3' encodes edges 1-->2 and 1-->3. Note that this format allows for saving isolated nodes.

template<class PGraph >

PGraph TSnap::LoadConnListStr	(	const TStr &	InFNm,
		TStrHash< TInt > &	StrToNIdH
	)

Loads a (directed, undirected or multi) graph from a text file InFNm with 1 node and all its edges in a single line.

Whitespace separated file of several columns: <source node="" name>=""> <destination node name 1> <destination node name 2> ... First colum of each line contains a source node name followed by ids of the destination nodes. For example, 'A B C' encodes edges A-->B and A-->C. Note that this format allows for saving isolated nodes. stores the mapping from node names to node ids.

PNGraph TSnap::LoadDyNet ( const TStr & FNm )

For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php)

Loads a directed network in the DyNetML format. Loads only the first network in the file FNm.

TVec< PNGraph > TSnap::LoadDyNetGraphV ( const TStr & FNm )

For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php)

Loads directed networks in the DyNetML format. Loads all the networks in the file FNm.

template<class PGraph >

PGraph TSnap::LoadEdgeList	(	const TStr &	InFNm,
		const int &	SrcColId,
		const int &	DstColId
	)

Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, integer node ids).

Whitespace separated file of several columns: ... <source node="" id>=""> ... <destination node="" id>=""> ... SrcColId and DstColId are column indexes of source/destination (integer!) node ids. This means there is one edge per line and node IDs are assumed to be integers. The function loads the format saved by TSnap::SaveEdgeList()

template<class PGraph >

PGraph TSnap::LoadEdgeList	(	const TStr &	InFNm,
		const int &	SrcColId,
		const int &	DstColId,
		const char &	Separator
	)

Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line ('Separator' separated columns, integer node ids).

'Separator' separated file of several columns: ... <source node="" id>=""> ... <destination node="" id>=""> ... SrcColId and DstColId are column indexes of source/destination (integer!) node ids. This means there is one edge per line and node IDs are assumed to be integers. The function loads the format saved by TSnap::SaveEdgeList() if we set Separator=''.

template<class PGraph >

PGraph TSnap::LoadEdgeListStr	(	const TStr &	InFNm,
		const int &	SrcColId,
		const int &	DstColId
	)

Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, arbitrary string node ids).

Whitespace separated file of several columns: ... <source node="" id>=""> ... <destination node="" id>=""> ... SrcColId and DstColId are column indexes of source/destination (string) node ids. This means there is one edge per line and node IDs can be arbitrary STRINGs. Note that the mapping of node names to ids is discarded.

template<class PGraph >

PGraph TSnap::LoadEdgeListStr	(	const TStr &	InFNm,
		const int &	SrcColId,
		const int &	DstColId,
		TStrHash< TInt > &	StrToNIdH
	)

Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, arbitrary string node ids).

Whitespace separated file of several columns: ... <source node="" id>=""> ... <destination node="" id>=""> ... SrcColId and DstColId are column indexes of source/destination (string) node ids. This means there is one edge per line and node IDs can be arbitrary STRINGs. The mapping of strings to node ids in stored in StrToNIdH. To map between node names and ids use: NId = StrToNIdH.GetKeyId(NodeName) and TStr NodeName = StrToNIdH[NId];

template<class PGraph >

PGraph TSnap::LoadPajek ( const TStr & InFNm )

Loads a (directed, undirected or multi) graph from Pajek .PAJ format file. Function supports both the 1 edge per line (<source> <destination> <weight>) as well as the 1 node per line (<source> <destination1> <destination2> ...) formats.

template<class PGraph >

void TSnap::MakeUnDir ( const PGraph & Graph )

template<class PGraph >

void TSnap::PlotClustCf	(	const PGraph &	Graph,
		const TStr &	FNmPref,
		TStr	DescStr = `TStr()`
	)

Plots the distribution of clustering coefficient of a Graph.

void TSnap::PlotEigValDistr	(	const PUNGraph &	Graph,
		const int &	EigVals,
		const TStr &	FNmPref,
		TStr	DescStr
	)

Plots the distribution of components of the leading eigen-vector of the Graph adjacency matrix. Plots first EigVals values.

void TSnap::PlotEigValRank	(	const PUNGraph &	Graph,
		const int &	EigVals,
		const TStr &	FNmPref,
		TStr	DescStr
	)

Plots the eigen-value rank distribution of the Graph adjacency matrix. Plots first EigVals eigenvalues.

template<class PGraph >

void TSnap::PlotHops	(	const PGraph &	Graph,
		const TStr &	FNmPref,
		const TStr &	DescStr,
		const bool &	IsDir = `false`,
		const int &	NApprox = `32`
	)

Plots the cumulative distribution of the shortest path lengths of a Graph. Implementation is based on ANF.

Parameters:

IsDir false: ignore edge directions and consider graph as undirected.

template<class PGraph >

void TSnap::PlotInDegDistr	(	const PGraph &	Graph,
		const TStr &	FNmPref,
		TStr	DescStr = `TStr()`,
		const bool &	PlotCCdf = `false`,
		const bool &	PowerFit = `false`
	)

Plots the in-degree distribution of a Graph.

Parameters:

PlotCCdf	Plots the distribution as a Complementary Cummulative distribution function.
PowerFit	Fits a Power-Law to the distribution.

void TSnap::PlotInvParticipRat	(	const PUNGraph &	Graph,
		const int &	MaxEigVecs,
		const int &	TimeLimit,
		const TStr &	FNmPref,
		TStr	DescStr = `TStr()`
	)

Plots the inverse participation ratio. See Spectra of "real-world" graphs: Beyond the semicircle law by Farkas, Derenyi, Barabasi and Vicsek.

template<class PGraph >

void TSnap::PlotOutDegDistr	(	const PGraph &	Graph,
		const TStr &	FNmPref,
		TStr	DescStr = `TStr()`,
		const bool &	PlotCCdf = `false`,
		const bool &	PowerFit = `false`
	)

Plots the out-degree distribution of a Graph.

Parameters:

PlotCCdf	Plots the distribution as a Complementary Cumulative Distribution Function (CCDF).
PowerFit	Fits a Power-Law to the distribution.

template<class PGraph >

void TSnap::PlotSccDistr	(	const PGraph &	Graph,
		const TStr &	FNmPref,
		TStr	DescStr = `TStr()`
	)

Plots the distribution of sizes of strongly connected components of a Graph.

template<class PGraph >

void TSnap::PlotShortPathDistr	(	const PGraph &	Graph,
		const TStr &	FNmPref,
		TStr	DescStr = `TStr()`,
		int	TestNodes = `TInt::Mx`
	)

Plots the distribution of the shortest path lengths of a Graph. Implementation is based on BFS.

void TSnap::PlotSngValDistr	(	const PNGraph &	Graph,
		const int &	SngVals,
		const TStr &	FNmPref,
		TStr	DescStr
	)

Plots the rank distribution of singular values of the Graph adjacency matrix. Plots first SngVals values.

void TSnap::PlotSngValRank	(	const PNGraph &	Graph,
		const int &	SngVals,
		const TStr &	FNmPref,
		TStr	DescStr
	)

Plots the rank distribution of singular values of the Graph adjacency matrix. Plots first SngVals values.

void TSnap::PlotSngVec	(	const PNGraph &	Graph,
		const TStr &	FNmPref,
		TStr	DescStr
	)

Plots the distribution of the values of the leading left singular vector of the Graph adjacency matrix. Plots first SngVals values.

template<class PGraph >

void TSnap::PlotWccDistr	(	const PGraph &	Graph,
		const TStr &	FNmPref,
		TStr	DescStr = `TStr()`
	)

Plots the distribution of sizes of weakly connected components of a Graph.

template<class PGraph >

void TSnap::PrintInfo	(	const PGraph &	Graph,
		const TStr &	Desc = `""`,
		const TStr &	OutFNm = `""`,
		const bool &	Fast = `true`
	)

Prints basic graph statistics.

Parameters:

Fast	true: only computes basic statistics (that can be computed fast). For more extensive information (and longer execution times) set Fast = false.

template<class PGraph >

void TSnap::SaveEdgeList	(	const PGraph &	Graph,
		const TStr &	OutFNm,
		const TStr &	Desc = `TStr()`
	)

Saves a graph into a text file. Each line contains two columsn and encodes a single edge: <source node="" id>=""><tab><destination node="" id>="">

template<class PGraph >

void TSnap::SaveGViz	(	const PGraph &	Graph,
		const TStr &	OutFNm,
		const TStr &	Desc = `TStr()`,
		const bool &	NodeLabels = `false`,
		const TIntStrH &	NIdColorH = `TIntStrH()`
	)

Save a graph in GraphVizp .DOT format.

Parameters:

NIdColorH Maps node ids to node colors (see GraphViz documentation for more details).

template<class PGraph >

void TSnap::SaveGViz	(	const PGraph &	Graph,
		const TStr &	OutFNm,
		const TStr &	Desc,
		const TIntStrH &	NIdLabelH
	)

Save a graph in GraphVizp .DOT format.

Parameters:

NIdLabelH Maps node ids to node string labels.

template<class PGraph >

void TSnap::SaveMatlabSparseMtx	(	const PGraph &	Graph,
		const TStr &	OutFNm
	)

Saves a graph in a MATLAB sparse matrix format.

Each line contains a tuple of 3 values: <source node="" id>=""><tab><destination node="" id>=""><tab>1.

template<class PGraph >

void TSnap::SavePajek	(	const PGraph &	Graph,
		const TStr &	OutFNm
	)

Saves a graph in a Pajek .NET format.

template<class PGraph >

void TSnap::SavePajek	(	const PGraph &	Graph,
		const TStr &	OutFNm,
		const TIntStrH &	NIdColorH
	)

Saves a graph in a Pajek .NET format.

NIdColorH maps node ids to node colors. Default node color is Red. See http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf for a list of supported color names.

template<class PGraph >

void TSnap::SavePajek	(	const PGraph &	Graph,
		const TStr &	OutFNm,
		const TIntStrH &	NIdColorH,
		const TIntStrH &	NIdLabelH
	)

Saves a graph in a Pajek .NET format.

NIdColorH maps node ids to node colors. Default node color is Red. NIdLabelH maps node ids to node string labels. See http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf for a list of supported color names.

template<class PGraph >

void TSnap::SavePajek	(	const PGraph &	Graph,
		const TStr &	OutFNm,
		const TIntStrH &	NIdColorH,
		const TIntStrH &	NIdLabelH,
		const TIntStrH &	EIdColorH
	)

Saves a graph in a Pajek .NET format.

NIdColorH maps node ids to node colors. Default node color is Red. NIdLabelH maps node ids to node string labels. EIdColorH maps edge ids to node colors. Default edge color is Black. See http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf for a list of supported color names.

void TSnap::SetAllInvertSign	(	TFltV &	ValV,
		const double &	Val
	)

template<class PGraph >

void TSnap::TestAnf ( )

Namespaces

Classes

Functions

Detailed Description

Function Documentation