SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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
TBigNet< TNodeData, IsDir > Class Template Reference

Big Network. More...

#include <bignet.h>

Collaboration diagram for TBigNet< TNodeData, IsDir >:

Classes

class  TEdgeI
 Edge iterator. More...
 
class  TNode
 Node container class. More...
 
class  TNodeI
 Node iterator. More...
 

Public Types

enum  { DelNId = INT_MAX }
 
typedef TNodeData TNodeDat
 
typedef TBigNet< TNodeData, IsDir > TNet
 
typedef TPt< TNetPNet
 
typedef THash< TInt, TNodeTNodeH
 
typedef TPt< TBigNet
< TNodeData, IsDir > > 
PBigNet
 
typedef TVecPool< TIntTVPool
 
typedef TPt< TVPoolPVPool
 

Public Member Functions

 TBigNet (const int &Nodes, const TSize &Edges, const bool &Sources=false)
 
 TBigNet (TSIn &SIn)
 
virtual ~TBigNet ()
 
virtual void Save (TSOut &SOut) const
 
TBigNetoperator= (const TBigNet &Net)
 
bool OnlySources () const
 
bool HasFlag (const TGraphFlag &Flag) const
 
void DumpFlags () const
 
int GetNodes () const
 
int GetMxNId () const
 Returns an id that is larger than any node id in the network. More...
 
int AddNode (int NId, const int &InDeg, const int &OutDeg)
 
int AddNode (int NId, const int &InDeg, const int &OutDeg, const TNodeDat &NodeDat)
 
int AddNode (int NId, const TIntV &InNIdV, const TIntV &OutNIdV)
 
int AddNode (int NId, const TIntV &InNIdV, const TIntV &OutNIdV, const TNodeDat &NodeDat)
 
int AddUndirNode (int NId, const int &Deg)
 
int AddUndirNode (int NId, const int &Deg, const TNodeDat &NodeDat)
 
int AddUndirNode (int NId, const TIntV &EdgeNIdV)
 
int AddUndirNode (int NId, const TIntV &EdgeNIdV, const TNodeDat &NodeDat)
 
void SetInNIdV (int NId, const TIntV &InNIdV)
 
void SetOutNIdV (int NId, const TIntV &OutNIdV)
 
void GetInNIdV (int NId, TIntV &OutNIdV) const
 
void GetOutNIdV (int NId, TIntV &OutNIdV) const
 
bool IsNode (const int &NId) const
 
TNodeI BegNI () const
 
TNodeI EndNI () const
 
TNodeI GetNI (const int &NId) const
 
TNodeDatGetNDat (const int &NId)
 
const TNodeDatGetNDat (const int &NId) const
 
TEdgeI BegEI () const
 
TEdgeI EndEI () const
 
TEdgeI GetEI (const int &EId) const
 
int IsolateNode (int NId)
 
int DelNode (int NId)
 
bool IsIsoNode (const int &NId) const
 
uint GetDelEdges ()
 
void CompactEdgePool ()
 
::TSize GetEdges () const
 
int AddEdge (const int &SrcNId, const int &DstNId)
 
bool IsEdge (const int &SrcNId, const int &DstNId, const bool &Dir=true) const
 
void SortEdgeV ()
 
void InvertFromSources (uint ExpectNodes=0)
 
void Rewire (TRnd &Rnd=TInt::Rnd)
 
PNGraph GetNGraph (const bool &RenumberNodes=false) const
 
PNGraph GetSubNGraph (const TIntV &NIdV) const
 
PBigNet GetSubGraph (const TIntV &NIdV, const bool &RenumberNodes=false) const
 
void GetSubGraph (const TIntV &NIdV, TBigNet *NewNet, const bool &RenumberNodes=false) const
 
int GetRndNId (TRnd &Rnd=TInt::Rnd) const
 
TNodeI GetRndNI (TRnd &Rnd=TInt::Rnd) const
 
void GetNIdV (TIntV &NIdV) const
 
bool Empty () const
 
void Clr (const bool &DoDel=true)
 
void Reserve (const int &Nodes, const TSize &Edges)
 
void Defrag (const bool &OnlyNodeLinks=false)
 
bool IsOk () const
 
void Dump (const TStr &Desc=TStr()) const
 
void SaveForDisk (const TStr &OutFNm) const
 

Static Public Member Functions

static PBigNet New (const int &Nodes, const TSize &Edges, const bool &Sources=false)
 
static PBigNet Load (TSIn &SIn)
 
static void LoadNodeDatH (const TStr &InFNm, TNodeH &NodeH)
 
static void SaveToDisk (const TStr &InFNm, const TStr &OutFNm, const bool &SaveSparseHash)
 

Protected Member Functions

bool IsNode (const int &NId, TNode &Node) const
 
int * GetInNIdVPt (const int &NId) const
 
int * GetOutNIdVPt (const int &NId) const
 
const TNodeGetNode (const int &NId) const
 
TNodeGetNode (const int &NId)
 

Static Protected Member Functions

static void AddSorted (int *Beg, int *End, const int &Val)
 
static const int * BinSearch (const int *Beg, const int *End, const int &Val)
 
static const int * BinSearch2 (const int *Beg, const int *End, const int &Val)
 

Protected Attributes

TCRef CRef
 
TInt MxNId
 
TB32Set Flags
 
TVPool Pool
 
TNodeH NodeH
 

Friends

class TPt< TBigNet >
 

Detailed Description

template<class TNodeData, bool IsDir>
class TBigNet< TNodeData, IsDir >

Big Network.

This class implements similar interface to TNGraph and TUNGraph. The class is meant for storing particularly large static directed or undirected networks. The network representation is optimized for low memory footprint. This means that when a particular node is added to the network its (maximum) in- and out-degree need to be specified, so that the class allocates enough memory for that number of edges being adjacent to a node. The class nicely supports adding as well as deleting nodes, although the memory does not get freed. Deleting edges is supported, while adding edges is supported only up to the point until the node reaches its prespecified in- or out-degree.

Definition at line 11 of file bignet.h.

Member Typedef Documentation

template<class TNodeData, bool IsDir>
typedef TPt<TBigNet<TNodeData, IsDir> > TBigNet< TNodeData, IsDir >::PBigNet

Definition at line 19 of file bignet.h.

template<class TNodeData, bool IsDir>
typedef TPt<TNet> TBigNet< TNodeData, IsDir >::PNet

Definition at line 15 of file bignet.h.

template<class TNodeData, bool IsDir>
typedef TPt<TVPool> TBigNet< TNodeData, IsDir >::PVPool

Definition at line 21 of file bignet.h.

template<class TNodeData, bool IsDir>
typedef TBigNet<TNodeData, IsDir> TBigNet< TNodeData, IsDir >::TNet

Definition at line 14 of file bignet.h.

template<class TNodeData, bool IsDir>
typedef TNodeData TBigNet< TNodeData, IsDir >::TNodeDat

Definition at line 13 of file bignet.h.

template<class TNodeData, bool IsDir>
typedef THash<TInt, TNode> TBigNet< TNodeData, IsDir >::TNodeH

Definition at line 17 of file bignet.h.

template<class TNodeData, bool IsDir>
typedef TVecPool<TInt> TBigNet< TNodeData, IsDir >::TVPool

Definition at line 20 of file bignet.h.

Member Enumeration Documentation

template<class TNodeData, bool IsDir>
anonymous enum
Enumerator
DelNId 

Definition at line 127 of file bignet.h.

127 { DelNId = INT_MAX }; // id of a deleted node

Constructor & Destructor Documentation

template<class TNodeData , bool IsDir>
TBigNet< TNodeData, IsDir >::TBigNet ( const int &  Nodes,
const TSize Edges,
const bool &  Sources = false 
)

Definition at line 288 of file bignet.h.

References TBigNet< TNodeData, IsDir >::Flags, gfSources, IAssertR, and TB32Set::Incl().

Referenced by TBigNet< TNodeData, IsDir >::Load(), and TBigNet< TNodeData, IsDir >::New().

288  :
289 CRef(), MxNId(0), Flags(), Pool(IsDir ? 2*Edges:Edges, 10000000, true, TInt::Mx), NodeH(Nodes) {
290  //Flags.Incl(gfNodeGraph);
291  //Flags.Incl(gfNetwork);
292  //if (IsDir) { Flags.Incl(gfDirected); }
293  if (Sources) {
295  IAssertR(! IsDir, "Jure: not clear what happens is graph is Undirected and has only sources.");
296  }
297  //DumpFlags();
298 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const int Mx
Definition: dt.h:1139
TCRef CRef
Definition: bignet.h:129
void Incl(const int &BitN)
Definition: bits.h:262
TB32Set Flags
Definition: bignet.h:131
TNodeH NodeH
Definition: bignet.h:133
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData, bool IsDir>
TBigNet< TNodeData, IsDir >::TBigNet ( TSIn SIn)
inline

Definition at line 136 of file bignet.h.

References IAssert.

136 : MxNId(SIn), Flags(SIn), Pool(SIn), NodeH(SIn) { TBool Dir(SIn); IAssert(Dir()==IsDir); }
#define IAssert(Cond)
Definition: bd.h:262
TB32Set Flags
Definition: bignet.h:131
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
Definition: dt.h:971
TVPool Pool
Definition: bignet.h:132
template<class TNodeData, bool IsDir>
virtual TBigNet< TNodeData, IsDir >::~TBigNet ( )
inlinevirtual

Definition at line 137 of file bignet.h.

137 { }

Member Function Documentation

template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddEdge ( const int &  SrcNId,
const int &  DstNId 
)

Definition at line 537 of file bignet.h.

References Assert, IAssert, TBigNet< TNodeData, IsDir >::TNode::InVId, and TBigNet< TNodeData, IsDir >::TNode::OutVId.

537  {
538  TNode Src; IAssert(IsNode(SrcNId, Src));
539  int* OutV = (int *)Pool.GetValVPt(Src.OutVId);
540  const int OutVLen = Pool.GetVLen(Src.OutVId);
541  Assert(BinSearch(OutV, OutV+OutVLen, DstNId)==NULL); // no edge yet
542  AddSorted(OutV, OutV+OutVLen, DstNId);
543  if (! OnlySources()) {
544  TNode Dst; IAssert(IsNode(DstNId, Dst));
545  int* InV = (int *)Pool.GetValVPt(Dst.InVId);
546  const int InVLen = Pool.GetVLen(Dst.InVId);
547  AddSorted(InV, InV+InVLen, SrcNId);
548  }
549  return -1; // edge id
550 }
#define IAssert(Cond)
Definition: bd.h:262
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1730
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1728
#define Assert(Cond)
Definition: bd.h:251
bool OnlySources() const
Definition: bignet.h:145
static const int * BinSearch(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:264
static void AddSorted(int *Beg, int *End, const int &Val)
Definition: bignet.h:248
TVPool Pool
Definition: bignet.h:132
template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddNode ( int  NId,
const int &  InDeg,
const int &  OutDeg 
)

Definition at line 320 of file bignet.h.

References CAssert, TStr::Fmt(), IAssertR, TBigNet< TNodeData, IsDir >::TNode::InVId, TBigNet< TNodeData, IsDir >::TNode::IsUnused(), TMath::Mx(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

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

320  {
321  CAssert(IsDir);
322  if (NId == -1) { NId = MxNId; MxNId.Val++; }
323  else { MxNId = TMath::Mx(NId+1, MxNId()); }
324  TNode& Node = NodeH.AddDat(NId);
325  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
326  Node.InVId = Pool.AddEmptyV(InDeg);
327  Node.OutVId = Pool.AddEmptyV(OutDeg);
328  return NId;
329 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1880
#define CAssert(Cond)
Definition: bd.h:302
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
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:

template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddNode ( int  NId,
const int &  InDeg,
const int &  OutDeg,
const TNodeDat NodeDat 
)

Definition at line 332 of file bignet.h.

References CAssert, TBigNet< TNodeData, IsDir >::TNode::Dat, TStr::Fmt(), IAssertR, TBigNet< TNodeData, IsDir >::TNode::InVId, TBigNet< TNodeData, IsDir >::TNode::IsUnused(), TMath::Mx(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

332  {
333  CAssert(IsDir);
334  if (NId == -1) { NId = MxNId; MxNId.Val++; }
335  else { MxNId = TMath::Mx(NId+1, MxNId()); }
336  TNode& Node = NodeH.AddDat(NId);
337  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
338  Node.InVId = Pool.AddEmptyV(InDeg);
339  Node.OutVId = Pool.AddEmptyV(OutDeg);
340  Node.Dat = NodeDat;
341  return NId;
342 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1880
#define CAssert(Cond)
Definition: bd.h:302
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddNode ( int  NId,
const TIntV InNIdV,
const TIntV OutNIdV 
)

Definition at line 370 of file bignet.h.

References CAssert, TStr::Fmt(), IAssert, IAssertR, TBigNet< TNodeData, IsDir >::TNode::InVId, TVec< TVal, TSizeTy >::IsSorted(), TBigNet< TNodeData, IsDir >::TNode::IsUnused(), TMath::Mx(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

370  {
371  CAssert(IsDir);
372  IAssert(InNIdV.IsSorted() && OutNIdV.IsSorted());
373  if (NId == -1) { NId = MxNId; MxNId.Val++; }
374  else { MxNId = TMath::Mx(NId+1, MxNId()); }
375  TNode& Node = NodeH.AddDat(NId);
376  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
377  Node.InVId = Pool.AddV(InNIdV);
378  Node.OutVId = Pool.AddV(OutNIdV);
379  return NId;
380 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1869
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
#define CAssert(Cond)
Definition: bd.h:302
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1323
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddNode ( int  NId,
const TIntV InNIdV,
const TIntV OutNIdV,
const TNodeDat NodeDat 
)

Definition at line 383 of file bignet.h.

References CAssert, TBigNet< TNodeData, IsDir >::TNode::Dat, TStr::Fmt(), IAssert, IAssertR, TBigNet< TNodeData, IsDir >::TNode::InVId, TVec< TVal, TSizeTy >::IsSorted(), TBigNet< TNodeData, IsDir >::TNode::IsUnused(), TMath::Mx(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

383  {
384  CAssert(IsDir);
385  IAssert(InNIdV.IsSorted() && OutNIdV.IsSorted());
386  if (NId == -1) { NId = MxNId; MxNId.Val++; }
387  else { MxNId = TMath::Mx(NId+1, MxNId()); }
388  TNode& Node = NodeH.AddDat(NId);
389  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
390  Node.InVId = Pool.AddV(InNIdV);
391  Node.OutVId = Pool.AddV(OutNIdV);
392  Node.Dat = NodeDat;
393  return NId;
394 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1869
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
#define CAssert(Cond)
Definition: bd.h:302
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1323
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::AddSorted ( int *  Beg,
int *  End,
const int &  Val 
)
staticprotected

Definition at line 248 of file bignet.h.

References IAssertR, and TInt::Mx.

248  {
249  // there is at least one free slot available for the Val
250  IAssertR(*(End-1)==TInt::Mx, "Edge can not be added: no free space");
251  // find position to insert
252  int Half, Len = int(End-Beg);
253  while (Len > 0) {
254  Half = Len/2;
255  int* Mid=Beg+Half;
256  if (*Mid < Val) { Beg=Mid+1; Len=Len-Half-1; } else { Len=Half; } }
257  IAssertR(*Beg != Val, "Value already existis");
258  // insert
259  memmove(Beg+1, Beg, sizeof(int)*(End-Beg-1));
260  *Beg = Val;
261 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const int Mx
Definition: dt.h:1139
template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddUndirNode ( int  NId,
const int &  Deg 
)

Definition at line 345 of file bignet.h.

References CAssert, TStr::Fmt(), IAssertR, TBigNet< TNodeData, IsDir >::TNode::InVId, TBigNet< TNodeData, IsDir >::TNode::IsUnused(), TMath::Mx(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

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

345  {
346  CAssert(! IsDir);
347  if (NId == -1) { NId = MxNId; MxNId.Val++; }
348  else { MxNId = TMath::Mx(NId+1, MxNId()); }
349  TNode& Node = NodeH.AddDat(NId);
350  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
351  Node.InVId = Pool.AddEmptyV(Deg);
352  Node.OutVId = Node.InVId; // same vector
353  return NId;
354 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1880
#define CAssert(Cond)
Definition: bd.h:302
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
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:

template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddUndirNode ( int  NId,
const int &  Deg,
const TNodeDat NodeDat 
)

Definition at line 357 of file bignet.h.

References CAssert, TBigNet< TNodeData, IsDir >::TNode::Dat, TStr::Fmt(), IAssertR, TBigNet< TNodeData, IsDir >::TNode::InVId, TBigNet< TNodeData, IsDir >::TNode::IsUnused(), TMath::Mx(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

357  {
358  CAssert(! IsDir);
359  if (NId == -1) { NId = MxNId; MxNId.Val++; }
360  else { MxNId = TMath::Mx(NId+1, MxNId()); }
361  TNode& Node = NodeH.AddDat(NId);
362  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
363  Node.InVId = Pool.AddEmptyV(Deg);
364  Node.OutVId = Node.InVId; // same vector
365  Node.Dat = NodeDat;
366  return NId;
367 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1880
#define CAssert(Cond)
Definition: bd.h:302
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddUndirNode ( int  NId,
const TIntV EdgeNIdV 
)

Definition at line 397 of file bignet.h.

References CAssert, TStr::Fmt(), IAssert, IAssertR, TBigNet< TNodeData, IsDir >::TNode::InVId, TVec< TVal, TSizeTy >::IsSorted(), TBigNet< TNodeData, IsDir >::TNode::IsUnused(), TMath::Mx(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

397  {
398  CAssert(! IsDir);
399  IAssert(EdgeNIdV.IsSorted());
400  if (NId == -1) { NId = MxNId; MxNId.Val++; }
401  else { MxNId = TMath::Mx(NId+1, MxNId()); }
402  TNode& Node = NodeH.AddDat(NId);
403  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
404  Node.InVId = Pool.AddV(EdgeNIdV);
405  Node.OutVId = Node.InVId;
406  return NId;
407 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1869
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
#define CAssert(Cond)
Definition: bd.h:302
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1323
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddUndirNode ( int  NId,
const TIntV EdgeNIdV,
const TNodeDat NodeDat 
)

Definition at line 410 of file bignet.h.

References CAssert, TBigNet< TNodeData, IsDir >::TNode::Dat, TStr::Fmt(), IAssert, IAssertR, TBigNet< TNodeData, IsDir >::TNode::InVId, TVec< TVal, TSizeTy >::IsSorted(), TBigNet< TNodeData, IsDir >::TNode::IsUnused(), TMath::Mx(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

410  {
411  CAssert(! IsDir);
412  IAssert(EdgeNIdV.IsSorted());
413  if (NId == -1) { NId = MxNId; MxNId.Val++; }
414  else { MxNId = TMath::Mx(NId+1, MxNId()); }
415  TNode& Node = NodeH.AddDat(NId);
416  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
417  Node.InVId = Pool.AddV(EdgeNIdV);
418  Node.OutVId = Node.InVId;
419  Node.Dat = NodeDat;
420  return NId;
421 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1869
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1136
#define CAssert(Cond)
Definition: bd.h:302
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1323
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
TEdgeI TBigNet< TNodeData, IsDir >::BegEI ( ) const
inline

Definition at line 173 of file bignet.h.

References TBigNet< TNodeData, IsDir >::BegNI(), TBigNet< TNodeData, IsDir >::EndNI(), and TBigNet< TNodeData, IsDir >::TNodeI::GetOutDeg().

173 { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0) NI++; return TEdgeI(NI, EndNI()); }
int GetOutDeg() const
Definition: bignet.h:72
TNodeI EndNI() const
Definition: bignet.h:168
TNodeI BegNI() const
Definition: bignet.h:167

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
TNodeI TBigNet< TNodeData, IsDir >::BegNI ( ) const
inline

Definition at line 167 of file bignet.h.

References THash< TKey, TDat, THashFunc >::BegI(), TBigNet< TNodeData, IsDir >::NodeH, and TBigNet< TNodeData, IsDir >::Pool.

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

167 { return TNodeI(NodeH.BegI(), (TVPool *)&Pool); }
TIter BegI() const
Definition: hash.h:213
TVecPool< TInt > TVPool
Definition: bignet.h:20
TNodeH NodeH
Definition: bignet.h:133
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData , bool IsDir>
const int * TBigNet< TNodeData, IsDir >::BinSearch ( const int *  Beg,
const int *  End,
const int &  Val 
)
staticprotected

Definition at line 264 of file bignet.h.

Referenced by TBigNet< TNodeData, IsDir >::TNodeI::IsInNId(), and TBigNet< TNodeData, IsDir >::TNodeI::IsOutNId().

264  {
265  End--; const int *Mid;
266  while (Beg <= End) { Mid = Beg+(End-Beg)/2;
267  if (*Mid == Val) { return Mid; }
268  else if (Val < *Mid) { End=Mid-1; } else { Beg=Mid+1; }
269  }
270  return NULL;
271 }

Here is the caller graph for this function:

template<class TNodeData , bool IsDir>
const int * TBigNet< TNodeData, IsDir >::BinSearch2 ( const int *  Beg,
const int *  End,
const int &  Val 
)
staticprotected

Definition at line 274 of file bignet.h.

274  {
275  const int* First = Beg;
276  const int* Last = End;
277  const int* Mid;
278  TSize len = End-Beg, half;
279  while (len > 0) {
280  half = len>>1; Mid=First+half;
281  if (*Mid < Val) { First = Mid; First++; len=len-half-1; }
282  else { len=half; }
283  }
284  return First==Last ? Last-1 : First;
285 }
size_t TSize
Definition: bd.h:58
template<class TNodeData, bool IsDir>
void TBigNet< TNodeData, IsDir >::Clr ( const bool &  DoDel = true)
inline

Definition at line 204 of file bignet.h.

References THash< TKey, TDat, THashFunc >::Clr(), TVecPool< TVal, TSizeTy >::Clr(), TBigNet< TNodeData, IsDir >::MxNId, TBigNet< TNodeData, IsDir >::NodeH, and TBigNet< TNodeData, IsDir >::Pool.

204 { MxNId = 0; NodeH.Clr(DoDel); Pool.Clr(DoDel); }
void Clr(bool DoDel=true)
Clears the contents of the pool.
Definition: ds.h:1759
TNodeH NodeH
Definition: bignet.h:133
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::CompactEdgePool ( )

Definition at line 532 of file bignet.h.

532  {
534 }
void CompactPool(const TVal &DelVal)
Deletes all elements of value DelVal from all vectors.
Definition: ds.h:1889
TVPool Pool
Definition: bignet.h:132
template<class TNodeData, bool IsDir>
void TBigNet< TNodeData, IsDir >::Defrag ( const bool &  OnlyNodeLinks = false)
inline

Definition at line 206 of file bignet.h.

206 { }
template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::DelNode ( int  NId)

Definition at line 501 of file bignet.h.

501  {
502  const int DelEdges = IsolateNode(NId);
503  NodeH.DelKey(NId);
504  return DelEdges;
505 }
int IsolateNode(int NId)
Definition: bignet.h:454
void DelKey(const TKey &Key)
Definition: hash.h:404
TNodeH NodeH
Definition: bignet.h:133
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::Dump ( const TStr Desc = TStr()) const

Definition at line 1037 of file bignet.h.

References TStr::CStr(), and TStr::Empty().

1037  {
1038  if (! Desc.Empty()) { printf("\n%s (%d, %u):\n", Desc.CStr(), GetNodes(), GetEdges()); }
1039  else { printf("\nNodes: %d, Edges: %u\n", GetNodes(), GetEdges()); }
1040  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
1041  printf("%d]\n IN %d]", NI.GetId(), NI.GetInDeg());
1042  for (int i=0; i<NI.GetInDeg(); i++) { printf(" %d", NI.GetInNId(i)); }
1043  if (IsDir) {
1044  printf("\n OUT %d]", NI.GetOutDeg());
1045  for (int i=0; i<NI.GetOutDeg(); i++) { printf(" %d", NI.GetOutNId(i)); }
1046  }
1047  printf("\n");
1048  }
1049 }
TNodeI EndNI() const
Definition: bignet.h:168
int GetNodes() const
Definition: bignet.h:151
::TSize GetEdges() const
Definition: bignet.h:185
TNodeI BegNI() const
Definition: bignet.h:167
bool Empty() const
Definition: dt.h:488
char * CStr()
Definition: dt.h:476

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::DumpFlags ( ) const

Definition at line 310 of file bignet.h.

References TSnap::GetFlagStr(), and gfMx.

310  {
311  for (int i = 1; i <int(gfMx); i++) {
312  if (HasFlag(TGraphFlag(i))) { printf(" +"); }
313  else { printf(" -"); }
314  printf("%s", TSnap::GetFlagStr(TGraphFlag(i)).CStr());
315  }
316  printf("\n");
317 }
TStr GetFlagStr(const TGraphFlag &GraphFlag)
Returns a string representation of a flag.
Definition: gbase.cpp:5
sentinel, last value for iteration
Definition: gbase.h:19
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
bool HasFlag(const TGraphFlag &Flag) const
Definition: bignet.h:146

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::Empty ( ) const
inline

Definition at line 203 of file bignet.h.

References TBigNet< TNodeData, IsDir >::GetNodes().

203 { return GetNodes()==0; }
int GetNodes() const
Definition: bignet.h:151

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
TEdgeI TBigNet< TNodeData, IsDir >::EndEI ( ) const
inline

Definition at line 174 of file bignet.h.

References TBigNet< TNodeData, IsDir >::EndNI().

174 { return TEdgeI(EndNI(), EndNI()); }
TNodeI EndNI() const
Definition: bignet.h:168

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
TNodeI TBigNet< TNodeData, IsDir >::EndNI ( ) const
inline

Definition at line 168 of file bignet.h.

References THash< TKey, TDat, THashFunc >::EndI(), TBigNet< TNodeData, IsDir >::NodeH, and TBigNet< TNodeData, IsDir >::Pool.

Referenced by TBigNet< TNodeData, IsDir >::BegEI(), and TBigNet< TNodeData, IsDir >::EndEI().

168 { return TNodeI(NodeH.EndI(), (TVPool *)&Pool); }
TIter EndI() const
Definition: hash.h:218
TVecPool< TInt > TVPool
Definition: bignet.h:20
TNodeH NodeH
Definition: bignet.h:133
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData , bool IsDir>
uint TBigNet< TNodeData, IsDir >::GetDelEdges ( )

Definition at line 518 of file bignet.h.

References TVec< TVal, TSizeTy >::Len().

518  {
519  uint DelEdges = 0;
520  TIntV OutV;
521  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
522  const int NId = NI.GetId();
523  GetOutNIdV(NId, OutV);
524  for (int i = 0; i < OutV.Len(); i++) {
525  if (OutV[i] == DelNId) { DelEdges++; }
526  }
527  }
528  return DelEdges;
529 }
unsigned int uint
Definition: bd.h:11
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNodeI EndNI() const
Definition: bignet.h:168
TNodeI BegNI() const
Definition: bignet.h:167
void GetOutNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:446

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
::TSize TBigNet< TNodeData, IsDir >::GetEdges ( ) const
inline

Definition at line 185 of file bignet.h.

References TVecPool< TVal, TSizeTy >::GetVals(), and TBigNet< TNodeData, IsDir >::Pool.

185 { return Pool.GetVals(); }
TSize GetVals() const
Returns the total number of values stored in the vector pool.
Definition: ds.h:1706
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
TEdgeI TBigNet< TNodeData, IsDir >::GetEI ( const int &  EId) const
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::GetInNIdV ( int  NId,
TIntV OutNIdV 
) const

Definition at line 440 of file bignet.h.

References EAssertR, TStr::Fmt(), and TBigNet< TNodeData, IsDir >::TNode::InVId.

440  {
441  TNode Node; EAssertR(IsNode(NId, Node), TStr::Fmt("Not node: NId=%d\n", NId).CStr());
442  Pool.GetV(Node.InVId, InNIdV);
443 }
void GetV(const int &VId, TValV &ValV) const
Returns ValV which is a reference (not a copy) to vector with id VId.
Definition: ds.h:1736
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
int* TBigNet< TNodeData, IsDir >::GetInNIdVPt ( const int &  NId) const
inlineprotected

Definition at line 119 of file bignet.h.

References TBigNet< TNodeData, IsDir >::GetNode(), TVecPool< TVal, TSizeTy >::GetValVPt(), and TBigNet< TNodeData, IsDir >::Pool.

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

119 { return (int *) Pool.GetValVPt(GetNode(NId).InVId); }
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1730
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData, bool IsDir>
int TBigNet< TNodeData, IsDir >::GetMxNId ( ) const
inline

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

Definition at line 153 of file bignet.h.

References TBigNet< TNodeData, IsDir >::MxNId.

153 { return MxNId; }
TInt MxNId
Definition: bignet.h:130
template<class TNodeData, bool IsDir>
TNodeDat& TBigNet< TNodeData, IsDir >::GetNDat ( const int &  NId)
inline

Definition at line 170 of file bignet.h.

References TBigNet< TNodeData, IsDir >::TNode::Dat, THash< TKey, TDat, THashFunc >::GetDat(), and TBigNet< TNodeData, IsDir >::NodeH.

170 { return NodeH.GetDat(NId).Dat; }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TNodeDat Dat
Data associated with the node.
Definition: bignet.h:35
TNodeH NodeH
Definition: bignet.h:133

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
const TNodeDat& TBigNet< TNodeData, IsDir >::GetNDat ( const int &  NId) const
inline

Definition at line 171 of file bignet.h.

References TBigNet< TNodeData, IsDir >::TNode::Dat, THash< TKey, TDat, THashFunc >::GetDat(), and TBigNet< TNodeData, IsDir >::NodeH.

171 { return NodeH.GetDat(NId).Dat; }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TNodeDat Dat
Data associated with the node.
Definition: bignet.h:35
TNodeH NodeH
Definition: bignet.h:133

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
PNGraph TBigNet< TNodeData, IsDir >::GetNGraph ( const bool &  RenumberNodes = false) const

Definition at line 766 of file bignet.h.

References TNGraph::AddNode(), IAssert, TNGraph::New(), and TNGraph::Reserve().

766  {
767  IAssert(RenumberNodes == false);
768  PNGraph Graph = TNGraph::New();
769  Graph->Reserve(GetNodes(), 0);
770  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
771  Graph->AddNode(NI.GetId(), Pool, NI.GetInVId(), NI.GetOutVId());
772  }
773  return Graph;
774 }
#define IAssert(Cond)
Definition: bd.h:262
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TNodeI EndNI() const
Definition: bignet.h:168
int GetNodes() const
Definition: bignet.h:151
TNodeI BegNI() const
Definition: bignet.h:167
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:606
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
TNodeI TBigNet< TNodeData, IsDir >::GetNI ( const int &  NId) const
inline

Definition at line 169 of file bignet.h.

References THash< TKey, TDat, THashFunc >::GetI(), TBigNet< TNodeData, IsDir >::NodeH, and TBigNet< TNodeData, IsDir >::Pool.

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

169 { return TNodeI(NodeH.GetI(NId), (TVPool *)&Pool); }
TVecPool< TInt > TVPool
Definition: bignet.h:20
TNodeH NodeH
Definition: bignet.h:133
TVPool Pool
Definition: bignet.h:132
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:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::GetNIdV ( TIntV NIdV) const

Definition at line 569 of file bignet.h.

References TVec< TVal, TSizeTy >::Add(), THashKeyDatI< TKey, TDat >::EndI, and TVec< TVal, TSizeTy >::Reserve().

569  {
570  NIdV.Reserve(GetNodes(), 0);
571  for (typename TNodeH::TIter I = NodeH.BegI(); I < NodeH.EndI(); I++) {
572  NIdV.Add(I->Key); }
573 }
TIter BegI() const
Definition: hash.h:213
TIter EndI() const
Definition: hash.h:218
int GetNodes() const
Definition: bignet.h:151
THashKeyDatI< TInt, TNode > TIter
Definition: hash.h:102
TNodeH NodeH
Definition: bignet.h:133
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
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:

template<class TNodeData, bool IsDir>
const TNode& TBigNet< TNodeData, IsDir >::GetNode ( const int &  NId) const
inlineprotected

Definition at line 124 of file bignet.h.

References THash< TKey, TDat, THashFunc >::GetDat(), and TBigNet< TNodeData, IsDir >::NodeH.

Referenced by TBigNet< TNodeData, IsDir >::GetInNIdVPt(), and TBigNet< TNodeData, IsDir >::GetOutNIdVPt().

124 { return NodeH.GetDat(NId); }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TNodeH NodeH
Definition: bignet.h:133

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData, bool IsDir>
TNode& TBigNet< TNodeData, IsDir >::GetNode ( const int &  NId)
inlineprotected

Definition at line 125 of file bignet.h.

References THash< TKey, TDat, THashFunc >::GetDat(), and TBigNet< TNodeData, IsDir >::NodeH.

125 { return NodeH.GetDat(NId); }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TNodeH NodeH
Definition: bignet.h:133

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
int TBigNet< TNodeData, IsDir >::GetNodes ( ) const
inline

Definition at line 151 of file bignet.h.

References THash< TKey, TDat, THashFunc >::Len(), and TBigNet< TNodeData, IsDir >::NodeH.

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

151 { return NodeH.Len(); }
TNodeH NodeH
Definition: bignet.h:133
int Len() const
Definition: hash.h:228

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::GetOutNIdV ( int  NId,
TIntV OutNIdV 
) const

Definition at line 446 of file bignet.h.

References EAssert, and TBigNet< TNodeData, IsDir >::TNode::OutVId.

446  {
447  TNode Node; EAssert(IsNode(NId, Node));
448  Pool.GetV(Node.OutVId, OutNIdV);
449 }
void GetV(const int &VId, TValV &ValV) const
Returns ValV which is a reference (not a copy) to vector with id VId.
Definition: ds.h:1736
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
#define EAssert(Cond)
Definition: bd.h:280
TVPool Pool
Definition: bignet.h:132
template<class TNodeData, bool IsDir>
int* TBigNet< TNodeData, IsDir >::GetOutNIdVPt ( const int &  NId) const
inlineprotected

Definition at line 120 of file bignet.h.

References TBigNet< TNodeData, IsDir >::GetNode(), TVecPool< TVal, TSizeTy >::GetValVPt(), and TBigNet< TNodeData, IsDir >::Pool.

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

120 { return (int *) Pool.GetValVPt(GetNode(NId).OutVId); }
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1730
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData, bool IsDir>
TNodeI TBigNet< TNodeData, IsDir >::GetRndNI ( TRnd Rnd = TInt::Rnd) const
inline

Definition at line 200 of file bignet.h.

References TBigNet< TNodeData, IsDir >::GetNI(), and TBigNet< TNodeData, IsDir >::GetRndNId().

200 { return GetNI(GetRndNId(Rnd)); }
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
int GetRndNId(TRnd &Rnd=TInt::Rnd) const
Definition: bignet.h:199

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
int TBigNet< TNodeData, IsDir >::GetRndNId ( TRnd Rnd = TInt::Rnd) const
inline

Definition at line 199 of file bignet.h.

References THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::GetRndKeyId(), and TBigNet< TNodeData, IsDir >::NodeH.

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

199 { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd)); }
TNodeH NodeH
Definition: bignet.h:133
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:

template<class TNodeData , bool IsDir>
TPt< TBigNet< TNodeData, IsDir > > TBigNet< TNodeData, IsDir >::GetSubGraph ( const TIntV NIdV,
const bool &  RenumberNodes = false 
) const

Definition at line 806 of file bignet.h.

References TSparseHash< TKey, TDat, GroupSize >::AddDat(), EAssert, TBigNet< TNodeData, IsDir >::TNodeI::GetInDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetInNId(), TBigNet< TNodeData, IsDir >::TNodeI::GetInVId(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutNId(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutVId(), gfDirected, gfSources, TVec< TVal, TSizeTy >::Len(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

806  {
807  const bool isDir = IsDir, onlySources = HasFlag(gfSources);
808  TSize Edges=0;
809  // find in- and out-degree
810  TSparseHash<TInt, TIntPr> NIdDegH(NIdV.Len());
811  for (int i = 0; i < NIdV.Len(); i++) { NIdDegH.AddDat(NIdV[i]); }
812  for (int i = 0; i < NIdV.Len(); i++) {
813  const TNodeI NI = GetNI(NIdV[i]);
814  int InDeg=0, OutDeg=0;
815  for (int n = 0; n < NI.GetOutDeg(); n++) {
816  if (NIdDegH.IsKey(NI.GetOutNId(n))) OutDeg++; }
817  if (! onlySources && isDir) {
818  for (int n = 0; n < NI.GetInDeg(); n++) {
819  if (NIdDegH.IsKey(NI.GetInNId(n))) InDeg++; }
820  }
821  Edges += OutDeg;
822  NIdDegH.GetDat(NIdV[i]) = TIntPr(InDeg, OutDeg);
823  }
824  // make network
825  typedef TBigNet<TNodeData, IsDir> TBNet;
826  TPt<TBNet> NewNetPt = TBNet::New(NIdV.Len(), Edges, HasFlag(gfDirected));
827  TBNet& NewNet = *NewNetPt;
828  NewNet.Flags = Flags;
829  // add nodes
830  if (isDir || onlySources) {
831  for (int i = 0; i < NIdV.Len(); i++) {
832  const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
833  NewNet.AddNode(NIdV[i], Deg.Val1, Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
834  } else {
835  for (int i = 0; i < NIdV.Len(); i++) {
836  const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
837  NewNet.AddUndirNode(NIdV[i], Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
838  }
839  // add edges
840  for (int i = 0; i < NIdV.Len(); i++) {
841  int NId = NIdV[i];
842  const TNodeI NI = GetNI(NId);
843  int *NIdVPt = (int *) NewNet.GetOutNIdVPt(NId);
844  int deg = 0;
845  for (int e = 0; e < NI.GetOutDeg(); e++) {
846  const int Dst = NI.GetOutNId(e);
847  if (NewNet.IsNode(Dst)) {
848  *NIdVPt = Dst; NIdVPt++; deg++; }
849  }
850  EAssert(deg == NIdDegH.GetDat(NId).Val2);
851  if (isDir && ! onlySources) {
852  EAssert((NI.GetInVId()==NI.GetOutVId() && NI.GetInVId()==0)
853  || (NI.GetInVId() != NI.GetOutVId()));
854  int * NIdVPt = (int *) NewNet.GetInNIdVPt(NId);
855  int deg = 0;
856  for (int e = 0; e < NI.GetInDeg(); e++) {
857  const int Dst = NI.GetInNId(e);
858  if (NewNet.IsNode(Dst)) {
859  *NIdVPt = Dst; NIdVPt++; deg++; }
860  }
861  EAssert(deg == NIdDegH.GetDat(NId).Val1);
862  }
863  }
864  return NewNetPt;
865 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TNodeDat & GetNDat(const int &NId)
Definition: bignet.h:170
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
size_t TSize
Definition: bd.h:58
Big Network.
Definition: bignet.h:11
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
#define EAssert(Cond)
Definition: bd.h:280
TB32Set Flags
Definition: bignet.h:131
Definition: ds.h:32
TDat & AddDat(const TKey &Key)
Definition: shash.h:687
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
Definition: bd.h:196
bool HasFlag(const TGraphFlag &Flag) const
Definition: bignet.h:146

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::GetSubGraph ( const TIntV NIdV,
TBigNet< TNodeData, IsDir > *  NewNet,
const bool &  RenumberNodes = false 
) const

Definition at line 868 of file bignet.h.

References THash< TKey, TDat, THashFunc >::AddDat(), THashSet< TKey, THashFunc >::AddKey(), TBigNet< TNodeData, IsDir >::AddNode(), TBigNet< TNodeData, IsDir >::AddUndirNode(), EAssert, TBigNet< TNodeData, IsDir >::Flags, THashSet< TKey, THashFunc >::Gen(), TBigNet< TNodeData, IsDir >::TNodeI::GetInDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetInNId(), TBigNet< TNodeData, IsDir >::GetInNIdVPt(), TBigNet< TNodeData, IsDir >::TNodeI::GetInVId(), THashSet< TKey, THashFunc >::GetKeyId(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutNId(), TBigNet< TNodeData, IsDir >::GetOutNIdVPt(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutVId(), gfSources, TBigNet< TNodeData, IsDir >::IsNode(), TVec< TVal, TSizeTy >::Len(), TBigNet< TNodeData, IsDir >::Reserve(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

868  {
869  printf("Set subgraph on %d nodes\n", NIdV.Len()); TExeTm ExeTm;
870  const bool isDir = IsDir, onlySources = HasFlag(gfSources);
871  TSize Edges=0;
872  // find in- and out-degree
873  THash<TInt, TIntPr> NIdDegH(NIdV.Len());
874  for (int i = 0; i < NIdV.Len(); i++) { NIdDegH.AddDat(NIdV[i]); }
875  for (int i = 0; i < NIdV.Len(); i++) {
876  const TNodeI NI = GetNI(NIdV[i]);
877  int InDeg=0, OutDeg=0;
878  for (int n = 0; n < NI.GetOutDeg(); n++) {
879  if (NIdDegH.IsKey(NI.GetOutNId(n))) OutDeg++; }
880  if (! onlySources && isDir) {
881  for (int n = 0; n < NI.GetInDeg(); n++) {
882  if (NIdDegH.IsKey(NI.GetInNId(n))) InDeg++; }
883  }
884  Edges += OutDeg;
885  NIdDegH.GetDat(NIdV[i]) = TIntPr(InDeg, OutDeg);
886  }
887  // make network
888  //typedef TBigNet<TNodeData, IsDir> TBNet;
889  //TPt<TBNet> NewNetPt = TBNet::New(NIdV.Len(), Edges, HasFlag(gfDirected));
890  NewNetPt->Reserve(NIdV.Len(), Edges);
891  TBigNet<TNodeData, IsDir>& NewNet = *NewNetPt;
892  NewNet.Flags = Flags;
893  TIntSet NIdMap;
894  // add nodes
895  if (! RenumberNodes) {
896  if (isDir || onlySources) {
897  for (int i = 0; i < NIdV.Len(); i++) {
898  const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
899  NewNet.AddNode(NIdV[i], Deg.Val1, Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
900  } else {
901  for (int i = 0; i < NIdV.Len(); i++) {
902  const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
903  NewNet.AddUndirNode(NIdV[i], Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
904  }
905  } else { // renumber nodes
906  NIdMap.Gen(NIdV.Len());
907  for (int i = 0; i < NIdV.Len(); i++) { NIdMap.AddKey(NIdV[i]); }
908  if (isDir || onlySources) {
909  for (int i = 0; i < NIdV.Len(); i++) {
910  const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
911  NewNet.AddNode(NIdMap.GetKeyId(NIdV[i]), Deg.Val1, Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
912  } else {
913  for (int i = 0; i < NIdV.Len(); i++) {
914  const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
915  NewNet.AddUndirNode(NIdMap.GetKeyId(NIdV[i]), Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
916  }
917  }
918  // add edges
919  for (int i = 0; i < NIdV.Len(); i++) {
920  int NId = NIdV[i];
921  const TNodeI NI = GetNI(NId);
922  int *NIdVPt = (int *) NewNet.GetOutNIdVPt(RenumberNodes?NIdMap.GetKeyId(NId):NId);
923  int deg = 0;
924  for (int e = 0; e < NI.GetOutDeg(); e++) {
925  const int Dst = RenumberNodes?NIdMap.GetKeyId(NI.GetOutNId(e)):NI.GetOutNId(e);
926  if (NewNet.IsNode(Dst)) {
927  *NIdVPt = Dst; NIdVPt++; deg++; }
928  }
929  EAssert(deg == NIdDegH.GetDat(NId).Val2);
930  if (isDir && ! onlySources) {
931  EAssert((NI.GetInVId()==NI.GetOutVId() && NI.GetInVId()==0)
932  || (NI.GetInVId() != NI.GetOutVId()));
933  int * NIdVPt = (int *) NewNet.GetInNIdVPt(RenumberNodes?NIdMap.GetKeyId(NId):NId);
934  int deg = 0;
935  for (int e = 0; e < NI.GetInDeg(); e++) {
936  const int Dst = RenumberNodes?NIdMap.GetKeyId(NI.GetInNId(e)):NI.GetInNId(e);
937  if (NewNet.IsNode(Dst)) {
938  *NIdVPt = Dst; NIdVPt++; deg++; }
939  }
940  EAssert(deg == NIdDegH.GetDat(NId).Val1);
941  }
942  }
943  printf(" %u edges [%s]\n", uint(Edges), ExeTm.GetStr());
944 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
int AddUndirNode(int NId, const int &Deg)
Definition: bignet.h:345
TNodeDat & GetNDat(const int &NId)
Definition: bignet.h:170
Definition: tm.h:355
unsigned int uint
Definition: bd.h:11
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Gen(const int &ExpectVals)
Definition: shash.h:1115
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
int * GetOutNIdVPt(const int &NId) const
Definition: bignet.h:120
size_t TSize
Definition: bd.h:58
Big Network.
Definition: bignet.h:11
int AddKey(const TKey &Key)
Definition: shash.h:1254
#define EAssert(Cond)
Definition: bd.h:280
TB32Set Flags
Definition: bignet.h:131
Definition: ds.h:32
int AddNode(int NId, const int &InDeg, const int &OutDeg)
Definition: bignet.h:320
int * GetInNIdVPt(const int &NId) const
Definition: bignet.h:119
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
bool HasFlag(const TGraphFlag &Flag) const
Definition: bignet.h:146

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
PNGraph TBigNet< TNodeData, IsDir >::GetSubNGraph ( const TIntV NIdV) const

Definition at line 777 of file bignet.h.

References TNGraph::AddEdge(), TNGraph::AddNode(), TBigNet< TNodeData, IsDir >::TNodeI::GetInDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetInNId(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutNId(), TNGraph::IsNode(), TVec< TVal, TSizeTy >::Len(), TNGraph::New(), TNGraph::ReserveNIdInDeg(), and TNGraph::ReserveNIdOutDeg().

777  {
778  PNGraph Graph = TNGraph::New(NIdV.Len(), 0);
779  // add nodes
780  for (int i = 0; i < NIdV.Len(); i++) {
781  Graph->AddNode(NIdV[i]); }
782  // reserve node in- and out-degree
783  for (int i = 0; i < NIdV.Len(); i++) {
784  const int SrcNId = NIdV[i];
785  const TNodeI NI = GetNI(SrcNId);
786  int InDeg=0, OutDeg=0;
787  for (int e = 0; e < NI.GetInDeg(); e++) { if (Graph->IsNode(NI.GetInNId(e))) InDeg++; }
788  for (int e = 0; e < NI.GetOutDeg(); e++) { if (Graph->IsNode(NI.GetOutNId(e))) OutDeg++; }
789  Graph->ReserveNIdInDeg(SrcNId, InDeg);
790  Graph->ReserveNIdOutDeg(SrcNId, OutDeg);
791  }
792  // add edges
793  for (int i = 0; i < NIdV.Len(); i++) {
794  const int SrcNId = NIdV[i];
795  const TNodeI NI = GetNI(SrcNId);
796  for (int e = 0; e < NI.GetOutDeg(); e++) {
797  const int DstNId = NI.GetOutNId(e);
798  if (Graph->IsNode(DstNId)) {
799  Graph->AddEdge(SrcNId, DstNId); }
800  }
801  }
802  return Graph;
803 }
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
void ReserveNIdInDeg(const int &NId, const int &InDeg)
Reserves memory for node ID NId having InDeg in-edges.
Definition: graph.h:608
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:542
void ReserveNIdOutDeg(const int &NId, const int &OutDeg)
Reserves memory for node ID NId having OutDeg out-edges.
Definition: graph.h:610

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::HasFlag ( const TGraphFlag Flag) const
inline

Definition at line 146 of file bignet.h.

References gfSources, HasGraphFlag, and TBigNet< TNodeData, IsDir >::OnlySources().

146  {
147  return HasGraphFlag(typename TBigNet, Flag) || (Flag==gfSources && OnlySources()); }
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
Big Network.
Definition: bignet.h:11
bool OnlySources() const
Definition: bignet.h:145
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::InvertFromSources ( uint  ExpectNodes = 0)

Definition at line 604 of file bignet.h.

References THash< TKey, TDat, THashFunc >::AddDat(), CAssert, TStr::CStr(), THash< TKey, TDat, THashFunc >::GetDat(), TInt::GetMegaStr(), TExeTm::GetSecs(), TVec< TVal, TSizeTy >::GetV(), gfSources, IAssert, TBigNet< TNodeData, IsDir >::TNode::InVId, TStr::Len(), TInt::Mx, and TVec< TVal, TSizeTy >::Sort().

604  {
605  typedef THash<TInt, TInt> TDegHash;
606  typedef int* TIntPt;
607  if (ExpectNodes == 0) ExpectNodes=4*GetNodes();
608  printf("\nInverting BigNet: reserved for %s nodes\n", TInt::GetMegaStr(ExpectNodes).CStr());
609  CAssert(IsDir);
610  IAssert(OnlySources());
611  TDegHash InDegH(ExpectNodes);
612  TSize NDest=0;
613  // get node in-degree
614  uint c=0; TExeTm ExeTm;
615  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, c++) {
616  for (int e = 0; e < NI.GetOutDeg(); e++) {
617  InDegH.AddDat(NI.GetOutNId(e)) += 1; }
618  if (c%100000==0) printf("\r%s h:%d [%g] ", TInt::GetMegaStr(c).CStr(), InDegH.Len(), ExeTm.GetSecs());
619  }
620  printf("\n Resizing NodePool: %lld -> %lld\n", uint64(Pool.Reserved()), uint64(GetEdges()));
621  if (2*GetEdges() > Pool.Reserved()) {
622  Pool.Reserve(2*GetEdges()); }
623  // add nodes
624  printf("NodeH: %s nodes, InDeg: %s nodes, Reserve: %s\n", TInt::GetMegaStr(NodeH.Len()).CStr(),
625  TInt::GetMegaStr(InDegH.Len()).CStr(), TInt::GetMegaStr(ExpectNodes).CStr());
626  NodeH.Reserve(ExpectNodes);
627  for (TDegHash::TIter I = InDegH.BegI(); I < InDegH.EndI(); I++) {
628  const int NId = I->Key, InDeg = I->Dat;
629  if (! IsNode(NId)) {
630  AddNode(NId, InDeg, 0); NDest++; } // new destination node, no out-links
631  else {
632  TNode& Node = GetNode(NId);
633  IAssert(Node.InVId == 0); // no in-links
634  Node.InVId = Pool.AddEmptyV(InDeg); }
635  }
636  InDegH.Clr(true);
637  printf("Added: %lld destination nodes\n", uint64(NDest));
638  printf("Graph nodes: %lld nodes\n", uint64(GetNodes()));
639  // pointer to in-links vector
640  THash<TInt, int*> NIdToPtH(GetNodes());
641  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, c++)
642  NIdToPtH.AddDat(NI.GetId(), (int *)Pool.GetValVPt(NI.GetInVId()));
643  // add in-edges
644  printf("Adding edges...\n");
645  c = 0;
646  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, c++) {
647  const int SrcNId = NI.GetId();
648  for (int e = 0; e < NI.GetOutDeg(); e++) {
649  TIntPt& InV = NIdToPtH.GetDat(NI.GetOutNId(e));
650  IAssert(*InV == TInt::Mx);
651  *InV = SrcNId; InV++;
652  }
653  if (c%100000==0) printf("\r%s [%g] ", TInt::GetMegaStr(c).CStr(), ExeTm.GetSecs());
654  }
655  // sort in-links
656  printf("\nSorting in-links...\n");
657  TIntV InNIdV; c = 0;
658  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, c++) {
659  Pool.GetV(NI.GetInVId(), InNIdV);
660  InNIdV.Sort();
661  if (c%100000==0) printf("\r%s [%g] ", TInt::GetMegaStr(c).CStr(), ExeTm.GetSecs());
662  }
663  printf("\r...done [%g]\n", ExeTm.GetSecs());
665 }
#define IAssert(Cond)
Definition: bd.h:262
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
void GetV(const int &VId, TValV &ValV) const
Returns ValV which is a reference (not a copy) to vector with id VId.
Definition: ds.h:1736
int Len() const
Definition: dt.h:487
Definition: tm.h:355
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1223
uint64 Reserved() const
Returns the total capacity of the pool.
Definition: ds.h:1710
unsigned int uint
Definition: bd.h:11
static const int Mx
Definition: dt.h:1139
TNodeI EndNI() const
Definition: bignet.h:168
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1880
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1730
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
unsigned long long uint64
Definition: bd.h:38
size_t TSize
Definition: bd.h:58
bool OnlySources() const
Definition: bignet.h:145
int GetNodes() const
Definition: bignet.h:151
::TSize GetEdges() const
Definition: bignet.h:185
TNodeI BegNI() const
Definition: bignet.h:167
TB32Set Flags
Definition: bignet.h:131
#define CAssert(Cond)
Definition: bd.h:302
void Reserve(const TSize &MxVals)
Reserves enough capacity for the pool to store MxVals elements.
Definition: ds.h:1712
int AddNode(int NId, const int &InDeg, const int &OutDeg)
Definition: bignet.h:320
TNodeH NodeH
Definition: bignet.h:133
double GetSecs() const
Definition: tm.h:366
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
void Excl(const int &BitN)
Definition: bits.h:265
char * CStr()
Definition: dt.h:476
int Len() const
Definition: hash.h:228
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
bool TBigNet< TNodeData, IsDir >::IsEdge ( const int &  SrcNId,
const int &  DstNId,
const bool &  Dir = true 
) const

Definition at line 553 of file bignet.h.

References TBigNet< TNodeData, IsDir >::TNode::OutVId.

553  {
554  TNode Src, Dst;
555  if (! IsNode(SrcNId, Src)) { return false; } // no source node
556  int* OutV1 = (int *)Pool.GetValVPt(Src.OutVId);
557  const bool IsEdge = BinSearch(OutV1, OutV1+Pool.GetVLen(Src.OutVId), DstNId) != NULL;
558  if (IsEdge && OnlySources()) { return true; }
559  const bool IsDstNode = IsNode(DstNId, Dst);
560  if (! IsDstNode) { return false; } // no destination node
561  else if (IsEdge) { return true; } // destination and link found
562  else if (! Dir) { // check for the undirected version of the edge
563  int* OutV2 = (int *)Pool.GetValVPt(Dst.OutVId);
564  return BinSearch(OutV2, OutV2+Pool.GetVLen(Dst.OutVId), SrcNId) != NULL; }
565  else { return false; }
566 }
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1730
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1728
bool OnlySources() const
Definition: bignet.h:145
static const int * BinSearch(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:264
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &Dir=true) const
Definition: bignet.h:553
TVPool Pool
Definition: bignet.h:132
template<class TNodeData , bool IsDir>
bool TBigNet< TNodeData, IsDir >::IsIsoNode ( const int &  NId) const

Definition at line 508 of file bignet.h.

References TVec< TVal, TSizeTy >::Empty().

508  {
509  if (NId == DelNId) { return true; }
510  TIntV OutV;
511  GetOutNIdV(NId, OutV);
512  if (OutV.Empty() || OutV[0] == DelNId) { return true; }
513  return false;
514 }
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
void GetOutNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:446

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::IsNode ( const int &  NId,
TNode Node 
) const
inlineprotected

Definition at line 118 of file bignet.h.

References THash< TKey, TDat, THashFunc >::IsKeyGetDat(), and TBigNet< TNodeData, IsDir >::NodeH.

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

118 { return NodeH.IsKeyGetDat(NId, Node); }
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
TNodeH NodeH
Definition: bignet.h:133

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::IsNode ( const int &  NId) const
inline

Definition at line 166 of file bignet.h.

References THash< TKey, TDat, THashFunc >::IsKey(), and TBigNet< TNodeData, IsDir >::NodeH.

166 { return NodeH.IsKey(NId); }
TNodeH NodeH
Definition: bignet.h:133
bool IsKey(const TKey &Key) const
Definition: hash.h:258

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
bool TBigNet< TNodeData, IsDir >::IsOk ( ) const

Definition at line 954 of file bignet.h.

References EAssert, EAssertR, TVec< TVal, TSizeTy >::Empty(), FailR, TStr::Fmt(), TBigNet< TNodeData, IsDir >::TNodeI::GetId(), TBigNet< TNodeData, IsDir >::TNodeI::GetInDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetInNId(), TInt::GetMegaStr(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutNId(), TExeTm::GetStr(), and TVec< TVal, TSizeTy >::Len().

954  {
955  // check the node pool
956  TIntV ValV; TExeTm ExeTm;
957  printf("Is ok network:\n Check Vec...");
958  for (uint id = 1; id < Pool.GetVecs(); id++) {
959  Pool.GetV(id, ValV);
960  if (! ValV.Empty()) {
961  EAssert((0<=ValV[0] && ValV[0]<MxNId) || ValV[0]==DelNId);
962  try {
963  for (int i = 1; i < ValV.Len(); i++) {
964  //if (ValV[i]==DelNId) { continue; }
965  // sorted & no duplicates & no empty values (can have deleted nodes)
966  EAssertR((ValV[i-1]<ValV[i]) || (ValV[i-1]==ValV[i] && ValV[i]==DelNId),
967  TStr::Fmt("NId1: %d NId2:%d", ValV[i-1](),ValV[i]()));
968  EAssertR((0<=ValV[i] && ValV[i]<MxNId) || ValV[i]==DelNId,
969  TStr::Fmt("NId1: %dm MxNId: %d", ValV[i](), MxNId));
970  if (! OnlySources()) {
971  EAssertR(IsNode(ValV[i]) || ValV[i]==DelNId,
972  TStr::Fmt("NId1: %dm MxNId: %d", ValV[i](), MxNId)); } // every link is a node
973  }
974  } catch (PExcept Except){
975  printf(" %s\n", Except->GetStr().CStr());
976  printf(" vec id: %d, lenght: %d\n", id, ValV.Len());
977  for (int i = 1; i < ValV.Len(); i++) {
978  printf(" %d", ValV[i]());
979  if (!((ValV[i-1]<ValV[i]) || (ValV[i-1]==ValV[i] && ValV[i]==DelNId))) { printf("*"); }
980  }
981  printf("\n");
982  return false;
983  }
984  }
985  if (id % 10000 == 0) {
986  printf("\r %dk / %dk [%s]", id/1000, Pool.GetVecs()/1000, ExeTm.GetStr()); }
987  }
988  printf("[%s]\n Check Edges...\n", ExeTm.GetStr());
989  // check edges
990  int ErrCnt = 0;
991  if (! OnlySources()) {
992  int Cnt=0;
993  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, Cnt++) {
994  // nodes that point to NI, have it on out-list
995  for (int e = 0; e < NI.GetInDeg(); e++) {
996  if (NI.GetInNId(e) == DelNId) { continue; } // skip deleted nodes
997  if (! IsEdge(NI.GetInNId(e), NI.GetId())) {
998  printf("\nno edge: %d --> %d", NI.GetInNId(e), NI.GetId());
999  printf("NId: %d deg %d,%d\n", NI.GetId(), NI.GetOutDeg(), NI.GetInDeg());
1000  for (int i = 0; i < NI.GetInDeg(); i++) { printf(" %d", NI.GetInNId(i)); }
1001  TNodeI NI2 = GetNI(NI.GetInNId(e));
1002  printf("\nNId2: %d deg %d,%d\n", NI2.GetId(), NI2.GetOutDeg(), NI2.GetInDeg());
1003  for (int j = 0; j < NI2.GetOutDeg(); j++) { printf(" %d", NI2.GetOutNId(j)); }
1004  printf("\n");
1005  ErrCnt++;
1006  }
1007  //EAssertR(IsEdge(NI.GetInNId(e), NI.GetId()),
1008  // TStr::Fmt("no edge: %d --> %d", NI.GetInNId(e), NI.GetId()));
1009  }
1010  // nodes NI points to, have it on in-list
1011  for (int e = 0; e < NI.GetOutDeg(); e++) {
1012  if (NI.GetOutNId(e) == DelNId) { continue; }
1013  const int InVId = GetNode(NI.GetOutNId(e)).InVId;
1014  int* DstInV = (int *)Pool.GetValVPt(InVId);
1015  if (BinSearch(DstInV, DstInV+Pool.GetVLen(InVId), NI.GetId()) == NULL) {
1016  printf("no edge: %d --> %d", NI.GetId(), NI.GetInNId(e));
1017  printf("NId: %d deg %d,%d\n", NI.GetId(), NI.GetOutDeg(), NI.GetInDeg());
1018  for (int i = 0; i < NI.GetOutDeg(); i++) { printf(" %d", NI.GetOutNId(i)); }
1019  TNodeI NI2 = GetNI(NI.GetOutNId(e));
1020  printf("\nNId2: %d deg %d,%d\n", NI2.GetId(), NI2.GetOutDeg(), NI2.GetInDeg());
1021  for (int j = 0; j < NI2.GetInDeg(); j++) { printf(" %d", NI2.GetInNId(j)); }
1022  printf("\n"); ErrCnt++;
1023  }
1024  //EAssertR(BinSearch(DstInV, DstInV+Pool.GetVLen(InVId), NI.GetId()) != NULL,
1025  // TStr::Fmt("no edge: %d --> %d", NI.GetId(), NI.GetInNId(e)));
1026  }
1027  if (ErrCnt > 5) { FailR("error count too large!"); }
1028  if (Cnt % 100000 == 0) {
1029  printf("\r%s [%s]", TInt::GetMegaStr(Cnt).CStr(), ExeTm.GetStr()); }
1030  }
1031  printf("\r%s [%s]\n", TInt::GetMegaStr(Cnt).CStr(), ExeTm.GetStr());
1032  }
1033  return true;
1034 }
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
void GetV(const int &VId, TValV &ValV) const
Returns ValV which is a reference (not a copy) to vector with id VId.
Definition: ds.h:1736
Definition: tm.h:355
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1223
unsigned int uint
Definition: bd.h:11
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNodeI EndNI() const
Definition: bignet.h:168
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1730
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1728
bool OnlySources() const
Definition: bignet.h:145
#define FailR(Reason)
Definition: bd.h:240
TNodeI BegNI() const
Definition: bignet.h:167
#define EAssert(Cond)
Definition: bd.h:280
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
static const int * BinSearch(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:264
int GetVecs() const
Returns the total number of vectors stored in the vector pool.
Definition: ds.h:1704
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
Definition: bd.h:196
TInt MxNId
Definition: bignet.h:130
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &Dir=true) const
Definition: bignet.h:553
const char * GetStr() const
Definition: tm.h:368
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::IsolateNode ( int  NId)

Definition at line 454 of file bignet.h.

References IAssert, TBigNet< TNodeData, IsDir >::TNode::InVId, TVec< TVal, TSizeTy >::Len(), TBigNet< TNodeData, IsDir >::TNode::OutVId, and TVec< TVal, TSizeTy >::PutAll().

454  {
455  TIntV OutV;
456  int NDel = 0;
457  // out-edges
458  GetOutNIdV(NId, OutV);
459  for (int i = 0; i < OutV.Len(); i++) {
460  if (OutV[i] == DelNId) { break; } // because they are sorted
461  // fast implementation
462  const TNode& N = NodeH.GetDat(OutV[i]);
463  int *InNIdV = (int *) Pool.GetValVPt(N.InVId);
464  const int Deg = Pool.GetVLen(N.InVId);
465  int* Val = (int *) BinSearch(InNIdV, InNIdV+Deg, NId);
466  if (Val == NULL) {
467  printf("BAD: Can't find: OUT: NId: %d -- OutNbrId: %d\n", NId, OutV[i]());
468  continue;
469  }
470  IAssert(Val != 0);
471  memcpy(Val, Val+1, sizeof(int)*int(InNIdV+Deg-Val));
472  *(InNIdV+Deg-1) = DelNId; NDel++;
473  }
474  OutV.PutAll(DelNId);
475  // in-edges
476  if (IsDir) {
477  TIntV InV;
478  GetInNIdV(NId, InV);
479  for (int i = 0; i < InV.Len(); i++) {
480  if (InV[i] == DelNId) { break; }
481  // fast implementation
482  const TNode& N = NodeH.GetDat(InV[i]);
483  int *OutNIdV = (int *) Pool.GetValVPt(N.OutVId);
484  const int Deg = Pool.GetVLen(N.OutVId);
485  int* Val = (int *) BinSearch(OutNIdV, OutNIdV+Deg, NId);
486  if (Val == NULL) {
487  printf("IN: NId: %d -- InNbrId: %d\n", NId, OutV[i]());
488  continue;
489  }
490  IAssert(Val != 0);
491  memcpy(Val, Val+1, sizeof(int)*int(OutNIdV+Deg-Val));
492  *(OutNIdV+Deg-1) = DelNId; NDel++;
493  }
494  InV.PutAll(DelNId);
495  }
496  return NDel;
497 }
#define IAssert(Cond)
Definition: bd.h:262
void GetInNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:440
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1730
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1728
static const int * BinSearch(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:264
TNodeH NodeH
Definition: bignet.h:133
void GetOutNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:446
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
static PBigNet TBigNet< TNodeData, IsDir >::Load ( TSIn SIn)
inlinestatic

Definition at line 141 of file bignet.h.

References TBigNet< TNodeData, IsDir >::TBigNet().

141 { return PBigNet(new TBigNet(SIn)); }
TPt< TBigNet< TNodeData, IsDir > > PBigNet
Definition: bignet.h:19
TBigNet(const int &Nodes, const TSize &Edges, const bool &Sources=false)
Definition: bignet.h:288

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::LoadNodeDatH ( const TStr InFNm,
TNodeH NodeH 
)
static

Definition at line 1077 of file bignet.h.

References TSIn::Load(), and THash< TKey, TDat, THashFunc >::Load().

1077  {
1078  TFIn SIn(InFNm);
1079  TInt MxNId(SIn);
1080  TB32Set Flags(SIn);
1081  printf("skipping Pool...\n");
1082  TBool FastCopy(SIn);
1083  uint64 _GrowBy, _MxVals, _Vals;
1084  SIn.Load(_GrowBy); SIn.Load(_MxVals); SIn.Load(_Vals);
1085  TInt EmptyVal(SIn);
1086  int Tmp;
1087  for (TSize ValN = 0; ValN < _Vals; ValN++) { SIn.Load(Tmp); }
1088  TInt MxVals(SIn), Vals(SIn);
1089  uint64 Offset;
1090  for (int ValN = 0; ValN < Vals; ValN++) { SIn.Load(Offset); }
1091  printf("loading Hode hash table...\n");
1092  NodeH.Load(SIn);
1093 }
Definition: fl.h:275
void Load(TSIn &SIn)
Definition: hash.h:177
unsigned long long uint64
Definition: bd.h:38
size_t TSize
Definition: bd.h:58
Definition: bits.h:239
Definition: dt.h:1134
TB32Set Flags
Definition: bignet.h:131
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
Definition: dt.h:971

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
static PBigNet TBigNet< TNodeData, IsDir >::New ( const int &  Nodes,
const TSize Edges,
const bool &  Sources = false 
)
inlinestatic

Definition at line 139 of file bignet.h.

References TBigNet< TNodeData, IsDir >::TBigNet().

139  {
140  return PBigNet(new TBigNet(Nodes, Edges, Sources)); }
TPt< TBigNet< TNodeData, IsDir > > PBigNet
Definition: bignet.h:19
TBigNet(const int &Nodes, const TSize &Edges, const bool &Sources=false)
Definition: bignet.h:288

Here is the call graph for this function:

template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::OnlySources ( ) const
inline

Definition at line 145 of file bignet.h.

References TBigNet< TNodeData, IsDir >::Flags, gfSources, and TB32Set::In().

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

145 { return Flags.In(gfSources); }
bool In(const int &BitN) const
Definition: bits.h:268
TB32Set Flags
Definition: bignet.h:131
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData, bool IsDir>
TBigNet& TBigNet< TNodeData, IsDir >::operator= ( const TBigNet< TNodeData, IsDir > &  Net)
inline

Definition at line 142 of file bignet.h.

References TBigNet< TNodeData, IsDir >::Flags, TBigNet< TNodeData, IsDir >::MxNId, TBigNet< TNodeData, IsDir >::NodeH, and TBigNet< TNodeData, IsDir >::Pool.

142  { if (this!=&Net) {
143  MxNId=Net.MxNId; Flags=Net.Flags; Pool=Net.Pool; NodeH=Net.NodeH; } return *this; }
TB32Set Flags
Definition: bignet.h:131
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::Reserve ( const int &  Nodes,
const TSize Edges 
)

Definition at line 947 of file bignet.h.

References Mega, and TMath::Mx().

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

947  {
948  NodeH.Gen(TMath::Mx(int(1.1*Nodes), 100));
949  Pool = TVPool(TMath::Mx(Edges, (TSize) Mega(1)), Mega(100), true);
950 }
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
void Gen(const int &ExpectVals)
Definition: hash.h:222
size_t TSize
Definition: bd.h:58
#define Mega(n)
Definition: gbase.h:4
TVecPool< TInt > TVPool
Definition: bignet.h:20
TNodeH NodeH
Definition: bignet.h:133
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::Rewire ( TRnd Rnd = TInt::Rnd)

Definition at line 668 of file bignet.h.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::Defrag(), THash< TKey, TDat, THashFunc >::DelKey(), THash< TKey, TDat, THashFunc >::GetDat(), TBigNet< TNodeData, IsDir >::TNodeI::GetId(), TBigNet< TNodeData, IsDir >::TNodeI::GetInDeg(), THash< TKey, TDat, THashFunc >::GetKey(), THash< TKey, TDat, THashFunc >::GetKeyV(), THash< TKey, TDat, THashFunc >::GetMxKeyIds(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutDeg(), TBigNet< TNodeData, IsDir >::TNodeI::GetOutNId(), THash< TKey, TDat, THashFunc >::GetRndKeyId(), TExeTm::GetStr(), IAssert, IAssertR, TBigNet< TNodeData, IsDir >::TNodeI::InNIdV, TBigNet< TNodeData, IsDir >::TNodeI::IsInNId(), THash< TKey, TDat, THashFunc >::IsKey(), THash< TKey, TDat, THashFunc >::Len(), Mega, and TBigNet< TNodeData, IsDir >::TNodeI::OutNIdV.

668  {
669  uint64 NDup=0, NResolve=0, NAddit=0, cnt = 0;
670  TExeTm ExeTm;
671  IAssertR(! IsDir, "Only undirected networks are supported");
672  printf("Rewiring the network... 1");
673  Pool.ShuffleAll(Rnd); printf("[%s]\n", ExeTm.GetStr());
674  //Pool.ShuffleAll(Rnd); printf(" done [%s]\n", ExeTm.GetStr());
675  printf(" sorting edges...\n");
676  SortEdgeV(); // sort individual edge vectors
677  printf(" done [%s]\n", ExeTm.GetStr());
678  // remove duplicates and self edges
679  printf(" removing duplicates...\n");
680  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, cnt++) {
681  const int VId = NI.GetOutVId();
682  int Len = Pool.GetVLen(VId);
683  int* V = (int *)Pool.GetValVPt(VId);
684  for (int i = 0; i < Len-1 && V[i]!=DelNId; i++) {
685  if (V[i] == V[i+1] || V[i]==NI.GetId()) {
686  memcpy(V+i, V+i+1, sizeof(int)*(Len-i-1)); i--;
687  V[Len-1] = DelNId; NDup++;
688  }
689  }
690  if (Len > 0 && V[Len-1]==NI.GetId()) { V[Len-1] = DelNId; NDup++; }
691  if (cnt % Mega(10) == 0) { printf("."); fflush(stdout); }
692  }
693  printf("\n %llu duplicate edges removed [%s]\n", NDup, ExeTm.GetStr());
694  if (OnlySources()) { return; }
695  // resolve one way edges
696  printf(" resolving one way edges...\n"); cnt=0; fflush(stdout);
697  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, cnt++) {
698  for (int e = 0; e < NI.GetOutDeg(); e++) {
699  if (NI.GetOutNId(e) == DelNId) { continue; } // skip deleted nodes
700  const int InVId = GetNode(NI.GetOutNId(e)).InVId;
701  const int InVLen = Pool.GetVLen(InVId); IAssert(InVLen>=0 && InVLen < Mega(3));
702  int* InV = (int *) Pool.GetValVPt(InVId);
703  int* Val = (int *) BinSearch2(InV, InV+InVLen, NI.GetId());
704  if (*Val == NI.GetId()) { continue; } // points back, everything is ok
705  if (InVLen>0 && InV[InVLen-1] == DelNId) { // there is space at the end, insert
706  IAssert((InVLen-(Val-InV)-1) >= 0);
707  memmove(Val+1, Val, sizeof(int)*(InVLen-(Val-InV)-1));
708  *Val = NI.GetId();
709  } else { // the other end could point at us but it doesn't
710  memmove(NI.OutNIdV+e, NI.OutNIdV+e+1, sizeof(int)*(NI.GetOutDeg()-e-1));
711  NI.OutNIdV[NI.GetOutDeg()-1]=DelNId; e--;
712  }
713  NResolve++;
714  }
715  if (cnt % Mega(10) == 0) { printf("."); fflush(stdout); }
716  }
717  printf("\n %llu resolved edges [%s]\n", NResolve, ExeTm.GetStr());
718  // check if there are two nodes that still have space and are not yet connected and connect them
719  printf(" filling empty edge slots...\n");
720  TIntPrV SlotNIdV;
721  THash<TInt, TInt> SlotNIdH;
722  int CumSlots=0;
723  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
724  if (NI.GetOutNId(NI.GetOutDeg()-1) == DelNId) {
725  int NSlots = 0;
726  for (int s = NI.GetOutDeg()-1; s >= 0; s--) {
727  if (NI.GetOutNId(s) == DelNId) { NSlots++; }
728  else { break; }
729  }
730  SlotNIdV.Add(TIntPr(NI.GetId(), NSlots));
731  SlotNIdH.AddDat(NI.GetId(), NSlots);
732  CumSlots+=NSlots;
733  }
734  }
735  printf(" %d nodes, with %d spokes available, %d edges\n", SlotNIdH.Len(), CumSlots, CumSlots/2);
736  TIntV NIdV; SlotNIdH.GetKeyV(NIdV);
737  for (int ni1 = 0; ni1 < NIdV.Len(); ni1++) {
738  const int nid = NIdV[ni1];
739  if (! SlotNIdH.IsKey(nid) || SlotNIdH.GetDat(nid) == 0) { continue; }
740  const int NI1Slots = SlotNIdH.GetDat(nid);
741  if ((SlotNIdH.GetMxKeyIds() - SlotNIdH.Len())/double(SlotNIdH.GetMxKeyIds()) > 0.5) { SlotNIdH.Defrag(); }
742  TNodeI NI = GetNI(nid);
743  for (int NTries = 0; NTries < 4*NI1Slots && NI.GetOutNId(NI.GetOutDeg()-1) == DelNId; NTries++) {
744  const int nid2 = SlotNIdH.GetKey(SlotNIdH.GetRndKeyId(Rnd));
745  if (nid == nid2) { continue; }
746  TNodeI NI2 = GetNI(nid2);
747  // insert the edge
748  if (NI2.GetOutNId(NI2.GetOutDeg()-1)==DelNId && ! NI2.IsInNId(NI.GetId())) {
749  int *V1 = (int *) BinSearch2(NI.OutNIdV, NI.OutNIdV+NI.GetOutDeg(), NI2.GetId());
750  int *V2 = (int *) BinSearch2(NI2.InNIdV, NI2.InNIdV+NI2.GetInDeg(), NI.GetId());
751  if (*V1 != DelNId) { memmove(V1+1, V1, sizeof(int)*(NI.GetOutDeg()-(V1-NI.OutNIdV)-1)); }
752  if (*V2 != DelNId) { memmove(V2+1, V2, sizeof(int)*(NI2.GetInDeg()-(V2-NI2.InNIdV)-1)); }
753  *V1 = NI2.GetId(); *V2 = NI.GetId();
754  NAddit++;
755  SlotNIdH.GetDat(nid)--; SlotNIdH.GetDat(nid2)--;
756  }
757  if (SlotNIdH.GetDat(nid2) == 0) { SlotNIdH.DelKey(nid2); continue; }
758  if (SlotNIdH.GetDat(nid) == 0) { SlotNIdH.DelKey(nid); break; }
759  }
760  if (ni1 % Mega(1) == 0) { printf("."); fflush(stdout); }
761  }
762  printf(" %llu edges added.\nDONE. TOTAL REWIRE TIME [%s]\n\n", NAddit, ExeTm.GetStr());
763 }
#define IAssert(Cond)
Definition: bd.h:262
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
#define IAssertR(Cond, Reason)
Definition: bd.h:265
Definition: tm.h:355
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TNodeI EndNI() const
Definition: bignet.h:168
void Defrag()
Definition: hash.h:555
void SortEdgeV()
Definition: bignet.h:576
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
void DelKey(const TKey &Key)
Definition: hash.h:404
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1730
unsigned long long uint64
Definition: bd.h:38
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1728
#define Mega(n)
Definition: gbase.h:4
bool OnlySources() const
Definition: bignet.h:145
TNodeI BegNI() const
Definition: bignet.h:167
int GetMxKeyIds() const
Definition: hash.h:231
static const int * BinSearch2(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:274
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
void ShuffleAll(TRnd &Rnd=TInt::Rnd)
Shuffles the order of all elements in the pool.
Definition: ds.h:1918
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 char * GetStr() const
Definition: tm.h:368
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::Save ( TSOut SOut) const
virtual

Definition at line 301 of file bignet.h.

References TBool::Save().

301  {
302  MxNId.Save(SOut);
303  Flags.Save(SOut);
304  Pool.Save(SOut);
305  NodeH.Save(SOut);
306  TBool(IsDir).Save(SOut);
307 }
void Save(TSOut &SOut) const
Definition: dt.h:1150
void Save(TSOut &SOut) const
Definition: hash.h:183
void Save(TSOut &SOut) const
Definition: ds.h:1834
void Save(TSOut &SOut) const
Definition: dt.h:992
void Save(TSOut &SOut) const
Definition: bits.h:248
TB32Set Flags
Definition: bignet.h:131
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
Definition: dt.h:971
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SaveForDisk ( const TStr OutFNm) const

Definition at line 1055 of file bignet.h.

References TSOut::Save().

1055  {
1056  const bool IsDirected = IsDir;
1057  TFOut FOut(OutFNm);
1058  FOut.Save(GetNodes());
1059  FOut.Save(GetEdges());
1060  FOut.Save(IsDirected);
1061  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
1062  FOut.Save(NI.GetId());
1063  NI.GetDat().Save(FOut);
1064  FOut.Save(NI.GetOutDeg());
1065  for (int i = 0; i < NI.GetOutDeg(); i++) {
1066  FOut.Save(NI.GetOutNId(i)); }
1067  if (IsDirected) {
1068  FOut.Save(NI.GetInDeg());
1069  for (int i = 0; i < NI.GetInDeg(); i++) {
1070  FOut.Save(NI.GetInNId(i)); }
1071  }
1072  }
1073 }
Definition: fl.h:319
TNodeI EndNI() const
Definition: bignet.h:168
int GetNodes() const
Definition: bignet.h:151
::TSize GetEdges() const
Definition: bignet.h:185
TNodeI BegNI() const
Definition: bignet.h:167

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SaveToDisk ( const TStr InFNm,
const TStr OutFNm,
const bool &  SaveSparseHash 
)
static

Definition at line 1097 of file bignet.h.

References THash< TKey, TDat, THashFunc >::AddDat(), THash< TKey, TDat, THashFunc >::BegI(), THash< TKey, TDat, THashFunc >::EndI(), FailR, THash< TKey, TDat, THashFunc >::Len(), TB32Set::Save(), TInt::Save(), and TVecPool< TVal, TSizeTy >::Save().

1097  {
1098  TFIn FIn(InFNm);
1099  TFOut FOut(OutFNm);
1100  { TInt MxNId(FIn); MxNId.Save(FOut);
1101  TB32Set Flags(FIn); Flags.Save(FOut);
1102  TVPool Pool(FIn); Pool.Save(FOut); }
1103  { TNodeH NodeH(FIn);
1104  if (! SaveSparseHash) {
1105  THash<TInt, TNode> NewH(NodeH.Len(), true);
1106  for (typename TNodeH::TIter I = NodeH.BegI(); I < NodeH.EndI(); I++) {
1107  NewH.AddDat(I->Key, I->Dat);
1108  }
1109  NewH.Save(FOut);
1110  } else {
1111  FailR("Not implemented");
1112  } }
1113 }
void Save(TSOut &SOut) const
Definition: dt.h:1150
TIter BegI() const
Definition: hash.h:213
Definition: fl.h:319
void Save(TSOut &SOut) const
Definition: ds.h:1834
TIter EndI() const
Definition: hash.h:218
Definition: fl.h:275
void Save(TSOut &SOut) const
Definition: bignet.h:43
void Save(TSOut &SOut) const
Definition: bits.h:248
THash< TInt, TNode > TNodeH
Definition: bignet.h:17
#define FailR(Reason)
Definition: bd.h:240
Definition: bits.h:239
TVecPool< TInt > TVPool
Definition: bignet.h:20
THashKeyDatI< TInt, TNode > TIter
Definition: hash.h:102
Definition: dt.h:1134
TB32Set Flags
Definition: bignet.h:131
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
int Len() const
Definition: hash.h:228
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SetInNIdV ( int  NId,
const TIntV InNIdV 
)

Definition at line 424 of file bignet.h.

References TVec< TVal, TSizeTy >::BegI(), EAssert, TVec< TVal, TSizeTy >::GetV(), TBigNet< TNodeData, IsDir >::TNode::InVId, and TVec< TVal, TSizeTy >::Len().

424  {
425  TNode Node; EAssert(IsNode(NId, Node));
426  TIntV InNodesV; Pool.GetV(Node.InVId, InNodesV);
427  EAssert(InNIdV.Len() == InNodesV.Len());
428  memcpy(InNodesV.BegI(), InNIdV.BegI(), sizeof(TInt)*InNIdV.Len());
429 }
void GetV(const int &VId, TValV &ValV) const
Returns ValV which is a reference (not a copy) to vector with id VId.
Definition: ds.h:1736
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
Definition: dt.h:1134
#define EAssert(Cond)
Definition: bd.h:280
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SetOutNIdV ( int  NId,
const TIntV OutNIdV 
)

Definition at line 432 of file bignet.h.

References TVec< TVal, TSizeTy >::BegI(), EAssert, TVec< TVal, TSizeTy >::GetV(), TVec< TVal, TSizeTy >::Len(), and TBigNet< TNodeData, IsDir >::TNode::OutVId.

432  {
433  TNode Node; EAssert(IsNode(NId, Node));
434  TIntV OutNodesV; Pool.GetV(Node.OutVId, OutNodesV);
435  EAssert(OutNIdV.Len() == OutNodesV.Len());
436  memcpy(OutNodesV.BegI(), OutNIdV.BegI(), sizeof(TInt)*OutNIdV.Len());
437 }
void GetV(const int &VId, TValV &ValV) const
Returns ValV which is a reference (not a copy) to vector with id VId.
Definition: ds.h:1736
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
Definition: dt.h:1134
#define EAssert(Cond)
Definition: bd.h:280
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TVPool Pool
Definition: bignet.h:132

Here is the call graph for this function:

template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SortEdgeV ( )

Definition at line 576 of file bignet.h.

References TExeTm::GetStr(), IAssert, TVec< TVal, TSizeTy >::IsSorted(), Mega, and TVec< TVal, TSizeTy >::Sort().

576  {
577  printf("Sorting Edges... ");
578  TExeTm ExeTm;
579  TIntV OutV, InV;
580  int cnt = 0;
581  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
582  const int NId = NI.GetId();
583  GetOutNIdV(NId, OutV);
584  OutV.Sort();
585  if (IsDir) {
586  GetInNIdV(NId, InV);
587  InV.Sort();
588  }
589  if (++cnt % Mega(1) == 0) { printf("\r sort:%dm %s", cnt/Mega(1), ExeTm.GetStr()); }
590  }
591  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
592  const int NId = NI.GetId();
593  GetOutNIdV(NId, OutV);
594  IAssert(OutV.IsSorted());
595  GetInNIdV(NId, InV);
596  IAssert(InV.IsSorted());
597  if (++cnt % Mega(1) == 0) { printf("\r check sorted:%dm %s", cnt/Mega(1), ExeTm.GetStr()); }
598  }
599  printf("done. [%s]\n", ExeTm.GetStr());
600 }
#define IAssert(Cond)
Definition: bd.h:262
void GetInNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:440
Definition: tm.h:355
TNodeI EndNI() const
Definition: bignet.h:168
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
#define Mega(n)
Definition: gbase.h:4
TNodeI BegNI() const
Definition: bignet.h:167
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1323
const char * GetStr() const
Definition: tm.h:368
void GetOutNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:446

Here is the call graph for this function:

Friends And Related Function Documentation

template<class TNodeData, bool IsDir>
friend class TPt< TBigNet >
friend

Definition at line 213 of file bignet.h.

Member Data Documentation

template<class TNodeData, bool IsDir>
TCRef TBigNet< TNodeData, IsDir >::CRef
protected

Definition at line 129 of file bignet.h.

template<class TNodeData, bool IsDir>
TB32Set TBigNet< TNodeData, IsDir >::Flags
protected
template<class TNodeData, bool IsDir>
TInt TBigNet< TNodeData, IsDir >::MxNId
protected

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