SNAP Library 6.0, Developer Reference
2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
Main namespace for all the Snap global entities. More...
Namespaces | |
TSnapDetail | |
Functions | |
template<class PGraph > | |
int | CntInDegNodes (const PGraph &Graph, const int &NodeInDeg) |
Returns the number of nodes with in-degree NodeInDeg. More... | |
template<class PGraph > | |
int | CntOutDegNodes (const PGraph &Graph, const int &NodeOutDeg) |
Returns the number of nodes with out-degree NodeOutDeg. More... | |
template<class PGraph > | |
int | CntDegNodes (const PGraph &Graph, const int &NodeDeg) |
Returns the number of nodes with degree NodeDeg. More... | |
template<class PGraph > | |
int | CntNonZNodes (const PGraph &Graph) |
Returns the number of nodes with degree greater than 0. More... | |
template<class PGraph > | |
int | CntEdgesToSet (const PGraph &Graph, const int &NId, const TIntSet &NodeSet) |
Returns the number of nodes in NodeSet that have an edge to the node NId. More... | |
template<class PGraph > | |
int | GetMxDegNId (const PGraph &Graph) |
Returns a randomly chosen node from all the nodes with the maximum degree. More... | |
template<class PGraph > | |
int | GetMxInDegNId (const PGraph &Graph) |
Returns a randomly chosen node from all the nodes with the maximum in-degree. More... | |
template<class PGraph > | |
int | GetMxOutDegNId (const PGraph &Graph) |
Returns a randomly chosen node from all the nodes with the maximum out-degree. More... | |
template<class PGraph > | |
void | GetInDegCnt (const PGraph &Graph, TIntPrV &DegToCntV) |
Returns an in-degree histogram: a set of pairs (in-degree, number of nodes of such in-degree) More... | |
template<class PGraph > | |
void | GetInDegCnt (const PGraph &Graph, TFltPrV &DegToCntV) |
Returns an in-degree histogram: a set of pairs (in-degree, number of nodes of such in-degree) More... | |
template<class PGraph > | |
void | GetOutDegCnt (const PGraph &Graph, TIntPrV &DegToCntV) |
Returns an out-degree histogram: a set of pairs (out-degree, number of nodes of such out-degree) More... | |
template<class PGraph > | |
void | GetOutDegCnt (const PGraph &Graph, TFltPrV &DegToCntV) |
Returns an out-degree histogram: a set of pairs (out-degree, number of nodes of such out-degree) More... | |
template<class PGraph > | |
void | GetDegCnt (const PGraph &Graph, TIntPrV &DegToCntV) |
Returns a degree histogram: a set of pairs (degree, number of nodes of such degree) More... | |
template<class PGraph > | |
void | GetDegCnt (const PGraph &Graph, TFltPrV &DegToCntV) |
Returns a degree histogram: a set of pairs (degree, number of nodes of such degree) More... | |
template<class PGraph > | |
void | GetDegSeqV (const PGraph &Graph, TIntV &DegV) |
Returns a degree sequence vector. More... | |
template<class PGraph > | |
void | GetDegSeqV (const PGraph &Graph, TIntV &InDegV, TIntV &OutDegV) |
Returns an in- and out-degree sequence vectors. More... | |
template<class PGraph > | |
void | GetNodeInDegV (const PGraph &Graph, TIntPrV &NIdInDegV) |
Returns a vector of pairs (node id, node in-degree) More... | |
template<class PGraph > | |
void | GetNodeOutDegV (const PGraph &Graph, TIntPrV &NIdOutDegV) |
Returns a vector of pairs (node id, node out-degree) More... | |
template<class PGraph > | |
int | CntUniqUndirEdges (const PGraph &Graph) |
Counts unique undirected edges in the graph Graph . Nodes (u,v) (where u!=v ) are connected via an undirected edge if there exists an edge in either direction (u,v) or (v,u) . More... | |
template<class PGraph > | |
int | CntUniqDirEdges (const PGraph &Graph) |
Counts unique directed edges in the graph Graph . Nodes (u,v) (where u!=v ) are connected via a directed edge if there exists a directed edge from node u to node v . More... | |
template<class PGraph > | |
int | CntUniqBiDirEdges (const PGraph &Graph) |
Counts unique bidirectional edges in the graph Graph . Edge is bidirectional if there exist directed edges in both directions: (u,v) and (v,u) More... | |
template<class PGraph > | |
int | CntSelfEdges (const PGraph &Graph) |
Counts the number of self-edges in a graph. Edge (u,u) is a self-edge. More... | |
template<class PGraph > | |
PGraph | GetUnDir (const PGraph &Graph) |
Returs an undirected version of the graph. For every edge (u,v) an edge (v,u) is added (if it does not yet exist). More... | |
template<class PGraph > | |
void | MakeUnDir (const PGraph &Graph) |
Makes the graph undirected. For every edge (u,v) an edge (v,u) is added (if it does not yet exist). More... | |
template<class PGraph > | |
void | AddSelfEdges (const PGraph &Graph) |
Adds a self-edge to every node in the graph. More... | |
template<class PGraph > | |
void | DelSelfEdges (const PGraph &Graph) |
Removes all the self-edges from the graph. More... | |
template<class PGraph > | |
void | DelNodes (PGraph &Graph, const TIntV &NIdV) |
Removes nodes with ids stored in NIdV from the graph. More... | |
template<class PGraph > | |
void | DelZeroDegNodes (PGraph &Graph) |
Removes all the zero-degree nodes, that isolated nodes, from the graph. More... | |
template<class PGraph > | |
void | DelDegKNodes (PGraph &Graph, const int &OutDegK, const int &InDegK) |
Removes all the node of out-degree OutDegK and all the nodes of in-degree InDegK from the graph. More... | |
template<class PGraph > | |
bool | IsTree (const PGraph &Graph, int &RootNIdX) |
template<class PGraph > | |
int | GetTreeRootNId (const PGraph &Graph) |
template<class PGraph > | |
void | GetTreeSig (const PGraph &Graph, const int &RootNId, TIntV &Sig) |
template<class PGraph > | |
void | GetTreeSig (const PGraph &Graph, const int &RootNId, TIntV &Sig, TIntPrV &NodeMap) |
template<class PGraph > | |
void | GetAnf (const PGraph &Graph, const int &SrcNId, TIntFltKdV &DistNbrsV, const int &MxDist, const bool &IsDir, const int &NApprox=32) |
template<class PGraph > | |
void | GetAnf (const PGraph &Graph, TIntFltKdV &DistNbrsV, const int &MxDist, const bool &IsDir, const int &NApprox=32) |
template<class PGraph > | |
double | GetAnfEffDiam (const PGraph &Graph, const bool &IsDir, const double &Percentile, const int &NApprox) |
template<class PGraph > | |
double | GetAnfEffDiam (const PGraph &Graph, const int NRuns=1, int NApprox=-1) |
template<class PGraph > | |
void | TestAnf () |
template<class PGraph > | |
PNGraph | GetBfsTree (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn) |
Returns a directed Breadth-First-Search tree rooted at StartNId. More... | |
template<class PGraph > | |
int | GetSubTreeSz (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, int &TreeSzX, int &TreeDepthX) |
Returns the BFS tree size (number of nodes) and depth (number of levels) by following in-links (parameter FollowIn = true) and/or out-links (parameter FollowOut = true) of node StartNId. More... | |
template<class PGraph > | |
int | GetNodesAtHop (const PGraph &Graph, const int &StartNId, const int &Hop, TIntV &NIdV, const bool &IsDir=false) |
Finds IDs of all nodes that are at distance Hop from node StartNId. More... | |
template<class PGraph > | |
int | GetNodesAtHops (const PGraph &Graph, const int &StartNId, TIntPrV &HopCntV, const bool &IsDir=false) |
Returns the number of nodes at each hop distance from the starting node StartNId. More... | |
template<class PGraph > | |
int | GetShortPath (const PGraph &Graph, const int &SrcNId, const int &DstNId, const bool &IsDir=false) |
Returns the length of the shortest path from node SrcNId to node DstNId. More... | |
template<class PGraph > | |
int | GetShortPath (const PGraph &Graph, const int &SrcNId, TIntH &NIdToDistH, const bool &IsDir=false, const int &MaxDist=TInt::Mx) |
Returns the length of the shortest path from node SrcNId to all other nodes in the network. More... | |
template<class PGraph > | |
int | GetBfsFullDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false) |
Returns the (approximation of the) Diameter (maximum shortest path length) of a graph (by performing BFS from NTestNodes random starting nodes). More... | |
template<class PGraph > | |
double | GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false) |
Returns the (approximation of the) Effective Diameter (90-th percentile of the distribution of shortest path lengths) of a graph (by performing BFS from NTestNodes random starting nodes). More... | |
template<class PGraph > | |
double | GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir, double &EffDiamX, int &FullDiamX) |
Returns the (approximation of the) Effective Diameter and the Diameter of a graph (by performing BFS from NTestNodes random starting nodes). More... | |
template<class PGraph > | |
double | GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const bool &IsDir, double &EffDiamX, int &FullDiamX, double &AvgSPLX) |
Returns the (approximation of the) Effective Diameter, the Diameter and the Average Shortest Path length in a graph (by performing BFS from NTestNodes random starting nodes). More... | |
template<class PGraph > | |
double | GetBfsEffDiamAll (const PGraph &Graph, const int &NTestNodes, const bool &IsDir, double &EffDiamX, int &FullDiamX, double &AvgSPLX) |
Returns the (approximation of the) Effective Diameter, the Diameter and the Average Shortest Path length in a graph (by performing BFS from NTestNodes random starting nodes). More... | |
template<class PGraph > | |
double | GetBfsEffDiam (const PGraph &Graph, const int &NTestNodes, const TIntV &SubGraphNIdV, const bool &IsDir, double &EffDiamX, int &FullDiamX) |
Use the whole graph (all edges) to measure the shortest path lengths but only report the path lengths between nodes in the SubGraphNIdV. More... | |
template<class PGraph > | |
int | GetShortestDistances (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, TIntV &ShortestDists) |
template<class PGraph > | |
int | GetShortestDistancesMP2 (const PGraph &Graph, const int &StartNId, const bool &FollowOut, const bool &FollowIn, TIntV &ShortestDists) |
PNGraph | CascGraphSource (PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W) |
Takes as input the column names of the PTable P as C1 , C2 ,C3 and C4 and returns a directed graph of W-adjacent events. For graph generation events are sorted by C1 . More... | |
PNGraph | CascGraphTime (PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W) |
Takes as input the column names of the PTable P as C1 , C2 ,C3 and C4 and returns a directed graph of W-adjacent events. For graph generation events are sorted by C3 . More... | |
PNGraph | CascGraph (PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, const TInt W, bool SortParam=true) |
Takes as input the column names of the PTable P as C1 , C2 , C3 and C4 and returns a directed graph of W-adjacent events. By default calls CascGraphSource. Toggle SortParam to use CascGraphTime. More... | |
void | CascFind (PNGraph Graph, PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, TVec< TIntV > &TopCascVV, bool Print=false) |
Takes as input a directed graph and returns all the top cascades in TopCascVV . More... | |
void | CascFindMP (PNGraph Graph, PTable P, const TStr C1, const TStr C2, const TStr C3, const TStr C4, TVec< TIntV > &TopCascVV) |
Parallel implementaion of CascFind takes as input a directed graph and returns all the top cascades in TopCascVV . More... | |
double | GetDegreeCentr (const PUNGraph &Graph, const int &NId) |
void | GetEigenVectorCentr (const PUNGraph &Graph, TIntFltH &NIdEigenH, const double &Eps, const int &MaxIter) |
double | GetGroupDegreeCentr (const PUNGraph &Graph, const PUNGraph &Group) |
double | GetGroupDegreeCentr0 (const PUNGraph &Graph, const TIntH &GroupNodes) |
double | GetGroupDegreeCentr (const PUNGraph &Graph, const TIntH &GroupNodes) |
double | GetGroupFarnessCentr (const PUNGraph &Graph, const TIntH &GroupNodes) |
PUNGraph * | AllGraphsWithNNodes (int n) |
TIntH * | AllCombinationsMN (int m, int n) |
double | GetGroupClosenessCentr (const PUNGraph &Graph, const TIntH &GroupNodes) |
TIntH | MaxCPGreedyBetter (const PUNGraph &Graph, const int k) |
Returns centrality Maximum k group. More... | |
TIntH | MaxCPGreedyBetter1 (const PUNGraph &Graph, const int k) |
Returns centrality Maximum k group. More... | |
TIntH | MaxCPGreedyBetter2 (const PUNGraph &Graph, const int k) |
Returns centrality Maximum k group. More... | |
TIntH | MaxCPGreedyBetter3 (const PUNGraph &Graph, const int k) |
Returns centrality Maximum k group. More... | |
int | GetWeightedPageRank (const PNEANet Graph, TIntFltH &PRankH, const TStr &Attr, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100) |
Weighted PageRank (TODO: Use template) More... | |
int | GetWeightedPageRankMP (const PNEANet Graph, TIntFltH &PRankH, const TStr &Attr, const double &C, const double &Eps, const int &MaxIter) |
TIntFltH | EventImportance (const PNGraph &Graph, const int k) |
Event importance. More... | |
TIntFltH | EventImportance1 (const PNGraph &Graph, const int k) |
int | Intersect (TUNGraph::TNodeI Node, TIntH NNodes) |
Intersect. More... | |
int | Intersect (TUNGraph::TNodeI Node, TStr NNodes) |
Intersect. More... | |
int | Intersect (TUNGraph::TNodeI Node, int *NNodes, int NNodes_br) |
Intersect. More... | |
int | Intersect1 (TUNGraph::TNodeI Node, TStr NNodes) |
TIntH | LoadNodeList (TStr InFNmNodes) |
int | findMinimum (TIntV &Frontier, TIntFltH &NIdDistH) |
int | GetWeightedShortestPath (const PNEANet Graph, const int &SrcNId, TIntFltH &NIdDistH, const TFltV &Attr) |
double | GetWeightedFarnessCentr (const PNEANet Graph, const int &NId, const TFltV &Attr, const bool &Normalized, const bool &IsDir) |
double | GetWeightedClosenessCentr (const PNEANet Graph, const int &NId, const TFltV &Attr, const bool &Normalized, const bool &IsDir) |
void | GetWeightedBetweennessCentr (const PNEANet Graph, const TIntV &BtwNIdV, TIntFltH &NodeBtwH, const bool &DoNodeCent, TIntPrFltH &EdgeBtwH, const bool &DoEdgeCent, const TFltV &Attr, const bool &IsDir) |
Computes (approximate) weighted Beetweenness Centrality of all nodes and all edges of the network. More... | |
void | GetWeightedBetweennessCentr (const PNEANet Graph, TIntFltH &NodeBtwH, TIntPrFltH &EdgeBtwH, const TFltV &Attr, const double &NodeFrac, const bool &IsDir) |
void | GetWeightedBetweennessCentr (const PNEANet Graph, TIntFltH &NodeBtwH, const TFltV &Attr, const double &NodeFrac, const bool &IsDir) |
void | GetWeightedBetweennessCentr (const PNEANet Graph, TIntPrFltH &EdgeBtwH, const TFltV &Attr, const double &NodeFrac, const bool &IsDir) |
TTableIterator | GetMapPageRank (const TVec< PNEANet > &GraphSeq, TTableContext *Context, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100) |
Gets sequence of PageRank tables from given GraphSeq . More... | |
TTableIterator | GetMapHitsIterator (const TVec< PNEANet > &GraphSeq, TTableContext *Context, const int &MaxIter=20) |
Gets sequence of Hits tables from given GraphSeq . More... | |
template<class PGraph > | |
double | GetFarnessCentr (const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false) |
template<class PGraph > | |
double | GetFarnessCentrMP (const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false) |
template<class PGraph > | |
double | GetClosenessCentr (const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false) |
template<class PGraph > | |
double | GetClosenessCentrMP (const PGraph &Graph, const int &NId, const bool &Normalized=true, const bool &IsDir=false) |
template<class PGraph > | |
int | GetNodeEcc (const PGraph &Graph, const int &NId, const bool &IsDir=false) |
template<class PGraph > | |
void | GetBetweennessCentr (const PGraph &Graph, TIntFltH &NIdBtwH, const double &NodeFrac=1.0, const bool &IsDir=false) |
template<class PGraph > | |
void | GetBetweennessCentr (const PGraph &Graph, TIntPrFltH &EdgeBtwH, const double &NodeFrac=1.0, const bool &IsDir=false) |
template<class PGraph > | |
void | GetBetweennessCentr (const PGraph &Graph, TIntFltH &NIdBtwH, TIntPrFltH &EdgeBtwH, const double &NodeFrac=1.0, const bool &IsDir=false) |
template<class PGraph > | |
void | GetBetweennessCentr (const PGraph &Graph, const TIntV &BtwNIdV, TIntFltH &NodeBtwH, const bool &DoNodeCent, TIntPrFltH &EdgeBtwH, const bool &DoEdgeCent, const bool &IsDir) |
template<class PGraph > | |
void | GetPageRank (const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100) |
template<class PGraph > | |
void | GetPageRank_v1 (const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100) |
template<class PGraph > | |
void | GetPageRankMP (const PGraph &Graph, TIntFltH &PRankH, const double &C=0.85, const double &Eps=1e-4, const int &MaxIter=100) |
template<class PGraph > | |
void | GetHits (const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20) |
template<class PGraph > | |
void | GetHitsMP (const PGraph &Graph, TIntFltH &NIdHubH, TIntFltH &NIdAuthH, const int &MaxIter=20) |
template<class PGraph > | |
void | MapPageRank (const TVec< PGraph > &GraphSeq, TVec< PTable > &TableSeq, TTableContext *Context, const double &C, const double &Eps, const int &MaxIter) |
Gets sequence of PageRank tables from given GraphSeq into TableSeq . More... | |
template<class PGraph > | |
void | MapHits (const TVec< PGraph > &GraphSeq, TVec< PTable > &TableSeq, TTableContext *Context, const int &MaxIter) |
Gets sequence of Hits tables from given GraphSeq into TableSeq . More... | |
double | CommunityGirvanNewman (PUNGraph &Graph, TCnComV &CmtyV) |
double | Infomap (PUNGraph &Graph, TCnComV &CmtyV) |
double | InfomapOnline (PUNGraph &Graph, int n1, int n2, TIntFltH &PAlpha, double &SumPAlphaLogPAlpha, TIntFltH &Qi, TIntH &Module, int &Br, TCnComV &CmtyV) |
void | CmtyEvolutionFileBatchV (TStr InFNm, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges, double alpha, double beta, int CmtyAlg) |
void | CmtyEvolutionFileBatch (TStr InFNm, TIntIntHH &sizesCont, TIntIntHH &cCont, TIntIntVH &edges, double alpha, double beta, int CmtyAlg) |
void | CmtyEvolutionJson (TStr &Json, TIntIntVH &sizesContV, TIntIntVH &cContV, TIntIntVH &edges) |
TStr | CmtyTest (TStr InFNm, int CmtyAlg) |
void | ReebSimplify (PNGraph &Graph, TIntH &t, int e, PNGraph &gFinal, TIntH &tFinal, bool collapse) |
void | ReebRefine (PNGraph &Graph, TIntH &t, int e, PNGraph &gFinal, TIntH &tFinal, bool collapse) |
double | CommunityCNM (const PUNGraph &Graph, TCnComV &CmtyV) |
template<typename PGraph > | |
double | GetModularity (const PGraph &G, const TIntV &NIdV, int GEdges=-1) |
template<typename PGraph > | |
double | GetModularity (const PGraph &G, const TCnComV &CmtyV, int GEdges=-1) |
template<typename PGraph > | |
void | GetEdgesInOut (const PGraph &Graph, const TIntV &NIdV, int &EdgesInX, int &EdgesOutX) |
void | GetBiConSzCnt (const PUNGraph &Graph, TIntPrV &SzCntV) |
Returns a distribution of bi-connected component sizes. More... | |
void | GetBiCon (const PUNGraph &Graph, TCnComV &BiCnComV) |
Returns all bi-connected components of a Graph. More... | |
void | GetArtPoints (const PUNGraph &Graph, TIntV &ArtNIdV) |
Returns articulation points of a Graph. More... | |
void | GetEdgeBridges (const PUNGraph &Graph, TIntPrV &EdgeV) |
Returns bridge edges of a Graph. More... | |
void | Get1CnComSzCnt (const PUNGraph &Graph, TIntPrV &SzCntV) |
Distribution of sizes of 1-components, maximal number of components that can be disconnected from the Graph by removing a single edge. More... | |
void | Get1CnCom (const PUNGraph &Graph, TCnComV &Cn1ComV) |
Returns 1-components: maximal connected components of that can be disconnected from the Graph by removing a single edge. More... | |
PUNGraph | GetMxBiCon (const PUNGraph &Graph, const bool &RenumberNodes=false) |
Returns a graph representing the largest bi-connected component on an undirected Graph. More... | |
template<class PGraph > | |
void | GetNodeWcc (const PGraph &Graph, const int &NId, TIntV &CnCom) |
Returns (via output parameter CnCom) all nodes that are in the same connected component as node NId. More... | |
template<class PGraph > | |
bool | IsConnected (const PGraph &Graph) |
Tests whether the Graph is (weakly) connected. More... | |
template<class PGraph > | |
bool | IsWeaklyConn (const PGraph &Graph) |
Tests whether the Graph is weakly connected. More... | |
template<class PGraph > | |
void | GetWccSzCnt (const PGraph &Graph, TIntPrV &WccSzCnt) |
Returns a distribution of weakly connected component sizes. More... | |
template<class PGraph > | |
void | GetWccs (const PGraph &Graph, TCnComV &CnComV) |
Returns all weakly connected components in a Graph. More... | |
template<class PGraph > | |
void | GetSccSzCnt (const PGraph &Graph, TIntPrV &SccSzCnt) |
Returns a distribution of strongly connected component sizes. More... | |
template<class PGraph > | |
void | GetSccs (const PGraph &Graph, TCnComV &CnComV) |
Returns all strongly connected components in a Graph. More... | |
template<class PGraph > | |
double | GetMxWccSz (const PGraph &Graph) |
Returns the fraction of nodes in the largest weakly connected component of a Graph. More... | |
template<class PGraph > | |
double | GetMxSccSz (const PGraph &Graph) |
Returns the fraction of nodes in the largest strongly connected component of a Graph. More... | |
template<class PGraph > | |
PGraph | GetMxWcc (const PGraph &Graph) |
Returns a graph representing the largest weakly connected component on an input Graph. More... | |
template<class PGraph > | |
PGraph | GetMxScc (const PGraph &Graph) |
Returns a graph representing the largest strongly connected component on an input Graph. More... | |
template<class PGraph > | |
PGraph | GetMxBiCon (const PGraph &Graph) |
Returns a graph representing the largest bi-connected component on an input Graph. More... | |
int | LoadModeNetToNet (PMMNet Graph, const TStr &Name, PTable Table, const TStr &NCol, TStrV &NodeAttrV) |
Loads a mode, with name Name, into the PMMNet from the TTable. NCol specifies the node id column and NodeAttrV the node attributes. More... | |
int | LoadMode (TModeNet &Graph, PTable Table, const TStr &NCol, TStrV &NodeAttrV) |
Loads the nodes specified in column NCol from the TTable with the attributes specified in NodeAttrV. More... | |
int | LoadCrossNetToNet (PMMNet Graph, const TStr &Mode1, const TStr &Mode2, const TStr &CrossName, PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV) |
Loads a crossnet from Mode1 to Mode2, with name CrossName, from the provided TTable. EdgeAttrV specifies edge attributes. More... | |
int | LoadCrossNet (TCrossNet &Graph, PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV) |
Loads the edges from the TTable and EdgeAttrV specifies columns containing edge attributes. More... | |
template<class PGraph > | |
PGraph | ToGraph (PTable Table, const TStr &SrcCol, const TStr &DstCol, TAttrAggr AggrPolicy) |
Sequentially converts the table into a graph with links from nodes in SrcCol to those in DstCol . More... | |
template<class PGraph > | |
PGraph | ToNetwork (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &SrcAttrV, TStrV &DstAttrV, TStrV &EdgeAttrV, TAttrAggr AggrPolicy) |
Converts the Table into a graph with edges from SrcCol to DstCol , and attribute vector defined by the arguments. More... | |
template<class PGraph > | |
PGraph | ToNetwork (PTable Table, const TStr &SrcCol, const TStr &DstCol, TAttrAggr AggrPolicy) |
Calls ToNetwork with an empty attribute vector. Convenience wrapper. More... | |
template<class PGraphMP > | |
PGraphMP | ToGraphMP (PTable Table, const TStr &SrcCol, const TStr &DstCol) |
Performs table to graph conversion in parallel using the sort-first algorithm. This is the recommended method to use. More... | |
template<class PGraphMP > | |
PGraphMP | ToGraphMP3 (PTable Table, const TStr &SrcCol, const TStr &DstCol) |
Performs table to graph conversion in parallel. Uses the hash-first method, which is less optimal, use ToGraphMP instead. More... | |
template<class PGraphMP > | |
PGraphMP | ToNetworkMP (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &SrcAttrV, TStrV &DstAttrV, TStrV &EdgeAttrV, TAttrAggr AggrPolicy) |
Does Table to Network conversion in parallel using the sort-first algorithm. This is the recommended method to use. More... | |
template<class PGraphMP > | |
PGraphMP | ToNetworkMP (PTable Table, const TStr &SrcCol, const TStr &DstCol, TAttrAggr AggrPolicy) |
Calls ToNetworkMP with empty attribute vector. Convenience wrapper. More... | |
template<class PGraphMP > | |
PGraphMP | ToNetworkMP2 (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &SrcAttrV, TStrV &DstAttrV, TStrV &EdgeAttrV, TAttrAggr AggrPolicy) |
Implements table to network conversion in parallel. Not the recommended algorithm, using ToNetworkMP instead. More... | |
template<class PGraphMP > | |
PGraphMP | ToNetworkMP2 (PTable Table, const TStr &SrcCol, const TStr &DstCol, TAttrAggr AggrPolicy) |
Calls ToNetworkMP2 with an empty attribute vector. Convenience wrapper. More... | |
template<class PGraph > | |
PGraph | ToNetwork (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV, TAttrAggr AggrPolicy) |
Converts table to a network sequentially. Use if network has only edge attributes. More... | |
template<class PGraphMP > | |
PGraphMP | ToNetworkMP (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV, TAttrAggr AggrPolicy) |
Converts table to network in parallel. Use if network has only edge attributes. More... | |
template<class PGraph > | |
PGraph | ToNetwork (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV, PTable NodeTable, const TStr &NodeCol, TStrV &NodeAttrV, TAttrAggr AggrPolicy) |
Converts table to network sequentially. Takes edges from Table and nodes explicitly from NodeCol in NodeTable , with attribute vectors passed as columns in corresponding tables. More... | |
template<class PGraphMP > | |
PGraphMP | ToNetworkMP (PTable Table, const TStr &SrcCol, const TStr &DstCol, TStrV &EdgeAttrV, PTable NodeTable, const TStr &NodeCol, TStrV &NodeAttrV, TAttrAggr AggrPolicy) |
Converts table to network in parallel. Takes edges from Table and nodes explicitly from NodeCol in NodeTable , with attribute vectors passed as columns in corresponding tables. More... | |
int | FastCorePeriphery (PUNGraph &Graph, TIntIntH &out) |
int | FastCorePeripheryGC (PUNGraph &Graph, TIntIntH &out) |
double | BorgattiEverettMeasure (PUNGraph &Graph, TIntIntH &out, double coresize, int type) |
double | PearsonCorrelation (PUNGraph &Graph, TIntIntH &out, int coresize) |
int | IntFlowBiDBFS (const PNEANet &Net, const int &CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, const int &SrcNId, const int &SnkNId) |
int | FindAugV (const PNEANet &Net, const int &CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, TIntV &MidToSrcAugV, TIntV &MidToSnkAugV, const int &SrcNId, const int &SnkNId) |
Returns the amount the flow can be augmented over the paths, 0 if no path can be found. More... | |
int | GetMaxFlowIntEK (PNEANet &Net, const int &SrcNId, const int &SnkNId) |
Returns the maximum integer valued flow in the network Net from source SrcNId to sink SnkNId . More... | |
void | PushToOutNbr (TPRManager &PRM, const int &NId, const int &OutNId, const int &EId) |
Pushes flow from a node NId to a neighbor OutNId over edge EId . More... | |
void | PushToInNbr (TPRManager &PRM, const int &NId, const int &InNId, const int &EId) |
Returns flow from a node NId to a neighbor InNId over edge EId . More... | |
void | Relabel (TPRManager &PRM, const int &NId, const TNEANet::TNodeI &NI) |
Increases the label of a node NId to allow valid pushes to some neighbor. More... | |
int | PushRelabel (TPRManager &PRM, const int &NId, const TNEANet::TNodeI &NI) |
Returns the ID of the neighbor that NId pushes to, -1 if no push was made. More... | |
void | GlobalRelabel (PNEANet &Net, TPRManager &PRM, const int &SrcNId, const int &SnkNId) |
Implements the Global Relabeling heuristic. More... | |
int | GetMaxFlowIntPR (PNEANet &Net, const int &SrcNId, const int &SnkNId) |
Returns the maximum integer valued flow in the network Net from source SrcNId to sink SnkNId . More... | |
TStr | GetFlagStr (const TGraphFlag &GraphFlag) |
Returns a string representation of a flag. More... | |
template<class PGraph > | |
void | PrintInfo (const PGraph &Graph, const TStr &Desc="", const TStr &OutFNm="", const bool &Fast=true) |
Prints basic graph statistics. More... | |
template<class PGraph > | |
int64 | GetTriads (const PGraph &Graph, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes) |
Computes the number of Closed and Open triads. More... | |
template<class PGraph > | |
int | GetKCoreNodes (const PGraph &Graph, TIntPrV &CoreIdSzV) |
Returns the number of nodes in each core of order K (where K=0, 1, ...) More... | |
template<class PGraph > | |
int | GetKCoreEdges (const PGraph &Graph, TIntPrV &CoreIdSzV) |
Returns the number of edges in each core of order K (where K=0, 1, ...) More... | |
PBPGraph | GenRndBipart (const int &LeftNodes, const int &RightNodes, const int &Edges, TRnd &Rnd=TInt::Rnd) |
Generates a random bipartite graph. More... | |
PUNGraph | GenRndDegK (const int &Nodes, const int &NodeDeg, const int &NSwitch=100, TRnd &Rnd=TInt::Rnd) |
Generates a random graph where each node has degree exactly NodeDeg. More... | |
PUNGraph | GenRndPowerLaw (const int &Nodes, const double &PowerExp, const bool &ConfModel=true, TRnd &Rnd=TInt::Rnd) |
Generates a random scale-free graph with power-law degree distribution. More... | |
PUNGraph | GenDegSeq (const TIntV &DegSeqV, TRnd &Rnd=TInt::Rnd) |
Generates a random graph with exact degree sequence. More... | |
PUNGraph | GenConfModel (const TIntV &DegSeqV, TRnd &Rnd=TInt::Rnd) |
Generates a random undirect graph with a given degree sequence. More... | |
PUNGraph | GenRewire (const PUNGraph &Graph, const int &NSwitch=100, TRnd &Rnd=TInt::Rnd) |
Rewire a random undirected graph. Keeps node degrees the same, but randomly rewires the edges. More... | |
PNGraph | GenRewire (const PNGraph &Graph, const int &NSwitch=100, TRnd &Rnd=TInt::Rnd) |
Rewire a random directed graph. Keeps node degrees the same, but randomly rewires the edges. More... | |
PBPGraph | GenRewire (const PBPGraph &Graph, const int &NSwitch=100, TRnd &Rnd=TInt::Rnd) |
Rewire a random bipartite graph. Keeps node degrees the same, but randomly rewires the edges. More... | |
PUNGraph | GenPrefAttach (const int &Nodes, const int &NodeOutDeg, TRnd &Rnd=TInt::Rnd) |
Generates a power-law degree distribution using Barabasi-Albert model of scale-free graphs. More... | |
PUNGraph | GenConfModel (const PUNGraph &G) |
Generate a random graph using (approximately) the same node degrees as in G using the configuration model. More... | |
PUNGraph | GenGeoPrefAttach (const int &Nodes, const int &OutDeg, const double &Beta, TRnd &Rnd=TInt::Rnd) |
Generates a random scale-free graph using the Geometric Preferential model. More... | |
PUNGraph | GenSmallWorld (const int &Nodes, const int &NodeOutDeg, const double &RewireProb, TRnd &Rnd=TInt::Rnd) |
Generates a randomly small-world graph using the Watts-Strogatz model. More... | |
PNGraph | GenForestFire (const int &Nodes, const double &FwdProb, const double &BckProb) |
Generates a random Forest Fire, directed graph with given probabilities. More... | |
PNGraph | GenCopyModel (const int &Nodes, const double &Beta, TRnd &Rnd=TInt::Rnd) |
Generates a random scale-free network using the Copying Model. More... | |
PNGraph | GenRMat (const int &Nodes, const int &Edges, const double &A, const double &B, const double &C, TRnd &Rnd=TInt::Rnd) |
Generates a R-MAT graph using recursive descent into a 2x2 matrix [A,B; C, 1-(A+B+C)]. More... | |
PNGraph | GenRMatEpinions () |
Generates a R-Mat graph, with a synthetic copy of the Epinions social network. More... | |
template<class PGraph > | |
PGraph | GenGrid (const int &Rows, const int &Cols, const bool &IsDir=true) |
Generates a 2D-grid graph of Rows rows and Cols columns. More... | |
template<class PGraph > | |
PGraph | GenStar (const int &Nodes, const bool &IsDir=true) |
Generates a graph with star topology. Node id 0 is in the center and then links to all other nodes. More... | |
template<class PGraph > | |
PGraph | GenCircle (const int &Nodes, const int &NodeOutDeg=1, const bool &IsDir=true) |
Generates a circle graph where every node creates out-links to NodeOutDeg forward nodes. More... | |
template<class PGraph > | |
PGraph | GenFull (const int &Nodes) |
Generates a complete graph on Nodes nodes. Graph has no self-loops. More... | |
template<class PGraph > | |
PGraph | GenTree (const int &Fanout, const int &Levels, const bool &IsDir=true, const bool &ChildPointsToParent=true) |
Generates a tree graph of Levels levels with every parent having Fanout children. More... | |
template<class PGraph > | |
PGraph | GenBaraHierar (const int &Levels, const bool &IsDir=true) |
Generates a Ravasz-Barabasi deterministic scale-free graph. More... | |
template<class PGraph > | |
PGraph | GenRndGnm (const int &Nodes, const int &Edges, const bool &IsDir=true, TRnd &Rnd=TInt::Rnd) |
Generates an Erdos-Renyi random graph. More... | |
int | ReadEdgeSchemaFromFile (TSsParser &Ss, const char &Separator, int &SrcColId, int &DstColId, TStrIntH &IntAttrEVals, TStrIntH &FltAttrEVals, TStrIntH &StrAttrEVals) |
bool | ReadEdgesFromFile (TSsParser &Ss, const char &Separator, PNEANet &Graph, int &SrcColId, int &DstColId, TStrIntH &IntAttrEVals, TStrIntH &FltAttrEVals, TStrIntH &StrAttrEVals) |
int | ReadNodeSchemaFromFile (TSsParser &Ss, const char &Separator, int &NId, TStrIntH &IntAttrNVals, TStrIntH &FltAttrNVals, TStrIntH &StrAttrNVals) |
bool | ReadNodesFromFile (TSsParser &Ss, const char &Separator, PNEANet &Graph, int &NColId, TStrIntH &IntAttrNVals, TStrIntH &FltAttrNVals, TStrIntH &StrAttrNVals) |
PNEANet | LoadEdgeListNet (const TStr &InFNm, const char &Separator) |
Loads a network from the text file InFNm with 1 node/edge per line ('Separator' separated columns, integer node id(s) + node/edge attributes). More... | |
void | WriteNodeSchemaToFile (FILE *F, TStrV &IntAttrNNames, TStrV &FltAttrNNames, TStrV &StrAttrNNames) |
void | WriteNodesToFile (FILE *F, const PNEANet &Graph, TStrV &IntAttrNNames, TStrV &FltAttrNNames, TStrV &StrAttrNNames) |
void | WriteEdgeSchemaToFile (FILE *F, TStrV &IntAttrENames, TStrV &FltAttrENames, TStrV &StrAttrENames) |
void | WriteEdgesToFile (FILE *F, const PNEANet &Graph, TStrV &IntAttrENames, TStrV &FltAttrENames, TStrV &StrAttrENames) |
void | SaveEdgeListNet (const PNEANet &Graph, const TStr &OutFNm, const TStr &Desc) |
Saves a network into a text file. Each line encodes either an edge or a node, along with its attributes. More... | |
PNGraph | LoadDyNet (const TStr &FNm) |
For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php) More... | |
TVec< PNGraph > | LoadDyNetGraphV (const TStr &FNm) |
For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php) More... | |
template<class PGraph > | |
PGraph | LoadEdgeList (const TStr &InFNm, const int &SrcColId=0, const int &DstColId=1) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, integer node ids). More... | |
template<class PGraph > | |
PGraph | LoadEdgeList (const TStr &InFNm, const int &SrcColId, const int &DstColId, const char &Separator) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line ('Separator' separated columns, integer node ids). More... | |
template<class PGraph > | |
PGraph | LoadEdgeListStr (const TStr &InFNm, const int &SrcColId=0, const int &DstColId=1) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, arbitrary string node ids). More... | |
template<class PGraph > | |
PGraph | LoadEdgeListStr (const TStr &InFNm, const int &SrcColId, const int &DstColId, TStrHash< TInt > &StrToNIdH) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, arbitrary string node ids). More... | |
template<class PGraph > | |
PGraph | LoadConnList (const TStr &InFNm) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 node and all its edges in a single line. More... | |
template<class PGraph > | |
PGraph | LoadConnListStr (const TStr &InFNm, TStrHash< TInt > &StrToNIdH) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 node and all its edges in a single line. More... | |
template<class PGraph > | |
PGraph | LoadPajek (const TStr &InFNm) |
Loads a (directed, undirected or multi) graph from Pajek .PAJ format file. More... | |
template<class PGraph > | |
void | SaveEdgeList (const PGraph &Graph, const TStr &OutFNm, const TStr &Desc=TStr()) |
Saves a graph into a text file. Each line contains two columns and encodes a single edge: <source node="" id>=""><tab><destination node="" id>=""> More... | |
template<class PGraph > | |
void | SavePajek (const PGraph &Graph, const TStr &OutFNm) |
Saves a graph in a Pajek .NET format. More... | |
template<class PGraph > | |
void | SavePajek (const PGraph &Graph, const TStr &OutFNm, const TIntStrH &NIdColorH) |
Saves a graph in a Pajek .NET format. More... | |
template<class PGraph > | |
void | SavePajek (const PGraph &Graph, const TStr &OutFNm, const TIntStrH &NIdColorH, const TIntStrH &NIdLabelH) |
Saves a graph in a Pajek .NET format. More... | |
template<class PGraph > | |
void | SavePajek (const PGraph &Graph, const TStr &OutFNm, const TIntStrH &NIdColorH, const TIntStrH &NIdLabelH, const TIntStrH &EIdColorH) |
Saves a graph in a Pajek .NET format. More... | |
template<class PGraph > | |
void | SaveMatlabSparseMtx (const PGraph &Graph, const TStr &OutFNm) |
Saves a graph in a MATLAB sparse matrix format. More... | |
template<class PGraph > | |
void | SaveGViz (const PGraph &Graph, const TStr &OutFNm, const TStr &Desc=TStr(), const bool &NodeLabels=false, const TIntStrH &NIdColorH=TIntStrH()) |
Save a graph in GraphVizp .DOT format. More... | |
template<class PGraph > | |
void | SaveGViz (const PGraph &Graph, const TStr &OutFNm, const TStr &Desc, const TIntStrH &NIdLabelH) |
Save a graph in GraphVizp .DOT format. More... | |
void | SetAllInvertSign (TFltV &ValV, const double &Val) |
bool | IsAllValVNeg (TFltV &ValV, const bool &InvertSign) |
void | GetSngVals (const PNGraph &Graph, const int &SngVals, TFltV &SngValV) |
Computes largest SngVals singular values of the adjacency matrix representing a directed Graph. More... | |
void | GetSngVec (const PNGraph &Graph, TFltV &LeftSV, TFltV &RightSV) |
Computes the leading left and right singular vector of the adjacency matrix representing a directed Graph. More... | |
void | GetSngVec (const PNGraph &Graph, const int &SngVecs, TFltV &SngValV, TFltVFltV &LeftSV, TFltVFltV &RightSV) |
void | GetEigVals (const PUNGraph &Graph, const int &EigVals, TFltV &EigValV) |
Computes top EigVals eigenvalues of the adjacency matrix representing a given undirected Graph. More... | |
void | GetEigVec (const PUNGraph &Graph, TFltV &EigVecV) |
Computes the leading eigenvector of the adjacency matrix representing a given undirected Graph. More... | |
void | GetEigVec (const PUNGraph &Graph, const int &EigVecs, TFltV &EigValV, TFltVFltV &EigVecV) |
Computes top EigVecs eigenvalues and eigenvectors of the adjacency matrix representing a given undirected Graph. More... | |
void | GetInvParticipRat (const PUNGraph &Graph, int MaxEigVecs, int TimeLimit, TFltPrV &EigValIprV) |
template<class PGraph > | |
void | DrawGViz (const PGraph &Graph, const TGVizLayout &Layout, const TStr &PltFNm, const TStr &Desc=TStr(), const bool &NodeLabels=false, const TIntStrH &NIdColorH=TIntStrH()) |
Draws a given Graph using a selected GraphViz Layout engine with nodes colored. More... | |
template<class PGraph > | |
void | DrawGViz (const PGraph &Graph, const TGVizLayout &Layout, const TStr &PltFNm, const TStr &Desc, const TIntStrH &NodeLabelH) |
Draws a given Graph using a selected GraphViz Layout engine with nodes labeled. More... | |
template<class PGraph > | |
PGraph | GetKCore (const PGraph &Graph, const int &K) |
void | TIntVToNumpy (TIntV &IntV, int *IntNumpyVecOut, int n) |
Converts TIntV to Numpy array. More... | |
void | TFltVToNumpy (TFltV &FltV, float *FltNumpyVecOut, int n) |
Converts TFltV to Numpy array. More... | |
void | NumpyToTIntV (TIntV &IntV, int *IntNumpyVecIn, int n) |
Converts NumpyArray to TIntV. More... | |
void | NumpyToTFltV (TFltV &FltV, float *FltNumpyVecIn, int n) |
Converts NumpyArray to TFltV. More... | |
template<class PGraph > | |
int | SamplePersonalizedPageRank (const PGraph &Graph, double JumpProb, const TIntV &StartNIdV, TRnd &Rnd) |
template<class PGraph > | |
double | GetPersonalizedPageRankBidirectional (const PGraph &Graph, double JumpProb, const TIntV &StartNIdV, int TargetNId, double MinProbability=-1.0, double RelativeError=0.1, bool provableRelativeError=false, bool PrintTimeForTuning=false) |
template<class PGraph > | |
double | GetRndWalkRestartBidirectional (const PGraph &Graph, double JumpProb, int StartNId, int TargetNId, double minProbability=-1.0, double relativeError=0.1, bool proveRelativeError=false, bool PrintTimeForTuning=false) |
void | PlotEigValRank (const PUNGraph &Graph, const int &EigVals, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the eigen-value rank distribution of the Graph adjacency matrix. Plots first EigVals eigenvalues. More... | |
void | PlotEigValDistr (const PUNGraph &Graph, const int &EigVals, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the distribution of components of the leading eigen-vector of the Graph adjacency matrix. Plots first EigVals values. More... | |
void | PlotInvParticipRat (const PUNGraph &Graph, const int &MaxEigVecs, const int &TimeLimit, const TStr &FNmPref, TStr DescStr) |
void | PlotSngValRank (const PNGraph &Graph, const int &SngVals, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the rank distribution of singular values of the Graph adjacency matrix. Plots first SngVals values. More... | |
void | PlotSngValDistr (const PNGraph &Graph, const int &SngVals, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the rank distribution of singular values of the Graph adjacency matrix. Plots first SngVals values. More... | |
void | PlotSngVec (const PNGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the distribution of the values of the leading left singular vector of the Graph adjacency matrix. Plots first SngVals values. More... | |
template<class PGraph > | |
void | PlotInDegDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr(), const bool &PlotCCdf=false, const bool &PowerFit=false) |
template<class PGraph > | |
void | PlotOutDegDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr(), const bool &PlotCCdf=false, const bool &PowerFit=false) |
template<class PGraph > | |
void | PlotWccDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the distribution of sizes of weakly connected components of a Graph. More... | |
template<class PGraph > | |
void | PlotSccDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the distribution of sizes of strongly connected components of a Graph. More... | |
template<class PGraph > | |
void | PlotClustCf (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the distribution of clustering coefficient of a Graph. More... | |
template<class PGraph > | |
void | PlotHops (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr(), const bool &IsDir=false, const int &NApprox=32) |
template<class PGraph > | |
void | PlotShortPathDistr (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr(), int TestNodes=TInt::Mx) |
Plots the distribution of the shortest path lengths of a Graph. Implementation is based on BFS. More... | |
template<class PGraph > | |
void | PlotKCoreNodes (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the k-Core node-size distribution: Core k vs. number of nodes in k-core. More... | |
template<class PGraph > | |
void | PlotKCoreEdges (const PGraph &Graph, const TStr &FNmPref, TStr DescStr=TStr()) |
Plots the k-Core edge-size distribution: Core k vs. number of edges in k-core. More... | |
PUNGraph | GetSubGraph (const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes=false) |
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumbering. More... | |
PNGraph | GetSubGraph (const PNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes) |
PUNGraph | GetEgonet (const PUNGraph &Graph, const int CtrNId, int &ArndEdgesX) |
Returns the egonet of node CtrNId as center in undirected graph Graph. And returns number of edges around the egonet. More... | |
PNGraph | GetEgonet (const PNGraph &Graph, const int CtrNId, int &InEgoEdgesX, int &OutEgoEdgesX) |
Returns the egonet of node CtrNId as center in directed graph Graph. And returns number of edges go in and out the egonet. More... | |
void | AddNodeWithAttributes (const PNEANet &Graph1, PNEANet &Graph2, const int NId) |
void | AddEdgeWithAttributes (const PNEANet &Graph1, PNEANet &Graph2, const int EId) |
void | AddEdgeWithAttributes (const PNEANet &Graph1, PNEANet &Graph2, const int NId, const int NbrId) |
PNEANet | GetEgonetAttr (const PNEANet &Graph, const int CtrNId, const int Radius) |
Returns the complete egonet of at given radius and copies node and edge attributes. More... | |
PNEANet | GetInEgonetAttr (const PNEANet &Graph, const int CtrNId, const int Radius) |
Returns the in-egonet of at given radius and copies node and edge attributes. More... | |
PNEANet | GetOutEgonetAttr (const PNEANet &Graph, const int CtrNId, const int Radius) |
Returns the out-egonet of at given radius and copies node and edge attributes. More... | |
PNEANet | GetInEgonetSubAttr (const PNEANet &Graph, const int CtrNId, const int Radius, const int MaxNum, const float percent) |
Returns the randomly sampled egonet with nodes sampled based on percentage or raw number, copying attributes. More... | |
PNEANet | GetGraphUnionAttr (PNEANet &DstGraph, const PNEANet &SrcGraph) |
template<class PGraph > | |
PGraph | GetSubGraph (const PGraph &Graph, const TIntV &NIdV) |
Returns an induced subgraph of graph Graph with NIdV nodes. More... | |
template<class PGraph > | |
PGraph | GetSubGraphRenumber (const PGraph &Graph, const TIntV &NIdV) |
Returns an induced subgraph of graph Graph with NIdV nodes with an node renumbering. More... | |
template<class PGraph > | |
PGraph | GetESubGraph (const PGraph &Graph, const TIntV &EIdV) |
Returns a subgraph of graph Graph with EIdV edges. More... | |
template<class PGraph > | |
PGraph | GetESubGraph (const PGraph &Graph, const TIntPrV &EdgeV) |
template<class PGraph , class TEdgeDat > | |
PGraph | GetEDatSubGraph (const PGraph &Graph, const TEdgeDat &EDat, const int &Cmp) |
Returns a subgraph of graph Graph with edges where edge data matches the parameters. More... | |
template<class PGraph , class TEdgeDat > | |
PGraph | GetEDatSubGraph (const PGraph &Graph, const TIntV &NIdV, const TEdgeDat &EDat, const int &Cmp) |
Returns a subgraph of graph Graph with NIdV nodes and edges where edge data matches the parameters. More... | |
template<class POutGraph , class PInGraph > | |
POutGraph | ConvertGraph (const PInGraph &InGraph, const bool &RenumberNodes=false) |
Performs conversion of graph InGraph with an optional node renumbering. More... | |
template<class POutGraph , class PInGraph > | |
POutGraph | ConvertSubGraph (const PInGraph &InGraph, const TIntV &NIdV, const bool &RenumberNodes=false) |
Returns an induced subgraph of graph InGraph with NIdV nodes with an optional node renumbering. More... | |
template<class POutGraph , class PInGraph > | |
POutGraph | ConvertESubGraph (const PInGraph &InGraph, const TIntV &EIdV, const bool &RenumberNodes=false) |
Returns a subgraph of graph InGraph with EIdV edges with an optional node renumbering. More... | |
template<class PGraph > | |
PGraph | GetRndSubGraph (const PGraph &Graph, const int &NNodes) |
Returns an induced random subgraph of graph Graph with NNodes nodes. More... | |
template<class PGraph > | |
PGraph | GetRndESubGraph (const PGraph &Graph, const int &NEdges) |
Returns a random subgraph of graph Graph with NEdges edges. More... | |
template<class PGraph > | |
PGraph | GetEgonetHop (const PGraph &Graph, const int CtrNId, const int Radius) |
Returns the egonet of node CtrNId as center for a Graph for a given radius. More... | |
template<class PGraph > | |
PGraph | GetInEgonetHop (const PGraph &Graph, const int CtrNId, const int Radius) |
Returns the in-egonet of node CtrNId as center in directed graph Graph for a given radius. More... | |
template<class PGraph > | |
PGraph | GetOutEgonetHop (const PGraph &Graph, const int CtrNId, const int Radius) |
Returns the out-egonet of node CtrNId as center in directed graph Graph for a given radius. More... | |
template<class PGraph > | |
PGraph | GetInEgonetSub (const PGraph &Graph, const int CtrNId, const int Radius, const int MaxNum=2, const float percent=-1.0) |
Returns the randomly sampled in-egonet with nodes sampled based on percentage, if percent != -1.0, or MaxNum nodes otherwise. More... | |
template<class PGraph > | |
PGraph | GetGraphUnion (PGraph &DstGraph, const PGraph &SrcGraph) |
int | GetCommon (TIntV &A, TIntV &B) |
Returns the number of common elements in two sorted TInt vectors. More... | |
template<class PGraph > | |
double | GetClustCf (const PGraph &Graph, int SampleNodes=-1) |
Computes the average clustering coefficient as defined in Watts and Strogatz, Collective dynamics of 'small-world' networks. More... | |
template<class PGraph > | |
double | GetClustCf (const PGraph &Graph, TFltPrV &DegToCCfV, int SampleNodes=-1) |
Computes the distribution of average clustering coefficient. More... | |
template<class PGraph > | |
double | GetClustCf (const PGraph &Graph, TFltPrV &DegToCCfV, int64 &ClosedTriads, int64 &OpenTriads, int SampleNodes=-1) |
Computes the distribution of average clustering coefficient as well as the number of open and closed triads in the graph. More... | |
template<class PGraph > | |
double | GetClustCfAll (const PGraph &Graph, TFltPrV &DegToCCfV, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes=-1) |
Computes the distribution of average clustering coefficient as well as the number of open and closed triads in the graph. More... | |
template<class PGraph > | |
double | GetNodeClustCf (const PGraph &Graph, const int &NId) |
Returns clustering coefficient of a particular node. More... | |
template<class PGraph > | |
void | GetNodeClustCf (const PGraph &Graph, TIntFltH &NIdCCfH) |
Computes clustering coefficient of each node of the Graph. More... | |
template<class PGraph > | |
int64 | GetTriads (const PGraph &Graph, int SampleNodes=-1) |
Returns the number of triangles in a graph. More... | |
template<class PGraph > | |
int64 | GetTriadsAll (const PGraph &Graph, int64 &ClosedTriadsX, int64 &OpenTriadsX, int SampleNodes=-1) |
Computes the number of Closed and Open triads. More... | |
template<class PGraph > | |
void | GetTriads (const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes=-1) |
Computes the number of open and close triads for every node of the network. More... | |
template<class PGraph > | |
int | GetTriadEdges (const PGraph &Graph, int SampleEdges=-1) |
Counts the number of edges that participate in at least one triad. More... | |
template<class PGraph > | |
int | GetNodeTriads (const PGraph &Graph, const int &NId) |
Returns the number of undirected triads a node NId participates in. More... | |
template<class PGraph > | |
int | GetNodeTriads (const PGraph &Graph, const int &NId, int &ClosedNTriadsX, int &OpenNTriadsX) |
Returns number of Open and Closed triads a node NId participates in. More... | |
template<class PGraph > | |
int | GetNodeTriadsAll (const PGraph &Graph, const int &NId, int &ClosedNTriadsX, int &OpenNTriadsX) |
Returns number of Open and Closed triads a node NId participates in. More... | |
template<class PGraph > | |
int | GetNodeTriads (const PGraph &Graph, const int &NId, const TIntSet &GroupSet, int &InGroupEdgesX, int &InOutGroupEdgesX, int &OutGroupEdgesX) |
Returns the number of triads between a node NId and a subset of its neighbors GroupSet . More... | |
template<class PGraph > | |
void | GetTriadParticip (const PGraph &Graph, TIntPrV &TriadCntV) |
Triangle Participation Ratio: For each node counts how many triangles it participates in and then returns a set of pairs (number of triangles, number of such nodes). More... | |
template<class PGraph > | |
int | GetCmnNbrs (const PGraph &Graph, const int &NId1, const int &NId2) |
Returns a number of shared neighbors between a pair of nodes NId1 and NId2. More... | |
template<class PGraph > | |
int | GetCmnNbrs (const PGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV) |
Returns the shared neighbors between a pair of nodes NId1 and NId2. More... | |
template<class PGraph > | |
int | GetLen2Paths (const PGraph &Graph, const int &NId1, const int &NId2) |
Returns the number of length 2 directed paths between a pair of nodes NId1, NId2 (NId1 –> U –> NId2). More... | |
template<class PGraph > | |
int | GetLen2Paths (const PGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV) |
Returns the 2 directed paths between a pair of nodes NId1, NId2 (NId1 –> U –> NId2). More... | |
template<class PGraph > | |
int64 | GetTriangleCnt (const PGraph &Graph) |
Returns the number of triangles in graph Graph . More... | |
template<class PGraph > | |
void | MergeNbrs (TIntV &NeighbourV, const typename PGraph::TObj::TNodeI &NI) |
Merges neighbors by removing duplicates and produces one sorted vector of neighbors. More... | |
template<class PGraph > | |
void | GetUniqueNbrV (const PGraph &Graph, const int &NId, TIntV &NbrV) |
Returns sorted vector NbrV containing unique in or out neighbors of node NId in graph Graph . More... | |
template<class PGraph > | |
void | GetTriads_v0 (const PGraph &Graph, TIntTrV &NIdCOTriadV, int SampleNodes) |
template<> | |
int | GetCmnNbrs< PUNGraph > (const PUNGraph &Graph, const int &NId1, const int &NId2, TIntV &NbrV) |
Variables | |
const TStr | CapAttrName = "capacity" |
const TStr | EDGES_START = ("#EDGES") |
const TStr | NODES_START = ("#NODES") |
const TStr | END_SENTINEL = ("#END") |
const TStr | SRC_ID_NAME = ("SrcNId") |
const TStr | DST_ID_NAME = ("DstNId") |
const TStr | NID_NAME = ("NId") |
const TStr | INT_TYPE_PREFIX = ("Int") |
const TStr | FLT_TYPE_PREFIX = ("Flt") |
const TStr | STR_TYPE_PREFIX = ("Str") |
const TStr | NULL_VAL = ("__null__") |
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).
Definition at line 179 of file subgraph.cpp.
References TVec< TVal, TSizeTy >::Len().
Referenced by GetEgonetAttr(), GetGraphUnionAttr(), GetInEgonetAttr(), GetInEgonetSubAttr(), and GetOutEgonetAttr().
void TSnap::AddEdgeWithAttributes | ( | const PNEANet & | Graph1, |
PNEANet & | Graph2, | ||
const int | NId, | ||
const int | NbrId | ||
) |
Definition at line 217 of file subgraph.cpp.
References TVec< TVal, TSizeTy >::Len().
Definition at line 143 of file subgraph.cpp.
References TVec< TVal, TSizeTy >::Len().
Referenced by GetEgonetAttr(), GetGraphUnionAttr(), GetInEgonetAttr(), GetInEgonetSubAttr(), and GetOutEgonetAttr().
void TSnap::AddSelfEdges | ( | const PGraph & | Graph | ) |
Adds a self-edge to every node in the graph.
Definition at line 369 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().
PUNGraph* TSnap::AllGraphsWithNNodes | ( | int | n | ) |
Definition at line 138 of file centr.cpp.
References TUNGraph::AddEdge(), and TUNGraph::AddNode().
double TSnap::BorgattiEverettMeasure | ( | PUNGraph & | Graph, |
TIntIntH & | out, | ||
double | coresize, | ||
int | type | ||
) |
Definition at line 186 of file coreper.cpp.
References TUNGraph::BegEI(), TUNGraph::EndEI(), and THash< TKey, TDat, THashFunc >::GetDat().
void TSnap::CascFind | ( | PNGraph | Graph, |
PTable | P, | ||
const TStr | C1, | ||
const TStr | C2, | ||
const TStr | C3, | ||
const TStr | C4, | ||
TVec< TIntV > & | TopCascVV, | ||
bool | |||
) |
Takes as input a directed graph and returns all the top cascades in TopCascVV
.
Definition at line 135 of file casc.cpp.
References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::BegI(), TSnapQueue< TVal >::Empty(), TVec< TVal, TSizeTy >::EndI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TVec< TVal, TSizeTy >::GetVal(), THashSet< TKey, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), THashSet< TKey, THashFunc >::Len(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), TVec< TVal, TSizeTy >::Sort(), TSnapQueue< TVal >::Top(), and TInt::Val.
void TSnap::CascFindMP | ( | PNGraph | Graph, |
PTable | P, | ||
const TStr | C1, | ||
const TStr | C2, | ||
const TStr | C3, | ||
const TStr | C4, | ||
TVec< TIntV > & | TopCascVV | ||
) |
Parallel implementaion of CascFind takes as input a directed graph and returns all the top cascades in TopCascVV
.
Definition at line 200 of file casc.cpp.
References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::BegI(), TSnapQueue< TVal >::Empty(), TVec< TVal, TSizeTy >::EndI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TVec< TVal, TSizeTy >::GetVal(), THashSet< TKey, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), TVec< TVal, TSizeTy >::Sort(), TSnapQueue< TVal >::Top(), and TInt::Val.
PNGraph TSnap::CascGraph | ( | PTable | P, |
const TStr | C1, | ||
const TStr | C2, | ||
const TStr | C3, | ||
const TStr | C4, | ||
const TInt | W, | ||
bool | SortParam | ||
) |
Takes as input the column names of the PTable P
as C1
, C2
, C3
and C4
and returns a directed graph of W-adjacent
events. By default calls CascGraphSource. Toggle SortParam to use CascGraphTime.
Definition at line 126 of file casc.cpp.
References CascGraphSource(), and CascGraphTime().
PNGraph TSnap::CascGraphSource | ( | PTable | P, |
const TStr | C1, | ||
const TStr | C2, | ||
const TStr | C3, | ||
const TStr | C4, | ||
const TInt | W | ||
) |
Takes as input the column names of the PTable P
as C1
, C2
,C3
and C4
and returns a directed graph of W-adjacent
events. For graph generation events are sorted by C1
.
Definition at line 3 of file casc.cpp.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), TNGraph::New(), and TInt::Val.
Referenced by CascGraph().
PNGraph TSnap::CascGraphTime | ( | PTable | P, |
const TStr | C1, | ||
const TStr | C2, | ||
const TStr | C3, | ||
const TStr | C4, | ||
const TInt | W | ||
) |
Takes as input the column names of the PTable P
as C1
, C2
,C3
and C4
and returns a directed graph of W-adjacent
events. For graph generation events are sorted by C3
.
Definition at line 59 of file casc.cpp.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), TNGraph::New(), and TInt::Val.
Referenced by CascGraph().
void TSnap::CmtyEvolutionFileBatch | ( | TStr | InFNm, |
TIntIntHH & | sizesCont, | ||
TIntIntHH & | cCont, | ||
TIntIntVH & | edges, | ||
double | alpha, | ||
double | beta, | ||
int | CmtyAlg | ||
) |
Definition at line 490 of file cmty.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TUNGraph::AddEdge(), TUNGraph::AddNode(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::Clr(), DelSelfEdges(), edge, TSsParser::Eof(), Fail, TStr::GetCh(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::GetDat(), TSsParser::GetInt(), THash< TKey, TDat, THashFunc >::GetKey(), TSsParser::GetLnStr(), TUNGraph::GetNodes(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::IsKey(), TUNGraph::IsNode(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TUNGraph::New(), TSsParser::Next(), and ssfWhiteSep.
Referenced by CmtyEvolutionFileBatchV().
void TSnap::CmtyEvolutionFileBatchV | ( | TStr | InFNm, |
TIntIntVH & | sizesContV, | ||
TIntIntVH & | cContV, | ||
TIntIntVH & | edges, | ||
double | alpha, | ||
double | beta, | ||
int | CmtyAlg | ||
) |
Definition at line 441 of file cmty.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), CmtyEvolutionFileBatch(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::IsIn(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Len().
Referenced by CmtyTest().
void TSnap::CmtyEvolutionJson | ( | TStr & | Json, |
TIntIntVH & | sizesContV, | ||
TIntIntVH & | cContV, | ||
TIntIntVH & | edges | ||
) |
Definition at line 725 of file cmty.cpp.
References THash< TKey, TDat, THashFunc >::BegI(), TInt::GetStr(), TStr::InsStr(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::Len(), and TStr::Len().
Referenced by CmtyTest().
Definition at line 827 of file cmty.cpp.
References CmtyEvolutionFileBatchV(), and CmtyEvolutionJson().
int TSnap::CntDegNodes | ( | const PGraph & | Graph, |
const int & | NodeDeg | ||
) |
Returns the number of nodes with degree NodeDeg.
Definition at line 105 of file alg.h.
Referenced by TTimeNet::LoadArxiv(), TTimeNet::LoadPatents(), and TGStat::TakeBasicStat().
int TSnap::CntEdgesToSet | ( | const PGraph & | Graph, |
const int & | NId, | ||
const TIntSet & | NodeSet | ||
) |
Returns the number of nodes in NodeSet that have an edge to the node NId.
Definition at line 123 of file alg.h.
References THashSet< TKey, THashFunc >::AddKey(), gfDirected, and THashSet< TKey, THashFunc >::IsKey().
int TSnap::CntInDegNodes | ( | const PGraph & | Graph, |
const int & | NodeInDeg | ||
) |
Returns the number of nodes with in-degree NodeInDeg.
Definition at line 87 of file alg.h.
Referenced by TTimeNet::LoadBipartite(), and TGStat::TakeBasicStat().
int TSnap::CntNonZNodes | ( | const PGraph & | Graph | ) |
Returns the number of nodes with degree greater than 0.
Definition at line 114 of file alg.h.
Referenced by TTimeNet::PlotMedianDegOverTm().
int TSnap::CntOutDegNodes | ( | const PGraph & | Graph, |
const int & | NodeOutDeg | ||
) |
Returns the number of nodes with out-degree NodeOutDeg.
Definition at line 96 of file alg.h.
Referenced by TTimeNet::LoadBipartite(), and TGStat::TakeBasicStat().
int TSnap::CntSelfEdges | ( | const PGraph & | Graph | ) |
Counts the number of self-edges in a graph. Edge (u,u)
is a self-edge.
int TSnap::CntUniqBiDirEdges | ( | const PGraph & | Graph | ) |
Counts unique bidirectional edges in the graph Graph
. Edge is bidirectional if there exist directed edges in both directions: (u,v)
and (v,u)
Definition at line 316 of file alg.h.
References CntUniqUndirEdges(), and gfDirected.
Referenced by TGStat::TakeBasicStat().
int TSnap::CntUniqDirEdges | ( | const PGraph & | Graph | ) |
Counts unique directed edges in the graph Graph
. Nodes (u,v)
(where u!=v
) are connected via a directed edge if there exists a directed edge from node u
to node v
.
Definition at line 301 of file alg.h.
References THashSet< TKey, THashFunc >::AddKey(), THashSet< TKey, THashFunc >::Clr(), and THashSet< TKey, THashFunc >::Len().
Referenced by TGStat::TakeBasicStat().
int TSnap::CntUniqUndirEdges | ( | const PGraph & | Graph | ) |
Counts unique undirected edges in the graph Graph
. Nodes (u,v)
(where u!=v
) are connected via an undirected edge if there exists an edge in either direction (u,v)
or (v,u)
.
Definition at line 279 of file alg.h.
References THashSet< TKey, THashFunc >::AddKey(), THashSet< TKey, THashFunc >::Clr(), and THashSet< TKey, THashFunc >::Len().
Referenced by CntUniqBiDirEdges().
Clauset-Newman-Moore community detection method for large networks. At every step of the algorithm two communities that contribute maximum positive value to global modularity are merged. See: Finding community structure in very large networks, A. Clauset, M.E.J. Newman, C. Moore, 2004
Definition at line 1449 of file cmty.cpp.
References TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN().
Girvan-Newman community detection algorithm based on Betweenness centrality. See: Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002)
Definition at line 312 of file cmty.cpp.
References TSnap::TSnapDetail::_GirvanNewmanGetModularity(), TUNGraph::BegNI(), TVec< TVal, TSizeTy >::Clr(), TSnap::TSnapDetail::CmtyGirvanNewmanStep(), TUNGraph::EndNI(), TUNGraph::GetEdges(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Swap().
POutGraph TSnap::ConvertESubGraph | ( | const PInGraph & | InGraph, |
const TIntV & | EIdV, | ||
const bool & | RenumberNodes = false |
||
) |
Returns a subgraph of graph InGraph with EIdV edges with an optional node renumbering.
Creates a subgraph of the input graph InGraph on EIdV edges and returns an output graph. Input and output graphs can have different types. Node and edge data is not copied, but it is shared by input and output graphs.
Parameter RenumberNodes determines, whether the node IDs are preserved or not. If RenumberNodes is false, then nodes in the resulting graph have the same node IDs as nodes in InGraph. If RenumberNodes is true, then nodes in the resulting graph are renumbered sequentially from 0 to N-1. By default, the nodes are not renumbered.
Definition at line 441 of file subgraph.h.
References CAssert, edge, gfMultiGraph, HasGraphFlag, IAssert, and TVec< TVal, TSizeTy >::Len().
POutGraph TSnap::ConvertGraph | ( | const PInGraph & | InGraph, |
const bool & | RenumberNodes = false |
||
) |
Performs conversion of graph InGraph with an optional node renumbering.
Takes an input graph InGraph and returns an output graph. Input and output graphs can have different types. Node and edge data is not copied, but it is shared by input and output graphs.
Parameter RenumberNodes determines, whether the node IDs are preserved or not. If RenumberNodes is false, then nodes in the resulting graph have the same node IDs as nodes in InGraph. If RenumberNodes is true, then nodes in the resulting graph are renumbered sequentially from 0 to N-1. By default, the nodes are not renumbered.
Definition at line 326 of file subgraph.h.
References THashSet< TKey, THashFunc >::AddKey(), gfDirected, and HasGraphFlag.
POutGraph TSnap::ConvertSubGraph | ( | const PInGraph & | InGraph, |
const TIntV & | NIdV, | ||
const bool & | RenumberNodes = false |
||
) |
Returns an induced subgraph of graph InGraph with NIdV nodes with an optional node renumbering.
Creates a subgraph of the input graph InGraph on NIdV nodes and returns an output graph. Input and output graphs can have different types. Node and edge data is not copied, but it is shared by input and output graphs.
Parameter RenumberNodes determines, whether the node IDs are preserved or not. If RenumberNodes is false, then nodes in the resulting graph have the same node IDs as nodes in InGraph. If RenumberNodes is true, then nodes in the resulting graph are renumbered sequentially from 0 to N-1. By default, the nodes are not renumbered.
Definition at line 436 of file subgraph.h.
void TSnap::DelDegKNodes | ( | PGraph & | Graph, |
const int & | OutDegK, | ||
const int & | InDegK | ||
) |
Removes all the node of out-degree OutDegK
and all the nodes of in-degree InDegK
from the graph.
Definition at line 445 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().
void TSnap::DelNodes | ( | PGraph & | Graph, |
const TIntV & | NIdV | ||
) |
Removes nodes with ids stored in NIdV
from the graph.
Definition at line 425 of file alg.h.
References TVec< TVal, TSizeTy >::Len().
void TSnap::DelSelfEdges | ( | const PGraph & | Graph | ) |
Removes all the self-edges from the graph.
Definition at line 419 of file alg.h.
Referenced by CmtyEvolutionFileBatch(), ChibaNishizekiWeighter::Initialize(), TAGMFit::InitNodeData(), TAGMFast::SetGraph(), TCoda::SetGraph(), TCesna::SetGraph(), and TKronMomentsFit::Test().
void TSnap::DelZeroDegNodes | ( | PGraph & | Graph | ) |
Removes all the zero-degree nodes, that isolated nodes, from the graph.
Definition at line 432 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().
Referenced by TKronMtx::PlotCmpGraphs(), and TMAGFitBern::PlotProperties().
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.
PltFNm | Output filename (extension .ps, .png, .gif) determines the output format. |
NIdColorH | Maps node ids to node colors (see GraphViz documentation for more details). |
Definition at line 34 of file gviz.h.
References TStr::GetFExt(), TStr::GetSubStr(), TSnap::TSnapDetail::GVizDoLayout(), TStr::Len(), and SaveGViz().
Referenced by TLocClust::DrawWhiskers(), and PlotRoles().
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.
PltFNm | Output filename (extension .ps, .png, .gif) determines the output format. |
NIdColorH | Maps node ids to node colors (see GraphViz documentation for more details). |
Definition at line 42 of file gviz.h.
References TStr::GetFExt(), TStr::GetSubStr(), TSnap::TSnapDetail::GVizDoLayout(), TStr::Len(), and SaveGViz().
Event importance.
Definition at line 527 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), and THash< TKey, TDat, THashFunc >::GetDat().
Definition at line 556 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), and THash< TKey, TDat, THashFunc >::GetDat().
Girvan-Newman community detection algorithm based on Betweenness centrality. See: Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002)
Definition at line 12 of file coreper.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TUNGraph::BegNI(), TUNGraph::EndNI(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::Len(), and THash< TKey, TDat, THashFunc >::SortByDat().
Definition at line 56 of file coreper.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TUNGraph::BegNI(), THash< TKey, TDat, THashFunc >::EndI(), TUNGraph::EndNI(), TUNGraph::GetNI(), TUNGraph::GetNodes(), Intersect(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::IsKey(), THash< TKey, TDat, THashFunc >::Len(), and THash< TKey, TDat, THashFunc >::SortByDat().
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.
MidToSrcAugV | Contains the path vector from the midpoint node where the bi-d search met back to the source node. |
MidToSnkAugV | Contains the path vector from the midpoint node where the bi-d search met back to the sink node. |
Definition at line 71 of file flow.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::GetDat(), TNEANet::TEdgeI::GetDstNId(), TNEANet::TEdgeI::GetSrcNId(), IntFlowBiDBFS(), and TInt::Mx.
Referenced by GetMaxFlowIntEK().
Definition at line 685 of file centr.cpp.
References TVec< TVal, TSizeTy >::Del(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), and TInt::Mx.
Referenced by GetWeightedShortestPath().
PGraph TSnap::GenBaraHierar | ( | const int & | Levels, |
const bool & | IsDir | ||
) |
Generates a Ravasz-Barabasi deterministic scale-free graph.
Corners of the graph are recursively expanded with miniature copies of the base graph (below). The graph has power-law degree distribution with the exponent 1+ln(5)/ln(4) and clustering coefficient with power-law decay exponent -1. Base graph:
/// o---o /// |\ /| /// | o | /// |/ \| /// o---o ///
See: Hierarchical organization in complex networks. Ravasz and Barabasi. URL: http://arxiv.org/abs/cond-mat/0206130
Definition at line 174 of file ggen.h.
References TMath::Power(), and TMath::Round().
PGraph TSnap::GenCircle | ( | const int & | Nodes, |
const int & | NodeOutDeg = 1 , |
||
const bool & | IsDir = true |
||
) |
Generates a circle graph where every node creates out-links to NodeOutDeg forward nodes.
Definition at line 104 of file ggen.h.
References gfDirected.
Generates a random undirect graph with a given degree sequence.
Generates a random undirect graph with a given degree sequence DegSeqV. Configuration model operates as follows. For each node N, of degree DeqSeqV[N] we create DeqSeqV[N] spokes (half-edges). We then pick two spokes at random, and connect the spokes endpoints. We continue this process until no spokes are left. Generally this generates a multigraph (i.e., spokes out of same nodes can be chosen multiple times).We ignore (discard) self-loops and multiple edges. Thus, the generated graph will only approximate follow the given degree sequence. The method is very fast!
Definition at line 122 of file ggen.cpp.
References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), TRnd::GetUniDevInt(), THashSet< TKey, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), TMath::Mn(), TUNGraph::New(), TUNGraph::Reserve(), and Swap().
Referenced by GenConfModel(), GenRndPowerLaw(), and TTimeNet::PlotEffDiam().
Generate a random graph using (approximately) the same node degrees as in G using the configuration model.
Definition at line 338 of file ggen.cpp.
References GenConfModel(), GetDegSeqV(), and TUNGraph::GetNodes().
Generates a random scale-free network using the Copying Model.
Generates a random scale-free network using the Copying Model. The generating process operates as follows: Node u is added to a graph, it selects a random node v, and with prob Beta it links to v, with 1-Beta links u links to neighbor of v. The power-law degree exponent is -1/(1-Beta). See: Stochastic models for the web graph. Kumar, Raghavan, Rajagopalan, Sivakumar, Tomkins, Upfal. URL: http://snap.stanford.edu/class/cs224w-readings/kumar00stochastic.pdf
Definition at line 456 of file ggen.cpp.
References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TNGraph::GetRndNId(), TRnd::GetUniDev(), TRnd::GetUniDevInt(), TNGraph::New(), and TNGraph::Reserve().
Generates a random graph with exact degree sequence.
Generates a random graph with exact degree sequence DegSeqV
. DegSeqV
must be sorted in descending order. The generated graph has no self loops. The graph generation process simulates the Configuration Model, but if a duplicate edge occurs, we find a random edge, break it and reconnect it with the duplicate.
Definition at line 61 of file ggen.cpp.
References TUNGraph::AddEdge(), TUNGraph::AddNode(), TUNGraph::DelEdge(), edge, TSnap::TSnapDetail::GetRndEdgeNonAdjNode(), IAssert, IAssertR, TUNGraph::IsEdge(), TVec< TVal, TSizeTy >::IsSorted(), TVec< TVal, TSizeTy >::Len(), TUNGraph::New(), TUNGraph::Reserve(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.
Referenced by GenRndDegK(), and GenRndPowerLaw().
PNGraph TSnap::GenForestFire | ( | const int & | Nodes, |
const double & | FwdProb, | ||
const double & | BckProb | ||
) |
Generates a random Forest Fire, directed graph with given probabilities.
Definition at line 445 of file ggen.cpp.
References TForestFire::GenGraph().
PGraph TSnap::GenFull | ( | const int & | Nodes | ) |
PUNGraph TSnap::GenGeoPrefAttach | ( | const int & | Nodes, |
const int & | OutDeg, | ||
const double & | Beta, | ||
TRnd & | Rnd | ||
) |
Generates a random scale-free graph using the Geometric Preferential model.
Generates a random scale-free graph using the Geometric Preferential Attachment model by Flexman, Frieze and Vera. See: A geometric preferential attachment model of networks by Flexman, Frieze and Vera. WAW 2004. URL: http://math.cmu.edu/~af1p/Texfiles/GeoWeb.pdf
Definition at line 364 of file ggen.cpp.
References TVec< TVal, TSizeTy >::Add(), TUNGraph::AddEdge(), TUNGraph::AddNode(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Del(), TUNGraph::TNodeI::GetDeg(), TUNGraph::GetNI(), TSnap::TSnapDetail::GetSphereDev(), TRnd::GetUniDevInt(), TUNGraph::IsNode(), TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), TUNGraph::New(), TMath::Pi, TMath::Sqr(), TTriple< TVal1, TVal2, TVal3 >::Val1, TTriple< TVal1, TVal2, TVal3 >::Val2, and TTriple< TVal1, TVal2, TVal3 >::Val3.
PGraph TSnap::GenGrid | ( | const int & | Rows, |
const int & | Cols, | ||
const bool & | IsDir = true |
||
) |
Generates a 2D-grid graph of Rows rows and Cols columns.
Definition at line 65 of file ggen.h.
References gfDirected.
Generates a power-law degree distribution using Barabasi-Albert model of scale-free graphs.
Barabasi-Albert model of scale-free graphs. The graph has power-law degree distribution. See: Emergence of scaling in random networks by Barabasi and Albert. URL: http://arxiv.org/abs/cond-mat/9910332
Definition at line 313 of file ggen.cpp.
References TVec< TVal, TSizeTy >::Add(), TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), THashSet< TKey, THashFunc >::Clr(), TRnd::GetUniDevInt(), TVec< TVal, TSizeTy >::Len(), THashSet< TKey, THashFunc >::Len(), TPt< TRec >::New(), and TUNGraph::Reserve().
Rewire a random undirected graph. Keeps node degrees the same, but randomly rewires the edges.
Rewire the network. Keeps node degrees as is but randomly rewires the edges. Use this function to generate a random graph with the same degree sequence as the OrigGraph. See: On the uniform generation of random graphs with prescribed degree sequences by R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon URL: http://arxiv.org/abs/cond-mat/0312028
Definition at line 168 of file ggen.cpp.
References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), TUNGraph::BegNI(), THashSet< TKey, THashFunc >::DelKeyId(), TUNGraph::EndNI(), TUNGraph::GetEdges(), TUNGraph::GetNodes(), THashSet< TKey, THashFunc >::GetRndKeyId(), TExeTm::GetSecs(), TExeTm::GetStr(), THashSet< TKey, THashFunc >::IsKey(), THashSet< TKey, THashFunc >::Len(), TUNGraph::New(), TUNGraph::Reserve(), Swap(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.
Referenced by GenRndDegK(), GenRndPowerLaw(), and TLocClust::PlotNCP().
Rewire a random directed graph. Keeps node degrees the same, but randomly rewires the edges.
Rewire the network. Keeps node degrees as is but randomly rewires the edges. Use this function to generate a random graph with the same degree sequence as the OrigGraph. See: On the uniform generation of random graphs with prescribed degree sequences by R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon. URL: http://arxiv.org/abs/cond-mat/0312028
Definition at line 219 of file ggen.cpp.
References TNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TNGraph::AddNode(), THashSet< TKey, THashFunc >::DelKeyId(), THashSet< TKey, THashFunc >::GetRndKeyId(), TExeTm::GetSecs(), TExeTm::GetStr(), THashSet< TKey, THashFunc >::IsKey(), THashSet< TKey, THashFunc >::Len(), TNGraph::New(), TNGraph::Reserve(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.
Rewire a random bipartite graph. Keeps node degrees the same, but randomly rewires the edges.
Rewire a bipartite graph. Keeps node degrees as is but randomly rewires the edges. Use this function to generate a random graph with the same degree sequence as the OrigGraph. See: On the uniform generation of random graphs with prescribed degree sequences by R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, U. Alon URL: http://arxiv.org/abs/cond-mat/0312028
Definition at line 266 of file ggen.cpp.
References TBPGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TBPGraph::AddNode(), THashSet< TKey, THashFunc >::DelKeyId(), THashSet< TKey, THashFunc >::GetRndKeyId(), TExeTm::GetSecs(), TExeTm::GetStr(), IAssert, THashSet< TKey, THashFunc >::IsKey(), THashSet< TKey, THashFunc >::Len(), TBPGraph::New(), TBPGraph::Reserve(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.
PNGraph TSnap::GenRMat | ( | const int & | Nodes, |
const int & | Edges, | ||
const double & | A, | ||
const double & | B, | ||
const double & | C, | ||
TRnd & | Rnd | ||
) |
Generates a R-MAT graph using recursive descent into a 2x2 matrix [A,B; C, 1-(A+B+C)].
R-MAT Generator. The modes is based on the recursive descent into a 2x2 matrix [A,B; C, 1-(A+B+C)]. See: R-MAT Generator: A Recursive Model for Graph Mining. D. Chakrabarti, Y. Zhan and C. Faloutsos, in SIAM Data Mining 2004. URL: http://www.cs.cmu.edu/~deepay/mywww/papers/siam04.pdf
Definition at line 481 of file ggen.cpp.
References TVec< TVal, TSizeTy >::Add(), TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::Defrag(), edge, Fail, TRnd::GetUniDev(), IAssert, TNGraph::IsEdge(), TNGraph::New(), and TNGraph::Reserve().
Referenced by GenRMatEpinions().
PNGraph 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 550 of file ggen.cpp.
References GenRMat().
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.
References TRnd::GetUniDevInt(), IAssertR, and TBPGraph::New().
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.
References TVec< TVal, TSizeTy >::Add(), GenDegSeq(), GenRewire(), and IAssert.
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.
References edge, TStr::Fmt(), TRnd::GetUniDevInt(), IAssert, and IAssertR.
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.
References TVec< TVal, TSizeTy >::Add(), GenConfModel(), GenDegSeq(), GenRewire(), TRnd::GetPowerDev(), TVec< TVal, TSizeTy >::Reverse(), TMath::Round(), and TVec< TVal, TSizeTy >::Sort().
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 415 of file ggen.cpp.
References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), TUNGraph::Defrag(), edge, TStr::Fmt(), TRnd::GetUniDev(), TRnd::GetUniDevInt(), IAssert, IAssertR, THashSet< TKey, THashFunc >::IsKey(), THashSet< TKey, THashFunc >::Len(), TUNGraph::New(), and TUNGraph::Reserve().
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.
References gfDirected.
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.
References edge.
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.
References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Del(), TUNGraph::DelEdge(), TVec< TVal, TSizeTy >::Empty(), GetEdgeBridges(), GetWccs(), IAssert, TVec< TVal, TSizeTy >::Len(), and TUNGraph::New().
Referenced by TLocClustStat::BagOfWhiskers(), TLocClustStat::BagOfWhiskers2(), and TLocClust::DrawWhiskers().
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.
References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Del(), TUNGraph::DelEdge(), TVec< TVal, TSizeTy >::Empty(), GetEdgeBridges(), GetWccs(), GetWccSzCnt(), IAssert, TVec< TVal, TSizeTy >::Len(), and TUNGraph::New().
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.
SrcNId | Starting node. |
DistNbrsV | Maps between the distance H (in hops) and the number of nodes reachable in <=H hops. |
MxDist | Maximum number of hops the algorithm spreads from SrcNId. |
IsDir | false: consider links as undirected (drop link directions). |
NApprox | Quality of approximation. See the ANF paper. |
Definition at line 204 of file anf.h.
References TGraphAnf< PGraph >::GetNodeAnf().
Referenced by PlotHops(), and TGStat::TakeDiam().
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.
DistNbrsV | Maps between the distance H (in hops) and the number of nodes reachable in <=H hops. |
MxDist | Maximum number of hops the algorithm spreads from SrcNId. |
IsDir | false: consider links as undirected (drop link directions). |
NApprox | Quality of approximation. See the ANF paper. |
Definition at line 210 of file anf.h.
References TGraphAnf< PGraph >::GetGraphAnf().
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).
IsDir | false: consider links as undirected (drop link directions). |
Definition at line 216 of file anf.h.
References TSnap::TSnapDetail::CalcEffDiam(), and TGraphAnf< PGraph >::GetGraphAnf().
Referenced by GetAnfEffDiam(), TKroneckerLL::GradDescentConvergence(), TTimeNet::PlotEffDiam(), and TTimeNENet::PlotEffDiam().
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).
IsDir | false: consider links as undirected (drop link directions). |
Definition at line 224 of file anf.h.
References TMom::Add(), TMom::Def(), GetAnfEffDiam(), and TMom::GetMean().
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.
References TCnCom::GetDfsVisitor(), and TUNGraph::GetNodes().
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.
NIdBtwH | hash table mapping node ids to their corresponding betweenness centrality values. |
NodeFrac | quality of approximation. NodeFrac=1.0 gives exact betweenness values. |
Definition at line 489 of file centr.h.
References TVec< TVal, TSizeTy >::DelLast(), TVec< TVal, TSizeTy >::Len(), TInt::Rnd, and TVec< TVal, TSizeTy >::Shuffle().
Referenced by TSnap::TSnapDetail::CmtyGirvanNewmanStep().
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.
EdgeBtwH | hash table mapping edges (pairs of node ids) to their corresponding betweenness centrality values. |
NodeFrac | quality of approximation. NodeFrac=1.0 gives exact betweenness values. |
Definition at line 501 of file centr.h.
References TVec< TVal, TSizeTy >::DelLast(), TVec< TVal, TSizeTy >::Len(), TInt::Rnd, and TVec< TVal, TSizeTy >::Shuffle().
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.
NIdBtwH | hash table mapping node ids to their corresponding betweenness centrality values. |
EdgeBtwH | hash table mapping edges (pairs of node ids) to their corresponding betweenness centrality values. |
NodeFrac | quality of approximation. NodeFrac=1.0 gives exact betweenness values. |
Definition at line 513 of file centr.h.
References TVec< TVal, TSizeTy >::DelLast(), TVec< TVal, TSizeTy >::Len(), TInt::Rnd, and TVec< TVal, TSizeTy >::Shuffle().
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.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Clr(), TSStack< TVal >::Clr(), TQQueue< TVal >::Clr(), TSStack< TVal >::Empty(), TQQueue< TVal >::Empty(), THash< TKey, TDat, THashFunc >::GetDat(), gfDirected, TVec< TVal, TSizeTy >::Len(), TMath::Mn(), TMath::Mx(), TSStack< TVal >::Pop(), TQQueue< TVal >::Pop(), TSStack< TVal >::Push(), TQQueue< TVal >::Push(), TSStack< TVal >::Top(), and TQQueue< TVal >::Top().
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).
IsDir | false: ignore edge directions and consider edges/paths as undirected (in case they are directed). |
Definition at line 424 of file bfsdfs.h.
Referenced by GetBfsEffDiam(), GetBfsEffDiamAll(), GetBfsFullDiam(), TTimeNet::PlotMissingPast(), and PrintInfo().
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).
IsDir | false: ignore edge directions and consider edges/paths as undirected (in case they are directed). |
Definition at line 432 of file bfsdfs.h.
References GetBfsEffDiam().
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).
IsDir | false: ignore edge directions and consider edges/paths as undirected (in case they are directed). |
Definition at line 439 of file bfsdfs.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TSnap::TSnapDetail::CalcEffDiamPdf(), TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::GetKey(), TVec< TVal, TSizeTy >::Last(), THash< TKey, TDat, THashFunc >::Len(), TMath::Mn(), TInt::Mx, TBreathFS< PGraph >::NIdDistH, TInt::Rnd, TVec< TVal, TSizeTy >::Shuffle(), and TVec< TVal, TSizeTy >::Sort().
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.
IsDir | false: ignore edge directions and consider edges/paths as undirected (in case they are directed). |
Definition at line 472 of file bfsdfs.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TSnap::TSnapDetail::CalcEffDiamPdf(), TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::IsKeyGetDat(), TVec< TVal, TSizeTy >::Last(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TMath::Mn(), TInt::Mx, TBreathFS< PGraph >::NIdDistH, TInt::Rnd, TVec< TVal, TSizeTy >::Shuffle(), and TVec< TVal, TSizeTy >::Sort().
double TSnap::GetBfsEffDiamAll | ( | const PGraph & | Graph, |
const int & | NTestNodes, | ||
const bool & | IsDir, | ||
double & | EffDiamX, | ||
int & | FullDiamX, | ||
double & | AvgSPLX | ||
) |
Returns the (approximation of the) Effective Diameter, the Diameter and the Average Shortest Path length in a graph (by performing BFS from NTestNodes random starting nodes).
This function is a duplicate. It is required by Snap.py.
IsDir | false: ignore edge directions and consider edges/paths as undirected (in case they are directed). |
Definition at line 467 of file bfsdfs.h.
References GetBfsEffDiam().
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).
IsDir | false: ignore edge directions and consider edges/paths as undirected (in case they are directed). |
Definition at line 416 of file bfsdfs.h.
References GetBfsEffDiam().
Referenced by TGStat::TakeDiam().
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 332 of file bfsdfs.h.
References TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::Len(), TInt::Mx, TNGraph::New(), TBreathFS< PGraph >::NIdDistH, and THash< TKey, TDat, THashFunc >::SortByDat().
Returns all bi-connected components of a Graph.
BiCnComV | is 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.
References TCnCom::GetDfsVisitor(), and TUNGraph::GetNodes().
Referenced by GetBiConSzCnt(), GetEdgeBridges(), and GetMxBiCon().
Returns a distribution of bi-connected component sizes.
SzCntV | returns a set of pairs (number of nodes in the bi-component, number of such components) |
Definition at line 31 of file cncom.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), GetBiCon(), THash< TKey, TDat, THashFunc >::GetKeyDatPrV(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Sort().
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.
double TSnap::GetClosenessCentrMP | ( | const PGraph & | Graph, |
const int & | NId, | ||
const bool & | Normalized = true , |
||
const bool & | IsDir = false |
||
) |
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 137 of file triad.h.
References TVec< TVal, TSizeTy >::Empty(), GetTriads(), IAssert, and TVec< TVal, TSizeTy >::Len().
Referenced by GetClustCfAll(), TTimeNet::PlotCCfOverTm(), PlotClustCf(), and TGStat::TakeClustCf().
double TSnap::GetClustCf | ( | const PGraph & | Graph, |
TFltPrV & | DegToCCfV, | ||
int | SampleNodes = -1 |
||
) |
Computes the distribution of average clustering coefficient.
Considers the graph as undirected.
DegToCCfV | Vector of pairs (degree, avg. clustering coefficient of nodes of that degree). |
SampleNodes | If !=-1 then compute clustering coefficient only for a random sample of SampleNodes nodes. Useful for approximate but quick computations. |
Definition at line 151 of file triad.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Empty(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), GetTriads(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Sort(), TInt::Val, TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.
double TSnap::GetClustCf | ( | const PGraph & | Graph, |
TFltPrV & | DegToCCfV, | ||
int64 & | ClosedTriads, | ||
int64 & | OpenTriads, | ||
int | SampleNodes = -1 |
||
) |
Computes the distribution of average clustering coefficient as well as the number of open and closed triads in the graph.
Considers the graph as undirected.
DegToCCfV | Vector of pairs (degree, avg. clustering coefficient of nodes of that degree). |
ClosedTriads | On return contains the number of closed triads. |
OpenTriads | On return contains the number of open triads. |
SampleNodes | If !=-1 then compute clustering coefficient only for a random sample of SampleNodes nodes. Useful for approximate but quick computations. |
Definition at line 178 of file triad.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Empty(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), GetTriads(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Sort(), TInt::Val, TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.
double TSnap::GetClustCfAll | ( | const PGraph & | Graph, |
TFltPrV & | DegToCCfV, | ||
int64 & | ClosedTriadsX, | ||
int64 & | OpenTriadsX, | ||
int | SampleNodes = -1 |
||
) |
Computes the distribution of average clustering coefficient as well as the number of open and closed triads in the graph.
Considers the graph as undirected. This function is a duplicate. It is required by Snap.py.
DegToCCfV | Vector of pairs (degree, avg. clustering coefficient of nodes of that degree). |
ClosedTriads | On return contains the number of closed triads. |
OpenTriads | On return contains the number of open triads. |
SampleNodes | If !=-1 then compute clustering coefficient only for a random sample of SampleNodes nodes. Useful for approximate but quick computations. |
Definition at line 215 of file triad.h.
References GetClustCf().
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 708 of file triad.h.
Referenced by TTimeNENet::GetTriadEdges().
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 715 of file triad.h.
References THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Len(), TMath::Mn(), and TVec< TVal, TSizeTy >::Reserve().
|
inline |
Definition at line 738 of file triad.h.
References TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetNbrNId(), IAssert, and TMath::Mn().
Returns the number of common elements in two sorted TInt vectors.
Definition at line 59 of file triad.cpp.
References TVec< TVal, TSizeTy >::Len().
Referenced by GetTriads(), and GetTriangleCnt().
void TSnap::GetDegCnt | ( | const PGraph & | Graph, |
TIntPrV & | DegToCntV | ||
) |
Returns a degree histogram: a set of pairs (degree, number of nodes of such degree)
Definition at line 223 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Sort().
void TSnap::GetDegCnt | ( | const PGraph & | Graph, |
TFltPrV & | DegToCntV | ||
) |
Returns a degree histogram: a set of pairs (degree, number of nodes of such degree)
Definition at line 234 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Sort().
double TSnap::GetDegreeCentr | ( | const PUNGraph & | Graph, |
const int & | NId | ||
) |
Returns Degree centrality of a given node NId. Degree centrality if a node is defined as its degree/(N-1), where N is the number of nodes in the network.
Definition at line 5 of file centr.cpp.
References TUNGraph::TNodeI::GetDeg(), TUNGraph::GetNI(), and TUNGraph::GetNodes().
void TSnap::GetDegSeqV | ( | const PGraph & | Graph, |
TIntV & | DegV | ||
) |
Returns a degree sequence vector.
Definition at line 245 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Gen().
Referenced by GenConfModel().
void TSnap::GetDegSeqV | ( | const PGraph & | Graph, |
TIntV & | InDegV, | ||
TIntV & | OutDegV | ||
) |
Returns an in- and out-degree sequence vectors.
Definition at line 253 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Gen().
PGraph TSnap::GetEDatSubGraph | ( | const PGraph & | Graph, |
const TEdgeDat & | EDat, | ||
const int & | Cmp | ||
) |
Returns a subgraph of graph Graph with edges where edge data matches the parameters.
EDat provides the value for edge data matching. Cmp determines the comparison function. Edges whose edge data matches EDat are included in the resulting subgraph as well as all the nodes which connect to at least one edge in the subgraph. Node IDs are preserved. Nodes in the resulting subgraph have the same node IDs as nodes in Graph.
Values of Cmp can be -1, 0, or +1. If Cmp is -1, edges with edge data less than EDat are included in the resulting subgraph. If Cmp equals 0, the values of edge data and EDat have to match. If Cmp is +1, edge data has to be greater than EDat.
Definition at line 286 of file subgraph.h.
References CAssert, gfEdgeDat, and HasGraphFlag.
PGraph TSnap::GetEDatSubGraph | ( | const PGraph & | Graph, |
const TIntV & | NIdV, | ||
const TEdgeDat & | EDat, | ||
const int & | Cmp | ||
) |
Returns a subgraph of graph Graph with NIdV nodes and edges where edge data matches the parameters.
The resulting subgraph contains all the nodes from Graph, which have node IDs in the NIdV vector and edges with both nodes in NIdV and whose edge data matches the parameters. Node IDs are preserved. Nodes in the resulting subgraph have the same node IDs as nodes in Graph.
EDat provides the value for edge data matching. Cmp determines the comparison function. Values of Cmp can be -1, 0, or +1. If Cmp is -1, edges with edge data less than EDat are included in the resulting subgraph. If Cmp equals 0, the values of edge data and EDat have to match. If Cmp is +1, edge data has to be greater than EDat.
Definition at line 306 of file subgraph.h.
References CAssert, gfEdgeDat, HasGraphFlag, and TVec< TVal, TSizeTy >::Len().
Returns bridge edges of a Graph.
Edge is a bridge if, when removed, increases the number of connected components. See http://en.wikipedia.org/wiki/Bridge_(graph_theory)
Definition at line 55 of file cncom.cpp.
References THashSet< TKey, THashFunc >::AddKey(), GetBiCon(), THashSet< TKey, THashFunc >::GetKeyV(), TVec< TVal, TSizeTy >::Len(), TMath::Mn(), and TMath::Mx().
Referenced by Get1CnCom(), and Get1CnComSzCnt().
void TSnap::GetEdgesInOut | ( | const PGraph & | Graph, |
const TIntV & | NIdV, | ||
int & | EdgesInX, | ||
int & | EdgesOutX | ||
) |
Returns the number of edges between the nodes NIdV and the edges pointing outside the set NIdV.
EdgesInX | Number of edges between the nodes NIdV. |
EdgesOutX | Number of edges between the nodes in NIdV and the rest of the graph. |
Definition at line 76 of file cmty.h.
References THashSet< TKey, THashFunc >::AddKey(), and TVec< TVal, TSizeTy >::Len().
Referenced by TLocClustStat::TCutInfo::TCutInfo().
Returns the egonet of node CtrNId as center in undirected graph Graph. And returns number of edges around the egonet.
Definition at line 82 of file subgraph.cpp.
References TUNGraph::AddEdge(), TUNGraph::AddNode(), TUNGraph::TNodeI::GetInDeg(), TUNGraph::TNodeI::GetInNId(), TUNGraph::GetNI(), TUNGraph::IsEdge(), TUNGraph::IsNode(), and TUNGraph::New().
Referenced by AddEgonetFeatures().
Returns the egonet of node CtrNId as center in directed graph Graph. And returns number of edges go in and out the egonet.
Definition at line 108 of file subgraph.cpp.
References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::TNodeI::GetDeg(), TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), TNGraph::TNodeI::GetNbrNId(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TNGraph::IsNode(), and TNGraph::New().
Returns the complete egonet of at given radius and copies node and edge attributes.
Definition at line 254 of file subgraph.cpp.
References AddEdgeWithAttributes(), AddNodeWithAttributes(), TSnapQueue< TVal >::Clr(), TSnapQueue< TVal >::Empty(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInEId(), TNEANet::TNodeI::GetInNId(), TNEANet::TNodeI::GetOutDeg(), TNEANet::TNodeI::GetOutEId(), TNEANet::TNodeI::GetOutNId(), TNEANet::IsEdge(), TNEANet::IsNode(), TPt< TRec >::New(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), and TSnapQueue< TVal >::Top().
PGraph TSnap::GetEgonetHop | ( | const PGraph & | Graph, |
const int | CtrNId, | ||
const int | Radius | ||
) |
Returns the egonet of node CtrNId as center for a Graph for a given radius.
Definition at line 506 of file subgraph.h.
References TSnapQueue< TVal >::Clr(), TSnapQueue< TVal >::Empty(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), and TSnapQueue< TVal >::Top().
void TSnap::GetEigenVectorCentr | ( | const PUNGraph & | Graph, |
TIntFltH & | NIdEigenH, | ||
const double & | Eps = 1e-4 , |
||
const int & | MaxIter = 100 |
||
) |
Computes Eigenvector Centrality of all nodes in the network Eigenvector Centrality of a node N is defined recursively as the average of centrality values of N's neighbors in the network.
Definition at line 11 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TUNGraph::BegNI(), TUNGraph::EndNI(), THash< TKey, TDat, THashFunc >::Gen(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::GetKey(), TUNGraph::GetNodes(), IAssert, THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Len().
Computes top EigVals eigenvalues of the adjacency matrix representing a given undirected Graph.
Definition at line 308 of file gsvd.cpp.
References TSparseSVD::Lanczos(), TVec< TVal, TSizeTy >::Len(), TSparseSVD::SimpleLanczos(), TVec< TVal, TSizeTy >::Sort(), and ssotFull.
Referenced by PlotEigValDistr(), and PlotEigValRank().
Computes the leading eigenvector of the adjacency matrix representing a given undirected Graph.
Definition at line 336 of file gsvd.cpp.
References TVVec< TVal, TSizeTy >::GetCol(), IsAllValVNeg(), TSparseSVD::Lanczos(), and ssotFull.
void TSnap::GetEigVec | ( | const PUNGraph & | Graph, |
const int & | EigVecs, | ||
TFltV & | EigValV, | ||
TFltVFltV & | EigVecV | ||
) |
Computes top EigVecs eigenvalues and eigenvectors of the adjacency matrix representing a given undirected Graph.
Definition at line 347 of file gsvd.cpp.
References TVec< TVal, TSizeTy >::Add(), TVVec< TVal, TSizeTy >::GetCol(), TUNGraph::GetNodes(), IsAllValVNeg(), TSparseSVD::Lanczos(), TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Sort(), and ssotFull.
PGraph TSnap::GetESubGraph | ( | const PGraph & | Graph, |
const TIntV & | EIdV | ||
) |
Returns a subgraph of graph Graph with EIdV edges.
The resulting subgraph contains all the edges from Graph, which have edge IDs in the EIdV vector and all the nodes which connect to at least one edge in EIdV. Node and edge IDs are preserved. Nodes and edges in the resulting subgraph have the same IDs as in Graph.
Use this function for multi-graphs, where the edges have edge IDs.
Definition at line 243 of file subgraph.h.
References CAssert, edge, gfMultiGraph, HasGraphFlag, IAssert, and TVec< TVal, TSizeTy >::Len().
Referenced by GetRndESubGraph(), and TTimeNENet::TimeGrowth().
PGraph TSnap::GetESubGraph | ( | const PGraph & | Graph, |
const TIntPrV & | EdgeV | ||
) |
Definition at line 264 of file subgraph.h.
References edge, and TVec< TVal, TSizeTy >::Len().
double TSnap::GetFarnessCentr | ( | const PGraph & | Graph, |
const int & | NId, | ||
const bool & | Normalized = true , |
||
const bool & | IsDir = false |
||
) |
Returns Farness centrality of a given node NId. Farness centrality of a node is the average shortest path length to all other nodes that reside is the same connected component as the given node.
Definition at line 123 of file centr.h.
References THashKeyDatI< TKey, TDat >::EndI, and TInt::Mx.
double TSnap::GetFarnessCentrMP | ( | const PGraph & | Graph, |
const int & | NId, | ||
const bool & | Normalized = true , |
||
const bool & | IsDir = false |
||
) |
Definition at line 142 of file centr.h.
References THashKeyDatI< TKey, TDat >::EndI, and TInt::Mx.
TStr TSnap::GetFlagStr | ( | const TGraphFlag & | GraphFlag | ) |
Returns a string representation of a flag.
Definition at line 5 of file gbase.cpp.
References FailR, gfBipart, gfDirected, gfEdgeDat, gfMultiGraph, gfNodeDat, gfSources, and gfUndef.
Referenced by TBigNet< TNodeData, IsDir >::DumpFlags(), and PrintInfo().
PGraph TSnap::GetGraphUnion | ( | PGraph & | DstGraph, |
const PGraph & | SrcGraph | ||
) |
Definition at line 764 of file subgraph.h.
References gfMultiGraph, and HasGraphFlag.
Definition at line 521 of file subgraph.cpp.
References AddEdgeWithAttributes(), and AddNodeWithAttributes().
Returns Group Degree centrality of a given group NId. Degree centrality if a node is defined as its degree/(N-1), where N is the number of nodes in the network.
Definition at line 169 of file centr.cpp.
References GetGroupFarnessCentr().
Definition at line 59 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TUNGraph::BegNI(), TUNGraph::EndNI(), TUNGraph::TNodeI::GetId(), TUNGraph::GetNI(), TUNGraph::IsNode(), and THash< TKey, TDat, THashFunc >::Len().
Returns Group Degree centrality of a given group NId. Degree centrality if a node is defined as its degree/(N-1), where N is the number of nodes in the network.
Definition at line 85 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), THash< TKey, TDat, THashFunc >::IsKey(), and THash< TKey, TDat, THashFunc >::Len().
Definition at line 72 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::GetDat(), TUNGraph::GetNI(), THash< TKey, TDat, THashFunc >::IsKey(), and THash< TKey, TDat, THashFunc >::Len().
Definition at line 105 of file centr.cpp.
References TUNGraph::BegNI(), TUNGraph::EndNI(), THash< TKey, TDat, THashFunc >::GetDat(), TUNGraph::GetNodes(), THash< TKey, TDat, THashFunc >::Len(), and TInt::Mx.
Referenced by GetGroupClosenessCentr().
void TSnap::GetHits | ( | const PGraph & | Graph, |
TIntFltH & | NIdHubH, | ||
TIntFltH & | NIdAuthH, | ||
const int & | MaxIter = 20 |
||
) |
HITS: Hubs and Authorities For more info see: http://en.wikipedia.org/wiki/HITS_algorithm)
Definition at line 524 of file centr.h.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Gen(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::Len(), and TMath::Sqr().
Referenced by MapHits().
void TSnap::GetHitsMP | ( | const PGraph & | Graph, |
TIntFltH & | NIdHubH, | ||
TIntFltH & | NIdAuthH, | ||
const int & | MaxIter = 20 |
||
) |
Definition at line 569 of file centr.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Gen(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::Len(), and TMath::Sqr().
void TSnap::GetInDegCnt | ( | const PGraph & | Graph, |
TIntPrV & | DegToCntV | ||
) |
Returns an in-degree histogram: a set of pairs (in-degree, number of nodes of such in-degree)
Definition at line 179 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Sort().
Referenced by PlotInDegDistr(), and TGStat::TakeDegDistr().
void TSnap::GetInDegCnt | ( | const PGraph & | Graph, |
TFltPrV & | DegToCntV | ||
) |
Returns an in-degree histogram: a set of pairs (in-degree, number of nodes of such in-degree)
Definition at line 190 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Sort().
Returns the in-egonet of at given radius and copies node and edge attributes.
Definition at line 342 of file subgraph.cpp.
References AddEdgeWithAttributes(), AddNodeWithAttributes(), TSnapQueue< TVal >::Clr(), TSnapQueue< TVal >::Empty(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInEId(), TNEANet::TNodeI::GetInNId(), TNEANet::TNodeI::GetOutDeg(), TNEANet::TNodeI::GetOutEId(), TNEANet::TNodeI::GetOutNId(), TNEANet::IsEdge(), TNEANet::IsNode(), TPt< TRec >::New(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), and TSnapQueue< TVal >::Top().
PGraph TSnap::GetInEgonetHop | ( | const PGraph & | Graph, |
const int | CtrNId, | ||
const int | Radius | ||
) |
Returns the in-egonet of node CtrNId as center in directed graph Graph for a given radius.
Definition at line 589 of file subgraph.h.
References TSnapQueue< TVal >::Clr(), TSnapQueue< TVal >::Empty(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), and TSnapQueue< TVal >::Top().
PGraph TSnap::GetInEgonetSub | ( | const PGraph & | Graph, |
const int | CtrNId, | ||
const int | Radius, | ||
const int | MaxNum = 2 , |
||
const float | percent = -1.0 |
||
) |
Returns the randomly sampled in-egonet with nodes sampled based on percentage, if percent != -1.0, or MaxNum nodes otherwise.
Definition at line 695 of file subgraph.h.
References TSnapQueue< TVal >::Clr(), TSnapQueue< TVal >::Empty(), TSnapQueue< TVal >::Len(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), TSnapQueue< TVal >::Sample(), and TSnapQueue< TVal >::Top().
PNEANet TSnap::GetInEgonetSubAttr | ( | const PNEANet & | Graph, |
const int | CtrNId, | ||
const int | Radius, | ||
const int | MaxNum, | ||
const float | percent | ||
) |
Returns the randomly sampled egonet with nodes sampled based on percentage or raw number, copying attributes.
Definition at line 453 of file subgraph.cpp.
References AddEdgeWithAttributes(), AddNodeWithAttributes(), TSnapQueue< TVal >::Clr(), TSnapQueue< TVal >::Empty(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInNId(), TNEANet::TNodeI::GetOutDeg(), TNEANet::TNodeI::GetOutNId(), TNEANet::IsEdge(), TNEANet::IsNode(), TSnapQueue< TVal >::Len(), TNEANet::New(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), TSnapQueue< TVal >::Sample(), and TSnapQueue< TVal >::Top().
void TSnap::GetInvParticipRat | ( | const PUNGraph & | Graph, |
int | MaxEigVecs, | ||
int | TimeLimit, | ||
TFltPrV & | EigValIprV | ||
) |
Computes Inverse participation ratio of a given graph. See Spectra of "real-world" graphs: Beyond the semicircle law by Farkas, Derenyi, Barabasi and Vicsek
Definition at line 378 of file gsvd.cpp.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Empty(), TVVec< TVal, TSizeTy >::GetCol(), TVVec< TVal, TSizeTy >::GetCols(), TSnap::TSnapDetail::GetInvParticipRatEig(), TUNGraph::GetNodes(), TExeTm::GetStr(), TSparseSVD::Lanczos2(), TVec< TVal, TSizeTy >::Len(), TMath::Mn(), TVec< TVal, TSizeTy >::Sort(), and ssotFull.
Referenced by PlotInvParticipRat().
PGraph TSnap::GetKCore | ( | const PGraph & | Graph, |
const int & | K | ||
) |
Returns the K-core of a graph. If the core of order K does not exist the function returns an empty graph.
Definition at line 106 of file kcore.h.
References TKCore< PGraph >::GetCoreK(), TKCore< PGraph >::GetNIdV(), and GetSubGraph().
Referenced by ChibaNishizekiWeighter::Initialize().
int TSnap::GetKCoreEdges | ( | const PGraph & | Graph, |
TIntPrV & | CoreIdSzV | ||
) |
Returns the number of edges in each core of order K (where K=0, 1, ...)
Definition at line 126 of file kcore.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), TKCore< PGraph >::GetCoreEdges(), TKCore< PGraph >::GetCurK(), and TKCore< PGraph >::GetNextCore().
Referenced by PlotKCoreEdges().
int TSnap::GetKCoreNodes | ( | const PGraph & | Graph, |
TIntPrV & | CoreIdSzV | ||
) |
Returns the number of nodes in each core of order K (where K=0, 1, ...)
Definition at line 114 of file kcore.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), TKCore< PGraph >::GetCoreNodes(), TKCore< PGraph >::GetCurK(), and TKCore< PGraph >::GetNextCore().
Referenced by PlotKCoreNodes().
int TSnap::GetLen2Paths | ( | const PGraph & | Graph, |
const int & | NId1, | ||
const int & | NId2 | ||
) |
Returns the number of length 2 directed paths between a pair of nodes NId1, NId2 (NId1 –> U –> NId2).
Definition at line 761 of file triad.h.
int TSnap::GetLen2Paths | ( | const PGraph & | Graph, |
const int & | NId1, | ||
const int & | NId2, | ||
TIntV & | NbrV | ||
) |
Returns the 2 directed paths between a pair of nodes NId1, NId2 (NId1 –> U –> NId2).
NbrV intermediary stores nodes U.
Definition at line 769 of file triad.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Reserve().
TTableIterator TSnap::GetMapHitsIterator | ( | const TVec< PNEANet > & | GraphSeq, |
TTableContext * | Context, | ||
const int & | MaxIter = 20 |
||
) |
Gets sequence of Hits tables from given GraphSeq
.
Definition at line 917 of file centr.cpp.
References TVec< TVal, TSizeTy >::Len(), and MapHits().
TTableIterator TSnap::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
.
Definition at line 907 of file centr.cpp.
References TVec< TVal, TSizeTy >::Len(), and MapPageRank().
int TSnap::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
.
Implements max flow using the Edmonds-Karp algorithm. http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm Although the asymptotic run time of Edmonds-Karp is worse than that of Push Relabel, in practice Edmonds Karp works very well, especially if the network is sparse. Unless the degree of each node is on the order of the number of nodes, it is best to use Edmonds Karp over Push Relabel.
Definition at line 105 of file flow.cpp.
References CapAttrName, FindAugV(), TNEANet::TEdgeI::GetDstNId(), TNEANet::TEdgeI::GetSrcNId(), IAssert, and TVec< TVal, TSizeTy >::Len().
int TSnap::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
.
Implements max flow using the Edmonds-Karp algorithm. http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm Although the asymptotic run time of Edmonds-Karp is worse than that of Push Relabel, in practice Edmonds Karp works very well, especially if the network is sparse. Unless the degree of each node is on the order of the number of nodes, it is best to use Edmonds Karp over Push Relabel.
Definition at line 410 of file flow.cpp.
References TSnap::TPRManager::Capacity(), TSnap::TPRManager::Excess(), TSnap::TPRManager::Flow(), TSnap::TPRManager::GetMaxLabel(), TNEANet::TNodeI::GetOutDeg(), TNEANet::TNodeI::GetOutEId(), TNEANet::TNodeI::GetOutNId(), GlobalRelabel(), TSnap::TPRManager::HasActive(), IAssert, TSnap::TPRManager::IsActive(), TSnap::TPRManager::Label(), TSnap::TPRManager::PopActive(), TSnap::TPRManager::PushActive(), PushRelabel(), and TSnap::TPRManager::SetLabel().
double TSnap::GetModularity | ( | const PGraph & | G, |
const TIntV & | NIdV, | ||
int | GEdges = -1 |
||
) |
Computes Modularity score of a set of nodes NIdV in a graph G. The function runs much faster if the number of edges in graph G is given (GEdges parameter).
Definition at line 46 of file cmty.h.
References THashSet< TKey, THashFunc >::AddKey(), and TVec< TVal, TSizeTy >::Len().
Referenced by GetModularity().
double TSnap::GetModularity | ( | const PGraph & | G, |
const TCnComV & | CmtyV, | ||
int | GEdges = -1 |
||
) |
Computes Modularity score of a set of communities (each community is defined by its member nodes) in a graph G. The function runs much faster if the number of edges in graph G is given (GEdges parameter).
Definition at line 66 of file cmty.h.
References GetModularity(), and TVec< TVal, TSizeTy >::Len().
PGraph TSnap::GetMxBiCon | ( | const PGraph & | Graph | ) |
Returns a graph representing the largest bi-connected component on an input Graph.
An undirected graph is bi-connected if by removing any single node does not disconnect the graph. http://en.wikipedia.org/wiki/Biconnected_component
Definition at line 486 of file cncom.h.
References TVec< TVal, TSizeTy >::Empty(), GetBiCon(), GetSubGraph(), and TVec< TVal, TSizeTy >::Len().
Returns a graph representing the largest bi-connected component on an undirected Graph.
An undirected graph is bi-connected if by removing any single node does not disconnect the graph. http://en.wikipedia.org/wiki/Biconnected_component
Definition at line 126 of file cncom.cpp.
References TVec< TVal, TSizeTy >::Empty(), GetBiCon(), GetSubGraph(), and TVec< TVal, TSizeTy >::Len().
Referenced by TGStat::TakeBccStat().
int TSnap::GetMxDegNId | ( | const PGraph & | Graph | ) |
Returns a randomly chosen node from all the nodes with the maximum degree.
Definition at line 143 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), EAssertR, TVec< TVal, TSizeTy >::Empty(), TRnd::GetUniDevInt(), TVec< TVal, TSizeTy >::Len(), and TInt::Rnd.
int TSnap::GetMxInDegNId | ( | const PGraph & | Graph | ) |
Returns a randomly chosen node from all the nodes with the maximum in-degree.
Definition at line 155 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), EAssertR, TVec< TVal, TSizeTy >::Empty(), TRnd::GetUniDevInt(), TVec< TVal, TSizeTy >::Len(), and TInt::Rnd.
int TSnap::GetMxOutDegNId | ( | const PGraph & | Graph | ) |
Returns a randomly chosen node from all the nodes with the maximum out-degree.
Definition at line 167 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), EAssertR, TVec< TVal, TSizeTy >::Empty(), TRnd::GetUniDevInt(), TVec< TVal, TSizeTy >::Len(), and TInt::Rnd.
PGraph TSnap::GetMxScc | ( | const PGraph & | Graph | ) |
Returns a graph representing the largest strongly connected component on an input Graph.
A directed graph is strongly connected if there exists a directed path from any vertex to any other vertex in the graph. See http://en.wikipedia.org/wiki/Strongly_connected_component
Definition at line 469 of file cncom.h.
References TVec< TVal, TSizeTy >::Empty(), GetSccs(), GetSubGraph(), and TVec< TVal, TSizeTy >::Len().
Referenced by TGStat::TakeSccStat().
double TSnap::GetMxSccSz | ( | const PGraph & | Graph | ) |
Returns the fraction of nodes in the largest strongly connected component of a Graph.
Definition at line 444 of file cncom.h.
References GetSccs(), and TVec< TVal, TSizeTy >::Len().
Referenced by PrintInfo().
PGraph TSnap::GetMxWcc | ( | const PGraph & | Graph | ) |
Returns a graph representing the largest weakly connected component on an input Graph.
A directed/undirected graph is connected if there exist an undirected path between any pair of nodes. See http://en.wikipedia.org/wiki/Connected_component_(graph_theory)
Definition at line 452 of file cncom.h.
References TVec< TVal, TSizeTy >::Empty(), GetSubGraph(), GetWccs(), and TVec< TVal, TSizeTy >::Len().
Referenced by main(), TKronMtx::PlotCmpGraphs(), TTimeNet::PlotEffDiam(), TTimeNENet::PlotEffDiam(), TTimeNet::PlotMissingPast(), TLocClustStat::Run(), and TGStat::TakeStat().
double TSnap::GetMxWccSz | ( | const PGraph & | Graph | ) |
Returns the fraction of nodes in the largest weakly connected component of a Graph.
Definition at line 436 of file cncom.h.
References GetWccs(), and TVec< TVal, TSizeTy >::Len().
Referenced by PrintInfo().
double TSnap::GetNodeClustCf | ( | const PGraph & | Graph, |
const int & | NId | ||
) |
Returns clustering coefficient of a particular node.
Considers the graph as undirected.
Definition at line 220 of file triad.h.
References GetNodeTriads().
void TSnap::GetNodeClustCf | ( | const PGraph & | Graph, |
TIntFltH & | NIdCCfH | ||
) |
Computes clustering coefficient of each node of the Graph.
Considers the graph as undirected.
Definition at line 228 of file triad.h.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Clr(), GetTriads(), and TVec< TVal, TSizeTy >::Len().
int TSnap::GetNodeEcc | ( | const PGraph & | Graph, |
const int & | NId, | ||
const bool & | IsDir = false |
||
) |
Returns node Eccentricity, the largest shortest-path distance from the node NId to any other node in the Graph.
IsDir | false: ignore edge directions and consider edges as undirected (in case they are directed). |
Definition at line 177 of file centr.h.
References TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::Len(), TInt::Mx, and TBreathFS< PGraph >::NIdDistH.
void TSnap::GetNodeInDegV | ( | const PGraph & | Graph, |
TIntPrV & | NIdInDegV | ||
) |
Returns a vector of pairs (node id, node in-degree)
Definition at line 263 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Reserve().
void TSnap::GetNodeOutDegV | ( | const PGraph & | Graph, |
TIntPrV & | NIdOutDegV | ||
) |
Returns a vector of pairs (node id, node out-degree)
Definition at line 271 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Reserve().
int TSnap::GetNodesAtHop | ( | const PGraph & | Graph, |
const int & | StartNId, | ||
const int & | Hop, | ||
TIntV & | NIdV, | ||
const bool & | IsDir = false |
||
) |
Finds IDs of all nodes that are at distance Hop from node StartNId.
false: ignore edge directions and consider edges/paths as undirected (in case they are directed).
Definition at line 375 of file bfsdfs.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), and TBreathFS< PGraph >::NIdDistH.
int TSnap::GetNodesAtHops | ( | const PGraph & | Graph, |
const int & | StartNId, | ||
TIntPrV & | HopCntV, | ||
const bool & | IsDir = false |
||
) |
Returns the number of nodes at each hop distance from the starting node StartNId.
false: ignore edge directions and consider edges/paths as undirected (in case they are directed).
Definition at line 387 of file bfsdfs.h.
References THash< TKey, TDat, THashFunc >::AddDat(), TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::GetKeyDatPrV(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TInt::Mx, TBreathFS< PGraph >::NIdDistH, and TVec< TVal, TSizeTy >::Sort().
int TSnap::GetNodeTriads | ( | const PGraph & | Graph, |
const int & | NId | ||
) |
Returns the number of undirected triads a node NId
participates in.
Considers the graph as undirected.
Graph | Input graph |
NId | Input node |
Definition at line 615 of file triad.h.
Referenced by GetNodeClustCf(), GetNodeTriadsAll(), and GetTriadParticip().
int TSnap::GetNodeTriads | ( | const PGraph & | Graph, |
const int & | NId, | ||
int & | ClosedNTriadsX, | ||
int & | OpenNTriadsX | ||
) |
Returns number of Open and Closed triads a node NId
participates in.
Considers the graph as undirected.
Graph | Input graph |
NId | Input node |
ClosedNTriadsX | On return contains the number of closed triads. |
OpenNTriadsX | On return contains the number of open triads. |
Definition at line 622 of file triad.h.
References THashSet< TKey, THashFunc >::AddKey(), and gfDirected.
int TSnap::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
.
Considers the graph as undirected.
Graph | Input graph |
NId | Input node |
GroupSet | Input set with node neighbors |
InGroupEdgesX | On return contains the number of triads (NId, G1, G2), where G1 and G2 are in GroupSet. |
InOutGroupEdgesX | On return contains the number of triads (NId, G1, O1), where G1 is in GroupSet and O1 not in GroupSet. |
OutGroupEdgesX | On return contains the number of triads (NId, O1, O2), where O1 and O2 are not in GroupSet. |
Definition at line 660 of file triad.h.
References THashSet< TKey, THashFunc >::AddKey(), gfDirected, and THashSet< TKey, THashFunc >::IsKey().
int TSnap::GetNodeTriadsAll | ( | const PGraph & | Graph, |
const int & | NId, | ||
int & | ClosedNTriadsX, | ||
int & | OpenNTriadsX | ||
) |
Returns number of Open and Closed triads a node NId
participates in.
Considers the graph as undirected. This function is a duplicate. It is required by Snap.py.
Graph | Input graph |
NId | Input node |
ClosedNTriadsX | On return contains the number of closed triads. |
OpenNTriadsX | On return contains the number of open triads. |
Definition at line 651 of file triad.h.
References GetNodeTriads().
void TSnap::GetNodeWcc | ( | const PGraph & | Graph, |
const int & | NId, | ||
TIntV & | CnCom | ||
) |
Returns (via output parameter CnCom) all nodes that are in the same connected component as node NId.
Definition at line 277 of file cncom.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Gen(), gfDirected, HasGraphFlag, and TSnapQueue< TVal >::Push().
Referenced by TSnap::TSnapDetail::CmtyGirvanNewmanStep().
void TSnap::GetOutDegCnt | ( | const PGraph & | Graph, |
TIntPrV & | DegToCntV | ||
) |
Returns an out-degree histogram: a set of pairs (out-degree, number of nodes of such out-degree)
Definition at line 201 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Sort().
Referenced by PlotOutDegDistr(), and TGStat::TakeDegDistr().
void TSnap::GetOutDegCnt | ( | const PGraph & | Graph, |
TFltPrV & | DegToCntV | ||
) |
Returns an out-degree histogram: a set of pairs (out-degree, number of nodes of such out-degree)
Definition at line 212 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Sort().
Returns the out-egonet of at given radius and copies node and edge attributes.
Definition at line 397 of file subgraph.cpp.
References AddEdgeWithAttributes(), AddNodeWithAttributes(), TSnapQueue< TVal >::Clr(), TSnapQueue< TVal >::Empty(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInEId(), TNEANet::TNodeI::GetInNId(), TNEANet::TNodeI::GetOutDeg(), TNEANet::TNodeI::GetOutEId(), TNEANet::TNodeI::GetOutNId(), TNEANet::IsEdge(), TNEANet::IsNode(), TPt< TRec >::New(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), and TSnapQueue< TVal >::Top().
PGraph TSnap::GetOutEgonetHop | ( | const PGraph & | Graph, |
const int | CtrNId, | ||
const int | Radius | ||
) |
Returns the out-egonet of node CtrNId as center in directed graph Graph for a given radius.
Definition at line 642 of file subgraph.h.
References TSnapQueue< TVal >::Clr(), TSnapQueue< TVal >::Empty(), TSnapQueue< TVal >::Pop(), TSnapQueue< TVal >::Push(), and TSnapQueue< TVal >::Top().
void TSnap::GetPageRank | ( | const PGraph & | Graph, |
TIntFltH & | PRankH, | ||
const double & | C = 0.85 , |
||
const double & | Eps = 1e-4 , |
||
const int & | MaxIter = 100 |
||
) |
PageRank For more info see: http://en.wikipedia.org/wiki/PageRank
Definition at line 240 of file centr.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Gen(), and TVec< TVal, TSizeTy >::Len().
Referenced by MapPageRank().
void TSnap::GetPageRank_v1 | ( | const PGraph & | Graph, |
TIntFltH & | PRankH, | ||
const double & | C = 0.85 , |
||
const double & | Eps = 1e-4 , |
||
const int & | MaxIter = 100 |
||
) |
Definition at line 200 of file centr.h.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Gen(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Len().
void TSnap::GetPageRankMP | ( | const PGraph & | Graph, |
TIntFltH & | PRankH, | ||
const double & | C = 0.85 , |
||
const double & | Eps = 1e-4 , |
||
const int & | MaxIter = 100 |
||
) |
Definition at line 306 of file centr.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Gen(), and TVec< TVal, TSizeTy >::Len().
double TSnap::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 |
||
) |
Definition at line 88 of file randwalk.h.
References anonymous_namespace{randwalk.h}::ApproxContributionsBalanced(), THash< TKey, TDat, THashFunc >::GetDatWithDefault(), TVec< TVal, TSizeTy >::Len(), SamplePersonalizedPageRank(), and anonymous_namespace{randwalk.h}::WallClockTime().
Referenced by GetRndWalkRestartBidirectional().
PGraph TSnap::GetRndESubGraph | ( | const PGraph & | Graph, |
const int & | NEdges | ||
) |
Returns a random subgraph of graph Graph with NEdges edges.
Randomly selects NEdges edges from the input graph and returns a subgraph on those edges.
Definition at line 490 of file subgraph.h.
References TVec< TVal, TSizeTy >::Add(), CAssert, GetESubGraph(), gfMultiGraph, HasGraphFlag, IAssert, and TInt::Rnd.
PGraph TSnap::GetRndSubGraph | ( | const PGraph & | Graph, |
const int & | NNodes | ||
) |
Returns an induced random subgraph of graph Graph with NNodes nodes.
Randomly selects NNodes nodes from the input graph and returns an induced graph on those nodes.
Definition at line 479 of file subgraph.h.
References TVec< TVal, TSizeTy >::Del(), GetSubGraph(), IAssert, TVec< TVal, TSizeTy >::Len(), TInt::Rnd, and TVec< TVal, TSizeTy >::Shuffle().
double TSnap::GetRndWalkRestartBidirectional | ( | const PGraph & | Graph, |
double | JumpProb, | ||
int | StartNId, | ||
int | TargetNId, | ||
double | minProbability = -1.0 , |
||
double | relativeError = 0.1 , |
||
bool | proveRelativeError = false , |
||
bool | PrintTimeForTuning = false |
||
) |
Definition at line 135 of file randwalk.h.
References GetPersonalizedPageRankBidirectional(), and TVec< TInt >::GetV().
void TSnap::GetSccs | ( | const PGraph & | Graph, |
TCnComV & | CnComV | ||
) |
Returns all strongly connected components in a Graph.
CnComV | is a vector of connected components. Each component is defined by the IDs of its member nodes. |
Definition at line 428 of file cncom.h.
References TSccVisitor< PGraph, OnlyCount >::CnComV, TCnCom::GetDfsVisitor(), and TVec< TVal, TSizeTy >::Sort().
Referenced by GetMxScc(), and GetMxSccSz().
void TSnap::GetSccSzCnt | ( | const PGraph & | Graph, |
TIntPrV & | SccSzCnt | ||
) |
Returns a distribution of strongly connected component sizes.
SccSzCnt | returns a set of pairs (number of nodes in the component, number of such components) |
Definition at line 420 of file cncom.h.
References TCnCom::GetDfsVisitor(), THash< TKey, TDat, THashFunc >::GetKeyDatPrV(), TSccVisitor< PGraph, OnlyCount >::SccCntH, and TVec< TVal, TSizeTy >::Sort().
Referenced by PlotSccDistr(), and TGStat::TakeConnComp().
int TSnap::GetShortestDistances | ( | const PGraph & | Graph, |
const int & | StartNId, | ||
const bool & | FollowOut, | ||
const bool & | FollowIn, | ||
TIntV & | ShortestDists | ||
) |
Definition at line 501 of file bfsdfs.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Empty(), TVec< TVal, TSizeTy >::Gen(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), TStdOut::New(), and TVec< TVal, TSizeTy >::Reduce().
int TSnap::GetShortestDistancesMP2 | ( | const PGraph & | Graph, |
const int & | StartNId, | ||
const bool & | FollowOut, | ||
const bool & | FollowIn, | ||
TIntV & | ShortestDists | ||
) |
Definition at line 545 of file bfsdfs.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::AddMP(), TVec< TVal, TSizeTy >::Empty(), TVec< TVal, TSizeTy >::Gen(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), and TVec< TVal, TSizeTy >::Reduce().
int TSnap::GetShortPath | ( | const PGraph & | Graph, |
const int & | SrcNId, | ||
const int & | DstNId, | ||
const bool & | IsDir = false |
||
) |
Returns the length of the shortest path from node SrcNId to node DstNId.
IsDir | false: ignore edge directions and consider edges/paths as undirected (in case they are directed). |
Definition at line 409 of file bfsdfs.h.
References TBreathFS< PGraph >::DoBfs(), TBreathFS< PGraph >::GetHops(), and TInt::Mx.
int TSnap::GetShortPath | ( | const PGraph & | Graph, |
const int & | SrcNId, | ||
TIntH & | NIdToDistH, | ||
const bool & | IsDir = false , |
||
const int & | MaxDist = TInt::Mx |
||
) |
Returns the length of the shortest path from node SrcNId to all other nodes in the network.
IsDir | false: ignore edge directions and consider edges/paths as undirected (in case they are directed). |
MaxDist | Maximum number of hops that BFS expands to. This is helpful for speeding-up the code if one in interested only in nodes less than MaxDist away from SrcNId. |
NIdToDistH | Maps node ID to shortest path distance. NIdToDistH contains only nodes that are reachable from SrcNId. |
Definition at line 400 of file bfsdfs.h.
References THash< TKey, TDat, THashFunc >::Clr(), TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::Len(), TBreathFS< PGraph >::NIdDistH, and THash< TKey, TDat, THashFunc >::Swap().
Computes largest SngVals singular values of the adjacency matrix representing a directed Graph.
Definition at line 175 of file gsvd.cpp.
References THash< TKey, TDat, THashFunc >::AddKey(), TVVec< TVal, TSizeTy >::At(), THash< TKey, TDat, THashFunc >::GetKeyId(), IAssert, TSparseSVD::LanczosSVD(), TVec< TVal, TSizeTy >::Len(), TSparseSVD::SimpleLanczosSVD(), TVec< TVal, TSizeTy >::Sort(), ssotFull, and TSvd::Svd1Based().
Referenced by TKroneckerLL::GradDescentConvergence(), PlotSngValDistr(), PlotSngValRank(), and TGStat::TakeSpectral().
Computes the leading left and right singular vector of the adjacency matrix representing a directed Graph.
Definition at line 225 of file gsvd.cpp.
References THash< TKey, TDat, THashFunc >::AddKey(), TVVec< TVal, TSizeTy >::At(), TVVec< TVal, TSizeTy >::GetCol(), THash< TKey, TDat, THashFunc >::GetKeyId(), IsAllValVNeg(), TSparseSVD::LanczosSVD(), TVec< TVal, TSizeTy >::Len(), TFlt::Mn, ssotFull, and TSvd::Svd1Based().
Referenced by PlotSngVec(), and TGStat::TakeSpectral().
void TSnap::GetSngVec | ( | const PNGraph & | Graph, |
const int & | SngVecs, | ||
TFltV & | SngValV, | ||
TFltVFltV & | LeftSV, | ||
TFltVFltV & | RightSV | ||
) |
Computes the singular values and left and right singular vectors of the adjacency matrix representing a directed Graph.
SngVecs | Number of singular values/vectors to compute. |
Definition at line 261 of file gsvd.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddKey(), TVVec< TVal, TSizeTy >::At(), TVec< TVal, TSizeTy >::Clr(), TVVec< TVal, TSizeTy >::GetCol(), THash< TKey, TDat, THashFunc >::GetKeyId(), IsAllValVNeg(), TSparseSVD::LanczosSVD(), TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Sort(), ssotFull, and TSvd::Svd1Based().
PUNGraph TSnap::GetSubGraph | ( | const PUNGraph & | Graph, |
const TIntV & | NIdV, | ||
const bool & | RenumberNodes = false |
||
) |
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumbering.
The resulting subgraph contains all the nodes from Graph, which have node IDs in the NIdV vector and all the edges with both nodes in NIdV. Parameter RenumberNodes determines, whether the node IDs are preserved or not. If RenumberNodes is false, then nodes in the resulting subgraph have the same node IDs as nodes in Graph. If RenumberNodes is true, then nodes in the resulting subgraph are renumbered sequentially from 0 to N-1. By default, the nodes are not renumbered.
Definition at line 7 of file subgraph.cpp.
References TUNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TUNGraph::AddNode(), edge, TUNGraph::GetNI(), TUNGraph::TNodeI::GetOutDeg(), TUNGraph::TNodeI::GetOutNId(), TUNGraph::IsNode(), TVec< TVal, TSizeTy >::Len(), TUNGraph::New(), and TUNGraph::Reserve().
Referenced by ProcessedGraph::countClique(), ProcessedGraph::countDirTriadMotif(), TCodaAnalyzer::Draw2ModeCommunity(), TLocClust::DrawWhiskers(), TKCore< PGraph >::GetCoreG(), GetKCore(), GetMxBiCon(), GetMxScc(), GetMxWcc(), GetRndSubGraph(), GetSubGraphRenumber(), TTimeNet::PlotCCfOverTm(), TTimeNet::PlotMedianDegOverTm(), TTimeNet::PlotMissingPast(), TLocClustStat::PlotPhiInOut(), TAGMFast::SetGraph(), TCoda::SetGraph(), TKroneckerLL::SetGraph(), TCesna::SetGraph(), and TMAGFitBern::SetGraph().
PGraph TSnap::GetSubGraph | ( | const PGraph & | Graph, |
const TIntV & | NIdV | ||
) |
Returns an induced subgraph of graph Graph with NIdV nodes.
The resulting subgraph contains all the nodes from Graph, which have node IDs in the NIdV vector and all the edges with both nodes in NIdV. Node IDs are preserved. Nodes in the resulting subgraph have the same node IDs as nodes in Graph.
Definition at line 232 of file subgraph.h.
PNGraph TSnap::GetSubGraph | ( | const PNGraph & | Graph, |
const TIntV & | NIdV, | ||
const bool & | RenumberNodes | ||
) |
Definition at line 45 of file subgraph.cpp.
References TNGraph::AddEdge(), THashSet< TKey, THashFunc >::AddKey(), TNGraph::AddNode(), edge, TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TVec< TVal, TSizeTy >::Len(), TNGraph::New(), and TNGraph::Reserve().
PGraph TSnap::GetSubGraphRenumber | ( | const PGraph & | Graph, |
const TIntV & | NIdV | ||
) |
Returns an induced subgraph of graph Graph with NIdV nodes with an node renumbering.
The resulting subgraph contains all the nodes from Graph, which have node IDs in the NIdV vector and all the edges with both nodes in NIdV. Node IDs are preserved. Nodes in the resulting subgraph have the same node IDs as nodes in Graph.
Definition at line 238 of file subgraph.h.
References GetSubGraph().
int TSnap::GetSubTreeSz | ( | const PGraph & | Graph, |
const int & | StartNId, | ||
const bool & | FollowOut, | ||
const bool & | FollowIn, | ||
int & | TreeSzX, | ||
int & | TreeDepthX | ||
) |
Returns the BFS tree size (number of nodes) and depth (number of levels) by following in-links (parameter FollowIn = true) and/or out-links (parameter FollowOut = true) of node StartNId.
Definition at line 363 of file bfsdfs.h.
References TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::Len(), TMath::Mx(), TInt::Mx, and TBreathFS< PGraph >::NIdDistH.
int TSnap::GetTreeRootNId | ( | const PGraph & | Graph | ) |
void TSnap::GetTreeSig | ( | const PGraph & | Graph, |
const int & | RootNId, | ||
TIntV & | Sig | ||
) |
Definition at line 484 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), CAssert, TVec< TVal, TSizeTy >::Gen(), gfDirected, HasGraphFlag, IAssert, TVec< TVal, TSizeTy >::Len(), TSnapQueue< TVal >::Push(), and TVec< TVal, TSizeTy >::QSort().
Referenced by TGHash< TDat >::AddKey(), TGHash< TDat >::GetNodeMap(), and TGHash< TDat >::IsGetKeyId().
void TSnap::GetTreeSig | ( | const PGraph & | Graph, |
const int & | RootNId, | ||
TIntV & | Sig, | ||
TIntPrV & | NodeMap | ||
) |
Definition at line 511 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), CAssert, TVec< TVal, TSizeTy >::Gen(), gfDirected, HasGraphFlag, IAssert, TVec< TVal, TSizeTy >::Len(), TSnapQueue< TVal >::Push(), and TVec< TVal, TSizeTy >::QSort().
int TSnap::GetTriadEdges | ( | const PGraph & | Graph, |
int | SampleEdges = -1 |
||
) |
Counts the number of edges that participate in at least one triad.
Considers the graph as undirected.
SampleNodes | If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations. |
Definition at line 579 of file triad.h.
References THashSet< TKey, THashFunc >::AddKey(), THashSet< TKey, THashFunc >::Clr(), gfDirected, and THashSet< TKey, THashFunc >::IsKey().
void TSnap::GetTriadParticip | ( | const PGraph & | Graph, |
TIntPrV & | TriadCntV | ||
) |
Triangle Participation Ratio: For each node counts how many triangles it participates in and then returns a set of pairs (number of triangles, number of such nodes).
Considers the graph as undirected.
Definition at line 697 of file triad.h.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::GetKeyDatPrV(), GetNodeTriads(), and TVec< TVal, TSizeTy >::Sort().
Referenced by TGStat::TakeTriadPart().
int64 TSnap::GetTriads | ( | const PGraph & | Graph, |
int | SampleNodes = -1 |
||
) |
Returns the number of triangles in a graph.
The function returns the number of unique triples of connected nodes (regardless of the number of edges between each pair of nodes). In other words, the function consideres the Graph as a simple undirected graph.
SampleNodes | If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations. |
Definition at line 240 of file triad.h.
References GetTriads().
void TSnap::GetTriads | ( | const PGraph & | Graph, |
TIntTrV & | NIdCOTriadV, | ||
int | SampleNodes = -1 |
||
) |
Computes the number of open and close triads for every node of the network.
Considers the graph as undirected.
NIdCOTriadV | Triple (node id, open triads: number of pairs of node's neighbors that are not connected, closed triads: number of pairs of node's neighbors that are connected between themselves). |
SampleNodes | If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations. |
Definition at line 318 of file triad.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), GetCommon(), GetUniqueNbrV(), gfDirected, TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Reduce(), TVec< TVal, TSizeTy >::Reserve(), and TVec< TVal, TSizeTy >::Shuffle().
int64 TSnap::GetTriads | ( | const PGraph & | Graph, |
int64 & | ClosedTriadsX, | ||
int64 & | OpenTriadsX, | ||
int | SampleNodes = -1 |
||
) |
Computes the number of Closed and Open triads.
Considers the graph as undirected.
SampleNodes | If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations. |
Definition at line 246 of file triad.h.
References TVec< TVal, TSizeTy >::Len().
Referenced by GetClustCf(), GetNodeClustCf(), GetTriads(), GetTriadsAll(), PrintInfo(), and TKronMomentsFit::TKronMomentsFit().
void TSnap::GetTriads_v0 | ( | const PGraph & | Graph, |
TIntTrV & | NIdCOTriadV, | ||
int | SampleNodes | ||
) |
Definition at line 270 of file triad.h.
References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::Clr(), THashSet< TKey, THashFunc >::Clr(), THashSet< TKey, THashFunc >::GetKey(), gfDirected, IAssert, THashSet< TKey, THashFunc >::Len(), TVec< TVal, TSizeTy >::Reserve(), and TVec< TVal, TSizeTy >::Shuffle().
int64 TSnap::GetTriadsAll | ( | const PGraph & | Graph, |
int64 & | ClosedTriadsX, | ||
int64 & | OpenTriadsX, | ||
int | SampleNodes = -1 |
||
) |
Computes the number of Closed and Open triads.
Considers the graph as undirected. This function is a duplicate. It is required by Snap.py.
SampleNodes | If !=-1 then compute triads only for a random sample of SampleNodes nodes. Useful for approximate but quick computations. |
Definition at line 263 of file triad.h.
References GetTriads().
int64 TSnap::GetTriangleCnt | ( | const PGraph & | Graph | ) |
Returns the number of triangles in graph Graph
.
Definition at line 454 of file triad.h.
References TVec< TVal, TSizeTy >::Add(), GetCommon(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Reduce(), and TVec< TVal, TSizeTy >::Reserve().
PGraph TSnap::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).
Definition at line 345 of file alg.h.
References MakeUnDir().
void TSnap::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
.
Definition at line 783 of file triad.h.
References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Reduce(), and TVec< TVal, TSizeTy >::Reserve().
Referenced by GetTriads().
void TSnap::GetWccs | ( | const PGraph & | Graph, |
TCnComV & | CnComV | ||
) |
Returns all weakly connected components in a Graph.
CnComV | is a vector of connected components. Each component is defined by the IDs of its member nodes. |
Definition at line 376 of file cncom.h.
References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), TVec< TVal, TSizeTy >::Clr(), THashSet< TKey, THashFunc >::Clr(), THashSet< TKey, THashFunc >::Gen(), gfDirected, HasGraphFlag, and TVec< TVal, TSizeTy >::Sort().
Referenced by TSnap::TSnapDetail::_GirvanNewmanGetModularity(), Get1CnCom(), Get1CnComSzCnt(), TCliqueOverlap::GetCPMCommunities(), GetMxWcc(), GetMxWccSz(), ReebSimplify(), MotifCluster::SpectralCut(), and SummarizeConnectedComponents().
void TSnap::GetWccSzCnt | ( | const PGraph & | Graph, |
TIntPrV & | WccSzCnt | ||
) |
Returns a distribution of weakly connected component sizes.
WccSzCnt | returns a set of pairs (number of nodes in the component, number of such components) |
Definition at line 337 of file cncom.h.
References THashSet< TKey, THashFunc >::AddKey(), gfDirected, HasGraphFlag, and TVec< TVal, TSizeTy >::Sort().
Referenced by Get1CnComSzCnt(), PlotWccDistr(), and TGStat::TakeConnComp().
void TSnap::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.
Definition at line 752 of file centr.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Clr(), TSStack< TVal >::Clr(), TQQueue< TVal >::Clr(), TSStack< TVal >::Empty(), TQQueue< TVal >::Empty(), THash< TKey, TDat, THashFunc >::GetDat(), gfDirected, TVec< TVal, TSizeTy >::Len(), TMath::Mn(), TMath::Mx(), TSStack< TVal >::Pop(), TQQueue< TVal >::Pop(), TSStack< TVal >::Push(), TQQueue< TVal >::Push(), TSStack< TVal >::Top(), and TQQueue< TVal >::Top().
Referenced by GetWeightedBetweennessCentr().
void TSnap::GetWeightedBetweennessCentr | ( | const PNEANet | Graph, |
TIntFltH & | NIdBtwH, | ||
TIntPrFltH & | EdgeBtwH, | ||
const TFltV & | Attr, | ||
const double & | NodeFrac = 1.0 , |
||
const bool & | IsDir = false |
||
) |
Computes (approximate) weighted Node and Edge Beetweenness Centrality based on a sample of NodeFrac nodes.
NIdBtwH | hash table mapping node ids to their corresponding betweenness centrality values. |
EdgeBtwH | hash table mapping edges (pairs of node ids) to their corresponding betweenness centrality values. |
NodeFrac | quality of approximation. NodeFrac=1.0 gives exact betweenness values. |
Definition at line 871 of file centr.cpp.
References TVec< TVal, TSizeTy >::DelLast(), GetWeightedBetweennessCentr(), TVec< TVal, TSizeTy >::Len(), TInt::Rnd, and TVec< TVal, TSizeTy >::Shuffle().
void TSnap::GetWeightedBetweennessCentr | ( | const PNEANet | Graph, |
TIntFltH & | NIdBtwH, | ||
const TFltV & | Attr, | ||
const double & | NodeFrac = 1.0 , |
||
const bool & | IsDir = false |
||
) |
Computes (approximate) weighted Node Beetweenness Centrality based on a sample of NodeFrac nodes.
NIdBtwH | hash table mapping node ids to their corresponding betweenness centrality values. |
NodeFrac | quality of approximation. NodeFrac=1.0 gives exact betweenness values. |
Definition at line 882 of file centr.cpp.
References TVec< TVal, TSizeTy >::DelLast(), GetWeightedBetweennessCentr(), TVec< TVal, TSizeTy >::Len(), TInt::Rnd, and TVec< TVal, TSizeTy >::Shuffle().
void TSnap::GetWeightedBetweennessCentr | ( | const PNEANet | Graph, |
TIntPrFltH & | EdgeBtwH, | ||
const TFltV & | Attr, | ||
const double & | NodeFrac = 1.0 , |
||
const bool & | IsDir = false |
||
) |
Computes (approximate) weighted Edge Beetweenness Centrality based on a sample of NodeFrac nodes.
EdgeBtwH | hash table mapping edges (pairs of node ids) to their corresponding betweenness centrality values. |
NodeFrac | quality of approximation. NodeFrac=1.0 gives exact betweenness values. |
Definition at line 894 of file centr.cpp.
References TVec< TVal, TSizeTy >::DelLast(), GetWeightedBetweennessCentr(), TVec< TVal, TSizeTy >::Len(), TInt::Rnd, and TVec< TVal, TSizeTy >::Shuffle().
double TSnap::GetWeightedClosenessCentr | ( | const PNEANet | Graph, |
const int & | NId, | ||
const TFltV & | Attr, | ||
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 745 of file centr.cpp.
References GetWeightedFarnessCentr().
double TSnap::GetWeightedFarnessCentr | ( | const PNEANet | Graph, |
const int & | NId, | ||
const TFltV & | Attr, | ||
const bool & | Normalized = true , |
||
const bool & | IsDir = false |
||
) |
Returns weighted Farness centrality of a given node NId
. Farness centrality of a node is the average shortest path length to all other nodes that reside is the same connected component as the given node.
Definition at line 726 of file centr.cpp.
References THashKeyDatI< TKey, TDat >::EndI, and GetWeightedShortestPath().
Referenced by GetWeightedClosenessCentr().
int TSnap::GetWeightedPageRank | ( | const PNEANet | Graph, |
TIntFltH & | PRankH, | ||
const TStr & | Attr, | ||
const double & | C, | ||
const double & | Eps, | ||
const int & | MaxIter | ||
) |
Weighted PageRank (TODO: Use template)
Definition at line 396 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Gen(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::Len(), and TVec< TVal, TSizeTy >::Len().
int TSnap::GetWeightedPageRankMP | ( | const PNEANet | Graph, |
TIntFltH & | PRankH, | ||
const TStr & | Attr, | ||
const double & | C, | ||
const double & | Eps, | ||
const int & | MaxIter | ||
) |
Definition at line 443 of file centr.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Gen(), THash< TKey, TDat, THashFunc >::GetDat(), TNEANet::TNodeI::GetId(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInNId(), and TVec< TVal, TSizeTy >::Len().
int TSnap::GetWeightedShortestPath | ( | const PNEANet | Graph, |
const int & | SrcNId, | ||
TIntFltH & | NIdDistH, | ||
const TFltV & | Attr | ||
) |
Dijkstra Algorithm For more info see: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Definition at line 700 of file centr.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Clr(), TVec< TVal, TSizeTy >::Empty(), findMinimum(), THash< TKey, TDat, THashFunc >::GetDat(), and THash< TKey, TDat, THashFunc >::IsKey().
Referenced by GetWeightedFarnessCentr().
void TSnap::GlobalRelabel | ( | PNEANet & | Net, |
TPRManager & | PRM, | ||
const int & | SrcNId, | ||
const int & | SnkNId | ||
) |
Implements the Global Relabeling heuristic.
Since labels reflect an estimate of the distance from a node to the sink node, every now and then the Global Relabel heuristic will be run. This BFS over the residual network starting from the sink and updates each nodes label as the distance to the sink. Unreacheable nodes from the sink have their labels set to N, where N is the number of nodes.
Definition at line 363 of file flow.cpp.
References TSnap::TPRManager::Capacity(), TQQueue< TVal >::Empty(), TSnap::TPRManager::Excess(), TSnap::TPRManager::Flow(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInEId(), TNEANet::TNodeI::GetInNId(), TSnap::TPRManager::GetMaxLabel(), TNEANet::TNodeI::GetOutDeg(), TNEANet::TNodeI::GetOutEId(), TNEANet::TNodeI::GetOutNId(), TSnap::TPRManager::IsActive(), TSnap::TPRManager::Label(), TQQueue< TVal >::Pop(), TQQueue< TVal >::Push(), TSnap::TPRManager::PushActive(), TSnap::TPRManager::RemoveActive(), TSnap::TPRManager::SetLabel(), and TQQueue< TVal >::Top().
Referenced by GetMaxFlowIntPR().
Rosvall-Bergstrom community detection algorithm based on information theoretic approach. See: Rosvall M., Bergstrom C. T., Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. USA 105, 1118-1123 (2008)
Definition at line 339 of file cmty.cpp.
References TCnCom::Add(), TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TUNGraph::BegNI(), TUNGraph::EndNI(), TSnap::TSnapDetail::Equation(), THash< TKey, TDat, THashFunc >::GetDat(), TUNGraph::TNodeI::GetDeg(), TUNGraph::GetEdges(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TSnap::TSnapDetail::MapEquationNew2Modules(), TRnd::Randomize(), TVec< TVal, TSizeTy >::Shuffle(), and THash< TKey, TDat, THashFunc >::SortByDat().
double TSnap::InfomapOnline | ( | PUNGraph & | Graph, |
int | n1, | ||
int | n2, | ||
TIntFltH & | PAlpha, | ||
double & | SumPAlphaLogPAlpha, | ||
TIntFltH & | Qi, | ||
TIntH & | Module, | ||
int & | Br, | ||
TCnComV & | CmtyV | ||
) |
Definition at line 419 of file cmty.cpp.
References TCnCom::Add(), TVec< TVal, TSizeTy >::Add(), TUNGraph::BegNI(), TUNGraph::EndNI(), THash< TKey, TDat, THashFunc >::GetDat(), TSnap::TSnapDetail::InfomapOnlineIncrement(), THash< TKey, TDat, THashFunc >::Len(), and THash< TKey, TDat, THashFunc >::SortByDat().
int TSnap::Intersect | ( | TUNGraph::TNodeI | Node, |
TIntH | NNodes | ||
) |
Intersect.
Definition at line 584 of file centr.cpp.
References TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetId(), TUNGraph::TNodeI::GetNbrNId(), and THash< TKey, TDat, THashFunc >::IsKey().
Referenced by FastCorePeripheryGC(), MaxCPGreedyBetter(), MaxCPGreedyBetter1(), MaxCPGreedyBetter2(), and MaxCPGreedyBetter3().
int TSnap::Intersect | ( | TUNGraph::TNodeI | Node, |
TStr | NNodes | ||
) |
Intersect.
Definition at line 597 of file centr.cpp.
References TStr::CStr(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetId(), TUNGraph::TNodeI::GetNbrNId(), TInt::GetStr(), and TStr::IsStrIn().
int TSnap::Intersect | ( | TUNGraph::TNodeI | Node, |
int * | NNodes, | ||
int | NNodes_br | ||
) |
Intersect.
Definition at line 621 of file centr.cpp.
References TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetId(), and TUNGraph::TNodeI::GetNbrNId().
int TSnap::Intersect1 | ( | TUNGraph::TNodeI | Node, |
TStr | NNodes | ||
) |
Definition at line 650 of file centr.cpp.
References TStr::CStr(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetId(), TUNGraph::TNodeI::GetNbrNId(), TInt::GetStr(), and TStr::SearchStr().
int TSnap::IntFlowBiDBFS | ( | const PNEANet & | Net, |
const int & | CapIndex, | ||
TIntV & | Flow, | ||
TIntQ & | FwdNodeQ, | ||
TIntH & | PredEdgeH, | ||
TIntQ & | BwdNodeQ, | ||
TIntH & | SuccEdgeH, | ||
const int & | SrcNId, | ||
const int & | SnkNId | ||
) |
Definition at line 4 of file flow.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TQQueue< TVal >::Empty(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInEId(), TNEANet::TNodeI::GetInNId(), TNEANet::TNodeI::GetOutDeg(), TNEANet::TNodeI::GetOutEId(), TNEANet::TNodeI::GetOutNId(), THash< TKey, TDat, THashFunc >::IsKey(), TQQueue< TVal >::Pop(), TQQueue< TVal >::Push(), and TQQueue< TVal >::Top().
Referenced by FindAugV().
bool TSnap::IsAllValVNeg | ( | TFltV & | ValV, |
const bool & | InvertSign | ||
) |
Definition at line 163 of file gsvd.cpp.
References TVec< TVal, TSizeTy >::Len().
Referenced by GetEigVec(), and GetSngVec().
bool TSnap::IsConnected | ( | const PGraph & | Graph | ) |
Tests whether the Graph is (weakly) connected.
Definition at line 305 of file cncom.h.
References IsWeaklyConn().
Referenced by IsTree().
bool TSnap::IsTree | ( | const PGraph & | Graph, |
int & | RootNIdX | ||
) |
Definition at line 460 of file alg.h.
References IsConnected().
Referenced by TGHash< TDat >::AddKey(), TGHash< TDat >::GetNodeMap(), GetTreeRootNId(), and TGHash< TDat >::IsGetKeyId().
bool TSnap::IsWeaklyConn | ( | const PGraph & | Graph | ) |
Tests whether the Graph is weakly connected.
Definition at line 310 of file cncom.h.
References gfDirected, HasGraphFlag, and TSnapQueue< TVal >::Push().
Referenced by IsConnected().
PGraph TSnap::LoadConnList | ( | const TStr & | InFNm | ) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 node and all its edges in a single line.
Loads Whitespace separated file of several columns: <source node="" id>=""> <destination node="" id1>=""> <destination node="" id2>="">
Whitespace separated file of several columns: <source node="" id>=""> <destination node="" id1>=""> <destination node="" id2>=""> ... First column of each line contains a source node id followed by ids of the destination nodes. For example, '1 2 3' encodes edges 1–>2 and 1–>3. Note that this format allows for saving isolated nodes.
Definition at line 169 of file gio.h.
References TSsParser::GetInt(), TSsParser::IsInt(), TSsParser::Len(), TSsParser::Next(), and ssfWhiteSep.
PGraph TSnap::LoadConnListStr | ( | const TStr & | InFNm, |
TStrHash< TInt > & | StrToNIdH | ||
) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 node and all its edges in a single line.
Loads Whitespace separated file of several columns: <source node="" id>=""> <destination node="" id1>=""> <destination node="" id2>="">, with a mapping of strings to node IDs.
Whitespace separated file of several columns: <source node="" name>=""> <destination node name 1> <destination node name 2> ... First colum of each line contains a source node name followed by ids of the destination nodes. For example, 'A B C' encodes edges A–>B and A–>C. Note that this format allows for saving isolated nodes. stores the mapping from node names to node ids.
Definition at line 193 of file gio.h.
References TStrHash< TDat, TStringPool, THashFunc >::AddDatId(), TSsParser::Len(), TSsParser::Next(), and ssfWhiteSep.
int TSnap::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.
Definition at line 69 of file conv.cpp.
References TCrossNet::AddEdge(), TCrossNet::AddFltAttrDatE(), TCrossNet::AddIntAttrDatE(), TCrossNet::AddStrAttrDatE(), Assert, atFlt, atInt, atStr, and TVec< TVal, TSizeTy >::Len().
Referenced by LoadCrossNetToNet().
int TSnap::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.
Definition at line 60 of file conv.cpp.
References LoadCrossNet().
For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php)
Loads a directed network in the DyNetML format. Loads only the first network in the file FNm.
Definition at line 296 of file gio.cpp.
References THashSet< TKey, THashFunc >::AddKey(), TXmlLx::GetArg(), THashSet< TKey, THashFunc >::GetKeyId(), TXmlLx::GetSym(), IAssert, TZipIn::IsZipFNm(), TZipIn::New(), TFIn::New(), TNGraph::New(), TXmlLx::Sym, TXmlLx::TagNm, xspTruncate, xsyEof, and xsySTag.
For more info see ORA Network Analysis Data (http://www.casos.cs.cmu.edu/computational_tools/data2.php)
Loads directed networks in the DyNetML format. Loads all the networks in the file FNm.
Definition at line 322 of file gio.cpp.
References TVec< TVal, TSizeTy >::Add(), THashSet< TKey, THashFunc >::AddKey(), TXmlLx::GetArg(), THashSet< TKey, THashFunc >::GetKeyId(), TXmlLx::GetSym(), IAssert, TZipIn::IsZipFNm(), TZipIn::New(), TFIn::New(), TNGraph::New(), TXmlLx::Sym, TXmlLx::TagNm, xspTruncate, xsyEof, and xsySTag.
PGraph TSnap::LoadEdgeList | ( | const TStr & | InFNm, |
const int & | SrcColId, | ||
const int & | DstColId | ||
) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, integer node ids).
Loads the format saved by TSnap::SaveEdgeList()
Whitespace separated file of several columns: ... <source node="" id>=""> ... <destination node="" id>=""> ... SrcColId and DstColId are column indexes of source/destination (integer!) node ids. This means there is one edge per line and node IDs are assumed to be integers.
Definition at line 84 of file gio.h.
References TSsParser::GetInt(), TSsParser::Next(), and ssfWhiteSep.
PGraph TSnap::LoadEdgeList | ( | const TStr & | InFNm, |
const int & | SrcColId, | ||
const int & | DstColId, | ||
const char & | Separator | ||
) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line ('Separator' separated columns, integer node ids).
Loads the format saved by TSnap::SaveEdgeList() if we set Separator=''.
'Separator' separated file of several columns: ... <source node="" id>=""> ... <destination node="" id>=""> ... SrcColId and DstColId are column indexes of source/destination (integer!) node ids. This means there is one edge per line and node IDs are assumed to be integers.
Definition at line 105 of file gio.h.
References TSsParser::GetInt(), and TSsParser::Next().
Loads a network from the text file InFNm with 1 node/edge per line ('Separator' separated columns, integer node id(s) + node/edge attributes).
Definition at line 138 of file gio.cpp.
References EDGES_START, TSsParser::GetFld(), TSsParser::GetFlds(), TPt< TRec >::New(), TSsParser::Next(), NODES_START, ReadEdgeSchemaFromFile(), ReadEdgesFromFile(), ReadNodeSchemaFromFile(), and ReadNodesFromFile().
PGraph TSnap::LoadEdgeListStr | ( | const TStr & | InFNm, |
const int & | SrcColId, | ||
const int & | DstColId | ||
) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, arbitrary string node ids).
Loads the format saved by TSnap::SaveEdgeList(), where node IDs are strings.
Whitespace separated file of several columns: ... <source node="" id>=""> ... <destination node="" id>=""> ... SrcColId and DstColId are column indexes of source/destination (string) node ids. This means there is one edge per line and node IDs can be arbitrary STRINGs. Note that the mapping of node names to ids is discarded.
Definition at line 126 of file gio.h.
References TStrHash< TDat, TStringPool, THashFunc >::AddKey(), Mega, TSsParser::Next(), and ssfWhiteSep.
PGraph TSnap::LoadEdgeListStr | ( | const TStr & | InFNm, |
const int & | SrcColId, | ||
const int & | DstColId, | ||
TStrHash< TInt > & | StrToNIdH | ||
) |
Loads a (directed, undirected or multi) graph from a text file InFNm with 1 edge per line (whitespace separated columns, arbitrary string node ids).
Loads the format saved by TSnap::SaveEdgeList(), where node IDs are strings and mapping of strings to node ids are stored.
Whitespace separated file of several columns: ... <source node="" id>=""> ... <destination node="" id>=""> ... SrcColId and DstColId are column indexes of source/destination (string) node ids. This means there is one edge per line and node IDs can be arbitrary STRINGs. The mapping of strings to node ids is stored in StrToNIdH. To map between node names and ids use: NId = StrToNIdH.GetKeyId(NodeName) and TStr NodeName = StrToNIdH.GetKey(NId);
Definition at line 149 of file gio.h.
References TStrHash< TDat, TStringPool, THashFunc >::AddKey(), TSsParser::Next(), and ssfWhiteSep.
Loads the nodes specified in column NCol from the TTable with the attributes specified in NodeAttrV.
Definition at line 14 of file conv.cpp.
References TNEANet::AddFltAttrDatN(), TNEANet::AddIntAttrDatN(), TNEANet::AddNode(), TNEANet::AddStrAttrDatN(), atFlt, atInt, atStr, TNEANet::IsNode(), and TVec< TVal, TSizeTy >::Len().
Referenced by LoadModeNetToNet().
int TSnap::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.
Definition at line 6 of file conv.cpp.
References LoadMode().
Definition at line 671 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TSsParser::GetInt(), TSsParser::Next(), and ssfWhiteSep.
PGraph TSnap::LoadPajek | ( | const TStr & | InFNm | ) |
Loads a (directed, undirected or multi) graph from Pajek .PAJ format file.
Function supports both the 1 edge per line (<source> <destination> <weight>) as well as the 1 node per line (<source> <destination1> <destination2> ...) formats.
Definition at line 210 of file gio.h.
References EAssert, TSsParser::Eof(), TSsParser::GetInt(), TSsParser::IsInt(), TSsParser::Len(), TSsParser::Next(), ssfSpaceSep, and TSsParser::ToLc().
void TSnap::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).
Definition at line 353 of file alg.h.
References TVec< TVal, TSizeTy >::Add(), CAssert, gfDirected, HasGraphFlag, and TVec< TVal, TSizeTy >::Len().
Referenced by GetUnDir().
void TSnap::MapHits | ( | const TVec< PGraph > & | GraphSeq, |
TVec< PTable > & | TableSeq, | ||
TTableContext * | Context, | ||
const int & | MaxIter | ||
) |
Gets sequence of Hits tables from given GraphSeq
into TableSeq
.
Definition at line 636 of file centr.h.
References TVec< TVal, TSizeTy >::Add(), GetHits(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Reserve(), and TTable::TableFromHashMap().
Referenced by GetMapHitsIterator().
void TSnap::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
.
Definition at line 621 of file centr.h.
References GetPageRank(), TVec< TVal, TSizeTy >::Len(), TVec< TVal, TSizeTy >::Reserve(), and TTable::TableFromHashMap().
Referenced by GetMapPageRank().
Returns centrality Maximum k group.
Definition at line 175 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TUNGraph::BegNI(), THash< TKey, TDat, THashFunc >::DelKey(), THash< TKey, TDat, THashFunc >::EndI(), TUNGraph::EndNI(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), Intersect(), and THash< TKey, TDat, THashFunc >::SortByDat().
Returns centrality Maximum k group.
Definition at line 223 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TUNGraph::BegNI(), THash< TKey, TDat, THashFunc >::DelKey(), THash< TKey, TDat, THashFunc >::EndI(), TUNGraph::EndNI(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), Intersect(), and THash< TKey, TDat, THashFunc >::SortByDat().
Returns centrality Maximum k group.
Definition at line 268 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TUNGraph::BegNI(), THash< TKey, TDat, THashFunc >::DelKey(), THash< TKey, TDat, THashFunc >::EndI(), TUNGraph::EndNI(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), TInt::GetStr(), Intersect(), and THash< TKey, TDat, THashFunc >::SortByDat().
Returns centrality Maximum k group.
Definition at line 322 of file centr.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TUNGraph::BegNI(), THash< TKey, TDat, THashFunc >::DelKey(), THash< TKey, TDat, THashFunc >::EndI(), TUNGraph::EndNI(), TUNGraph::TNodeI::GetDeg(), TUNGraph::TNodeI::GetNbrNId(), TUNGraph::GetNI(), TUNGraph::GetNodes(), Intersect(), and THash< TKey, TDat, THashFunc >::SortByDat().
void TSnap::MergeNbrs | ( | TIntV & | NeighbourV, |
const typename PGraph::TObj::TNodeI & | NI | ||
) |
Merges neighbors by removing duplicates and produces one sorted vector of neighbors.
Definition at line 526 of file triad.h.
References TVec< TVal, TSizeTy >::Add().
void TSnap::NumpyToTFltV | ( | TFltV & | FltV, |
float * | FltNumpyVecIn, | ||
int | n | ||
) |
void TSnap::NumpyToTIntV | ( | TIntV & | IntV, |
int * | IntNumpyVecIn, | ||
int | n | ||
) |
Definition at line 205 of file coreper.cpp.
References TUNGraph::BegEI(), TUNGraph::EndEI(), THash< TKey, TDat, THashFunc >::GetDat(), and TUNGraph::GetNodes().
void TSnap::PlotClustCf | ( | const PGraph & | Graph, |
const TStr & | FNmPref, | ||
TStr | DescStr = TStr() |
||
) |
Plots the distribution of clustering coefficient of a Graph.
Definition at line 111 of file statplot.h.
References TGnuPlot::AddPlot(), TStr::CStr(), TStr::Empty(), TStr::Fmt(), GetClustCf(), gpsLog10XY, gpwLinesPoints, TGnuPlot::SavePng(), TGnuPlot::SetScale(), and TGnuPlot::SetXYLabel().
void TSnap::PlotEigValDistr | ( | const PUNGraph & | Graph, |
const int & | EigVals, | ||
const TStr & | FNmPref, | ||
TStr | DescStr | ||
) |
Plots the distribution of components of the leading eigen-vector of the Graph adjacency matrix. Plots first EigVals values.
Definition at line 14 of file statplot.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::CStr(), TStr::Empty(), TVec< TVal, TSizeTy >::Empty(), TStr::Fmt(), TUNGraph::GetEdges(), GetEigVals(), THash< TKey, TDat, THashFunc >::GetKeyDatPrV(), TUNGraph::GetNodes(), gpsAuto, gpwLinesPoints, TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), TGnuPlot::PlotValV(), and TVec< TVal, TSizeTy >::Sort().
void TSnap::PlotEigValRank | ( | const PUNGraph & | Graph, |
const int & | EigVals, | ||
const TStr & | FNmPref, | ||
TStr | DescStr | ||
) |
Plots the eigen-value rank distribution of the Graph adjacency matrix. Plots first EigVals eigenvalues.
Definition at line 5 of file statplot.cpp.
References TStr::CStr(), TStr::Empty(), TStr::Fmt(), TUNGraph::GetEdges(), GetEigVals(), TUNGraph::GetNodes(), gpsLog10XY, gpwLinesPoints, TGnuPlot::PlotValV(), and TVec< TVal, TSizeTy >::Sort().
void TSnap::PlotHops | ( | const PGraph & | Graph, |
const TStr & | FNmPref, | ||
TStr | DescStr = TStr() , |
||
const bool & | IsDir = false , |
||
const int & | NApprox = 32 |
||
) |
Plots the cumulative distribution of the shortest path lengths of a Graph. Implementation is based on ANF.
IsDir | false: ignore edge directions and consider graph as undirected. |
Definition at line 126 of file statplot.h.
References TGnuPlot::AddPlot(), TSnap::TSnapDetail::CalcEffDiam(), TStr::CStr(), TStr::Empty(), TStr::Fmt(), GetAnf(), gpsLog10Y, gpwLinesPoints, TGnuPlot::SavePng(), TGnuPlot::SetScale(), and TGnuPlot::SetXYLabel().
void TSnap::PlotInDegDistr | ( | const PGraph & | Graph, |
const TStr & | FNmPref, | ||
TStr | DescStr = TStr() , |
||
const bool & | PlotCCdf = false , |
||
const bool & | PowerFit = false |
||
) |
Plots the in-degree distribution of a Graph.
PlotCCdf | Plots the distribution as a Complementary Cummulative distribution function. |
PowerFit | Fits a Power-Law to the distribution. |
Definition at line 47 of file statplot.h.
References TStr::CStr(), TStr::Empty(), TStr::Fmt(), TGUtil::GetCCdf(), GetInDegCnt(), gpsLog10XY, gpwLinesPoints, TVec< TVal, TSizeTy >::Len(), and TGnuPlot::PlotValV().
void TSnap::PlotInvParticipRat | ( | const PUNGraph & | Graph, |
const int & | MaxEigVecs, | ||
const int & | TimeLimit, | ||
const TStr & | FNmPref, | ||
TStr | DescStr = TStr() |
||
) |
Plots the inverse participation ratio. See Spectra of "real-world" graphs: Beyond the semicircle law by Farkas, Derenyi, Barabasi and Vicsek.
Definition at line 39 of file statplot.cpp.
References TVec< TVal, TSizeTy >::Add(), TStr::CStr(), TStr::Empty(), TVec< TVal, TSizeTy >::Empty(), TStr::Fmt(), TUNGraph::GetEdges(), GetInvParticipRat(), TUNGraph::GetNodes(), gpsLog10Y, gpwPoints, TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), and TGnuPlot::PlotValV().
void TSnap::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.
Definition at line 175 of file statplot.h.
References TStr::CStr(), TStr::Empty(), TStr::Fmt(), GetKCoreEdges(), gpsLog10Y, gpwLinesPoints, and TGnuPlot::PlotValV().
void TSnap::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.
Definition at line 167 of file statplot.h.
References TStr::CStr(), TStr::Empty(), TStr::Fmt(), GetKCoreNodes(), gpsLog10Y, gpwLinesPoints, and TGnuPlot::PlotValV().
void TSnap::PlotOutDegDistr | ( | const PGraph & | Graph, |
const TStr & | FNmPref, | ||
TStr | DescStr = TStr() , |
||
const bool & | PlotCCdf = false , |
||
const bool & | PowerFit = false |
||
) |
Plots the out-degree distribution of a Graph.
PlotCCdf | Plots the distribution as a Complementary Cumulative Distribution Function (CCDF). |
PowerFit | Fits a Power-Law to the distribution. |
Definition at line 66 of file statplot.h.
References TStr::CStr(), TStr::Empty(), TStr::Fmt(), TGUtil::GetCCdf(), GetOutDegCnt(), gpsLog10XY, gpwLinesPoints, TVec< TVal, TSizeTy >::Len(), and TGnuPlot::PlotValV().
void TSnap::PlotSccDistr | ( | const PGraph & | Graph, |
const TStr & | FNmPref, | ||
TStr | DescStr = TStr() |
||
) |
Plots the distribution of sizes of strongly connected components of a Graph.
Definition at line 98 of file statplot.h.
References TGnuPlot::AddPlot(), TStr::CStr(), TStr::Empty(), TStr::Fmt(), GetSccSzCnt(), gpsLog10XY, gpwLinesPoints, TVec< TVal, TSizeTy >::Last(), and TPair< TVal1, TVal2 >::Val1.
void TSnap::PlotShortPathDistr | ( | const PGraph & | Graph, |
const TStr & | FNmPref, | ||
TStr | DescStr = TStr() , |
||
int | TestNodes = TInt::Mx |
||
) |
Plots the distribution of the shortest path lengths of a Graph. Implementation is based on BFS.
Definition at line 140 of file statplot.h.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TSnap::TSnapDetail::CalcAvgDiamPdf(), TSnap::TSnapDetail::CalcEffDiamPdf(), TStr::CStr(), TBreathFS< PGraph >::DoBfs(), TStr::Empty(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::GetKey(), gpsLog10Y, gpwLinesPoints, TVec< TVal, TSizeTy >::Last(), THash< TKey, TDat, THashFunc >::Len(), TMath::Mn(), TInt::Mx, TBreathFS< PGraph >::NIdDistH, TGnuPlot::PlotValV(), TInt::Rnd, TVec< TVal, TSizeTy >::Shuffle(), and THash< TKey, TDat, THashFunc >::SortByKey().
void TSnap::PlotSngValDistr | ( | const PNGraph & | Graph, |
const int & | SngVals, | ||
const TStr & | FNmPref, | ||
TStr | DescStr | ||
) |
Plots the rank distribution of singular values of the Graph adjacency matrix. Plots first SngVals values.
Definition at line 58 of file statplot.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::CStr(), TStr::Empty(), TVec< TVal, TSizeTy >::Empty(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::GetKeyDatPrV(), GetSngVals(), gpsAuto, gpwLinesPoints, TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), TGnuPlot::PlotValV(), and TVec< TVal, TSizeTy >::Sort().
void TSnap::PlotSngValRank | ( | const PNGraph & | Graph, |
const int & | SngVals, | ||
const TStr & | FNmPref, | ||
TStr | DescStr | ||
) |
Plots the rank distribution of singular values of the Graph adjacency matrix. Plots first SngVals values.
Definition at line 49 of file statplot.cpp.
References TStr::CStr(), TStr::Empty(), TStr::Fmt(), GetSngVals(), gpsLog10XY, gpwLinesPoints, TGnuPlot::PlotValV(), and TVec< TVal, TSizeTy >::Sort().
Plots the distribution of the values of the leading left singular vector of the Graph adjacency matrix. Plots first SngVals values.
Definition at line 81 of file statplot.cpp.
References TStr::CStr(), TStr::Empty(), TStr::Fmt(), GetSngVec(), gpsLog10XY, gpwLinesPoints, TGUtil::MakeExpBins(), TGnuPlot::PlotValV(), and TVec< TVal, TSizeTy >::Sort().
void TSnap::PlotWccDistr | ( | const PGraph & | Graph, |
const TStr & | FNmPref, | ||
TStr | DescStr = TStr() |
||
) |
Plots the distribution of sizes of weakly connected components of a Graph.
Definition at line 85 of file statplot.h.
References TGnuPlot::AddPlot(), TStr::CStr(), TStr::Empty(), TStr::Fmt(), GetWccSzCnt(), gpsLog10XY, gpwLinesPoints, TVec< TVal, TSizeTy >::Last(), and TPair< TVal1, TVal2 >::Val1.
void TSnap::PrintInfo | ( | const PGraph & | Graph, |
const TStr & | Desc = "" , |
||
const TStr & | OutFNm = "" , |
||
const bool & | Fast = true |
||
) |
Prints basic graph statistics.
Fast | true: only computes basic statistics (that can be computed fast). For more extensive information (and longer execution times) set Fast = false . |
Definition at line 87 of file gbase.h.
References THash< TKey, TDat, THashFunc >::AddKey(), TStr::CStr(), edge, TStr::Empty(), GetBfsEffDiam(), GetFlagStr(), TInt::GetMn(), TInt::GetMx(), GetMxSccSz(), GetMxWccSz(), TUInt64::GetStr(), GetTriads(), gfMx, gfUndef, HasGraphFlag, and THash< TKey, TDat, THashFunc >::Len().
Referenced by main(), and TKronMomentsFit::Test().
int TSnap::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.
Definition at line 328 of file flow.cpp.
References TSnap::TPRManager::Capacity(), TSnap::TPRManager::EdgeNum(), TSnap::TPRManager::Flow(), TNEANet::TNodeI::GetDeg(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInEId(), TNEANet::TNodeI::GetInNId(), TNEANet::TNodeI::GetOutEId(), TNEANet::TNodeI::GetOutNId(), TSnap::TPRManager::Label(), PushToInNbr(), PushToOutNbr(), and Relabel().
Referenced by GetMaxFlowIntPR().
void TSnap::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
.
Definition at line 297 of file flow.cpp.
References TSnap::TPRManager::Excess(), TSnap::TPRManager::Flow(), and MIN.
Referenced by PushRelabel().
void TSnap::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
.
Definition at line 289 of file flow.cpp.
References TSnap::TPRManager::Capacity(), TSnap::TPRManager::Excess(), TSnap::TPRManager::Flow(), and MIN.
Referenced by PushRelabel().
int TSnap::ReadEdgeSchemaFromFile | ( | TSsParser & | Ss, |
const char & | Separator, | ||
int & | SrcColId, | ||
int & | DstColId, | ||
TStrIntH & | IntAttrEVals, | ||
TStrIntH & | FltAttrEVals, | ||
TStrIntH & | StrAttrEVals | ||
) |
Definition at line 6 of file gio.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), DST_ID_NAME, EDGES_START, FLT_TYPE_PREFIX, TSsParser::GetFld(), TSsParser::GetFlds(), INT_TYPE_PREFIX, TStr::SplitOnCh(), SRC_ID_NAME, and STR_TYPE_PREFIX.
Referenced by LoadEdgeListNet().
bool TSnap::ReadEdgesFromFile | ( | TSsParser & | Ss, |
const char & | Separator, | ||
PNEANet & | Graph, | ||
int & | SrcColId, | ||
int & | DstColId, | ||
TStrIntH & | IntAttrEVals, | ||
TStrIntH & | FltAttrEVals, | ||
TStrIntH & | StrAttrEVals | ||
) |
Definition at line 38 of file gio.cpp.
References THash< TKey, TDat, THashFunc >::BegI(), EDGES_START, END_SENTINEL, THash< TKey, TDat, THashFunc >::EndI(), TSsParser::GetFld(), TSsParser::GetFlds(), TSsParser::GetFlt(), TSsParser::GetInt(), TSsParser::Next(), NODES_START, and NULL_VAL.
Referenced by LoadEdgeListNet().
int TSnap::ReadNodeSchemaFromFile | ( | TSsParser & | Ss, |
const char & | Separator, | ||
int & | NId, | ||
TStrIntH & | IntAttrNVals, | ||
TStrIntH & | FltAttrNVals, | ||
TStrIntH & | StrAttrNVals | ||
) |
Definition at line 77 of file gio.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), FLT_TYPE_PREFIX, TSsParser::GetFld(), TSsParser::GetFlds(), INT_TYPE_PREFIX, NID_NAME, NODES_START, TStr::SplitOnCh(), and STR_TYPE_PREFIX.
Referenced by LoadEdgeListNet().
bool TSnap::ReadNodesFromFile | ( | TSsParser & | Ss, |
const char & | Separator, | ||
PNEANet & | Graph, | ||
int & | NColId, | ||
TStrIntH & | IntAttrNVals, | ||
TStrIntH & | FltAttrNVals, | ||
TStrIntH & | StrAttrNVals | ||
) |
Definition at line 105 of file gio.cpp.
References THash< TKey, TDat, THashFunc >::BegI(), EDGES_START, END_SENTINEL, THash< TKey, TDat, THashFunc >::EndI(), TSsParser::GetFld(), TSsParser::GetFlds(), TSsParser::GetFlt(), TSsParser::GetInt(), TSsParser::Next(), NODES_START, and NULL_VAL.
Referenced by LoadEdgeListNet().
void TSnap::ReebRefine | ( | PNGraph & | Graph, |
TIntH & | t, | ||
int | e, | ||
PNGraph & | gFinal, | ||
TIntH & | tFinal, | ||
bool | collapse | ||
) |
Definition at line 984 of file cmty.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), TVec< TVal, TSizeTy >::Clr(), THash< TKey, TDat, THashFunc >::DelKey(), THash< TKey, TDat, THashFunc >::EndI(), THashKeyDatI< TKey, TDat >::GetDat(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::GetDat(), TNGraph::TNodeI::GetInNId(), THashKeyDatI< TKey, TDat >::GetKey(), TNGraph::TNodeI::GetOutNId(), THashKeyDatI< TKey, TDat >::IsEnd(), THash< TKey, TDat, THashFunc >::IsKey(), THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TNGraph::New(), and TSnap::TSnapDetail::vectorIntersect().
void TSnap::ReebSimplify | ( | PNGraph & | Graph, |
TIntH & | t, | ||
int | e, | ||
PNGraph & | gFinal, | ||
TIntH & | tFinal, | ||
bool | collapse | ||
) |
Definition at line 844 of file cmty.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::DelKey(), TSnap::TSnapDetail::edgeIntersect(), THash< TKey, TDat, THashFunc >::EndI(), THashKeyDatI< TKey, TDat >::GetDat(), THash< TKey, TDat, THashFunc >::GetDat(), TVec< TVal, TSizeTy >::GetDat(), THashKeyDatI< TKey, TDat >::GetKey(), GetWccs(), TVec< TVal, TSizeTy >::IntrsLen(), THashKeyDatI< TKey, TDat >::IsEnd(), TVec< TVal, TSizeTy >::Len(), and TNGraph::New().
void TSnap::Relabel | ( | TPRManager & | PRM, |
const int & | NId, | ||
const TNEANet::TNodeI & | NI | ||
) |
Increases the label of a node NId
to allow valid pushes to some neighbor.
Definition at line 305 of file flow.cpp.
References TSnap::TPRManager::Capacity(), TSnap::TPRManager::Flow(), TNEANet::TNodeI::GetInDeg(), TNEANet::TNodeI::GetInEId(), TNEANet::TNodeI::GetInNId(), TSnap::TPRManager::GetMaxLabel(), TNEANet::TNodeI::GetOutDeg(), TNEANet::TNodeI::GetOutEId(), TNEANet::TNodeI::GetOutNId(), TSnap::TPRManager::Label(), MIN, and TSnap::TPRManager::SetLabel().
Referenced by PushRelabel().
int TSnap::SamplePersonalizedPageRank | ( | const PGraph & | Graph, |
double | JumpProb, | ||
const TIntV & | StartNIdV, | ||
TRnd & | Rnd | ||
) |
Definition at line 67 of file randwalk.h.
References TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TVec< TVal, TSizeTy >::GetRndVal(), TRnd::GetUniDev(), and TRnd::GetUniDevInt().
Referenced by GetPersonalizedPageRankBidirectional().
void TSnap::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>="">
Definition at line 245 of file gio.h.
References TStr::CStr(), TStr::Empty(), gfDirected, and HasGraphFlag.
Referenced by main().
Saves a network into a text file. Each line encodes either an edge or a node, along with its attributes.
Definition at line 269 of file gio.cpp.
References TStr::CStr(), TStr::Empty(), END_SENTINEL, WriteEdgeSchemaToFile(), WriteEdgesToFile(), WriteNodeSchemaToFile(), and WriteNodesToFile().
void TSnap::SaveGViz | ( | const PGraph & | Graph, |
const TStr & | OutFNm, | ||
const TStr & | Desc = TStr() , |
||
const bool & | NodeLabels = false , |
||
const TIntStrH & | NIdColorH = TIntStrH() |
||
) |
Save a graph in GraphVizp .DOT format.
Save a graph in GraphVizp .DOT format.
NIdColorH | Maps node ids to node colors (see GraphViz documentation for more details). |
Definition at line 387 of file gio.h.
References TStr::CStr(), TStr::Empty(), THash< TKey, TDat, THashFunc >::GetDat(), gfDirected, HasGraphFlag, and THash< TKey, TDat, THashFunc >::IsKey().
Referenced by DrawGViz().
void TSnap::SaveGViz | ( | const PGraph & | Graph, |
const TStr & | OutFNm, | ||
const TStr & | Desc, | ||
const TIntStrH & | NIdLabelH | ||
) |
Save a graph in GraphVizp .DOT format.
Save a graph in GraphVizp .DOT format.
NIdLabelH | Maps node ids to node string labels. |
Definition at line 425 of file gio.h.
References TStr::CStr(), TStr::Empty(), THash< TKey, TDat, THashFunc >::GetDat(), gfDirected, and THash< TKey, TDat, THashFunc >::IsKey().
void TSnap::SaveMatlabSparseMtx | ( | const PGraph & | Graph, |
const TStr & | OutFNm | ||
) |
Saves a graph in a MATLAB sparse matrix format.
Each line contains a tuple of 3 values: <source node="" id>=""><tab><destination node="" id>=""><tab>1.
Definition at line 369 of file gio.h.
References THashSet< TKey, THashFunc >::AddKey(), TStr::CStr(), gfDirected, and HasGraphFlag.
void TSnap::SavePajek | ( | const PGraph & | Graph, |
const TStr & | OutFNm | ||
) |
Saves a graph in a Pajek .NET format.
Definition at line 260 of file gio.h.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::CStr(), gfDirected, and HasGraphFlag.
void TSnap::SavePajek | ( | const PGraph & | Graph, |
const TStr & | OutFNm, | ||
const TIntStrH & | NIdColorH | ||
) |
Saves a graph in a Pajek .NET format.
NIdColorH maps node ids to node colors. Default node color is Red. See http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf for a list of supported color names.
Definition at line 285 of file gio.h.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::CStr(), THash< TKey, TDat, THashFunc >::GetDat(), gfDirected, HasGraphFlag, and THash< TKey, TDat, THashFunc >::IsKey().
void TSnap::SavePajek | ( | const PGraph & | Graph, |
const TStr & | OutFNm, | ||
const TIntStrH & | NIdColorH, | ||
const TIntStrH & | NIdLabelH | ||
) |
Saves a graph in a Pajek .NET format.
NIdColorH maps node ids to node colors. Default node color is Red. NIdLabelH maps node ids to node string labels. See http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf for a list of supported color names.
Definition at line 312 of file gio.h.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::CStr(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::GetDat(), gfDirected, HasGraphFlag, and THash< TKey, TDat, THashFunc >::IsKey().
void TSnap::SavePajek | ( | const PGraph & | Graph, |
const TStr & | OutFNm, | ||
const TIntStrH & | NIdColorH, | ||
const TIntStrH & | NIdLabelH, | ||
const TIntStrH & | EIdColorH | ||
) |
Saves a graph in a Pajek .NET format.
NIdColorH maps node ids to node colors. Default node color is Red. NIdLabelH maps node ids to node string labels. EIdColorH maps edge ids to node colors. Default edge color is Black. See http://vlado.fmf.uni-lj.si/pub/networks/pajek/doc/pajekman.pdf for a list of supported color names.
Definition at line 341 of file gio.h.
References THash< TKey, TDat, THashFunc >::AddDat(), CAssert, TStr::CStr(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::GetDat(), gfDirected, gfMultiGraph, HasGraphFlag, and THash< TKey, TDat, THashFunc >::IsKey().
void TSnap::SetAllInvertSign | ( | TFltV & | ValV, |
const double & | Val | ||
) |
Definition at line 158 of file gsvd.cpp.
References TVec< TVal, TSizeTy >::Len().
void TSnap::TestAnf | ( | ) |
Definition at line 240 of file anf.h.
References TVec< TVal, TSizeTy >::Add(), TGraphAnf< PGraph >::GetGraphAnf(), TMom::GetMean(), TMom::GetSDev(), TVec< TVal, TSizeTy >::Last(), and TVec< TVal, TSizeTy >::Len().
void TSnap::TFltVToNumpy | ( | TFltV & | FltV, |
float * | FltNumpyVecOut, | ||
int | n | ||
) |
Converts TFltV to Numpy array.
Fills the numpyvec array with TFltV vector values. Note that only the first n values are filled.
Definition at line 15 of file numpy.cpp.
References TVec< TVal, TSizeTy >::Len(), and MIN.
void TSnap::TIntVToNumpy | ( | TIntV & | IntV, |
int * | IntNumpyVecOut, | ||
int | n | ||
) |
Converts TIntV to Numpy array.
Fills the numpyvec array with TIntV vector values. Note that only the first n values are filled.
Definition at line 4 of file numpy.cpp.
References TVec< TVal, TSizeTy >::Len(), and MIN.
PGraph TSnap::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
.
Converts table to a directed/undirected graph. Suitable for PUNGraph and PNGraph, but not for PNEANet where attributes are expected.
Definition at line 8 of file conv.h.
References Assert, atFlt, and atInt.
PGraphMP TSnap::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.
Definition at line 192 of file conv.h.
References TVec< TVal, TSizeTy >::Add(), Assert, atInt, atStr, TVec< TVal, TSizeTy >::CopyUniqueFrom(), TRowIterator::GetIntAttr(), TRowIterator::GetRowIdx(), TRowIterator::GetStrMapById(), TVec< TVal, TSizeTy >::GetVal(), TVec< TVal, TSizeTy >::Len(), TNGraphMP::New(), TTable::QSortKeyVal(), and TVec< TVal, TSizeTy >::Reserve().
PGraphMP TSnap::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.
Definition at line 532 of file conv.h.
References Assert, atInt, atStr, TPt< TRec >::Clr(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Gen(), TInt::GetPrimHashCd(), and TNGraphMP::New().
PGraph TSnap::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.
Converts table to a network. Suitable for PNEANet - Requires node and edge attribute column names as vectors.
Definition at line 64 of file conv.h.
References Assert, atFlt, atInt, atStr, THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::IsKey(), and TVec< TVal, TSizeTy >::Len().
PGraph TSnap::ToNetwork | ( | PTable | Table, |
const TStr & | SrcCol, | ||
const TStr & | DstCol, | ||
TAttrAggr | AggrPolicy | ||
) |
PGraph TSnap::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.
Definition at line 1572 of file conv.h.
References Assert, atFlt, atInt, atStr, and TVec< TVal, TSizeTy >::Len().
PGraph TSnap::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.
Definition at line 2010 of file conv.h.
References Assert, atFlt, atInt, atStr, and TVec< TVal, TSizeTy >::Len().
|
inline |
Does Table to Network conversion in parallel using the sort-first algorithm. This is the recommended method to use.
Definition at line 696 of file conv.h.
References TVec< TVal, TSizeTy >::Add(), TStopwatch::AddEdges, TStopwatch::AddNeighborhoods, TStopwatch::AllocateColumnCopies, Assert, atFlt, atInt, atStr, THash< TKey, TDat, THashFunc >::BegI(), TStopwatch::CopyColumns, TVec< TVal, TSizeTy >::CopyUniqueFrom(), THash< TKey, TDat, THashFunc >::EndI(), THash< TKey, TDat, THashFunc >::GetDat(), TStopwatch::GetInstance(), TRowIterator::GetIntAttr(), TRowIterator::GetRowIdx(), TRowIterator::GetStrMapById(), TVec< TVal, TSizeTy >::GetVal(), TStopwatch::Group, THash< TKey, TDat, THashFunc >::IsKey(), TVec< TVal, TSizeTy >::Len(), TStopwatch::MergeNeighborhoods, TTable::QSortKeyVal(), TVec< TVal, TSizeTy >::Reserve(), TStopwatch::Sort, TStopwatch::Start(), and TStopwatch::Stop().
PGraphMP TSnap::ToNetworkMP | ( | PTable | Table, |
const TStr & | SrcCol, | ||
const TStr & | DstCol, | ||
TAttrAggr | AggrPolicy | ||
) |
|
inline |
Converts table to network in parallel. Use if network has only edge attributes.
Definition at line 1651 of file conv.h.
References TVec< TVal, TSizeTy >::Add(), TStopwatch::AddEdges, TStopwatch::AddNeighborhoods, TStopwatch::AllocateColumnCopies, Assert, atFlt, atInt, atStr, TStopwatch::CopyColumns, TVec< TVal, TSizeTy >::CopyUniqueFrom(), TStopwatch::GetInstance(), TRowIterator::GetIntAttr(), TRowIterator::GetRowIdx(), TRowIterator::GetStrMapById(), TVec< TVal, TSizeTy >::GetVal(), TStopwatch::Group, TVec< TVal, TSizeTy >::Len(), TStopwatch::MergeNeighborhoods, TTable::QSortKeyVal(), TVec< TVal, TSizeTy >::Reserve(), TStopwatch::Sort, TStopwatch::Start(), and TStopwatch::Stop().
|
inline |
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.
Definition at line 2131 of file conv.h.
References TVec< TVal, TSizeTy >::Add(), TStopwatch::AddEdges, TStopwatch::AddNeighborhoods, TStopwatch::AllocateColumnCopies, Assert, atFlt, atInt, atStr, TStopwatch::CopyColumns, TVec< TVal, TSizeTy >::CopyUniqueFrom(), TStopwatch::GetInstance(), TRowIterator::GetIntAttr(), TRowIterator::GetRowIdx(), TRowIterator::GetStrMapById(), TVec< TVal, TSizeTy >::GetVal(), TStopwatch::Group, TVec< TVal, TSizeTy >::Len(), TStopwatch::MergeNeighborhoods, TTable::QSortKeyVal(), TVec< TVal, TSizeTy >::Reserve(), TStopwatch::Sort, TStopwatch::Start(), and TStopwatch::Stop().
|
inline |
Implements table to network conversion in parallel. Not the recommended algorithm, using ToNetworkMP instead.
Definition at line 1118 of file conv.h.
References TVec< TVal, TSizeTy >::Add(), TStopwatch::AddEdges, TStopwatch::AddNeighborhoods, TStopwatch::AllocateColumnCopies, Assert, atInt, atStr, TStopwatch::CopyColumns, TVec< TVal, TSizeTy >::CopyUniqueFrom(), TStopwatch::GetInstance(), TRowIterator::GetIntAttr(), TRowIterator::GetRowIdx(), TRowIterator::GetStrMapById(), TVec< TVal, TSizeTy >::GetVal(), TStopwatch::Group, TVec< TVal, TSizeTy >::Len(), TStopwatch::MergeNeighborhoods, TTable::QSortKeyVal(), TVec< TVal, TSizeTy >::Reserve(), TStopwatch::Sort, TStopwatch::Start(), TStopwatch::Stop(), and TInt::Val.
PGraphMP TSnap::ToNetworkMP2 | ( | PTable | Table, |
const TStr & | SrcCol, | ||
const TStr & | DstCol, | ||
TAttrAggr | AggrPolicy | ||
) |
void TSnap::WriteEdgeSchemaToFile | ( | FILE * | F, |
TStrV & | IntAttrENames, | ||
TStrV & | FltAttrENames, | ||
TStrV & | StrAttrENames | ||
) |
Definition at line 221 of file gio.cpp.
References TStr::CStr(), DST_ID_NAME, EDGES_START, FLT_TYPE_PREFIX, INT_TYPE_PREFIX, TVec< TVal, TSizeTy >::Len(), SRC_ID_NAME, and STR_TYPE_PREFIX.
Referenced by SaveEdgeListNet().
void TSnap::WriteEdgesToFile | ( | FILE * | F, |
const PNEANet & | Graph, | ||
TStrV & | IntAttrENames, | ||
TStrV & | FltAttrENames, | ||
TStrV & | StrAttrENames | ||
) |
Definition at line 238 of file gio.cpp.
References TStr::CStr(), TVec< TVal, TSizeTy >::Len(), and NULL_VAL.
Referenced by SaveEdgeListNet().
void TSnap::WriteNodeSchemaToFile | ( | FILE * | F, |
TStrV & | IntAttrNNames, | ||
TStrV & | FltAttrNNames, | ||
TStrV & | StrAttrNNames | ||
) |
Definition at line 171 of file gio.cpp.
References TStr::CStr(), FLT_TYPE_PREFIX, INT_TYPE_PREFIX, TVec< TVal, TSizeTy >::Len(), NID_NAME, NODES_START, and STR_TYPE_PREFIX.
Referenced by SaveEdgeListNet().
void TSnap::WriteNodesToFile | ( | FILE * | F, |
const PNEANet & | Graph, | ||
TStrV & | IntAttrNNames, | ||
TStrV & | FltAttrNNames, | ||
TStrV & | StrAttrNNames | ||
) |
Definition at line 188 of file gio.cpp.
References TStr::CStr(), TVec< TVal, TSizeTy >::Len(), and NULL_VAL.
Referenced by SaveEdgeListNet().
const TStr TSnap::CapAttrName = "capacity" |
Definition at line 4 of file flow.h.
Referenced by GetMaxFlowIntEK(), and TSnap::TPRManager::TPRManager().
const TStr TSnap::DST_ID_NAME = ("DstNId") |
Definition at line 10 of file gio.h.
Referenced by ReadEdgeSchemaFromFile(), and WriteEdgeSchemaToFile().
const TStr TSnap::EDGES_START = ("#EDGES") |
Definition at line 6 of file gio.h.
Referenced by LoadEdgeListNet(), ReadEdgeSchemaFromFile(), ReadEdgesFromFile(), ReadNodesFromFile(), and WriteEdgeSchemaToFile().
const TStr TSnap::END_SENTINEL = ("#END") |
Definition at line 8 of file gio.h.
Referenced by ReadEdgesFromFile(), ReadNodesFromFile(), and SaveEdgeListNet().
const TStr TSnap::FLT_TYPE_PREFIX = ("Flt") |
Definition at line 13 of file gio.h.
Referenced by ReadEdgeSchemaFromFile(), ReadNodeSchemaFromFile(), WriteEdgeSchemaToFile(), and WriteNodeSchemaToFile().
const TStr TSnap::INT_TYPE_PREFIX = ("Int") |
Definition at line 12 of file gio.h.
Referenced by ReadEdgeSchemaFromFile(), ReadNodeSchemaFromFile(), WriteEdgeSchemaToFile(), and WriteNodeSchemaToFile().
const TStr TSnap::NID_NAME = ("NId") |
Definition at line 11 of file gio.h.
Referenced by ReadNodeSchemaFromFile(), and WriteNodeSchemaToFile().
const TStr TSnap::NODES_START = ("#NODES") |
Definition at line 7 of file gio.h.
Referenced by LoadEdgeListNet(), ReadEdgesFromFile(), ReadNodeSchemaFromFile(), ReadNodesFromFile(), and WriteNodeSchemaToFile().
const TStr TSnap::NULL_VAL = ("__null__") |
Definition at line 15 of file gio.h.
Referenced by ReadEdgesFromFile(), ReadNodesFromFile(), WriteEdgesToFile(), and WriteNodesToFile().
const TStr TSnap::SRC_ID_NAME = ("SrcNId") |
Definition at line 9 of file gio.h.
Referenced by ReadEdgeSchemaFromFile(), and WriteEdgeSchemaToFile().
const TStr TSnap::STR_TYPE_PREFIX = ("Str") |
Definition at line 14 of file gio.h.
Referenced by ReadEdgeSchemaFromFile(), ReadNodeSchemaFromFile(), WriteEdgeSchemaToFile(), and WriteNodeSchemaToFile().