Undirected graph. More...

#include <graph.h>

Collaboration diagram for TUNGraph:

[legend]

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 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. More...

	TUNGraph (const TUNGraph &Graph)

	TUNGraph (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...

TUNGraph &	operator= (const TUNGraph &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 &NodeI)
	Adds a node of ID NodeI.GetId() to the graph. More...

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. More...

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. 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 between node IDs SrcNId and 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 between node IDs SrcNId and DstNId to the graph. More...

int	AddEdge2 (const int &SrcNId, const int &DstNId)
	Adds an edge between node IDs SrcNId and DstNId to the graph. If nodes do not exists, create them. More...

int	AddEdge (const TEdgeI &EdgeI)
	Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph. More...

void	DelEdge (const int &SrcNId, const int &DstNId)
	Deletes an edge between node IDs SrcNId and DstNId from the graph. More...

bool	IsEdge (const int &SrcNId, const int &DstNId) const
	Tests whether an edge between node IDs SrcNId and 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	SortNodeAdjV ()
	Sorts the adjacency lists of each node. More...

void	Reserve (const int &Nodes, const int &Edges)
	Reserves memory for a graph of Nodes nodes and Edges edges. More...

void	ReserveNIdDeg (const int &NId, const int &Deg)
	Reserves memory for node ID NId having Deg edges. 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 PUNGraph	New ()
	Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New(). More...

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. More...

static PUNGraph	Load (TSIn &SIn)
	Static constructor that loads the graph from a stream SIn and returns a pointer to it. More...

static PUNGraph	LoadShM (TShMIn &ShMIn)
	Static constructor that loads the graph from shared memory. More...

static PUNGraph	GetSmallGraph ()
	Returns a small graph on 5 nodes and 5 edges. More...

Private Member Functions
TNode &	GetNode (const int &NId)

const TNode &	GetNode (const int &NId) const

void	LoadGraphShM (TShMIn &ShMIn)

Private Attributes
TCRef	CRef

TInt	MxNId

TInt	NEdges

THash< TInt, TNode >	NodeH

Friends
class	TUNGraphMtx

class	TPt< TUNGraph >

Detailed Description

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.

Definition at line 32 of file graph.h.

Member Typedef Documentation

typedef TPt<TUNGraph> TUNGraph::PNet

Definition at line 35 of file graph.h.

typedef TUNGraph TUNGraph::TNet

Definition at line 34 of file graph.h.

Constructor & Destructor Documentation

TUNGraph::TUNGraph ( )

inline

Definition at line 162 of file graph.h.

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

162 : CRef(), MxNId(0), NEdges(0), NodeH() { }

TUNGraph::NEdges

TInt NEdges

Definition: graph.h:144

TUNGraph::CRef

TCRef CRef

Definition: graph.h:143

TUNGraph::MxNId

TInt MxNId

Definition: graph.h:144

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

Here is the caller graph for this function:

TUNGraph::TUNGraph	(	const int &	Nodes,
		const int &	Edges
	)

inlineexplicit

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

Definition at line 164 of file graph.h.

References Reserve().

164 : MxNId(0), NEdges(0) { Reserve(Nodes, Edges); }

TUNGraph::NEdges

TInt NEdges

Definition: graph.h:144

TUNGraph::MxNId

TInt MxNId

Definition: graph.h:144

TUNGraph::Reserve

void Reserve(const int &Nodes, const int &Edges)

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

Definition: graph.h:302

Here is the call graph for this function:

TUNGraph::TUNGraph ( const TUNGraph & Graph )

inline

Definition at line 165 of file graph.h.

165 : MxNId(Graph.MxNId), NEdges(Graph.NEdges), NodeH(Graph.NodeH) { }

TUNGraph::NEdges

TInt NEdges

Definition: graph.h:144

TUNGraph::MxNId

TInt MxNId

Definition: graph.h:144

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

TUNGraph::TUNGraph ( TSIn & SIn )

inline

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

Definition at line 167 of file graph.h.

167 : MxNId(SIn), NEdges(SIn), NodeH(SIn) { }

TUNGraph::NEdges

TInt NEdges

Definition: graph.h:144

TUNGraph::MxNId

TInt MxNId

Definition: graph.h:144

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

Member Function Documentation

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

References TVec< TVal, TSizeTy >::AddSorted(), TStr::Fmt(), GetNode(), IAssertR, IsEdge(), IsNode(), NEdges, and TUNGraph::TNode::NIdV.

Referenced by TUndirFFire::AddNodes(), TSnap::AllGraphsWithNNodes(), TCliqueOverlap::CalculateOverlapMtx(), TSnap::CmtyEvolutionFileBatch(), TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenGeoPrefAttach(), TSnap::GenPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), TSnap::Get1CnCom(), TSnap::Get1CnComSzCnt(), TSnap::GetEgonet(), GetSmallGraph(), TSnap::GetSubGraph(), TTimeNENet::GetTriadEdges(), TSnap::TSnapDetail::InfomapOnlineIncrement(), 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; // no edge id
 }

Here is the call graph for this function:

Here is the caller graph for this function:

int TUNGraph::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 254 of file graph.h.

References AddEdge().

Referenced by AddEdge().

254 { return AddEdge(SrcNId, DstNId); }

TUNGraph::AddEdge

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

Adds an edge between node IDs SrcNId and DstNId to the graph.

Definition: graph.cpp:92

Here is the call graph for this function:

Here is the caller graph for this function:

int TUNGraph::AddEdge ( const TEdgeI & EdgeI )

inline

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

Definition at line 267 of file graph.h.

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

Referenced by AddEdge().

267 { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }

TUNGraph::AddEdge

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

Adds an edge between node IDs SrcNId and DstNId to the graph.

Definition: graph.cpp:92

Here is the call graph for this function:

Here is the caller graph for this function:

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

Adds an edge between node IDs SrcNId and DstNId to the graph. If nodes do not exists, create them.

Definition at line 112 of file graph.cpp.

References AddNode(), TVec< TVal, TSizeTy >::AddSorted(), GetNode(), IsNode(), NEdges, and TUNGraph::TNode::NIdV.

                                                            {
   if (! IsNode(SrcNId)) { AddNode(SrcNId); }
   if (! IsNode(DstNId)) { AddNode(DstNId); }
   if (GetNode(SrcNId).IsNbrNId(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; // no edge id
 }

Here is the call graph for this function:

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

Adds an edge between node IDs SrcNId and 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 103 of file graph.cpp.

References TVec< TVal, TSizeTy >::Add(), GetNode(), NEdges, and TUNGraph::TNode::NIdV.

                                                                    {
   GetNode(SrcNId).NIdV.Add(DstNId);
   if (SrcNId!=DstNId) { // not a self edge
     GetNode(DstNId).NIdV.Add(SrcNId); }
   NEdges++;
   return -1; // no edge id
 }

Here is the call graph for this function:

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 AddEdge2(), TUndirFFire::AddNodes(), TSnap::AllGraphsWithNNodes(), TCliqueOverlap::CalculateOverlapMtx(), TSnap::CmtyEvolutionFileBatch(), TAGM::GenAGM(), TSnap::GenConfModel(), TSnap::GenDegSeq(), TSnap::GenGeoPrefAttach(), TSnap::GenPrefAttach(), TSnap::GenRewire(), TSnap::GenSmallWorld(), TSnap::GetEgonet(), GetSmallGraph(), TSnap::GetSubGraph(), TTimeNENet::GetTriadEdges(), TSnap::TSnapDetail::InfomapOnlineIncrement(), ChibaNishizekiWeighter::Initialize(), 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;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

int TUNGraph::AddNode ( const TNodeI & NodeI )

inline

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

Definition at line 206 of file graph.h.

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

Referenced by AddNode().

206 { return AddNode(NodeI.GetId()); }

TUNGraph::AddNode

int AddNode(int NId=-1)

Adds a node of ID NId to the graph.

Definition: graph.cpp:8

Here is the call graph for this function:

Here is the caller graph for this function:

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

References THash< TKey, TDat, THashFunc >::AddDat(), TVec< TVal, TSizeTy >::AddSorted(), TStr::Fmt(), TUNGraph::TNode::GetDeg(), GetNode(), IAssertR, TUNGraph::TNode::Id, IsNode(), TVec< TVal, TSizeTy >::Len(), 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();
   for (int i = 0; i < NbrNIdV.Len(); i++) {
     GetNode(NbrNIdV[i]).NIdV.AddSorted(NewNId);
   }
   return NewNId;
 }

Here is the call graph for this function:

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 49 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;
 }

Here is the call graph for this function:

int TUNGraph::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 20 of file graph.cpp.

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

                                       {
   if (IsNode(NId)) { return -1;}
   MxNId = TMath::Mx(NId+1, MxNId());
   NodeH.AddDat(NId, TNode(NId));
   return NId;
 }

Here is the call graph for this function:

TEdgeI TUNGraph::BegEI ( ) const

inline

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

Definition at line 278 of file graph.h.

References BegNI(), EndNI(), TUNGraph::TNodeI::GetId(), GetNodes(), TUNGraph::TNodeI::GetOutDeg(), and TUNGraph::TNodeI::GetOutNId().

Referenced by TSnap::BorgattiEverettMeasure(), ProcessedGraph::countClique(), MotifCluster::EdgeMotifAdjacency(), TAGMFast::FindComsByCV(), IsOk(), TSnap::PearsonCorrelation(), and TAGMUtil::SaveGephi().

278 { TNodeI NI = BegNI(); TEdgeI EI(NI, EndNI(), 0); if (GetNodes() != 0 && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { EI++; } return EI; }

TUNGraph::GetNodes

int GetNodes() const

Returns the number of nodes in the graph.

Definition: graph.h:192

TUNGraph::EndNI

TNodeI EndNI() const

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

Definition: graph.h:239

TUNGraph::BegNI

TNodeI BegNI() const

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

Definition: graph.h:237

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TUNGraph::BegNI ( ) const

inline

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

Definition at line 237 of file graph.h.

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

Referenced by ProcessedGraph::assignWeights_dir(), ProcessedGraph::assignWeights_undir(), BegEI(), TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN(), TSnap::CommunityGirvanNewman(), ProcessedGraph::countClique(), ProcessedGraph::countDirTriadMotif(), TLocClust::DrawWhiskers(), TSnap::FastCorePeriphery(), TSnap::FastCorePeripheryGC(), TSnap::GenRewire(), TAGMFit::GetEdgeJointCom(), TSnap::GetEigenVectorCentr(), TSnap::GetGroupDegreeCentr(), TSnap::GetGroupFarnessCentr(), TCliqueOverlap::GetMaximalCliques(), TSnap::Infomap(), TSnap::InfomapOnline(), TSnap::TSnapDetail::TCNMQMatrix::Init(), TAGMFit::InitNodeData(), TSnap::TSnapDetail::MapEquationNew2Modules(), TSnap::MaxCPGreedyBetter(), TSnap::MaxCPGreedyBetter1(), TSnap::MaxCPGreedyBetter2(), TSnap::MaxCPGreedyBetter3(), TTimeNet::PlotEffDiam(), TTimeNet::PlotMedianDegOverTm(), TTimeNet::PlotMissingPast(), ProcessedGraph::printCounts(), ProcessedGraph::printWeights(), TAGMUtil::SaveGephi(), TLocClust::SavePajek(), MotifCluster::SemicliqueMotifAdjacency(), SortNodeAdjV(), and TKronMomentsFit::TKronMomentsFit().

237 { return TNodeI(NodeH.BegI()); }

THash::BegI

TIter BegI() const

Definition: hash.h:213

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

Here is the call graph for this function:

Here is the caller graph for this function:

void TUNGraph::Clr ( )

inline

Deletes all nodes and edges from the graph.

Definition at line 298 of file graph.h.

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

298 { MxNId=0; NEdges=0; NodeH.Clr(); }

TUNGraph::NEdges

TInt NEdges

Definition: graph.h:144

TUNGraph::MxNId

TInt MxNId

Definition: graph.h:144

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

THash::Clr

void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)

Definition: hash.h:361

Here is the call graph for this function:

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 160 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();
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 124 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 ProcessedGraph::assignWeights_dir(), TSnap::TSnapDetail::CmtyGirvanNewmanStep(), TSnap::GenDegSeq(), TSnap::Get1CnCom(), TSnap::Get1CnComSzCnt(), 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); }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 67 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);
 }

Here is the call graph for this function:

void TUNGraph::DelNode ( const TNode & NodeI )

inline

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

Definition at line 233 of file graph.h.

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

Referenced by DelNode().

233 { DelNode(NodeI.GetId()); }

TUNGraph::DelNode

void DelNode(const int &NId)

Deletes node of ID NId from the graph.

Definition: graph.cpp:67

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 207 of file graph.cpp.

References edge, THash< TKey, TDat, THashFunc >::FFirstKeyId(), THash< TKey, TDat, THashFunc >::FNextKeyId(), TUNGraph::TNode::GetDeg(), GetEdges(), TUNGraph::TNode::GetId(), TUNGraph::TNode::GetNbrNId(), GetNodes(), and NodeH.

Referenced by ProcessedGraph::printWeights().

                                     {
   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");
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool TUNGraph::Empty ( ) const

inline

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

Definition at line 296 of file graph.h.

References GetNodes().

296 { return GetNodes()==0; }

TUNGraph::GetNodes

int GetNodes() const

Returns the number of nodes in the graph.

Definition: graph.h:192

Here is the call graph for this function:

TEdgeI TUNGraph::EndEI ( ) const

inline

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

Definition at line 280 of file graph.h.

References EndNI().

Referenced by TSnap::BorgattiEverettMeasure(), ProcessedGraph::countClique(), MotifCluster::EdgeMotifAdjacency(), TAGMFast::FindComsByCV(), IsOk(), TSnap::PearsonCorrelation(), and TAGMUtil::SaveGephi().

280 { return TEdgeI(EndNI(), EndNI()); }

TUNGraph::EndNI

TNodeI EndNI() const

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

Definition: graph.h:239

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TUNGraph::EndNI ( ) const

inline

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

Definition at line 239 of file graph.h.

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

Referenced by ProcessedGraph::assignWeights_dir(), ProcessedGraph::assignWeights_undir(), BegEI(), TSnap::TSnapDetail::TCNMQMatrix::CmtyCMN(), TSnap::CommunityGirvanNewman(), ProcessedGraph::countClique(), ProcessedGraph::countDirTriadMotif(), TLocClust::DrawWhiskers(), EndEI(), TSnap::FastCorePeriphery(), TSnap::FastCorePeripheryGC(), TSnap::GenRewire(), TAGMFit::GetEdgeJointCom(), GetEI(), TSnap::GetEigenVectorCentr(), TSnap::GetGroupDegreeCentr(), TSnap::GetGroupFarnessCentr(), TCliqueOverlap::GetMaximalCliques(), TSnap::Infomap(), TSnap::InfomapOnline(), TSnap::TSnapDetail::TCNMQMatrix::Init(), TAGMFit::InitNodeData(), TSnap::TSnapDetail::MapEquationNew2Modules(), TSnap::MaxCPGreedyBetter(), TSnap::MaxCPGreedyBetter1(), TSnap::MaxCPGreedyBetter2(), TSnap::MaxCPGreedyBetter3(), TTimeNet::PlotEffDiam(), TTimeNet::PlotMedianDegOverTm(), TTimeNet::PlotMissingPast(), ProcessedGraph::printCounts(), ProcessedGraph::printWeights(), TAGMUtil::SaveGephi(), TLocClust::SavePajek(), MotifCluster::SemicliqueMotifAdjacency(), SortNodeAdjV(), and TKronMomentsFit::TKronMomentsFit().

239 { return TNodeI(NodeH.EndI()); }

THash::EndI

TIter EndI() const

Definition: hash.h:218

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

Here is the call graph for this function:

Here is the caller graph for this function:

int TUNGraph::GetEdges ( ) const

Returns the number of edges in the graph.

Definition at line 82 of file graph.cpp.

References NEdges.

Referenced by TLocClustStat::AddCut(), TUndirFFire::AddNodes(), TLocClustStat::AddToBestCutH(), ProcessedGraph::assignWeights_undir(), TSnap::CommunityGirvanNewman(), ProcessedGraph::countClique(), TLocClust::DrawWhiskers(), Dump(), TAGMUtil::FindComsByAGM(), TAGMFast::FindComsByCV(), TAGM::GenAGM(), TSnap::GenRewire(), TAGMFast::GetCmtyVV(), TCesna::GetCmtyVV(), TCesna::GetCmtyVVUnSorted(), TAGMUtil::GetConductance(), TCliqueOverlap::GetCPMCommunities(), TLocClust::GetCutStat(), TAGMFit::GetEdgeJointCom(), TTimeNENet::GetTriadEdges(), TLocClustStat::ImposeNCP(), TSnap::Infomap(), TSnap::TSnapDetail::InfomapOnlineIncrement(), TSnap::TSnapDetail::TCNMQMatrix::Init(), IsOk(), TAGMFit::MLEGradAscentGivenCAG(), TAGMFast::NeighborComInit(), TAGMFit::NeighborComInit(), TLocClustStat::ParamStr(), TLocClustStat::PlotBoltzmanCurve(), TTimeNet::PlotCCfOverTm(), TTimeNet::PlotEffDiam(), TSnap::PlotEigValDistr(), TSnap::PlotEigValRank(), TSnap::PlotInvParticipRat(), TTimeNet::PlotMedianDegOverTm(), TLocClustStat::PlotNCPModul(), TLocClustStat::Run(), TAGMFit::RunMCMC(), TLocClust::SavePajek(), TLocClustStat::SaveTxtInfo(), and TGStat::TakeStat().

                              {
   //int Edges = 0;
   //for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
   //  Edges += NodeH[N].GetDeg();
   //}
   //return Edges/2;
   return NEdges;
 }

Here is the caller graph for this function:

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 143 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);
 }

Here is the call graph for this function:

int TUNGraph::GetMxNId ( ) const

inline

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

Definition at line 243 of file graph.h.

References MxNId.

Referenced by ProcessedGraph::assignWeights_dir(), ProcessedGraph::assignWeights_undir(), ProcessedGraph::countDirTriadMotif(), ChibaNishizekiWeighter::Initialize(), and MotifCluster::MotifAdjacency().

243 { return MxNId; }

TUNGraph::MxNId

TInt MxNId

Definition: graph.h:144

Here is the caller graph for this function:

TNodeI TUNGraph::GetNI ( const int & NId ) const

inline

Returns an iterator referring to the node of ID NId in the graph.

Definition at line 241 of file graph.h.

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

Referenced by TSnap::TSnapDetail::_GirvanNewmanGetModularity(), TLocClust::ApproxPageRank(), TLocClustStat::BagOfWhiskers(), TLocClustStat::BagOfWhiskers2(), TUndirFFire::BurnGeoFire(), MAPPR::computeAPPR(), MAPPR::computeProfile(), TLocClust::DrawWhiskers(), TSnap::FastCorePeripheryGC(), TLocClust::FindBestCut(), TSnap::GenGeoPrefAttach(), TAGMUtil::GetConductance(), TLocClust::GetCutStat(), TSnap::GetDegreeCentr(), TSnap::GetEgonet(), GetEI(), TLocClustStat::TCutInfo::GetFracDegOut(), TSnap::GetGroupDegreeCentr(), TSnap::GetGroupDegreeCentr0(), TAGMUtil::GetNbhCom(), TCliqueOverlap::GetNbrs(), TCliqueOverlap::GetNodeIdWithMaxDeg(), GetRndNI(), TSnap::GetSubGraph(), TAGMFast::GradientForOneVar(), TAGMFast::GradientForRow(), TCesna::GradientForRow(), TAGMFast::HessianForOneVar(), TSnap::Infomap(), TSnap::TSnapDetail::InfomapOnlineIncrement(), TSnap::TSnapDetail::TCNMQMatrix::Init(), ChibaNishizekiWeighter::Initialize(), TAGMFit::JoinCom(), TAGMFit::LeaveCom(), TAGMFast::LikelihoodForOneVar(), TAGMFast::LikelihoodForRow(), TCesna::LikelihoodForRow(), TSnap::TSnapDetail::MapEquationNew2Modules(), TSnap::MaxCPGreedyBetter(), TSnap::MaxCPGreedyBetter1(), TSnap::MaxCPGreedyBetter2(), TSnap::MaxCPGreedyBetter3(), TCliqueOverlap::MaxNbrsInCANDNodeId(), TAGMFast::MLEGradAscent(), TAGMFast::MLEGradAscentParallel(), TCesna::MLEGradAscentParallel(), TAGMFast::MLENewton(), TAGMFast::NeighborComInit(), TAGMFit::NeighborComInit(), TCesna::NeighborComInit(), TAGMFast::RandomInit(), TAGMFit::RandomInit(), TCesna::RandomInit(), TAGMFit::SeekJoin(), TAGMFit::SeekLeave(), TAGMFit::SeekSwitch(), MotifCluster::SemicliqueMotifAdjacency(), and TLocClust::SupportSweep().

241 { return TNodeI(NodeH.GetI(NId)); }

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

THash::GetI

TIter GetI(const TKey &Key) const

Definition: hash.h:220

Here is the call graph for this function:

Here is the caller graph for this function:

void TUNGraph::GetNIdV ( TIntV & NIdV ) const

Gets a vector IDs of all nodes in the graph.

Definition at line 153 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(), TAGMFast::SetGraph(), and TCesna::SetGraph().

                                         {
   NIdV.Gen(GetNodes(), 0);
   for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
     NIdV.Add(NodeH.GetKey(N)); }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

TNode& TUNGraph::GetNode ( const int & NId )

inlineprivate

Definition at line 153 of file graph.h.

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

Referenced by AddEdge(), AddEdge2(), AddEdgeUnchecked(), AddNode(), DelEdge(), DelNode(), IsEdge(), and ReserveNIdDeg().

153 { return NodeH.GetDat(NId); }

THash::GetDat

const TDat & GetDat(const TKey &Key) const

Definition: hash.h:262

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

Here is the call graph for this function:

Here is the caller graph for this function:

const TNode& TUNGraph::GetNode ( const int & NId ) const

inlineprivate

Definition at line 154 of file graph.h.

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

154 { return NodeH.GetDat(NId); }

THash::GetDat

const TDat & GetDat(const TKey &Key) const

Definition: hash.h:262

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

Here is the call graph for this function:

int TUNGraph::GetNodes ( ) const

inline

Returns the number of nodes in the graph.

Definition at line 192 of file graph.h.

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

Referenced by TGStatVec::Add(), TUndirFFire::AddNodes(), TLocClust::ApproxPageRank(), BegEI(), TAGMFit::CalcPNoComByCmtyVV(), TUNGraphMtx::CheckNodeIds(), TSnap::CmtyEvolutionFileBatch(), TLocClust::DrawWhiskers(), Dump(), Empty(), TSnap::FastCorePeripheryGC(), TCesna::FindComs(), TAGMUtil::FindComsByAGM(), TAGMFast::FindComsByCV(), TAGM::GenAGM(), TSnap::GenConfModel(), TCesna::GenHoldOutAttr(), TSnap::GenRewire(), TSnap::GetArtPoints(), TSnap::GetBiCon(), TAGMFast::GetCmtyVV(), TAGMFit::GetCmtyVV(), TCesna::GetCmtyVV(), TCesna::GetCmtyVVUnSorted(), TCliqueOverlap::GetCPMCommunities(), TSnap::GetDegreeCentr(), TSnap::GetEigenVectorCentr(), TSnap::GetEigVec(), TSnap::GetGroupFarnessCentr(), TSnap::GetInvParticipRat(), TCliqueOverlap::GetMaximalCliques(), GetNIdV(), TLocClustStat::ImposeNCP(), ChibaNishizekiWeighter::Initialize(), TAGMFit::InitNodeData(), TSnap::MaxCPGreedyBetter3(), TAGMFast::MLEGradAscent(), TCesna::MLEGradAscent(), TAGMFast::MLEGradAscentParallel(), TCesna::MLEGradAscentParallel(), TAGMFast::MLENewton(), TAGMFast::NeighborComInit(), TAGMFit::NeighborComInit(), TCesna::NeighborComInit(), TLocClustStat::ParamStr(), TSnap::PearsonCorrelation(), TUNGraphMtx::PGetCols(), TUNGraphMtx::PGetRows(), TLocClustStat::PlotBoltzmanCurve(), TTimeNet::PlotCCfOverTm(), TTimeNet::PlotEffDiam(), TSnap::PlotEigValDistr(), TSnap::PlotEigValRank(), TSnap::PlotInvParticipRat(), TTimeNet::PlotMedianDegOverTm(), TLocClustStat::PlotNCP(), TLocClustStat::PlotNCPModul(), TLocClustStat::PlotNCPScatter(), TLocClustStat::PlotNcpTop10(), TLocClustStat::PlotPhiInOut(), TAGMFast::RandomInit(), TCesna::RandomInit(), TAGMFit::RandomInitCmtyVV(), TLocClustStat::Run(), TAGMFit::RunMCMC(), TAGMFit::SampleTransition(), TLocClust::SavePajek(), TLocClustStat::SaveTxtInfo(), TAGMFast::SetCmtyVV(), TCesna::SetCmtyVV(), TAGMFit::SetDefaultPNoCom(), TAGMFast::SetGraph(), TCesna::SetGraph(), TGStat::TakeStat(), TKronMomentsFit::Test(), and TUNGraphMtx::TUNGraphMtx().

192 { return NodeH.Len(); }

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

THash::Len

int Len() const

Definition: hash.h:228

Here is the call graph for this function:

Here is the caller graph for this function:

TNodeI TUNGraph::GetRndNI ( TRnd & Rnd = TInt::Rnd )

inline

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

Definition at line 291 of file graph.h.

References GetNI(), and GetRndNId().

Referenced by TAGMFit::NeighborComInit().

291 { return GetNI(GetRndNId(Rnd)); }

TUNGraph::GetRndNId

int GetRndNId(TRnd &Rnd=TInt::Rnd)

Returns an ID of a random node in the graph.

Definition: graph.h:289

TUNGraph::GetNI

TNodeI GetNI(const int &NId) const

Returns an iterator referring to the node of ID NId in the graph.

Definition: graph.h:241

Here is the call graph for this function:

Here is the caller graph for this function:

int TUNGraph::GetRndNId ( TRnd & Rnd = TInt::Rnd )

inline

Returns an ID of a random node in the graph.

Definition at line 289 of file graph.h.

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

Referenced by GetRndNI(), TLocClustStat::Run(), and TAGMFit::SampleTransition().

289 { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

THash::GetRndKeyId

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

THash::GetKey

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:

PUNGraph TUNGraph::GetSmallGraph ( )

static

Returns a small graph on 5 nodes and 5 edges.

/// Graph:   3--0--4
///            /|
///           1-2
///

Definition at line 221 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;
 }

Here is the call graph for this function:

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

References GetNode(), TUNGraph::TNode::IsNbrNId(), and IsNode().

Referenced by AddEdge(), TAGMFit::CalcPNoComByCmtyVV(), TSnap::GenDegSeq(), TSnap::GetEgonet(), TTimeNENet::GetTriadEdges(), TCluster::Gradient(), TAGMFast::LikelihoodHoldOut(), TCesna::LikelihoodHoldOut(), TCluster::LogLikelihood(), TCluster::MCMC(), and MotifCluster::SemicliqueMotifAdjacency().

                                                                 {
   if (! IsNode(SrcNId) || ! IsNode(DstNId)) return false;
   return GetNode(SrcNId).IsNbrNId(DstNId);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool TUNGraph::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 276 of file graph.h.

276 { return false; }

bool TUNGraph::IsNode ( const int & NId ) const

inline

Tests whether ID NId is a node.

Definition at line 235 of file graph.h.

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

Referenced by AddEdge(), AddEdge2(), AddNode(), AddNodeUnchecked(), TUNGraphMtx::CheckNodeIds(), TSnap::CmtyEvolutionFileBatch(), DelEdge(), DelNode(), TAGM::GenAGM(), TSnap::GenGeoPrefAttach(), TAGMUtil::GetConductance(), TLocClust::GetCutStat(), TSnap::GetEgonet(), TSnap::GetGroupDegreeCentr(), TSnap::GetSubGraph(), TTimeNENet::GetTriadEdges(), TSnap::TSnapDetail::InfomapOnlineIncrement(), ChibaNishizekiWeighter::Initialize(), IsEdge(), IsOk(), TTimeNet::PlotMissingPast(), TAGMFit::SeekLeave(), TAGMFast::SetCmtyVV(), TAGMFit::SetCmtyVV(), TAGMFast::SetGraph(), TCesna::SetGraph(), and TGraphAttributes::TGraphAttributes().

235 { return NodeH.IsKey(NId); }

TUNGraph::NodeH

THash< TInt, TNode > NodeH

Definition: graph.h:145

THash::IsKey

bool IsKey(const TKey &Key) const

Definition: hash.h:258

Here is the call graph for this function:

Here is the caller graph for this function:

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 170 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;
 }

Here is the call graph for this function:

static PUNGraph TUNGraph::Load ( TSIn & SIn )

inlinestatic

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

Definition at line 178 of file graph.h.

References TUNGraph().

Referenced by TAGMFit::Load(), TAGMFast::Load(), and TCesna::Load().

178 { return PUNGraph(new TUNGraph(SIn)); }

TUNGraph::TUNGraph

TUNGraph()

Definition: graph.h:162

PUNGraph

TPt< TUNGraph > PUNGraph

Pointer to an undirected graph (TUNGraph)

Definition: graph.h:5

Here is the call graph for this function:

Here is the caller graph for this function:

void TUNGraph::LoadGraphShM ( TShMIn & ShMIn )

inlineprivate

Definition at line 155 of file graph.h.

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

Referenced by LoadShM().

                                    {
     MxNId = TInt(ShMIn);
     NEdges = TInt(ShMIn);
     TLoadTNodeInitializer Fn;
     NodeH.LoadShM(ShMIn, Fn);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

static PUNGraph TUNGraph::LoadShM ( TShMIn & ShMIn )

inlinestatic

Static constructor that loads the graph from shared 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 182 of file graph.h.

References LoadGraphShM(), and TUNGraph().

                                          {
     TUNGraph* Graph = new TUNGraph();
     Graph->LoadGraphShM(ShMIn);
     return PUNGraph(Graph);
   }  