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
TNGraph Class Reference

Directed graph. More...

#include <graph.h>

Collaboration diagram for TNGraph:

Classes

class  TEdgeI
 Edge iterator. Only forward iteration (operator++) is supported. More...
 
class  TLoadTNodeInitializer
 
class  TNode
 
class  TNodeI
 Node iterator. Only forward iteration (operator++) is supported. More...
 

Public Types

typedef TNGraph TNet
 
typedef TPt< TNGraphPNet
 

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. More...
 
 TNGraph (const TNGraph &Graph)
 
 TNGraph (TSIn &SIn)
 Constructor that loads the graph from a (binary) stream SIn. More...
 
void Save (TSOut &SOut) const
 Saves the graph to a (binary) stream SOut. More...
 
bool HasFlag (const TGraphFlag &Flag) const
 Allows for run-time checking the type of the graph (see the TGraphFlag for flags). More...
 
TNGraphoperator= (const TNGraph &Graph)
 
int GetNodes () const
 Returns the number of nodes in the graph. More...
 
int AddNode (int NId=-1)
 Adds a node of ID NId to the graph. More...
 
int AddNodeUnchecked (int NId=-1)
 Adds a node of ID NId to the network, noop if the node already exists. More...
 
int AddNode (const TNodeI &NodeId)
 Adds a node of ID NodeI.GetId() to the graph. More...
 
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. More...
 
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 . More...
 
void DelNode (const int &NId)
 Deletes node of ID NId from the graph. More...
 
void DelNode (const TNode &NodeI)
 Deletes node of ID NodeI.GetId() from the graph. More...
 
bool IsNode (const int &NId) const
 Tests whether ID NId is a node. More...
 
TNodeI BegNI () const
 Returns an iterator referring to the first node in the graph. More...
 
TNodeI EndNI () const
 Returns an iterator referring to the past-the-end node in the graph. More...
 
TNodeI GetNI (const int &NId) const
 Returns an iterator referring to the node of ID NId in the graph. More...
 
int GetMxNId () const
 Returns an ID that is larger than any node ID in the graph. More...
 
int GetEdges () const
 Returns the number of edges in the graph. More...
 
int AddEdge (const int &SrcNId, const int &DstNId)
 Adds an edge from node SrcNId to node DstNId to the graph. More...
 
int AddEdge (const int &SrcNId, const int &DstNId, const int &EId)
 Adds an edge between node IDs SrcNId and DstNId to the graph, ignores EId (for compatibility with TNEANet). More...
 
int AddEdgeUnchecked (const int &SrcNId, const int &DstNId)
 Adds an edge from node SrcNId to node DstNId to the graph. More...
 
int AddEdge2 (const int &SrcNId, const int &DstNId)
 Adds an edge from node IDs SrcNId to node DstNId to the graph. If nodes do not exist, create them. More...
 
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph. More...
 
void DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true)
 Deletes an edge from node IDs SrcNId to DstNId from the graph. More...
 
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. More...
 
bool IsEdge (const int &EId) const
 Tests whether an edge EId exists in the graph (for compatibility with TNEANet), always returns false. More...
 
TEdgeI BegEI () const
 Returns an iterator referring to the first edge in the graph. More...
 
TEdgeI EndEI () const
 Returns an iterator referring to the past-the-end edge in the graph. More...
 
TEdgeI GetEI (const int &EId) const
 Not supported/implemented! More...
 
TEdgeI GetEI (const int &SrcNId, const int &DstNId) const
 Returns an iterator referring to edge (SrcNId, DstNId) in the graph. More...
 
int GetRndNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random node in the graph. More...
 
TNodeI GetRndNI (TRnd &Rnd=TInt::Rnd)
 Returns an interator referring to a random node in the graph. More...
 
void GetNIdV (TIntV &NIdV) const
 Gets a vector IDs of all nodes in the graph. More...
 
bool Empty () const
 Tests whether the graph is empty (has zero nodes). More...
 
void Clr ()
 Deletes all nodes and edges from the graph. More...
 
void Reserve (const int &Nodes, const int &Edges)
 Reserves memory for a graph of Nodes nodes and Edges edges. More...
 
void ReserveNIdInDeg (const int &NId, const int &InDeg)
 Reserves memory for node ID NId having InDeg in-edges. More...
 
void ReserveNIdOutDeg (const int &NId, const int &OutDeg)
 Reserves memory for node ID NId having OutDeg out-edges. More...
 
void SortNodeAdjV ()
 Sorts the adjacency lists of each node. More...
 
void Defrag (const bool &OnlyNodeLinks=false)
 Defragments the graph. More...
 
bool IsOk (const bool &ThrowExcept=true) const
 Checks the graph data structure for internal consistency. More...
 
void Dump (FILE *OutF=stdout) const
 Print the graph in a human readable form to an output stream OutF. More...
 

Static Public Member Functions

static PNGraph New ()
 Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New(). More...
 
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. More...
 
static PNGraph Load (TSIn &SIn)
 Static constructor that loads the graph from a stream SIn and returns a pointer to it. More...
 
static PNGraph LoadShM (TShMIn &ShMIn)
 Static constructor that loads the graph from a shared memory stream and returns pointer to it. More...
 
static PNGraph GetSmallGraph ()
 Returns a small graph on 5 nodes and 6 edges. More...
 

Private Member Functions

TNodeGetNode (const int &NId)
 
const TNodeGetNode (const int &NId) const
 
void LoadGraphShM (TShMIn &ShMIn)
 

Private Attributes

TCRef CRef
 
TInt MxNId
 
THash< TInt, TNodeNodeH
 

Friends

class TPt< TNGraph >
 
class TNGraphMtx
 

Detailed Description

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.

Definition at line 346 of file graph.h.

Member Typedef Documentation

Definition at line 349 of file graph.h.

Definition at line 348 of file graph.h.

Constructor & Destructor Documentation

TNGraph::TNGraph ( )
inline

Definition at line 472 of file graph.h.

Referenced by Load(), LoadShM(), and New().

472 : CRef(), MxNId(0), NodeH() { }
THash< TInt, TNode > NodeH
Definition: graph.h:455
TCRef CRef
Definition: graph.h:453
TInt MxNId
Definition: graph.h:454

Here is the caller graph for this function:

TNGraph::TNGraph ( const int &  Nodes,
const int &  Edges 
)
inlineexplicit

Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.

Definition at line 474 of file graph.h.

References Reserve().

474 : MxNId(0) { Reserve(Nodes, Edges); }
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:614
TInt MxNId
Definition: graph.h:454

Here is the call graph for this function:

TNGraph::TNGraph ( const TNGraph Graph)
inline

Definition at line 475 of file graph.h.

475 : MxNId(Graph.MxNId), NodeH(Graph.NodeH) { }
THash< TInt, TNode > NodeH
Definition: graph.h:455
TInt MxNId
Definition: graph.h:454
TNGraph::TNGraph ( TSIn SIn)
inline

Constructor that loads the graph from a (binary) stream SIn.

Definition at line 477 of file graph.h.

477 : MxNId(SIn), NodeH(SIn) { }
THash< TInt, TNode > NodeH
Definition: graph.h:455
TInt MxNId
Definition: graph.h:454

Member Function Documentation

int TNGraph::AddEdge ( const int &  SrcNId,
const int &  DstNId 
)

Adds an edge from node 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 321 of file graph.cpp.

References TVec< TVal, TSizeTy >::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::GenRewire(), TSnap::GenRMat(), TKronMtx::GenRndGraph(), TKronMtx::GenThreshGraph(), TSnap::GetEgonet(), TGraphEnumUtils::GetGraph(), TCoda::GetGraphRawNID(), TNIBs::GetGroundTruthGraphAtT(), TGraphEnumUtils::GetIndGraph(), TNIBs::GetInferredGraphAtT(), TGraphKey::GetNGraph(), TGraphEnumUtils::GetNormalizedGraph(), GetSmallGraph(), TSnap::GetSubGraph(), TBigNet< TNodeData, IsDir >::GetSubNGraph(), TNetInfBs::GreedyOpt(), TNetInfBs::LoadGroundTruthTxt(), TCodaAnalyzer::Net2ModeCommunities(), and TKroneckerLL::SetRandomEdges().

321  {
322  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
323  //IAssert(! IsEdge(SrcNId, DstNId));
324  if (IsEdge(SrcNId, DstNId)) { return -2; }
325  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
326  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
327  return -1; // no edge id
328 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1117
TNode & GetNode(const int &NId)
Definition: graph.h:463
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TIntV InNIdV
Definition: graph.h:354
TIntV OutNIdV
Definition: graph.h:354

Here is the call graph for this function:

Here is the caller graph for this function:

int TNGraph::AddEdge ( const int &  SrcNId,
const int &  DstNId,
const int &  EId 
)
inline

Adds an edge between node IDs SrcNId and DstNId to the graph, ignores EId (for compatibility with TNEANet).

Definition at line 569 of file graph.h.

References AddEdge().

Referenced by AddEdge().

569 { return AddEdge(SrcNId, DstNId); }
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321

Here is the call graph for this function:

Here is the caller graph for this function:

int TNGraph::AddEdge ( const TEdgeI EdgeI)
inline

Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph.

Definition at line 582 of file graph.h.

References AddEdge(), TNGraph::TEdgeI::GetDstNId(), and TNGraph::TEdgeI::GetSrcNId().

Referenced by AddEdge().

582 { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321

Here is the call graph for this function:

Here is the caller graph for this function:

int TNGraph::AddEdge2 ( const int &  SrcNId,
const int &  DstNId 
)

Adds an edge from node IDs SrcNId to node DstNId to the graph. If nodes do not exist, create them.

Definition at line 336 of file graph.cpp.

References AddNode(), TVec< TVal, TSizeTy >::AddSorted(), GetNode(), TNGraph::TNode::InNIdV, IsNode(), and TNGraph::TNode::OutNIdV.

336  {
337  if (! IsNode(SrcNId)) { AddNode(SrcNId); }
338  if (! IsNode(DstNId)) { AddNode(DstNId); }
339  if (GetNode(SrcNId).IsOutNId(DstNId)) { return -2; } // edge already exists
340  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
341  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
342  return -1; // no edge id
343 }
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1117
TNode & GetNode(const int &NId)
Definition: graph.h:463
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
TIntV InNIdV
Definition: graph.h:354
TIntV OutNIdV
Definition: graph.h:354

Here is the call graph for this function:

int TNGraph::AddEdgeUnchecked ( const int &  SrcNId,
const int &  DstNId 
)

Adds an edge from node SrcNId to node DstNId to the graph.

Returns -1. The method assumes that SrcNId and DstNId are existing nodes in the graph and adds new neighbor values at the end of their adjacency vectors. No checks are performed to verify these assumptions. Adjacency vectors must be sorted and have duplicates removed after a sequence of these operations to assure consistency of data structures.

Definition at line 330 of file graph.cpp.

References TVec< TVal, TSizeTy >::Add(), GetNode(), TNGraph::TNode::InNIdV, and TNGraph::TNode::OutNIdV.

330  {
331  GetNode(SrcNId).OutNIdV.Add(DstNId);
332  GetNode(DstNId).InNIdV.Add(SrcNId);
333  return -1; // no edge id
334 }
TNode & GetNode(const int &NId)
Definition: graph.h:463
TIntV InNIdV
Definition: graph.h:354
TIntV OutNIdV
Definition: graph.h:354
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

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 236 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), IAssertR, IsNode(), TMath::Mx(), MxNId, and NodeH.

Referenced by AddEdge2(), TFfGGen::AddNodes(), TKroneckerLL::AppendIsoNodes(), TMAGParam< TNodeAttr >::GenAttrMAG(), TSnap::GenCopyModel(), TKronMtx::GenDetKronecker(), TKronMtx::GenFastKronecker(), TKronMtx::GenKronecker(), TSnap::GenRewire(), TSnap::GenRMat(), TKronMtx::GenRndGraph(), TKronMtx::GenThreshGraph(), TSnap::GetEgonet(), TGraphEnumUtils::GetGraph(), TCoda::GetGraphRawNID(), TNIBs::GetGroundTruthGraphAtT(), TGraphEnumUtils::GetIndGraph(), TNIBs::GetInferredGraphAtT(), TGraphKey::GetNGraph(), TBigNet< TNodeData, IsDir >::GetNGraph(), TGraphEnumUtils::GetNormalizedGraph(), GetSmallGraph(), TSnap::GetSubGraph(), TBigNet< TNodeData, IsDir >::GetSubNGraph(), TNetInfBs::Init(), TNetInfBs::LoadGroundTruthTxt(), and TCodaAnalyzer::Net2ModeCommunities().

236  {
237  if (NId == -1) {
238  NId = MxNId; MxNId++;
239  } else {
240  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
241  MxNId = TMath::Mx(NId+1, MxNId());
242  }
243  NodeH.AddDat(NId, TNode(NId));
244  return NId;
245 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
THash< TInt, TNode > NodeH
Definition: graph.h:455
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TInt MxNId
Definition: graph.h:454
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

Here is the caller graph for this function:

int TNGraph::AddNode ( const TNodeI NodeId)
inline

Adds a node of ID NodeI.GetId() to the graph.

Definition at line 517 of file graph.h.

References AddNode(), and TNGraph::TNodeI::GetId().

Referenced by AddNode().

517 { return AddNode(NodeId.GetId()); }
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236

Here is the call graph for this function:

Here is the caller graph for this function:

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 256 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, TSizeTy >::Sort().

256  {
257  int NewNId;
258  if (NId == -1) {
259  NewNId = MxNId; MxNId++;
260  } else {
261  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
262  NewNId = NId;
263  MxNId = TMath::Mx(NewNId+1, MxNId());
264  }
265  TNode& Node = NodeH.AddDat(NewNId);
266  Node.Id = NewNId;
267  Node.InNIdV = InNIdV;
268  Node.OutNIdV = OutNIdV;
269  Node.InNIdV.Sort();
270  Node.OutNIdV.Sort();
271  return NewNId;
272 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
THash< TInt, TNode > NodeH
Definition: graph.h:455
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TInt MxNId
Definition: graph.h:454
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

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 276 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TStr::Fmt(), TVec< TVal, TSizeTy >::GenExt(), TVecPool< TVal, TSizeTy >::GetValVPt(), TVecPool< TVal, TSizeTy >::GetVLen(), IAssertR, TNGraph::TNode::Id, TNGraph::TNode::InNIdV, IsNode(), TMath::Mx(), MxNId, NodeH, TNGraph::TNode::OutNIdV, and TVec< TVal, TSizeTy >::Sort().

276  {
277  int NewNId;
278  if (NId == -1) {
279  NewNId = MxNId; MxNId++;
280  } else {
281  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
282  NewNId = NId;
283  MxNId = TMath::Mx(NewNId+1, MxNId());
284  }
285  TNode& Node = NodeH.AddDat(NewNId);
286  Node.Id = NewNId;
287  Node.InNIdV.GenExt(Pool.GetValVPt(SrcVId), Pool.GetVLen(SrcVId));
288  Node.OutNIdV.GenExt(Pool.GetValVPt(DstVId), Pool.GetVLen(DstVId));
289  Node.InNIdV.Sort();
290  Node.OutNIdV.Sort();
291  return NewNId;
292 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
THash< TInt, TNode > NodeH
Definition: graph.h:455
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TInt MxNId
Definition: graph.h:454
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

int TNGraph::AddNodeUnchecked ( int  NId = -1)

Adds a node of ID NId to the network, noop if the node already exists.

Returns -1, if the node NId already exists. Otherwise, it returns the ID of the node being added. If NId is -1, node ID is automatically assigned.

Definition at line 247 of file graph.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), IsNode(), TMath::Mx(), MxNId, and NodeH.

247  {
248  if (IsNode(NId)) { return NId;}
249  MxNId = TMath::Mx(NId+1, MxNId());
250  NodeH.AddDat(NId, TNode(NId));
251  return NId;
252 }
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
THash< TInt, TNode > NodeH
Definition: graph.h:455
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
TInt MxNId
Definition: graph.h:454
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

TEdgeI TNGraph::BegEI ( ) const
inline

Returns an iterator referring to the first edge in the graph.

Definition at line 594 of file graph.h.

References BegNI(), EndNI(), and TNGraph::TNodeI::GetOutDeg().

Referenced by TempMotifCounter::Count3TEdge2Node(), TempMotifCounter::Count3TEdgeTriads(), ProcessedGraph::countDirTriadMotif(), MotifCluster::EdgeMotifAdjacency(), TKronNoise::FlipEdgeNoise(), TGraphEnumUtils::GetIsoGraphs(), TGraphEnumUtils::GetNormalizedGraph(), TMAGFitBern::GradApxAffMtx(), TGraphEnumUtils::GraphId(), TKronNoise::RemoveEdgeNoise(), TNetInfBs::SaveGroundTruth(), TNetInfBs::SavePajek(), TNetInfBs::SavePlaneTextNet(), and TKroneckerLL::SetGraph().

594 { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0){NI++;} return TEdgeI(NI, EndNI()); }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::Clr ( )
inline

Deletes all nodes and edges from the graph.

Definition at line 612 of file graph.h.

References THash< TKey, TDat, THashFunc >::Clr().

Referenced by TFfGGen::Clr(), and TGraphEnumUtils::GetGraph().

612 { MxNId=0; NodeH.Clr(); }
THash< TInt, TNode > NodeH
Definition: graph.h:455
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TInt MxNId
Definition: graph.h:454

Here is the call graph for this function:

Here is the caller graph for this function:

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 382 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, TSizeTy >::Pack().

Referenced by TSnap::GenRMat(), and TGraphKey::GetNGraph().

382  {
383  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
384  TNode& Node = NodeH[n];
385  Node.InNIdV.Pack(); Node.OutNIdV.Pack();
386  }
387  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
388 }
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
THash< TInt, TNode > NodeH
Definition: graph.h:455
void Defrag()
Definition: hash.h:555
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
void Pack()
Definition: hash.h:289

Here is the call graph for this function:

Here is the caller graph for this function:

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 345 of file graph.cpp.

References TVec< TVal, TSizeTy >::Del(), TStr::Fmt(), GetNode(), IAssertR, TNGraph::TNode::InNIdV, IsNode(), TNGraph::TNode::OutNIdV, and TVec< TVal, TSizeTy >::SearchBin().

Referenced by TKronNoise::FlipEdgeNoise(), TKroneckerLL::MetroGibbsSampleNext(), TKronNoise::RemoveEdgeNoise(), and TKroneckerLL::RestoreGraph().

345  {
346  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
347  { TNode& N = GetNode(SrcNId);
348  const int n = N.OutNIdV.SearchBin(DstNId);
349  if (n!= -1) { N.OutNIdV.Del(n); } }
350  { TNode& N = GetNode(DstNId);
351  const int n = N.InNIdV.SearchBin(SrcNId);
352  if (n!= -1) { N.InNIdV.Del(n); } }
353  if (! IsDir) {
354  { TNode& N = GetNode(SrcNId);
355  const int n = N.InNIdV.SearchBin(DstNId);
356  if (n!= -1) { N.InNIdV.Del(n); } }
357  { TNode& N = GetNode(DstNId);
358  const int n = N.OutNIdV.SearchBin(SrcNId);
359  if (n!= -1) { N.OutNIdV.Del(n); } }
360  }
361 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TNode & GetNode(const int &NId)
Definition: graph.h:463
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599

Here is the call graph for this function:

Here is the caller graph for this function:

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 294 of file graph.cpp.

References TVec< TVal, TSizeTy >::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, TSizeTy >::SearchBin().

Referenced by TCodaAnalyzer::Net2ModeCommunities(), TKronNoise::RemoveNodeNoise(), and TKroneckerLL::RestoreGraph().

294  {
295  { TNode& Node = GetNode(NId);
296  for (int e = 0; e < Node.GetOutDeg(); e++) {
297  const int nbr = Node.GetOutNId(e);
298  if (nbr == NId) { continue; }
299  TNode& N = GetNode(nbr);
300  const int n = N.InNIdV.SearchBin(NId);
301  if (n!= -1) { N.InNIdV.Del(n); }
302  }
303  for (int e = 0; e < Node.GetInDeg(); e++) {
304  const int nbr = Node.GetInNId(e);
305  if (nbr == NId) { continue; }
306  TNode& N = GetNode(nbr);
307  const int n = N.OutNIdV.SearchBin(NId);
308  if (n!= -1) { N.OutNIdV.Del(n); }
309  } }
310  NodeH.DelKey(NId);
311 }
THash< TInt, TNode > NodeH
Definition: graph.h:455
TNode & GetNode(const int &NId)
Definition: graph.h:463
void DelKey(const TKey &Key)
Definition: hash.h:404

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::DelNode ( const TNode NodeI)
inline

Deletes node of ID NodeI.GetId() from the graph.

Definition at line 544 of file graph.h.

References DelNode(), and TNGraph::TNode::GetId().

Referenced by DelNode().

544 { DelNode(NodeI.GetId()); }
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:294

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::Dump ( FILE *  OutF = stdout) const

Print the graph in a human readable form to an output stream OutF.

Definition at line 437 of file graph.cpp.

References edge, 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.

437  {
438  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
439  fprintf(OutF, "-------------------------------------------------\nDirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
440  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
441  const TNode& Node = NodeH[N];
442  fprintf(OutF, " %*d]\n", NodePlaces, Node.GetId());
443  fprintf(OutF, " in [%d]", Node.GetInDeg());
444  for (int edge = 0; edge < Node.GetInDeg(); edge++) {
445  fprintf(OutF, " %*d", NodePlaces, Node.GetInNId(edge)); }
446  fprintf(OutF, "\n out[%d]", Node.GetOutDeg());
447  for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
448  fprintf(OutF, " %*d", NodePlaces, Node.GetOutNId(edge)); }
449  fprintf(OutF, "\n");
450  }
451  fprintf(OutF, "\n");
452 }
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
THash< TInt, TNode > NodeH
Definition: graph.h:455
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278

Here is the call graph for this function:

bool TNGraph::Empty ( ) const
inline

Tests whether the graph is empty (has zero nodes).

Definition at line 610 of file graph.h.

References GetNodes().

610 { return GetNodes()==0; }
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503

Here is the call graph for this function:

TEdgeI TNGraph::EndEI ( ) const
inline

Returns an iterator referring to the past-the-end edge in the graph.

Definition at line 596 of file graph.h.

References EndNI().

Referenced by TempMotifCounter::Count3TEdge2Node(), TempMotifCounter::Count3TEdgeTriads(), ProcessedGraph::countDirTriadMotif(), MotifCluster::EdgeMotifAdjacency(), TKronNoise::FlipEdgeNoise(), TGraphEnumUtils::GetIsoGraphs(), TGraphEnumUtils::GetNormalizedGraph(), TMAGFitBern::GradApxAffMtx(), TGraphEnumUtils::GraphId(), TKronNoise::RemoveEdgeNoise(), TNetInfBs::SaveGroundTruth(), TNetInfBs::SavePajek(), TNetInfBs::SavePlaneTextNet(), and TKroneckerLL::SetGraph().

596 { return TEdgeI(EndNI(), EndNI()); }
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550

Here is the call graph for this function:

Here is the caller graph for this function:

int TNGraph::GetEdges ( ) const

Returns the number of edges in the graph.

Definition at line 313 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(), TCoda::GetGraphRawNID(), TKroneckerLL::GradDescent(), TKroneckerLL::GradDescent2(), TKroneckerLL::GradDescentConvergence(), TNetInfBs::GreedyOpt(), TNetInfBs::LoadGroundTruthTxt(), TCodaAnalyzer::Net2ModeCommunities(), TMAGFitBern::NormalizeAffMtxV(), TKronMtx::PlotCmpGraphs(), TForestFire::PlotFire(), TFfGGen::PlotFireSize(), TTimeNet::PlotMedianDegOverTm(), TMAGFitBern::PlotProperties(), TKronNoise::RemoveEdgeNoise(), TKroneckerLL::RunMStep(), TKroneckerLL::SetGraph(), TGraphKey::TakeSig(), TGStat::TakeStat(), TCodaAnalyzer::TCodaAnalyzer(), TKroneckerLL::TestBicCriterion(), TKroneckerLL::TestGradDescent(), TKroneckerLL::TestSamplePerm(), and TMAGFitBern::UnNormalizeAffMtxV().

313  {
314  int edges=0;
315  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
316  edges+=NodeH[N].GetOutDeg();
317  }
318  return edges;
319 }
THash< TInt, TNode > NodeH
Definition: graph.h:455
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278

Here is the call graph for this function:

Here is the caller graph for this function:

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 369 of file graph.cpp.

References EndNI(), GetNI(), IAssert, and TNGraph::TNodeI::NodeHI.

369  {
370  const TNodeI SrcNI = GetNI(SrcNId);
371  const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
372  IAssert(NodeN != -1);
373  return TEdgeI(SrcNI, EndNI(), NodeN);
374 }
#define IAssert(Cond)
Definition: bd.h:262
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550

Here is the call graph for this function:

int TNGraph::GetMxNId ( ) const
inline

Returns an ID that is larger than any node ID in the graph.

Definition at line 556 of file graph.h.

References MxNId.

Referenced by TempMotifCounter::Count3TEdgeTriads(), MotifCluster::DegreeOrdering(), TempMotifCounter::GetAllStaticTriangles(), MotifCluster::MotifAdjacency(), and TempMotifCounter::TempMotifCounter().

556 { return MxNId; }
TInt MxNId
Definition: graph.h:454

Here is the caller graph for this function:

void TNGraph::GetNIdV ( TIntV NIdV) const

Gets a vector IDs of all nodes in the graph.

Definition at line 376 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 TKronNoise::FlipEdgeNoise(), TCoda::GetNonEdgePairScores(), TCodaAnalyzer::Net2ModeCommunities(), TKronNoise::RemoveNodeNoise(), TCoda::SetGraph(), TKroneckerLL::SetGraph(), and TMAGFitBern::SetGraph().

376  {
377  NIdV.Gen(GetNodes(), 0);
378  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
379  NIdV.Add(NodeH.GetKey(N)); }
380 }
THash< TInt, TNode > NodeH
Definition: graph.h:455
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252

Here is the call graph for this function:

Here is the caller graph for this function:

TNode& TNGraph::GetNode ( const int &  NId)
inlineprivate

Definition at line 463 of file graph.h.

References THash< TKey, TDat, THashFunc >::GetDat().

Referenced by AddEdge(), AddEdge2(), AddEdgeUnchecked(), DelEdge(), DelNode(), IsEdge(), ReserveNIdInDeg(), and ReserveNIdOutDeg().

463 { return NodeH.GetDat(NId); }
THash< TInt, TNode > NodeH
Definition: graph.h:455
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262

Here is the call graph for this function:

Here is the caller graph for this function:

const TNode& TNGraph::GetNode ( const int &  NId) const
inlineprivate

Definition at line 464 of file graph.h.

References THash< TKey, TDat, THashFunc >::GetDat().

464 { return NodeH.GetDat(NId); }
THash< TInt, TNode > NodeH
Definition: graph.h:455
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262

Here is the call graph for this function:

int TNGraph::GetNodes ( ) const
inline

Returns the number of nodes in the graph.

Definition at line 503 of file graph.h.

References THash< TKey, TDat, THashFunc >::Len().

Referenced by TGStatVec::Add(), TFfGGen::AddNodes(), TKroneckerLL::AppendIsoNodes(), TNGraphMtx::CheckNodeIds(), Dump(), TCoda::DumpMemberships(), Empty(), TCoda::FindComsByCV(), TKronNoise::FlipEdgeNoise(), TNetInfBs::GenCascade(), TFfGGen::GenGraph(), TCoda::GetCmtyS(), TCoda::GetCmtyVV(), TCoda::GetCmtyVVUnSorted(), TCoda::GetGraphRawNID(), TGraphEnumUtils::GetIsoGraphs(), GetNIdV(), TGHash< TDat >::GetNodeMap(), TNetInfBs::GetNodes(), TCoda::GetNonEdgePairScores(), TGraphEnumUtils::GetNormalizedGraph(), TKronMtx::GetNZeroK(), TSubGraphEnum< TGraphCounter >::GetSubGraphs(), TKroneckerLL::GradDescent(), TKroneckerLL::GradDescent2(), TKroneckerLL::GradDescentConvergence(), TGraphEnumUtils::GraphId(), TForestFire::InfectAll(), TForestFire::InfectRnd(), TNetInfBs::LoadGroundTruthTxt(), TCoda::MLEGradAscent(), TCoda::MLEGradAscentParallel(), TCoda::NeighborComInit(), TCodaAnalyzer::Net2ModeCommunities(), TNGraphMtx::PGetCols(), TNGraphMtx::PGetRows(), TKronMtx::PlotCmpGraphs(), TTimeNENet::PlotEffDiam(), TForestFire::PlotFire(), TFfGGen::PlotFireSize(), TTimeNet::PlotMedianDegOverTm(), TCoda::RandomInit(), TKronNoise::RemoveNodeNoise(), TKroneckerLL::RestoreGraph(), TKroneckerLL::RunMStep(), TCoda::SetCmtyVV(), TCoda::SetGraph(), TKroneckerLL::SetGraph(), TMAGFitBern::SetGraph(), TKroneckerLL::SetOrderPerm(), TKroneckerLL::SetRndPerm(), TGraphKey::TakeGraph(), TGraphKey::TakeSig(), TGStat::TakeSpectral(), TGStat::TakeStat(), TCodaAnalyzer::TCodaAnalyzer(), TKroneckerLL::TestBicCriterion(), TKroneckerLL::TestGradDescent(), TKroneckerLL::TestSamplePerm(), and TMAGFitBern::TMAGFitBern().

503 { return NodeH.Len(); }
THash< TInt, TNode > NodeH
Definition: graph.h:455
int Len() const
Definition: hash.h:228

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TNGraph::GetRndNI ( TRnd Rnd = TInt::Rnd)
inline

Returns an interator referring to a random node in the graph.

Definition at line 605 of file graph.h.

References GetNI(), and GetRndNId().

605 { return GetNI(GetRndNId(Rnd)); }
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:603

Here is the call graph for this function:

int TNGraph::GetRndNId ( TRnd Rnd = TInt::Rnd)
inline

Returns an ID of a random node in the graph.

Definition at line 603 of file graph.h.

References THash< TKey, TDat, THashFunc >::GetKey(), and THash< TKey, TDat, THashFunc >::GetRndKeyId().

Referenced by TNetInfBs::GenCascade(), TSnap::GenCopyModel(), and GetRndNI().

603 { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
THash< TInt, TNode > NodeH
Definition: graph.h:455
int GetRndKeyId(TRnd &Rnd) const
Get an index of a random element. If the hash table has many deleted keys, this may take a long time...
Definition: hash.h:444
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252

Here is the call graph for this function:

Here is the caller graph for this function:

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 454 of file graph.cpp.

References AddEdge(), AddNode(), and New().

454  {
455  PNGraph G = TNGraph::New();
456  for (int i = 0; i < 5; i++) { G->AddNode(i); }
457  G->AddEdge(0,1); G->AddEdge(1,2); G->AddEdge(0,2);
458  G->AddEdge(1,3); G->AddEdge(3,4); G->AddEdge(2,3);
459  return G;
460 }
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
Definition: bd.h:196

Here is the call graph for this function:

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 232 of file graph.cpp.

References HasGraphFlag.

232  {
233  return HasGraphFlag(TNGraph::TNet, Flag);
234 }
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
Directed graph.
Definition: graph.h:346
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 363 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(), ProcessedGraph::countDirTriadMotif(), TSnap::TSnapDetail::edgeIntersect(), MotifCluster::EdgeMotifAdjacency(), TKronNoise::FlipEdgeNoise(), TKronMtx::GenFastKronecker(), TSnap::GenRMat(), TempMotifCounter::GetAllStaticTriangles(), TNetInfBs::GetBestEdge(), TNetInfBs::GetBound(), TCoda::GetNonEdgePairScores(), TMAGFitBern::GradAffMtx(), TNetInfBs::GreedyOpt(), MotifCluster::IsBidirEdge(), TGraphEnumUtils::IsEdge(), MotifCluster::IsNoEdge(), MotifCluster::IsUnidirEdge(), TCoda::LikelihoodHoldOut(), TKroneckerLL::NodeDLLDelta(), TKroneckerLL::NodeLLDelta(), TKroneckerLL::SetRandomEdges(), TKroneckerLL::SwapNodesLL(), MotifCluster::TriangleMotifAdjacency(), TKroneckerLL::UpdateGraphDLL(), TMAGFitBern::UpdatePhi(), and TMAGFitBern::UpdatePhiMI().

363  {
364  if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
365  if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
366  else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
367 }
TNode & GetNode(const int &NId)
Definition: graph.h:463
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
bool IsOutNId(const int &NId) const
Definition: graph.h:369

Here is the call graph for this function:

Here is the caller graph for this function:

bool TNGraph::IsEdge ( const int &  EId) const
inline

Tests whether an edge EId exists in the graph (for compatibility with TNEANet), always returns false.

Definition at line 592 of file graph.h.

592 { return false; }
bool TNGraph::IsNode ( const int &  NId) const
inline
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 391 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, TSizeTy >::IsSorted(), NodeH, and TNGraph::TNode::OutNIdV.

391  {
392  bool RetVal = true;
393  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
394  const TNode& Node = NodeH[N];
395  if (! Node.OutNIdV.IsSorted()) {
396  const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
397  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
398  }
399  if (! Node.InNIdV.IsSorted()) {
400  const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
401  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
402  }
403  // check out-edges
404  int prevNId = -1;
405  for (int e = 0; e < Node.GetOutDeg(); e++) {
406  if (! IsNode(Node.GetOutNId(e))) {
407  const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
408  Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
409  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
410  }
411  if (e > 0 && prevNId == Node.GetOutNId(e)) {
412  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
413  Node.GetId(), Node.GetId(), Node.GetOutNId(e));
414  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
415  }
416  prevNId = Node.GetOutNId(e);
417  }
418  // check in-edges
419  prevNId = -1;
420  for (int e = 0; e < Node.GetInDeg(); e++) {
421  if (! IsNode(Node.GetInNId(e))) {
422  const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
423  Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
424  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
425  }
426  if (e > 0 && prevNId == Node.GetInNId(e)) {
427  const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
428  Node.GetId(), Node.GetId(), Node.GetInNId(e));
429  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
430  }
431  prevNId = Node.GetInNId(e);
432  }
433  }
434  return RetVal;
435 }
THash< TInt, TNode > NodeH
Definition: graph.h:455
void ErrNotify(const char *NotifyCStr)
Definition: bd.h:74
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
int FFirstKeyId() const
Definition: hash.h:278
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
char * CStr()
Definition: dt.h:479

Here is the call graph for this function:

static PNGraph TNGraph::Load ( TSIn SIn)
inlinestatic

Static constructor that loads the graph from a stream SIn and returns a pointer to it.

Definition at line 487 of file graph.h.

References TNGraph().

Referenced by TCoda::Load(), and TKronMomentsFit::Test().

487 { return PNGraph(new TNGraph(SIn)); }
TNGraph()
Definition: graph.h:472
TPt< TNGraph > PNGraph
Pointer to a directed graph (TNGraph)
Definition: graph.h:16

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::LoadGraphShM ( TShMIn ShMIn)
inlineprivate

Definition at line 465 of file graph.h.

References THash< TKey, TDat, THashFunc >::LoadShM().

Referenced by LoadShM().

465  {
466  MxNId = TInt(ShMIn);
467  TLoadTNodeInitializer Fn;
468  NodeH.LoadShM(ShMIn, Fn);
469  }
THash< TInt, TNode > NodeH
Definition: graph.h:455
void LoadShM(TShMIn &ShMIn)
Load THash from shared memory file. Copying/Deleting Keys is illegal.
Definition: hash.h:157
Definition: dt.h:1137
TInt MxNId
Definition: graph.h:454

Here is the call graph for this function:

Here is the caller graph for this function:

static PNGraph TNGraph::LoadShM ( TShMIn ShMIn)
inlinestatic

Static constructor that loads the graph from a shared memory stream and returns pointer to it.

static constructor to load the graph from memory. Cannot perform operations that edit the edge vectors of nodes or perform illegal operations on the NodeH (deletion or swapping keys)

Definition at line 492 of file graph.h.

References LoadGraphShM(), and TNGraph().

492  {
493  TNGraph* Graph = new TNGraph();
494  Graph->LoadGraphShM(ShMIn);
495  return PNGraph(Graph);
496  }
void LoadGraphShM(TShMIn &ShMIn)
Definition: graph.h:465
TNGraph()
Definition: graph.h:472
TPt< TNGraph > PNGraph
Pointer to a directed graph (TNGraph)
Definition: graph.h:16
Directed graph.
Definition: graph.h:346

Here is the call graph for this function:

static PNGraph TNGraph::New ( const int &  Nodes,
const int &  Edges 
)
inlinestatic

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 485 of file graph.h.

References TNGraph().

485 { return new TNGraph(Nodes, Edges); }
TNGraph()
Definition: graph.h:472

Here is the call graph for this function:

TNGraph& TNGraph::operator= ( const TNGraph Graph)
inline

Definition at line 499 of file graph.h.

References MxNId, and NodeH.

499  {
500  if (this!=&Graph) { MxNId=Graph.MxNId; NodeH=Graph.NodeH; } return *this; }
THash< TInt, TNode > NodeH
Definition: graph.h:455
TInt MxNId
Definition: graph.h:454
void TNGraph::Reserve ( const int &  Nodes,
const int &  Edges 
)
inline

Reserves memory for a graph of Nodes nodes and Edges edges.

Definition at line 614 of file graph.h.

References THash< TKey, TDat, THashFunc >::Gen().

Referenced by TSnap::GenCopyModel(), TSnap::GenRewire(), TSnap::GenRMat(), TBigNet< TNodeData, IsDir >::GetNGraph(), TSnap::GetSubGraph(), and TNGraph().

614 { if (Nodes>0) { NodeH.Gen(Nodes/2); } }
THash< TInt, TNode > NodeH
Definition: graph.h:455
void Gen(const int &ExpectVals)
Definition: hash.h:222

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::ReserveNIdInDeg ( const int &  NId,
const int &  InDeg 
)
inline

Reserves memory for node ID NId having InDeg in-edges.

Definition at line 616 of file graph.h.

References GetNode(), TNGraph::TNode::InNIdV, and TVec< TVal, TSizeTy >::Reserve().

Referenced by TBigNet< TNodeData, IsDir >::GetSubNGraph().

616 { GetNode(NId).InNIdV.Reserve(InDeg); }
TNode & GetNode(const int &NId)
Definition: graph.h:463
TIntV InNIdV
Definition: graph.h:354
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::ReserveNIdOutDeg ( const int &  NId,
const int &  OutDeg 
)
inline

Reserves memory for node ID NId having OutDeg out-edges.

Definition at line 618 of file graph.h.

References GetNode(), TNGraph::TNode::OutNIdV, and TVec< TVal, TSizeTy >::Reserve().

Referenced by TBigNet< TNodeData, IsDir >::GetSubNGraph().

618 { GetNode(NId).OutNIdV.Reserve(OutDeg); }
TNode & GetNode(const int &NId)
Definition: graph.h:463
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
TIntV OutNIdV
Definition: graph.h:354

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::Save ( TSOut SOut) const
inline

Saves the graph to a (binary) stream SOut.

Definition at line 479 of file graph.h.

References THash< TKey, TDat, THashFunc >::Save(), and TInt::Save().

Referenced by TCoda::Save().

479 { MxNId.Save(SOut); NodeH.Save(SOut); }
void Save(TSOut &SOut) const
Definition: dt.h:1153
THash< TInt, TNode > NodeH
Definition: graph.h:455
void Save(TSOut &SOut) const
Definition: hash.h:183
TInt MxNId
Definition: graph.h:454

Here is the call graph for this function:

Here is the caller graph for this function:

void TNGraph::SortNodeAdjV ( )
inline

Sorts the adjacency lists of each node.

Definition at line 620 of file graph.h.

References BegNI(), and EndNI().

620 { for (TNodeI NI = BegNI(); NI < EndNI(); NI++) { NI.SortNIdV();} }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550

Here is the call graph for this function:

Friends And Related Function Documentation

friend class TNGraphMtx
friend

Definition at line 642 of file graph.h.

friend class TPt< TNGraph >
friend

Definition at line 641 of file graph.h.

Member Data Documentation

TCRef TNGraph::CRef
private

Definition at line 453 of file graph.h.

TInt TNGraph::MxNId
private

Definition at line 454 of file graph.h.

Referenced by AddNode(), AddNodeUnchecked(), GetMxNId(), and operator=().


The documentation for this class was generated from the following files: