SNAP Library 3.0, User Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | Friends | List of all members
TNodeNet< TNodeData > Class Template Reference

Node Network (directed graph, TNGraph with data on nodes only). More...

#include <network.h>

Classes

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

Public Types

typedef TNodeData TNodeDat
 
typedef TNodeNet< TNodeData > TNet
 
typedef TPt< TNet > PNet
 

Public Member Functions

 TNodeNet ()
 
 TNodeNet (const int &Nodes, const int &Edges)
 Constructor that reserves enough memory for a network of Nodes nodes and Edges edges. More...
 
 TNodeNet (const TNodeNet &NodeNet)
 
 TNodeNet (TSIn &SIn)
 Constructor that loads the network from a (binary) stream SIn. More...
 
virtual ~TNodeNet ()
 
virtual void Save (TSOut &SOut) const
 Saves the network to a (binary) stream SOut. More...
 
bool HasFlag (const TGraphFlag &Flag) const
 Allows for run-time checking the type of the network (see the TGraphFlag for flags). More...
 
TNodeNet & operator= (const TNodeNet &NodeNet)
 
int GetNodes () const
 Returns the number of nodes in the network. More...
 
int AddNode (int NId=-1)
 Adds a node of ID NId to the network. More...
 
int AddNode (int NId, const TNodeData &NodeDat)
 Adds a node of ID NId and node data NodeDat to the network. More...
 
int AddNode (const TNodeI &NodeI)
 Adds a node NodeI and its node data to the network. More...
 
virtual void DelNode (const int &NId)
 Deletes node of ID NId from the network. More...
 
void DelNode (const TNode &NodeI)
 Deletes node of ID NodeI.GetId() from the network. 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 network. More...
 
TNodeI EndNI () const
 Returns an iterator referring to the past-the-end node in the network. More...
 
TNodeI GetNI (const int &NId) const
 Returns an iterator referring to the node of ID NId in the network. More...
 
const TNode & GetNode (const int &NId) const
 Returns node element for the node of ID NId in the network. More...
 
void SetNDat (const int &NId, const TNodeData &NodeDat)
 Sets node data for the node of ID NId in the network. More...
 
TNodeData & GetNDat (const int &NId)
 Returns node data for the node of ID NId in the network. More...
 
const TNodeData & GetNDat (const int &NId) const
 Returns node data for the node of ID NId in the network. More...
 
int GetMxNId () const
 Returns an ID that is larger than any node ID in the network. More...
 
int GetEdges () const
 Returns the number of edges in the network. More...
 
int AddEdge (const int &SrcNId, const int &DstNId)
 Adds an edge from node IDs SrcNId to node DstNId to the network. More...
 
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the network. More...
 
void DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true)
 Deletes an edge from node IDs SrcNId to DstNId from the network. 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 network. More...
 
TEdgeI BegEI () const
 Returns an iterator referring to the first edge in the network. More...
 
TEdgeI EndEI () const
 Returns an iterator referring to the past-the-end edge in the network. 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 network. More...
 
int GetRndNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random node in the network. More...
 
TNodeI GetRndNI (TRnd &Rnd=TInt::Rnd)
 Returns an interator referring to a random node in the network. More...
 
void GetNIdV (TIntV &NIdV) const
 Gets a vector IDs of all nodes in the network. More...
 
bool Empty () const
 Tests whether the network is empty (has zero nodes). More...
 
void Clr (const bool &DoDel=true, const bool &ResetDat=true)
 Deletes all nodes and edges from the network. More...
 
void Reserve (const int &Nodes, const int &Edges)
 Reserves memory for a network of Nodes nodes and Edges edges. More...
 
void SortNIdById (const bool &Asc=true)
 Sorts nodes by node IDs. More...
 
void SortNIdByDat (const bool &Asc=true)
 Sorts nodes by node data. More...
 
void Defrag (const bool &OnlyNodeLinks=false)
 Defragments the network. More...
 
bool IsOk (const bool &ThrowExcept=true) const
 Checks the network data structure for internal consistency. More...
 

Static Public Member Functions

static PNet New ()
 Static constructor that returns a pointer to the network. Call: TPt <TNodeNet<TNodeData> > Net = TNodeNet<TNodeData>::New(). More...
 
static PNet Load (TSIn &SIn)
 Static constructor that loads the network from a stream SIn and returns a pointer to it. More...
 

Protected Member Functions

TNode & GetNode (const int &NId)
 

Protected Attributes

TCRef CRef
 
TInt MxNId
 
THash< TInt, TNode > NodeH
 

Friends

class TPt< TNodeNet< TNodeData > >
 

Detailed Description

template<class TNodeData>
class TNodeNet< TNodeData >

Node Network (directed graph, TNGraph with data on nodes only).

Definition at line 17 of file network.h.

Member Typedef Documentation

template<class TNodeData>
typedef TPt<TNet> TNodeNet< TNodeData >::PNet

Definition at line 21 of file network.h.

template<class TNodeData>
typedef TNodeNet<TNodeData> TNodeNet< TNodeData >::TNet

Definition at line 20 of file network.h.

template<class TNodeData>
typedef TNodeData TNodeNet< TNodeData >::TNodeDat

Definition at line 19 of file network.h.

Constructor & Destructor Documentation

template<class TNodeData>
TNodeNet< TNodeData >::TNodeNet ( )
inline

Definition at line 141 of file network.h.

141 : CRef(), MxNId(0), NodeH() { }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::CRef
TCRef CRef
Definition: network.h:136
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
template<class TNodeData>
TNodeNet< TNodeData >::TNodeNet ( const int &  Nodes,
const int &  Edges 
)
inlineexplicit

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

Definition at line 143 of file network.h.

143 : MxNId(0) { Reserve(Nodes, Edges); }
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
TNodeNet::Reserve
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a network of Nodes nodes and Edges edges.
Definition: network.h:243
template<class TNodeData>
TNodeNet< TNodeData >::TNodeNet ( const TNodeNet< TNodeData > &  NodeNet)
inline

Definition at line 144 of file network.h.

144 : MxNId(NodeNet.MxNId), NodeH(NodeNet.NodeH) { }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
template<class TNodeData>
TNodeNet< TNodeData >::TNodeNet ( TSIn &  SIn)
inline

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

Definition at line 146 of file network.h.

146 : MxNId(SIn), NodeH(SIn) { }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
template<class TNodeData>
virtual TNodeNet< TNodeData >::~TNodeNet ( )
inlinevirtual

Definition at line 147 of file network.h.

147 { }

Member Function Documentation

template<class TNodeData >
int TNodeNet< TNodeData >::AddEdge ( const int &  SrcNId,
const int &  DstNId 
)

Adds an edge from node IDs SrcNId to node DstNId to the network.

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 TNodeNet have no IDs we return -1. Function aborts if SrcNId or DstNId are not nodes in the network.

Definition at line 334 of file network.h.

334  {
335  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
336  if (IsEdge(SrcNId, DstNId)) { return -2; }
337  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
338  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
339  return -1; // edge id
340 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TNodeNet::GetNode
TNode & GetNode(const int &NId)
Definition: network.h:133
TNodeNet::TNode::InNIdV
TIntV InNIdV
Definition: network.h:27
TVec::AddSorted
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1063
TNodeNet::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:182
TNodeNet::IsEdge
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 network.
Definition: network.h:354
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TNodeNet::TNode::OutNIdV
TIntV OutNIdV
Definition: network.h:27
template<class TNodeData>
int TNodeNet< TNodeData >::AddEdge ( const TEdgeI &  EdgeI)
inline

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

Definition at line 212 of file network.h.

212 { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
TNodeNet::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the network.
Definition: network.h:334
template<class TNodeData >
int TNodeNet< TNodeData >::AddNode ( int  NId = -1)

Adds a node of ID NId to the network.

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 276 of file network.h.

276  {
277  if (NId == -1) {
278  NId = MxNId; MxNId++;
279  } else {
280  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
281  MxNId = TMath::Mx(NId+1, MxNId());
282  }
283  NodeH.AddDat(NId, TNode(NId));
284  return NId;
285 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:182
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
template<class TNodeData>
int TNodeNet< TNodeData >::AddNode ( int  NId,
const TNodeData &  NodeDat 
)

Adds a node of ID NId and node data NodeDat to the network.

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 288 of file network.h.

288  {
289  if (NId == -1) {
290  NId = MxNId; MxNId++;
291  } else {
292  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
293  MxNId = TMath::Mx(NId+1, MxNId());
294  }
295  NodeH.AddDat(NId, TNode(NId, NodeDat));
296  return NId;
297 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:182
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
template<class TNodeData>
int TNodeNet< TNodeData >::AddNode ( const TNodeI &  NodeI)
inline

Adds a node NodeI and its node data to the network.

Definition at line 174 of file network.h.

174 { return AddNode(NodeI.GetId(), NodeI.GetDat()); }
TNodeNet::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:276
template<class TNodeData>
TEdgeI TNodeNet< TNodeData >::BegEI ( ) const
inline

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

Definition at line 222 of file network.h.

222 { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0) NI++; return TEdgeI(NI, EndNI()); }
TNodeNet::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:186
TNodeNet::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:184
TNodeNet::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:74
template<class TNodeData>
TNodeI TNodeNet< TNodeData >::BegNI ( ) const
inline

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

Definition at line 184 of file network.h.

184 { return TNodeI(NodeH.BegI(), this); }
THash::BegI
TIter BegI() const
Definition: hash.h:171
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
template<class TNodeData>
void TNodeNet< TNodeData >::Clr ( const bool &  DoDel = true,
const bool &  ResetDat = true 
)
inline

Deletes all nodes and edges from the network.

Definition at line 240 of file network.h.

240  {
241  MxNId = 0; NodeH.Clr(DoDel, -1, ResetDat); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:319
template<class TNodeData >
void TNodeNet< TNodeData >::Defrag ( const bool &  OnlyNodeLinks = false)

Defragments the network.

After performing many node and edge insertions and deletions to a network, the network data structure will be fragmented in memory. This function compacts down the network data structure and frees unneeded memory.

Definition at line 376 of file network.h.

376  {
377  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
378  TNode& Node = NodeH[n];
379  Node.InNIdV.Pack(); Node.OutNIdV.Pack();
380  }
381  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
382  NodeH.Defrag(); }
383 }
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::Defrag
void Defrag()
Definition: hash.h:513
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
THash::Pack
void Pack()
Definition: hash.h:247
template<class TNodeData >
void TNodeNet< TNodeData >::DelEdge ( const int &  SrcNId,
const int &  DstNId,
const bool &  IsDir = true 
)

Deletes an edge from node IDs SrcNId to DstNId from the network.

If the edge (SrcNId, DstNId) does not exist in the network function still completes. But the function aborts if SrcNId or DstNId are not nodes in the network.

Definition at line 343 of file network.h.

343  {
344  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
345  GetNode(SrcNId).OutNIdV.DelIfIn(DstNId);
346  GetNode(DstNId).InNIdV.DelIfIn(SrcNId);
347  if (! IsDir) {
348  GetNode(DstNId).OutNIdV.DelIfIn(SrcNId);
349  GetNode(SrcNId).InNIdV.DelIfIn(DstNId);
350  }
351 }
TVec::DelIfIn
bool DelIfIn(const TVal &Val)
Removes the first occurrence of element Val.
Definition: ds.h:1151
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TNodeNet::GetNode
TNode & GetNode(const int &NId)
Definition: network.h:133
TNodeNet::TNode::InNIdV
TIntV InNIdV
Definition: network.h:27
TNodeNet::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:182
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TNodeNet::TNode::OutNIdV
TIntV OutNIdV
Definition: network.h:27
template<class TNodeData >
void TNodeNet< TNodeData >::DelNode ( const int &  NId)
virtual

Deletes node of ID NId from the network.

If the node of ID NId does not exist the function aborts.

Definition at line 300 of file network.h.

300  {
301  { TNode& Node = GetNode(NId);
302  for (int e = 0; e < Node.GetOutDeg(); e++) {
303  const int nbr = Node.GetOutNId(e);
304  if (nbr == NId) { continue; }
305  TNode& N = GetNode(nbr);
306  int n = N.InNIdV.SearchBin(NId);
307  if (n!= -1) { N.InNIdV.Del(n); }
308  }
309  for (int e = 0; e < Node.GetInDeg(); e++) {
310  const int nbr = Node.GetInNId(e);
311  if (nbr == NId) { continue; }
312  TNode& N = GetNode(nbr);
313  int n = N.OutNIdV.SearchBin(NId);
314  if (n!= -1) { N.OutNIdV.Del(n); }
315  } }
316  NodeH.DelKey(NId);
317 }
TNodeNet::GetNode
TNode & GetNode(const int &NId)
Definition: network.h:133
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:362
template<class TNodeData>
void TNodeNet< TNodeData >::DelNode ( const TNode &  NodeI)
inline

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

Definition at line 180 of file network.h.

180 { DelNode(NodeI.GetId()); }
TNodeNet::DelNode
virtual void DelNode(const int &NId)
Deletes node of ID NId from the network.
Definition: network.h:300
template<class TNodeData>
bool TNodeNet< TNodeData >::Empty ( ) const
inline

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

Definition at line 238 of file network.h.

238 { return GetNodes()==0; }
TNodeNet::GetNodes
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:160
template<class TNodeData>
TEdgeI TNodeNet< TNodeData >::EndEI ( ) const
inline

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

Definition at line 224 of file network.h.

224 { return TEdgeI(EndNI(), EndNI()); }
TNodeNet::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:186
template<class TNodeData>
TNodeI TNodeNet< TNodeData >::EndNI ( ) const
inline

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

Definition at line 186 of file network.h.

186 { return TNodeI(NodeH.EndI(), this); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::EndI
TIter EndI() const
Definition: hash.h:176
template<class TNodeData >
int TNodeNet< TNodeData >::GetEdges ( ) const

Returns the number of edges in the network.

Definition at line 326 of file network.h.

326  {
327  int edges=0;
328  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N);) {
329  edges+=NodeH[N].GetOutDeg(); }
330  return edges;
331 }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
template<class TNodeData>
TEdgeI TNodeNet< TNodeData >::GetEI ( const int &  EId) const

Not supported/implemented!

template<class TNodeData >
TNodeNet< TNodeData >::TEdgeI TNodeNet< TNodeData >::GetEI ( const int &  SrcNId,
const int &  DstNId 
) const

Returns an iterator referring to edge (SrcNId, DstNId) in the network.

Definition at line 368 of file network.h.

368  {
369  const TNodeI SrcNI = GetNI(SrcNId);
370  const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
371  if (NodeN == -1) { return EndEI(); }
372  return TEdgeI(SrcNI, EndNI(), NodeN);
373 }
TNodeNet::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:186
TNodeNet::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:188
TNodeNet::EndEI
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the network.
Definition: network.h:224
template<class TNodeData>
int TNodeNet< TNodeData >::GetMxNId ( ) const
inline

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

Definition at line 198 of file network.h.

198 { return MxNId; }
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
template<class TNodeData>
TNodeData& TNodeNet< TNodeData >::GetNDat ( const int &  NId)
inline

Returns node data for the node of ID NId in the network.

Definition at line 194 of file network.h.

194 { return NodeH.GetDat(NId).NodeDat; }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TNodeNet::TNode::NodeDat
TNodeData NodeDat
Definition: network.h:26
template<class TNodeData>
const TNodeData& TNodeNet< TNodeData >::GetNDat ( const int &  NId) const
inline

Returns node data for the node of ID NId in the network.

Definition at line 196 of file network.h.

196 { return NodeH.GetDat(NId).NodeDat; }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TNodeNet::TNode::NodeDat
TNodeData NodeDat
Definition: network.h:26
template<class TNodeData>
TNodeI TNodeNet< TNodeData >::GetNI ( const int &  NId) const
inline

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

Definition at line 188 of file network.h.

188 { return TNodeI(NodeH.GetI(NId), this); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::GetI
TIter GetI(const TKey &Key) const
Definition: hash.h:178
template<class TNodeData >
void TNodeNet< TNodeData >::GetNIdV ( TIntV &  NIdV) const

Gets a vector IDs of all nodes in the network.

Definition at line 361 of file network.h.

361  {
362  NIdV.Reserve(GetNodes(), 0);
363  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
364  NIdV.Add(NodeH.GetKey(N)); }
365 }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::GetNodes
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:160
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TVec::Reserve
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:515
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
template<class TNodeData>
TNode& TNodeNet< TNodeData >::GetNode ( const int &  NId)
inlineprotected

Definition at line 133 of file network.h.

133 { return NodeH.GetDat(NId); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
template<class TNodeData>
const TNode& TNodeNet< TNodeData >::GetNode ( const int &  NId) const
inline

Returns node element for the node of ID NId in the network.

Definition at line 190 of file network.h.

190 { return NodeH.GetDat(NId); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
template<class TNodeData>
int TNodeNet< TNodeData >::GetNodes ( ) const
inline

Returns the number of nodes in the network.

Definition at line 160 of file network.h.

160 { return NodeH.Len(); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::Len
int Len() const
Definition: hash.h:186
template<class TNodeData>
TNodeI TNodeNet< TNodeData >::GetRndNI ( TRnd &  Rnd = TInt::Rnd)
inline

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

Definition at line 233 of file network.h.

233 { return GetNI(GetRndNId(Rnd)); }
TNodeNet::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:188
TNodeNet::GetRndNId
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the network.
Definition: network.h:231
template<class TNodeData>
int TNodeNet< TNodeData >::GetRndNId ( TRnd &  Rnd = TInt::Rnd)
inline

Returns an ID of a random node in the network.

Definition at line 231 of file network.h.

231 { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
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:402
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
template<class TNodeData >
bool TNodeNet< TNodeData >::HasFlag ( const TGraphFlag &  Flag) const

Allows for run-time checking the type of the network (see the TGraphFlag for flags).

Definition at line 271 of file network.h.

271  {
272  return HasGraphFlag(typename TNet, Flag);
273 }
HasGraphFlag
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
TNodeNet::TNet
TNodeNet< TNodeData > TNet
Definition: network.h:20
template<class TNodeData >
bool TNodeNet< TNodeData >::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 network.

Definition at line 354 of file network.h.

354  {
355  if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
356  if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
357  else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
358 }
TNodeNet::TNode::IsOutNId
bool IsOutNId(const int &NId) const
Definition: network.h:45
TNodeNet::GetNode
TNode & GetNode(const int &NId)
Definition: network.h:133
TNodeNet::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:182
template<class TNodeData>
bool TNodeNet< TNodeData >::IsNode ( const int &  NId) const
inline

Tests whether ID NId is a node.

Definition at line 182 of file network.h.

182 { return NodeH.IsKey(NId); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
template<class TNodeData >
bool TNodeNet< TNodeData >::IsOk ( const bool &  ThrowExcept = true) const

Checks the network data structure for internal consistency.

For each node in the network check that its neighbors are also nodes in the network.

Definition at line 386 of file network.h.

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

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

Definition at line 153 of file network.h.

153 { return PNet(new TNodeNet(SIn)); }
TNodeNet::TNodeNet
TNodeNet()
Definition: network.h:141
TNodeNet::PNet
TPt< TNet > PNet
Definition: network.h:21
template<class TNodeData>
static PNet TNodeNet< TNodeData >::New ( )
inlinestatic

Static constructor that returns a pointer to the network. Call: TPt <TNodeNet<TNodeData> > Net = TNodeNet<TNodeData>::New().

Definition at line 151 of file network.h.

151 { return PNet(new TNodeNet()); }
TNodeNet::TNodeNet
TNodeNet()
Definition: network.h:141
TNodeNet::PNet
TPt< TNet > PNet
Definition: network.h:21
template<class TNodeData>
TNodeNet& TNodeNet< TNodeData >::operator= ( const TNodeNet< TNodeData > &  NodeNet)
inline

Definition at line 156 of file network.h.

156  {
157  if (this!=&NodeNet) { NodeH=NodeNet.NodeH; MxNId=NodeNet.MxNId; } return *this; }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
template<class TNodeData>
void TNodeNet< TNodeData >::Reserve ( const int &  Nodes,
const int &  Edges 
)
inline

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

Definition at line 243 of file network.h.

243 { if (Nodes>0) { NodeH.Gen(Nodes/2); } }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:180
template<class TNodeData>
virtual void TNodeNet< TNodeData >::Save ( TSOut &  SOut) const
inlinevirtual

Saves the network to a (binary) stream SOut.

Reimplemented in TTimeNet.

Definition at line 149 of file network.h.

149 { MxNId.Save(SOut); NodeH.Save(SOut); }
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1060
THash::Save
void Save(TSOut &SOut) const
Definition: hash.h:141
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
TNodeNet::MxNId
TInt MxNId
Definition: network.h:137
template<class TNodeData>
void TNodeNet< TNodeData >::SetNDat ( const int &  NId,
const TNodeData &  NodeDat 
)

Sets node data for the node of ID NId in the network.

Definition at line 320 of file network.h.

320  {
321  IAssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist.", NId).CStr());
322  NodeH.GetDat(NId).NodeDat = NodeDat;
323 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TNodeNet::TNode::NodeDat
TNodeData NodeDat
Definition: network.h:26
TNodeNet::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:182
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
template<class TNodeData>
void TNodeNet< TNodeData >::SortNIdByDat ( const bool &  Asc = true)
inline

Sorts nodes by node data.

Definition at line 247 of file network.h.

247 { NodeH.SortByDat(Asc); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::SortByDat
void SortByDat(const bool &Asc=true)
Definition: hash.h:250
template<class TNodeData>
void TNodeNet< TNodeData >::SortNIdById ( const bool &  Asc = true)
inline

Sorts nodes by node IDs.

Definition at line 245 of file network.h.

245 { NodeH.SortByKey(Asc); }
TNodeNet::NodeH
THash< TInt, TNode > NodeH
Definition: network.h:138
THash::SortByKey
void SortByKey(const bool &Asc=true)
Definition: hash.h:249

Friends And Related Function Documentation

template<class TNodeData>
friend class TPt< TNodeNet< TNodeData > >
friend

Definition at line 261 of file network.h.

Member Data Documentation

template<class TNodeData>
TCRef TNodeNet< TNodeData >::CRef
protected

Definition at line 136 of file network.h.

template<class TNodeData>
TInt TNodeNet< TNodeData >::MxNId
protected

Definition at line 137 of file network.h.

template<class TNodeData>
THash<TInt, TNode> TNodeNet< TNodeData >::NodeH
protected

Definition at line 138 of file network.h.

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