SNAP Library 4.0, User Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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). GetBfsEffDiam3. 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. GetBfsEffDiam4. 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)
 
PUNGraphAllGraphsWithNNodes (int n)
 
TIntHAllCombinationsMN (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< PNGraphLoadDyNetGraphV (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, TVec< TFltV > &LeftSV, TVec< TFltV > &RightSV)
 
void GetEigVals (const PUNGraph &Graph, const int &EigVals, TFltV &EigValV)
 Computes top EigVals eigenvalues of the adjacency matrix representing a given undirected Graph. 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, TVec< TFltV > &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 &ArndEdges)
 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 &InEdges, int &OutEdges)
 Returns the egonet of node CtrNId as center in directed graph Graph. And returns number of edges go in and out the egonet. More...
 
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 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...
 
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 &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 >
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 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

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.

369  {
370  TIntV EdgeV;
371  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
372  const int NId = NI.GetId();
373  if (! Graph->IsEdge(NId, NId)) {
374  EdgeV.Add(NId);
375  }
376  }
377  for (int i = 0; i < EdgeV.Len(); i++) {
378  Graph->AddEdge(EdgeV[i], EdgeV[i]);
379  }
380 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TIntH* TSnap::AllCombinationsMN ( int  m,
int  n 
)

Definition at line 157 of file centr.cpp.

157  {
158  float N = 1;
159  for(int i=n; i>0; i--){
160  N *= (float)m/(float)n;
161  m--;
162  n--;
163  }
164 
165  TIntH* C = new TIntH[(int)N];
166  return C;
167 }
PUNGraph* TSnap::AllGraphsWithNNodes ( int  n)

Definition at line 138 of file centr.cpp.

138  {
139  PUNGraph* g = new PUNGraph[(((n*n)-n)/2)+1];
140  PUNGraph g0;
141  for(int i=0; i<n; i++)
142  g0->AddNode(i);
143 
144  g[0] = g0;
145  int br=1;
146 
147  for(int i=0; i<n; i++)
148  for(int j=i; j<n; j++){
149  g0->AddEdge(i,j);
150  g[br] = g0;
151  br++;
152  }
153 
154  return g;
155 }
Definition: bd.h:196
double TSnap::BorgattiEverettMeasure ( PUNGraph Graph,
TIntIntH out,
double  coresize,
int  type 
)

Definition at line 186 of file coreper.cpp.

186  {
187 
188  double sum = 0.0;
189  for (TUNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++){ // Calculate and store the degrees of each node.
190  int i = EI.GetSrcNId();
191  int j = EI.GetDstNId();
192  if (type == 1) {
193  if (out.GetDat(i) == 1 || out.GetDat(j) == 1)
194  sum += 1;
195  }
196  else {
197  if (out.GetDat(i) == 1 && out.GetDat(j) == 1)
198  sum += 1;
199  }
200  }
201 
202  return sum/(((coresize*coresize)-coresize)/2);
203  }
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
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.

135  {
136  // Attribute to Int mapping
137  TInt SIdx = P->GetColIdx(C1);
138  TInt DIdx = P->GetColIdx(C2);
139  TInt StIdx = P->GetColIdx(C3);
140  TInt DuIdx = P->GetColIdx(C4);
141  TIntV MapV, PhyV;
142  TStrV SortBy;
143  SortBy.Add(C3);
144  P->Order(SortBy);
145  int count = 0;
146  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
147  MapV.Add(RI.GetRowIdx());
148  PhyV.Add(count++);
149  }
150  // After sort attach with each row a rank helpful for sorting
151  P->StoreIntCol("Physical",PhyV);
152  TInt PIdx = P->GetColIdx("Physical");
153  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
154  // Check for top cascades
155  if (NI.GetInDeg() != 0) { continue;}
156  TIntV CurCasc;
157  TSnapQueue<TInt> EventQ;
158  THashSet<TInt> VisitedH;
159  TInt NId = NI.GetId();
160  EventQ.Push(NId);
161  VisitedH.AddKey(NId);
162  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,NId));
163  while (! EventQ.Empty()) {
164  TNGraph::TNodeI CNI = Graph->GetNI(EventQ.Top().Val); //Get Current Node
165  EventQ.Pop();
166  // Go over the outdegree nodes of the currernt node
167  for (int e = 0; e < CNI.GetOutDeg(); e++) {
168  TInt CId = CNI.GetOutNId(e);
169  if ( !VisitedH.IsKey(CId)) {
170  EventQ.Push(CId);
171  VisitedH.AddKey(CId);
172  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,CId));
173  }
174  }
175  }
176  CurCasc.Sort();
177  TIntV ToAddV;
178  if (Print && VisitedH.Len() > 1) {
179  printf("__casacade__\t%d\n",VisitedH.Len());
180  }
181  for (TIntV::TIter VI = CurCasc.BegI(); VI < CurCasc.EndI(); VI++) {
182  ToAddV.Add(MapV.GetVal(VI->Val));
183  if (Print && VisitedH.Len() > 1) {
184  int PIdx = MapV.GetVal(VI->Val).Val;
185  int PSource = P->GetIntValAtRowIdx(SIdx,PIdx).Val;
186  int PDest = P->GetIntValAtRowIdx(DIdx,PIdx).Val;
187  int PStart = P->GetIntValAtRowIdx(StIdx,PIdx).Val;
188  int PDur = P->GetIntValAtRowIdx(DuIdx,PIdx).Val;
189  printf("%d\t%d\t%d\t%d\t%d\n",PIdx,PSource,PDest,PStart,PDur);
190  }
191  }
192  if (ToAddV.Len() > 1) {
193  TopCascVV.Add(ToAddV);
194  }
195  }
196  return;
197 }
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
int Val
Definition: dt.h:1136
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
void Pop()
Removes the first element from the queue.
Definition: gbase.h:198
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:186
Iterator class for TTable rows.
Definition: table.h:330
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
int AddKey(const TKey &Key)
Definition: shash.h:1254
Definition: dt.h:1134
int Len() const
Definition: shash.h:1121
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:201
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
Fast Queue used by the TBreathFS (uses memcpy to move objects TVal around).
Definition: gbase.h:158
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:196
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
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.

200  {
201  // Attribute to Int mapping
202  TInt SIdx = P->GetColIdx(C1);
203  TInt DIdx = P->GetColIdx(C2);
204  TInt StIdx = P->GetColIdx(C3);
205  TInt DuIdx = P->GetColIdx(C4);
206  TIntV MapV, PhyV;
207  TStrV SortBy;
208  SortBy.Add(C3);
209  P->Order(SortBy);
210  int count = 0;
211  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
212  MapV.Add(RI.GetRowIdx());
213  PhyV.Add(count++);
214  }
215  P->StoreIntCol("Physical",PhyV);
216  TInt PIdx = P->GetColIdx("Physical");
217  TIntV GNodeV;
218  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
219  if (NI.GetInDeg() == 0) { GNodeV.Add(NI.GetId()); }
220  }
221  TVec<TIntV> ThTopCascVV; // for each thread
222  #pragma omp parallel private(ThTopCascVV) num_threads(10)
223  {
224  #pragma omp for schedule(dynamic,1000)
225  for (int i = 0; i < GNodeV.Len(); i++) {
226  TIntV CurCasc;
227  TSnapQueue<TInt> EventQ;
228  THashSet<TInt> VisitedH;
229  TInt NId = GNodeV[i];
230  EventQ.Push(NId);
231  VisitedH.AddKey(NId);
232  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,NId));
233  while (! EventQ.Empty()) {
234  TNGraph::TNodeI CNI = Graph->GetNI(EventQ.Top().Val); //Get Current Node
235  EventQ.Pop();
236  // Go over the outdegree nodes of the currernt node
237  for (int e = 0; e < CNI.GetOutDeg(); e++) {
238  TInt CId = CNI.GetOutNId(e);
239  if ( !VisitedH.IsKey(CId)) {
240  EventQ.Push(CId);
241  VisitedH.AddKey(CId);
242  CurCasc.Add(P->GetIntValAtRowIdx(PIdx,CId));
243  }
244  }
245  }
246  CurCasc.Sort();
247  TIntV ToAddV;
248  for (TIntV::TIter VI = CurCasc.BegI(); VI < CurCasc.EndI(); VI++) {
249  ToAddV.Add(MapV.GetVal(VI->Val));
250  }
251  if (ToAddV.Len() > 1) { ThTopCascVV.Add(ToAddV);}
252  }
253  #pragma omp critical
254  {
255  for (int j = 0; j < ThTopCascVV.Len(); j++) {
256  TopCascVV.Add(ThTopCascVV[j]);
257  }
258  }
259  }
260  return;
261 }
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
int Val
Definition: dt.h:1136
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
void Pop()
Removes the first element from the queue.
Definition: gbase.h:198
bool Empty() const
Tests whether the queue is empty (contains no elements).
Definition: gbase.h:186
Iterator class for TTable rows.
Definition: table.h:330
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
int AddKey(const TKey &Key)
Definition: shash.h:1254
Definition: dt.h:1134
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:201
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
Fast Queue used by the TBreathFS (uses memcpy to move objects TVal around).
Definition: gbase.h:158
const TVal & Top() const
Returns the value of the first element in the queue, but does not remove the element.
Definition: gbase.h:196
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
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.

126  {
127  if (SortParam) {
128  return CascGraphSource(P, C1, C2, C3, C4, W);
129  }
130  else {
131  return CascGraphTime(P, C1, C2, C3, C4, W);
132  }
133 }
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...
Definition: casc.cpp:3
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...
Definition: casc.cpp:59
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.

3  {
4  // Attribute to Int mapping
5  TInt SIdx = P->GetColIdx(C1); //Source
6  TInt DIdx = P->GetColIdx(C2); //Dest
7  TInt StIdx = P->GetColIdx(C3); //Start
8  TInt DuIdx = P->GetColIdx(C4); //Duration
9  TIntV MapV;
10  TStrV SortBy;
11  SortBy.Add(C1);
12  P->Order(SortBy);
13  TIntV Source;
14  P->ReadIntCol(C1,Source);
15  PNGraph Graph = TNGraph::New();
16  //Add Nodes
17  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
18  Graph->AddNode(RI.GetRowIdx().Val);
19  MapV.Add(RI.GetRowIdx());
20  }
21  //Add Edges
22  for (TRowIterator OI = P->BegRI(); OI < P->EndRI(); OI++) {
23  int OIdx = OI.GetRowIdx().Val;
24  int ODest = P->GetIntValAtRowIdx(DIdx,OIdx).Val;
25  int OStart = P->GetIntValAtRowIdx(StIdx,OIdx).Val;
26  int ODur = P->GetIntValAtRowIdx(DuIdx,OIdx).Val;
27  // Inline binary Search
28  int val = ODest;
29  int lo = 0;
30  int hi = Source.Len() - 1;
31  int index = -1;
32  while (hi >= lo) {
33  int mid = lo + (hi - lo)/2;
34  if (Source.GetVal(mid) > val) { hi = mid - 1;}
35  else if (Source.GetVal(mid) < val) { lo = mid + 1;}
36  else { index = mid; hi = mid - 1;}
37  }
38  // End of binary Search
39  if (index < 0) {
40  continue;
41  }
42  int BIdx = index;
43  for(int i = BIdx; i < Source.Len(); i++) {
44  int InIdx = MapV.GetVal(i).Val;
45  if (InIdx == OIdx) {continue;}
46  int InSource = P->GetIntValAtRowIdx(SIdx,InIdx).Val;
47  int InStart = P->GetIntValAtRowIdx(StIdx,InIdx).Val;
48  if (InSource != ODest) { break;}
49  if (InStart >= (ODur + OStart) && InStart - (ODur + OStart) <= W.Val) {
50  if (!Graph->IsEdge(OIdx,InIdx)) {
51  Graph->AddEdge(OIdx,InIdx);
52  }
53  }
54  }
55  }
56  return Graph;
57 }
int Val
Definition: dt.h:1136
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
Iterator class for TTable rows.
Definition: table.h:330
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
Definition: dt.h:1134
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

59  {
60  // Attribute to Int mapping
61  TInt SIdx = P->GetColIdx(C1); //Source
62  TInt DIdx = P->GetColIdx(C2); //Dest
63  TInt StIdx = P->GetColIdx(C3); //Start
64  TInt DuIdx = P->GetColIdx(C4); //Duration
65  TIntV MapV;
66  TStrV SortBy;
67  SortBy.Add(C3);
68  P->Order(SortBy);
69  TIntV Start;
70  P->ReadIntCol(C3,Start);
71  PNGraph Graph = TNGraph::New();
72  //Add Nodes
73  for (TRowIterator RI = P->BegRI(); RI < P-> EndRI(); RI++) {
74  Graph->AddNode(RI.GetRowIdx().Val);
75  MapV.Add(RI.GetRowIdx());
76  }
77  //Add Edges
78  for (TRowIterator OI = P->BegRI(); OI < P->EndRI(); OI++) {
79  int OIdx = OI.GetRowIdx().Val;
80  int ODest = P->GetIntValAtRowIdx(DIdx,OIdx).Val;
81  int OStart = P->GetIntValAtRowIdx(StIdx,OIdx).Val;
82  int ODur = P->GetIntValAtRowIdx(DuIdx,OIdx).Val;
83  // Inline binary Search
84  int val = OStart + ODur;
85  int lo = 0;
86  int hi = Start.Len() - 1;
87  int index = -1;
88  if (val >= Start.GetVal(hi)) { val = Start.GetVal(hi);}
89  while (hi >= lo) {
90  int mid = lo + (hi - lo)/2;
91  if (Start.GetVal(mid) > val) {
92  if ((mid-1) >= lo && Start.GetVal(mid - 1) < val) {
93  index = mid - 1;break;
94  }
95  hi = mid - 1;
96  }
97  else if (Start.GetVal(mid) < val) {
98  if (mid + 1 <= hi && Start.GetVal(mid + 1) > val) {
99  index = mid;break;
100  }
101  lo = mid + 1;
102  }
103  else { index = mid; hi = mid - 1;}
104  }
105  // End of binary Search
106  if (index < 0) {
107  continue;
108  }
109  int BIdx = index;
110  for(int i = BIdx; i < Start.Len(); i++) {
111  int InIdx = MapV.GetVal(i).Val;
112  if (InIdx == OIdx) {continue;}
113  int InSource = P->GetIntValAtRowIdx(SIdx,InIdx).Val;
114  int InStart = P->GetIntValAtRowIdx(StIdx,InIdx).Val;
115  if (InStart - (ODur + OStart) > W.Val) { break;}
116  if (InSource == ODest && InStart >= (ODur + OStart)) {
117  if (!Graph->IsEdge(OIdx,InIdx)) {
118  Graph->AddEdge(OIdx,InIdx);
119  }
120  }
121  }
122  }
123  return Graph;
124 }
int Val
Definition: dt.h:1136
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
Iterator class for TTable rows.
Definition: table.h:330
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
Definition: dt.h:1134
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void TSnap::CmtyEvolutionFileBatch ( TStr  InFNm,
TIntIntHH sizesCont,
TIntIntHH cCont,
TIntIntVH edges,
double  alpha,
double  beta,
int  CmtyAlg 
)

Definition at line 488 of file cmty.cpp.

488  {
489 
490 
491  // reading folder with networks and calculating core/periphery
492  int br = 0;
493  TIntIntH prev;
494  TIntH prev_sizes;
495 
496  TSsParser Ss(InFNm, ssfWhiteSep, true, false, true);
497  Ss.Next();
498  //int internal_year_counter = 0;
499  // variable for delimiter between networks
500  TStr Marker;
501  // defining variables for node ids and starting year
502  int SrcNId, DstNId; // , t = 1970;
503 
504  // temporal container for edges
505  TIntIntVH edges_;
506 
507  while (!Ss.Eof()) {
508 
509  //printf("%i\n", t);
510  Marker = Ss.GetLnStr();
511  // get the year from the network seperator
512  //t = Marker.GetSubStr(1, 4).GetInt();
513 
514  if (Marker.GetCh(0) == '#'){
515 
516  Ss.Next();
517  PUNGraph Graph = PUNGraph::TObj::New();
518  do{
519  if (!Ss.GetInt(0, SrcNId) || !Ss.GetInt(1, DstNId)) {
520  if (!Ss.Eof()){
521  Ss.Next();
522  if (!Ss.Eof())
523  Marker = Ss.GetLnStr();
524  }
525  continue;
526  }
527  if (!Graph->IsNode(SrcNId)) { Graph->AddNode(SrcNId); }
528  if (!Graph->IsNode(DstNId)) { Graph->AddNode(DstNId); }
529  Graph->AddEdge(SrcNId, DstNId);
530  Ss.Next();
531  if (!Ss.Eof())
532  Marker = Ss.GetLnStr();
533  } while (Marker.GetCh(0) != '#' && !Ss.Eof());
534 
535 
536  if (Graph->GetNodes()>0) {
537  // WORK
538 
539  TSnap::DelSelfEdges(Graph);
540  TCnComV CmtyV;
541  //double Q = 0.0;
542  TStr CmtyAlgStr;
543  if (CmtyAlg == 1) {
544  CmtyAlgStr = "Girvan-Newman";
545  //Q = TSnap::CommunityGirvanNewman(Graph, CmtyV);
546  }
547  else if (CmtyAlg == 2) {
548  CmtyAlgStr = "Clauset-Newman-Moore";
549  //Q = TSnap::CommunityCNM(Graph, CmtyV);
550  }
551  else if (CmtyAlg == 3) {
552  CmtyAlgStr = "Infomap";
553  //Q = TSnap::Infomap(Graph, CmtyV);
554  }
555  else { Fail; }
556 
557  TIntIntHH distCont;
558 
559  if (br == 0) {
560  prev.Clr();
561  //int size = 0;
562  for (int c = 0; c < CmtyV.Len(); c++) {
563  for (int i = 0; i < CmtyV[c].Len(); i++){
564  prev.AddDat(CmtyV[c][i].Val, c);
565  }
566  //int s = CmtyV[c].Len();
567  prev_sizes.AddDat(c, CmtyV[c].Len());
568  }
569  }
570  else {
571 
572  // containers for statistics
573 
574  //TIntFltHH stat1;
575  //TIntIntHH stat2;
576  TIntH dist;
577  TIntH map;
578 
579  int first_new_c_id = -1;
580 
581  // getting first free id for a new community
582  for (THashKeyDatI<TInt, TInt> it = prev_sizes.BegI(); !it.IsEnd(); it++)
583  if (it.GetKey() > first_new_c_id)
584  first_new_c_id = it.GetKey();
585  if (CmtyV.Len() - 1>first_new_c_id)
586  first_new_c_id = CmtyV.Len() - 1;
587  first_new_c_id++;
588 
589  for (int c = 0; c < CmtyV.Len(); c++) {
590 
591  TIntV stat;
592  TIntFltH statH1;
593  TIntFltH statH2;
594 
595  // initialize distributions to 0
596  for (THashKeyDatI<TInt, TInt> it = prev_sizes.BegI(); !it.IsEnd(); it++)
597  dist.AddDat(it.GetKey(), 0);
598  //for new nodes
599  dist.AddDat(-1, 0);
600 
601  for (int i = 0; i < CmtyV[c].Len(); i++) {
602  int id = CmtyV[c][i].Val;
603  int prev_comm = -1;
604  if (prev.IsKey(id))
605  prev_comm = prev.GetDat(CmtyV[c][i].Val);
606  stat.Add(prev_comm);
607  int pre_val = dist.GetDat(prev_comm);
608  dist.AddDat(prev_comm, pre_val + 1);
609  }
610 
611  double sumstat2 = 0;
612  for (THashKeyDatI<TInt, TInt> it = dist.BegI(); !it.IsEnd(); it++) {
613 
614  int k = it.GetKey();
615  int d = it.GetDat();
616  if (d > 0){
617  if (prev_sizes.IsKey(it.GetKey())){
618 
619  double stat1_ = (double)d / (double)prev_sizes.GetDat(k);
620  statH1.AddDat(k, stat1_);
621  }
622  double stat2_ = (double)d / (double)CmtyV[c].Len();
623  statH2.AddDat(k, stat2_);
624  sumstat2 += stat2_;
625 
626  TIntV edge;
627  edge.Add(k);
628  edge.Add(c);
629  edge.Add(d);
630  edge.Add(br - 1);
631  edge.Add(br);
632  edges_.AddDat(edges_.Len() + 1, edge);
633  }
634 
635  // adding edges between two communities in two neighbouring time points;
636 
637 
638  if (sumstat2 > 0.98) break;
639  }
640 
641  int n_of_c_greater_than_half = 0;
642  int id_of_c_greater_than_half = -1;
643  TIntV ids_of_c_greater_than_half;
644 
645  for (THashKeyDatI<TInt, TFlt> it = statH1.BegI(); !it.IsEnd(); it++){
646  if (it.GetDat()>alpha){
647  id_of_c_greater_than_half = it.GetKey();
648  ids_of_c_greater_than_half.Add(it.GetKey());
649  n_of_c_greater_than_half++;
650  }
651  }
652 
653  // 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
654  if (n_of_c_greater_than_half == 1){
655  map.AddDat(c, id_of_c_greater_than_half);
656  }
657  else{
658  int h2part_id = -2;
659  for (int i = 0; i<ids_of_c_greater_than_half.Len(); i++){
660  double H2 = statH2.GetDat(ids_of_c_greater_than_half[i]);
661  if (H2>beta){
662  h2part_id = ids_of_c_greater_than_half[i];
663  }
664  }
665  if (h2part_id != -2)
666  map.AddDat(c, h2part_id);
667  else{
668  map.AddDat(c, first_new_c_id);
669  first_new_c_id++;
670  }
671  }
672 
673  distCont.AddDat(c, dist);
674 
675  //stat1.AddDat(c,statH1);
676  //stat2.AddDat(c,statH2);
677 
678  }
679 
680 
681  prev.Clr();
682  prev_sizes.Clr();
683  for (int c = 0; c < CmtyV.Len(); c++){
684  for (int i = 0; i < CmtyV[c].Len(); i++){
685  prev.AddDat(CmtyV[c][i].Val, map.GetDat(c));
686  }
687  //int s = CmtyV[c].Len();
688  prev_sizes.AddDat(map.GetDat(c), CmtyV[c].Len());
689  }
690 
691  // filing the edges container - the key thing is the map(c)
692  for (THashKeyDatI<TInt, TIntV> it = edges_.BegI(); !it.IsEnd(); it++){
693  TIntV edgesV;
694  int a = it.GetDat()[0];
695  int b = it.GetDat()[1];
696  int v = it.GetDat()[2];
697  int d = it.GetDat()[3];
698  int e = it.GetDat()[4];
699  edgesV.Add(map.GetDat(b));
700  edgesV.Add(a);
701  edgesV.Add(v);
702  edgesV.Add(d);
703  edgesV.Add(e);
704  if (a != -1)
705  edges.AddDat(edges.Len(), edgesV);
706  }
707  edges_.Clr();
708 
709 
710  }
711 
712  sizesCont.AddDat(br, prev_sizes);
713  cCont.AddDat(br, prev);
714  br++;
715  // WORK - END
716  }
717  }
718  else Ss.Next();
719  }
720 
721 }
#define Fail
Definition: bd.h:238
TIter BegI() const
Definition: hash.h:213
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Definition: ss.h:72
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
bool IsEnd() const
Tests whether the iterator is pointing to the past-end element.
Definition: hash.h:78
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
Whitespace (space or tab) separated.
Definition: ss.h:11
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
char GetCh(const int &ChN) const
Definition: dt.h:483
Definition: dt.h:412
Definition: hash.h:97
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
Definition: bd.h:196
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void DelSelfEdges(const PGraph &Graph)
Removes all the self-edges from the graph.
Definition: alg.h:419
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
void TSnap::CmtyEvolutionFileBatchV ( TStr  InFNm,
TIntIntVH sizesContV,
TIntIntVH cContV,
TIntIntVH edges,
double  alpha,
double  beta,
int  CmtyAlg 
)

Definition at line 439 of file cmty.cpp.

439  {
440  TIntIntHH sizesCont;
441  TIntIntHH cCont;
442  CmtyEvolutionFileBatch(InFNm, sizesCont, cCont, edges, alpha, beta, CmtyAlg);
443 
444  TIntV uniqueId;
445  for (int i = 0; i < cCont.Len(); i++){
446  for (THashKeyDatI<TInt, TInt> it = cCont[i].BegI(); !it.IsEnd(); it++){
447  if (!uniqueId.IsIn(it.GetKey()))
448  uniqueId.Add(it.GetKey());
449  }
450  }
451 
452  for (int j = 0; j<uniqueId.Len(); j++)
453  {
454  TIntV cV;
455  for (int i = 0; i<cCont.Len(); i++)
456  {
457  if (cCont[i].IsKey(uniqueId[j]))
458  cV.Add(cCont[i].GetDat(uniqueId[j]));
459  else
460  cV.Add(-1);
461  }
462  cContV.AddDat(uniqueId[j], cV);
463  }
464 
465  TIntV uniqueC;
466  for (int i = 0; i < sizesCont.Len(); i++){
467  for (THashKeyDatI<TInt, TInt> it = sizesCont[i].BegI(); !it.IsEnd(); it++){
468  if (!uniqueC.IsIn(it.GetKey()))
469  uniqueC.Add(it.GetKey());
470  }
471  }
472 
473  for (int j = 0; j<uniqueC.Len(); j++)
474  {
475  TIntV cV;
476  for (int i = 0; i<sizesCont.Len(); i++)
477  {
478  if (sizesCont[i].IsKey(uniqueC[j]))
479  cV.Add(sizesCont[i].GetDat(uniqueC[j]));
480  else
481  cV.Add(0);
482  }
483  sizesContV.AddDat(uniqueC[j], cV);
484  }
485 
486 }
bool IsIn(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:828
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
void CmtyEvolutionFileBatch(TStr InFNm, TIntIntHH &sizesCont, TIntIntHH &cCont, TIntIntVH &edges, double alpha, double beta, int CmtyAlg)
Definition: cmty.cpp:488
Definition: hash.h:97
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void TSnap::CmtyEvolutionJson ( TStr Json,
TIntIntVH sizesContV,
TIntIntVH cContV,
TIntIntVH edges 
)

Definition at line 723 of file cmty.cpp.

723  {
725  // This function creates a JSON string with communities and edges for community evolution visualization using D3.js
727 
728  // writing json label for edges
729  Json.InsStr(Json.Len(), "{\n\"edges\":[\n");
730 
731  TInt br = 0;
732  // iterating hash of vector of edges and writing into string
733  for (THashKeyDatI<TInt, TIntV> it = edges.BegI(); !it.IsEnd(); it++)
734  {
735  // first node
736  TInt n1 = it.GetDat()[1];
737  // second node
738  TInt n2 = it.GetDat()[0];
739  // edge weight
740  TInt w = it.GetDat()[2];
741  // start time point
742  TInt t0 = it.GetDat()[3];
743  // end time point
744  TInt t1 = it.GetDat()[4];
745 
746  if (br>0)
747  Json.InsStr(Json.Len(), ",");
748 
749  // writing to string
750  Json.InsStr(Json.Len(), "{\"n1\":"); Json.InsStr(Json.Len(), n1.GetStr());
751  Json.InsStr(Json.Len(), ", \"n2\":"); Json.InsStr(Json.Len(), n2.GetStr());
752  Json.InsStr(Json.Len(), ", \"w\":"); Json.InsStr(Json.Len(), w.GetStr());
753  Json.InsStr(Json.Len(), ", \"t0\":"); Json.InsStr(Json.Len(), t0.GetStr());
754  Json.InsStr(Json.Len(), ", \"t1\":"); Json.InsStr(Json.Len(), t1.GetStr());
755  Json.InsStr(Json.Len(), " }\n");
756  br++;
757  }
758 
759  // json label for communities
760  Json.InsStr(Json.Len(), "],\n\"communities\":[\n");
761 
762  br = 0;
763  // printing communities into json file
764  for (int i = 0; i < sizesContV[0].Len(); i++)
765  {
766  for (THashKeyDatI<TInt, TIntV> it = sizesContV.BegI(); !it.IsEnd(); it++)
767  {
768  // id of community
769  TInt id = it.GetKey();
770  // community size
771  TInt size = it.GetDat()[i];
772  // time
773  TInt j = i;
774 
775  // if the community has size greater than 0, output it to json string
776  if (size > 0) {
777  if (br>0)
778  Json.InsStr(Json.Len(), ",");
779 
780  TInt size = it.GetDat()[i];
781  Json.InsStr(Json.Len(), "{\"id\":"); Json.InsStr(Json.Len(), id.GetStr());
782  Json.InsStr(Json.Len(), ", \"size\":"); Json.InsStr(Json.Len(), size.GetStr());
783  Json.InsStr(Json.Len(), ", \"t\":"); Json.InsStr(Json.Len(), j.GetStr());
784  Json.InsStr(Json.Len(), " }\n");
785 
786  br++;
787  }
788  }
789  }
790 
791  // printing communities into json file - alternative ordering
792  /*
793  for (THashKeyDatI<TInt, TIntV> it = sizesContV.BegI(); !it.IsEnd(); it++)
794  {
795  TInt id = it.GetKey();
796  int len = it.GetDat().Len();
797  for (int i=0; i < it.GetDat().Len(); i++)
798  {
799  TInt size = it.GetDat()[i];
800  TInt j = i;
801  if (size > 0) {
802 
803  if(br>0)
804  Json.InsStr(Json.Len(),",");
805 
806  TInt size = it.GetDat()[i];
807 
808  Json.InsStr(Json.Len(),"{\"id\":"); Json.InsStr(Json.Len(),id.GetStr());
809  Json.InsStr(Json.Len(),", \"size\":"); Json.InsStr(Json.Len(),size.GetStr());
810  Json.InsStr(Json.Len(),", \"t\":"); Json.InsStr(Json.Len(),j.GetStr());
811  Json.InsStr(Json.Len()," }\n");
812 
813  br++;
814 
815  }
816 
817  }
818  }
819  */
820 
821  Json.InsStr(Json.Len(), "]\n}");
822 
823 }
TStr GetStr() const
Definition: dt.h:1197
int Len() const
Definition: dt.h:487
TIter BegI() const
Definition: hash.h:213
bool IsEnd() const
Tests whether the iterator is pointing to the past-end element.
Definition: hash.h:78
Definition: dt.h:1134
int Len() const
Definition: hash.h:228
void InsStr(const int &BChN, const TStr &Str)
Definition: dt.cpp:825
TStr TSnap::CmtyTest ( TStr  InFNm,
int  CmtyAlg 
)

Definition at line 825 of file cmty.cpp.

825  {
826 
827  TIntIntVH sizesContV;
828  TIntIntVH cContV;
829  TIntIntVH edges;
830  double alpha = 0.5;
831  double beta = 0.75;
832  CmtyEvolutionFileBatchV(InFNm, sizesContV, cContV, edges, alpha, beta, CmtyAlg);
833  TStr out;
834  //int a = sizesContV.Len();
835  //int b = cContV.Len();
836  //int c = edges.Len();
837  CmtyEvolutionJson(out, sizesContV, cContV, edges);
838 
839  return out;
840 }
void CmtyEvolutionFileBatchV(TStr InFNm, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges, double alpha, double beta, int CmtyAlg)
Definition: cmty.cpp:439
void CmtyEvolutionJson(TStr &Json, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges)
Definition: cmty.cpp:723
Definition: dt.h:412
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.

105  {
106  int Cnt = 0;
107  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
108  if (NI.GetDeg() == NodeDeg) Cnt++;
109  }
110  return Cnt;
111 }
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.

123  {
124  if (! Graph->IsNode(NId)) { return 0; }
125  const bool IsDir = Graph->HasFlag(gfDirected);
126  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
127  if (! IsDir) {
128  int EdgesToSet = 0;
129  for (int e = 0; e < NI.GetOutDeg(); e++) {
130  if (NodeSet.IsKey(NI.GetOutNId(e))) { EdgesToSet++; } }
131  return EdgesToSet;
132  } else {
133  TIntSet Set(NI.GetDeg());
134  for (int e = 0; e < NI.GetOutDeg(); e++) {
135  if (NodeSet.IsKey(NI.GetOutNId(e))) { Set.AddKey(NI.GetOutNId(e)); } }
136  for (int e = 0; e < NI.GetInDeg(); e++) {
137  if (NodeSet.IsKey(NI.GetInNId(e))) { Set.AddKey(NI.GetInNId(e)); } }
138  return Set.Len();
139  }
140 }
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
int AddKey(const TKey &Key)
Definition: shash.h:1254
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
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.

87  {
88  int Cnt = 0;
89  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
90  if (NI.GetInDeg() == NodeInDeg) Cnt++;
91  }
92  return Cnt;
93 }
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.

114  {
115  int Cnt = 0;
116  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
117  if (NI.GetDeg() > 0) Cnt++;
118  }
119  return Cnt;
120 }
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.

96  {
97  int Cnt = 0;
98  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
99  if (NI.GetOutDeg() == NodeOutDeg) Cnt++;
100  }
101  return Cnt;
102 }
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.

334  {
335  int Cnt = 0;
336  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
337  for (int e = 0; e < NI.GetOutDeg(); e++) {
338  if (NI.GetId() == NI.GetOutNId(e)) { Cnt++; }
339  }
340  }
341  return Cnt;
342 }
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.

316  {
317  if (! Graph->HasFlag(gfDirected)) { // graph is undirected
318  return CntUniqUndirEdges(Graph); // then every edge is bi-directional
319  }
320  TIntSet NbrSet;
321  int Cnt = 0;
322  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
323  const int SrcId = NI.GetId();
324  for (int e = 0; e < NI.GetOutDeg(); e++) {
325  const int DstId = NI.GetOutNId(e);
326  if (DstId <= SrcId) { continue; } // count each un-dir edge only once
327  if (Graph->IsEdge(DstId, SrcId)) { Cnt++; }
328  }
329  }
330  return Cnt;
331 }
int CntUniqUndirEdges(const PGraph &Graph)
Counts unique undirected edges in the graph Graph. Nodes (u,v) (where u!=v) are connected via an undi...
Definition: alg.h:279
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
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.

301  {
302  TIntSet NbrSet;
303  int Cnt = 0;
304  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
305  NbrSet.Clr(false);
306  for (int e = 0; e < NI.GetOutDeg(); e++) { // unique out-neighbors of a node
307  if (NI.GetOutNId(e) != NI.GetId()) { // skip self-edges
308  NbrSet.AddKey(NI.GetOutNId(e)); }
309  }
310  Cnt += NbrSet.Len();
311  }
312  return Cnt;
313 }
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
int AddKey(const TKey &Key)
Definition: shash.h:1254
int Len() const
Definition: shash.h:1121
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.

279  {
280  TIntSet NbrSet;
281  TIntSet SelfNbrSet;
282  int Cnt = 0;
283  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
284  NbrSet.Clr(false);
285  for (int e = 0; e < NI.GetDeg(); e++) { // unique neighbors of a node
286  const int NbrId = NI.GetNbrNId(e);
287  if (NbrId == NI.GetId()) { // remember self-edges
288  SelfNbrSet.AddKey(NbrId);
289  } else {
290  NbrSet.AddKey(NbrId);
291  }
292  }
293  Cnt += NbrSet.Len();
294  }
295  // OP RS 2014/06/11 self-edges are currently not used
296  //return Cnt / 2 + SelfNbrSet.Len();
297  return Cnt / 2;
298 }
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
int AddKey(const TKey &Key)
Definition: shash.h:1254
int Len() const
Definition: shash.h:1121
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 1447 of file cmty.cpp.

1447  {
1448  return TSnapDetail::TCNMQMatrix::CmtyCMN(Graph, CmtyV);
1449 }
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.

312  {
313  TIntH OutDegH;
314  const int NEdges = Graph->GetEdges();
315  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
316  OutDegH.AddDat(NI.GetId(), NI.GetOutDeg());
317  }
318  double BestQ = -1; // modularity
319  TCnComV CurCmtyV;
320  CmtyV.Clr();
321  TIntV Cmty1, Cmty2;
322  while (true) {
323  TSnapDetail::CmtyGirvanNewmanStep(Graph, Cmty1, Cmty2);
324  const double Q = TSnapDetail::_GirvanNewmanGetModularity(Graph, OutDegH, NEdges, CurCmtyV);
325  //printf("current modularity: %f\n", Q);
326  if (Q > BestQ) {
327  BestQ = Q;
328  CmtyV.Swap(CurCmtyV);
329  }
330  if (Cmty1.Len() == 0 || Cmty2.Len() == 0) { break; }
331  }
332  return BestQ;
333 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
double _GirvanNewmanGetModularity(const PUNGraph &G, const TIntH &OutDegH, const int &OrigEdges, TCnComV &CnComV)
Definition: cmty.cpp:37
void CmtyGirvanNewmanStep(PUNGraph &Graph, TIntV &Cmty1, TIntV &Cmty2)
A single step of Girvan-Newman clustering procedure.
Definition: cmty.cpp:15
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 403 of file subgraph.h.

403  {
404  CAssert(HasGraphFlag(typename PInGraph::TObj, gfMultiGraph)); // needs to have explicit edges
405  POutGraph NewGraphPt = POutGraph::TObj::New();
406  typename POutGraph::TObj& NewGraph = *NewGraphPt;
407  NewGraph.Reserve(-1, EIdV.Len());
408  if (! RenumberNodes) {
409  for (int edge = 0; edge < EIdV.Len(); edge++) {
410  const int EId = EIdV[edge];
411  IAssert(InGraph->IsEdge(EId));
412  const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
413  const int SrcNId = EI.GetSrcNId();
414  const int DstNId = EI.GetDstNId();
415  if (! NewGraph.IsNode(SrcNId)) {
416  NewGraph.AddNode(SrcNId); }
417  if (! NewGraph.IsNode(DstNId)) {
418  NewGraph.AddNode(DstNId); }
419  NewGraph.AddEdge(SrcNId, DstNId);
420  }
421  } else {
422  // renumber nodes so that node ids are 0...N-1
423  TIntSet NIdSet(InGraph->GetNodes());
424  for (int edge = 0; edge < EIdV.Len(); edge++) {
425  const int EId = EIdV[edge];
426  IAssert(InGraph->IsEdge(EId));
427  const typename PInGraph::TObj::TEdgeI EI = InGraph->GetEI(EId);
428  const int SrcNId = NIdSet.AddKey(EI.GetSrcNId()); // map node ids
429  const int DstNId = NIdSet.AddKey(EI.GetDstNId());
430  if (! NewGraph.IsNode(SrcNId)) {
431  NewGraph.AddNode(SrcNId); }
432  if (! NewGraph.IsNode(DstNId)) {
433  NewGraph.AddNode(DstNId); }
434  NewGraph.AddEdge(SrcNId, DstNId);
435  }
436  }
437  return NewGraphPt;
438 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
#define CAssert(Cond)
Definition: bd.h:302
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 288 of file subgraph.h.

288  {
289  POutGraph OutGraphPt = POutGraph::TObj::New();
290  typename POutGraph::TObj& OutGraph = *OutGraphPt;
291  OutGraph.Reserve(InGraph->GetNodes(), InGraph->GetEdges());
292  if (! RenumberNodes) {
293  for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
294  OutGraph.AddNode(NI.GetId());
295  }
296  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
297  OutGraph.AddEdge(EI.GetSrcNId(), EI.GetDstNId());
298  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) { // add edge in the other direction
299  OutGraph.AddEdge(EI.GetDstNId(), EI.GetSrcNId()); }
300  }
301  } else { // renumber nodes so that node ids are 0...N-1
302  TIntSet NIdSet(InGraph->GetNodes());
303  for (typename PInGraph::TObj::TNodeI NI = InGraph->BegNI(); NI < InGraph->EndNI(); NI++) {
304  const int nid = NIdSet.AddKey(NI.GetId());
305  OutGraph.AddNode(nid);
306  }
307  for (typename PInGraph::TObj::TEdgeI EI = InGraph->BegEI(); EI < InGraph->EndEI(); EI++) {
308  const int SrcNId = NIdSet.GetKeyId(EI.GetSrcNId());
309  const int DstNId = NIdSet.GetKeyId(EI.GetDstNId());
310  OutGraph.AddEdge(SrcNId, DstNId);
311  if (! HasGraphFlag(typename PInGraph::TObj, gfDirected) && HasGraphFlag(typename POutGraph::TObj, gfDirected)) {
312  OutGraph.AddEdge(DstNId, SrcNId); }
313  }
314  }
315  //OutGraph.Defrag();
316  return OutGraphPt;
317 }
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
int AddKey(const TKey &Key)
Definition: shash.h:1254
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
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 398 of file subgraph.h.

398  {
399  return TSnapDetail::TConvertSubGraph<POutGraph, PInGraph, HasGraphFlag(typename PInGraph::TObj, gfMultiGraph)>::Do(InGraph, NIdV, RenumberNodes);
400 }
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.

445  {
446  TIntV DelNIdV;
447  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
448  if (NI.GetOutDeg() == OutDegK || NI.GetInDeg() == InDegK) {
449  DelNIdV.Add(NI.GetId());
450  }
451  }
452  for (int i = 0; i < DelNIdV.Len(); i++) {
453  Graph->DelNode(DelNIdV[i]);
454  }
455 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

425  {
426  for (int n = 0; n < NIdV.Len(); n++) {
427  Graph->DelNode(NIdV[n]);
428  }
429 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
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.

419  {
420  TSnapDetail::TDelSelfEdges<PGraph, HasGraphFlag(typename PGraph::TObj, gfMultiGraph)>
421  ::Do(Graph);
422 }
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.

432  {
433  TIntV DelNIdV;
434  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
435  if (NI.GetDeg() == 0) {
436  DelNIdV.Add(NI.GetId());
437  }
438  }
439  for (int i = 0; i < DelNIdV.Len(); i++) {
440  Graph->DelNode(DelNIdV[i]);
441  }
442 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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
PltFNmOutput filename (extension .ps, .png, .gif) determines the output format.
NIdColorHMaps node ids to node colors (see GraphViz documentation for more details).

Definition at line 34 of file gviz.h.

34  {
35  const TStr Ext = PltFNm.GetFExt();
36  const TStr GraphFNm = PltFNm.GetSubStr(0, PltFNm.Len()-Ext.Len()) + "dot";
37  SaveGViz(Graph, GraphFNm, Desc, NodeLabels, NIdColorH);
38  TSnap::TSnapDetail::GVizDoLayout(GraphFNm, PltFNm, Layout);
39 }
int Len() const
Definition: dt.h:487
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.
Definition: gio.h:386
TStr GetSubStr(const int &BChN, const int &EChN) const
Definition: dt.cpp:811
TStr GetFExt() const
Definition: dt.cpp:1421
void GVizDoLayout(const TStr &GraphInFNm, TStr OutFNm, const TGVizLayout &Layout)
Runs GraphViz layout engine over a graph saved in the file GraphInFNm with output saved to OutFNm...
Definition: gviz.cpp:5
Definition: dt.h:412
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
PltFNmOutput filename (extension .ps, .png, .gif) determines the output format.
NIdColorHMaps node ids to node colors (see GraphViz documentation for more details).

Definition at line 42 of file gviz.h.

42  {
43  const TStr Ext = PltFNm.GetFExt();
44  const TStr GraphFNm = PltFNm.GetSubStr(0, PltFNm.Len()-Ext.Len()) + "dot";
45  SaveGViz(Graph, GraphFNm, Desc, NodeLabelH);
46  TSnap::TSnapDetail::GVizDoLayout(GraphFNm, PltFNm, Layout);
47 }
int Len() const
Definition: dt.h:487
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.
Definition: gio.h:386
TStr GetSubStr(const int &BChN, const int &EChN) const
Definition: dt.cpp:811
TStr GetFExt() const
Definition: dt.cpp:1421
void GVizDoLayout(const TStr &GraphInFNm, TStr OutFNm, const TGVizLayout &Layout)
Runs GraphViz layout engine over a graph saved in the file GraphInFNm with output saved to OutFNm...
Definition: gviz.cpp:5
Definition: dt.h:412
TIntFltH TSnap::EventImportance ( const PNGraph Graph,
const int  k 
)

Event importance.

Definition at line 527 of file centr.cpp.

527  {
528  TIntFltH NodeList; // values for nodese
529 
530  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
531  NodeList.AddDat(NI.GetId(),NI.GetOutDeg());
532  }
533 
534 
535  for (THashKeyDatI<TInt,TFlt> NI = NodeList.BegI(); NI < NodeList.EndI(); NI++){
536  int outdeg = Graph->GetNI(NI.GetKey()).GetOutDeg();
537  int indeg = Graph->GetNI(NI.GetKey()).GetInDeg();
538 
539  if (outdeg>1 && indeg>0){
540  double val = (1-(1/(double)outdeg))/(double)indeg;
541  for(int i=0; i<(outdeg+indeg);i++){
542  int NId = Graph->GetNI(NI.GetKey()).GetNbrNId(i);
543  if (Graph->GetNI(NI.GetKey()).IsInNId(NId) == true){
544  NodeList.AddDat(NId,NodeList.GetDat(NId)+val);
545  }
546 
547  }
548  }
549 
550  }
551 
552  return NodeList;
553 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
TIter BegI() const
Definition: hash.h:213
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TIter EndI() const
Definition: hash.h:218
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TIntFltH TSnap::EventImportance1 ( const PNGraph Graph,
const int  k 
)

Definition at line 556 of file centr.cpp.

556  {
557  TIntFltH NodeList; // values for nodese
558 
559  for (TNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){
560  NodeList.AddDat(NI.GetId(),NI.GetOutDeg());
561  }
562 
563 
564  for (THashKeyDatI<TInt,TFlt> NI = NodeList.BegI(); NI < NodeList.EndI(); NI++){
565  int outdeg = Graph->GetNI(NI.GetKey()).GetOutDeg();
566  int indeg = Graph->GetNI(NI.GetKey()).GetInDeg();
567 
568  if (outdeg>1 && indeg>0){
569  double val = (1-(1/(double)outdeg))/(double)indeg;
570  for(int i=0; i<(outdeg+indeg);i++){
571  int NId = Graph->GetNI(NI.GetKey()).GetNbrNId(i);
572  if (Graph->GetNI(NI.GetKey()).IsInNId(NId) == true){
573  NodeList.AddDat(NId,NodeList.GetDat(NId)+val);
574  }
575 
576  }
577  }
578 
579  }
580 
581  return NodeList;
582 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
TIter BegI() const
Definition: hash.h:213
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TIter EndI() const
Definition: hash.h:218
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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.

12  {
13 
14  TIntIntH nodes;
15  double Z=0;
16 
17  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){ // Calculate and store the degrees of each node.
18  int deg = NI.GetDeg();
19  int id = NI.GetId();
20  Z += deg;
21  nodes.AddDat(id,deg);
22  }
23 
24  Z = Z/2;
25 
26  nodes.SortByDat(false); // Then sort the nodes in descending order of degree, to get a list of nodes {v1, v2, . . . , vn}.
27 
28  double Zbest = 99999900000000000;
29  int kbest = 0;
30 
31  int br=0;
32  for (int k=0; k<nodes.Len(); k++){
33  br++;
34  Z = Z + br - 1 - nodes[k];
35  if (Z < Zbest){ // or <=
36  Zbest = Z;
37  kbest = br;
38  }
39  }
40 
41  int cp = 0;
42  br = 0;
43  for (THashKeyDatI<TInt, TInt> it = nodes.BegI(); !it.IsEnd(); it++) {
44  if (br < kbest)
45  cp = 1;
46  else
47  cp = 0;
48  out.AddDat(it.GetKey(), cp);
49  br++;
50  }
51 
52  return kbest;
53  }
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
bool IsEnd() const
Tests whether the iterator is pointing to the past-end element.
Definition: hash.h:78
Definition: hash.h:97
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void SortByDat(const bool &Asc=true)
Definition: hash.h:292
int TSnap::FastCorePeripheryGC ( PUNGraph Graph,
TIntIntH out 
)

Definition at line 56 of file coreper.cpp.

56  {
57  TIntH GroupNodes; // buildup cpntainer of group nodes
58  int *NNodes = new int[Graph->GetNodes()]; // container of neighbouring nodes
59  int NNodes_br = 0;
60 
61  TIntIntH nodes;
62  TIntIntH nodesIds;
63  double Z=0;
64 
65  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++){ // Calculate and store the degrees of each node.
66  int deg = NI.GetDeg();
67  int id = NI.GetId();
68  Z += deg;
69  nodes.AddDat(id,deg);
70 
71  }
72 
73  Z = Z/2;
74 
75  nodes.SortByDat(false); // Then sort the nodes in descending order of degree, to get a list of nodes {v1, v2, . . . , vn}.
76 
77  int br1=0;
78  for (THashKeyDatI<TInt,TInt> NI = nodes.BegI(); NI < nodes.EndI(); NI++){
79  nodesIds.AddDat(NI.GetKey(),NI.GetKey());
80  br1++;
81  }
82 
83  double Zbest = 99999900000000000;
84  //int kbest;
85  //int olddeg;
86  int br=0;
87  for (int k=0; k<nodes.Len(); k++){
88  if (k<nodes.Len()-1){
89  if (nodes[k]==nodes[k+1]){ // go into same deg mode
90  int kmin=-2; int knew=-1;
91  while (kmin < 999999 && kmin !=-1 ){
92  int kind=-1;
93  knew=k;
94  kmin=999999;
95  while(nodes[k]==nodes[knew] && knew < nodes.Len()-1){
96  int inter = Intersect(Graph->GetNI(nodesIds[knew]),NNodes,NNodes_br);
97  int deg = nodes[knew];
98  //if (((((nodes.Len()-NNodes_br)*(nodes.Len()-NNodes_br)))-(nodes.Len()-NNodes_br))/2<(((br*br)-br)/2))
99  if ((deg-inter)<kmin && !GroupNodes.IsKey(nodesIds[knew]))
100  {
101  kmin = deg-inter; kind = knew;
102  }
103 
104  knew++;
105  }
106 
107  if (kind!=-1){
108  br++;
109  Z = Z + br - 1 - nodes[kind];
110  if (Z < (Zbest)){ // or <=
111  //if (olddeg>nodes[kind])
112 
113  //olddeg = nodes[kind];
114  Zbest = Z;
115  //kbest = br;
116  int w = nodes[kind];
117  int id = nodesIds[kind];
118  GroupNodes.AddDat(id,w);
119  NNodes[NNodes_br] = id;
120  NNodes_br++;
121  }
122  else{
123 
124  break;
125  }
126  }
127  }
128  k=knew-1;
129  }
130  else{
131  br++;
132  Z = Z + br - 1 - nodes[k];
133  if (Z < (Zbest)){ // or <=
134  //if (olddeg>nodes[k])
135 
136  //olddeg = nodes[k];
137  Zbest = Z;
138  //kbest = br;
139  int w = nodes[k];
140  int id = nodesIds[k];
141  GroupNodes.AddDat(id,w);
142  NNodes[NNodes_br] = id;
143  NNodes_br++;
144  }
145  }
146  }
147 
148  else{
149  br++;
150  Z = Z + br - 1 - nodes[k];
151  if (Z < Zbest){ // or <=
152  //if (olddeg>nodes[k])
153 
154  //olddeg = nodes[k];
155  Zbest = Z;
156  //kbest = br;
157  int w = nodes[k];
158  int id = nodesIds[k];
159  GroupNodes.AddDat(id,w);
160  NNodes[NNodes_br] = id;
161  NNodes_br++;
162  }
163  }
164  }
165 
166  int cp = 0;
167  br = 0;
168  for (THashKeyDatI<TInt, TInt> it = nodes.BegI(); !it.IsEnd(); it++) {
169  if (GroupNodes.IsKey(it.GetKey()))
170  cp = 1;
171  else
172  cp = 0;
173  out.AddDat(it.GetKey(), cp);
174  br++;
175  }
176 
177  /*for (THashKeyDatI<TInt, TInt> it = GroupNodes.BegI(); it < GroupNodes.EndI(); it++) {
178  out.AddDat(it.GetKey(), 1);
179  br++;
180  }*/
181 
182  //return kbest;
183  return GroupNodes.Len();
184  }
int Intersect(TUNGraph::TNodeI Node, TIntH NNodes)
Intersect.
Definition: centr.cpp:584
TIter BegI() const
Definition: hash.h:213
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TIter EndI() const
Definition: hash.h:218
bool IsEnd() const
Tests whether the iterator is pointing to the past-end element.
Definition: hash.h:78
bool IsKey(const TKey &Key) const
Definition: hash.h:258
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void SortByDat(const bool &Asc=true)
Definition: hash.h:292
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
MidToSrcAugVContains the path vector from the midpoint node where the bi-d search met back to the source node.
MidToSnkAugVContains 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.

71  {
72  int MidPtNId = IntFlowBiDBFS(Net, CapIndex, Flow, FwdNodeQ, PredEdgeH, BwdNodeQ, SuccEdgeH, SrcNId, SnkNId);
73  if (MidPtNId == -1) { return 0; }
74  int MinAug = TInt::Mx, NId = MidPtNId, AugFlow = 0;
75  // Build the path from the midpoint back to the source by tracing through the PredEdgeH
76  for (int EId = PredEdgeH.GetDat(NId); NId != SrcNId; EId = PredEdgeH.GetDat(NId)) {
77  MidToSrcAugV.Add(EId);
78  const TNEANet::TEdgeI &EI = Net->GetEI(EId);
79  if (EI.GetSrcNId() == NId) {
80  NId = EI.GetDstNId();
81  AugFlow = Flow[EId];
82  } else {
83  NId = EI.GetSrcNId();
84  AugFlow = Net->GetIntAttrIndDatE(EId, CapIndex) - Flow[EId];
85  }
86  if (AugFlow < MinAug) { MinAug = AugFlow; }
87  }
88  NId = MidPtNId;
89  // Build the path from the midpoint back to the sink by tracing through the SuccEdgeH
90  for (int EId = SuccEdgeH.GetDat(NId); NId != SnkNId; EId = SuccEdgeH.GetDat(NId)) {
91  MidToSnkAugV.Add(EId);
92  const TNEANet::TEdgeI &EI = Net->GetEI(EId);
93  if (EI.GetDstNId() == NId) {
94  NId = EI.GetSrcNId();
95  AugFlow = Flow[EId];
96  } else {
97  NId = EI.GetDstNId();
98  AugFlow = Net->GetIntAttrIndDatE(EId, CapIndex) - Flow[EId];
99  }
100  if (AugFlow < MinAug) { MinAug = AugFlow; }
101  }
102  return MinAug;
103 }
static const int Mx
Definition: dt.h:1139
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
int GetDstNId() const
Returns the destination of the edge.
Definition: network.h:1886
int GetSrcNId() const
Returns the source of the edge.
Definition: network.h:1884
int IntFlowBiDBFS(const PNEANet &Net, const int &CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, const int &SrcNId, const int &SnkNId)
Definition: flow.cpp:4
Edge iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1867
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int TSnap::findMinimum ( TIntV Frontier,
TIntFltH NIdDistH 
)

Definition at line 685 of file centr.cpp.

685  {
686  TFlt minimum = TInt::Mx;
687  int min_index = 0;
688  for (int i = 0; i < Frontier.Len(); i++) {
689  int NId = Frontier.GetVal(i);
690  if (NIdDistH[NId] < minimum) {
691  minimum = NIdDistH[NId];
692  min_index = i;
693  }
694  }
695  const int NId = Frontier.GetVal(min_index);
696  Frontier.Del(min_index);
697  return NId;
698 }
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
static const int Mx
Definition: dt.h:1139
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Definition: dt.h:1383
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
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.

174  {
175  const int Nodes = (int) TMath::Round(TMath::Power(5, Levels));
176  PGraph GraphPt = PGraph::New();
177  typename PGraph::TObj& Graph = *GraphPt;
178  Graph.Reserve(Nodes, -1);
179  // base graph
180  for (int i = 0; i < 5; i++) { Graph.AddNode(i); }
181  Graph.AddEdge(1,2); Graph.AddEdge(2,3);
182  Graph.AddEdge(3,4); Graph.AddEdge(4,1);
183  Graph.AddEdge(1,0); Graph.AddEdge(3,0);
184  Graph.AddEdge(2,0); Graph.AddEdge(4,0);
185  // expansion
186  const int CenterId = 0;
187  for (int lev = 1; lev < Levels+1; lev++) {
188  const int MxNId = Graph.GetNodes();
189  // make 4 duplicate copies
190  for (int d = 0; d < 4; d++) {
191  for (int n = 0; n < MxNId; n++) { Graph.AddNode(); }
192  for (int n = 0; n < MxNId; n++) {
193  typename PGraph::TObj::TNodeI NI = Graph.GetNI(n);
194  const int SrcId = n+MxNId*(d+1);
195  for (int e = 0; e < NI.GetOutDeg(); e++) {
196  Graph.AddEdge(SrcId, NI.GetOutNId(e)+MxNId*(d+1));
197  }
198  }
199  }
200  // add edges to the center
201  //const int LevPow = (int)TMath::Round(TMath::Power(5,lev-1));
202  for (int n = MxNId; n < Graph.GetNodes(); n++) {
203  typename PGraph::TObj::TNodeI NI = Graph.GetNI(n);
204  const int SrcId = n;
205  int Pow = 1; bool Skip = false;
206  for (int p = 1; p <= lev; p++) {
207  if (SrcId % (5*Pow) < Pow) { Skip=true; break; }
208  Pow *= 5;
209  }
210  if (Skip) { continue; }
211  Graph.AddEdge(SrcId, CenterId);
212  }
213  }
214  return GraphPt;
215 }
static double Round(const double &Val)
Definition: xmath.h:16
static double Power(const double &Base, const double &Exponent)
Definition: xmath.h:25
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.

104  {
105  PGraph Graph = PGraph::TObj::New();
106  Graph->Reserve(Nodes, Nodes*NodeOutDeg);
107  for (int n = 0; n < Nodes; n++) {
108  Graph->AddNode(n); }
109  for (int n = 0; n < Nodes; n++) {
110  for (int x = 0; x < NodeOutDeg; x++) {
111  Graph->AddEdge(n, (n+x+1) % Nodes);
112  if (Graph->HasFlag(gfDirected) && ! IsDir) { Graph->AddEdge((n+x+1) % Nodes, n); }
113  }
114  }
115  return Graph;
116 }
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
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 119 of file ggen.cpp.

119  {
120  const int Nodes = DegSeqV.Len();
121  PUNGraph GraphPt = TUNGraph::New();
122  TUNGraph& Graph = *GraphPt;
123  Graph.Reserve(Nodes, -1);
124  TIntV NIdDegV(DegSeqV.Len(), 0);
125  int DegSum=0, edges=0;
126  for (int node = 0; node < Nodes; node++) {
127  Graph.AddNode(node);
128  for (int d = 0; d < DegSeqV[node]; d++) { NIdDegV.Add(node); }
129  DegSum += DegSeqV[node];
130  }
131  NIdDegV.Shuffle(Rnd);
132  TIntPrSet EdgeH(DegSum/2); // set of all edges, is faster than graph edge lookup
133  if (DegSum % 2 != 0) {
134  printf("Seg seq is odd [%d]: ", DegSeqV.Len());
135  for (int d = 0; d < TMath::Mn(100, DegSeqV.Len()); d++) { printf(" %d", (int)DegSeqV[d]); }
136  printf("\n");
137  }
138  int u=0, v=0;
139  for (int c = 0; NIdDegV.Len() > 1; c++) {
140  u = Rnd.GetUniDevInt(NIdDegV.Len());
141  while ((v = Rnd.GetUniDevInt(NIdDegV.Len())) == u) { }
142  if (u > v) { Swap(u, v); }
143  const int E1 = NIdDegV[u];
144  const int E2 = NIdDegV[v];
145  if (v == NIdDegV.Len()-1) { NIdDegV.DelLast(); }
146  else { NIdDegV[v] = NIdDegV.Last(); NIdDegV.DelLast(); }
147  if (u == NIdDegV.Len()-1) { NIdDegV.DelLast(); }
148  else { NIdDegV[u] = NIdDegV.Last(); NIdDegV.DelLast(); }
149  if (E1 == E2 || EdgeH.IsKey(TIntPr(E1, E2))) { continue; }
150  EdgeH.AddKey(TIntPr(E1, E2));
151  Graph.AddEdge(E1, E2);
152  edges++;
153  if (c % (DegSum/100+1) == 0) { printf("\r configuration model: iter %d: edges: %d, left: %d", c, edges, NIdDegV.Len()/2); }
154  }
155  printf("\n");
156  return GraphPt;
157 }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Undirected graph.
Definition: graph.h:32
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:298
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
Definition: ds.h:32
Definition: bd.h:196
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
void Swap(TRec &Rec1, TRec &Rec2)
Definition: bd.h:568
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 335 of file ggen.cpp.

335  {
336  TIntV DegSeqV(G->GetNodes(), 0);
337  TSnap::GetDegSeqV(G, DegSeqV);
338  return TSnap::GenConfModel(DegSeqV);
339 }
void GetDegSeqV(const PGraph &Graph, TIntV &DegV)
Returns a degree sequence vector.
Definition: alg.h:245
PUNGraph GenConfModel(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random undirect graph with a given degree sequence.
Definition: ggen.cpp:119
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 453 of file ggen.cpp.

453  {
454  PNGraph GraphPt = TNGraph::New();
455  TNGraph& Graph = *GraphPt;
456  Graph.Reserve(Nodes, Nodes);
457  const int startNId = Graph.AddNode();
458  Graph.AddEdge(startNId, startNId);
459  for (int n = 1; n < Nodes; n++) {
460  const int rnd = Graph.GetRndNId();
461  const int NId = Graph.AddNode();
462  if (Rnd.GetUniDev() < Beta) {
463  Graph.AddEdge(NId, rnd); }
464  else {
465  const TNGraph::TNodeI NI = Graph.GetNI(rnd);
466  const int rnd2 = Rnd.GetUniDevInt(NI.GetOutDeg());
467  Graph.AddEdge(NId, NI.GetOutNId(rnd2));
468  }
469  }
470  return GraphPt;
471 }
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:595
Directed graph.
Definition: graph.h:342
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:402
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
double GetUniDev()
Definition: dt.h:30
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:606
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:412
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. 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 58 of file ggen.cpp.

58  {
59  const int Nodes = DegSeqV.Len();
60  PUNGraph GraphPt = TUNGraph::New();
61  TUNGraph& Graph = *GraphPt;
62  Graph.Reserve(Nodes, -1);
63  TIntH DegH(DegSeqV.Len(), true);
64 
65  IAssertR(DegSeqV.IsSorted(false), "DegSeqV must be sorted in descending order.");
66  int DegSum=0, edge=0;
67  for (int node = 0; node < Nodes; node++) {
68  IAssert(Graph.AddNode(node) == node);
69  DegH.AddDat(node, DegSeqV[node]);
70  DegSum += DegSeqV[node];
71  }
72  IAssert(DegSum % 2 == 0);
73  while (! DegH.Empty()) {
74  // pick random nodes and connect
75  const int NId1 = DegH.GetKey(DegH.GetRndKeyId(TInt::Rnd, 0.5));
76  const int NId2 = DegH.GetKey(DegH.GetRndKeyId(TInt::Rnd, 0.5));
77  IAssert(DegH.IsKey(NId1) && DegH.IsKey(NId2));
78  if (NId1 == NId2) {
79  if (DegH.GetDat(NId1) == 1) { continue; }
80  // find rnd edge, break it, and connect the endpoints to the nodes
81  const TIntPr Edge = TSnapDetail::GetRndEdgeNonAdjNode(GraphPt, NId1, -1);
82  if (Edge.Val1==-1) { continue; }
83  Graph.DelEdge(Edge.Val1, Edge.Val2);
84  Graph.AddEdge(Edge.Val1, NId1);
85  Graph.AddEdge(NId1, Edge.Val2);
86  if (DegH.GetDat(NId1) == 2) { DegH.DelKey(NId1); }
87  else { DegH.GetDat(NId1) -= 2; }
88  } else {
89  if (! Graph.IsEdge(NId1, NId2)) {
90  Graph.AddEdge(NId1, NId2); } // good edge
91  else {
92  // find rnd edge, break and cross-connect
93  const TIntPr Edge = TSnapDetail::GetRndEdgeNonAdjNode(GraphPt, NId1, NId2);
94  if (Edge.Val1==-1) { continue; }
95  Graph.DelEdge(Edge.Val1, Edge.Val2);
96  Graph.AddEdge(NId1, Edge.Val1);
97  Graph.AddEdge(NId2, Edge.Val2);
98  }
99  if (DegH.GetDat(NId1)==1) { DegH.DelKey(NId1); }
100  else { DegH.GetDat(NId1) -= 1; }
101  if (DegH.GetDat(NId2)==1) { DegH.DelKey(NId2); }
102  else { DegH.GetDat(NId2) -= 1; }
103  }
104  if (++edge % 1000 == 0) {
105  printf("\r %dk / %dk", edge/1000, DegSum/2000); }
106  }
107  return GraphPt;
108 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static TRnd Rnd
Definition: dt.h:1143
TIntPr GetRndEdgeNonAdjNode(const PGraph &Graph, int NId1, int NId2)
Returns a random edge in a graph Graph where the edge does not touch nodes NId1 and NId2...
Definition: ggen.h:240
Undirected graph.
Definition: graph.h:32
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:298
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
Definition: ds.h:32
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1323
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
Definition: bd.h:196
bool IsEdge(const int &SrcNId, const int &DstNId) const
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition: graph.cpp:137
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 442 of file ggen.cpp.

442  {
443  return TForestFire::GenGraph(Nodes, FwdProb, BckProb);
444 }
static PNGraph GenGraph(const int &Nodes, const double &FwdProb, const double &BckProb)
Definition: ff.cpp:250
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.

119  {
120  PGraph Graph = PGraph::TObj::New();
121  Graph->Reserve(Nodes, Nodes*Nodes);
122  for (int n = 0; n < Nodes; n++) {
123  Graph->AddNode(n); }
124  for (int n1 = 0; n1 < Nodes; n1++) {
125  for (int n2 = 0; n2 < Nodes; n2++) {
126  if (n1 != n2) { Graph->AddEdge(n1, n2); }
127  }
128  }
129  return Graph;
130 }
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 361 of file ggen.cpp.

361  {
362  PUNGraph G = TUNGraph::New(Nodes, Nodes*OutDeg);
363  TFltTrV PointV(Nodes, 0);
364  TFltV ValV;
365  // points on a sphere of radius 1/(2*pi)
366  const double Rad = 0.5 * TMath::Pi;
367  for (int i = 0; i < Nodes; i++) {
368  TSnapDetail::GetSphereDev(3, Rnd, ValV);
369  PointV.Add(TFltTr(Rad*ValV[0], Rad*ValV[1], Rad*ValV[2]));
370  }
371  const double R2 = TMath::Sqr(log((double) Nodes) / (pow((double) Nodes, 0.5-Beta)));
372  TIntV DegV, NIdV;
373  int SumDeg;
374  for (int t = 0; t < Nodes; t++) {
375  const int pid = t;
376  const TFltTr& P1 = PointV[pid];
377  // add node
378  if (! G->IsNode(pid)) { G->AddNode(pid); }
379  // find neighborhood
380  DegV.Clr(false); NIdV.Clr(false); SumDeg=0;
381  for (int p = 0; p < t; p++) {
382  const TFltTr& P2 = PointV[p];
383  if (TMath::Sqr(P1.Val1-P2.Val1)+TMath::Sqr(P1.Val2-P2.Val2)+TMath::Sqr(P1.Val3-P2.Val3) < R2) {
384  NIdV.Add(p);
385  DegV.Add(G->GetNI(p).GetDeg()+1);
386  SumDeg += DegV.Last();
387  }
388  }
389  // add edges
390  for (int m = 0; m < OutDeg; m++) {
391  const int rnd = Rnd.GetUniDevInt(SumDeg);
392  int sum = 0, dst = -1;
393  for (int s = 0; s < DegV.Len(); s++) {
394  sum += DegV[s];
395  if (rnd < sum) { dst=s; break; }
396  }
397  if (dst != -1) {
398  G->AddEdge(pid, NIdV[dst]);
399  SumDeg -= DegV[dst];
400  NIdV.Del(dst); DegV.Del(dst);
401  }
402  }
403  }
404  return G;
405 }
Definition: ds.h:130
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TVal1 Val1
Definition: ds.h:132
static double Sqr(const double &x)
Definition: xmath.h:12
void GetSphereDev(const int &Dim, TRnd &Rnd, TFltV &ValV)
Sample random point from the surface of a Dim-dimensional unit sphere.
Definition: ggen.cpp:343
TVal2 Val2
Definition: ds.h:133
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
TTriple< TFlt, TFlt, TFlt > TFltTr
Definition: ds.h:181
static double Pi
Definition: xmath.h:8
Definition: bd.h:196
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVal3 Val3
Definition: ds.h:134
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
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.

65  {
66  PGraph GraphPt = PGraph::New();
67  typename PGraph::TObj& Graph = *GraphPt;
68  Graph.Reserve(Rows*Cols, 4*Rows*Cols);
69  int node, r, c;
70  for (node = 0; node < Rows * Cols; node++) {
71  Graph.AddNode(node); }
72  for (r = 0; r < Rows; r++) {
73  for (c = 0; c < Cols; c++) {
74  const int nodeId = Cols*r + c;
75  if (r < Rows-1) { // bottom node
76  Graph.AddEdge(nodeId, nodeId+Cols);
77  if (Graph.HasFlag(gfDirected) && ! IsDir) {
78  Graph.AddEdge(nodeId+Cols, nodeId); }
79  }
80  if (c < Cols-1) { // right node
81  Graph.AddEdge(nodeId, nodeId+1);
82  if (Graph.HasFlag(gfDirected) && ! IsDir) {
83  Graph.AddEdge(nodeId+1, nodeId); }
84  }
85  }
86  }
87  return GraphPt;
88 }
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
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 310 of file ggen.cpp.

310  {
311  PUNGraph GraphPt = PUNGraph::New();
312  TUNGraph& Graph = *GraphPt;
313  Graph.Reserve(Nodes, NodeOutDeg*Nodes);
314  TIntV NIdV(NodeOutDeg*Nodes, 0);
315  // first edge
316  Graph.AddNode(0); Graph.AddNode(1);
317  NIdV.Add(0); NIdV.Add(1);
318  Graph.AddEdge(0, 1);
319  TIntSet NodeSet;
320  for (int node = 2; node < Nodes; node++) {
321  NodeSet.Clr(false);
322  while (NodeSet.Len() < NodeOutDeg && NodeSet.Len() < node) {
323  NodeSet.AddKey(NIdV[TInt::Rnd.GetUniDevInt(NIdV.Len())]);
324  }
325  const int N = Graph.AddNode();
326  for (int i = 0; i < NodeSet.Len(); i++) {
327  Graph.AddEdge(N, NodeSet[i]);
328  NIdV.Add(N);
329  NIdV.Add(NodeSet[i]);
330  }
331  }
332  return GraphPt;
333 }
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
static TPt New()
Definition: bd.h:479
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
static TRnd Rnd
Definition: dt.h:1143
Undirected graph.
Definition: graph.h:32
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:298
int AddKey(const TKey &Key)
Definition: shash.h:1254
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
int Len() const
Definition: shash.h:1121
Definition: bd.h:196
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 165 of file ggen.cpp.

165  {
166  const int Nodes = OrigGraph->GetNodes();
167  const int Edges = OrigGraph->GetEdges();
168  PUNGraph GraphPt = TUNGraph::New();
169  TUNGraph& Graph = *GraphPt;
170  Graph.Reserve(Nodes, -1);
171  TExeTm ExeTm;
172  // generate a graph that satisfies the constraints
173  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
174  TIntPrSet EdgeSet(Edges);
175  for (TUNGraph::TNodeI NI = OrigGraph->BegNI(); NI < OrigGraph->EndNI(); NI++) {
176  const int NId = NI.GetId();
177  for (int e = 0; e < NI.GetOutDeg(); e++) {
178  if (NId <= NI.GetOutNId(e)) { continue; }
179  EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e)));
180  }
181  Graph.AddNode(NI.GetId());
182  }
183  // edge switching
184  uint skip=0;
185  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
186  const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
187  const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
188  if (keyId1 == keyId2) { skip++; continue; }
189  const TIntPr& E1 = EdgeSet[keyId1];
190  const TIntPr& E2 = EdgeSet[keyId2];
191  TIntPr NewE1(E1.Val1, E2.Val1), NewE2(E1.Val2, E2.Val2);
192  if (NewE1.Val1 > NewE1.Val2) { Swap(NewE1.Val1, NewE1.Val2); }
193  if (NewE2.Val1 > NewE2.Val2) { Swap(NewE2.Val1, NewE2.Val2); }
194  if (NewE1!=NewE2 && NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
195  EdgeSet.DelKeyId(keyId1); EdgeSet.DelKeyId(keyId2);
196  EdgeSet.AddKey(TIntPr(NewE1));
197  EdgeSet.AddKey(TIntPr(NewE2));
198  } else { skip++; }
199  if (swps % Edges == 0) {
200  printf("\r %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
201  if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
202  }
203  }
204  printf("\r total %uk switchings attempted, %uk skiped [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
205  for (int e = 0; e < EdgeSet.Len(); e++) {
206  Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
207  return GraphPt;
208 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
Definition: tm.h:355
unsigned int uint
Definition: bd.h:11
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
Undirected graph.
Definition: graph.h:32
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:298
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
Definition: ds.h:32
double GetSecs() const
Definition: tm.h:366
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
Definition: bd.h:196
const char * GetStr() const
Definition: tm.h:368
void Swap(TRec &Rec1, TRec &Rec2)
Definition: bd.h:568
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 216 of file ggen.cpp.

216  {
217  const int Nodes = OrigGraph->GetNodes();
218  const int Edges = OrigGraph->GetEdges();
219  PNGraph GraphPt = TNGraph::New();
220  TNGraph& Graph = *GraphPt;
221  Graph.Reserve(Nodes, -1);
222  TExeTm ExeTm;
223  // generate a graph that satisfies the constraints
224  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
225  TIntPrSet EdgeSet(Edges);
226  for (TNGraph::TNodeI NI = OrigGraph->BegNI(); NI < OrigGraph->EndNI(); NI++) {
227  const int NId = NI.GetId();
228  for (int e = 0; e < NI.GetOutDeg(); e++) {
229  EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e))); }
230  Graph.AddNode(NI);
231  }
232  // edge switching
233  uint skip=0;
234  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
235  const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
236  const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
237  if (keyId1 == keyId2) { skip++; continue; }
238  const TIntPr& E1 = EdgeSet[keyId1];
239  const TIntPr& E2 = EdgeSet[keyId2];
240  TIntPr NewE1(E1.Val1, E2.Val2), NewE2(E2.Val1, E1.Val2);
241  if (NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && NewE1.Val1!=NewE2.Val1 && NewE1.Val2!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
242  EdgeSet.DelKeyId(keyId1); EdgeSet.DelKeyId(keyId2);
243  EdgeSet.AddKey(TIntPr(NewE1));
244  EdgeSet.AddKey(TIntPr(NewE2));
245  } else { skip++; }
246  if (swps % Edges == 0) {
247  printf("\r %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
248  if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
249  }
250  }
251  printf("\r total %uk switchings attempted, %uk skiped [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
252  for (int e = 0; e < EdgeSet.Len(); e++) {
253  Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
254  return GraphPt;
255 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
Definition: tm.h:355
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
unsigned int uint
Definition: bd.h:11
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
Directed graph.
Definition: graph.h:342
Definition: ds.h:32
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
double GetSecs() const
Definition: tm.h:366
TVal1 Val1
Definition: ds.h:34
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:606
TVal2 Val2
Definition: ds.h:35
const char * GetStr() const
Definition: tm.h:368
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 263 of file ggen.cpp.

263  {
264  const int Nodes = OrigGraph->GetNodes();
265  const int Edges = OrigGraph->GetEdges();
266  PBPGraph GraphPt = TBPGraph::New();
267  TBPGraph& Graph = *GraphPt;
268  Graph.Reserve(Nodes, -1);
269  TExeTm ExeTm;
270  // generate a graph that satisfies the constraints
271  printf("Randomizing edges (%d, %d)...\n", Nodes, Edges);
272  TIntPrSet EdgeSet(Edges);
273  for (TBPGraph::TNodeI NI = OrigGraph->BegLNI(); NI < OrigGraph->EndLNI(); NI++) {
274  const int NId = NI.GetId();
275  for (int e = 0; e < NI.GetOutDeg(); e++) {
276  EdgeSet.AddKey(TIntPr(NId, NI.GetOutNId(e))); } // edges left-->right
277  Graph.AddNode(NI.GetId(), true); } // left nodes
278  for (TBPGraph::TNodeI NI = OrigGraph->BegRNI(); NI < OrigGraph->EndRNI(); NI++) {
279  Graph.AddNode(NI.GetId(), false); } // right nodes
280  IAssert(EdgeSet.Len() == Edges);
281  // edge switching
282  uint skip=0;
283  for (uint swps = 0; swps < 2*uint(Edges)*uint(NSwitch); swps++) {
284  const int keyId1 = EdgeSet.GetRndKeyId(Rnd);
285  const int keyId2 = EdgeSet.GetRndKeyId(Rnd);
286  if (keyId1 == keyId2) { skip++; continue; }
287  const TIntPr& E1 = EdgeSet[keyId1];
288  const TIntPr& E2 = EdgeSet[keyId2];
289  TIntPr NewE1(E1.Val1, E2.Val2), NewE2(E2.Val1, E1.Val2);
290  if (NewE1!=NewE2 && NewE1.Val1!=NewE1.Val2 && NewE2.Val1!=NewE2.Val2 && ! EdgeSet.IsKey(NewE1) && ! EdgeSet.IsKey(NewE2)) {
291  EdgeSet.DelKeyId(keyId1); EdgeSet.DelKeyId(keyId2);
292  EdgeSet.AddKey(TIntPr(NewE1));
293  EdgeSet.AddKey(TIntPr(NewE2));
294  } else { skip++; }
295  if (swps % Edges == 0) {
296  printf("\r %uk/%uk: %uk skip [%s]", swps/1000u, 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
297  if (ExeTm.GetSecs() > 2*3600) { printf(" *** Time limit!\n"); break; } // time limit 2 hours
298  }
299  }
300  printf("\r total %uk switchings attempted, %uk skiped [%s]\n", 2*uint(Edges)*uint(NSwitch)/1000u, skip/1000u, ExeTm.GetStr());
301  for (int e = 0; e < EdgeSet.Len(); e++) {
302  Graph.AddEdge(EdgeSet[e].Val1, EdgeSet[e].Val2); }
303  return GraphPt;
304 }
#define IAssert(Cond)
Definition: bd.h:262
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a biparite graph of Nodes nodes and Edges edges.
Definition: graph.cpp:790
Definition: tm.h:355
unsigned int uint
Definition: bd.h:11
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:960
int AddNode(int NId=-1, const bool &LeftNode=true)
Adds a node of ID NId to the graph.
Definition: graph.cpp:671
int AddEdge(const int &LeftNId, const int &RightNId)
Adds an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartit...
Definition: graph.cpp:705
Definition: ds.h:32
Bipartite graph.
Definition: graph.h:928
double GetSecs() const
Definition: tm.h:366
TVal1 Val1
Definition: ds.h:34
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:1054
TVal2 Val2
Definition: ds.h:35
Definition: bd.h:196
const char * GetStr() const
Definition: tm.h:368
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 478 of file ggen.cpp.

478  {
479  PNGraph GraphPt = TNGraph::New();
480  TNGraph& Graph = *GraphPt;
481  Graph.Reserve(Nodes, Edges);
482  IAssert(A+B+C < 1.0);
483  int rngX, rngY, offX, offY;
484  int Depth=0, Collisions=0, Cnt=0, PctDone=0;
485  const int EdgeGap = Edges / 100 + 1;
486  // sum of parameters (probabilities)
487  TVec<double> sumA(128, 0), sumAB(128, 0), sumAC(128, 0), sumABC(128, 0); // up to 2^128 vertices ~ 3.4e38
488  for (int i = 0; i < 128; i++) {
489  const double a = A * (Rnd.GetUniDev() + 0.5);
490  const double b = B * (Rnd.GetUniDev() + 0.5);
491  const double c = C * (Rnd.GetUniDev() + 0.5);
492  const double d = (1.0 - (A+B+C)) * (Rnd.GetUniDev() + 0.5);
493  const double abcd = a+b+c+d;
494  sumA.Add(a / abcd);
495  sumAB.Add((a+b) / abcd);
496  sumAC.Add((a+c) / abcd);
497  sumABC.Add((a+b+c) / abcd);
498  }
499  // nodes
500  for (int node = 0; node < Nodes; node++) {
501  IAssert(Graph.AddNode(-1) == node);
502  }
503  // edges
504  for (int edge = 0; edge < Edges; ) {
505  rngX = Nodes; rngY = Nodes; offX = 0; offY = 0;
506  Depth = 0;
507  // recurse the matrix
508  while (rngX > 1 || rngY > 1) {
509  const double RndProb = Rnd.GetUniDev();
510  if (rngX>1 && rngY>1) {
511  if (RndProb < sumA[Depth]) { rngX/=2; rngY/=2; }
512  else if (RndProb < sumAB[Depth]) { offX+=rngX/2; rngX-=rngX/2; rngY/=2; }
513  else if (RndProb < sumABC[Depth]) { offY+=rngY/2; rngX/=2; rngY-=rngY/2; }
514  else { offX+=rngX/2; offY+=rngY/2; rngX-=rngX/2; rngY-=rngY/2; }
515  } else
516  if (rngX>1) { // row vector
517  if (RndProb < sumAC[Depth]) { rngX/=2; rngY/=2; }
518  else { offX+=rngX/2; rngX-=rngX/2; rngY/=2; }
519  } else
520  if (rngY>1) { // column vector
521  if (RndProb < sumAB[Depth]) { rngX/=2; rngY/=2; }
522  else { offY+=rngY/2; rngX/=2; rngY-=rngY/2; }
523  } else { Fail; }
524  Depth++;
525  }
526  // add edge
527  const int NId1 = offX;
528  const int NId2 = offY;
529  if (NId1 != NId2 && ! Graph.IsEdge(NId1, NId2)) {
530  Graph.AddEdge(NId1, NId2);
531  if (++Cnt > EdgeGap) {
532  Cnt=0; printf("\r %d%% edges", ++PctDone); }
533  edge++;
534  } else {
535  Collisions++; }
536  }
537  printf("\r RMat: nodes:%d, edges:%d, Iterations:%d, Collisions:%d (%.1f%%).\n", Nodes, Edges,
538  Edges+Collisions, Collisions, 100*Collisions/double(Edges+Collisions));
539  Graph.Defrag();
540  return GraphPt;
541 }
#define IAssert(Cond)
Definition: bd.h:262
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
#define Fail
Definition: bd.h:238
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:382
Directed graph.
Definition: graph.h:342
double GetUniDev()
Definition: dt.h:30
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:606
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
PNGraph TSnap::GenRMatEpinions ( )

Generates a R-Mat graph, with a synthetic copy of the Epinions social network.

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

Definition at line 547 of file ggen.cpp.

547  {
548  return GenRMat(75888, 508837, 0.550, 0.228, 0.212);
549 }
PNGraph 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)].
Definition: ggen.cpp:478
PBPGraph TSnap::GenRndBipart ( const int &  LeftNodes,
const int &  RightNodes,
const int &  Edges,
TRnd Rnd 
)

Generates a random bipartite graph.

Definition at line 5 of file ggen.cpp.

5  {
7  for (int i = 0; i < LeftNodes; i++) { G->AddNode(i, true); }
8  for (int i = 0; i < RightNodes; i++) { G->AddNode(LeftNodes+i, false); }
9  IAssertR(Edges <= LeftNodes*RightNodes, "Too many edges in the bipartite graph!");
10  for (int edges = 0; edges < Edges; ) {
11  const int LNId = Rnd.GetUniDevInt(LeftNodes);
12  const int RNId = LeftNodes + Rnd.GetUniDevInt(RightNodes);
13  if (G->AddEdge(LNId, RNId) != -2) { edges++; } // is new edge
14  }
15  return G;
16 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:1054
Definition: bd.h:196
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
PUNGraph TSnap::GenRndDegK ( const int &  Nodes,
const int &  NodeDeg,
const int &  NSwitch,
TRnd Rnd 
)

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

Definition at line 18 of file ggen.cpp.

18  {
19  // create degree sequence
20  TIntV DegV(Nodes, 0);
21  int DegSum=0;
22  for (int i = 0; i < Nodes; i++) {
23  DegV.Add(NodeDeg);
24  DegSum += NodeDeg;
25  }
26  IAssert(DegSum % 2 == 0);
27  PUNGraph G = GenDegSeq(DegV, Rnd); // get some graph that obeys the degree sequnce
28  return GenRewire(G, NSwitch, Rnd); // make it random
29 }
#define IAssert(Cond)
Definition: bd.h:262
PUNGraph GenDegSeq(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random graph with exact degree sequence.
Definition: ggen.cpp:58
PBPGraph GenRewire(const PBPGraph &OrigGraph, const int &NSwitch, TRnd &Rnd)
Rewire a random bipartite graph. Keeps node degrees the same, but randomly rewires the edges...
Definition: ggen.cpp:263
Definition: bd.h:196
template<class PGraph >
PGraph TSnap::GenRndGnm ( const int &  Nodes,
const int &  Edges,
const bool &  IsDir = true,
TRnd Rnd = TInt::Rnd 
)

Generates an Erdos-Renyi random graph.

Definition at line 218 of file ggen.h.

218  {
219  PGraph GraphPt = PGraph::New();
220  typename PGraph::TObj& Graph = *GraphPt;
221  Graph.Reserve(Nodes, Edges);
222  IAssertR((1.0 * (Nodes-1) / 2 * (IsDir ? 2 : 1)) >= (1.0 * Edges / Nodes), TStr::Fmt("Not enough nodes (%d), for edges (%d).", Nodes, Edges));
223  for (int node = 0; node < Nodes; node++) {
224  IAssert(Graph.AddNode(node) == node);
225  }
226  for (int edge = 0; edge < Edges; ) {
227  const int SrcNId = Rnd.GetUniDevInt(Nodes);
228  const int DstNId = Rnd.GetUniDevInt(Nodes);
229  if (SrcNId != DstNId && Graph.AddEdge(SrcNId, DstNId) != -2) { // is new edge
230  if (! IsDir) { Graph.AddEdge(DstNId, SrcNId); }
231  edge++;
232  }
233  }
234  return GraphPt;
235 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
PUNGraph TSnap::GenRndPowerLaw ( const int &  Nodes,
const double &  PowerExp,
const bool &  ConfModel,
TRnd Rnd 
)

Generates a random scale-free graph with power-law degree distribution.

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

Definition at line 34 of file ggen.cpp.

34  {
35  TIntV DegSeqV;
36  uint DegSum=0;
37  for (int n = 0; n < Nodes; n++) {
38  const int Val = (int) TMath::Round(Rnd.GetPowerDev(PowerExp));
39  if (! (Val >= 1 && Val < Nodes/2)) { n--; continue; } // skip nodes with too large degree
40  DegSeqV.Add(Val);
41  DegSum += Val;
42  }
43  printf("%d nodes, %u edges\n", Nodes, DegSum);
44  if (DegSum % 2 == 1) { DegSeqV[0] += 1; }
45  if (ConfModel) {
46  // use configuration model -- fast but does not exactly obey the degree sequence
47  return GenConfModel(DegSeqV, Rnd);
48  } else {
49  PUNGraph G = TSnap::GenDegSeq(DegSeqV, Rnd);
50  return TSnap::GenRewire(G, 10, Rnd);
51  }
52 }
PUNGraph GenRewire(const PUNGraph &OrigGraph, const int &NSwitch, TRnd &Rnd)
Rewire a random undirected graph. Keeps node degrees the same, but randomly rewires the edges...
Definition: ggen.cpp:165
unsigned int uint
Definition: bd.h:11
PUNGraph GenDegSeq(const TIntV &DegSeqV, TRnd &Rnd)
Generates a random graph with exact degree sequence.
Definition: ggen.cpp:58
static double Round(const double &Val)
Definition: xmath.h:16
PUNGraph GenConfModel(const PUNGraph &G)
Generate a random graph using (approximately) the same node degrees as in G using the configuration m...
Definition: ggen.cpp:335
Definition: bd.h:196
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
double GetPowerDev(const double &AlphaSlope)
Definition: dt.h:47
PUNGraph TSnap::GenSmallWorld ( const int &  Nodes,
const int &  NodeOutDeg,
const double &  RewireProb,
TRnd Rnd 
)

Generates a randomly small-world graph using the Watts-Strogatz model.

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

Definition at line 412 of file ggen.cpp.

412  {
413  THashSet<TIntPr> EdgeSet(Nodes*NodeOutDeg);
414 
415  IAssertR(Nodes > NodeOutDeg, TStr::Fmt("Insufficient nodes for out degree, %d!", NodeOutDeg));
416  for (int node = 0; node < Nodes; node++) {
417  const int src = node;
418  for (int edge = 1; edge <= NodeOutDeg; edge++) {
419  int dst = (node+edge) % Nodes; // edge to next neighbor
420  if (Rnd.GetUniDev() < RewireProb) { // random edge
421  dst = Rnd.GetUniDevInt(Nodes);
422  while (dst == src || EdgeSet.IsKey(TIntPr(src, dst))) {
423  dst = Rnd.GetUniDevInt(Nodes); }
424  }
425  EdgeSet.AddKey(TIntPr(src, dst));
426  }
427  }
428  PUNGraph GraphPt = TUNGraph::New();
429  TUNGraph& Graph = *GraphPt;
430  Graph.Reserve(Nodes, EdgeSet.Len());
431  int node;
432  for (node = 0; node < Nodes; node++) {
433  IAssert(Graph.AddNode(node) == node);
434  }
435  for (int edge = 0; edge < EdgeSet.Len(); edge++) {
436  Graph.AddEdge(EdgeSet[edge].Val1, EdgeSet[edge].Val2);
437  }
438  Graph.Defrag();
439  return GraphPt;
440 }
#define IAssert(Cond)
Definition: bd.h:262
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
Undirected graph.
Definition: graph.h:32
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:298
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
Definition: ds.h:32
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:160
double GetUniDev()
Definition: dt.h:30
Definition: bd.h:196
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
template<class PGraph >
PGraph TSnap::GenStar ( const int &  Nodes,
const bool &  IsDir = true 
)

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

Definition at line 91 of file ggen.h.

91  {
92  PGraph Graph = PGraph::TObj::New();
93  Graph->Reserve(Nodes, Nodes);
94  Graph->AddNode(0);
95  for (int n = 1; n < Nodes; n++) {
96  Graph->AddNode(n);
97  Graph->AddEdge(0, n);
98  if (Graph->HasFlag(gfDirected) && ! IsDir) { Graph->AddEdge(n, 0); }
99  }
100  return Graph;
101 }
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
template<class PGraph >
PGraph TSnap::GenTree ( const int &  Fanout,
const int &  Levels,
const bool &  IsDir = true,
const bool &  ChildPointsToParent = true 
)

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

Definition at line 133 of file ggen.h.

133  {
134  const int Nodes = (int) (pow(double(Fanout), double(Levels+1)) - 1) / (Fanout - 1);
135  const int Edges = Nodes - 1;
136  PGraph GraphPt = PGraph::New();
137  typename PGraph::TObj& Graph = *GraphPt;
138  Graph.Reserve(Nodes, Edges);
139  int node;
140  for (node = 0; node < Nodes; node++) {
141  Graph.AddNode(node); }
142  // non-leaf nodes
143  for (node = 0; node < (int) Nodes - (int) pow(double(Fanout), double(Levels)); node++) {
144  for (int edge = 1; edge <= Fanout; edge++) {
145  if (IsDir) {
146  if (ChildPointsToParent) { Graph.AddEdge(Fanout*node+edge, node); }
147  else { Graph.AddEdge(node, Fanout*node+edge); }
148  } else {
149  Graph.AddEdge(node, Fanout*node+edge); // link children
150  Graph.AddEdge(Fanout*node+edge, node);
151  }
152  }
153  }
154  return GraphPt;
155 }
void TSnap::Get1CnCom ( const PUNGraph Graph,
TCnComV Cn1ComV 
)

Returns 1-components: maximal connected components of that can be disconnected from the Graph by removing a single edge.

We find such components as follows: Find all bridge edges, remove them from the Graph, find largest component K and add back all bridges that do not touch K. Now, find the connected components of this graph.

Definition at line 98 of file cncom.cpp.

98  {
99  //TCnCom::GetWccCnt(Graph, SzCntV); IAssertR(SzCntV.Len() == 1, "Graph is not connected.");
100  TIntPrV EdgeV;
101  GetEdgeBridges(Graph, EdgeV);
102  if (EdgeV.Empty()) { Cn1ComV.Clr(false); return; }
103  PUNGraph TmpG = TUNGraph::New();
104  *TmpG = *Graph;
105  for (int e = 0; e < EdgeV.Len(); e++) {
106  TmpG->DelEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
107  TCnComV CnComV; GetWccs(TmpG, CnComV);
108  IAssert(CnComV.Len() >= 2);
109  const TIntV& MxWcc = CnComV[0].NIdV;
110  TIntSet MxCcSet(MxWcc.Len());
111  for (int i = 0; i < MxWcc.Len(); i++) {
112  MxCcSet.AddKey(MxWcc[i]); }
113  // create new graph: bridges not touching MxCc of G with no bridges
114  for (int e = 0; e < EdgeV.Len(); e++) {
115  if (! MxCcSet.IsKey(EdgeV[e].Val1) && ! MxCcSet.IsKey(EdgeV[e].Val2)) {
116  TmpG->AddEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
117  }
118  GetWccs(TmpG, Cn1ComV);
119  // remove the largest component of G
120  for (int c = 0; c < Cn1ComV.Len(); c++) {
121  if (MxCcSet.IsKey(Cn1ComV[c].NIdV[0])) {
122  Cn1ComV.Del(c); break; }
123  }
124 }
#define IAssert(Cond)
Definition: bd.h:262
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddKey(const TKey &Key)
Definition: shash.h:1254
void GetEdgeBridges(const PUNGraph &Graph, TIntPrV &EdgeV)
Returns bridge edges of a Graph.
Definition: cncom.cpp:55
Definition: bd.h:196
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376
void TSnap::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.

We find such components as follows: Find all bridge edges, remove them from the Graph, find largest component K and add back all bridges that do not touch K. Now, find the connected components of this graph.

Definition at line 70 of file cncom.cpp.

70  {
71  //TCnCom::GetWccCnt(Graph, SzCntV); IAssertR(SzCntV.Len() == 1, "Graph is not connected.");
72  TIntPrV EdgeV;
73  GetEdgeBridges(Graph, EdgeV);
74  if (EdgeV.Empty()) { SzCntV.Clr(false); return; }
75  PUNGraph TmpG = TUNGraph::New();
76  *TmpG = *Graph;
77  for (int e = 0; e < EdgeV.Len(); e++) {
78  TmpG->DelEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
79  TCnComV CnComV; GetWccs(TmpG, CnComV);
80  IAssert(CnComV.Len() >= 2);
81  const TIntV& MxWcc = CnComV[0].NIdV;
82  TIntSet MxCcSet(MxWcc.Len());
83  for (int i = 0; i < MxWcc.Len(); i++) {
84  MxCcSet.AddKey(MxWcc[i]); }
85  // create new graph: bridges not touching MxCc of G with no bridges
86  for (int e = 0; e < EdgeV.Len(); e++) {
87  if (! MxCcSet.IsKey(EdgeV[e].Val1) && ! MxCcSet.IsKey(EdgeV[e].Val2)) {
88  TmpG->AddEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
89  }
90  GetWccSzCnt(TmpG, SzCntV);
91  for (int c = 0; c < SzCntV.Len(); c++) {
92  if (SzCntV[c].Val1 == MxCcSet.Len()) {
93  SzCntV.Del(c); break; }
94  }
95 }
#define IAssert(Cond)
Definition: bd.h:262
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddKey(const TKey &Key)
Definition: shash.h:1254
void GetEdgeBridges(const PUNGraph &Graph, TIntPrV &EdgeV)
Returns bridge edges of a Graph.
Definition: cncom.cpp:55
Definition: bd.h:196
void GetWccSzCnt(const PGraph &Graph, TIntPrV &WccSzCnt)
Returns a distribution of weakly connected component sizes.
Definition: cncom.h:337
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376
template<class PGraph >
void TSnap::GetAnf ( const PGraph &  Graph,
const int &  SrcNId,
TIntFltKdV DistNbrsV,
const int &  MxDist,
const bool &  IsDir,
const int &  NApprox = 32 
)

Approximate Neighborhood Function of a node: Returns the (approximate) number of nodes reachable from SrcNId in less than H hops.

Parameters
SrcNIdStarting node.
DistNbrsVMaps between the distance H (in hops) and the number of nodes reachable in <=H hops.
MxDistMaximum number of hops the algorithm spreads from SrcNId.
IsDirfalse: consider links as undirected (drop link directions).
NApproxQuality of approximation. See the ANF paper.

Definition at line 204 of file anf.h.

204  {
205  TGraphAnf<PGraph> Anf(Graph, NApprox, 5, 0);
206  Anf.GetNodeAnf(SrcNId, DistNbrsV, MxDist, IsDir);
207 }
Definition: anf.h:33
template<class PGraph >
void TSnap::GetAnf ( const PGraph &  Graph,
TIntFltKdV DistNbrsV,
const int &  MxDist,
const bool &  IsDir,
const int &  NApprox = 32 
)

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

Parameters
DistNbrsVMaps between the distance H (in hops) and the number of nodes reachable in <=H hops.
MxDistMaximum number of hops the algorithm spreads from SrcNId.
IsDirfalse: consider links as undirected (drop link directions).
NApproxQuality of approximation. See the ANF paper.

Definition at line 210 of file anf.h.

210  {
211  TGraphAnf<PGraph> Anf(Graph, NApprox, 5, 0);
212  Anf.GetGraphAnf(DistNbrsV, MxDist, IsDir);
213 }
Definition: anf.h:33
template<class PGraph >
double TSnap::GetAnfEffDiam ( const PGraph &  Graph,
const bool &  IsDir,
const double &  Percentile,
const int &  NApprox 
)

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

Parameters
IsDirfalse: consider links as undirected (drop link directions).

Definition at line 216 of file anf.h.

216  {
217  TIntFltKdV DistNbrsV;
218  TGraphAnf<PGraph> Anf(Graph, NApprox, 5, 0);
219  Anf.GetGraphAnf(DistNbrsV, -1, IsDir);
220  return TSnap::TSnapDetail::CalcEffDiam(DistNbrsV, Percentile);
221 }
double CalcEffDiam(const TIntFltKdV &DistNbrsCdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function...
Definition: anf.cpp:7
Definition: anf.h:33
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
template<class PGraph >
double TSnap::GetAnfEffDiam ( const PGraph &  Graph,
const int  NRuns = 1,
int  NApprox = -1 
)

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

Parameters
IsDirfalse: consider links as undirected (drop link directions).

Definition at line 224 of file anf.h.

224  {
225  //return TSnap::GetEffDiam(Graph, IsDir, 0.9, 32);
226  TMom Mom;
227  if (NApprox == -1) {
228  if (Graph->GetNodes() < 100000) { NApprox = 64; }
229  else if (Graph->GetNodes() < 1000000) { NApprox = 32; }
230  else { NApprox = 16; }
231  }
232  const bool IsDir = false;
233  for (int r = 0; r < NRuns; r++) {
234  Mom.Add(TSnap::GetAnfEffDiam(Graph, IsDir, 0.9, NApprox));
235  }
236  Mom.Def();
237  return Mom.GetMean();
238 }
double GetAnfEffDiam(const PGraph &Graph, const bool &IsDir, const double &Percentile, const int &NApprox)
Definition: anf.h:216
Definition: xmath.h:129
void Add(const TFlt &Val, const TFlt &Wgt=1)
Definition: xmath.h:217
double GetMean() const
Definition: xmath.h:240
void Def()
Definition: xmath.cpp:339
void TSnap::GetArtPoints ( const PUNGraph Graph,
TIntV ArtNIdV 
)

Returns articulation points of a Graph.

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

Definition at line 48 of file cncom.cpp.

48  {
49  TArtPointVisitor Visitor(Graph->GetNodes());
50  TCnCom::GetDfsVisitor(Graph, Visitor);
51  Visitor.ArtSet.GetKeyV(ArtNIdV);
52 }
static void GetDfsVisitor(const PGraph &Graph, TVisitor &Visitor)
Definition: cncom.h:124
Articulation point Depth-First-Search visitor class.
Definition: cncom.h:169
template<class PGraph >
void TSnap::GetBetweennessCentr ( const PGraph &  Graph,
TIntFltH NIdBtwH,
const double &  NodeFrac = 1.0,
const bool &  IsDir = false 
)

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

Parameters
NIdBtwHhash table mapping node ids to their corresponding betweenness centrality values.
NodeFracquality of approximation. NodeFrac=1.0 gives exact betweenness values.

Definition at line 489 of file centr.h.

489  {
490  TIntPrFltH EdgeBtwH;
491  TIntV NIdV; Graph->GetNIdV(NIdV);
492  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
493  NIdV.Shuffle(TInt::Rnd);
494  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
495  NIdV.DelLast(); }
496  }
497  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, true, EdgeBtwH, false, IsDir);
498 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static TRnd Rnd
Definition: dt.h:1143
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
template<class PGraph >
void TSnap::GetBetweennessCentr ( const PGraph &  Graph,
TIntPrFltH EdgeBtwH,
const double &  NodeFrac = 1.0,
const bool &  IsDir = false 
)

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

Parameters
EdgeBtwHhash table mapping edges (pairs of node ids) to their corresponding betweenness centrality values.
NodeFracquality of approximation. NodeFrac=1.0 gives exact betweenness values.

Definition at line 501 of file centr.h.

501  {
502  TIntFltH NodeBtwH;
503  TIntV NIdV; Graph->GetNIdV(NIdV);
504  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
505  NIdV.Shuffle(TInt::Rnd);
506  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
507  NIdV.DelLast(); }
508  }
509  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, false, EdgeBtwH, true, IsDir);
510 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static TRnd Rnd
Definition: dt.h:1143
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
template<class PGraph >
void TSnap::GetBetweennessCentr ( const PGraph &  Graph,
TIntFltH NIdBtwH,
TIntPrFltH EdgeBtwH,
const double &  NodeFrac = 1.0,
const bool &  IsDir = false 
)

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

Parameters
NIdBtwHhash table mapping node ids to their corresponding betweenness centrality values.
EdgeBtwHhash table mapping edges (pairs of node ids) to their corresponding betweenness centrality values.
NodeFracquality of approximation. NodeFrac=1.0 gives exact betweenness values.

Definition at line 513 of file centr.h.

513  {
514  TIntV NIdV; Graph->GetNIdV(NIdV);
515  if (NodeFrac < 1.0) { // calculate beetweenness centrality for a subset of nodes
516  NIdV.Shuffle(TInt::Rnd);
517  for (int i = int((1.0-NodeFrac)*NIdV.Len()); i > 0; i--) {
518  NIdV.DelLast(); }
519  }
520  GetBetweennessCentr<PGraph> (Graph, NIdV, NodeBtwH, true, EdgeBtwH, true, IsDir);
521 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static TRnd Rnd
Definition: dt.h:1143
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
template<class PGraph >
void TSnap::GetBetweennessCentr ( const PGraph &  Graph,
const TIntV BtwNIdV,
TIntFltH NodeBtwH,
const bool &  DoNodeCent,
TIntPrFltH EdgeBtwH,
const bool &  DoEdgeCent,
const bool &  IsDir 
)

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

Definition at line 374 of file centr.h.

374  {
375  if (DoNodeCent) { NodeBtwH.Clr(); }
376  if (DoEdgeCent) { EdgeBtwH.Clr(); }
377  const int nodes = Graph->GetNodes();
378  TIntS S(nodes);
379  TIntQ Q(nodes);
380  TIntIntVH P(nodes); // one vector for every node
381  TIntFltH delta(nodes);
382  TIntH sigma(nodes), d(nodes);
383  // init
384  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
385  if (DoNodeCent) {
386  NodeBtwH.AddDat(NI.GetId(), 0); }
387  if (DoEdgeCent) {
388  for (int e = 0; e < NI.GetOutDeg(); e++) {
389  if (Graph->HasFlag(gfDirected) && IsDir) {
390  // add all outgoing edges for directed graphs
391  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetOutNId(e)), 0);
392  } else {
393  // add each edge only once in undirected graphs
394  if (NI.GetId() < NI.GetOutNId(e)) {
395  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetOutNId(e)), 0);
396  }
397  }
398  }
399  // add incoming edges in directed graphs that were not added yet
400  if (Graph->HasFlag(gfDirected) && !IsDir) {
401  for (int e = 0; e < NI.GetInDeg(); e++) {
402  if (NI.GetId() < NI.GetInNId(e) &&
403  !Graph->IsEdge(NI.GetId(), NI.GetInNId(e))) {
404  EdgeBtwH.AddDat(TIntPr(NI.GetId(), NI.GetInNId(e)), 0);
405  }
406  }
407  }
408  }
409  sigma.AddDat(NI.GetId(), 0);
410  d.AddDat(NI.GetId(), -1);
411  P.AddDat(NI.GetId(), TIntV());
412  delta.AddDat(NI.GetId(), 0);
413  }
414  // calc betweeness
415  for (int k=0; k < BtwNIdV.Len(); k++) {
416  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(BtwNIdV[k]);
417  // reset
418  for (int i = 0; i < sigma.Len(); i++) {
419  sigma[i]=0; d[i]=-1; delta[i]=0; P[i].Clr(false);
420  }
421  S.Clr(false);
422  Q.Clr(false);
423  sigma.AddDat(NI.GetId(), 1);
424  d.AddDat(NI.GetId(), 0);
425  Q.Push(NI.GetId());
426  while (! Q.Empty()) {
427  const int v = Q.Top(); Q.Pop();
428  const typename PGraph::TObj::TNodeI NI2 = Graph->GetNI(v);
429  S.Push(v);
430  const int VDat = d.GetDat(v);
431  // iterate over all outgoing edges
432  for (int e = 0; e < NI2.GetOutDeg(); e++) {
433  const int w = NI2.GetOutNId(e);
434  if (d.GetDat(w) < 0) { // find w for the first time
435  Q.Push(w);
436  d.AddDat(w, VDat+1);
437  }
438  //shortest path to w via v ?
439  if (d.GetDat(w) == VDat+1) {
440  sigma.AddDat(w) += sigma.GetDat(v);
441  P.GetDat(w).Add(v);
442  }
443  }
444  // if ignoring direction in directed networks, iterate over incoming edges
445  if (Graph->HasFlag(gfDirected) && !IsDir) {
446  for (int e = 0; e < NI2.GetInDeg(); e++) {
447  const int w = NI2.GetInNId(e);
448  // skip neighbors that are also outgoing
449  if (Graph->IsEdge(NI2.GetId(), w)) {
450  continue;
451  }
452  if (d.GetDat(w) < 0) { // find w for the first time
453  Q.Push(w);
454  d.AddDat(w, VDat+1);
455  }
456  //shortest path to w via v ?
457  if (d.GetDat(w) == VDat+1) {
458  sigma.AddDat(w) += sigma.GetDat(v);
459  P.GetDat(w).Add(v);
460  }
461  }
462  }
463  }
464  while (! S.Empty()) {
465  const int w = S.Top();
466  const double SigmaW = sigma.GetDat(w);
467  const double DeltaW = delta.GetDat(w);
468  const TIntV NIdV = P.GetDat(w);
469  S.Pop();
470  for (int i = 0; i < NIdV.Len(); i++) {
471  const int NId = NIdV[i];
472  const double c = (sigma.GetDat(NId)*1.0/SigmaW) * (1+DeltaW);
473  delta.AddDat(NId) += c;
474  if (DoEdgeCent) {
475  if (Graph->HasFlag(gfDirected) && IsDir) {
476  EdgeBtwH.AddDat(TIntPr(NId, w)) += c;
477  } else {
478  EdgeBtwH.AddDat(TIntPr(TMath::Mn(NId, w), TMath::Mx(NId, w))) += c;
479  }
480  }
481  }
482  if (DoNodeCent && w != NI.GetId()) {
483  NodeBtwH.AddDat(w) += delta.GetDat(w)/2.0; }
484  }
485  }
486 }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:838
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
TVec< TInt > TIntV
Definition: ds.h:1594
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
template<class PGraph >
double TSnap::GetBfsEffDiam ( const PGraph &  Graph,
const int &  NTestNodes,
const bool &  IsDir = false 
)

Returns the (approximation of the) Effective Diameter (90-th percentile of the distribution of shortest path lengths) of a graph (by performing BFS from NTestNodes random starting nodes).

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

Definition at line 415 of file bfsdfs.h.

415  {
416  int FullDiam;
417  double EffDiam;
418  GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
419  return EffDiam;
420 }
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...
Definition: bfsdfs.h:458
template<class PGraph >
double TSnap::GetBfsEffDiam ( const PGraph &  Graph,
const int &  NTestNodes,
const bool &  IsDir,
double &  EffDiamX,
int &  FullDiamX 
)

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

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

Definition at line 423 of file bfsdfs.h.

423  {
424  double AvgDiam;
425  EffDiam = -1; FullDiam = -1;
426  return GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam, AvgDiam);
427 }
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...
Definition: bfsdfs.h:458
template<class PGraph >
double TSnap::GetBfsEffDiam ( const PGraph &  Graph,
const int &  NTestNodes,
const bool &  IsDir,
double &  EffDiamX,
int &  FullDiamX,
double &  AvgSPLX 
)

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

Definition at line 430 of file bfsdfs.h.

430  {
431  EffDiam = -1; FullDiam = -1; AvgSPL = -1;
432  TIntFltH DistToCntH;
433  TBreathFS<PGraph> BFS(Graph);
434  // shotest paths
435  TIntV NodeIdV;
436  Graph->GetNIdV(NodeIdV); NodeIdV.Shuffle(TInt::Rnd);
437  for (int tries = 0; tries < TMath::Mn(NTestNodes, Graph->GetNodes()); tries++) {
438  const int NId = NodeIdV[tries];
439  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
440  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
441  DistToCntH.AddDat(BFS.NIdDistH[i]) += 1; }
442  }
443  TIntFltKdV DistNbrsPdfV;
444  double SumPathL=0, PathCnt=0;
445  for (int i = 0; i < DistToCntH.Len(); i++) {
446  DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
447  SumPathL += DistToCntH.GetKey(i) * DistToCntH[i];
448  PathCnt += DistToCntH[i];
449  }
450  DistNbrsPdfV.Sort();
451  EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
452  FullDiam = DistNbrsPdfV.Last().Key; // approximate full diameter (max shortest path length over the sampled nodes)
453  AvgSPL = SumPathL/PathCnt; // average shortest path length
454  return EffDiam;
455 }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
static const int Mx
Definition: dt.h:1139
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:381
static TRnd Rnd
Definition: dt.h:1143
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
double CalcEffDiamPdf(const TIntFltKdV &DistNbrsPdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) probability distribution functio...
Definition: anf.cpp:29
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1335
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
template<class PGraph >
double TSnap::GetBfsEffDiam ( const PGraph &  Graph,
const int &  NTestNodes,
const TIntV SubGraphNIdV,
const bool &  IsDir,
double &  EffDiamX,
int &  FullDiamX 
)

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

Definition at line 458 of file bfsdfs.h.

458  {
459  EffDiam = -1;
460  FullDiam = -1;
461 
462  TIntFltH DistToCntH;
463  TBreathFS<PGraph> BFS(Graph);
464  // shotest paths
465  TIntV NodeIdV(SubGraphNIdV); NodeIdV.Shuffle(TInt::Rnd);
466  TInt Dist;
467  for (int tries = 0; tries < TMath::Mn(NTestNodes, SubGraphNIdV.Len()); tries++) {
468  const int NId = NodeIdV[tries];
469  BFS.DoBfs(NId, true, ! IsDir, -1, TInt::Mx);
470  for (int i = 0; i < SubGraphNIdV.Len(); i++) {
471  if (BFS.NIdDistH.IsKeyGetDat(SubGraphNIdV[i], Dist)) {
472  DistToCntH.AddDat(Dist) += 1;
473  }
474  }
475  }
476  TIntFltKdV DistNbrsPdfV;
477  for (int i = 0; i < DistToCntH.Len(); i++) {
478  DistNbrsPdfV.Add(TIntFltKd(DistToCntH.GetKey(i), DistToCntH[i]));
479  }
480  DistNbrsPdfV.Sort();
481  EffDiam = TSnap::TSnapDetail::CalcEffDiamPdf(DistNbrsPdfV, 0.9); // effective diameter (90-th percentile)
482  FullDiam = DistNbrsPdfV.Last().Key; // approximate full diameter (max shortest path length over the sampled nodes)
483  return EffDiam; // average shortest path length
484 }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
static const int Mx
Definition: dt.h:1139
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:381
static TRnd Rnd
Definition: dt.h:1143
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
double CalcEffDiamPdf(const TIntFltKdV &DistNbrsPdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) probability distribution functio...
Definition: anf.cpp:29
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
Definition: dt.h:1134
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
template<class PGraph >
int TSnap::GetBfsFullDiam ( const PGraph &  Graph,
const int &  NTestNodes,
const bool &  IsDir = false 
)

Returns the (approximation of the) Diameter (maximum shortest path length) of a graph (by performing BFS from NTestNodes random starting nodes).

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

Definition at line 407 of file bfsdfs.h.

407  {
408  int FullDiam;
409  double EffDiam;
410  GetBfsEffDiam(Graph, NTestNodes, IsDir, EffDiam, FullDiam);
411  return FullDiam;
412 }
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...
Definition: bfsdfs.h:458
template<class PGraph >
PNGraph TSnap::GetBfsTree ( const PGraph &  Graph,
const int &  StartNId,
const bool &  FollowOut,
const bool &  FollowIn 
)

Returns a directed Breadth-First-Search tree rooted at StartNId.

Returns a directed graph where a parent points to its child node. Tree is created by following in-links (parameter FollowIn = true) and/or out-links (parameter FollowOut = true).

Definition at line 323 of file bfsdfs.h.

323  {
324  TBreathFS<PGraph> BFS(Graph);
325  BFS.DoBfs(StartNId, FollowOut, FollowIn, -1, TInt::Mx);
326  PNGraph Tree = TNGraph::New();
327  BFS.NIdDistH.SortByDat();
328  for (int i = 0; i < BFS.NIdDistH.Len(); i++) {
329  const int NId = BFS.NIdDistH.GetKey(i);
330  const int Dist = BFS.NIdDistH[i];
331  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
332  if (!Tree->IsNode(NId)) {
333  Tree->AddNode(NId);
334  }
335  if (FollowOut) {
336  for (int e = 0; e < NI.GetInDeg(); e++) {
337  const int Prev = NI.GetInNId(e);
338  if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
339  Tree->AddEdge(Prev, NId); }
340  }
341  }
342  if (FollowIn) {
343  for (int e = 0; e < NI.GetOutDeg(); e++) {
344  const int Prev = NI.GetOutNId(e);
345  if (Tree->IsNode(Prev) && BFS.NIdDistH.GetDat(Prev)==Dist-1) {
346  Tree->AddEdge(Prev, NId); }
347  }
348  }
349  }
350  return Tree;
351 }
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
static const int Mx
Definition: dt.h:1139
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:542
void TSnap::GetBiCon ( const PUNGraph Graph,
TCnComV BiCnComV 
)

Returns all bi-connected components of a Graph.

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

Definition at line 42 of file cncom.cpp.

42  {
43  TBiConVisitor Visitor(Graph->GetNodes());
44  TCnCom::GetDfsVisitor(Graph, Visitor);
45  BiCnComV = Visitor.CnComV;
46 }
static void GetDfsVisitor(const PGraph &Graph, TVisitor &Visitor)
Definition: cncom.h:124
Biconnected componetns Depth-First-Search visitor class.
Definition: cncom.h:195
void TSnap::GetBiConSzCnt ( const PUNGraph Graph,
TIntPrV SzCntV 
)

Returns a distribution of bi-connected component sizes.

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

Definition at line 31 of file cncom.cpp.

31  {
32  TCnComV BiCnComV;
33  GetBiCon(Graph, BiCnComV);
34  TIntH SzCntH;
35  for (int c =0; c < BiCnComV.Len(); c++) {
36  SzCntH.AddDat(BiCnComV[c].Len()) += 1;
37  }
38  SzCntH.GetKeyDatPrV(SzCntV);
39  SzCntV.Sort();
40 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void GetBiCon(const PUNGraph &Graph, TCnComV &BiCnComV)
Returns all bi-connected components of a Graph.
Definition: cncom.cpp:42
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
template<class PGraph >
double TSnap::GetClosenessCentr ( const PGraph &  Graph,
const int &  NId,
const bool &  Normalized = true,
const bool &  IsDir = false 
)

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

Definition at line 161 of file centr.h.

161  {
162  const double Farness = GetFarnessCentr<PGraph> (Graph, NId, Normalized, IsDir);
163  if (Farness != 0.0) { return 1.0/Farness; }
164  else { return 0.0; }
165  return 0.0;
166 }
template<class PGraph >
double TSnap::GetClosenessCentrMP ( const PGraph &  Graph,
const int &  NId,
const bool &  Normalized = true,
const bool &  IsDir = false 
)

Definition at line 169 of file centr.h.

169  {
170  const double Farness = GetFarnessCentrMP<PGraph> (Graph, NId, Normalized, IsDir);
171  if (Farness != 0.0) { return 1.0/Farness; }
172  else { return 0.0; }
173  return 0.0;
174 }
template<class PGraph >
double TSnap::GetClustCf ( const PGraph &  Graph,
int  SampleNodes = -1 
)

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

Considers the graph as undirected.

Definition at line 113 of file triad.h.

113  {
114  TIntTrV NIdCOTriadV;
115  GetTriads(Graph, NIdCOTriadV, SampleNodes);
116  if (NIdCOTriadV.Empty()) { return 0.0; }
117  double SumCcf = 0.0;
118  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
119  const double OpenCnt = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
120  if (OpenCnt > 0) {
121  SumCcf += NIdCOTriadV[i].Val2() / OpenCnt; }
122  }
123  IAssert(SumCcf>=0);
124  return SumCcf / double(NIdCOTriadV.Len());
125 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
void GetTriads(const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes=-1)
Computes the number of open and close triads for every node of the network.
Definition: triad.h:274
template<class PGraph >
double TSnap::GetClustCf ( const PGraph &  Graph,
TFltPrV DegToCCfV,
int  SampleNodes = -1 
)

Computes the distribution of average clustering coefficient.

Considers the graph as undirected.

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

Definition at line 127 of file triad.h.

127  {
128  TIntTrV NIdCOTriadV;
129  GetTriads(Graph, NIdCOTriadV, SampleNodes);
130  THash<TInt, TFltPr> DegSumCnt;
131  double SumCcf = 0.0;
132  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
133  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
134  const double Ccf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
135  TFltPr& SumCnt = DegSumCnt.AddDat(Graph->GetNI(NIdCOTriadV[i].Val1).GetDeg());
136  SumCnt.Val1 += Ccf;
137  SumCnt.Val2 += 1;
138  SumCcf += Ccf;
139  }
140  // get average clustering coefficient for each degree
141  DegToCCfV.Gen(DegSumCnt.Len(), 0);
142  for (int d = 0; d < DegSumCnt.Len(); d++) {
143  DegToCCfV.Add(TFltPr(DegSumCnt.GetKey(d).Val, double(DegSumCnt[d].Val1()/DegSumCnt[d].Val2())));
144  }
145  DegToCCfV.Sort();
146  return SumCcf / double(NIdCOTriadV.Len());
147 }
int Val
Definition: dt.h:1136
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
void GetTriads(const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes=-1)
Computes the number of open and close triads for every node of the network.
Definition: triad.h:274
Definition: ds.h:32
Definition: hash.h:97
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
template<class PGraph >
double TSnap::GetClustCf ( 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.

Considers the graph as undirected.

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

Definition at line 150 of file triad.h.

150  {
151  TIntTrV NIdCOTriadV;
152  GetTriads(Graph, NIdCOTriadV, SampleNodes);
153  THash<TInt, TFltPr> DegSumCnt;
154  double SumCcf = 0.0;
155  int64 closedTriads = 0;
156  int64 openTriads = 0;
157  for (int i = 0; i < NIdCOTriadV.Len(); i++) {
158  const int D = NIdCOTriadV[i].Val2()+NIdCOTriadV[i].Val3();
159  const double Ccf = D!=0 ? NIdCOTriadV[i].Val2() / double(D) : 0.0;
160  closedTriads += NIdCOTriadV[i].Val2;
161  openTriads += NIdCOTriadV[i].Val3;
162  TFltPr& SumCnt = DegSumCnt.AddDat(Graph->GetNI(NIdCOTriadV[i].Val1).GetDeg());
163  SumCnt.Val1 += Ccf;
164  SumCnt.Val2 += 1;
165  SumCcf += Ccf;
166  }
167  // get average clustering coefficient for each degree
168  DegToCCfV.Gen(DegSumCnt.Len(), 0);
169  for (int d = 0; d < DegSumCnt.Len(); d++) {
170  DegToCCfV.Add(TFltPr(DegSumCnt.GetKey(d).Val, DegSumCnt[d].Val1()/DegSumCnt[d].Val2()));
171  }
172  //if(closedTriads/3 > (uint64) TInt::Mx) { WarnNotify(TStr::Fmt("[%s line %d] %g closed triads.\n", __FILE__, __LINE__, float(closedTriads/3)).CStr()); }
173  //if(openTriads > (uint64) TInt::Mx) { WarnNotify(TStr::Fmt("[%s line %d] %g open triads.\n", __FILE__, __LINE__, float(openTriads/3)).CStr()); }
174  ClosedTriads = closedTriads/int64(3); // each triad is counted 3 times
175  OpenTriads = openTriads;
176  DegToCCfV.Sort();
177  return SumCcf / double(NIdCOTriadV.Len());
178 }
int Val
Definition: dt.h:1136
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
void GetTriads(const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes=-1)
Computes the number of open and close triads for every node of the network.
Definition: triad.h:274
Definition: ds.h:32
long long int64
Definition: bd.h:27
Definition: hash.h:97
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
template<class PGraph >
int TSnap::GetCmnNbrs ( const PGraph &  Graph,
const int &  NId1,
const int &  NId2 
)

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

Definition at line 659 of file triad.h.

659  {
660  TIntV NbrV;
661  return GetCmnNbrs(Graph, NId1, NId2, NbrV);
662 }
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.
Definition: triad.h:666
template<class PGraph >
int TSnap::GetCmnNbrs ( const PGraph &  Graph,
const int &  NId1,
const int &  NId2,
TIntV NbrV 
)

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

Definition at line 666 of file triad.h<