SNAP Library 4.1, User Reference  2018-07-26 16:30:42
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Friends | List of all members
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< TNet > PNet
 
typedef THash< TInt, TNode > TNodeH
 
typedef TPt< TBigNet
< TNodeData, IsDir > > 		PBigNet
 
typedef TVecPool< TInt > TVPool
 
typedef TPt< TVPool > PVPool
 

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
 
TBigNet & operator= (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
 
TNodeDat & GetNDat (const int &NId)
 
const TNodeDat & GetNDat (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 TNode & GetNode (const int &NId) const
 
TNode & GetNode (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) {
294  Flags.Incl(gfSources);
295  IAssertR(! IsDir, "Jure: not clear what happens is graph is Undirected and has only sources.");
296  }
297  //DumpFlags();
298 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TInt::Mx
static const int Mx
Definition: dt.h:1139
TBigNet::CRef
TCRef CRef
Definition: bignet.h:129
TB32Set::Incl
void Incl(const int &BitN)
Definition: bits.h:262
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
gfSources
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
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); }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBool
Definition: dt.h:971
TBigNet::Pool
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TVecPool::GetValVPt
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
TVecPool::GetVLen
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
Assert
#define Assert(Cond)
Definition: bd.h:251
TBigNet::OnlySources
bool OnlySources() const
Definition: bignet.h:145
TBigNet::BinSearch
static const int * BinSearch(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:264
TBigNet::AddSorted
static void AddSorted(int *Beg, int *End, const int &Val)
Definition: bignet.h:248
TBigNet::Pool
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 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
TVecPool::AddEmptyV
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1881
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
TVecPool::AddEmptyV
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1881
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVecPool::AddV
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1870
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TVec::IsSorted
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
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVecPool::AddV
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1870
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TVec::IsSorted
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
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TInt::Mx
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.

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 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
TVecPool::AddEmptyV
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1881
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
TVecPool::AddEmptyV
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1881
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVecPool::AddV
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1870
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TVec::IsSorted
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
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVecPool::AddV
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1870
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt::Val
int Val
Definition: dt.h:1136
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TVec::IsSorted
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
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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()); }
TBigNet::TNodeI::GetOutDeg
int GetOutDeg() const
Definition: bignet.h:72
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TBigNet::BegNI
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); }
THash::BegI
TIter BegI() const
Definition: hash.h:213
TBigNet::TVPool
TVecPool< TInt > TVPool
Definition: bignet.h:20
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::Pool
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 }
TSize
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); }
TVecPool::Clr
void Clr(bool DoDel=true)
Clears the contents of the pool.
Definition: ds.h:1760
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
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  {
533  Pool.CompactPool(DelNId);
534 }
TVecPool::CompactPool
void CompactPool(const TVal &DelVal)
Deletes all elements of value DelVal from all vectors.
Definition: ds.h:1890
TBigNet::Pool
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 }
TBigNet::IsolateNode
int IsolateNode(int NId)
Definition: bignet.h:454
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:404
TBigNet::NodeH
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 }
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TBigNet::GetNodes
int GetNodes() const
Definition: bignet.h:151
TBigNet::GetEdges
::TSize GetEdges() const
Definition: bignet.h:185
TBigNet::BegNI
TNodeI BegNI() const
Definition: bignet.h:167
TStr::Empty
bool Empty() const
Definition: dt.h:488
TStr::CStr
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 }
TSnap::GetFlagStr
TStr GetFlagStr(const TGraphFlag &GraphFlag)
Returns a string representation of a flag.
Definition: gbase.cpp:5
gfMx
sentinel, last value for iteration
Definition: gbase.h:19
TGraphFlag
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
TBigNet::HasFlag
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; }
TBigNet::GetNodes
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()); }
TBigNet::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); }
THash::EndI
TIter EndI() const
Definition: hash.h:218
TBigNet::TVPool
TVecPool< TInt > TVPool
Definition: bignet.h:20
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::Pool
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 }
uint
unsigned int uint
Definition: bd.h:11
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TBigNet::BegNI
TNodeI BegNI() const
Definition: bignet.h:167
TBigNet::GetOutNIdV
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(); }
TVecPool::GetVals
TSize GetVals() const
Returns the total number of values stored in the vector pool.
Definition: ds.h:1707
TBigNet::Pool
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 }
TVecPool::GetV
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:1737
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
EAssertR
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TBigNet::Pool
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); }
TBigNet::GetNode
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
TVecPool::GetValVPt
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
TBigNet::Pool
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; }
TBigNet::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; }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TBigNet::TNode::Dat
TNodeDat Dat
Data associated with the node.
Definition: bignet.h:35
TBigNet::NodeH
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; }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TBigNet::TNode::Dat
TNodeDat Dat
Data associated with the node.
Definition: bignet.h:35
TBigNet::NodeH
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TBigNet::GetNodes
int GetNodes() const
Definition: bignet.h:151
TBigNet::BegNI
TNodeI BegNI() const
Definition: bignet.h:167
TNGraph::Reserve
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:606
TBigNet::Pool
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); }
TBigNet::TVPool
TVecPool< TInt > TVPool
Definition: bignet.h:20
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::GetI
TIter GetI(const TKey &Key) const
Definition: hash.h:220
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 }
THash::BegI
TIter BegI() const
Definition: hash.h:213
THash::EndI
TIter EndI() const
Definition: hash.h:218
TBigNet::GetNodes
int GetNodes() const
Definition: bignet.h:151
THash< TInt, TNode >::TIter
THashKeyDatI< TInt, TNode > TIter
Definition: hash.h:102
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TVec::Reserve
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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); }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TBigNet::NodeH
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); }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TBigNet::NodeH
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(); }
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
THash::Len
int Len() const
Definition: hash.h:228
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 }
TVecPool::GetV
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:1737
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
EAssert
#define EAssert(Cond)
Definition: bd.h:280
TBigNet::Pool
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); }
TBigNet::GetNode
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
TVecPool::GetValVPt
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
TBigNet::Pool
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)); }
TBigNet::GetNI
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
TBigNet::GetRndNId
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)); }
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
THash::GetRndKeyId
int GetRndKeyId(TRnd &Rnd) const
Get an index of a random element. If the hash table has many deleted keys, this may take a long time...
Definition: hash.h:444
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
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 }
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TBigNet::GetNDat
TNodeDat & GetNDat(const int &NId)
Definition: bignet.h:170
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TBigNet::GetNI
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
TSize
size_t TSize
Definition: bd.h:58
TBigNet
Big Network.
Definition: bignet.h:11
gfDirected
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
EAssert
#define EAssert(Cond)
Definition: bd.h:280
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
TPair
Definition: ds.h:32
TSparseHash::AddDat
TDat & AddDat(const TKey &Key)
Definition: shash.h:687
gfSources
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TPair::Val2
TVal2 Val2
Definition: ds.h:35
TPt
Definition: bd.h:196
TBigNet::HasFlag
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 }
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TBigNet::AddUndirNode
int AddUndirNode(int NId, const int &Deg)
Definition: bignet.h:345
TBigNet::GetNDat
TNodeDat & GetNDat(const int &NId)
Definition: bignet.h:170
TExeTm
Definition: tm.h:355
uint
unsigned int uint
Definition: bd.h:11
THashSet::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THashSet::Gen
void Gen(const int &ExpectVals)
Definition: shash.h:1115
TBigNet::GetNI
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TBigNet::GetOutNIdVPt
int * GetOutNIdVPt(const int &NId) const
Definition: bignet.h:120
TSize
size_t TSize
Definition: bd.h:58
TBigNet
Big Network.
Definition: bignet.h:11
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
EAssert
#define EAssert(Cond)
Definition: bd.h:280
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
TPair
Definition: ds.h:32
TBigNet::AddNode
int AddNode(int NId, const int &InDeg, const int &OutDeg)
Definition: bignet.h:320
TBigNet::GetInNIdVPt
int * GetInNIdVPt(const int &NId) const
Definition: bignet.h:119
gfSources
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TPair::Val2
TVal2 Val2
Definition: ds.h:35
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TBigNet::HasFlag
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 }
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TNGraph::ReserveNIdInDeg
void ReserveNIdInDeg(const int &NId, const int &InDeg)
Reserves memory for node ID NId having InDeg in-edges.
Definition: graph.h:608
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TBigNet::GetNI
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
TNGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:542
TNGraph::ReserveNIdOutDeg
void ReserveNIdOutDeg(const int &NId, const int &OutDeg)
Reserves memory for node ID NId having OutDeg out-edges.
Definition: graph.h:610
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()); }
HasGraphFlag
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
TBigNet
Big Network.
Definition: bignet.h:11
TBigNet::OnlySources
bool OnlySources() const
Definition: bignet.h:145
gfSources
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());
664  Flags.Excl(gfSources);
665 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBigNet::GetNode
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
TVecPool::GetV
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:1737
TStr::Len
int Len() const
Definition: dt.h:487
TExeTm
Definition: tm.h:355
TInt::GetMegaStr
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1223
TVecPool::Reserved
uint64 Reserved() const
Returns the total capacity of the pool.
Definition: ds.h:1711
uint
unsigned int uint
Definition: bd.h:11
TInt::Mx
static const int Mx
Definition: dt.h:1139
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TVecPool::AddEmptyV
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1881
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TVecPool::GetValVPt
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
uint64
unsigned long long uint64
Definition: bd.h:38
TSize
size_t TSize
Definition: bd.h:58
TBigNet::OnlySources
bool OnlySources() const
Definition: bignet.h:145
TBigNet::GetNodes
int GetNodes() const
Definition: bignet.h:151
TBigNet::GetEdges
::TSize GetEdges() const
Definition: bignet.h:185
TBigNet::BegNI
TNodeI BegNI() const
Definition: bignet.h:167
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
CAssert
#define CAssert(Cond)
Definition: bd.h:302
TVecPool::Reserve
void Reserve(const TSize &MxVals)
Reserves enough capacity for the pool to store MxVals elements.
Definition: ds.h:1713
TBigNet::AddNode
int AddNode(int NId, const int &InDeg, const int &OutDeg)
Definition: bignet.h:320
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TExeTm::GetSecs
double GetSecs() const
Definition: tm.h:366
gfSources
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
TB32Set::Excl
void Excl(const int &BitN)
Definition: bits.h:265
TStr::CStr
char * CStr()
Definition: dt.h:476
THash::Len
int Len() const
Definition: hash.h:228
TBigNet::Pool
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 }
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TVecPool::GetValVPt
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
TVecPool::GetVLen
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
TBigNet::OnlySources
bool OnlySources() const
Definition: bignet.h:145
TBigNet::BinSearch
static const int * BinSearch(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:264
TBigNet::IsEdge
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &Dir=true) const
Definition: bignet.h:553
TBigNet::Pool
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 }
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TBigNet::GetOutNIdV
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); }
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
TBigNet::NodeH
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); }
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
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 }
TBigNet::GetNode
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
TVecPool::GetV
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:1737
TExeTm
Definition: tm.h:355
TInt::GetMegaStr
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1223
uint
unsigned int uint
Definition: bd.h:11
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TBigNet::GetNI
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TVecPool::GetValVPt
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
TVecPool::GetVLen
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
TBigNet::OnlySources
bool OnlySources() const
Definition: bignet.h:145
FailR
#define FailR(Reason)
Definition: bd.h:240
TBigNet::BegNI
TNodeI BegNI() const
Definition: bignet.h:167
EAssert
#define EAssert(Cond)
Definition: bd.h:280
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TBigNet::BinSearch
static const int * BinSearch(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:264
TVecPool::GetVecs
int GetVecs() const
Returns the total number of vectors stored in the vector pool.
Definition: ds.h:1705
EAssertR
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TPt
Definition: bd.h:196
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::IsEdge
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &Dir=true) const
Definition: bignet.h:553
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TBigNet::Pool
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBigNet::GetInNIdV
void GetInNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:440
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TVecPool::GetValVPt
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
TVecPool::GetVLen
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
TBigNet::BinSearch
static const int * BinSearch(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:264
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::GetOutNIdV
void GetOutNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:446
TBigNet::Pool
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)); }
TBigNet::PBigNet
TPt< TBigNet< TNodeData, IsDir > > PBigNet
Definition: bignet.h:19
TBigNet::TBigNet
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 }
TFIn
Definition: fl.h:275
THash::Load
void Load(TSIn &SIn)
Definition: hash.h:177
uint64
unsigned long long uint64
Definition: bd.h:38
TSize
size_t TSize
Definition: bd.h:58
TB32Set
Definition: bits.h:239
TInt
Definition: dt.h:1134
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBool
Definition: dt.h:971
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)); }
TBigNet::PBigNet
TPt< TBigNet< TNodeData, IsDir > > PBigNet
Definition: bignet.h:19
TBigNet::TBigNet
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); }
TB32Set::In
bool In(const int &BitN) const
Definition: bits.h:268
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
gfSources
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; }
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::Pool
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 }
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:222
TSize
size_t TSize
Definition: bd.h:58
Mega
#define Mega(n)
Definition: gbase.h:4
TBigNet::TVPool
TVecPool< TInt > TVPool
Definition: bignet.h:20
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::Pool
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBigNet::GetNode
const TNode & GetNode(const int &NId) const
Definition: bignet.h:124
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TExeTm
Definition: tm.h:355
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
THash::Defrag
void Defrag()
Definition: hash.h:555
TBigNet::SortEdgeV
void SortEdgeV()
Definition: bignet.h:576
TBigNet::GetNI
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:404
TVecPool::GetValVPt
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
uint64
unsigned long long uint64
Definition: bd.h:38
TVecPool::GetVLen
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
Mega
#define Mega(n)
Definition: gbase.h:4
TBigNet::OnlySources
bool OnlySources() const
Definition: bignet.h:145
TBigNet::BegNI
TNodeI BegNI() const
Definition: bignet.h:167
THash::GetMxKeyIds
int GetMxKeyIds() const
Definition: hash.h:231
TBigNet::BinSearch2
static const int * BinSearch2(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:274
THash::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
TVecPool::ShuffleAll
void ShuffleAll(TRnd &Rnd=TInt::Rnd)
Shuffles the order of all elements in the pool.
Definition: ds.h:1919
THash::GetRndKeyId
int GetRndKeyId(TRnd &Rnd) const
Get an index of a random element. If the hash table has many deleted keys, this may take a long time...
Definition: hash.h:444
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::Len
int Len() const
Definition: hash.h:228
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
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 }
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1150
THash::Save
void Save(TSOut &SOut) const
Definition: hash.h:183
TVecPool::Save
void Save(TSOut &SOut) const
Definition: ds.h:1835
TBool::Save
void Save(TSOut &SOut) const
Definition: dt.h:992
TB32Set::Save
void Save(TSOut &SOut) const
Definition: bits.h:248
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBool
Definition: dt.h:971
TBigNet::Pool
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 }
TFOut
Definition: fl.h:319
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TBigNet::GetNodes
int GetNodes() const
Definition: bignet.h:151
TBigNet::GetEdges
::TSize GetEdges() const
Definition: bignet.h:185
TBigNet::BegNI
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 }
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1150
THash::BegI
TIter BegI() const
Definition: hash.h:213
TFOut
Definition: fl.h:319
TVecPool::Save
void Save(TSOut &SOut) const
Definition: ds.h:1835
THash::EndI
TIter EndI() const
Definition: hash.h:218
TFIn
Definition: fl.h:275
TBigNet::TNode::Save
void Save(TSOut &SOut) const
Definition: bignet.h:43
TB32Set::Save
void Save(TSOut &SOut) const
Definition: bits.h:248
TBigNet::TNodeH
THash< TInt, TNode > TNodeH
Definition: bignet.h:17
FailR
#define FailR(Reason)
Definition: bd.h:240
TB32Set
Definition: bits.h:239
TBigNet::TVPool
TVecPool< TInt > TVPool
Definition: bignet.h:20
THash< TInt, TNode >::TIter
THashKeyDatI< TInt, TNode > TIter
Definition: hash.h:102
TInt
Definition: dt.h:1134
TBigNet::Flags
TB32Set Flags
Definition: bignet.h:131
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
THash::Len
int Len() const
Definition: hash.h:228
TBigNet::Pool
TVPool Pool
Definition: bignet.h:132
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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 }
TVecPool::GetV
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:1737
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TInt
Definition: dt.h:1134
EAssert
#define EAssert(Cond)
Definition: bd.h:280
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TBigNet::Pool
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 }
TVecPool::GetV
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:1737
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TInt
Definition: dt.h:1134
EAssert
#define EAssert(Cond)
Definition: bd.h:280
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TBigNet::Pool
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBigNet::GetInNIdV
void GetInNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:440
TExeTm
Definition: tm.h:355
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
Mega
#define Mega(n)
Definition: gbase.h:4
TBigNet::BegNI
TNodeI BegNI() const
Definition: bignet.h:167
TVec::IsSorted
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
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TBigNet::GetOutNIdV
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: