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
TBigNet< TNodeData, IsDir > Class Template Reference

Big Network. More...

#include <bignet.h>

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.

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:1049
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
template<class TNodeData, bool IsDir>
TBigNet< TNodeData, IsDir >::TBigNet ( TSIn SIn)
inline

Definition at line 136 of file bignet.h.

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:881
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.

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:1665
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1663
#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.

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:1046
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1815
#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:196
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.

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:1046
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1815
#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:196
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.

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:1804
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1046
#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:1259
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:196
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.

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:1804
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1046
#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:1259
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:196
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.

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:1049
template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddUndirNode ( int  NId,
const int &  Deg 
)

Definition at line 345 of file bignet.h.

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:1046
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1815
#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:196
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.

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:1046
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1815
#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:196
template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::AddUndirNode ( int  NId,
const TIntV EdgeNIdV 
)

Definition at line 397 of file bignet.h.

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:1804
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1046
#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:1259
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:196
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.

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:1804
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int Val
Definition: dt.h:1046
#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:1259
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:196
template<class TNodeData, bool IsDir>
TEdgeI TBigNet< TNodeData, IsDir >::BegEI ( ) const
inline

Definition at line 173 of file bignet.h.

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
template<class TNodeData, bool IsDir>
TNodeI TBigNet< TNodeData, IsDir >::BegNI ( ) const
inline

Definition at line 167 of file bignet.h.

167 { return TNodeI(NodeH.BegI(), (TVPool *)&Pool); }
TIter BegI() const
Definition: hash.h:171
TVecPool< TInt > TVPool
Definition: bignet.h:20
TNodeH NodeH
Definition: bignet.h:133
TVPool Pool
Definition: bignet.h:132
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.

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

204 { MxNId = 0; NodeH.Clr(DoDel); Pool.Clr(DoDel); }
void Clr(bool DoDel=true)
Clears the contents of the pool.
Definition: ds.h:1694
TNodeH NodeH
Definition: bignet.h:133
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:319
TInt MxNId
Definition: bignet.h:130
TVPool Pool
Definition: bignet.h:132
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:1824
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:362
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.

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
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::DumpFlags ( ) const

Definition at line 310 of file bignet.h.

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
template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::Empty ( ) const
inline

Definition at line 203 of file bignet.h.

203 { return GetNodes()==0; }
int GetNodes() const
Definition: bignet.h:151
template<class TNodeData, bool IsDir>
TEdgeI TBigNet< TNodeData, IsDir >::EndEI ( ) const
inline

Definition at line 174 of file bignet.h.

174 { return TEdgeI(EndNI(), EndNI()); }
TNodeI EndNI() const
Definition: bignet.h:168
template<class TNodeData, bool IsDir>
TNodeI TBigNet< TNodeData, IsDir >::EndNI ( ) const
inline

Definition at line 168 of file bignet.h.

168 { return TNodeI(NodeH.EndI(), (TVPool *)&Pool); }
TIter EndI() const
Definition: hash.h:176
TVecPool< TInt > TVPool
Definition: bignet.h:20
TNodeH NodeH
Definition: bignet.h:133
TVPool Pool
Definition: bignet.h:132
template<class TNodeData , bool IsDir>
uint TBigNet< TNodeData, IsDir >::GetDelEdges ( )

Definition at line 518 of file bignet.h.

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:547
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
template<class TNodeData, bool IsDir>
::TSize TBigNet< TNodeData, IsDir >::GetEdges ( ) const
inline

Definition at line 185 of file bignet.h.

185 { return Pool.GetVals(); }
TSize GetVals() const
Returns the total number of values stored in the vector pool.
Definition: ds.h:1641
TVPool Pool
Definition: bignet.h:132
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.

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:1671
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
template<class TNodeData, bool IsDir>
int* TBigNet< TNodeData, IsDir >::GetInNIdVPt ( const int &  NId) const
inlineprotected

Definition at line 119 of file bignet.h.

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:1665
TVPool Pool
Definition: bignet.h:132
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.

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.

170 { return NodeH.GetDat(NId).Dat; }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TNodeDat Dat
Data associated with the node.
Definition: bignet.h:35
TNodeH NodeH
Definition: bignet.h:133
template<class TNodeData, bool IsDir>
const TNodeDat& TBigNet< TNodeData, IsDir >::GetNDat ( const int &  NId) const
inline

Definition at line 171 of file bignet.h.

171 { return NodeH.GetDat(NId).Dat; }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TNodeDat Dat
Data associated with the node.
Definition: bignet.h:35
TNodeH NodeH
Definition: bignet.h:133
template<class TNodeData , bool IsDir>
PNGraph TBigNet< TNodeData, IsDir >::GetNGraph ( const bool &  RenumberNodes = false) const

Definition at line 766 of file bignet.h.

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:425
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:534
TVPool Pool
Definition: bignet.h:132
template<class TNodeData, bool IsDir>
TNodeI TBigNet< TNodeData, IsDir >::GetNI ( const int &  NId) const
inline

Definition at line 169 of file bignet.h.

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:178
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::GetNIdV ( TIntV NIdV) const

Definition at line 569 of file bignet.h.

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:171
TIter EndI() const
Definition: hash.h:176
int GetNodes() const
Definition: bignet.h:151
THashKeyDatI< TInt, TNode > TIter
Definition: hash.h:93
TNodeH NodeH
Definition: bignet.h:133
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:515
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
template<class TNodeData, bool IsDir>
const TNode& TBigNet< TNodeData, IsDir >::GetNode ( const int &  NId) const
inlineprotected

Definition at line 124 of file bignet.h.

124 { return NodeH.GetDat(NId); }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TNodeH NodeH
Definition: bignet.h:133
template<class TNodeData, bool IsDir>
TNode& TBigNet< TNodeData, IsDir >::GetNode ( const int &  NId)
inlineprotected

Definition at line 125 of file bignet.h.

125 { return NodeH.GetDat(NId); }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TNodeH NodeH
Definition: bignet.h:133
template<class TNodeData, bool IsDir>
int TBigNet< TNodeData, IsDir >::GetNodes ( ) const
inline

Definition at line 151 of file bignet.h.

151 { return NodeH.Len(); }
TNodeH NodeH
Definition: bignet.h:133
int Len() const
Definition: hash.h:186
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::GetOutNIdV ( int  NId,
TIntV OutNIdV 
) const

Definition at line 446 of file bignet.h.

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:1671
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.

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:1665
TVPool Pool
Definition: bignet.h:132
template<class TNodeData, bool IsDir>
TNodeI TBigNet< TNodeData, IsDir >::GetRndNI ( TRnd Rnd = TInt::Rnd) const
inline

Definition at line 200 of file bignet.h.

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
template<class TNodeData, bool IsDir>
int TBigNet< TNodeData, IsDir >::GetRndNId ( TRnd Rnd = TInt::Rnd) const
inline

Definition at line 199 of file bignet.h.

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:402
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
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.

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:547
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
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.

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:547
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:196
bool HasFlag(const TGraphFlag &Flag) const
Definition: bignet.h:146
template<class TNodeData , bool IsDir>
PNGraph TBigNet< TNodeData, IsDir >::GetSubNGraph ( const TIntV NIdV) const

Definition at line 777 of file bignet.h.

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:425
void ReserveNIdInDeg(const int &NId, const int &InDeg)
Reserves memory for node ID NId having InDeg in-edges.
Definition: graph.h:536
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
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 IDs 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:477
void ReserveNIdOutDeg(const int &NId, const int &OutDeg)
Reserves memory for node ID NId having OutDeg out-edges.
Definition: graph.h:538
template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::HasFlag ( const TGraphFlag Flag) const
inline

Definition at line 146 of file bignet.h.

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
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::InvertFromSources ( uint  ExpectNodes = 0)

Definition at line 604 of file bignet.h.

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:1671
int Len() const
Definition: dt.h:487
Definition: tm.h:355
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1133
uint64 Reserved() const
Returns the total capacity of the pool.
Definition: ds.h:1645
unsigned int uint
Definition: bd.h:11
static const int Mx
Definition: dt.h:1049
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:1815
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:1665
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1254
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:1647
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:186
TVPool Pool
Definition: bignet.h:132
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.

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:1665
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1663
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.

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:542
void GetOutNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:446
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.

118 { return NodeH.IsKeyGetDat(NId, Node); }
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:232
TNodeH NodeH
Definition: bignet.h:133
template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::IsNode ( const int &  NId) const
inline

Definition at line 166 of file bignet.h.

166 { return NodeH.IsKey(NId); }
TNodeH NodeH
Definition: bignet.h:133
bool IsKey(const TKey &Key) const
Definition: hash.h:216
template<class TNodeData , bool IsDir>
bool TBigNet< TNodeData, IsDir >::IsOk ( ) const

Definition at line 954 of file bignet.h.

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:1671
Definition: tm.h:355
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1133
unsigned int uint
Definition: bd.h:11
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TNodeI EndNI() const
Definition: bignet.h:168
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
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:1665
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1663
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:1639
#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
template<class TNodeData , bool IsDir>
int TBigNet< TNodeData, IsDir >::IsolateNode ( int  NId)

Definition at line 454 of file bignet.h.

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:547
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1665
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1663
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
template<class TNodeData, bool IsDir>
static PBigNet TBigNet< TNodeData, IsDir >::Load ( TSIn SIn)
inlinestatic

Definition at line 141 of file bignet.h.

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
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::LoadNodeDatH ( const TStr InFNm,
TNodeH NodeH 
)
static

Definition at line 1077 of file bignet.h.

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:137
unsigned long long uint64
Definition: bd.h:38
size_t TSize
Definition: bd.h:58
Definition: bits.h:239
Definition: dt.h:1044
TB32Set Flags
Definition: bignet.h:131
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
Definition: dt.h:881
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.

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
template<class TNodeData, bool IsDir>
bool TBigNet< TNodeData, IsDir >::OnlySources ( ) const
inline

Definition at line 145 of file bignet.h.

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
template<class TNodeData, bool IsDir>
TBigNet& TBigNet< TNodeData, IsDir >::operator= ( const TBigNet< TNodeData, IsDir > &  Net)
inline

Definition at line 142 of file bignet.h.

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.

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:180
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
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::Rewire ( TRnd Rnd = TInt::Rnd)

Definition at line 668 of file bignet.h.

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:220
TNodeI EndNI() const
Definition: bignet.h:168
void Defrag()
Definition: hash.h:513
void SortEdgeV()
Definition: bignet.h:576
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
void DelKey(const TKey &Key)
Definition: hash.h:362
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1665
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:1663
#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:189
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:442
void ShuffleAll(TRnd &Rnd=TInt::Rnd)
Shuffles the order of all elements in the pool.
Definition: ds.h:1853
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
const char * GetStr() const
Definition: tm.h:368
bool IsKey(const TKey &Key) const
Definition: hash.h:216
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
int Len() const
Definition: hash.h:186
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::Save ( TSOut SOut) const
virtual

Definition at line 301 of file bignet.h.

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:1060
void Save(TSOut &SOut) const
Definition: hash.h:141
void Save(TSOut &SOut) const
Definition: ds.h:1769
void Save(TSOut &SOut) const
Definition: dt.h:902
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:881
TVPool Pool
Definition: bignet.h:132
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SaveForDisk ( const TStr OutFNm) const

Definition at line 1055 of file bignet.h.

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

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:1060
TIter BegI() const
Definition: hash.h:171
Definition: fl.h:319
void Save(TSOut &SOut) const
Definition: ds.h:1769
TIter EndI() const
Definition: hash.h:176
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:93
Definition: dt.h:1044
TB32Set Flags
Definition: bignet.h:131
TNodeH NodeH
Definition: bignet.h:133
TInt MxNId
Definition: bignet.h:130
int Len() const
Definition: hash.h:186
TVPool Pool
Definition: bignet.h:132
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SetInNIdV ( int  NId,
const TIntV InNIdV 
)

Definition at line 424 of file bignet.h.

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:1671
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
Definition: dt.h:1044
#define EAssert(Cond)
Definition: bd.h:280
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:565
TVPool Pool
Definition: bignet.h:132
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SetOutNIdV ( int  NId,
const TIntV OutNIdV 
)

Definition at line 432 of file bignet.h.

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:1671
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
Definition: dt.h:1044
#define EAssert(Cond)
Definition: bd.h:280
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:565
TVPool Pool
Definition: bignet.h:132
template<class TNodeData , bool IsDir>
void TBigNet< TNodeData, IsDir >::SortEdgeV ( )

Definition at line 576 of file bignet.h.

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:1254
#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:1259
const char * GetStr() const
Definition: tm.h:368
void GetOutNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:446

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

Definition at line 131 of file bignet.h.

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

Definition at line 130 of file bignet.h.

template<class TNodeData, bool IsDir>
TNodeH TBigNet< TNodeData, IsDir >::NodeH
protected

Definition at line 133 of file bignet.h.

template<class TNodeData, bool IsDir>
TVPool TBigNet< TNodeData, IsDir >::Pool
protected

Definition at line 132 of file bignet.h.


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