|
SNAP Library 2.0, Developer Reference
2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
|
SNAP Library 2.0, Developer Reference
2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
Undirected graph. More...
#include <graph.h>
Classes | |
| class | TEdgeI |
| Edge iterator. Only forward iteration (operator++) is supported. More... | |
| class | TNode |
| class | TNodeI |
| Node iterator. Only forward iteration (operator++) is supported. More... | |
Public Types | |
| typedef TUNGraph | TNet |
| typedef TPt< TUNGraph > | PNet |
Public Member Functions | |
| TUNGraph () | |
| TUNGraph (const int &Nodes, const int &Edges) | |
| Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges. | |
| TUNGraph (const TUNGraph &Graph) | |
| TUNGraph (TSIn &SIn) | |
| Constructor that loads the graph from a (binary) stream SIn. | |
| void | Save (TSOut &SOut) const |
| Saves the graph to a (binary) stream SOut. | |
| bool | HasFlag (const TGraphFlag &Flag) const |
| Allows for run-time checking the type of the graph (see the TGraphFlag for flags). | |
| TUNGraph & | operator= (const TUNGraph &Graph) |
| int | GetNodes () const |
| Returns the number of nodes in the graph. | |
| int | AddNode (int NId=-1) |
| Adds a node of ID NId to the graph. | |
| int | AddNode (const TNodeI &NodeI) |
| Adds a node of ID NodeI.GetId() to the graph. | |
| int | AddNode (const int &NId, const TIntV &NbrNIdV) |
| Adds a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV. | |
| int | AddNode (const int &NId, const TVecPool< TInt > &Pool, const int &NIdVId) |
| Adds a node of ID NId to the graph and create edges to all nodes in vector NIdVId in the vector pool Pool. | |
| void | DelNode (const int &NId) |
| Deletes node of ID NId from the graph. | |
| void | DelNode (const TNode &NodeI) |
| Deletes node of ID NodeI.GetId() from the graph. | |
| bool | IsNode (const int &NId) const |
| Tests whether ID NId is a node. | |
| TNodeI | BegNI () const |
| Returns an iterator referring to the first node in the graph. | |
| TNodeI | EndNI () const |
| Returns an iterator referring to the past-the-end node in the graph. | |
| TNodeI | GetNI (const int &NId) const |
| Returns an iterator referring to the node of ID NId in the graph. | |
| int | GetMxNId () const |
| Returns the maximum id of a any node in the graph. | |
| int | GetEdges () const |
| Returns the number of edges in the graph. | |
| int | AddEdge (const int &SrcNId, const int &DstNId) |
| Adds an edge between node IDs SrcNId and DstNId to the graph. | |
| int | AddEdge (const TEdgeI &EdgeI) |
| Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph. | |
| void | DelEdge (const int &SrcNId, const int &DstNId) |
| Deletes an edge between node IDs SrcNId and DstNId from the graph. | |
| bool | IsEdge (const int &SrcNId, const int &DstNId) const |
| Tests whether an edge between node IDs SrcNId and DstNId exists in the graph. | |
| TEdgeI | BegEI () const |
| Returns an iterator referring to the first edge in the graph. | |
| TEdgeI | EndEI () const |
| Returns an iterator referring to the past-the-end edge in the graph. | |
| TEdgeI | GetEI (const int &EId) const |
| Not supported/implemented! | |
| TEdgeI | GetEI (const int &SrcNId, const int &DstNId) const |
| Returns an iterator referring to edge (SrcNId, DstNId) in the graph. | |
| int | GetRndNId (TRnd &Rnd=TInt::Rnd) |
| Returns an ID of a random node in the graph. | |
| TNodeI | GetRndNI (TRnd &Rnd=TInt::Rnd) |
| Returns an interator referring to a random node in the graph. | |
| void | GetNIdV (TIntV &NIdV) const |
| Gets a vector IDs of all nodes in the graph. | |
| bool | Empty () const |
| Tests whether the graph is empty (has zero nodes). | |
| void | Clr () |
| Deletes all nodes and edges from the graph. | |
| void | Reserve (const int &Nodes, const int &Edges) |
| Reserves memory for a graph of Nodes nodes and Edges edges. | |
| void | ReserveNIdDeg (const int &NId, const int &Deg) |
| Reserves memory for node ID NId having Deg edges. | |
| void | Defrag (const bool &OnlyNodeLinks=false) |
| Defragments the graph. | |
| bool | IsOk (const bool &ThrowExcept=true) const |
| Checks the graph data structure for internal consistency. | |
| void | Dump (FILE *OutF=stdout) const |
| Print the graph in a human readable form to an output stream OutF. | |
Static Public Member Functions | |
| static PUNGraph | New () |
| Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New(). | |
| static PUNGraph | New (const int &Nodes, const int &Edges) |
| Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and Edges edges. | |
| static PUNGraph | Load (TSIn &SIn) |
| Static constructor that loads the graph from a stream SIn and returns a pointer to it. | |
| static PUNGraph | GetSmallGraph () |
| Returns a small graph on 5 nodes and 5 edges. | |
Private Member Functions | |
| TNode & | GetNode (const int &NId) |
| const TNode & | GetNode (const int &NId) const |
Private Attributes | |
| TCRef | CRef |
| TInt | MxNId |
| TInt | NEdges |
| THash< TInt, TNode > | NodeH |
Friends | |
| class | TUNGraphMtx |
| class | TPt< TUNGraph > |
Undirected graph.
Node IDs can be arbitrary non-negative integers. Nodes and edges have no attributes/data associated with them. There is at most one undirected edge between a pair of nodes. Self loops (one per node) are allowed but multiple (parallel) edges are not. The undirected graph data structure is implemented using sorted adjacency lists. This means adding a node takes constant time, while adding an edge takes linear time (since adjacency list is kept sorted) in the node degree. Accessing arbitrary node takes constant time and accessing any edge takes logarithmic time in the node degree.
| typedef TPt<TUNGraph> TUNGraph::PNet |
| typedef TUNGraph TUNGraph::TNet |
| TUNGraph::TUNGraph | ( | ) | [inline] |
| TUNGraph::TUNGraph | ( | const int & | Nodes, |
| const int & | Edges | ||
| ) | [inline, explicit] |
| TUNGraph::TUNGraph | ( | const TUNGraph & | Graph | ) | [inline] |
| TUNGraph::TUNGraph | ( | TSIn & | SIn | ) | [inline] |
| int TUNGraph::AddEdge | ( | const int & | SrcNId, |
| const int & | DstNId | ||
| ) |
Adds an edge between node IDs SrcNId and DstNId to the graph.
If the edge already exists return -2. If the edge was successfully added return -1. Normally the function should return an ID of the edge added but since edges in TUNGraph have no IDs we return -1. The function aborts if SrcNId or DstNId are not nodes in the graph.
Definition at line 81 of file graph.cpp.
References TVec< TVal, TSizeTy >::AddSorted(), TStr::Fmt(), GetNode(), IAssertR, IsEdge(), IsNode(), NEdges, and TUNGraph::TNode::NIdV.
Referenced by TUndirFFire::AddNodes(), TCliqueOverlap::CalculateOverlapMtx(), TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), GetSmallGraph(), TSnap::GetSubGraph(), TTimeNENet::GetTriadEdges(), TAGM::RndConnectInsideCommunity(), and TNetConstraint< PGraph >::Test().
{
IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
if (IsEdge(SrcNId, DstNId)) { return -2; } // edge already exists
GetNode(SrcNId).NIdV.AddSorted(DstNId);
if (SrcNId!=DstNId) { // not a self edge
GetNode(DstNId).NIdV.AddSorted(SrcNId); }
NEdges++;
return -1; // edge id
}
| int TUNGraph::AddEdge | ( | const TEdgeI & | EdgeI | ) | [inline] |
Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
Definition at line 218 of file graph.h.
References AddEdge(), TUNGraph::TEdgeI::GetDstNId(), and TUNGraph::TEdgeI::GetSrcNId().
Referenced by AddEdge().
{ return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
| int TUNGraph::AddNode | ( | int | NId = -1 | ) |
Adds a node of ID NId to the graph.
Returns the ID of the node being added. If NId is -1, node ID is automatically assigned. Aborts, if a node with ID NId already exists.
Definition at line 8 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), IAssertR, IsNode(), TMath::Mx(), MxNId, and NodeH.
Referenced by TUndirFFire::AddNodes(), TCliqueOverlap::CalculateOverlapMtx(), TAGM::GenAGM(), TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), GetSmallGraph(), TSnap::GetSubGraph(), TTimeNENet::GetTriadEdges(), and TNetConstraint< PGraph >::Test().
{
if (NId == -1) {
NId = MxNId; MxNId++;
} else {
IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
MxNId = TMath::Mx(NId+1, MxNId());
}
NodeH.AddDat(NId, TNode(NId));
return NId;
}
| int TUNGraph::AddNode | ( | const TNodeI & | NodeI | ) | [inline] |
| int TUNGraph::AddNode | ( | const int & | NId, |
| const TIntV & | NbrNIdV | ||
| ) |
Adds a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV.
Returns the ID of the node being added. If NId is -1, node ID is automatically assigned. Aborts, if a node with ID NId already exists.
The operation can create inconsistent graphs when the neighboring nodes in NbrNIdV vector do not exist. Use TUNGraph::IsOk to check that the resulting graph is consistent after the operation.
Definition at line 20 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), TUNGraph::TNode::GetDeg(), IAssertR, TUNGraph::TNode::Id, IsNode(), TMath::Mx(), MxNId, NEdges, TUNGraph::TNode::NIdV, NodeH, and TVec< TVal, TSizeTy >::Sort().
{
int NewNId;
if (NId == -1) {
NewNId = MxNId; MxNId++;
} else {
IAssertR(! IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
NewNId = NId;
MxNId = TMath::Mx(NewNId+1, MxNId());
}
TNode& Node = NodeH.AddDat(NewNId);
Node.Id = NewNId;
Node.NIdV = NbrNIdV;
Node.NIdV.Sort();
NEdges += Node.GetDeg();
return NewNId;
}
| int TUNGraph::AddNode | ( | const int & | NId, |
| const TVecPool< TInt > & | Pool, | ||
| const int & | NIdVId | ||
| ) |
Adds a node of ID NId to the graph and create edges to all nodes in vector NIdVId in the vector pool Pool.
Returns the ID of the node being added. If NId is -1, node ID is automatically assigned. Aborts, if a node with ID NId already exists.
The operation can create inconsistent graphs when the neighboring nodes stored in the Pool vector are not explicitly added to the graph. Use TUNGraph::IsOk to check that the resulting graph is consistent.
Definition at line 38 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), TVec< TVal, TSizeTy >::GenExt(), TUNGraph::TNode::GetDeg(), TVecPool< TVal, TSizeTy >::GetValVPt(), TVecPool< TVal, TSizeTy >::GetVLen(), IAssertR, TUNGraph::TNode::Id, IsNode(), TMath::Mx(), MxNId, NEdges, TUNGraph::TNode::NIdV, NodeH, and TVec< TVal, TSizeTy >::Sort().
{
int NewNId;
if (NId == -1) {
NewNId = MxNId; MxNId++;
} else {
IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
NewNId = NId;
MxNId = TMath::Mx(NewNId+1, MxNId());
}
TNode& Node = NodeH.AddDat(NewNId);
Node.Id = NewNId;
Node.NIdV.GenExt(Pool.GetValVPt(NIdVId), Pool.GetVLen(NIdVId));
Node.NIdV.Sort();
NEdges += Node.GetDeg();
return NewNId;
}
| TEdgeI TUNGraph::BegEI | ( | ) | const [inline] |
Returns an iterator referring to the first edge in the graph.
Definition at line 227 of file graph.h.
References BegNI(), EndNI(), TUNGraph::TNodeI::GetId(), GetNodes(), TUNGraph::TNodeI::GetOutDeg(), and TUNGraph::TNodeI::GetOutNId().
Referenced by TAGMFast::FindComsByCV(), IsOk(), and TAGMUtil::SaveGephi().
{ TNodeI NI = BegNI(); TEdgeI EI(NI, EndNI(), 0); if (GetNodes() != 0 && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { EI++; } return EI; }
| TNodeI TUNGraph::BegNI | ( | ) | const [inline] |
Returns an iterator referring to the first node in the graph.
Definition at line 201 of file graph.h.
References THash< TKey, TDat, THashFunc >::BegI(), and NodeH.
Referenced by BegEI(), TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN(), TLocClust::DrawWhiskers(), TAGMFit::GetEdgeJointCom(), TCliqueOverlap::GetMaximalCliques(), TSnap::TSnapDetail::TCNMQMatrix::Init(), TAGMFit::InitNodeData(), TTimeNet::PlotEffDiam(), TTimeNet::PlotMedianDegOverTm(), TTimeNet::PlotMissingPast(), TAGMUtil::SaveGephi(), TLocClust::SavePajek(), and TKronMomentsFit::TKronMomentsFit().
| void TUNGraph::Clr | ( | ) | [inline] |
| void TUNGraph::Defrag | ( | const bool & | OnlyNodeLinks = false | ) |
Defragments the graph.
After performing many node and edge insertions and deletions to a graph, the graph data structure will be fragmented in memory. This function compacts down the graph data structure and frees unneeded memory.
Definition at line 129 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::Defrag(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), THash< TKey, TDat, THashFunc >::IsKeyIdEqKeyN(), NodeH, and THash< TKey, TDat, THashFunc >::Pack().
Referenced by TAGM::GenAGM(), TSnap::GenSmallWorld(), and TTimeNet::PlotMissingPast().
{
for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
NodeH[n].NIdV.Pack();
}
if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
NodeH.Defrag();
}
}
| void TUNGraph::DelEdge | ( | const int & | SrcNId, |
| const int & | DstNId | ||
| ) |
Deletes an edge between node IDs SrcNId and DstNId from the graph.
If the edge (SrcNId, DstNId) does not exist in the graph function still completes. But the function aborts if SrcNId or DstNId are not nodes in the graph.
Definition at line 92 of file graph.cpp.
References TVec< TVal, TSizeTy >::Del(), TStr::Fmt(), GetNode(), IAssertR, IsNode(), NEdges, TUNGraph::TNode::NIdV, and TVec< TVal, TSizeTy >::SearchBin().
Referenced by TSnap::TSnapDetail::CmtyGirvanNewmanStep(), TSnap::GenDegSeq(), and TTimeNet::PlotMissingPast().
{
IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
{ TNode& N = GetNode(SrcNId);
const int n = N.NIdV.SearchBin(DstNId);
if (n!= -1) { N.NIdV.Del(n); NEdges--; } }
if (SrcNId != DstNId) { // not a self edge
TNode& N = GetNode(DstNId);
const int n = N.NIdV.SearchBin(SrcNId);
if (n!= -1) { N.NIdV.Del(n); }
}
}
| void TUNGraph::DelNode | ( | const int & | NId | ) |
Deletes node of ID NId from the graph.
If the node of ID NId does not exist the function aborts.
Definition at line 56 of file graph.cpp.
References AssertR, TVec< TVal, TSizeTy >::Del(), THash< TKey, TDat, THashFunc >::DelKey(), TStr::Fmt(), TUNGraph::TNode::GetDeg(), TUNGraph::TNode::GetNbrNId(), GetNode(), IAssert, IsNode(), NEdges, TUNGraph::TNode::NIdV, NodeH, and TVec< TVal, TSizeTy >::SearchBin().
{
{ AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
TNode& Node = GetNode(NId);
NEdges -= Node.GetDeg();
for (int e = 0; e < Node.GetDeg(); e++) {
const int nbr = Node.GetNbrNId(e);
if (nbr == NId) { continue; }
TNode& N = GetNode(nbr);
const int n = N.NIdV.SearchBin(NId);
IAssert(n != -1); // if NId points to N, then N also should point back
if (n!= -1) { N.NIdV.Del(n); }
} }
NodeH.DelKey(NId);
}
| void TUNGraph::DelNode | ( | const TNode & | NodeI | ) | [inline] |
| void TUNGraph::Dump | ( | FILE * | OutF = stdout | ) | const |
Print the graph in a human readable form to an output stream OutF.
Definition at line 176 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TUNGraph::TNode::GetDeg(), GetEdges(), TUNGraph::TNode::GetId(), TUNGraph::TNode::GetNbrNId(), GetNodes(), and NodeH.
{
const int NodePlaces = (int) ceil(log10((double) GetNodes()));
fprintf(OutF, "-------------------------------------------------\nUndirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
const TNode& Node = NodeH[N];
fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
for (int edge = 0; edge < Node.GetDeg(); edge++) {
fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
fprintf(OutF, "\n");
}
fprintf(OutF, "\n");
}
| bool TUNGraph::Empty | ( | ) | const [inline] |
Tests whether the graph is empty (has zero nodes).
Definition at line 245 of file graph.h.
References GetNodes().
{ return GetNodes()==0; }
| TEdgeI TUNGraph::EndEI | ( | ) | const [inline] |
Returns an iterator referring to the past-the-end edge in the graph.
Definition at line 229 of file graph.h.
References EndNI().
Referenced by TAGMFast::FindComsByCV(), IsOk(), and TAGMUtil::SaveGephi().
| TNodeI TUNGraph::EndNI | ( | ) | const [inline] |
Returns an iterator referring to the past-the-end node in the graph.
Definition at line 203 of file graph.h.
References THash< TKey, TDat, THashFunc >::EndI(), and NodeH.
Referenced by BegEI(), TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN(), TLocClust::DrawWhiskers(), EndEI(), TAGMFit::GetEdgeJointCom(), GetEI(), TCliqueOverlap::GetMaximalCliques(), TSnap::TSnapDetail::TCNMQMatrix::Init(), TAGMFit::InitNodeData(), TTimeNet::PlotEffDiam(), TTimeNet::PlotMedianDegOverTm(), TTimeNet::PlotMissingPast(), TAGMUtil::SaveGephi(), TLocClust::SavePajek(), and TKronMomentsFit::TKronMomentsFit().
| int TUNGraph::GetEdges | ( | ) | const |
Returns the number of edges in the graph.
Definition at line 71 of file graph.cpp.
References NEdges.
Referenced by TLocClustStat::AddCut(), TUndirFFire::AddNodes(), TLocClustStat::AddToBestCutH(), TLocClust::DrawWhiskers(), Dump(), TAGMUtil::FindComsByAGM(), TAGMFast::FindComsByCV(), TAGM::GenAGM(), TAGMFast::GetCmtyVV(), TAGMUtil::GetConductance(), TCliqueOverlap::GetCPMCommunities(), TLocClust::GetCutStat(), TAGMFit::GetEdgeJointCom(), TTimeNENet::GetTriadEdges(), TLocClustStat::ImposeNCP(), TSnap::TSnapDetail::TCNMQMatrix::Init(), IsOk(), TAGMFit::MLEGradAscentGivenCAG(), TAGMFast::NeighborComInit(), TAGMFit::NeighborComInit(), TLocClustStat::ParamStr(), TLocClustStat::PlotBoltzmanCurve(), TTimeNet::PlotCCfOverTm(), TTimeNet::PlotEffDiam(), TTimeNet::PlotMedianDegOverTm(), TLocClustStat::PlotNCPModul(), TLocClustStat::Run(), TAGMFit::RunMCMC(), TLocClust::SavePajek(), and TLocClustStat::SaveTxtInfo().
{
//int Edges = 0;
//for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
// Edges += NodeH[N].GetDeg();
//}
//return Edges/2;
return NEdges;
}
| TEdgeI TUNGraph::GetEI | ( | const int & | EId | ) | const |
Not supported/implemented!
| TUNGraph::TEdgeI TUNGraph::GetEI | ( | const int & | SrcNId, |
| const int & | DstNId | ||
| ) | const |
Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
Note that since this is an undirected graph GetEI(SrcNId, DstNId) has the same effect as GetEI(DstNId, SrcNId).
Definition at line 111 of file graph.cpp.
References EndNI(), GetNI(), IAssert, TMath::Mn(), TMath::Mx(), MxNId, and TUNGraph::TNodeI::NodeHI.
{
const int MnNId = TMath::Mn(SrcNId, DstNId);
const int MxNId = TMath::Mx(SrcNId, DstNId);
const TNodeI SrcNI = GetNI(MnNId);
const int NodeN = SrcNI.NodeHI.GetDat().NIdV.SearchBin(MxNId);
IAssert(NodeN != -1);
return TEdgeI(SrcNI, EndNI(), NodeN);
}
| int TUNGraph::GetMxNId | ( | ) | const [inline] |
| TNodeI TUNGraph::GetNI | ( | const int & | NId | ) | const [inline] |
Returns an iterator referring to the node of ID NId in the graph.
Definition at line 205 of file graph.h.
References THash< TKey, TDat, THashFunc >::GetI(), and NodeH.
Referenced by TSnap::TSnapDetail::_GirvanNewmanGetModularity(), TLocClust::ApproxPageRank(), TLocClustStat::BagOfWhiskers(), TLocClustStat::BagOfWhiskers2(), TUndirFFire::BurnGeoFire(), TLocClust::DrawWhiskers(), TLocClust::FindBestCut(), TAGMUtil::GetConductance(), TLocClust::GetCutStat(), GetEI(), TLocClustStat::TCutInfo::GetFracDegOut(), TAGMUtil::GetNbhCom(), TCliqueOverlap::GetNbrs(), TCliqueOverlap::GetNodeIdWithMaxDeg(), GetRndNI(), TAGMFast::GradientForOneVar(), TAGMFast::GradientForRow(), TAGMFast::HessianForOneVar(), TSnap::TSnapDetail::TCNMQMatrix::Init(), TAGMFit::JoinCom(), TAGMFit::LeaveCom(), TAGMFast::LikelihoodForOneVar(), TAGMFast::LikelihoodForRow(), TCliqueOverlap::MaxNbrsInCANDNodeId(), TAGMFast::MLEGradAscent(), TAGMFast::MLEGradAscentParallel(), TAGMFast::MLENewton(), TAGMFast::NeighborComInit(), TAGMFit::NeighborComInit(), TAGMFast::RandomInit(), TAGMFit::RandomInit(), TAGMFit::SeekJoin(), TAGMFit::SeekLeave(), TAGMFit::SeekSwitch(), and TLocClust::SupportSweep().
| void TUNGraph::GetNIdV | ( | TIntV & | NIdV | ) | const |
Gets a vector IDs of all nodes in the graph.
Definition at line 122 of file graph.cpp.
References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TVec< TVal, TSizeTy >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), GetNodes(), and NodeH.
Referenced by TAGMFit::AddBaseCmty(), TAGMFit::CalcPNoComByCmtyVV(), TAGMFast::FindComsByCV(), TAGMUtil::GenCmtyVVFromPL(), TAGMFast::MLENewton(), TAGMFit::NeighborComInit(), and TAGMFast::SetGraph().
{
NIdV.Gen(GetNodes(), 0);
for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
NIdV.Add(NodeH.GetKey(N)); }
}
| TNode& TUNGraph::GetNode | ( | const int & | NId | ) | [inline, private] |
| const TNode& TUNGraph::GetNode | ( | const int & | NId | ) | const [inline, private] |
| int TUNGraph::GetNodes | ( | ) | const [inline] |
Returns the number of nodes in the graph.
Definition at line 162 of file graph.h.
References THash< TKey, TDat, THashFunc >::Len(), and NodeH.
Referenced by TUndirFFire::AddNodes(), TLocClust::ApproxPageRank(), BegEI(), TAGMFit::CalcPNoComByCmtyVV(), TUNGraphMtx::CheckNodeIds(), TLocClust::DrawWhiskers(), Dump(), Empty(), TAGMUtil::FindComsByAGM(), TAGMFast::FindComsByCV(), TAGM::GenAGM(), TAGMFast::GetCmtyVV(), TAGMFit::GetCmtyVV(), TCliqueOverlap::GetCPMCommunities(), TCliqueOverlap::GetMaximalCliques(), GetNIdV(), TLocClustStat::ImposeNCP(), TAGMFit::InitNodeData(), TAGMFast::MLEGradAscent(), TAGMFast::MLEGradAscentParallel(), TAGMFast::MLENewton(), TAGMFast::NeighborComInit(), TAGMFit::NeighborComInit(), TLocClustStat::ParamStr(), TUNGraphMtx::PGetCols(), TUNGraphMtx::PGetRows(), TLocClustStat::PlotBoltzmanCurve(), TTimeNet::PlotCCfOverTm(), TTimeNet::PlotEffDiam(), TTimeNet::PlotMedianDegOverTm(), TLocClustStat::PlotNCP(), TLocClustStat::PlotNCPModul(), TLocClustStat::PlotNCPScatter(), TLocClustStat::PlotNcpTop10(), TLocClustStat::PlotPhiInOut(), TAGMFast::RandomInit(), TAGMFit::RandomInitCmtyVV(), TLocClustStat::Run(), TAGMFit::RunMCMC(), TAGMFit::SampleTransition(), TLocClust::SavePajek(), TLocClustStat::SaveTxtInfo(), TAGMFast::SetCmtyVV(), TAGMFit::SetDefaultPNoCom(), TAGMFast::SetGraph(), TKronMomentsFit::Test(), and TUNGraphMtx::TUNGraphMtx().
| TNodeI TUNGraph::GetRndNI | ( | TRnd & | Rnd = TInt::Rnd | ) | [inline] |
Returns an interator referring to a random node in the graph.
Definition at line 240 of file graph.h.
References GetNI(), and GetRndNId().
Referenced by TAGMFit::NeighborComInit().
| int TUNGraph::GetRndNId | ( | TRnd & | Rnd = TInt::Rnd | ) | [inline] |
Returns an ID of a random node in the graph.
Definition at line 238 of file graph.h.
References THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::GetRndKeyId(), and NodeH.
Referenced by GetRndNI(), TLocClustStat::Run(), and TAGMFit::SampleTransition().
{ return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
| PUNGraph TUNGraph::GetSmallGraph | ( | ) | [static] |
Returns a small graph on 5 nodes and 5 edges.
* Graph: 3--0--4 * /| * 1-2 *
Definition at line 190 of file graph.cpp.
References AddEdge(), AddNode(), and New().
{
PUNGraph Graph = TUNGraph::New();
for (int i = 0; i < 5; i++) { Graph->AddNode(i); }
Graph->AddEdge(0,1); Graph->AddEdge(0,2);
Graph->AddEdge(0,3); Graph->AddEdge(0,4);
Graph->AddEdge(1,2);
return Graph;
}
| bool TUNGraph::HasFlag | ( | const TGraphFlag & | Flag | ) | const |
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition at line 3 of file graph.cpp.
References HasGraphFlag.
{
return HasGraphFlag(TUNGraph::TNet, Flag);
}
| bool TUNGraph::IsEdge | ( | const int & | SrcNId, |
| const int & | DstNId | ||
| ) | const |
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition at line 105 of file graph.cpp.
References GetNode(), TUNGraph::TNode::IsNbrNId(), and IsNode().
Referenced by AddEdge(), TAGMFit::CalcPNoComByCmtyVV(), TSnap::GenDegSeq(), TTimeNENet::GetTriadEdges(), TCluster::Gradient(), TAGMFast::LikelihoodHoldOut(), TCluster::LogLikelihood(), and TCluster::MCMC().
{
if (! IsNode(SrcNId) || ! IsNode(DstNId)) return false;
return GetNode(SrcNId).IsNbrNId(DstNId);
}
| bool TUNGraph::IsNode | ( | const int & | NId | ) | const [inline] |
Tests whether ID NId is a node.
Definition at line 199 of file graph.h.
References THash< TKey, TDat, THashFunc >::IsKey(), and NodeH.
Referenced by AddEdge(), AddNode(), TUNGraphMtx::CheckNodeIds(), DelEdge(), DelNode(), TAGM::GenAGM(), TAGMUtil::GetConductance(), TLocClust::GetCutStat(), TTimeNENet::GetTriadEdges(), IsEdge(), IsOk(), TTimeNet::PlotMissingPast(), TAGMFit::SeekLeave(), TAGMFast::SetCmtyVV(), TAGMFit::SetCmtyVV(), TAGMFast::SetGraph(), and TGraphAttributes::TGraphAttributes().
| bool TUNGraph::IsOk | ( | const bool & | ThrowExcept = true | ) | const |
Checks the graph data structure for internal consistency.
For each node in the graph check that its neighbors are also nodes in the graph.
Definition at line 139 of file graph.cpp.
References BegEI(), TStr::CStr(), EAssertR, EndEI(), ErrNotify(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TUNGraph::TNode::GetDeg(), GetEdges(), TUNGraph::TNode::GetId(), TUNGraph::TNode::GetNbrNId(), IsNode(), TVec< TVal, TSizeTy >::IsSorted(), TUNGraph::TNode::NIdV, and NodeH.
{
bool RetVal = true;
for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
const TNode& Node = NodeH[N];
if (! Node.NIdV.IsSorted()) {
const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", Node.GetId());
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
RetVal=false;
}
int prevNId = -1;
for (int e = 0; e < Node.GetDeg(); e++) {
if (! IsNode(Node.GetNbrNId(e))) {
const TStr Msg = TStr::Fmt("Edge %d --> %d: node %d does not exist.",
Node.GetId(), Node.GetNbrNId(e), Node.GetNbrNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
RetVal=false;
}
if (e > 0 && prevNId == Node.GetNbrNId(e)) {
const TStr Msg = TStr::Fmt("Node %d has duplicate edge %d --> %d.",
Node.GetId(), Node.GetId(), Node.GetNbrNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
RetVal=false;
}
prevNId = Node.GetNbrNId(e);
}
}
int EdgeCnt = 0;
for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { EdgeCnt++; }
if (EdgeCnt != GetEdges()) {
const TStr Msg = TStr::Fmt("Number of edges counter is corrupted: GetEdges():%d, EdgeCount:%d.", GetEdges(), EdgeCnt);
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
RetVal=false;
}
return RetVal;
}
| static PUNGraph TUNGraph::Load | ( | TSIn & | SIn | ) | [inline, static] |
Static constructor that loads the graph from a stream SIn and returns a pointer to it.
Definition at line 155 of file graph.h.
References TUNGraph().
Referenced by TAGMFast::Load().
| static PUNGraph TUNGraph::New | ( | ) | [inline, static] |
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition at line 149 of file graph.h.
References TUNGraph().
Referenced by TCliqueOverlap::CalculateOverlapMtx(), TAGM::GenAGM(), TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenGeoPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), TSnap::Get1CnCom(), TSnap::Get1CnComSzCnt(), GetSmallGraph(), TSnap::GetSubGraph(), and TNetConstraint< PGraph >::Test().
{ return new TUNGraph(); }
| static PUNGraph TUNGraph::New | ( | const int & | Nodes, |
| const int & | Edges | ||
| ) | [inline, static] |
Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and Edges edges.
Call: PUNGraph Graph = TUNGraph::New(Nodes, Edges).
Definition at line 153 of file graph.h.
References TUNGraph().
{ return new TUNGraph(Nodes, Edges); }
| void TUNGraph::Reserve | ( | const int & | Nodes, |
| const int & | Edges | ||
| ) | [inline] |
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition at line 249 of file graph.h.
References THash< TKey, TDat, THashFunc >::Gen(), and NodeH.
Referenced by TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), TSnap::GetSubGraph(), and TUNGraph().
| void TUNGraph::ReserveNIdDeg | ( | const int & | NId, |
| const int & | Deg | ||
| ) | [inline] |
Reserves memory for node ID NId having Deg edges.
Definition at line 251 of file graph.h.
References GetNode(), TUNGraph::TNode::NIdV, and TVec< TVal, TSizeTy >::Reserve().
| void TUNGraph::Save | ( | TSOut & | SOut | ) | const [inline] |
Saves the graph to a (binary) stream SOut.
Definition at line 147 of file graph.h.
References MxNId, NEdges, NodeH, THash< TKey, TDat, THashFunc >::Save(), and TInt::Save().
Referenced by TAGMFit::Save(), and TAGMFast::Save().
friend class TUNGraphMtx [friend] |
TCRef TUNGraph::CRef [private] |
TInt TUNGraph::MxNId [private] |
Definition at line 134 of file graph.h.
Referenced by AddNode(), Clr(), GetEI(), GetMxNId(), operator=(), and Save().
TInt TUNGraph::NEdges [private] |
Definition at line 134 of file graph.h.
Referenced by AddEdge(), AddNode(), Clr(), DelEdge(), DelNode(), GetEdges(), operator=(), and Save().
THash<TInt, TNode> TUNGraph::NodeH [private] |
Definition at line 135 of file graph.h.
Referenced by AddNode(), BegNI(), Clr(), Defrag(), DelNode(), Dump(), EndNI(), GetNI(), GetNIdV(), GetNode(), GetNodes(), GetRndNId(), IsNode(), IsOk(), operator=(), TUNGraphMtx::PMultiply(), TUNGraphMtx::PMultiplyT(), Reserve(), and Save().
1.8.0