TSnap Namespace Reference

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

Namespaces
	TSnapDetail

Classes
struct	IsBipart
	Tests (at compile time) if the graph is a bipartite graph type. More...
struct	IsBipart< TBPGraph >
struct	IsDirected
	Tests (at compile time) if the graph is directed. More...
struct	IsDirected< TBigNet< TNodeData, IsDir > >
struct	IsDirected< TBigNet< TNodeData, true > >
struct	IsDirected< TDirNet >
struct	IsDirected< TModeNet >
struct	IsDirected< TNEANet >
struct	IsDirected< TNEANetMP >
struct	IsDirected< TNEGraph >
struct	IsDirected< TNGraph >
struct	IsDirected< TNGraphMP >
struct	IsDirected< TNodeEDatNet< TNodeData, TEdgeData > >
struct	IsDirected< TNodeEdgeNet< TNodeData, TEdgeData > >
struct	IsDirected< TNodeNet< TNodeData > >
struct	IsDirected< TTimeNENet >
struct	IsDirected< TTimeNet >
struct	IsEdgeDat
	Tests (at compile time) if the graph is a network with data on edges. More...
struct	IsEdgeDat< TNodeEDatNet< TNodeData, TEdgeData > >
struct	IsEdgeDat< TNodeEdgeNet< TNodeData, TEdgeData > >
struct	IsEdgeDat< TTimeNENet >
struct	IsMultiGraph
	Tests (at compile time) if the graph is a multigraph with multiple edges between the same nodes. More...
struct	IsMultiGraph< TModeNet >
struct	IsMultiGraph< TNEANet >
struct	IsMultiGraph< TNEANetMP >
struct	IsMultiGraph< TNEGraph >
struct	IsMultiGraph< TNodeEdgeNet< TNodeData, TEdgeData > >
struct	IsMultiGraph< TTimeNENet >
struct	IsNodeDat
	Tests (at compile time) if the graph is a network with data on nodes. More...
struct	IsNodeDat< TBigNet< TNodeData, IsDir > >
struct	IsNodeDat< TNodeEDatNet< TNodeData, TEdgeData > >
struct	IsNodeDat< TNodeEdgeNet< TNodeData, TEdgeData > >
struct	IsNodeDat< TNodeNet< TNodeData > >
struct	IsNodeDat< TTimeNENet >
struct	IsNodeDat< TTimeNet >
struct	IsSources
	Tests (at compile time) if the nodes store only out-edges, but not in-edges. More...
class	TPRManager
	Push relabel attr manager. More...

Functions
template<class PGraph >
int	CntInDegNodes (const PGraph &Graph, const int &NodeInDeg)
	Returns the number of nodes with in-degree NodeInDeg. More...
template<class PGraph >
int	CntOutDegNodes (const PGraph &Graph, const int &NodeOutDeg)
	Returns the number of nodes with out-degree NodeOutDeg. More...
template<class PGraph >
int	CntDegNodes (const PGraph &Graph, const int &NodeDeg)
	Returns the number of nodes with degree NodeDeg. More...
template<class PGraph >
int	CntNonZNodes (const PGraph &Graph)
	Returns the number of nodes with degree greater than 0. More...
template<class PGraph >
int	CntEdgesToSet (const PGraph &Graph, const int &NId, const TIntSet &NodeSet)
	Returns the number of nodes in NodeSet that have an edge to the node NId. More...
template<class PGraph >
int	GetMxDegNId (const PGraph &Graph)
	Returns a randomly chosen node from all the nodes with the maximum degree. More...
template<class PGraph >
int	GetMxInDegNId (const PGraph &Graph)
	Returns a randomly chosen node from all the nodes with the maximum in-degree. More...
template<class PGraph >
int	GetMxOutDegNId (const PGraph &Graph)
	Returns a randomly chosen node from all the nodes with the maximum out-degree. More...
template<class PGraph >
void	GetInDegCnt (const PGraph &Graph, TIntPrV &DegToCntV)
	Returns an in-degree histogram: a set of pairs (in-degree, number of nodes of such in-degree) More...
template<class PGraph >
void	GetInDegCnt (const PGraph &Graph, TFltPrV &DegToCntV)
	Returns an in-degree histogram: a set of pairs (in-degree, number of nodes of such in-degree) More...
template<class PGraph >
void	GetOutDegCnt (const PGraph &Graph, TIntPrV &DegToCntV)
	Returns an out-degree histogram: a set of pairs (out-degree, number of nodes of such out-degree) More...
template<class PGraph >
void	GetOutDegCnt (const PGraph &Graph, TFltPrV &DegToCntV)
	Returns an out-degree histogram: a set of pairs (out-degree, number of nodes of such out-degree) More...
template<class PGraph >
void	GetDegCnt (const PGraph &Graph, TIntPrV &DegToCntV)
	Returns a degree histogram: a set of pairs (degree, number of nodes of such degree) More...
template<class PGraph >
void	GetDegCnt (const PGraph &Graph, TFltPrV &DegToCntV)
	Returns a degree histogram: a set of pairs (degree, number of nodes of such degree) More...
template<class PGraph >
void	GetDegSeqV (const PGraph &Graph, TIntV &DegV)
	Returns a degree sequence vector. More...
template<class PGraph >
void	GetDegSeqV (const PGraph &Graph, TIntV &InDegV, TIntV &OutDegV)
	Returns an in- and out-degree sequence vectors. More...
template<class PGraph >
void	GetNodeInDegV (const PGraph &Graph, TIntPrV &NIdInDegV)
	Returns a vector of pairs (node id, node in-degree) More...
template<class PGraph >
void	GetNodeOutDegV (const PGraph &Graph, TIntPrV &NIdOutDegV)
	Returns a vector of pairs (node id, node out-degree) More...
template<class PGraph >
int	CntUniqUndirEdges (const PGraph &Graph)
	Counts unique undirected edges in the graph Graph. Nodes (u,v) (where u!=v) are connected via an undirected edge if there exists an edge in either direction (u,v) or (v,u). More...
template<class PGraph >
int	CntUniqDirEdges (const PGraph &Graph)
	Counts unique directed edges in the graph Graph. Nodes (u,v) (where u!=v) are connected via a directed edge if there exists a directed edge from node u to node v. More...
template<class PGraph >
int	CntUniqBiDirEdges (const PGraph &Graph)
	Counts unique bidirectional edges in the graph Graph. Edge is bidirectional if there exist directed edges in both directions: (u,v) and (v,u) More...
template<class PGraph >
int	CntSelfEdges (const PGraph &Graph)
	Counts the number of self-edges in a graph. Edge (u,u) is a self-edge. More...
template<class PGraph >
PGraph	GetUnDir (const PGraph &Graph)
	Returs an undirected version of the graph. For every edge (u,v) an edge (v,u) is added (if it does not yet exist). More...
template<class PGraph >
void	MakeUnDir (const PGraph &Graph)
	Makes the graph undirected. For every edge (u,v) an edge (v,u) is added (if it does not yet exist). More...
template<class PGraph >
void	AddSelfEdges (const PGraph &Graph)
	Adds a self-edge to every node in the graph. More...
template<class PGraph >
void	DelSelfEdges (const PGraph &Graph)
	Removes all the self-edges from the graph. More...
template<class PGraph >
void	DelNodes (PGraph &Graph, const TIntV &NIdV)
	Removes nodes with ids stored in NIdV from the graph. More...
template<class PGraph >
void	DelZeroDegNodes (PGraph &Graph)
	Removes all the zero-degree nodes, that isolated nodes, from the graph. More...
template<class PGraph >
void	DelDegKNodes (PGraph &Graph, const int &OutDegK, const int &InDegK)
	Removes all the node of out-degree OutDegK and all the nodes of in-degree InDegK from the graph. More...
template<class PGraph >
bool	IsTree (const PGraph &Graph, int &RootNIdX)
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)
	Returns a directed Breadth-First-Search tree rooted at StartNId. More...
template<class PGraph >
int	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. More...
template<class PGraph >
int	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. More...
template<class PGraph >
int	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. More...
template<class PGraph >
int	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. More...
template<class PGraph >
int	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. More...
template<class PGraph >
int	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). More...
template<class PGraph >
double	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). More...
template<class PGraph >
double	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). More...
template<class PGraph >
double	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). More...
template<class PGraph >
double	GetBfsEffDiamAll (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). More...
template<class PGraph >
double	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. More...
template<class PGraph >
int	GetShortestDistances (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, TIntV &ShortestDists)
template<class PGraph >
int	GetShortestDistancesMP2 (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, TIntV &ShortestDists)
PNGraph	CascGraphSource (PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W)
	Takes as input the column names of the PTable P as C1, C2,C3 and C4 and returns a directed graph of W-adjacent events. For graph generation events are sorted by C1. More...
PNGraph	CascGraphTime (PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W)
	Takes as input the column names of the PTable P as C1, C2,C3 and C4 and returns a directed graph of W-adjacent events. For graph generation events are sorted by C3. More...
PNGraph	CascGraph (PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W, bool SortParam=true)
	Takes as input the column names of the PTable P as C1, C2, C3 and C4 and returns a directed graph of W-adjacent events. By default calls CascGraphSource. Toggle SortParam to use CascGraphTime. More...
void	CascFind (PNGraph Graph, PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, TVec< TIntV > &TopCascVV, bool Print=false)
	Takes as input a directed graph and returns all the top cascades in TopCascVV. More...
void	CascFindMP (PNGraph Graph, PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, TVec< TIntV > &TopCascVV)
	Parallel implementaion of CascFind takes as input a directed graph and returns all the top cascades in TopCascVV. More...
double	GetDegreeCentr (const PUNGraph &Graph, const int &NId)
void	GetEigenVectorCentr (const PUNGraph &Graph, TIntFltH &NIdEigenH, const double &Eps, const int &MaxIter)
double	GetGroupDegreeCentr (const PUNGraph &Graph, const PUNGraph &Group)
double	GetGroupDegreeCentr0 (const PUNGraph &Graph, const TIntH &GroupNodes)
double	GetGroupDegreeCentr (const PUNGraph &Graph, const TIntH &GroupNodes)
double	GetGroupFarnessCentr (const PUNGraph &Graph, const TIntH &GroupNodes)
PUNGraph *	AllGraphsWithNNodes (int n)
TIntH *	AllCombinationsMN (int m, int n)
double	GetGroupClosenessCentr (const PUNGraph &Graph, const TIntH &GroupNodes)
TIntH	MaxCPGreedyBetter (const PUNGraph &Graph, const int k)
	Returns centrality Maximum k group. More...
TIntH	MaxCPGreedyBetter1 (const PUNGraph &Graph, const int k)
	Returns centrality Maximum k group. More...
TIntH	MaxCPGreedyBetter2 (const PUNGraph &Graph, const int k)
	Returns centrality Maximum k group. More...
TIntH	MaxCPGreedyBetter3 (const PUNGraph &Graph, const int k)
	Returns centrality Maximum k group. More...
int	GetWeightedPageRank (const PNEANet Graph, TIntFltH &PRankH, const TStr &Attr, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
	Weighted PageRank (TODO: Use template) More...
int	GetWeightedPageRankMP (const PNEANet Graph, TIntFltH &PRankH, const TStr &Attr, const double &C, const double &Eps, const int &MaxIter)
TIntFltH	EventImportance (const PNGraph &Graph, const int k)
	Event importance. More...
TIntFltH	EventImportance1 (const PNGraph &Graph, const int k)
int	Intersect (TUNGraph::TNodeI Node, TIntH NNodes)
	Intersect. More...
int	Intersect (TUNGraph::TNodeI Node, TStr NNodes)
	Intersect. More...
int	Intersect (TUNGraph::TNodeI Node, int *NNodes, int NNodes_br)
	Intersect. More...
int	Intersect1 (TUNGraph::TNodeI Node, TStr NNodes)
TIntH	LoadNodeList (TStr InFNmNodes)
int	findMinimum (TIntV &Frontier, TIntFltH &NIdDistH)
int	GetWeightedShortestPath (const PNEANet Graph, const int &SrcNId, TIntFltH &NIdDistH, const TFltV &Attr)
double	GetWeightedFarnessCentr (const PNEANet Graph, const int &NId, const TFltV &Attr, const bool &Normalized, const bool &IsDir)
double	GetWeightedClosenessCentr (const PNEANet Graph, const int &NId, const TFltV &Attr, const bool &Normalized, const bool &IsDir)
void	GetWeightedBetweennessCentr (const PNEANet Graph, const TIntV &BtwNIdV, TIntFltH &NodeBtwH, const bool &DoNodeCent, TIntPrFltH &EdgeBtwH, const bool &DoEdgeCent, const TFltV &Attr, const bool &IsDir)
	Computes (approximate) weighted Beetweenness Centrality of all nodes and all edges of the network. More...
void	GetWeightedBetweennessCentr (const PNEANet Graph, TIntFltH &NodeBtwH, TIntPrFltH &EdgeBtwH, const TFltV &Attr, const double &NodeFrac, const bool &IsDir)
void	GetWeightedBetweennessCentr (const PNEANet Graph, TIntFltH &NodeBtwH, const TFltV &Attr, const double &NodeFrac, const bool &IsDir)
void	GetWeightedBetweennessCentr (const PNEANet Graph, TIntPrFltH &EdgeBtwH, const TFltV &Attr, const double &NodeFrac, const bool &IsDir)
TTableIterator	GetMapPageRank (const TVec< PNEANet > &GraphSeq, TTableContext *Context, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
	Gets sequence of PageRank tables from given GraphSeq. More...
TTableIterator	GetMapHitsIterator (const TVec< PNEANet > &GraphSeq, TTableContext *Context, const int &MaxIter=20)
	Gets sequence of Hits tables from given GraphSeq. More...
template<class PGraph >
double	GetFarnessCentr (const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false)
template<class PGraph >
double	GetFarnessCentrMP (const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false)
template<class PGraph >
double	GetClosenessCentr (const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false)
template<class PGraph >
double	GetClosenessCentrMP (const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false)
template<class PGraph >
int	GetNodeEcc (const PGraph &Graph, const int &NId, const bool &IsDir=false)
template<class PGraph >
void	GetBetweennessCentr (const PGraph &Graph, TIntFltH &NIdBtwH, const double &NodeFrac=1.0, const bool &IsDir=false)
template<class PGraph >
void	GetBetweennessCentr (const PGraph &Graph, TIntPrFltH &EdgeBtwH, const double &NodeFrac=1.0, const bool &IsDir=false)
template<class PGraph >
void	GetBetweennessCentr (const PGraph &Graph, TIntFltH &NIdBtwH, TIntPrFltH &EdgeBtwH, const double &NodeFrac=1.0, const bool &IsDir=false)
template<class PGraph >
void	GetBetweennessCentr (const PGraph &Graph, const TIntV &BtwNIdV, TIntFltH &NodeBtwH, const bool &DoNodeCent, TIntPrFltH &EdgeBtwH, const bool &DoEdgeCent, const bool &IsDir)
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	GetPageRank_v1 (const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100)
template<class PGraph >
void	GetPageRankMP (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)
template<class PGraph >
void	GetHitsMP (const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20)
template<class PGraph >
void	MapPageRank (const TVec< PGraph > &GraphSeq, TVec< PTable > &TableSeq, TTableContext *Context, const double &C, const double &Eps, const int &MaxIter)
	Gets sequence of PageRank tables from given GraphSeq into TableSeq. More...
template<class PGraph >
void	MapHits (const TVec< PGraph > &GraphSeq, TVec< PTable > &TableSeq, TTableContext *Context, const int &MaxIter)
	Gets sequence of Hits tables from given GraphSeq into TableSeq. More...
double	CommunityGirvanNewman (PUNGraph &Graph, TCnComV &CmtyV)
double	Infomap (PUNGraph &Graph, TCnComV &CmtyV)
double	InfomapOnline (PUNGraph &Graph, int n1, int n2, TIntFltH &PAlpha, double &SumPAlphaLogPAlpha, TIntFltH &Qi, TIntH &Module, int &Br, TCnComV &CmtyV)
void	CmtyEvolutionFileBatchV (TStr InFNm, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges, double alpha, double beta, int CmtyAlg)
void	CmtyEvolutionFileBatch (TStr InFNm, TIntIntHH &sizesCont, TIntIntHH &cCont, TIntIntVH &edges, double alpha, double beta, int CmtyAlg)
void	CmtyEvolutionJson (TStr &Json, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges)
TStr	CmtyTest (TStr InFNm, int CmtyAlg)
void	ReebSimplify (PNGraph &Graph, TIntH &t, int e, PNGraph &gFinal, TIntH &tFinal, bool collapse)
void	ReebRefine (PNGraph &Graph, TIntH &t, int e, PNGraph &gFinal, TIntH &tFinal, bool collapse)
double	CommunityCNM (const PUNGraph &Graph, TCnComV &CmtyV)
template<typename PGraph >
double	GetModularity (const PGraph &G, const TIntV &NIdV, int GEdges=-1)
template<typename PGraph >
double	GetModularity (const PGraph &G, const TCnComV &CmtyV, int GEdges=-1)
template<typename PGraph >
void	GetEdgesInOut (const PGraph &Graph, const TIntV &NIdV, int &EdgesInX, int &EdgesOutX)
void	GetBiConSzCnt (const PUNGraph &Graph, TIntPrV &SzCntV)
	Returns a distribution of bi-connected component sizes. More...
void	GetBiCon (const PUNGraph &Graph, TCnComV &BiCnComV)
	Returns all bi-connected components of a Graph. More...
void	GetArtPoints (const PUNGraph &Graph, TIntV &ArtNIdV)
	Returns articulation points of a Graph. More...
void	GetEdgeBridges (const PUNGraph &Graph, TIntPrV &EdgeV)
	Returns bridge edges of a Graph. More...
void	Get1CnComSzCnt (const PUNGraph &Graph, TIntPrV &SzCntV)
	Distribution of sizes of 1-components, maximal number of components that can be disconnected from the Graph by removing a single edge. More...
void	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. More...
PUNGraph	GetMxBiCon (const PUNGraph &Graph, const bool &RenumberNodes=false)
	Returns a graph representing the largest bi-connected component on an undirected Graph. More...
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. More...
template<class PGraph >
bool	IsConnected (const PGraph &Graph)
	Tests whether the Graph is (weakly) connected. More...
template<class PGraph >
bool	IsWeaklyConn (const PGraph &Graph)
	Tests whether the Graph is weakly connected. More...
template<class PGraph >
void	GetWccSzCnt (const PGraph &Graph, TIntPrV &WccSzCnt)
	Returns a distribution of weakly connected component sizes. More...
template<class PGraph >
void	GetWccs (const PGraph &Graph, TCnComV &CnComV)
	Returns all weakly connected components in a Graph. More...
template<class PGraph >
void	GetSccSzCnt (const PGraph &Graph, TIntPrV &SccSzCnt)
	Returns a distribution of strongly connected component sizes. More...
template<class PGraph >
void	GetSccs (const PGraph &Graph, TCnComV &CnComV)
	Returns all strongly connected components in a Graph. More...
template<class PGraph >
double	GetMxWccSz (const PGraph &Graph)
	Returns the fraction of nodes in the largest weakly connected component of a Graph. More...
template<class PGraph >
double	GetMxSccSz (const PGraph &Graph)
	Returns the fraction of nodes in the largest strongly connected component of a Graph. More...
template<class PGraph >
PGraph	GetMxWcc (const PGraph &Graph)
	Returns a graph representing the largest weakly connected component on an input Graph. More...
template<class PGraph >
PGraph	GetMxScc (const PGraph &Graph)
	Returns a graph representing the largest strongly connected component on an input Graph. More...
template<class PGraph >
PGraph	GetMxBiCon (const PGraph &Graph)
	Returns a graph representing the largest bi-connected component on an input Graph. More...
int	LoadModeNetToNet (PMMNet Graph, const TStr &Name, PTable Table, const TStr &NCol, TStrV &NodeAttrV)
	Loads a mode, with name Name, into the PMMNet from the TTable. NCol specifies the node id column and NodeAttrV the node attributes. More...
int	LoadMode (TModeNet &Graph, PTable Table, const TStr &NCol, TStrV &NodeAttrV)
	Loads the nodes specified in column NCol from the TTable with the attributes specified in NodeAttrV. More...
int	LoadCrossNetToNet (PMMNet Graph, const TStr &Mode1, const TStr &Mode2, const TStr &CrossName, PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV)
	Loads a crossnet from Mode1 to Mode2, with name CrossName, from the provided TTable. EdgeAttrV specifies edge attributes. More...
int	LoadCrossNet (TCrossNet &Graph, PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV)
	Loads the edges from the TTable and EdgeAttrV specifies columns containing edge attributes. More...
template<class PGraph >
PGraph	ToGraph (PTable Table, const TStr &SrcCol, const TStr &DstCol, TAttrAggr AggrPolicy)
	Sequentially converts the table into a graph with links from nodes in SrcCol to those in DstCol. More...
template<class PGraph >
PGraph	ToNetwork (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &SrcAttrV, TStrV &DstAttrV, TStrV &EdgeAttrV, TAttrAggr AggrPolicy)
	Converts the Table into a graph with edges from SrcCol to DstCol, and attribute vector defined by the arguments. More...
template<class PGraph >
PGraph	ToNetwork (PTable Table, const TStr &SrcCol, const TStr &DstCol, TAttrAggr AggrPolicy)
	Calls ToNetwork with an empty attribute vector. Convenience wrapper. More...
template<class PGraphMP >
PGraphMP	ToGraphMP (PTable Table, const TStr &SrcCol, const TStr &DstCol)
	Performs table to graph conversion in parallel using the sort-first algorithm. This is the recommended method to use. More...
template<class PGraphMP >
PGraphMP	ToGraphMP3 (PTable Table, const TStr &SrcCol, const TStr &DstCol)
	Performs table to graph conversion in parallel. Uses the hash-first method, which is less optimal, use ToGraphMP instead. More...
template<class PGraphMP >
PGraphMP	ToNetworkMP (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &SrcAttrV, TStrV &DstAttrV, TStrV &EdgeAttrV, TAttrAggr AggrPolicy)
	Does Table to Network conversion in parallel using the sort-first algorithm. This is the recommended method to use. More...
template<class PGraphMP >
PGraphMP	ToNetworkMP (PTable Table, const TStr &SrcCol, const TStr &DstCol, TAttrAggr AggrPolicy)
	Calls ToNetworkMP with empty attribute vector. Convenience wrapper. More...
template<class PGraphMP >
PGraphMP	ToNetworkMP2 (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &SrcAttrV, TStrV &DstAttrV, TStrV &EdgeAttrV, TAttrAggr AggrPolicy)
	Implements table to network conversion in parallel. Not the recommended algorithm, using ToNetworkMP instead. More...
template<class PGraphMP >
PGraphMP	ToNetworkMP2 (PTable Table, const TStr &SrcCol, const TStr &DstCol, TAttrAggr AggrPolicy)
	Calls ToNetworkMP2 with an empty attribute vector. Convenience wrapper. More...
template<class PGraph >
PGraph	ToNetwork (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV, TAttrAggr AggrPolicy)
	Converts table to a network sequentially. Use if network has only edge attributes. More...
template<class PGraphMP >
PGraphMP	ToNetworkMP (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV, TAttrAggr AggrPolicy)
	Converts table to network in parallel. Use if network has only edge attributes. More...
template<class PGraph >
PGraph	ToNetwork (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV, PTable NodeTable, const TStr &NodeCol, TStrV &NodeAttrV, TAttrAggr AggrPolicy)
	Converts table to network sequentially. Takes edges from Table and nodes explicitly from NodeCol in NodeTable, with attribute vectors passed as columns in corresponding tables. More...
template<class PGraphMP >
PGraphMP	ToNetworkMP (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV, PTable NodeTable, const TStr &NodeCol, TStrV &NodeAttrV, TAttrAggr AggrPolicy)
	Converts table to network in parallel. Takes edges from Table and nodes explicitly from NodeCol in NodeTable, with attribute vectors passed as columns in corresponding tables. More...
int	FastCorePeriphery (PUNGraph &Graph, TIntIntH &out)
int	FastCorePeripheryGC (PUNGraph &Graph, TIntIntH &out)
double	BorgattiEverettMeasure (PUNGraph &Graph, TIntIntH &out, double coresize, int type)
double	PearsonCorrelation (PUNGraph &Graph, TIntIntH &out, int coresize)
int	IntFlowBiDBFS (const PNEANet &Net, const int &CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, const int &SrcNId, const int &SnkNId)
int	FindAugV (const PNEANet &Net, const int &CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, TIntV &MidToSrcAugV, TIntV &MidToSnkAugV, const int &SrcNId, const int &SnkNId)
	Returns the amount the flow can be augmented over the paths, 0 if no path can be found. More...
int	GetMaxFlowIntEK (PNEANet &Net, const int &SrcNId, const int &SnkNId)
	Returns the maximum integer valued flow in the network Net from source SrcNId to sink SnkNId. More...
void	PushToOutNbr (TPRManager &PRM, const int &NId, const int &OutNId, const int &EId)
	Pushes flow from a node NId to a neighbor OutNId over edge EId. More...
void	PushToInNbr (TPRManager &PRM, const int &NId, const int &InNId, const int &EId)
	Returns flow from a node NId to a neighbor InNId over edge EId. More...
void	Relabel (TPRManager &PRM, const int &NId, const TNEANet::TNodeI &NI)
	Increases the label of a node NId to allow valid pushes to some neighbor. More...
int	PushRelabel (TPRManager &PRM, const int &NId, const TNEANet::TNodeI &NI)
	Returns the ID of the neighbor that NId pushes to, -1 if no push was made. More...
void	GlobalRelabel (PNEANet &Net, TPRManager &PRM, const int &SrcNId, const int &SnkNId)
	Implements the Global Relabeling heuristic. More...
int	GetMaxFlowIntPR (PNEANet &Net, const int &SrcNId, const int &SnkNId)
	Returns the maximum integer valued flow in the network Net from source SrcNId to sink SnkNId. More...
TStr	GetFlagStr (const TGraphFlag &GraphFlag)
	Returns a string representation of a flag. More...
template<class PGraph >
void	PrintInfo (const PGraph &Graph, const TStr &Desc="", const TStr &OutFNm="", const bool &Fast=true)
	Prints basic graph statistics. More...
template<class PGraph >
int64	GetTriads (const PGraph &Graph, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes)
	Computes the number of Closed and Open triads. More...
template<class PGraph >
int	GetKCoreNodes (const PGraph &Graph, TIntPrV &CoreIdSzV)
	Returns the number of nodes in each core of order K (where K=0, 1, ...) More...
template<class PGraph >
int	GetKCoreEdges (const PGraph &Graph, TIntPrV &CoreIdSzV)
	Returns the number of edges in each core of order K (where K=0, 1, ...) More...
PBPGraph	GenRndBipart (const int &LeftNodes, const int &RightNodes, const int &Edges, TRnd &Rnd=TInt::Rnd)
	Generates a random bipartite graph. More...
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. More...
PUNGraph	GenRndPowerLaw (const int &Nodes, const double &PowerExp, const bool &ConfModel=true, TRnd &Rnd=TInt::Rnd)
	Generates a random scale-free graph with power-law degree distribution. More...
PUNGraph	GenDegSeq (const TIntV &DegSeqV, TRnd &Rnd=TInt::Rnd)
	Generates a random graph with exact degree sequence. More...
PUNGraph	GenConfModel (const TIntV &DegSeqV, TRnd &Rnd=TInt::Rnd)
	Generates a random undirect graph with a given degree sequence. More...
PUNGraph	GenRewire (const PUNGraph &Graph, const int &NSwitch=100, TRnd &Rnd=TInt::Rnd)
	Rewire a random undirected graph. Keeps node degrees the same, but randomly rewires the edges. More...
PNGraph	GenRewire (const PNGraph &Graph, const int &NSwitch=100, TRnd &Rnd=TInt::Rnd)
	Rewire a random directed graph. Keeps node degrees the same, but randomly rewires the edges. More...
PBPGraph	GenRewire (const PBPGraph &Graph, const int &NSwitch=100, TRnd &Rnd=TInt::Rnd)
	Rewire a random bipartite graph. Keeps node degrees the same, but randomly rewires the edges. More...
PUNGraph	GenPrefAttach (const int &Nodes, const int &NodeOutDeg, TRnd &Rnd=TInt::Rnd)
	Generates a power-law degree distribution using Barabasi-Albert model of scale-free graphs. More...
PUNGraph	GenConfModel (const PUNGraph &G)
	Generate a random graph using (approximately) the same node degrees as in G using the configuration model. More...
PUNGraph	GenGeoPrefAttach (const int &Nodes, const int &OutDeg, const double &Beta, TRnd &Rnd=TInt::Rnd)
	Generates a random scale-free graph using the Geometric Preferential model. More...
PUNGraph	GenSmallWorld (const int &Nodes, const int &NodeOutDeg, const double &RewireProb, TRnd &Rnd=TInt::Rnd)
	Generates a randomly small-world graph using the Watts-Strogatz model. More...
PNGraph	GenForestFire (const int &Nodes, const double &FwdProb, const double &BckProb)
	Generates a random Forest Fire, directed graph with given probabilities. More...
PNGraph	GenCopyModel (const int &Nodes, const double &Beta, TRnd &Rnd=TInt::Rnd)
	Generates a random scale-free network using the Copying Model. More...
PNGraph	GenRMat (const int &Nodes, const int &Edges, const double &A, const double &B, const double &C, TRnd &Rnd=TInt::Rnd)
	Generates a R-MAT graph using recursive descent into a 2x2 matrix [A,B; C, 1-(A+B+C)]. More...
PNGraph	GenRMatEpinions ()
	Generates a R-Mat graph, with a synthetic copy of the Epinions social network. More...
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. More...
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. More...
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. More...
template<class PGraph >
PGraph	GenFull (const int &Nodes)
	Generates a complete graph on Nodes nodes. Graph has no self-loops. More...
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. More...
template<class PGraph >
PGraph	GenBaraHierar (const int &Levels, const bool &IsDir=true)
	Generates a Ravasz-Barabasi deterministic scale-free graph. More...
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. More...
int	ReadEdgeSchemaFromFile (TSsParser &Ss, const char &Separator, int &SrcColId, int &DstColId, TStrIntH &IntAttrEVals, TStrIntH &FltAttrEVals, TStrIntH &StrAttrEVals)
bool	ReadEdgesFromFile (TSsParser &Ss, const char &Separator, PNEANet &Graph, int &SrcColId, int &DstColId, TStrIntH &IntAttrEVals, TStrIntH &FltAttrEVals, TStrIntH &StrAttrEVals)
int	ReadNodeSchemaFromFile (TSsParser &Ss, const char &Separator, int &NId, TStrIntH &IntAttrNVals, TStrIntH &FltAttrNVals, TStrIntH &StrAttrNVals)
bool	ReadNodesFromFile (TSsParser &Ss, const char &Separator, PNEANet &Graph, int &NColId, TStrIntH &IntAttrNVals, TStrIntH &FltAttrNVals, TStrIntH &StrAttrNVals)
PNEANet	LoadEdgeListNet (const TStr &InFNm, const char &Separator)
	Loads a network from the text file InFNm with 1 node/edge per line ('Separator' separated columns, integer node id(s) + node/edge attributes). More...
void	WriteNodeSchemaToFile (FILE *F, TStrV &IntAttrNNames, TStrV &FltAttrNNames, TStrV &StrAttrNNames)
void	WriteNodesToFile (FILE *F, const PNEANet &Graph, TStrV &IntAttrNNames, TStrV &FltAttrNNames, TStrV &StrAttrNNames)
void	WriteEdgeSchemaToFile (FILE *F, TStrV &IntAttrENames, TStrV &FltAttrENames, TStrV &StrAttrENames)
void	WriteEdgesToFile (FILE *F, const PNEANet &Graph, TStrV &IntAttrENames, TStrV &FltAttrENames, TStrV &StrAttrENames)
void	SaveEdgeListNet (const PNEANet &Graph, const TStr &OutFNm, const TStr &Desc)
	Saves a network into a text file. Each line encodes either an edge or a node, along with its attributes. More...
PNGraph	LoadDyNet (const TStr &FNm)
	For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php) More...
TVec< PNGraph >	LoadDyNetGraphV (const TStr &FNm)
	For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php) More...
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). More...
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). More...
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). More...
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). More...
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. More...
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. More...
template<class PGraph >
PGraph	LoadPajek (const TStr &InFNm)
	Loads a (directed, undirected or multi) graph from Pajek .PAJ format file. More...
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 columns and encodes a single edge: <source node="" id>=""><tab><destination node="" id>=""> More...
template<class PGraph >
void	SavePajek (const PGraph &Graph, const TStr &OutFNm)
	Saves a graph in a Pajek .NET format. More...
template<class PGraph >
void	SavePajek (const PGraph &Graph, const TStr &OutFNm, const TIntStrH &NIdColorH)
	Saves a graph in a Pajek .NET format. More...
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. More...
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. More...
template<class PGraph >
void	SaveMatlabSparseMtx (const PGraph &Graph, const TStr &OutFNm)
	Saves a graph in a MATLAB sparse matrix format. More...
template<class PGraph >
void	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. More...
template<class PGraph >
void	SaveGViz (const PGraph &Graph, const TStr &OutFNm, const TStr &Desc, const TIntStrH &NIdLabelH)
	Save a graph in GraphVizp .DOT format. More...
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. More...
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. More...
void	GetSngVec (const PNGraph &Graph, const int &SngVecs, TFltV &SngValV, TFltVFltV &LeftSV, TFltVFltV &RightSV)
void	GetEigVals (const PUNGraph &Graph, const int &EigVals, TFltV &EigValV)
	Computes top EigVals eigenvalues of the adjacency matrix representing a given undirected Graph. More...
void	GetEigVec (const PUNGraph &Graph, TFltV &EigVecV)
	Computes the leading eigenvector of the adjacency matrix representing a given undirected Graph. More...
void	GetEigVec (const PUNGraph &Graph, const int &EigVecs, TFltV &EigValV, TFltVFltV &EigVecV)
	Computes top EigVecs eigenvalues and eigenvectors of the adjacency matrix representing a given undirected Graph. More...
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())
	Draws a given Graph using a selected GraphViz Layout engine with nodes colored. More...
template<class PGraph >
void	DrawGViz (const PGraph &Graph, const TGVizLayout &Layout, const TStr &PltFNm, const TStr &Desc, const TIntStrH &NodeLabelH)
	Draws a given Graph using a selected GraphViz Layout engine with nodes labeled. More...
template<class PGraph >
PGraph	GetKCore (const PGraph &Graph, const int &K)
void	TIntVToNumpy (TIntV &IntV, int *IntNumpyVecOut, int n)
	Converts TIntV to Numpy array. More...
void	TFltVToNumpy (TFltV &FltV, float *FltNumpyVecOut, int n)
	Converts TFltV to Numpy array. More...
void	NumpyToTIntV (TIntV &IntV, int *IntNumpyVecIn, int n)
	Converts NumpyArray to TIntV. More...
void	NumpyToTFltV (TFltV &FltV, float *FltNumpyVecIn, int n)
	Converts NumpyArray to TFltV. More...
template<class PGraph >
int	SamplePersonalizedPageRank (const PGraph &Graph, double JumpProb, const TIntV &StartNIdV, TRnd &Rnd)
template<class PGraph >
double	GetPersonalizedPageRankBidirectional (const PGraph &Graph, double JumpProb, const TIntV &StartNIdV, int TargetNId, double MinProbability=-1.0, double RelativeError=0.1, bool provableRelativeError=false, bool PrintTimeForTuning=false)
template<class PGraph >
double	GetRndWalkRestartBidirectional (const PGraph &Graph, double JumpProb, int StartNId, int TargetNId, double minProbability=-1.0, double relativeError=0.1, bool proveRelativeError=false, bool PrintTimeForTuning=false)
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. More...
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. More...
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. More...
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. More...
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. More...
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. More...
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. More...
template<class PGraph >
void	PlotClustCf (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the distribution of clustering coefficient of a Graph. More...
template<class PGraph >
void	PlotHops (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr(), 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. More...
template<class PGraph >
void	PlotKCoreNodes (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the k-Core node-size distribution: Core k vs. number of nodes in k-core. More...
template<class PGraph >
void	PlotKCoreEdges (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr())
	Plots the k-Core edge-size distribution: Core k vs. number of edges in k-core. More...
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. More...
PNGraph	GetSubGraph (const PNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
PUNGraph	GetEgonet (const PUNGraph &Graph, const int CtrNId, int &ArndEdgesX)
	Returns the egonet of node CtrNId as center in undirected graph Graph. And returns number of edges around the egonet. More...
PNGraph	GetEgonet (const PNGraph &Graph, const int CtrNId, int &InEgoEdgesX, int &OutEgoEdgesX)
	Returns the egonet of node CtrNId as center in directed graph Graph. And returns number of edges go in and out the egonet. More...
void	AddNodeWithAttributes (const PNEANet &Graph1, PNEANet &Graph2, const int NId)
void	AddEdgeWithAttributes (const PNEANet &Graph1, PNEANet &Graph2, const int EId)
void	AddEdgeWithAttributes (const PNEANet &Graph1, PNEANet &Graph2, const int NId, const int NbrId)
PNEANet	GetEgonetAttr (const PNEANet &Graph, const int CtrNId, const int Radius)
	Returns the complete egonet of at given radius and copies node and edge attributes. More...
PNEANet	GetInEgonetAttr (const PNEANet &Graph, const int CtrNId, const int Radius)
	Returns the in-egonet of at given radius and copies node and edge attributes. More...
PNEANet	GetOutEgonetAttr (const PNEANet &Graph, const int CtrNId, const int Radius)
	Returns the out-egonet of at given radius and copies node and edge attributes. More...
PNEANet	GetInEgonetSubAttr (const PNEANet &Graph, const int CtrNId, const int Radius, const int MaxNum, const float percent)
	Returns the randomly sampled egonet with nodes sampled based on percentage or raw number, copying attributes. More...
PNEANet	GetGraphUnionAttr (PNEANet &DstGraph, const PNEANet &SrcGraph)
template<class PGraph >
PGraph	GetSubGraph (const PGraph &Graph, const TIntV &NIdV)
	Returns an induced subgraph of graph Graph with NIdV nodes. More...
template<class PGraph >
PGraph	GetSubGraphRenumber (const PGraph &Graph, const TIntV &NIdV)
	Returns an induced subgraph of graph Graph with NIdV nodes with an node renumbering. More...
template<class PGraph >
PGraph	GetESubGraph (const PGraph &Graph, const TIntV &EIdV)
	Returns a subgraph of graph Graph with EIdV edges. More...
template<class PGraph >
PGraph	GetESubGraph (const PGraph &Graph, const TIntPrV &EdgeV)
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. More...
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. More...
template<class POutGraph , class PInGraph >
POutGraph	ConvertGraph (const PInGraph &InGraph, const bool &RenumberNodes=false)
	Performs conversion of graph InGraph with an optional node renumbering. More...
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. More...
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. More...
template<class PGraph >
PGraph	GetRndSubGraph (const PGraph &Graph, const int &NNodes)
	Returns an induced random subgraph of graph Graph with NNodes nodes. More...
template<class PGraph >
PGraph	GetRndESubGraph (const PGraph &Graph, const int &NEdges)
	Returns a random subgraph of graph Graph with NEdges edges. More...
template<class PGraph >
PGraph	GetEgonetHop (const PGraph &Graph, const int CtrNId, const int Radius)
	Returns the egonet of node CtrNId as center for a Graph for a given radius. More...
template<class PGraph >
PGraph	GetInEgonetHop (const PGraph &Graph, const int CtrNId, const int Radius)
	Returns the in-egonet of node CtrNId as center in directed graph Graph for a given radius. More...
template<class PGraph >
PGraph	GetOutEgonetHop (const PGraph &Graph, const int CtrNId, const int Radius)
	Returns the out-egonet of node CtrNId as center in directed graph Graph for a given radius. More...
template<class PGraph >
PGraph	GetInEgonetSub (const PGraph &Graph, const int CtrNId, const int Radius, const int MaxNum=2, const float percent=-1.0)
	Returns the randomly sampled in-egonet with nodes sampled based on percentage, if percent != -1.0, or MaxNum nodes otherwise. More...
template<class PGraph >
PGraph	GetGraphUnion (PGraph &DstGraph, const PGraph &SrcGraph)
int	GetCommon (TIntV &A, TIntV &B)
	Returns the number of common elements in two sorted TInt vectors. More...
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. More...
template<class PGraph >
double	GetClustCf (const PGraph &Graph, TFltPrV &DegToCCfV, int SampleNodes=-1)
	Computes the distribution of average clustering coefficient. More...
template<class PGraph >
double	GetClustCf (const PGraph &Graph, TFltPrV &DegToCCfV, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1)
	Computes the distribution of average clustering coefficient as well as the number of open and closed triads in the graph. More...
template<class PGraph >
double	GetClustCfAll (const PGraph &Graph, TFltPrV &DegToCCfV, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes=-1)
	Computes the distribution of average clustering coefficient as well as the number of open and closed triads in the graph. More...
template<class PGraph >
double	GetNodeClustCf (const PGraph &Graph, const int &NId)
	Returns clustering coefficient of a particular node. More...
template<class PGraph >
void	GetNodeClustCf (const PGraph &Graph, TIntFltH &NIdCCfH)
	Computes clustering coefficient of each node of the Graph. More...
template<class PGraph >
int64	GetTriads (const PGraph &Graph, int SampleNodes=-1)
	Returns the number of triangles in a graph. More...
template<class PGraph >
int64	GetTriadsAll (const PGraph &Graph, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes=-1)
	Computes the number of Closed and Open triads. More...
template<class PGraph >
void	GetTriads (const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes=-1)
	Computes the number of open and close triads for every node of the network. More...
template<class PGraph >
int	GetTriadEdges (const PGraph &Graph, int SampleEdges=-1)
	Counts the number of edges that participate in at least one triad. More...
template<class PGraph >
int	GetNodeTriads (const PGraph &Graph, const int &NId)
	Returns the number of undirected triads a node NId participates in. More...
template<class PGraph >
int	GetNodeTriads (const PGraph &Graph, const int &NId, int &ClosedNTriadsX, int &OpenNTriadsX)
	Returns number of Open and Closed triads a node NId participates in. More...
template<class PGraph >
int	GetNodeTriadsAll (const PGraph &Graph, const int &NId, int &ClosedNTriadsX, int &OpenNTriadsX)
	Returns number of Open and Closed triads a node NId participates in. More...
template<class PGraph >
int	GetNodeTriads (const PGraph &Graph, const int &NId, const TIntSet &GroupSet, int &InGroupEdgesX, int &InOutGroupEdgesX, int &OutGroupEdgesX)
	Returns the number of triads between a node NId and a subset of its neighbors GroupSet. More...
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). More...
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. More...
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. More...
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). More...
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). More...
template<class PGraph >
int64	GetTriangleCnt (const PGraph &Graph)
	Returns the number of triangles in graph Graph. More...
template<class PGraph >
void	MergeNbrs (TIntV &NeighbourV, const typename PGraph::TObj::TNodeI &NI)
	Merges neighbors by removing duplicates and produces one sorted vector of neighbors. More...
template<class PGraph >
void	GetUniqueNbrV (const PGraph &Graph, const int &NId, TIntV &NbrV)
	Returns sorted vector NbrV containing unique in or out neighbors of node NId in graph Graph. More...
template<class PGraph >
void	GetTriads_v0 (const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes)
template<>
int	GetCmnNbrs< PUNGraph > (const PUNGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV)

Variables
const TStr	CapAttrName = "capacity"
const TStr	EDGES_START = ("#EDGES")
const TStr	NODES_START = ("#NODES")
const TStr	END_SENTINEL = ("#END")
const TStr	SRC_ID_NAME = ("SrcNId")
const TStr	DST_ID_NAME = ("DstNId")
const TStr	NID_NAME = ("NId")
const TStr	INT_TYPE_PREFIX = ("Int")
const TStr	FLT_TYPE_PREFIX = ("Flt")
const TStr	STR_TYPE_PREFIX = ("Str")
const TStr	NULL_VAL = ("__null__")

Detailed Description

Main namespace for all the Snap global entities.

The name of the friend is not found by simple name lookup until a matching declaration is provided in that namespace scope (either before or after the class declaration granting friendship).

Function Documentation

void TSnap::AddEdgeWithAttributes	(	const PNEANet &	Graph1,
		PNEANet &	Graph2,
		const int	EId
	)

Definition at line 179 of file subgraph.cpp.

References TVec< TVal, TSizeTy >::Len().

Referenced by GetEgonetAttr(), GetGraphUnionAttr(), GetInEgonetAttr(), GetInEgonetSubAttr(), and GetOutEgonetAttr().

                                                                                 {
  const TNEANet::TEdgeI EI = Graph1->GetEI(EId);
  Graph2->AddEdge(EI);
  //const int EId = Graph2->GetEId(NId, NbrId);
  // Copy Int Attributes
  TStrV IntAttrNames;
  TIntV IntAttrValues;
  Graph1->IntAttrNameEI(EId, IntAttrNames);
  Graph1->IntAttrValueEI(EId, IntAttrValues);
  for (int i = 0; i < IntAttrNames.Len(); i++) {
    Graph2->AddIntAttrDatE(EId, IntAttrValues[i], IntAttrNames[i]);
  }
  // Copy Float Attributes
  TStrV FltAttrNames;
  TFltV FltAttrValues;
  Graph1->FltAttrNameEI(EId, FltAttrNames);
  Graph1->FltAttrValueEI(EId, FltAttrValues);
  for (int i = 0; i < FltAttrNames.Len(); i++) {
    Graph2->AddFltAttrDatE(EId, FltAttrValues[i], FltAttrNames[i]);
  }
  // Copy Str Attributes
  TStrV StrAttrNames;
  TStrV StrAttrValues;
  Graph1->StrAttrNameEI(EId, StrAttrNames);
  Graph1->StrAttrValueEI(EId, StrAttrValues);
  for (int i = 0; i < StrAttrNames.Len(); i++) {
    Graph2->AddStrAttrDatE(EId, StrAttrValues[i], StrAttrNames[i]);
  }
  // Copy IntV Attributes
  TStrV IntVAttrNames;
  TVec<TIntV> IntVAttrValues;
  Graph1->IntVAttrNameEI(EId, IntVAttrNames);
  Graph1->IntVAttrValueEI(EId, IntVAttrValues);
  for (int i = 0; i < IntVAttrNames.Len(); i++) {
    Graph2->AddIntVAttrDatE(EId, IntVAttrValues[i], IntVAttrNames[i]);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::AddEdgeWithAttributes	(	const PNEANet &	Graph1,
		PNEANet &	Graph2,
		const int	NId,
		const int	NbrId
	)

Definition at line 217 of file subgraph.cpp.

References TVec< TVal, TSizeTy >::Len().

                                                                                                   {
  Graph2->AddEdge(NId, NbrId);
  const int EId = Graph2->GetEId(NId, NbrId);
  // Copy Int Attributes
  TStrV IntAttrNames;
  TIntV IntAttrValues;
  Graph1->IntAttrNameEI(EId, IntAttrNames);
  Graph1->IntAttrValueEI(EId, IntAttrValues);
  for (int i = 0; i < IntAttrNames.Len(); i++) {
    Graph2->AddIntAttrDatE(EId, IntAttrValues[i], IntAttrNames[i]);
  }
  // Copy Float Attributes
  TStrV FltAttrNames;
  TFltV FltAttrValues;
  Graph1->FltAttrNameEI(EId, FltAttrNames);
  Graph1->FltAttrValueEI(EId, FltAttrValues);
  for (int i = 0; i < FltAttrNames.Len(); i++) {
    Graph2->AddFltAttrDatE(EId, FltAttrValues[i], FltAttrNames[i]);
  }
  // Copy Str Attributes
  TStrV StrAttrNames;
  TStrV StrAttrValues;
  Graph1->StrAttrNameEI(EId, StrAttrNames);
  Graph1->StrAttrValueEI(EId, StrAttrValues);
  for (int i = 0; i < StrAttrNames.Len(); i++) {
    Graph2->AddStrAttrDatE(EId, StrAttrValues[i], StrAttrNames[i]);
  }
  // Copy IntV Attributes
  TStrV IntVAttrNames;
  TVec<TIntV> IntVAttrValues;
  Graph1->IntVAttrNameEI(EId, IntVAttrNames);
  Graph1->IntVAttrValueEI(EId, IntVAttrValues);
  for (int i = 0; i < IntVAttrNames.Len(); i++) {
    Graph2->AddIntVAttrDatE(EId, IntVAttrValues[i], IntVAttrNames[i]);
  }
}

Here is the call graph for this function:

void TSnap::AddNodeWithAttributes	(	const PNEANet &	Graph1,
		PNEANet &	Graph2,
		const int	NId
	)

Definition at line 143 of file subgraph.cpp.

References TVec< TVal, TSizeTy >::Len().

Referenced by GetEgonetAttr(), GetGraphUnionAttr(), GetInEgonetAttr(), GetInEgonetSubAttr(), and GetOutEgonetAttr().

                                                                                  {
  Graph2->AddNode(NId);
  // Copy Int Attributes
  TStrV IntAttrNames;
  TIntV IntAttrValues;
  Graph1->IntAttrNameNI(NId, IntAttrNames);
  Graph1->IntAttrValueNI(NId, IntAttrValues);
  for (int i = 0; i < IntAttrNames.Len(); i++) {
    Graph2->AddIntAttrDatN(NId, IntAttrValues[i], IntAttrNames[i]);
  }
  // Copy Float Attributes
  TStrV FltAttrNames;
  TFltV FltAttrValues;
  Graph1->FltAttrNameNI(NId, FltAttrNames);
  Graph1->FltAttrValueNI(NId, FltAttrValues);
  for (int i = 0; i < FltAttrNames.Len(); i++) {
    Graph2->AddFltAttrDatN(NId, FltAttrValues[i], FltAttrNames[i]);
  }
  // Copy Str Attributes
  TStrV StrAttrNames;
  TStrV StrAttrValues;
  Graph1->StrAttrNameNI(NId, StrAttrNames);
  Graph1->StrAttrValueNI(NId, StrAttrValues);
  for (int i = 0; i < StrAttrNames.Len(); i++) {
    Graph2->AddStrAttrDatN(NId, StrAttrValues[i], StrAttrNames[i]);
  }
  // Copy IntV Attributes
  TStrV IntVAttrNames;
  TVec<TIntV> IntVAttrValues;
  Graph1->IntVAttrNameNI(NId, IntVAttrNames);
  Graph1->IntVAttrValueNI(NId, IntVAttrValues);
  for (int i = 0; i < IntVAttrNames.Len(); i++) {
    Graph2->AddIntVAttrDatN(NId, IntVAttrValues[i], IntVAttrNames[i]);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >

void TSnap::AddSelfEdges

(

const PGraph &

Graph

)

Adds a self-edge to every node in the graph.

Definition at line 369 of file alg.h.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().

                                       {
  TIntV EdgeV;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    const int NId = NI.GetId();
    if (! Graph->IsEdge(NId, NId)) {
      EdgeV.Add(NId);
    }
  }
  for (int i = 0; i < EdgeV.Len(); i++) {
    Graph->AddEdge(EdgeV[i], EdgeV[i]);
  }
}

Here is the call graph for this function:

TIntH* TSnap::AllCombinationsMN	(	int	m,
		int	n
	)

Definition at line 157 of file centr.cpp.

                                      {
  float N = 1;
  for(int i=n; i>0; i--){
    N *= (float)m/(float)n;
    m--;
  n--;
  }

  TIntH* C = new TIntH[(int)N];
  return C;
}

PUNGraph* TSnap::AllGraphsWithNNodes

(

int

n

)

Definition at line 138 of file centr.cpp.

References TUNGraph::AddEdge(), and TUNGraph::AddNode().

                                    {
  PUNGraph* g = new PUNGraph[(((n*n)-n)/2)+1];
  PUNGraph g0;
  for(int i=0; i<n; i++)
    g0->AddNode(i);
  
  g[0] = g0;
  int br=1;

  for(int i=0; i<n; i++)
  for(int j=i; j<n; j++){
      g0->AddEdge(i,j);
    g[br] = g0;
    br++;
  }

  return g;
}

Here is the call graph for this function:

double TSnap::BorgattiEverettMeasure	(	PUNGraph &	Graph,
		TIntIntH &	out,
		double	coresize,
		int	type
	)

Definition at line 186 of file coreper.cpp.

References TUNGraph::BegEI(), TUNGraph::EndEI(), and THash< TKey, TDat, THashFunc >::GetDat().

                                                                                          {
    
    double sum = 0.0;
    for (TUNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++){ // Calculate and store the degrees of each node.
      int i = EI.GetSrcNId();
      int j = EI.GetDstNId();
      if (type == 1) {
        if (out.GetDat(i) == 1 || out.GetDat(j) == 1)
          sum += 1;
      }
      else {
        if (out.GetDat(i) == 1 && out.GetDat(j) == 1)
          sum += 1;
      }
    }

    return sum/(((coresize*coresize)-coresize)/2);
  }

Here is the call graph for this function:

void TSnap::CascFind	(	PNGraph	Graph,
		PTable	P,
		const TStr	C1,
		const TStr	C2,
		const TStr	C3,
		const TStr	C4,
		TVec< TIntV > &	TopCascVV,
		bool	Print
	)

Takes as input a directed graph and returns all the top cascades in TopCascVV.

Definition at line 135 of file casc.cpp.

References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::BegI(), TSnapQueue< TVal >::Empty(), TVec< TVal, TSizeTy >::EndI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TVec< TVal, TSizeTy >::GetVal(), THashSet< TKey, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), THashSet< TKey, THashFunc >::Len(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), TVec< TVal, TSizeTy >::Sort(), TSnapQueue< TVal >::Top(), and TInt::Val.

                                                                                                                                {
  // Attribute to Int mapping
  TInt SIdx = P->GetColIdx(C1);
  TInt DIdx = P->GetColIdx(C2);
  TInt StIdx = P->GetColIdx(C3);
  TInt DuIdx = P->GetColIdx(C4);
  TIntV MapV, PhyV;
  TStrV SortBy;
  SortBy.Add(C3);
  P->Order(SortBy);
  int count = 0;
  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
    MapV.Add(RI.GetRowIdx());
    PhyV.Add(count++);
  }
  // After sort attach with each row a rank helpful for sorting
  P->StoreIntCol("Physical",PhyV);
  TInt PIdx = P->GetColIdx("Physical");
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    // Check for top cascades
    if (NI.GetInDeg() != 0) { continue;}
    TIntV CurCasc;
    TSnapQueue<TInt> EventQ;
    THashSet<TInt> VisitedH;
    TInt NId = NI.GetId();
    EventQ.Push(NId);
    VisitedH.AddKey(NId);
    CurCasc.Add(P->GetIntValAtRowIdx(PIdx,NId));
    while (! EventQ.Empty()) {
      TNGraph::TNodeI CNI = Graph->GetNI(EventQ.Top().Val); //Get Current Node
      EventQ.Pop();
      // Go over the outdegree nodes of the currernt node
      for (int e = 0; e < CNI.GetOutDeg(); e++) {
        TInt CId = CNI.GetOutNId(e);
        if ( !VisitedH.IsKey(CId)) {
          EventQ.Push(CId);
          VisitedH.AddKey(CId);
          CurCasc.Add(P->GetIntValAtRowIdx(PIdx,CId));
        }
      }
    }
    CurCasc.Sort();
    TIntV ToAddV;
    if (Print && VisitedH.Len() > 1) {
      printf("__casacade__\t%d\n",VisitedH.Len());
    }
    for (TIntV::TIter VI = CurCasc.BegI(); VI < CurCasc.EndI(); VI++) {
      ToAddV.Add(MapV.GetVal(VI->Val));
      if (Print && VisitedH.Len() > 1) {
        int PIdx = MapV.GetVal(VI->Val).Val;
        int PSource = P->GetIntValAtRowIdx(SIdx,PIdx).Val;
        int PDest = P->GetIntValAtRowIdx(DIdx,PIdx).Val;
        int PStart = P->GetIntValAtRowIdx(StIdx,PIdx).Val;    
        int PDur = P->GetIntValAtRowIdx(DuIdx,PIdx).Val;
        printf("%d\t%d\t%d\t%d\t%d\n",PIdx,PSource,PDest,PStart,PDur);
      }   
    }
    if (ToAddV.Len() > 1) {
      TopCascVV.Add(ToAddV);
    }
  }
  return;
}

Here is the call graph for this function:

void TSnap::CascFindMP	(	PNGraph	Graph,
		PTable	P,
		const TStr	C1,
		const TStr	C2,
		const TStr	C3,
		const TStr	C4,
		TVec< TIntV > &	TopCascVV
	)

Parallel implementaion of CascFind takes as input a directed graph and returns all the top cascades in TopCascVV.

Definition at line 200 of file casc.cpp.

References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::BegI(), TSnapQueue< TVal >::Empty(), TVec< TVal, TSizeTy >::EndI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TVec< TVal, TSizeTy >::GetVal(), THashSet< TKey, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), TVec< TVal, TSizeTy >::Sort(), TSnapQueue< TVal >::Top(), and TInt::Val.

                                                                                                                       {
  // Attribute to Int mapping
  TInt SIdx = P->GetColIdx(C1);
  TInt DIdx = P->GetColIdx(C2);
  TInt StIdx = P->GetColIdx(C3);
  TInt DuIdx = P->GetColIdx(C4);
  TIntV MapV, PhyV;
  TStrV SortBy;
  SortBy.Add(C3);
  P->Order(SortBy);
  int count = 0;
  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
    MapV.Add(RI.GetRowIdx());
    PhyV.Add(count++);
  }
  P->StoreIntCol("Physical",PhyV);
  TInt PIdx = P->GetColIdx("Physical");
  TIntV GNodeV;
  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    if (NI.GetInDeg() == 0) { GNodeV.Add(NI.GetId()); }
  }
  TVec<TIntV> ThTopCascVV; // for each thread
  #pragma omp parallel private(ThTopCascVV) num_threads(10)
  {
    #pragma omp for schedule(dynamic,1000)
    for (int i = 0; i < GNodeV.Len(); i++) {
      TIntV CurCasc;
      TSnapQueue<TInt> EventQ;
      THashSet<TInt> VisitedH;
      TInt NId = GNodeV[i];
      EventQ.Push(NId);
      VisitedH.AddKey(NId);
      CurCasc.Add(P->GetIntValAtRowIdx(PIdx,NId));
      while (! EventQ.Empty()) {
        TNGraph::TNodeI CNI = Graph->GetNI(EventQ.Top().Val); //Get Current Node
        EventQ.Pop();
        // Go over the outdegree nodes of the currernt node
        for (int e = 0; e < CNI.GetOutDeg(); e++) {
          TInt CId = CNI.GetOutNId(e);
          if ( !VisitedH.IsKey(CId)) {
            EventQ.Push(CId);
            VisitedH.AddKey(CId);
            CurCasc.Add(P->GetIntValAtRowIdx(PIdx,CId));
          }
        }
      }
      CurCasc.Sort();
      TIntV ToAddV;
      for (TIntV::TIter VI = CurCasc.BegI(); VI < CurCasc.EndI(); VI++) {
        ToAddV.Add(MapV.GetVal(VI->Val));
      }
      if (ToAddV.Len() > 1) { ThTopCascVV.Add(ToAddV);}  
    }
    #pragma omp critical
    {
      for (int j = 0; j < ThTopCascVV.Len(); j++) {
        TopCascVV.Add(ThTopCascVV[j]);
      }
    }
  }
  return;
}

Here is the call graph for this function:

PNGraph TSnap::CascGraph	(	PTable	P,
		const TStr	C1,
		const TStr	C2,
		const TStr	C3,
		const TStr	C4,
		const TInt	W,
		bool	SortParam
	)

Takes as input the column names of the PTable P as C1, C2, C3 and C4 and returns a directed graph of W-adjacent events. By default calls CascGraphSource. Toggle SortParam to use CascGraphTime.

Definition at line 126 of file casc.cpp.

References CascGraphSource(), and CascGraphTime().

                                                                                                                {
  if (SortParam) {
    return CascGraphSource(P, C1, C2, C3, C4, W);
  }
  else {
    return CascGraphTime(P, C1, C2, C3, C4, W);
  }
}

Here is the call graph for this function:

PNGraph TSnap::CascGraphSource	(	PTable	P,
		const TStr	C1,
		const TStr	C2,
		const TStr	C3,
		const TStr	C4,
		const TInt	W
	)

Takes as input the column names of the PTable P as C1, C2,C3 and C4 and returns a directed graph of W-adjacent events. For graph generation events are sorted by C1.

Definition at line 3 of file casc.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), TNGraph::New(), and TInt::Val.

Referenced by CascGraph().

                                                                                                       {
  // Attribute to Int mapping
  TInt SIdx = P->GetColIdx(C1); //Source
  TInt DIdx = P->GetColIdx(C2); //Dest
  TInt StIdx = P->GetColIdx(C3); //Start
  TInt DuIdx = P->GetColIdx(C4); //Duration
  TIntV MapV;
  TStrV SortBy;
  SortBy.Add(C1);
  P->Order(SortBy);
  TIntV Source; 
  P->ReadIntCol(C1,Source);
  PNGraph Graph = TNGraph::New();
  //Add Nodes
  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
    Graph->AddNode(RI.GetRowIdx().Val);
    MapV.Add(RI.GetRowIdx());
  }
  //Add Edges
  for (TRowIterator OI = P->BegRI(); OI < P->EndRI(); OI++) {
    int OIdx = OI.GetRowIdx().Val;
    int ODest = P->GetIntValAtRowIdx(DIdx,OIdx).Val;
    int OStart = P->GetIntValAtRowIdx(StIdx,OIdx).Val;
    int ODur = P->GetIntValAtRowIdx(DuIdx,OIdx).Val;
    // Inline binary Search
    int val = ODest;
    int lo = 0;
    int hi = Source.Len() - 1;
    int index = -1;
    while (hi >= lo) {
      int mid = lo + (hi - lo)/2;
      if (Source.GetVal(mid) > val) { hi = mid - 1;}
      else if (Source.GetVal(mid) < val) { lo = mid + 1;}
      else { index = mid; hi = mid - 1;}
    }
    // End of binary Search
    if (index < 0) {
      continue;
    }
    int BIdx = index;
    for(int i = BIdx; i < Source.Len(); i++) {
      int InIdx = MapV.GetVal(i).Val;
      if (InIdx == OIdx) {continue;}
      int InSource = P->GetIntValAtRowIdx(SIdx,InIdx).Val;
      int InStart = P->GetIntValAtRowIdx(StIdx,InIdx).Val;
      if (InSource != ODest) { break;}
      if (InStart >= (ODur + OStart) && InStart - (ODur + OStart) <= W.Val) {
        if (!Graph->IsEdge(OIdx,InIdx)) {
          Graph->AddEdge(OIdx,InIdx);
        }
      }      
    }
  }
  return Graph;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PNGraph TSnap::CascGraphTime	(	PTable	P,
		const TStr	C1,
		const TStr	C2,
		const TStr	C3,
		const TStr	C4,
		const TInt	W
	)

Takes as input the column names of the PTable P as C1, C2,C3 and C4 and returns a directed graph of W-adjacent events. For graph generation events are sorted by C3.

Definition at line 59 of file casc.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), TNGraph::New(), and TInt::Val.

Referenced by CascGraph().

                                                                                                     {
  // Attribute to Int mapping
  TInt SIdx = P->GetColIdx(C1); //Source
  TInt DIdx = P->GetColIdx(C2); //Dest
  TInt StIdx = P->GetColIdx(C3); //Start
  TInt DuIdx = P->GetColIdx(C4); //Duration
  TIntV MapV;
  TStrV SortBy;
  SortBy.Add(C3);
  P->Order(SortBy);
  TIntV Start; 
  P->ReadIntCol(C3,Start);
  PNGraph Graph = TNGraph::New();
  //Add Nodes
  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
    Graph->AddNode(RI.GetRowIdx().Val);
    MapV.Add(RI.GetRowIdx());
  }
  //Add Edges
  for (TRowIterator OI = P->BegRI(); OI < P->EndRI(); OI++) {
    int OIdx = OI.GetRowIdx().Val;
    int ODest = P->GetIntValAtRowIdx(DIdx,OIdx).Val;
    int OStart = P->GetIntValAtRowIdx(StIdx,OIdx).Val;
    int ODur = P->GetIntValAtRowIdx(DuIdx,OIdx).Val;
    // Inline binary Search
    int val = OStart + ODur;
    int lo = 0;
    int hi = Start.Len() - 1;
    int index = -1;
    if (val >= Start.GetVal(hi)) { val = Start.GetVal(hi);}
    while (hi >= lo) {
      int mid = lo + (hi - lo)/2;
      if (Start.GetVal(mid) > val) {
        if ((mid-1) >= lo  &&  Start.GetVal(mid - 1) < val) {
          index = mid - 1;break;
        }
        hi = mid - 1;
      }
      else if (Start.GetVal(mid) < val) {
        if (mid + 1 <= hi  &&  Start.GetVal(mid + 1) > val) {
          index = mid;break;
        }
        lo = mid + 1;
      }
      else { index = mid; hi = mid - 1;}
    }
    // End of binary Search
    if (index < 0) {
      continue;
    }
    int BIdx = index;
    for(int i = BIdx; i < Start.Len(); i++) {
      int InIdx = MapV.GetVal(i).Val;
      if (InIdx == OIdx) {continue;}
      int InSource = P->GetIntValAtRowIdx(SIdx,InIdx).Val;
      int InStart = P->GetIntValAtRowIdx(StIdx,InIdx).Val;
      if (InStart - (ODur + OStart) > W.Val) { break;}
      if (InSource == ODest && InStart >= (ODur + OStart)) {
        if (!Graph->IsEdge(OIdx,InIdx)) {
          Graph->AddEdge(OIdx,InIdx);
        }
      }      
    }
  }
  return Graph;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::CmtyEvolutionFileBatch	(	TStr	InFNm,
		TIntIntHH &	sizesCont,
		TIntIntHH &	cCont,
		TIntIntVH &	edges,
		double	alpha,
		double	beta,
		int	CmtyAlg
	)

Definition at line 490 of file cmty.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TUNGraph::AddEdge(), TUNGraph::AddNode(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::Clr(), DelSelfEdges(), edge, TSsParser::Eof(), Fail, TStr::GetCh(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::GetDat(), TSsParser::GetInt(), THash< TKey, TDat, THashFunc >::GetKey(), TSsParser::GetLnStr(), TUNGraph::GetNodes(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::IsKey(), TUNGraph::IsNode(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TUNGraph::New(), TSsParser::Next(), and ssfWhiteSep.

Referenced by CmtyEvolutionFileBatchV().

                                                                                                                                          {


  // reading folder with networks and calculating core/periphery
  int br = 0;
  TIntIntH prev;
  TIntH prev_sizes;

  TSsParser Ss(InFNm, ssfWhiteSep, true, false, true);
  Ss.Next();
  //int internal_year_counter = 0;
  // variable for delimiter between networks
  TStr Marker;
  // defining variables for node ids and starting year
  int SrcNId, DstNId; // , t = 1970;

  // temporal container for edges
  TIntIntVH edges_;

  while (!Ss.Eof()) {

    //printf("%i\n", t);
    Marker = Ss.GetLnStr();
    // get the year from the network seperator
    //t = Marker.GetSubStr(1, 4).GetInt();

    if (Marker.GetCh(0) == '#'){

      Ss.Next();
      PUNGraph Graph = PUNGraph::TObj::New();
      do{
        if (!Ss.GetInt(0, SrcNId) || !Ss.GetInt(1, DstNId)) {
          if (!Ss.Eof()){
            Ss.Next();
            if (!Ss.Eof())
              Marker = Ss.GetLnStr();
          }
          continue;
        }
        if (!Graph->IsNode(SrcNId)) { Graph->AddNode(SrcNId); }
        if (!Graph->IsNode(DstNId)) { Graph->AddNode(DstNId); }
        Graph->AddEdge(SrcNId, DstNId);
        Ss.Next();
        if (!Ss.Eof())
          Marker = Ss.GetLnStr();
      } while (Marker.GetCh(0) != '#' && !Ss.Eof());


      if (Graph->GetNodes()>0) {
        // WORK

        TSnap::DelSelfEdges(Graph);
        TCnComV CmtyV;
        //double Q = 0.0;
        TStr CmtyAlgStr;
        if (CmtyAlg == 1) {
          CmtyAlgStr = "Girvan-Newman";
          //Q = TSnap::CommunityGirvanNewman(Graph, CmtyV);
        }
        else if (CmtyAlg == 2) {
          CmtyAlgStr = "Clauset-Newman-Moore";
          //Q = TSnap::CommunityCNM(Graph, CmtyV);
        }
        else if (CmtyAlg == 3) {
          CmtyAlgStr = "Infomap";
          //Q = TSnap::Infomap(Graph, CmtyV);
        }
        else { Fail; }

        TIntIntHH distCont;

        if (br == 0) {
          prev.Clr();
          //int size = 0;
          for (int c = 0; c < CmtyV.Len(); c++) {
            for (int i = 0; i < CmtyV[c].Len(); i++){
              prev.AddDat(CmtyV[c][i].Val, c);
            }
            //int s = CmtyV[c].Len();
            prev_sizes.AddDat(c, CmtyV[c].Len());
          }
        }
        else {

          // containers for statistics

          //TIntFltHH stat1;
          //TIntIntHH stat2;
          TIntH dist;
          TIntH map;

          int first_new_c_id = -1;

          // getting first free id for a new community
          for (THashKeyDatI<TInt, TInt> it = prev_sizes.BegI(); !it.IsEnd(); it++)
            if (it.GetKey() > first_new_c_id)
              first_new_c_id = it.GetKey();
          if (CmtyV.Len() - 1>first_new_c_id)
            first_new_c_id = CmtyV.Len() - 1;
          first_new_c_id++;

          for (int c = 0; c < CmtyV.Len(); c++) {

            TIntV stat;
            TIntFltH statH1;
            TIntFltH statH2;

            // initialize distributions to 0
            for (THashKeyDatI<TInt, TInt> it = prev_sizes.BegI(); !it.IsEnd(); it++)
              dist.AddDat(it.GetKey(), 0);
            //for new nodes
            dist.AddDat(-1, 0);

            for (int i = 0; i < CmtyV[c].Len(); i++) {
              int id = CmtyV[c][i].Val;
              int prev_comm = -1;
              if (prev.IsKey(id))
                prev_comm = prev.GetDat(CmtyV[c][i].Val);
              stat.Add(prev_comm);
              int pre_val = dist.GetDat(prev_comm);
              dist.AddDat(prev_comm, pre_val + 1);
            }

            double sumstat2 = 0;
            for (THashKeyDatI<TInt, TInt> it = dist.BegI(); !it.IsEnd(); it++) {

              int k = it.GetKey();
              int d = it.GetDat();
              if (d > 0){
                if (prev_sizes.IsKey(it.GetKey())){

                  double stat1_ = (double)d / (double)prev_sizes.GetDat(k);
                  statH1.AddDat(k, stat1_);
                }
                double stat2_ = (double)d / (double)CmtyV[c].Len();
                statH2.AddDat(k, stat2_);
                sumstat2 += stat2_;

                TIntV edge;
                edge.Add(k);
                edge.Add(c);
                edge.Add(d);
                edge.Add(br - 1);
                edge.Add(br);
                edges_.AddDat(edges_.Len() + 1, edge);
              }

              // adding edges between two communities in two neighbouring time points;


              if (sumstat2 > 0.98) break;
            }

            int n_of_c_greater_than_half = 0;
            int id_of_c_greater_than_half = -1;
            TIntV ids_of_c_greater_than_half;

            for (THashKeyDatI<TInt, TFlt> it = statH1.BegI(); !it.IsEnd(); it++){
              if (it.GetDat()>alpha){
                id_of_c_greater_than_half = it.GetKey();
                ids_of_c_greater_than_half.Add(it.GetKey());
                n_of_c_greater_than_half++;
              }
            }

            // if this community is build of majority of one previous community and the other parts of the community are fractions of other communities smaller than half, the new community gets its label 
            if (n_of_c_greater_than_half == 1){
              map.AddDat(c, id_of_c_greater_than_half);
            }
            else{
              int h2part_id = -2;
              for (int i = 0; i<ids_of_c_greater_than_half.Len(); i++){
                double H2 = statH2.GetDat(ids_of_c_greater_than_half[i]);
                if (H2>beta){
                  h2part_id = ids_of_c_greater_than_half[i];
                }
              }
              if (h2part_id != -2)
                map.AddDat(c, h2part_id);
              else{
                map.AddDat(c, first_new_c_id);
                first_new_c_id++;
              }
            }

            distCont.AddDat(c, dist);

            //stat1.AddDat(c,statH1);
            //stat2.AddDat(c,statH2);

          }


          prev.Clr();
          prev_sizes.Clr();
          for (int c = 0; c < CmtyV.Len(); c++){
            for (int i = 0; i < CmtyV[c].Len(); i++){
              prev.AddDat(CmtyV[c][i].Val, map.GetDat(c));
            }
            //int s = CmtyV[c].Len();
            prev_sizes.AddDat(map.GetDat(c), CmtyV[c].Len());
          }

          // filing the edges container - the key thing is the map(c)
          for (THashKeyDatI<TInt, TIntV> it = edges_.BegI(); !it.IsEnd(); it++){
            TIntV edgesV;
            int a = it.GetDat()[0];
            int b = it.GetDat()[1];
            int v = it.GetDat()[2];
            int d = it.GetDat()[3];
            int e = it.GetDat()[4];
            edgesV.Add(map.GetDat(b));
            edgesV.Add(a);
            edgesV.Add(v);
            edgesV.Add(d);
            edgesV.Add(e);
            if (a != -1)
              edges.AddDat(edges.Len(), edgesV);
          }
          edges_.Clr();


        }

        sizesCont.AddDat(br, prev_sizes);
        cCont.AddDat(br, prev);
        br++;
        // WORK - END
      }
    }
    else Ss.Next();
  }

}

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::CmtyEvolutionFileBatchV	(	TStr	InFNm,
		TIntIntVH &	sizesContV,
		TIntIntVH &	cContV,
		TIntIntVH &	edges,
		double	alpha,
		double	beta,
		int	CmtyAlg
	)

Definition at line 441 of file cmty.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), CmtyEvolutionFileBatch(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::IsIn(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Len().

Referenced by CmtyTest().

                                                                                                                                             {
  TIntIntHH sizesCont;
  TIntIntHH cCont;
  CmtyEvolutionFileBatch(InFNm, sizesCont, cCont, edges, alpha, beta, CmtyAlg);

  TIntV uniqueId;
  for (int i = 0; i < cCont.Len(); i++){
    for (THashKeyDatI<TInt, TInt> it = cCont[i].BegI(); !it.IsEnd(); it++){
      if (!uniqueId.IsIn(it.GetKey()))
        uniqueId.Add(it.GetKey());
    }
  }

  for (int j = 0; j<uniqueId.Len(); j++)
  {
    TIntV cV;
    for (int i = 0; i<cCont.Len(); i++)
    {
      if (cCont[i].IsKey(uniqueId[j]))
        cV.Add(cCont[i].GetDat(uniqueId[j]));
      else
        cV.Add(-1);
    }
    cContV.AddDat(uniqueId[j], cV);
  }

  TIntV uniqueC;
  for (int i = 0; i < sizesCont.Len(); i++){
    for (THashKeyDatI<TInt, TInt> it = sizesCont[i].BegI(); !it.IsEnd(); it++){
      if (!uniqueC.IsIn(it.GetKey()))
        uniqueC.Add(it.GetKey());
    }
  }

  for (int j = 0; j<uniqueC.Len(); j++)
  {
    TIntV cV;
    for (int i = 0; i<sizesCont.Len(); i++)
    {
      if (sizesCont[i].IsKey(uniqueC[j]))
        cV.Add(sizesCont[i].GetDat(uniqueC[j]));
      else
        cV.Add(0);
    }
    sizesContV.AddDat(uniqueC[j], cV);
  }

}

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::CmtyEvolutionJson	(	TStr &	Json,
		TIntIntVH &	sizesContV,
		TIntIntVH &	cContV,
		TIntIntVH &	edges
	)

Definition at line 725 of file cmty.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), TInt::GetStr(), TStr::InsStr(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::Len(), and TStr::Len().

Referenced by CmtyTest().

                                                                                              {
  // This function creates a JSON string with communities and edges for community evolution visualization using D3.js

  // writing json label for edges
  Json.InsStr(Json.Len(), "{\n\"edges\":[\n");

  TInt br = 0;
  // iterating hash of vector of edges and writing into string 
  for (THashKeyDatI<TInt, TIntV> it = edges.BegI(); !it.IsEnd(); it++)
  {
    // first node
    TInt n1 = it.GetDat()[1];
    // second node
    TInt n2 = it.GetDat()[0];
    // edge weight
    TInt w = it.GetDat()[2];
    // start time point
    TInt t0 = it.GetDat()[3];
    // end time point
    TInt t1 = it.GetDat()[4];

    if (br>0)
      Json.InsStr(Json.Len(), ",");

    // writing to string
    Json.InsStr(Json.Len(), "{\"n1\":"); Json.InsStr(Json.Len(), n1.GetStr());
    Json.InsStr(Json.Len(), ", \"n2\":"); Json.InsStr(Json.Len(), n2.GetStr());
    Json.InsStr(Json.Len(), ", \"w\":"); Json.InsStr(Json.Len(), w.GetStr());
    Json.InsStr(Json.Len(), ", \"t0\":"); Json.InsStr(Json.Len(), t0.GetStr());
    Json.InsStr(Json.Len(), ", \"t1\":"); Json.InsStr(Json.Len(), t1.GetStr());
    Json.InsStr(Json.Len(), " }\n");
    br++;
  }

  // json label for communities
  Json.InsStr(Json.Len(), "],\n\"communities\":[\n");

  br = 0;
  // printing communities into json file 
  for (int i = 0; i < sizesContV[0].Len(); i++)
  {
    for (THashKeyDatI<TInt, TIntV> it = sizesContV.BegI(); !it.IsEnd(); it++)
    {
      // id of community
      TInt id = it.GetKey();
      // community size
      TInt size = it.GetDat()[i];
      // time
      TInt j = i;

      // if the community has size greater than 0, output it to json string
      if (size > 0) {
        if (br>0)
          Json.InsStr(Json.Len(), ",");

        TInt size = it.GetDat()[i];
        Json.InsStr(Json.Len(), "{\"id\":"); Json.InsStr(Json.Len(), id.GetStr());
        Json.InsStr(Json.Len(), ", \"size\":"); Json.InsStr(Json.Len(), size.GetStr());
        Json.InsStr(Json.Len(), ", \"t\":"); Json.InsStr(Json.Len(), j.GetStr());
        Json.InsStr(Json.Len(), " }\n");

        br++;
      }
    }
  }

  // printing communities into json file - alternative ordering
  /*
  for (THashKeyDatI<TInt, TIntV> it = sizesContV.BegI();  !it.IsEnd(); it++)
  {
  TInt id = it.GetKey();
  int len = it.GetDat().Len();
  for (int i=0; i < it.GetDat().Len(); i++)
  {
  TInt size = it.GetDat()[i];
  TInt j = i;
  if (size > 0) {

  if(br>0)
  Json.InsStr(Json.Len(),",");

  TInt size = it.GetDat()[i];

  Json.InsStr(Json.Len(),"{\"id\":"); Json.InsStr(Json.Len(),id.GetStr());
  Json.InsStr(Json.Len(),", \"size\":"); Json.InsStr(Json.Len(),size.GetStr());
  Json.InsStr(Json.Len(),", \"t\":"); Json.InsStr(Json.Len(),j.GetStr());
  Json.InsStr(Json.Len()," }\n");

  br++;

  }

  }
  }
  */

  Json.InsStr(Json.Len(), "]\n}");

}

Here is the call graph for this function:

Here is the caller graph for this function:

TStr TSnap::CmtyTest	(	TStr	InFNm,
		int	CmtyAlg
	)

Definition at line 827 of file cmty.cpp.

References CmtyEvolutionFileBatchV(), and CmtyEvolutionJson().

                                      {

  TIntIntVH sizesContV;
  TIntIntVH cContV;
  TIntIntVH edges;
  double alpha = 0.5;
  double beta = 0.75;
  CmtyEvolutionFileBatchV(InFNm, sizesContV, cContV, edges, alpha, beta, CmtyAlg);
  TStr out;
  //int a = sizesContV.Len();
  //int b = cContV.Len();
  //int c = edges.Len();
  CmtyEvolutionJson(out, sizesContV, cContV, edges);

  return out;
}

Here is the call graph for this function:

template<class PGraph >

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

Returns the number of nodes with degree NodeDeg.

Definition at line 105 of file alg.h.

Referenced by TTimeNet::LoadArxiv(), TTimeNet::LoadPatents(), and TGStat::TakeBasicStat().

                                                         {
  int Cnt = 0;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    if (NI.GetDeg() == NodeDeg) Cnt++;
  }
  return Cnt;
}

Here is the caller graph for this function:

template<class PGraph >

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

Returns the number of nodes in NodeSet that have an edge to the node NId.

Definition at line 123 of file alg.h.

References THashSet< TKey, THashFunc >::AddKey(), gfDirected, and THashSet< TKey, THashFunc >::IsKey().

                                                                               {
  if (! Graph->IsNode(NId)) { return 0; }
  const bool IsDir = Graph->HasFlag(gfDirected);
  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
  if (! IsDir) {
    int EdgesToSet = 0;
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      if (NodeSet.IsKey(NI.GetOutNId(e))) { EdgesToSet++; } }
    return EdgesToSet;
  } else {
    TIntSet Set(NI.GetDeg());
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      if (NodeSet.IsKey(NI.GetOutNId(e))) { Set.AddKey(NI.GetOutNId(e)); } }
    for (int e = 0; e < NI.GetInDeg(); e++) {
      if (NodeSet.IsKey(NI.GetInNId(e))) { Set.AddKey(NI.GetInNId(e)); } }
    return Set.Len();
  }
}

Here is the call graph for this function:

template<class PGraph >

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

Returns the number of nodes with in-degree NodeInDeg.

Definition at line 87 of file alg.h.

Referenced by TTimeNet::LoadBipartite(), and TGStat::TakeBasicStat().

                                                             {
  int Cnt = 0;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    if (NI.GetInDeg() == NodeInDeg) Cnt++;
  }
  return Cnt;
}

Here is the caller graph for this function:

template<class PGraph >

int TSnap::CntNonZNodes

(

const PGraph &

Graph

)

Returns the number of nodes with degree greater than 0.

Definition at line 114 of file alg.h.

Referenced by TTimeNet::PlotMedianDegOverTm().

                                      {
  int Cnt = 0;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    if (NI.GetDeg() > 0) Cnt++;
  }
  return Cnt;
}

Here is the caller graph for this function:

template<class PGraph >

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

Returns the number of nodes with out-degree NodeOutDeg.

Definition at line 96 of file alg.h.

Referenced by TTimeNet::LoadBipartite(), and TGStat::TakeBasicStat().

                                                               {
  int Cnt = 0;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    if (NI.GetOutDeg() == NodeOutDeg) Cnt++;
  }
  return Cnt;
}

Here is the caller graph for this function:

template<class PGraph >

int TSnap::CntSelfEdges

(

const PGraph &

Graph

)

Counts the number of self-edges in a graph. Edge (u,u) is a self-edge.

Definition at line 334 of file alg.h.

                                      {
  int Cnt = 0;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      if (NI.GetId() == NI.GetOutNId(e)) { Cnt++; }
    }
  }
  return Cnt;
}

template<class PGraph >

int TSnap::CntUniqBiDirEdges

(

const PGraph &

Graph

)

Counts unique bidirectional edges in the graph Graph. Edge is bidirectional if there exist directed edges in both directions: (u,v) and (v,u)

Definition at line 316 of file alg.h.

References CntUniqUndirEdges(), and gfDirected.

Referenced by TGStat::TakeBasicStat().

                                           {
  if (! Graph->HasFlag(gfDirected)) { // graph is undirected
    return CntUniqUndirEdges(Graph);  // then every edge is bi-directional
  }
  TIntSet NbrSet;
  int Cnt = 0;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    const int SrcId = NI.GetId();
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      const int DstId = NI.GetOutNId(e);
      if (DstId <= SrcId) { continue; } // count each un-dir edge only once
      if (Graph->IsEdge(DstId, SrcId)) { Cnt++; }
    }
  }
  return Cnt;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >

int TSnap::CntUniqDirEdges

(

const PGraph &

Graph

)

Counts unique directed edges in the graph Graph. Nodes (u,v) (where u!=v) are connected via a directed edge if there exists a directed edge from node u to node v.

Definition at line 301 of file alg.h.

References THashSet< TKey, THashFunc >::AddKey(), THashSet< TKey, THashFunc >::Clr(), and THashSet< TKey, THashFunc >::Len().

Referenced by TGStat::TakeBasicStat().

                                         {
  TIntSet NbrSet;
  int Cnt = 0;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    NbrSet.Clr(false);
    for (int e = 0; e < NI.GetOutDeg(); e++) { // unique out-neighbors of a node
      if (NI.GetOutNId(e) != NI.GetId()) { // skip self-edges
        NbrSet.AddKey(NI.GetOutNId(e)); }
    }
    Cnt += NbrSet.Len();
  }
  return Cnt;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >

int TSnap::CntUniqUndirEdges

(

const PGraph &

Graph

)

Counts unique undirected edges in the graph Graph. Nodes (u,v) (where u!=v) are connected via an undirected edge if there exists an edge in either direction (u,v) or (v,u).

Definition at line 279 of file alg.h.

References THashSet< TKey, THashFunc >::AddKey(), THashSet< TKey, THashFunc >::Clr(), and THashSet< TKey, THashFunc >::Len().

Referenced by CntUniqBiDirEdges().

                                           {
  TIntSet NbrSet;
  TIntSet SelfNbrSet;
  int Cnt = 0;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    NbrSet.Clr(false);
    for (int e = 0; e < NI.GetDeg(); e++) { // unique neighbors of a node
      const int NbrId = NI.GetNbrNId(e);
      if (NbrId == NI.GetId()) { // remember self-edges
        SelfNbrSet.AddKey(NbrId);
      } else {
        NbrSet.AddKey(NbrId);
      }
    }
    Cnt += NbrSet.Len();
  }
  // OP RS 2014/06/11 self-edges are currently not used 
  //return Cnt / 2 + SelfNbrSet.Len();
  return Cnt / 2;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 1449 of file cmty.cpp.

References TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN().

                                                           {
  return TSnapDetail::TCNMQMatrix::CmtyCMN(Graph, CmtyV);
}

Here is the call graph for this function:

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)

Definition at line 312 of file cmty.cpp.

References TSnap::TSnapDetail::_GirvanNewmanGetModularity(), TUNGraph::BegNI(), TVec< TVal, TSizeTy >::Clr(), TSnap::TSnapDetail::CmtyGirvanNewmanStep(), TUNGraph::EndNI(), TUNGraph::GetEdges(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Swap().

                                                              {
  PUNGraph LocalGraph = TSnap::ConvertGraph<PUNGraph>(Graph, false);

  TIntH OutDegH;
  const int NEdges = LocalGraph->GetEdges();
  for (TUNGraph::TNodeI NI = LocalGraph->BegNI(); NI < LocalGraph->EndNI(); NI++) {
    OutDegH.AddDat(NI.GetId(), NI.GetOutDeg());
  }
  double BestQ = -1; // modularity
  TCnComV CurCmtyV;
  CmtyV.Clr();
  TIntV Cmty1, Cmty2;
  while (true) {
    TSnapDetail::CmtyGirvanNewmanStep(LocalGraph, Cmty1, Cmty2);
    const double Q = TSnapDetail::_GirvanNewmanGetModularity(LocalGraph, OutDegH, NEdges, CurCmtyV);
    //printf("current modularity: %f\n", Q);
    if (Q > BestQ) {
      BestQ = Q; 
      CmtyV.Swap(CurCmtyV);
    }
    if (Cmty1.Len() == 0 || Cmty2.Len() == 0) { break; }
  }
  return BestQ;
}

Here is the call graph for this function:

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.

Definition at line 441 of file subgraph.h.

References CAssert, edge, gfMultiGraph, HasGraphFlag, IAssert, and TVec< TVal, TSizeTy >::Len().

                                                                                                  {
  CAssert(HasGraphFlag(typename PInGraph::TObj, gfMultiGraph)); // needs to have explicit edges
  POutGraph NewGraphPt = POutGraph::TObj::New();
  typename POutGraph::TObj& NewGraph = *NewGraphPt;
  NewGraph.Reserve(-1, EIdV.Len());
  if (! RenumberNodes) {
    for (int edge = 0; edge < EIdV.Len(); edge++) {
      const int EId = EIdV[edge];
      IAssert(InGraph->IsEdge(EId));
      const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
      const int SrcNId = EI.GetSrcNId();
      const int DstNId = EI.GetDstNId();
      if (! NewGraph.IsNode(SrcNId)) {
        NewGraph.AddNode(SrcNId); }
      if (! NewGraph.IsNode(DstNId)) {
        NewGraph.AddNode(DstNId); }
      NewGraph.AddEdge(SrcNId, DstNId);
    }
  } else {
    // renumber nodes so that node ids are 0...N-1
    TIntSet NIdSet(InGraph->GetNodes());
    for (int edge = 0; edge < EIdV.Len(); edge++) {
      const int EId = EIdV[edge];
      IAssert(InGraph->IsEdge(EId));
      const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
      const int SrcNId = NIdSet.AddKey(EI.GetSrcNId()); // map node ids
      const int DstNId = NIdSet.AddKey(EI.GetDstNId());
      if (! NewGraph.IsNode(SrcNId)) {
        NewGraph.AddNode(SrcNId); }
      if (! NewGraph.IsNode(DstNId)) {
        NewGraph.AddNode(DstNId); }
      NewGraph.AddEdge(SrcNId, DstNId);
    }
  }
  return NewGraphPt;
}

Here is the call graph for this function:

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.

Definition at line 326 of file subgraph.h.

References THashSet< TKey, THashFunc >::AddKey(), gfDirected, and HasGraphFlag.

                                                                           {
  POutGraph OutGraphPt = POutGraph::TObj::New();
  typename POutGraph::TObj& OutGraph = *OutGraphPt;
  OutGraph.Reserve(InGraph->GetNodes(), InGraph->GetEdges());
  if (! RenumberNodes) {
    for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
      OutGraph.AddNode(NI.GetId());
    }
    for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
      OutGraph.AddEdge(EI.GetSrcNId(), EI.GetDstNId());
      if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) { // add edge in the other direction
        OutGraph.AddEdge(EI.GetDstNId(), EI.GetSrcNId()); }
    }
  } else { // renumber nodes so that node ids are 0...N-1
    TIntSet NIdSet(InGraph->GetNodes());
    for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
      const int nid = NIdSet.AddKey(NI.GetId());
      OutGraph.AddNode(nid);
    }
    for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
      const int SrcNId = NIdSet.GetKeyId(EI.GetSrcNId());
      const int DstNId = NIdSet.GetKeyId(EI.GetDstNId());
      OutGraph.AddEdge(SrcNId, DstNId);
      if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
        OutGraph.AddEdge(DstNId, SrcNId); }
    }
  }
  //OutGraph.Defrag();
  return OutGraphPt;
}

Here is the call graph for this function:

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.

Definition at line 436 of file subgraph.h.

                                                                                                 {
  return TSnapDetail::TConvertSubGraph<POutGraph, PInGraph, HasGraphFlag(typename PInGraph::TObj, gfMultiGraph)>::Do(InGraph, NIdV, RenumberNodes);
}

template<class PGraph >

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

Removes all the node of out-degree OutDegK and all the nodes of in-degree InDegK from the graph.

Definition at line 445 of file alg.h.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().

                                                                        {
  TIntV DelNIdV;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    if (NI.GetOutDeg() == OutDegK || NI.GetInDeg() == InDegK) {
      DelNIdV.Add(NI.GetId());
    }
  }
  for (int i = 0; i < DelNIdV.Len(); i++) {
    Graph->DelNode(DelNIdV[i]);
  }
}

Here is the call graph for this function:

template<class PGraph >

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

Removes nodes with ids stored in NIdV from the graph.

Definition at line 425 of file alg.h.

References TVec< TVal, TSizeTy >::Len().

                                                {
  for (int n = 0; n < NIdV.Len(); n++) {
    Graph->DelNode(NIdV[n]);
  }
}

Here is the call graph for this function:

template<class PGraph >

void TSnap::DelSelfEdges

(

const PGraph &

Graph

)

Removes all the self-edges from the graph.

Definition at line 419 of file alg.h.

Referenced by CmtyEvolutionFileBatch(), ChibaNishizekiWeighter::Initialize(), TAGMFit::InitNodeData(), TAGMFast::SetGraph(), TCoda::SetGraph(), TCesna::SetGraph(), and TKronMomentsFit::Test().

                                       {
  TSnapDetail::TDelSelfEdges<PGraph, HasGraphFlag(typename PGraph::TObj, gfMultiGraph)>
    ::Do(Graph);
}

Here is the caller graph for this function:

template<class PGraph >

void TSnap::DelZeroDegNodes

(

PGraph &

Graph

)

Removes all the zero-degree nodes, that isolated nodes, from the graph.

Definition at line 432 of file alg.h.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().

Referenced by TKronMtx::PlotCmpGraphs(), and TMAGFitBern::PlotProperties().

                                    {
  TIntV DelNIdV;
  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
    if (NI.GetDeg() == 0) {
      DelNIdV.Add(NI.GetId());
    }
  }
  for (int i = 0; i < DelNIdV.Len(); i++) {
    Graph->DelNode(DelNIdV[i]);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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 with nodes colored.

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

Definition at line 34 of file gviz.h.

References TStr::GetFExt(), TStr::GetSubStr(), TSnap::TSnapDetail::GVizDoLayout(), TStr::Len(), and SaveGViz().

Referenced by TLocClust::DrawWhiskers(), and PlotRoles().

                                                                                                                                                       {
  const TStr Ext = PltFNm.GetFExt();
  const TStr GraphFNm = PltFNm.GetSubStr(0, PltFNm.Len()-Ext.Len()) + "dot";
  SaveGViz(Graph, GraphFNm, Desc, NodeLabels, NIdColorH);
  TSnap::TSnapDetail::GVizDoLayout(GraphFNm, PltFNm, Layout);
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >

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

Draws a given Graph using a selected GraphViz Layout engine with nodes labeled.

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

Definition at line 42 of file gviz.h.

References TStr::GetFExt(), TStr::GetSubStr(), TSnap::TSnapDetail::GVizDoLayout(), TStr::Len(), and SaveGViz().

                                                                                                                                {
  const TStr Ext = PltFNm.GetFExt();
  const TStr GraphFNm = PltFNm.GetSubStr(0, PltFNm.Len()-Ext.Len()) + "dot";
  SaveGViz(Graph, GraphFNm, Desc, NodeLabelH);
  TSnap::TSnapDetail::GVizDoLayout(GraphFNm, PltFNm, Layout);
}

Here is the call graph for this function:

TIntFltH TSnap::EventImportance	(	const PNGraph &	Graph,
		const int	k
	)

Event importance.

Definition at line 527 of file centr.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), and THash< TKey, TDat, THashFunc >::GetDat().

                                                            {
  TIntFltH NodeList; // values for nodese

  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
    NodeList.AddDat(NI.GetId(),NI.GetOutDeg());
  }


  for (THashKeyDatI<TInt,TFlt> NI = NodeList.BegI(); NI < NodeList.EndI(); NI++){
    int outdeg = Graph->GetNI(NI.GetKey()).GetOutDeg();
    int indeg = Graph->GetNI(NI.GetKey()).GetInDeg();
    
    if (outdeg>1 && indeg>0){
      double val = (1-(1/(double)outdeg))/(double)indeg;
      for(int i=0; i<(outdeg+indeg);i++){
        int NId = Graph->GetNI(NI.GetKey()).GetNbrNId(i);
        if (Graph->GetNI(NI.GetKey()).IsInNId(NId) == true){
        NodeList.AddDat(NId,NodeList.GetDat(NId)+val);
        }
        
      }
    }
    
  }

  return NodeList;
}

Here is the call graph for this function:

TIntFltH TSnap::EventImportance1	(	const PNGraph &	Graph,
		const int	k
	)

Definition at line 556 of file centr.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), and THash< TKey, TDat, THashFunc >::GetDat().

                                                              {
  TIntFltH NodeList; // values for nodese

  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
    NodeList.AddDat(NI.GetId(),NI.GetOutDeg());
  }


  for (THashKeyDatI<TInt,TFlt> NI = NodeList.BegI(); NI < NodeList.EndI(); NI++){
    int outdeg = Graph->GetNI(NI.GetKey()).GetOutDeg();
    int indeg = Graph->GetNI(NI.GetKey()).GetInDeg();
    
    if (outdeg>1 && indeg>0){
      double val = (1-(1/(double)outdeg))/(double)indeg;
      for(int i=0; i<(outdeg+indeg);i++){
        int NId = Graph->GetNI(NI.GetKey()).GetNbrNId(i);
        if (Graph->GetNI(NI.GetKey()).IsInNId(NId) == true){
        NodeList.AddDat(NId,NodeList.GetDat(NId)+val);
        }
        
      }
    }
    
  }

  return NodeList;
}

Here is the call graph for this function:

int TSnap::FastCorePeriphery	(	PUNGraph &	Graph,
		TIntIntH &	out
	)

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)

Definition at line 12 of file coreper.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TUNGraph::BegNI(), TUNGraph::EndNI(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::Len(), and THash< TKey, TDat, THashFunc >::SortByDat().

                                                       {

    TIntIntH nodes;
    double Z=0;

    for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){ // Calculate and store the degrees of each node.
      int deg = NI.GetDeg();
      int id = NI.GetId();
      Z += deg;
      nodes.AddDat(id,deg);
    }

    Z = Z/2;

    nodes.SortByDat(false); // Then sort the nodes in descending order of degree, to get a list of nodes {v1, v2, . . . , vn}.

    double Zbest = 99999900000000000;
    int kbest = 0;
    
    int br=0;
    for (int k=0; k<nodes.Len(); k++){
      br++;
      Z = Z + br - 1 - nodes[k];
      if (Z < Zbest){ // or <=
        Zbest = Z;
        kbest = br;
      }
    }

    int cp = 0;
    br = 0;
    for (THashKeyDatI<TInt, TInt> it = nodes.BegI();  !it.IsEnd(); it++) {
      if (br < kbest)
        cp = 1;
      else
        cp = 0;
      out.AddDat(it.GetKey(), cp);
      br++;
    }

    return kbest;
  }

Here is the call graph for this function:

int TSnap::FastCorePeripheryGC	(	PUNGraph &	Graph,
		TIntIntH &	out
	)

Definition at line 56 of file coreper.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TUNGraph::BegNI(), THash< TKey, TDat, THashFunc >::EndI(), TUNGraph::EndNI(), TUNGraph::GetNI(), TUNGraph::GetNodes(), Intersect(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::IsKey(), THash< TKey, TDat, THashFunc >::Len(), and THash< TKey, TDat, THashFunc >::SortByDat().

                                                         {
    TIntH GroupNodes; // buildup cpntainer of group nodes
    int *NNodes = new int[Graph->GetNodes()]; // container of neighbouring nodes
    int NNodes_br = 0;

    TIntIntH nodes;
    TIntIntH nodesIds;
    double Z=0;

    for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){ // Calculate and store the degrees of each node.
      int deg = NI.GetDeg();
      int id = NI.GetId();
      Z += deg;
      nodes.AddDat(id,deg);
      
    }

    Z = Z/2;

    nodes.SortByDat(false); // Then sort the nodes in descending order of degree, to get a list of nodes {v1, v2, . . . , vn}.

    int br1=0;
    for (THashKeyDatI<TInt,TInt> NI = nodes.BegI(); NI < nodes.EndI(); NI++){
      nodesIds.AddDat(NI.GetKey(),NI.GetKey());
      br1++;
    }

    double Zbest = 99999900000000000;
    //int kbest;
    //int olddeg;
    int br=0;
    for (int k=0; k<nodes.Len(); k++){
      if (k<nodes.Len()-1){
        if (nodes[k]==nodes[k+1]){ // go into same deg mode
          int kmin=-2; int knew=-1;
          while (kmin < 999999 && kmin !=-1 ){
            int kind=-1;
            knew=k;
            kmin=999999;
            while(nodes[k]==nodes[knew] && knew < nodes.Len()-1){
              int inter = Intersect(Graph->GetNI(nodesIds[knew]),NNodes,NNodes_br);
              int deg = nodes[knew];
              //if (((((nodes.Len()-NNodes_br)*(nodes.Len()-NNodes_br)))-(nodes.Len()-NNodes_br))/2<(((br*br)-br)/2))
              if ((deg-inter)<kmin && !GroupNodes.IsKey(nodesIds[knew]))
              { 
                kmin = deg-inter; kind = knew;
              }
              
              knew++;
            }
            
            if (kind!=-1){
              br++;
              Z = Z + br - 1 - nodes[kind];
              if (Z < (Zbest)){ // or <=
                //if (olddeg>nodes[kind])
                  
                //olddeg = nodes[kind];
                Zbest = Z;
                //kbest = br;
                int w = nodes[kind];
                int id = nodesIds[kind];
                GroupNodes.AddDat(id,w);
                NNodes[NNodes_br] = id;
                NNodes_br++;
              }
              else{
                
                break;
              }
            }
          }
          k=knew-1;
        }
        else{
          br++;
          Z = Z + br - 1 - nodes[k];
          if (Z < (Zbest)){ // or <=
            //if (olddeg>nodes[k])
              
            //olddeg = nodes[k];
            Zbest = Z;
            //kbest = br;
            int w = nodes[k];
            int id = nodesIds[k];
            GroupNodes.AddDat(id,w);
            NNodes[NNodes_br] = id;
            NNodes_br++;
          }
        }
      }
      
      else{
        br++;
        Z = Z + br - 1 - nodes[k];
        if (Z < Zbest){ // or <=
          //if (olddeg>nodes[k])
            
          //olddeg = nodes[k];
          Zbest = Z;
          //kbest = br;
          int w = nodes[k];
          int id = nodesIds[k];
          GroupNodes.AddDat(id,w);
          NNodes[NNodes_br] = id;
          NNodes_br++;
        }
      }
    }

    int cp = 0;
    br = 0;
    for (THashKeyDatI<TInt, TInt> it = nodes.BegI();  !it.IsEnd(); it++) {
      if (GroupNodes.IsKey(it.GetKey()))
        cp = 1;
      else
        cp = 0;
      out.AddDat(it.GetKey(), cp);
      br++;
    }

    /*for (THashKeyDatI<TInt, TInt> it = GroupNodes.BegI();  it < GroupNodes.EndI(); it++) {
      out.AddDat(it.GetKey(), 1);
      br++;
    }*/

    //return kbest;
    return GroupNodes.Len();
  }

Here is the call graph for this function:

int TSnap::FindAugV	(	const PNEANet &	Net,
		const int &	CapIndex,
		TIntV &	Flow,
		TIntQ &	FwdNodeQ,
		TIntH &	PredEdgeH,
		TIntQ &	BwdNodeQ,
		TIntH &	SuccEdgeH,
		TIntV &	MidToSrcAugV,
		TIntV &	MidToSnkAugV,
		const int &	SrcNId,
		const int &	SnkNId
	)

Returns the amount the flow can be augmented over the paths, 0 if no path can be found.

Find the augmenting path. Calls bidirectional BFS to find the path, and then builds the two path vectors.

Parameters

MidToSrcAugV	Contains the path vector from the midpoint node where the bi-d search met back to the source node.
MidToSnkAugV	Contains the path vector from the midpoint node where the bi-d search met back to the sink node.

Definition at line 71 of file flow.cpp.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::GetDat(), TNEANet::TEdgeI::GetDstNId(), TNEANet::TEdgeI::GetSrcNId(), IntFlowBiDBFS(), and TInt::Mx.

Referenced by GetMaxFlowIntEK().

                                                                                                                                                                                                                          {
  int MidPtNId = IntFlowBiDBFS(Net, CapIndex, Flow, FwdNodeQ, PredEdgeH, BwdNodeQ, SuccEdgeH, SrcNId, SnkNId);
  if (MidPtNId == -1) { return 0; }
  int MinAug = TInt::Mx, NId = MidPtNId, AugFlow = 0;
  // Build the path from the midpoint back to the source by tracing through the PredEdgeH
  for (int EId = PredEdgeH.GetDat(NId); NId != SrcNId; EId = PredEdgeH.GetDat(NId)) {
    MidToSrcAugV.Add(EId);
    const TNEANet::TEdgeI &EI = Net->GetEI(EId);
    if (EI.GetSrcNId() == NId) {
      NId = EI.GetDstNId();
      AugFlow = Flow[EId];
    } else {
      NId = EI.GetSrcNId();
      AugFlow = Net->GetIntAttrIndDatE(EId, CapIndex) - Flow[EId];
    }
    if (AugFlow < MinAug) { MinAug = AugFlow; }
  }
  NId = MidPtNId;
  // Build the path from the midpoint back to the sink by tracing through the SuccEdgeH
  for (int EId = SuccEdgeH.GetDat(NId); NId != SnkNId; EId = SuccEdgeH.GetDat(NId)) {
    MidToSnkAugV.Add(EId);
    const TNEANet::TEdgeI &EI = Net->GetEI(EId);
    if (EI.GetDstNId() == NId) {
      NId = EI.GetSrcNId();
      AugFlow = Flow[EId];
    } else {
      NId = EI.GetDstNId();
      AugFlow = Net->GetIntAttrIndDatE(EId, CapIndex) - Flow[EId];
    }
    if (AugFlow < MinAug) { MinAug = AugFlow; }
  }
  return MinAug;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int TSnap::findMinimum	(	TIntV &	Frontier,
		TIntFltH &	NIdDistH
	)

Definition at line 685 of file centr.cpp.

References TVec< TVal, TSizeTy >::Del(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), and TInt::Mx.

Referenced by GetWeightedShortestPath().

                                                     {
  TFlt minimum = TInt::Mx;
  int min_index = 0;
  for (int i = 0; i < Frontier.Len(); i++) {
    int NId = Frontier.GetVal(i);
    if (NIdDistH.GetDat(NId) < minimum) {
      minimum = NIdDistH.GetDat(NId);
      min_index = i;
    }
  }
  const int NId = Frontier.GetVal(min_index);
  Frontier.Del(min_index);
  return NId;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 174 of file ggen.h.

References TMath::Power(), and TMath::Round().

                                                           {
  const int Nodes = (int) TMath::Round(TMath::Power(5, Levels));
  PGraph GraphPt = PGraph::New();
  typename PGraph::TObj& Graph = *GraphPt;
  Graph.Reserve(Nodes, -1);
  // base graph
  for (int i = 0; i < 5; i++) { Graph.AddNode(i); }
  Graph.AddEdge(1,2);  Graph.AddEdge(2,3);
  Graph.AddEdge(3,4);  Graph.AddEdge(4,1);
  Graph.AddEdge(1,0);  Graph.AddEdge(3,0);
  Graph.AddEdge(2,0);  Graph.AddEdge(4,0);
  // expansion
  const int CenterId = 0;
  for (int lev = 1; lev < Levels+1; lev++) {
    const int MxNId = Graph.GetNodes();
    // make 4 duplicate copies
    for (int d = 0; d < 4; d++) {
      for (int n = 0; n < MxNId; n++) { Graph.AddNode(); }
      for (int n = 0; n < MxNId; n++) {
        typename PGraph::TObj::TNodeI NI = Graph.GetNI(n);
        const int SrcId = n+MxNId*(d+1);
        for (int e = 0; e < NI.GetOutDeg(); e++) {
          Graph.AddEdge(SrcId, NI.GetOutNId(e)+MxNId*(d+1));
        }
      }
    }
    // add edges to the center
    //const int LevPow = (int)TMath::Round(TMath::Power(5,lev-1));
    for (int n = MxNId; n < Graph.GetNodes(); n++) {
      //typename PGraph::TObj::TNodeI NI = Graph.GetNI(n);
      const int SrcId = n;
      int Pow = 1;  bool Skip = false;
      for (int p = 1; p <= lev; p++) {
        if (SrcId % (5*Pow) < Pow) { Skip=true; break; }
        Pow *= 5;
      }
      if (Skip) { continue; }
      Graph.AddEdge(SrcId, CenterId);
    }
  }
  return GraphPt;
}

Here is the call graph for this function:

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.

Definition at line 104 of file ggen.h.

References gfDirected.

                                                                             {
  PGraph Graph = PGraph::TObj::New();
  Graph->Reserve(Nodes, Nodes*NodeOutDeg);
  for (int n = 0; n < Nodes; n++) {
    Graph->AddNode(n); }
  for (int n = 0; n < Nodes; n++) {
    for (int x = 0; x < NodeOutDeg; x++) {
      Graph->AddEdge(n, (n+x+1) % Nodes);
      if (Graph->HasFlag(gfDirected) && ! IsDir) { Graph->AddEdge((n+x+1) % Nodes, n); }
    }
  }
  return Graph;
}

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

Generates a random undirect graph with a given degree sequence.

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!

Definition at line 122 of file ggen.cpp.

References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), TRnd::GetUniDevInt(), THashSet< TKey, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), TMath::Mn(), TUNGraph::New(), TUNGraph::Reserve(), and Swap().

Referenced by GenConfModel(), GenRndPowerLaw(), and TTimeNet::PlotEffDiam().

                                                       {
  const int Nodes = DegSeqV.Len();
  PUNGraph GraphPt = TUNGraph::New();
  TUNGraph& Graph = *GraphPt;
  Graph.Reserve(Nodes, -1);
  TIntV NIdDegV(DegSeqV.Len(), 0);
  int DegSum=0, edges=0;
  for (int node = 0; node < Nodes; node++) {
    Graph.AddNode(node);
    for (int d = 0; d < DegSeqV[node]; d++) { NIdDegV.Add(node); }
    DegSum += DegSeqV[node];
  }
  NIdDegV.Shuffle(Rnd);
  TIntPrSet EdgeH(DegSum/2); // set of all edges, is faster than graph edge lookup
  if (DegSum % 2 != 0) {
    printf("Seg seq is odd [%d]: ", DegSeqV.Len());
    for (int d = 0; d < TMath::Mn(100, DegSeqV.Len()); d++) { printf("  %d", (int)DegSeqV[d]); }
    printf("\n");
  }
  int u=0, v=0;
  for (int c = 0; NIdDegV.Len() > 1; c++) {
    u = Rnd.GetUniDevInt(NIdDegV.Len());
    while ((v = Rnd.GetUniDevInt(NIdDegV.Len())) == u) { }
    if (u > v) { Swap(u, v); }
    const int E1 = NIdDegV[u];
    const int E2 = NIdDegV[v];
    if (v == NIdDegV.Len()-1) { NIdDegV.DelLast(); } 
    else { NIdDegV[v] = NIdDegV.Last();  NIdDegV.DelLast(); }
    if (u == NIdDegV.Len()-1) { NIdDegV.DelLast(); } 
    else { NIdDegV[u] = NIdDegV.Last();  NIdDegV.DelLast(); }
    if (E1 == E2 || EdgeH.IsKey(TIntPr(E1, E2))) { continue; }
    EdgeH.AddKey(TIntPr(E1, E2));
    Graph.AddEdge(E1, E2);
    edges++;
    if (c % (DegSum/100+1) == 0) { printf("\r configuration model: iter %d: edges: %d, left: %d", c, edges, NIdDegV.Len()/2); }
  }
  printf("\n");
  return GraphPt;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PUNGraph TSnap::GenConfModel

(

const PUNGraph &

G

)

Generate a random graph using (approximately) the same node degrees as in G using the configuration model.

Definition at line 338 of file ggen.cpp.

References GenConfModel(), GetDegSeqV(), and TUNGraph::GetNodes().

                                         {
  TIntV DegSeqV(G->GetNodes(), 0);
  TSnap::GetDegSeqV(G, DegSeqV);
  return TSnap::GenConfModel(DegSeqV);
}

Here is the call graph for this function:

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

Generates a random scale-free network using the Copying Model.

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

Definition at line 456 of file ggen.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TNGraph::GetRndNId(), TRnd::GetUniDev(), TRnd::GetUniDevInt(), TNGraph::New(), and TNGraph::Reserve().

                                                                      {
  PNGraph GraphPt = TNGraph::New();
  TNGraph& Graph = *GraphPt;
  Graph.Reserve(Nodes, Nodes);
  const int startNId = Graph.AddNode();
  Graph.AddEdge(startNId, startNId);
  for (int n = 1; n < Nodes; n++) {
    const int rnd = Graph.GetRndNId();
    const int NId = Graph.AddNode();
    if (Rnd.GetUniDev() < Beta) {
      Graph.AddEdge(NId, rnd); }
    else {
      const TNGraph::TNodeI NI = Graph.GetNI(rnd);
      const int rnd2 = Rnd.GetUniDevInt(NI.GetOutDeg());
      Graph.AddEdge(NId, NI.GetOutNId(rnd2));
    }
  }
  return GraphPt;
}

Here is the call graph for this function:

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

Generates a random graph with exact degree sequence.

Generates a random graph with exact degree sequence DegSeqV. DegSeqV must be sorted in descending order. 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.

Definition at line 61 of file ggen.cpp.

References TUNGraph::AddEdge(), TUNGraph::AddNode(), TUNGraph::DelEdge(), edge, TSnap::TSnapDetail::GetRndEdgeNonAdjNode(), IAssert, IAssertR, TUNGraph::IsEdge(), TVec< TVal, TSizeTy >::IsSorted(), TVec< TVal, TSizeTy >::Len(), TUNGraph::New(), TUNGraph::Reserve(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

Referenced by GenRndDegK(), and GenRndPowerLaw().

                                                    {
  const int Nodes = DegSeqV.Len();
  PUNGraph GraphPt = TUNGraph::New();
  TUNGraph& Graph = *GraphPt;
  Graph.Reserve(Nodes, -1);
  TIntH DegH(DegSeqV.Len(), true);
  
  IAssertR(DegSeqV.IsSorted(false), "DegSeqV must be sorted in descending order.");
  int DegSum=0, edge=0;
  for (int node = 0; node < Nodes; node++) {
    IAssert(Graph.AddNode(node) == node);
    DegH.AddDat(node, DegSeqV[node]);
    DegSum += DegSeqV[node];
  }
  IAssert(DegSum % 2 == 0);
  while (! DegH.Empty()) {
    // pick random nodes and connect
    const int NId1 = DegH.GetKey(DegH.GetRndKeyId(Rnd, 0.5));
    const int NId2 = DegH.GetKey(DegH.GetRndKeyId(Rnd, 0.5));
    IAssert(DegH.IsKey(NId1) && DegH.IsKey(NId2));
    if (NId1 == NId2) {
      if (DegH.GetDat(NId1) == 1) { continue; }
      // find rnd edge, break it, and connect the endpoints to the nodes
      const TIntPr Edge = TSnapDetail::GetRndEdgeNonAdjNode(GraphPt, NId1, -1);
      if (Edge.Val1==-1) { continue; }
      Graph.DelEdge(Edge.Val1, Edge.Val2);
      Graph.AddEdge(Edge.Val1, NId1);
      Graph.AddEdge(NId1, Edge.Val2);
      if (DegH.GetDat(NId1) == 2) { DegH.DelKey(NId1); }
      else { DegH.GetDat(NId1) -= 2; }
    } else {
      if (! Graph.IsEdge(NId1, NId2)) {
        Graph.AddEdge(NId1, NId2); }  // good edge
      else {
        // find rnd edge, break and cross-connect
        const TIntPr Edge = TSnapDetail::GetRndEdgeNonAdjNode(GraphPt, NId1, NId2);
        if (Edge.Val1==-1) { continue; }
        Graph.DelEdge(Edge.Val1, Edge.Val2);
        Graph.AddEdge(NId1, Edge.Val1);
        Graph.AddEdge(NId2, Edge.Val2);
      }
      if (DegH.GetDat(NId1)==1) { DegH.DelKey(NId1); }
      else { DegH.GetDat(NId1) -= 1; }
      if (DegH.GetDat(NId2)==1) { DegH.DelKey(NId2); }
      else { DegH.GetDat(NId2) -= 1; }
    }
    if (++edge % 1000 == 0) {
      printf("\r %dk / %dk", edge/1000, DegSum/2000); }
  }
  return GraphPt;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Generates a random Forest Fire, directed graph with given probabilities.

Definition at line 445 of file ggen.cpp.

References TForestFire::GenGraph().

                                                                                      {
  return TForestFire::GenGraph(Nodes, FwdProb, BckProb);
}

Here is the call graph for this function:

template<class PGraph >

PGraph TSnap::GenFull

(

const int &

Nodes

)

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

Definition at line 119 of file ggen.h.

                                 {
  PGraph Graph = PGraph::TObj::New();
  Graph->Reserve(Nodes, Nodes*Nodes);
  for (int n = 0; n < Nodes; n++) {
    Graph->AddNode(n); }
  for (int n1 = 0; n1 < Nodes; n1++) {
    for (int n2 = 0; n2 < Nodes; n2++) {
      if (n1 != n2) { Graph->AddEdge(n1, n2); }
    }
  }
  return Graph;
}

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

Generates a random scale-free graph using the Geometric Preferential model.

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

Definition at line 364 of file ggen.cpp.

References TVec< TVal, TSizeTy >::Add(), TUNGraph::AddEdge(), TUNGraph::AddNode(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Del(), TUNGraph::TNodeI::GetDeg(), TUNGraph::GetNI(), TSnap::TSnapDetail::GetSphereDev(), TRnd::GetUniDevInt(), TUNGraph::IsNode(), TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), TUNGraph::New(), TMath::Pi, TMath::Sqr(), TTriple< TVal1, TVal2, TVal3 >::Val1, TTriple< TVal1, TVal2, TVal3 >::Val2, and TTriple< TVal1, TVal2, TVal3 >::Val3.

                                                                                              {
  PUNGraph G = TUNGraph::New(Nodes, Nodes*OutDeg);
  TFltTrV PointV(Nodes, 0);
  TFltV ValV;
  // points on a sphere of radius 1/(2*pi)
  const double Rad = 0.5 * TMath::Pi;
  for (int i = 0; i < Nodes; i++) {
    TSnapDetail::GetSphereDev(3, Rnd, ValV);
    PointV.Add(TFltTr(Rad*ValV[0], Rad*ValV[1], Rad*ValV[2]));
  }
  const double R2 = TMath::Sqr(log((double) Nodes) / (pow((double) Nodes, 0.5-Beta)));
  TIntV DegV, NIdV;
  int SumDeg;
  for (int t = 0; t < Nodes; t++) {
    const int pid = t;
    const TFltTr& P1 = PointV[pid];
    // add node
    if (! G->IsNode(pid)) { G->AddNode(pid); }
    // find neighborhood
    DegV.Clr(false);  NIdV.Clr(false);  SumDeg=0;
    for (int p = 0; p < t; p++) {
      const TFltTr& P2 = PointV[p];
      if (TMath::Sqr(P1.Val1-P2.Val1)+TMath::Sqr(P1.Val2-P2.Val2)+TMath::Sqr(P1.Val3-P2.Val3) < R2) {
        NIdV.Add(p);
        DegV.Add(G->GetNI(p).GetDeg()+1);
        SumDeg += DegV.Last();
      }
    }
    // add edges
    for (int m = 0; m < OutDeg; m++) {
      const int rnd = Rnd.GetUniDevInt(SumDeg);
      int sum = 0, dst = -1;
      for (int s = 0; s < DegV.Len(); s++) {
        sum += DegV[s];
        if (rnd < sum) { dst=s;  break; }
      }
      if (dst != -1) {
        G->AddEdge(pid, NIdV[dst]);
        SumDeg -= DegV[dst];
        NIdV.Del(dst);  DegV.Del(dst);
      }
    }
  }
  return G;
}

Here is the call graph for this function:

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.

Definition at line 65 of file ggen.h.

References gfDirected.

                                                                    {
  PGraph GraphPt = PGraph::New();
  typename PGraph::TObj& Graph = *GraphPt;
  Graph.Reserve(Rows*Cols, 4*Rows*Cols);
  int node, r, c;
  for (node = 0; node < Rows * Cols; node++) {
    Graph.AddNode(node); }
  for (r = 0; r < Rows; r++) {
    for (c = 0; c < Cols; c++) {
      const int nodeId = Cols*r + c;
      if (r < Rows-1) { // bottom node
        Graph.AddEdge(nodeId, nodeId+Cols); 
        if (Graph.HasFlag(gfDirected) && ! IsDir) { 
          Graph.AddEdge(nodeId+Cols, nodeId); }
      }
      if (c < Cols-1) { // right node
        Graph.AddEdge(nodeId, nodeId+1); 
        if (Graph.HasFlag(gfDirected) && ! IsDir) { 
          Graph.AddEdge(nodeId+1, nodeId); }
      }
    }
  }
  return GraphPt;
}

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

Generates a power-law degree distribution using Barabasi-Albert model of scale-free graphs.

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

Definition at line 313 of file ggen.cpp.

References TVec< TVal, TSizeTy >::Add(), TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), THashSet< TKey, THashFunc >::Clr(), TRnd::GetUniDevInt(), TVec< TVal, TSizeTy >::Len(), THashSet< TKey, THashFunc >::Len(), TPt< TRec >::New(), and TUNGraph::Reserve().

                                                                           {
  PUNGraph GraphPt = PUNGraph::New();
  TUNGraph& Graph = *GraphPt;
  Graph.Reserve(Nodes, NodeOutDeg*Nodes);
  TIntV NIdV(NodeOutDeg*Nodes, 0);
  // first edge
  Graph.AddNode(0);  Graph.AddNode(1);
  NIdV.Add(0);  NIdV.Add(1);
  Graph.AddEdge(0, 1);
  TIntSet NodeSet;
  for (int node = 2; node < Nodes; node++) {
    NodeSet.Clr(false);
    while (NodeSet.Len() < NodeOutDeg && NodeSet.Len() < node) {
      NodeSet.AddKey(NIdV[Rnd.GetUniDevInt(NIdV.Len())]);
    }
    const int N = Graph.AddNode();
    for (int i = 0; i < NodeSet.Len(); i++) {
      Graph.AddEdge(N, NodeSet[i]);
      NIdV.Add(N);
      NIdV.Add(NodeSet[i]);
    }
  }
  return GraphPt;
}

Here is the call graph for this function:

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

Rewire a random undirected graph. Keeps node degrees the same, but randomly rewires the edges.

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

Definition at line 168 of file ggen.cpp.

References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), TUNGraph::BegNI(), THashSet< TKey, THashFunc >::DelKeyId(), TUNGraph::EndNI(), TUNGraph::GetEdges(), TUNGraph::GetNodes(), THashSet< TKey, THashFunc >::GetRndKeyId(), TExeTm::GetSecs(), TExeTm::GetStr(), THashSet< TKey, THashFunc >::IsKey(), THashSet< TKey, THashFunc >::Len(), TUNGraph::New(), TUNGraph::Reserve(), Swap(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

Referenced by GenRndDegK(), GenRndPowerLaw(), and TLocClust::PlotNCP().

                                                                             {
  const int Nodes = OrigGraph->GetNodes();
  const int Edges = OrigGraph->GetEdges();
  PUNGraph GraphPt = TUNGraph::New();
  TUNGraph& Graph = *GraphPt;
  Graph.Reserve(Nodes, -1);
  TExeTm ExeTm;
  // generate a graph that satisfies the constraints
  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
  TIntPrSet EdgeSet(Edges);
  for (TUNGraph::TNodeI NI = OrigGraph->BegNI(); NI < OrigGraph->EndNI(); NI++) {
    const int NId = NI.GetId();
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      if (NId <= NI.GetOutNId(e)) { continue; }
      EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e)));
    }
    Graph.AddNode(NI.GetId());
  }
  // edge switching
  uint skip=0;
  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
    const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
    const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
    if (keyId1 == keyId2) { skip++; continue; }
    const TIntPr& E1 = EdgeSet[keyId1];
    const TIntPr& E2 = EdgeSet[keyId2];
    TIntPr NewE1(E1.Val1, E2.Val1), NewE2(E1.Val2, E2.Val2);
    if (NewE1.Val1 > NewE1.Val2) { Swap(NewE1.Val1, NewE1.Val2); }
    if (NewE2.Val1 > NewE2.Val2) { Swap(NewE2.Val1, NewE2.Val2); }
    if (NewE1!=NewE2 && NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
      EdgeSet.DelKeyId(keyId1);  EdgeSet.DelKeyId(keyId2);
      EdgeSet.AddKey(TIntPr(NewE1));
      EdgeSet.AddKey(TIntPr(NewE2));
    } else { skip++; }
    if (swps % Edges == 0) {
      printf("\r  %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
      if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
    }
  }
  printf("\r  total %uk switchings attempted, %uk skiped  [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
  for (int e = 0; e < EdgeSet.Len(); e++) {
    Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
  return GraphPt;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Rewire a random directed graph. Keeps node degrees the same, but randomly rewires the edges.

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

Definition at line 219 of file ggen.cpp.

References TNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TNGraph::AddNode(), THashSet< TKey, THashFunc >::DelKeyId(), THashSet< TKey, THashFunc >::GetRndKeyId(), TExeTm::GetSecs(), TExeTm::GetStr(), THashSet< TKey, THashFunc >::IsKey(), THashSet< TKey, THashFunc >::Len(), TNGraph::New(), TNGraph::Reserve(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

                                                                           {
  const int Nodes = OrigGraph->GetNodes();
  const int Edges = OrigGraph->GetEdges();
  PNGraph GraphPt = TNGraph::New();
  TNGraph& Graph = *GraphPt;
  Graph.Reserve(Nodes, -1);
  TExeTm ExeTm;
  // generate a graph that satisfies the constraints
  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
  TIntPrSet EdgeSet(Edges);
  for (TNGraph::TNodeI NI = OrigGraph->BegNI(); NI < OrigGraph->EndNI(); NI++) {
    const int NId = NI.GetId();
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e))); }
    Graph.AddNode(NI);
  }
  // edge switching
  uint skip=0;
  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
    const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
    const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
    if (keyId1 == keyId2) { skip++; continue; }
    const TIntPr& E1 = EdgeSet[keyId1];
    const TIntPr& E2 = EdgeSet[keyId2];
    TIntPr NewE1(E1.Val1, E2.Val2), NewE2(E2.Val1, E1.Val2);
    if (NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && NewE1.Val1!=NewE2.Val1 && NewE1.Val2!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
      EdgeSet.DelKeyId(keyId1);  EdgeSet.DelKeyId(keyId2);
      EdgeSet.AddKey(TIntPr(NewE1));
      EdgeSet.AddKey(TIntPr(NewE2));
    } else { skip++; }
    if (swps % Edges == 0) {
      printf("\r  %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
      if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
    }
  }
  printf("\r  total %uk switchings attempted, %uk skiped  [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
  for (int e = 0; e < EdgeSet.Len(); e++) {
    Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
  return GraphPt;
}

Here is the call graph for this function:

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

Rewire a random bipartite graph. Keeps node degrees the same, but randomly rewires the edges.

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

Definition at line 266 of file ggen.cpp.

References TBPGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TBPGraph::AddNode(), THashSet< TKey, THashFunc >::DelKeyId(), THashSet< TKey, THashFunc >::GetRndKeyId(), TExeTm::GetSecs(), TExeTm::GetStr(), IAssert, THashSet< TKey, THashFunc >::IsKey(), THashSet< TKey, THashFunc >::Len(), TBPGraph::New(), TBPGraph::Reserve(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

                                                                             {
  const int Nodes = OrigGraph->GetNodes();
  const int Edges = OrigGraph->GetEdges();
  PBPGraph GraphPt = TBPGraph::New();
  TBPGraph& Graph = *GraphPt;
  Graph.Reserve(Nodes, -1);
  TExeTm ExeTm;
  // generate a graph that satisfies the constraints
  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
  TIntPrSet EdgeSet(Edges);
  for (TBPGraph::TNodeI NI = OrigGraph->BegLNI(); NI < OrigGraph->EndLNI(); NI++) {
    const int NId = NI.GetId();
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e))); } // edges left-->right
    Graph.AddNode(NI.GetId(), true); } // left nodes
  for (TBPGraph::TNodeI NI = OrigGraph->BegRNI(); NI < OrigGraph->EndRNI(); NI++) {
    Graph.AddNode(NI.GetId(), false); } // right nodes
  IAssert(EdgeSet.Len() == Edges);
  // edge switching
  uint skip=0;
  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
    const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
    const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
    if (keyId1 == keyId2) { skip++; continue; }
    const TIntPr& E1 = EdgeSet[keyId1];
    const TIntPr& E2 = EdgeSet[keyId2];
    TIntPr NewE1(E1.Val1, E2.Val2), NewE2(E2.Val1, E1.Val2);
    if (NewE1!=NewE2 && NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
      EdgeSet.DelKeyId(keyId1);  EdgeSet.DelKeyId(keyId2);
      EdgeSet.AddKey(TIntPr(NewE1));
      EdgeSet.AddKey(TIntPr(NewE2));
    } else { skip++; }
    if (swps % Edges == 0) {
      printf("\r  %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
      if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
    }
  }
  printf("\r  total %uk switchings attempted, %uk skiped  [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
  for (int e = 0; e < EdgeSet.Len(); e++) {
    Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
  return GraphPt;
}

Here is the call graph for this function:

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

Generates a R-MAT graph using recursive descent into a 2x2 matrix [A,B; C, 1-(A+B+C)].

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

Definition at line 481 of file ggen.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::Defrag(), edge, Fail, TRnd::GetUniDev(), IAssert, TNGraph::IsEdge(), TNGraph::New(), and TNGraph::Reserve().

Referenced by GenRMatEpinions().

                                                                                                                  {
  PNGraph GraphPt = TNGraph::New();
  TNGraph& Graph = *GraphPt;
  Graph.Reserve(Nodes, Edges);
  IAssert(A+B+C < 1.0);
  int rngX, rngY, offX, offY;
  int Depth=0, Collisions=0, Cnt=0, PctDone=0;
  const int EdgeGap = Edges / 100 + 1;
  // sum of parameters (probabilities)
  TVec<double> sumA(128, 0), sumAB(128, 0), sumAC(128, 0), sumABC(128, 0);  // up to 2^128 vertices ~ 3.4e38
  for (int i = 0; i < 128; i++) {
    const double a = A * (Rnd.GetUniDev() + 0.5);
    const double b = B * (Rnd.GetUniDev() + 0.5);
    const double c = C * (Rnd.GetUniDev() + 0.5);
    const double d = (1.0 - (A+B+C)) * (Rnd.GetUniDev() + 0.5);
    const double abcd = a+b+c+d;
    sumA.Add(a / abcd);
    sumAB.Add((a+b) / abcd);
    sumAC.Add((a+c) / abcd);
    sumABC.Add((a+b+c) / abcd);
  }
  // nodes
  for (int node = 0; node < Nodes; node++) {
    IAssert(Graph.AddNode(-1) == node);
  }
  // edges
  for (int edge = 0; edge < Edges; ) {
    rngX = Nodes;  rngY = Nodes;  offX = 0;  offY = 0;
    Depth = 0;
    // recurse the matrix
    while (rngX > 1 || rngY > 1) {
      const double RndProb = Rnd.GetUniDev();
      if (rngX>1 && rngY>1) {
        if (RndProb < sumA[Depth]) { rngX/=2; rngY/=2; }
        else if (RndProb < sumAB[Depth]) { offX+=rngX/2;  rngX-=rngX/2;  rngY/=2; }
        else if (RndProb < sumABC[Depth]) { offY+=rngY/2;  rngX/=2;  rngY-=rngY/2; }
        else { offX+=rngX/2;  offY+=rngY/2;  rngX-=rngX/2;  rngY-=rngY/2; }
      } else
      if (rngX>1) { // row vector
        if (RndProb < sumAC[Depth]) { rngX/=2; rngY/=2; }
        else { offX+=rngX/2;  rngX-=rngX/2;  rngY/=2; }
      } else
      if (rngY>1) { // column vector
        if (RndProb < sumAB[Depth]) { rngX/=2; rngY/=2; }
        else { offY+=rngY/2;  rngX/=2;  rngY-=rngY/2; }
      } else { Fail; }
      Depth++;
    }
    // add edge
    const int NId1 = offX;