|
SNAP Library , Developer Reference
2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
|
SNAP Library , Developer Reference
2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
Directed 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 TNGraph | TNet |
| typedef TPt< TNGraph > | PNet |
Public Member Functions | |
| TNGraph () | |
| TNGraph (const int &Nodes, const int &Edges) | |
| Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges. | |
| TNGraph (const TNGraph &Graph) | |
| TNGraph (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). | |
| TNGraph & | operator= (const TNGraph &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 &NodeId) |
| Adds a node of ID NodeI.GetId() to the graph. | |
| int | AddNode (const int &NId, const TIntV &InNIdV, const TIntV &OutNIdV) |
| Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV, creates edges from the node to all nodes in vector OutNIdV. | |
| int | AddNode (const int &NId, const TVecPool< TInt > &Pool, const int &SrcVId, const int &DstVId) |
| Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV in the vector pool Pool, creates edges from the node to all nodes in vector OutNIdVin 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 from node IDs SrcNId to node DstNId to the graph. | |
| int | AddEdge (const TEdgeI &EdgeI) |
| Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph. | |
| void | DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true) |
| Deletes an edge from node IDs SrcNId to DstNId from the graph. | |
| bool | IsEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true) const |
| Tests whether an edge from node IDs SrcNId to DstNId exists in the graph. | |
| 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 | ReserveNIdInDeg (const int &NId, const int &InDeg) |
| Reserves memory for node ID NId having InDeg in-edges. | |
| void | ReserveNIdOutDeg (const int &NId, const int &OutDeg) |
| Reserves memory for node ID NId having OutDeg out-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 PNGraph | New () |
| Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New(). | |
| static PNGraph | 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 PNGraph | Load (TSIn &SIn) |
| Static constructor that loads the graph from a stream SIn and returns a pointer to it. | |
| static PNGraph | GetSmallGraph () |
| Returns a small graph on 5 nodes and 6 edges. | |
Private Member Functions | |
| TNode & | GetNode (const int &NId) |
| const TNode & | GetNode (const int &NId) const |
Private Attributes | |
| TCRef | CRef |
| TInt | MxNId |
| THash< TInt, TNode > | NodeH |
Friends | |
| class | TPt< TNGraph > |
| class | TNGraphMtx |
Directed graph.
Node IDs can be arbitrary non-negative integers. Nodes and edges have no attributes/data associated with them. There is at most one directed edge from one source node to a destination node. There can be an edge between the same pair of nodes in the opposite direction. Self loops (one per node) are allowed but multiple (parallel) edges are not. The directed 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<TNGraph> TNGraph::PNet |
| typedef TNGraph TNGraph::TNet |
| TNGraph::TNGraph | ( | ) | [inline] |
| TNGraph::TNGraph | ( | const int & | Nodes, |
| const int & | Edges | ||
| ) | [inline, explicit] |
| TNGraph::TNGraph | ( | const TNGraph & | Graph | ) | [inline] |
| TNGraph::TNGraph | ( | TSIn & | SIn | ) | [inline] |
| int TNGraph::AddEdge | ( | const int & | SrcNId, |
| const int & | DstNId | ||
| ) |
Adds an edge from node IDs SrcNId to node 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 TNGraph have no IDs we return -1. Function aborts if SrcNId or DstNId are not nodes in the graph.
Definition at line 283 of file graph.cpp.
References TVec< TVal >::AddSorted(), TStr::Fmt(), GetNode(), IAssertR, TNGraph::TNode::InNIdV, IsEdge(), IsNode(), and TNGraph::TNode::OutNIdV.
Referenced by TFfGGen::AddNodes(), TKronNoise::FlipEdgeNoise(), TMAGParam< TNodeAttr >::GenAttrMAG(), TSnap::GenCopyModel(), TKronMtx::GenDetKronecker(), TKronMtx::GenFastKronecker(), TKronMtx::GenKronecker(), TSnap::GenRMat(), TKronMtx::GenRndGraph(), TKronMtx::GenThreshGraph(), TSnap::GetBfsTree(), TGraphEnumUtils::GetGraph(), TNIBs::GetGroundTruthGraphAtT(), TGraphEnumUtils::GetIndGraph(), TNIBs::GetInferredGraphAtT(), TGraphKey::GetNGraph(), TGraphEnumUtils::GetNormalizedGraph(), GetSmallGraph(), TBigNet< TNodeData, IsDir >::GetSubNGraph(), TNetInfBs::GreedyOpt(), TSnap::LoadDyNet(), TSnap::LoadDyNetGraphV(), TNetInfBs::LoadGroundTruthTxt(), main(), and TKroneckerLL::SetRandomEdges().
{
IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
//IAssert(! IsEdge(SrcNId, DstNId));
if (IsEdge(SrcNId, DstNId)) { return -2; }
GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
GetNode(DstNId).InNIdV.AddSorted(SrcNId);
return -1; // edge id
}
| int TNGraph::AddEdge | ( | const TEdgeI & | EdgeI | ) | [inline] |
Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph.
Definition at line 479 of file graph.h.
References AddEdge(), TNGraph::TEdgeI::GetDstNId(), and TNGraph::TEdgeI::GetSrcNId().
Referenced by AddEdge().
{ return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
| int TNGraph::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 205 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), IAssertR, IsNode(), TMath::Mx(), MxNId, and NodeH.
Referenced by TFfGGen::AddNodes(), TKroneckerLL::AppendIsoNodes(), TMAGParam< TNodeAttr >::GenAttrMAG(), TSnap::GenCopyModel(), TKronMtx::GenDetKronecker(), TKronMtx::GenFastKronecker(), TKronMtx::GenKronecker(), TSnap::GenRMat(), TKronMtx::GenRndGraph(), TKronMtx::GenThreshGraph(), TSnap::GetBfsTree(), TGraphEnumUtils::GetGraph(), TNIBs::GetGroundTruthGraphAtT(), TGraphEnumUtils::GetIndGraph(), TNIBs::GetInferredGraphAtT(), TGraphKey::GetNGraph(), TBigNet< TNodeData, IsDir >::GetNGraph(), TGraphEnumUtils::GetNormalizedGraph(), GetSmallGraph(), TBigNet< TNodeData, IsDir >::GetSubNGraph(), TNetInfBs::Init(), TSnap::LoadDyNet(), TSnap::LoadDyNetGraphV(), TNetInfBs::LoadGroundTruthTxt(), and main().
{
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 TNGraph::AddNode | ( | const TNodeI & | NodeId | ) | [inline] |
| int TNGraph::AddNode | ( | const int & | NId, |
| const TIntV & | InNIdV, | ||
| const TIntV & | OutNIdV | ||
| ) |
Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV, creates edges from the node to all nodes in vector OutNIdV.
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 vectors InNIdV and OutNIdV do not exist. Use TNGraph::IsOk to check that the resulting graph is consistent after the operation.
Definition at line 218 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), IAssertR, TNGraph::TNode::Id, TNGraph::TNode::InNIdV, IsNode(), TMath::Mx(), MxNId, NodeH, TNGraph::TNode::OutNIdV, and TVec< TVal >::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.InNIdV = InNIdV;
Node.OutNIdV = OutNIdV;
Node.InNIdV.Sort();
Node.OutNIdV.Sort();
return NewNId;
}
| int TNGraph::AddNode | ( | const int & | NId, |
| const TVecPool< TInt > & | Pool, | ||
| const int & | SrcVId, | ||
| const int & | DstVId | ||
| ) |
Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV in the vector pool Pool, creates edges from the node to all nodes in vector OutNIdVin 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 TNGraph::IsOk to check that the resulting graph is consistent.
Definition at line 238 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), TVec< TVal >::GenExt(), TVecPool< TVal >::GetValVPt(), TVecPool< TVal >::GetVLen(), IAssertR, TNGraph::TNode::Id, TNGraph::TNode::InNIdV, IsNode(), TMath::Mx(), MxNId, NodeH, TNGraph::TNode::OutNIdV, and TVec< TVal >::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.InNIdV.GenExt(Pool.GetValVPt(SrcVId), Pool.GetVLen(SrcVId));
Node.OutNIdV.GenExt(Pool.GetValVPt(DstVId), Pool.GetVLen(DstVId));
Node.InNIdV.Sort();
Node.OutNIdV.Sort();
return NewNId;
}
| TEdgeI TNGraph::BegEI | ( | ) | const [inline] |
Returns an iterator referring to the first edge in the graph.
Definition at line 489 of file graph.h.
References BegNI(), EndNI(), and TNGraph::TNodeI::GetOutDeg().
Referenced by TKronNoise::FlipEdgeNoise(), TGraphEnumUtils::GetIsoGraphs(), TGraphEnumUtils::GetNormalizedGraph(), TMAGFitBern::GradApxAffMtx(), TGraphEnumUtils::GraphId(), TKronNoise::RemoveEdgeNoise(), TNetInfBs::SaveGroundTruth(), TNetInfBs::SavePajek(), TNetInfBs::SavePlaneTextNet(), and TKroneckerLL::SetGraph().
| TNodeI TNGraph::BegNI | ( | ) | const [inline] |
Returns an iterator referring to the first node in the graph.
Definition at line 458 of file graph.h.
References THash< TKey, TDat, THashFunc >::BegI(), and NodeH.
Referenced by BegEI(), TSubGraphsEnum::Gen2Graphs(), TGHash< TDat >::GetNodeMap(), TGraphEnumUtils::GetNormalizedMap(), TSnap::GetSngVals(), TSnap::GetSngVec(), TForestFire::InfectAll(), TForestFire::InfectRnd(), TNetInfBs::Init(), main(), TFfGGen::PlotFireSize(), TTimeNet::PlotMedianDegOverTm(), TSubGraphsEnum::RecurBfs(), TSubGraphsEnum::RecurBfs1(), TNetInfBs::SaveCascades(), TNetInfBs::SaveGroundTruth(), TKroneckerLL::SetDegPerm(), TGraphKey::TakeGraph(), and TGraphKey::TakeSig().
| void TNGraph::Clr | ( | ) | [inline] |
Deletes all nodes and edges from the graph.
Definition at line 507 of file graph.h.
References THash< TKey, TDat, THashFunc >::Clr(), MxNId, and NodeH.
Referenced by TFfGGen::Clr(), and TGraphEnumUtils::GetGraph().
| void TNGraph::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 329 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::Defrag(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TNGraph::TNode::InNIdV, THash< TKey, TDat, THashFunc >::IsKeyIdEqKeyN(), NodeH, TNGraph::TNode::OutNIdV, and TVec< TVal >::Pack().
Referenced by TSnap::GenRMat(), and TGraphKey::GetNGraph().
{
for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
TNode& Node = NodeH[n];
Node.InNIdV.Pack(); Node.OutNIdV.Pack();
}
if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
}
| void TNGraph::DelEdge | ( | const int & | SrcNId, |
| const int & | DstNId, | ||
| const bool & | IsDir = true |
||
| ) |
Deletes an edge from node IDs SrcNId to 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 292 of file graph.cpp.
References TVec< TVal >::Del(), TStr::Fmt(), GetNode(), IAssertR, TNGraph::TNode::InNIdV, IsNode(), TNGraph::TNode::OutNIdV, and TVec< TVal >::SearchBin().
Referenced by TKronNoise::FlipEdgeNoise(), TKroneckerLL::MetroGibbsSampleNext(), TKronNoise::RemoveEdgeNoise(), and TKroneckerLL::RestoreGraph().
{
IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
{ TNode& N = GetNode(SrcNId);
const int n = N.OutNIdV.SearchBin(DstNId);
if (n!= -1) { N.OutNIdV.Del(n); } }
{ TNode& N = GetNode(DstNId);
const int n = N.InNIdV.SearchBin(SrcNId);
if (n!= -1) { N.InNIdV.Del(n); } }
if (! IsDir) {
{ TNode& N = GetNode(SrcNId);
const int n = N.InNIdV.SearchBin(DstNId);
if (n!= -1) { N.InNIdV.Del(n); } }
{ TNode& N = GetNode(DstNId);
const int n = N.OutNIdV.SearchBin(SrcNId);
if (n!= -1) { N.OutNIdV.Del(n); } }
}
}
| void TNGraph::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 256 of file graph.cpp.
References TVec< TVal >::Del(), THash< TKey, TDat, THashFunc >::DelKey(), TNGraph::TNode::GetInDeg(), TNGraph::TNode::GetInNId(), GetNode(), TNGraph::TNode::GetOutDeg(), TNGraph::TNode::GetOutNId(), TNGraph::TNode::InNIdV, NodeH, TNGraph::TNode::OutNIdV, and TVec< TVal >::SearchBin().
Referenced by TKronNoise::RemoveNodeNoise(), and TKroneckerLL::RestoreGraph().
{
{ TNode& Node = GetNode(NId);
for (int e = 0; e < Node.GetOutDeg(); e++) {
const int nbr = Node.GetOutNId(e);
if (nbr == NId) { continue; }
TNode& N = GetNode(nbr);
const int n = N.InNIdV.SearchBin(NId);
if (n!= -1) { N.InNIdV.Del(n); }
}
for (int e = 0; e < Node.GetInDeg(); e++) {
const int nbr = Node.GetInNId(e);
if (nbr == NId) { continue; }
TNode& N = GetNode(nbr);
const int n = N.OutNIdV.SearchBin(NId);
if (n!= -1) { N.OutNIdV.Del(n); }
} }
NodeH.DelKey(NId);
}
| void TNGraph::DelNode | ( | const TNode & | NodeI | ) | [inline] |
| void TNGraph::Dump | ( | FILE * | OutF = stdout | ) | const |
Print the graph in a human readable form to an output stream OutF.
Definition at line 384 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), GetEdges(), TNGraph::TNode::GetId(), TNGraph::TNode::GetInDeg(), TNGraph::TNode::GetInNId(), GetNodes(), TNGraph::TNode::GetOutDeg(), TNGraph::TNode::GetOutNId(), and NodeH.
{
const int NodePlaces = (int) ceil(log10((double) GetNodes()));
fprintf(OutF, "-------------------------------------------------\nDirected 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]\n", NodePlaces, Node.GetId());
fprintf(OutF, " in [%d]", Node.GetInDeg());
for (int edge = 0; edge < Node.GetInDeg(); edge++) {
fprintf(OutF, " %*d", NodePlaces, Node.GetInNId(edge)); }
fprintf(OutF, "\n out[%d]", Node.GetOutDeg());
for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
fprintf(OutF, " %*d", NodePlaces, Node.GetOutNId(edge)); }
fprintf(OutF, "\n");
}
fprintf(OutF, "\n");
}
| bool TNGraph::Empty | ( | ) | const [inline] |
Tests whether the graph is empty (has zero nodes).
Definition at line 505 of file graph.h.
References GetNodes().
{ return GetNodes()==0; }
| TEdgeI TNGraph::EndEI | ( | ) | const [inline] |
Returns an iterator referring to the past-the-end edge in the graph.
Definition at line 491 of file graph.h.
References EndNI().
Referenced by TKronNoise::FlipEdgeNoise(), TGraphEnumUtils::GetIsoGraphs(), TGraphEnumUtils::GetNormalizedGraph(), TMAGFitBern::GradApxAffMtx(), TGraphEnumUtils::GraphId(), TKronNoise::RemoveEdgeNoise(), TNetInfBs::SaveGroundTruth(), TNetInfBs::SavePajek(), TNetInfBs::SavePlaneTextNet(), and TKroneckerLL::SetGraph().
| TNodeI TNGraph::EndNI | ( | ) | const [inline] |
Returns an iterator referring to the past-the-end node in the graph.
Definition at line 460 of file graph.h.
References THash< TKey, TDat, THashFunc >::EndI(), and NodeH.
Referenced by BegEI(), EndEI(), TSubGraphsEnum::Gen2Graphs(), GetEI(), TGraphEnumUtils::GetNormalizedMap(), TSnap::GetSngVals(), TSnap::GetSngVec(), TForestFire::InfectAll(), TForestFire::InfectRnd(), TNetInfBs::Init(), main(), TFfGGen::PlotFireSize(), TTimeNet::PlotMedianDegOverTm(), TSubGraphsEnum::RecurBfs(), TSubGraphsEnum::RecurBfs1(), TNetInfBs::SaveCascades(), TNetInfBs::SaveGroundTruth(), TKroneckerLL::SetDegPerm(), TGraphKey::TakeGraph(), and TGraphKey::TakeSig().
| int TNGraph::GetEdges | ( | ) | const |
Returns the number of edges in the graph.
Definition at line 275 of file graph.cpp.
References THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), and NodeH.
Referenced by TFfGGen::AddNodes(), Dump(), TKronNoise::FlipEdgeNoise(), TSubGraphsEnum::Gen2Graphs(), TKronMtx::GenFastKronecker(), TKronMtx::GenKronecker(), TKroneckerLL::GetAbsErr(), TNetInfBs::GetBestEdge(), TNetInfBs::GetBound(), TSnap::GetSngVals(), TSnap::GetSngVec(), TKroneckerLL::GradDescent(), TKroneckerLL::GradDescent2(), TKroneckerLL::GradDescentConvergence(), TNetInfBs::GreedyOpt(), TNetInfBs::LoadGroundTruthTxt(), TMAGFitBern::NormalizeAffMtxV(), TKronMtx::PlotCmpGraphs(), TForestFire::PlotFire(), TFfGGen::PlotFireSize(), TTimeNet::PlotMedianDegOverTm(), TMAGFitBern::PlotProperties(), TSnap::PlotSngValDistr(), TSnap::PlotSngValRank(), TSnap::PlotSngVec(), TKronNoise::RemoveEdgeNoise(), TKroneckerLL::RunMStep(), TKroneckerLL::SetGraph(), TGraphKey::TakeSig(), TGStat::TakeStat(), TKroneckerLL::TestBicCriterion(), TKroneckerLL::TestGradDescent(), TKroneckerLL::TestSamplePerm(), and TMAGFitBern::UnNormalizeAffMtxV().
{
int edges=0;
for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
edges+=NodeH[N].GetOutDeg();
}
return edges;
}
| TEdgeI TNGraph::GetEI | ( | const int & | EId | ) | const |
Not supported/implemented!
| TNGraph::TEdgeI TNGraph::GetEI | ( | const int & | SrcNId, |
| const int & | DstNId | ||
| ) | const |
Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
Definition at line 316 of file graph.cpp.
References EndNI(), GetNI(), IAssert, and TNGraph::TNodeI::NodeHI.
{
const TNodeI SrcNI = GetNI(SrcNId);
const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
IAssert(NodeN != -1);
return TEdgeI(SrcNI, EndNI(), NodeN);
}
| int TNGraph::GetMxNId | ( | ) | const [inline] |
| TNodeI TNGraph::GetNI | ( | const int & | NId | ) | const [inline] |
Returns an iterator referring to the node of ID NId in the graph.
Definition at line 462 of file graph.h.
References THash< TKey, TDat, THashFunc >::GetI(), and NodeH.
Referenced by TForestFire::BurnExpFire(), TForestFire::BurnGeoFire(), TKroneckerLL::CalcApxGraphDLL(), TKroneckerLL::CalcApxGraphLL(), TKroneckerLL::CalcGraphLL(), TNetInfBs::GenCascade(), TSnap::GenCopyModel(), GetEI(), TGraphEnumUtils::GetIndGraph(), TCascade::GetProb(), GetRndNI(), TKroneckerLL::NodeDLLDelta(), TKroneckerLL::NodeLLDelta(), TSubGraphsEnum::RecurBfs(), TSubGraphsEnum::RecurBfs1(), TKroneckerLL::SetBestDegPerm(), and TMAGFitBern::UpdateApxPhiMI().
| void TNGraph::GetNIdV | ( | TIntV & | NIdV | ) | const |
Gets a vector IDs of all nodes in the graph.
Definition at line 323 of file graph.cpp.
References TVec< TVal >::Add(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TVec< TVal >::Gen(), THash< TKey, TDat, THashFunc >::GetKey(), GetNodes(), and NodeH.
Referenced by TKronNoise::FlipEdgeNoise(), TKronNoise::RemoveNodeNoise(), TKroneckerLL::SetGraph(), and TMAGFitBern::SetGraph().
{
NIdV.Gen(GetNodes(), 0);
for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
NIdV.Add(NodeH.GetKey(N)); }
}
| TNode& TNGraph::GetNode | ( | const int & | NId | ) | [inline, private] |
Definition at line 394 of file graph.h.
References THash< TKey, TDat, THashFunc >::GetDat(), and NodeH.
Referenced by AddEdge(), DelEdge(), DelNode(), IsEdge(), ReserveNIdInDeg(), and ReserveNIdOutDeg().
| const TNode& TNGraph::GetNode | ( | const int & | NId | ) | const [inline, private] |
| int TNGraph::GetNodes | ( | ) | const [inline] |
Returns the number of nodes in the graph.
Definition at line 419 of file graph.h.
References THash< TKey, TDat, THashFunc >::Len(), and NodeH.
Referenced by TGStatVec::Add(), TFfGGen::AddNodes(), TKroneckerLL::AppendIsoNodes(), TNGraphMtx::CheckNodeIds(), Dump(), Empty(), TKronNoise::FlipEdgeNoise(), TNetInfBs::GenCascade(), TFfGGen::GenGraph(), TGraphEnumUtils::GetIsoGraphs(), GetNIdV(), TGHash< TDat >::GetNodeMap(), TNetInfBs::GetNodes(), TGraphEnumUtils::GetNormalizedGraph(), TKronMtx::GetNZeroK(), TSnap::GetSngVals(), TSnap::GetSngVec(), TSubGraphEnum< TGraphCounter >::GetSubGraphs(), TKroneckerLL::GradDescent(), TKroneckerLL::GradDescent2(), TKroneckerLL::GradDescentConvergence(), TGraphEnumUtils::GraphId(), TForestFire::InfectAll(), TForestFire::InfectRnd(), TNetInfBs::LoadGroundTruthTxt(), TNGraphMtx::PGetCols(), TNGraphMtx::PGetRows(), TKronMtx::PlotCmpGraphs(), TTimeNENet::PlotEffDiam(), TForestFire::PlotFire(), TFfGGen::PlotFireSize(), TTimeNet::PlotMedianDegOverTm(), TSnap::PlotSngValDistr(), TSnap::PlotSngValRank(), TSnap::PlotSngVec(), TKronNoise::RemoveNodeNoise(), TKroneckerLL::RestoreGraph(), TKroneckerLL::RunMStep(), TKroneckerLL::SetGraph(), TMAGFitBern::SetGraph(), TKroneckerLL::SetOrderPerm(), TKroneckerLL::SetRndPerm(), TGraphKey::TakeGraph(), TGraphKey::TakeSig(), TGStat::TakeSpectral(), TGStat::TakeStat(), TKroneckerLL::TestBicCriterion(), TKroneckerLL::TestGradDescent(), TKroneckerLL::TestSamplePerm(), and TMAGFitBern::TMAGFitBern().
| TNodeI TNGraph::GetRndNI | ( | TRnd & | Rnd = TInt::Rnd | ) | [inline] |
| int TNGraph::GetRndNId | ( | TRnd & | Rnd = TInt::Rnd | ) | [inline] |
Returns an ID of a random node in the graph.
Definition at line 498 of file graph.h.
References THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::GetRndKeyId(), and NodeH.
Referenced by TNetInfBs::GenCascade(), TSnap::GenCopyModel(), and GetRndNI().
{ return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
| PNGraph TNGraph::GetSmallGraph | ( | ) | [static] |
Returns a small graph on 5 nodes and 6 edges.
* Edges: 0 -> 1, 1 -> 2, 0 -> 2, 1 -> 3, 3 -> 4, 2 -> 3 *
Definition at line 401 of file graph.cpp.
References AddEdge(), AddNode(), and New().
{
PNGraph G = TNGraph::New();
for (int i = 0; i < 5; i++) { G->AddNode(i); }
G->AddEdge(0,1); G->AddEdge(1,2); G->AddEdge(0,2);
G->AddEdge(1,3);
G->AddEdge(3,4);
G->AddEdge(2,3);
return G;
}
| bool TNGraph::HasFlag | ( | const TGraphFlag & | Flag | ) | const |
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition at line 201 of file graph.cpp.
References HasGraphFlag.
{
return HasGraphFlag(TNGraph::TNet, Flag);
}
| bool TNGraph::IsEdge | ( | const int & | SrcNId, |
| const int & | DstNId, | ||
| const bool & | IsDir = true |
||
| ) | const |
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition at line 310 of file graph.cpp.
References GetNode(), IsNode(), and TNGraph::TNode::IsOutNId().
Referenced by AddEdge(), TKroneckerLL::CalcFullApxGraphDLL(), TKroneckerLL::CalcGraphDLL(), TMAGFitBern::ComputeApxAdjLL(), TMAGFitBern::ComputeApxLL(), TMAGFitBern::ComputeJointAdjLL(), TMAGFitBern::ComputeJointOneLL(), TKronNoise::FlipEdgeNoise(), TKronMtx::GenFastKronecker(), TSnap::GenRMat(), TNetInfBs::GetBestEdge(), TNetInfBs::GetBound(), TMAGFitBern::GradAffMtx(), TNetInfBs::GreedyOpt(), TGraphEnumUtils::IsEdge(), TKroneckerLL::NodeDLLDelta(), TKroneckerLL::NodeLLDelta(), TKroneckerLL::SetRandomEdges(), TKroneckerLL::SwapNodesLL(), TKroneckerLL::UpdateGraphDLL(), TMAGFitBern::UpdatePhi(), and TMAGFitBern::UpdatePhiMI().
{
if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
}
| bool TNGraph::IsNode | ( | const int & | NId | ) | const [inline] |
Tests whether ID NId is a node.
Definition at line 456 of file graph.h.
References THash< TKey, TDat, THashFunc >::IsKey(), and NodeH.
Referenced by AddEdge(), AddNode(), TNGraphMtx::CheckNodeIds(), DelEdge(), TSnap::GetBfsTree(), TGraphEnumUtils::GetIndGraph(), TBigNet< TNodeData, IsDir >::GetSubNGraph(), TNetInfBs::Init(), IsEdge(), IsOk(), TSnap::LoadDyNet(), TSnap::LoadDyNetGraphV(), TKroneckerLL::NodeDLLDelta(), TKroneckerLL::NodeLLDelta(), TKroneckerLL::SetGraph(), and TMAGFitBern::SetGraph().
| bool TNGraph::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 338 of file graph.cpp.
References TStr::CStr(), EAssertR, ErrNotify(), THash< TKey, TDat, THashFunc >::FFirstKeyId(), TStr::Fmt(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TNGraph::TNode::GetId(), TNGraph::TNode::GetInDeg(), TNGraph::TNode::GetInNId(), TNGraph::TNode::GetOutDeg(), TNGraph::TNode::GetOutNId(), TNGraph::TNode::InNIdV, IsNode(), TVec< TVal >::IsSorted(), NodeH, and TNGraph::TNode::OutNIdV.
{
bool RetVal = true;
for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
const TNode& Node = NodeH[N];
if (! Node.OutNIdV.IsSorted()) {
const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
if (! Node.InNIdV.IsSorted()) {
const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
// check out-edges
int prevNId = -1;
for (int e = 0; e < Node.GetOutDeg(); e++) {
if (! IsNode(Node.GetOutNId(e))) {
const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
if (e > 0 && prevNId == Node.GetOutNId(e)) {
const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
Node.GetId(), Node.GetId(), Node.GetOutNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
prevNId = Node.GetOutNId(e);
}
// check in-edges
prevNId = -1;
for (int e = 0; e < Node.GetInDeg(); e++) {
if (! IsNode(Node.GetInNId(e))) {
const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
if (e > 0 && prevNId == Node.GetInNId(e)) {
const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
Node.GetId(), Node.GetId(), Node.GetInNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
prevNId = Node.GetInNId(e);
}
}
return RetVal;
}
| static PNGraph TNGraph::Load | ( | TSIn & | SIn | ) | [inline, static] |
Static constructor that loads the graph from a stream SIn and returns a pointer to it.
Definition at line 412 of file graph.h.
References TNGraph().
Referenced by TKronMomentsFit::Test().
| static PNGraph TNGraph::New | ( | ) | [inline, static] |
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition at line 406 of file graph.h.
References TNGraph().
Referenced by TMAGParam< TNodeAttr >::GenAttrMAG(), TSnap::GenCopyModel(), TKronMtx::GenDetKronecker(), TKronMtx::GenFastKronecker(), TKronMtx::GenKronecker(), TSnap::GenRMat(), TKronMtx::GenRndGraph(), TKronMtx::GenThreshGraph(), TSnap::GetBfsTree(), TD34GraphCounter::GetGraph(), TNIBs::GetGroundTruthGraphAtT(), TNIBs::GetInferredGraphAtT(), TGraphEnumUtils::GetIsoGraphs(), TGraphKey::GetNGraph(), TBigNet< TNodeData, IsDir >::GetNGraph(), GetSmallGraph(), TBigNet< TNodeData, IsDir >::GetSubNGraph(), TNetInfBs::Init(), TSnap::LoadDyNet(), TSnap::LoadDyNetGraphV(), TNetInfBs::LoadGroundTruthTxt(), main(), and TDGHashGraphCounter::operator()().
{ return new TNGraph(); }
| static PNGraph TNGraph::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: PNGraph Graph = TNGraph::New(Nodes, Edges).
Definition at line 410 of file graph.h.
References TNGraph().
{ return new TNGraph(Nodes, Edges); }
| void TNGraph::Reserve | ( | const int & | Nodes, |
| const int & | Edges | ||
| ) | [inline] |
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition at line 509 of file graph.h.
References THash< TKey, TDat, THashFunc >::Gen(), and NodeH.
Referenced by TSnap::GenCopyModel(), TSnap::GenRMat(), TBigNet< TNodeData, IsDir >::GetNGraph(), and TNGraph().
| void TNGraph::ReserveNIdInDeg | ( | const int & | NId, |
| const int & | InDeg | ||
| ) | [inline] |
Reserves memory for node ID NId having InDeg in-edges.
Definition at line 511 of file graph.h.
References GetNode(), TNGraph::TNode::InNIdV, and TVec< TVal >::Reserve().
Referenced by TBigNet< TNodeData, IsDir >::GetSubNGraph().
| void TNGraph::ReserveNIdOutDeg | ( | const int & | NId, |
| const int & | OutDeg | ||
| ) | [inline] |
Reserves memory for node ID NId having OutDeg out-edges.
Definition at line 513 of file graph.h.
References GetNode(), TNGraph::TNode::OutNIdV, and TVec< TVal >::Reserve().
Referenced by TBigNet< TNodeData, IsDir >::GetSubNGraph().
| void TNGraph::Save | ( | TSOut & | SOut | ) | const [inline] |
Saves the graph to a (binary) stream SOut.
Definition at line 404 of file graph.h.
References MxNId, NodeH, THash< TKey, TDat, THashFunc >::Save(), and TInt::Save().
friend class TNGraphMtx [friend] |
TCRef TNGraph::CRef [private] |
TInt TNGraph::MxNId [private] |
Definition at line 391 of file graph.h.
Referenced by AddNode(), Clr(), GetMxNId(), operator=(), and Save().
THash<TInt, TNode> TNGraph::NodeH [private] |
Definition at line 392 of file graph.h.
Referenced by AddNode(), BegNI(), Clr(), Defrag(), DelNode(), Dump(), EndNI(), GetEdges(), GetNI(), GetNIdV(), GetNode(), GetNodes(), GetRndNId(), IsNode(), IsOk(), operator=(), TNGraphMtx::PMultiply(), TNGraphMtx::PMultiplyT(), Reserve(), and Save().
1.8.0