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.

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

                                                                                            :
CRef(), MxNId(0), Flags(), Pool(IsDir ? 2*Edges:Edges, 10000000, true, TInt::Mx), NodeH(Nodes) {
  //Flags.Incl(gfNodeGraph);
  //Flags.Incl(gfNetwork);
  //if (IsDir) { Flags.Incl(gfDirected); }
  if (Sources) {
    Flags.Incl(gfSources);
    IAssertR(! IsDir, "Jure: not clear what happens is graph is Undirected and has only sources.");
  }
  //DumpFlags();
}

template<class TNodeData, bool IsDir>

TBigNet< TNodeData, IsDir >::TBigNet ( TSIn &  SIn )

inline

Definition at line 136 of file bignet.h.

: MxNId(SIn), Flags(SIn), Pool(SIn), NodeH(SIn) { TBool Dir(SIn); IAssert(Dir()==IsDir); }

template<class TNodeData, bool IsDir>

virtual TBigNet< TNodeData, IsDir >::~TBigNet ( )

inlinevirtual

Definition at line 137 of file bignet.h.

{ }

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.

                                                                           {
  TNode Src;  IAssert(IsNode(SrcNId, Src));
  int* OutV = (int *)Pool.GetValVPt(Src.OutVId);
  const int OutVLen = Pool.GetVLen(Src.OutVId);
  Assert(BinSearch(OutV, OutV+OutVLen, DstNId)==NULL); // no edge yet
  AddSorted(OutV, OutV+OutVLen, DstNId);
  if (! OnlySources()) {
    TNode Dst;  IAssert(IsNode(DstNId, Dst));
    int* InV = (int *)Pool.GetValVPt(Dst.InVId);
    const int InVLen = Pool.GetVLen(Dst.InVId);
    AddSorted(InV, InV+InVLen, SrcNId);
  }
  return -1; // edge id
}

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.

                                                                                   {
  CAssert(IsDir);
  if (NId == -1) { NId = MxNId;  MxNId.Val++; }
  else { MxNId = TMath::Mx(NId+1, MxNId()); }
  TNode& Node = NodeH.AddDat(NId);
  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
  Node.InVId = Pool.AddEmptyV(InDeg);
  Node.OutVId = Pool.AddEmptyV(OutDeg);
  return NId;
}

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.

                                                                                                             {
  CAssert(IsDir);
  if (NId == -1) { NId = MxNId;  MxNId.Val++; }
  else { MxNId = TMath::Mx(NId+1, MxNId()); }
  TNode& Node = NodeH.AddDat(NId);
  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
  Node.InVId = Pool.AddEmptyV(InDeg);
  Node.OutVId = Pool.AddEmptyV(OutDeg);
  Node.Dat = NodeDat;
  return NId;
}

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.

                                                                                         {
  CAssert(IsDir);
  IAssert(InNIdV.IsSorted() && OutNIdV.IsSorted());
  if (NId == -1) { NId = MxNId;  MxNId.Val++; }
  else { MxNId = TMath::Mx(NId+1, MxNId()); }
  TNode& Node = NodeH.AddDat(NId);
  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
  Node.InVId = Pool.AddV(InNIdV);
  Node.OutVId = Pool.AddV(OutNIdV);
  return NId;
}

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.

                                                                                                                   {
  CAssert(IsDir);
  IAssert(InNIdV.IsSorted() && OutNIdV.IsSorted());
  if (NId == -1) { NId = MxNId;  MxNId.Val++; }
  else { MxNId = TMath::Mx(NId+1, MxNId()); }
  TNode& Node = NodeH.AddDat(NId);
  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
  Node.InVId = Pool.AddV(InNIdV);
  Node.OutVId = Pool.AddV(OutNIdV);
  Node.Dat = NodeDat;
  return NId;
}

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.

                                                                            {
  // there is at least one free slot available for the Val
  IAssertR(*(End-1)==TInt::Mx, "Edge can not be added: no free space");
  // find position to insert
  int Half, Len = int(End-Beg);
  while (Len > 0) {
    Half = Len/2;
    int* Mid=Beg+Half;
    if (*Mid < Val) { Beg=Mid+1; Len=Len-Half-1; } else { Len=Half; } }
  IAssertR(*Beg != Val, "Value already existis");
  // insert
  memmove(Beg+1, Beg, sizeof(int)*(End-Beg-1));
  *Beg = Val;
}

template<class TNodeData , bool IsDir>

int TBigNet< TNodeData, IsDir >::AddUndirNode	(	int	NId,
		const int &	Deg
	)

Definition at line 345 of file bignet.h.

                                                                   {
  CAssert(! IsDir);
  if (NId == -1) { NId = MxNId;  MxNId.Val++; }
  else { MxNId = TMath::Mx(NId+1, MxNId()); }
  TNode& Node = NodeH.AddDat(NId);
  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
  Node.InVId = Pool.AddEmptyV(Deg);
  Node.OutVId = Node.InVId; // same vector
  return NId;
}

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.

                                                                                             {
  CAssert(! IsDir);
  if (NId == -1) { NId = MxNId;  MxNId.Val++; }
  else { MxNId = TMath::Mx(NId+1, MxNId()); }
  TNode& Node = NodeH.AddDat(NId);
  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
  Node.InVId = Pool.AddEmptyV(Deg);
  Node.OutVId = Node.InVId; // same vector
  Node.Dat = NodeDat;
  return NId;
}

template<class TNodeData , bool IsDir>

int TBigNet< TNodeData, IsDir >::AddUndirNode	(	int	NId,
		const TIntV &	EdgeNIdV
	)

Definition at line 397 of file bignet.h.

                                                                          {
  CAssert(! IsDir);
  IAssert(EdgeNIdV.IsSorted());
  if (NId == -1) { NId = MxNId;  MxNId.Val++; }
  else { MxNId = TMath::Mx(NId+1, MxNId()); }
  TNode& Node = NodeH.AddDat(NId);
  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
  Node.InVId = Pool.AddV(EdgeNIdV);
  Node.OutVId = Node.InVId;
  return NId;
}

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.

                                                                                                    {
  CAssert(! IsDir);
  IAssert(EdgeNIdV.IsSorted());
  if (NId == -1) { NId = MxNId;  MxNId.Val++; }
  else { MxNId = TMath::Mx(NId+1, MxNId()); }
  TNode& Node = NodeH.AddDat(NId);
  IAssertR(Node.IsUnused(), TStr::Fmt("NodeId %d already exists", NId));
  Node.InVId = Pool.AddV(EdgeNIdV);
  Node.OutVId = Node.InVId;
  Node.Dat = NodeDat;
  return NId;
}

template<class TNodeData, bool IsDir>

TEdgeI TBigNet< TNodeData, IsDir >::BegEI ( ) const

inline

Definition at line 173 of file bignet.h.

{ TNodeI NI=BegNI();  while(NI<EndNI() && NI.GetOutDeg()==0) NI++;  return TEdgeI(NI, EndNI()); }

template<class TNodeData, bool IsDir>

TNodeI TBigNet< TNodeData, IsDir >::BegNI ( ) const

inline

Definition at line 167 of file bignet.h.

{ return TNodeI(NodeH.BegI(), (TVPool *)&Pool); }

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.

                                                                                              {
  End--;  const int *Mid;
  while (Beg <= End) { Mid = Beg+(End-Beg)/2;
    if (*Mid == Val) { return Mid; }
    else if (Val < *Mid) { End=Mid-1; } else { Beg=Mid+1; }
  }
  return NULL;
}

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.

                                                                                               {
  const int* First = Beg;
  const int* Last = End;
  const int* Mid;
  TSize len = End-Beg, half;
  while (len > 0) {
    half = len>>1;  Mid=First+half;
    if (*Mid < Val) { First = Mid; First++; len=len-half-1; }
    else { len=half; }
  }
  return First==Last ? Last-1 : First;
}

template<class TNodeData, bool IsDir>

void TBigNet< TNodeData, IsDir >::Clr ( const bool &  DoDel = true )

inline

Definition at line 204 of file bignet.h.

{ MxNId = 0;  NodeH.Clr(DoDel); Pool.Clr(DoDel); }

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::CompactEdgePool

(

)

Definition at line 532 of file bignet.h.

                                                {
  Pool.CompactPool(DelNId);
}

template<class TNodeData, bool IsDir>

void TBigNet< TNodeData, IsDir >::Defrag ( const bool &  OnlyNodeLinks = false )

inline

Definition at line 206 of file bignet.h.

{ }

template<class TNodeData , bool IsDir>

int TBigNet< TNodeData, IsDir >::DelNode

(

int

NId

)

Definition at line 501 of file bignet.h.

                                               {
  const int DelEdges = IsolateNode(NId);
  NodeH.DelKey(NId);
  return DelEdges;
}

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::Dump

(

const TStr &

Desc = TStr()

)

const

Definition at line 1037 of file bignet.h.

                                                           {
  if (! Desc.Empty()) { printf("\n%s (%d, %u):\n", Desc.CStr(), GetNodes(), GetEdges()); }
  else { printf("\nNodes: %d,  Edges: %u\n", GetNodes(), GetEdges()); }
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
    printf("%d]\n  IN %d]", NI.GetId(), NI.GetInDeg());
    for (int i=0; i<NI.GetInDeg(); i++) { printf(" %d", NI.GetInNId(i)); }
    if (IsDir) {
      printf("\n  OUT %d]", NI.GetOutDeg());
      for (int i=0; i<NI.GetOutDeg(); i++) { printf(" %d", NI.GetOutNId(i)); }
    }
    printf("\n");
  }
}

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::DumpFlags

(

)

const

Definition at line 310 of file bignet.h.

                                                {
  for (int i = 1; i <int(gfMx); i++) {
    if (HasFlag(TGraphFlag(i))) { printf("  +"); }
    else { printf("  -"); }
    printf("%s", TSnap::GetFlagStr(TGraphFlag(i)).CStr());
  }
  printf("\n");
}

template<class TNodeData, bool IsDir>

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

inline

Definition at line 203 of file bignet.h.

{ return GetNodes()==0; }

template<class TNodeData, bool IsDir>

TEdgeI TBigNet< TNodeData, IsDir >::EndEI ( ) const

inline

Definition at line 174 of file bignet.h.

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

template<class TNodeData, bool IsDir>

TNodeI TBigNet< TNodeData, IsDir >::EndNI ( ) const

inline

Definition at line 168 of file bignet.h.

{ return TNodeI(NodeH.EndI(), (TVPool *)&Pool); }

template<class TNodeData , bool IsDir>

uint TBigNet< TNodeData, IsDir >::GetDelEdges

(

)

Definition at line 518 of file bignet.h.

                                            {
  uint DelEdges = 0;
  TIntV OutV;
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
    const int NId = NI.GetId();
    GetOutNIdV(NId, OutV);
    for (int i = 0; i < OutV.Len(); i++) {
      if (OutV[i] == DelNId) { DelEdges++; }
    }
  }
  return DelEdges;
}

template<class TNodeData, bool IsDir>

::TSize TBigNet< TNodeData, IsDir >::GetEdges ( ) const

inline

Definition at line 185 of file bignet.h.

{ return Pool.GetVals(); }

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.

                                                                      {
  TNode Node;  EAssertR(IsNode(NId, Node), TStr::Fmt("Not node: NId=%d\n", NId).CStr());
  Pool.GetV(Node.InVId, InNIdV);
}

template<class TNodeData, bool IsDir>

int* TBigNet< TNodeData, IsDir >::GetInNIdVPt ( const int &  NId ) const

inlineprotected

Definition at line 119 of file bignet.h.

{ return (int *) Pool.GetValVPt(GetNode(NId).InVId); }

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.

{ return MxNId; }

template<class TNodeData, bool IsDir>

TNodeDat& TBigNet< TNodeData, IsDir >::GetNDat ( const int &  NId )

inline

Definition at line 170 of file bignet.h.

{ return NodeH.GetDat(NId).Dat; }

template<class TNodeData, bool IsDir>

const TNodeDat& TBigNet< TNodeData, IsDir >::GetNDat ( const int &  NId ) const

inline

Definition at line 171 of file bignet.h.

{ return NodeH.GetDat(NId).Dat; }

template<class TNodeData , bool IsDir>

PNGraph TBigNet< TNodeData, IsDir >::GetNGraph

(

const bool &

RenumberNodes = false

)

const

Definition at line 766 of file bignet.h.

                                                                            {
  IAssert(RenumberNodes == false);
  PNGraph Graph = TNGraph::New();
  Graph->Reserve(GetNodes(), 0);
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
    Graph->AddNode(NI.GetId(), Pool, NI.GetInVId(), NI.GetOutVId());
  }
  return Graph;
}

template<class TNodeData, bool IsDir>

TNodeI TBigNet< TNodeData, IsDir >::GetNI ( const int &  NId ) const

inline

Definition at line 169 of file bignet.h.

{ return TNodeI(NodeH.GetI(NId), (TVPool *)&Pool); }

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::GetNIdV

(

TIntV &

NIdV

)

const

Definition at line 569 of file bignet.h.

                                                         {
  NIdV.Reserve(GetNodes(), 0);
  for (typename TNodeH::TIter I = NodeH.BegI(); I < NodeH.EndI(); I++) {
    NIdV.Add(I->Key); }
}

template<class TNodeData, bool IsDir>

const TNode& TBigNet< TNodeData, IsDir >::GetNode ( const int &  NId ) const

inlineprotected

Definition at line 124 of file bignet.h.

{ return NodeH.GetDat(NId); }

template<class TNodeData, bool IsDir>

TNode& TBigNet< TNodeData, IsDir >::GetNode ( const int &  NId )

inlineprotected

Definition at line 125 of file bignet.h.

{ return NodeH.GetDat(NId); }

template<class TNodeData, bool IsDir>

int TBigNet< TNodeData, IsDir >::GetNodes ( ) const

inline

Definition at line 151 of file bignet.h.

{ return NodeH.Len(); }

template<class TNodeData , bool IsDir>

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

Definition at line 446 of file bignet.h.

                                                                        {
  TNode Node;  EAssert(IsNode(NId, Node));
  Pool.GetV(Node.OutVId, OutNIdV);
}

template<class TNodeData, bool IsDir>

int* TBigNet< TNodeData, IsDir >::GetOutNIdVPt ( const int &  NId ) const

inlineprotected

Definition at line 120 of file bignet.h.

{ return (int *) Pool.GetValVPt(GetNode(NId).OutVId); }

template<class TNodeData, bool IsDir>

TNodeI TBigNet< TNodeData, IsDir >::GetRndNI ( TRnd &  Rnd = TInt::Rnd ) const

inline

Definition at line 200 of file bignet.h.

{ return GetNI(GetRndNId(Rnd)); }

template<class TNodeData, bool IsDir>

int TBigNet< TNodeData, IsDir >::GetRndNId ( TRnd &  Rnd = TInt::Rnd ) const

inline

Definition at line 199 of file bignet.h.

{ return NodeH.GetKey(NodeH.GetRndKeyId(Rnd)); }

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.

                                                                                                                         {
  const bool isDir = IsDir, onlySources = HasFlag(gfSources);
  TSize Edges=0;
  // find in- and out-degree
  TSparseHash<TInt, TIntPr> NIdDegH(NIdV.Len());
  for (int i = 0; i < NIdV.Len(); i++) { NIdDegH.AddDat(NIdV[i]); }
  for (int i = 0; i < NIdV.Len(); i++) {
    const TNodeI NI = GetNI(NIdV[i]);
    int InDeg=0, OutDeg=0;
    for (int n = 0; n < NI.GetOutDeg(); n++) {
      if (NIdDegH.IsKey(NI.GetOutNId(n))) OutDeg++; }
    if (! onlySources && isDir) {
      for (int n = 0; n < NI.GetInDeg(); n++) {
        if (NIdDegH.IsKey(NI.GetInNId(n))) InDeg++; }
    }
    Edges += OutDeg;
    NIdDegH.GetDat(NIdV[i]) = TIntPr(InDeg, OutDeg);
  }
  // make network
  typedef TBigNet<TNodeData, IsDir> TBNet;
  TPt<TBNet> NewNetPt = TBNet::New(NIdV.Len(), Edges, HasFlag(gfDirected));
  TBNet& NewNet = *NewNetPt;
  NewNet.Flags = Flags;
  // add nodes
  if (isDir || onlySources) {
    for (int i = 0; i < NIdV.Len(); i++) {
      const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
      NewNet.AddNode(NIdV[i], Deg.Val1, Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
  } else {
    for (int i = 0; i < NIdV.Len(); i++) {
      const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
      NewNet.AddUndirNode(NIdV[i], Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
  }
  // add edges
  for (int i = 0; i < NIdV.Len(); i++) {
    int NId = NIdV[i];
    const TNodeI NI = GetNI(NId);
    int *NIdVPt = (int *) NewNet.GetOutNIdVPt(NId);
    int deg = 0;
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      const int Dst = NI.GetOutNId(e);
      if (NewNet.IsNode(Dst)) {
        *NIdVPt = Dst;  NIdVPt++;  deg++; }
    }
    EAssert(deg == NIdDegH.GetDat(NId).Val2);
    if (isDir && ! onlySources) {
      EAssert((NI.GetInVId()==NI.GetOutVId() && NI.GetInVId()==0)
        || (NI.GetInVId() != NI.GetOutVId()));
      int * NIdVPt = (int *) NewNet.GetInNIdVPt(NId);
      int deg = 0;
      for (int e = 0; e < NI.GetInDeg(); e++) {
        const int Dst = NI.GetInNId(e);
        if (NewNet.IsNode(Dst)) {
          *NIdVPt = Dst;  NIdVPt++;  deg++; }
      }
      EAssert(deg == NIdDegH.GetDat(NId).Val1);
    }
  }
  return NewNetPt;
}

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.

                                                                                                                 {
  printf("Set subgraph on %d nodes\n", NIdV.Len()); TExeTm ExeTm;
  const bool isDir = IsDir, onlySources = HasFlag(gfSources);
  TSize Edges=0;
  // find in- and out-degree
  THash<TInt, TIntPr> NIdDegH(NIdV.Len());
  for (int i = 0; i < NIdV.Len(); i++) { NIdDegH.AddDat(NIdV[i]); }
  for (int i = 0; i < NIdV.Len(); i++) {
    const TNodeI NI = GetNI(NIdV[i]);
    int InDeg=0, OutDeg=0;
    for (int n = 0; n < NI.GetOutDeg(); n++) {
      if (NIdDegH.IsKey(NI.GetOutNId(n))) OutDeg++; }
    if (! onlySources && isDir) {
      for (int n = 0; n < NI.GetInDeg(); n++) {
        if (NIdDegH.IsKey(NI.GetInNId(n))) InDeg++; }
    }
    Edges += OutDeg;
    NIdDegH.GetDat(NIdV[i]) = TIntPr(InDeg, OutDeg);
  }
  // make network
  //typedef TBigNet<TNodeData, IsDir> TBNet;
  //TPt<TBNet> NewNetPt = TBNet::New(NIdV.Len(), Edges, HasFlag(gfDirected));
  NewNetPt->Reserve(NIdV.Len(), Edges);
  TBigNet<TNodeData, IsDir>& NewNet = *NewNetPt;
  NewNet.Flags = Flags;
  TIntSet NIdMap;
  // add nodes
  if (! RenumberNodes) {
    if (isDir || onlySources) {
      for (int i = 0; i < NIdV.Len(); i++) {
        const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
        NewNet.AddNode(NIdV[i], Deg.Val1, Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
    } else {
      for (int i = 0; i < NIdV.Len(); i++) {
        const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
        NewNet.AddUndirNode(NIdV[i], Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
    }
  } else { // renumber nodes
    NIdMap.Gen(NIdV.Len());
    for (int i = 0; i < NIdV.Len(); i++) { NIdMap.AddKey(NIdV[i]);  }
    if (isDir || onlySources) {
      for (int i = 0; i < NIdV.Len(); i++) {
        const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
        NewNet.AddNode(NIdMap.GetKeyId(NIdV[i]), Deg.Val1, Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
    } else {
      for (int i = 0; i < NIdV.Len(); i++) {
        const TIntPr& Deg = NIdDegH.GetDat(NIdV[i]);
        NewNet.AddUndirNode(NIdMap.GetKeyId(NIdV[i]), Deg.Val2, GetNDat(NIdV[i])); } // also copy the node data
    }
  }
  // add edges
  for (int i = 0; i < NIdV.Len(); i++) {
    int NId = NIdV[i];
    const TNodeI NI = GetNI(NId);
    int *NIdVPt = (int *) NewNet.GetOutNIdVPt(RenumberNodes?NIdMap.GetKeyId(NId):NId);
    int deg = 0;
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      const int Dst = RenumberNodes?NIdMap.GetKeyId(NI.GetOutNId(e)):NI.GetOutNId(e);
      if (NewNet.IsNode(Dst)) {
        *NIdVPt = Dst;  NIdVPt++;  deg++; }
    }
    EAssert(deg == NIdDegH.GetDat(NId).Val2);
    if (isDir && ! onlySources) {
      EAssert((NI.GetInVId()==NI.GetOutVId() && NI.GetInVId()==0)
        || (NI.GetInVId() != NI.GetOutVId()));
      int * NIdVPt = (int *) NewNet.GetInNIdVPt(RenumberNodes?NIdMap.GetKeyId(NId):NId);
      int deg = 0;
      for (int e = 0; e < NI.GetInDeg(); e++) {
        const int Dst = RenumberNodes?NIdMap.GetKeyId(NI.GetInNId(e)):NI.GetInNId(e);
        if (NewNet.IsNode(Dst)) {
          *NIdVPt = Dst;  NIdVPt++;  deg++; }
      }
      EAssert(deg == NIdDegH.GetDat(NId).Val1);
    }
  }
  printf("  %u edges [%s]\n", uint(Edges), ExeTm.GetStr());
}

template<class TNodeData , bool IsDir>

PNGraph TBigNet< TNodeData, IsDir >::GetSubNGraph

(

const TIntV &

NIdV

)

const

Definition at line 777 of file bignet.h.

                                                                       {
  PNGraph Graph = TNGraph::New(NIdV.Len(), 0);
  // add nodes
  for (int i = 0; i < NIdV.Len(); i++) {
    Graph->AddNode(NIdV[i]); }
  // reserve node in- and out-degree
  for (int i = 0; i < NIdV.Len(); i++) {
    const int SrcNId = NIdV[i];
    const TNodeI NI = GetNI(SrcNId);
    int InDeg=0, OutDeg=0;
    for (int e = 0; e < NI.GetInDeg(); e++) { if (Graph->IsNode(NI.GetInNId(e))) InDeg++; }
    for (int e = 0; e < NI.GetOutDeg(); e++) { if (Graph->IsNode(NI.GetOutNId(e))) OutDeg++; }
    Graph->ReserveNIdInDeg(SrcNId, InDeg);
    Graph->ReserveNIdOutDeg(SrcNId, OutDeg);
  }
  // add edges
  for (int i = 0; i < NIdV.Len(); i++) {
    const int SrcNId = NIdV[i];
    const TNodeI NI = GetNI(SrcNId);
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      const int DstNId = NI.GetOutNId(e);
      if (Graph->IsNode(DstNId)) {
        Graph->AddEdge(SrcNId, DstNId); }
    }
  }
  return Graph;
}

template<class TNodeData, bool IsDir>

bool TBigNet< TNodeData, IsDir >::HasFlag ( const TGraphFlag &  Flag ) const

inline

Definition at line 146 of file bignet.h.

                                             {
    return HasGraphFlag(typename TBigNet, Flag) || (Flag==gfSources && OnlySources()); }

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::InvertFromSources

(

uint

ExpectNodes = 0

)

Definition at line 604 of file bignet.h.

                                                                  {
  typedef THash<TInt, TInt> TDegHash;
  typedef int* TIntPt;
  if (ExpectNodes == 0) ExpectNodes=4*GetNodes();
  printf("\nInverting BigNet: reserved for %s nodes\n", TInt::GetMegaStr(ExpectNodes).CStr());
  CAssert(IsDir);
  IAssert(OnlySources());
  TDegHash InDegH(ExpectNodes);
  TSize NDest=0;
  // get node in-degree
  uint c=0;  TExeTm ExeTm;
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, c++) {
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      InDegH.AddDat(NI.GetOutNId(e)) += 1; }
    if (c%100000==0) printf("\r%s h:%d [%g]    ", TInt::GetMegaStr(c).CStr(), InDegH.Len(), ExeTm.GetSecs());
  }
  printf("\n Resizing NodePool: %lld -> %lld\n", uint64(Pool.Reserved()), uint64(GetEdges()));
  if (2*GetEdges() > Pool.Reserved()) {
    Pool.Reserve(2*GetEdges()); }
  // add nodes
  printf("NodeH: %s nodes, InDeg: %s nodes, Reserve: %s\n", TInt::GetMegaStr(NodeH.Len()).CStr(),
    TInt::GetMegaStr(InDegH.Len()).CStr(), TInt::GetMegaStr(ExpectNodes).CStr());
  NodeH.Reserve(ExpectNodes);
  for (TDegHash::TIter I = InDegH.BegI(); I < InDegH.EndI(); I++) {
    const int NId = I->Key, InDeg = I->Dat;
    if (! IsNode(NId)) {
      AddNode(NId, InDeg, 0); NDest++; } // new destination node, no out-links
    else {
      TNode& Node = GetNode(NId);
      IAssert(Node.InVId == 0); // no in-links
      Node.InVId = Pool.AddEmptyV(InDeg); }
  }
  InDegH.Clr(true);
  printf("Added: %lld destination nodes\n", uint64(NDest));
  printf("Graph nodes: %lld nodes\n", uint64(GetNodes()));
  // pointer to in-links vector
  THash<TInt, int*> NIdToPtH(GetNodes());
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, c++)
    NIdToPtH.AddDat(NI.GetId(), (int *)Pool.GetValVPt(NI.GetInVId()));
  // add in-edges
  printf("Adding edges...\n");
  c = 0;
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, c++) {
    const int SrcNId = NI.GetId();
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      TIntPt& InV = NIdToPtH.GetDat(NI.GetOutNId(e));
      IAssert(*InV == TInt::Mx);
      *InV = SrcNId;  InV++;
    }
    if (c%100000==0) printf("\r%s [%g]   ", TInt::GetMegaStr(c).CStr(), ExeTm.GetSecs());
  }
  // sort in-links
  printf("\nSorting in-links...\n");
  TIntV InNIdV;  c = 0;
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, c++) {
    Pool.GetV(NI.GetInVId(), InNIdV);
    InNIdV.Sort();
    if (c%100000==0) printf("\r%s [%g]    ", TInt::GetMegaStr(c).CStr(), ExeTm.GetSecs());
  }
  printf("\r...done [%g]\n", ExeTm.GetSecs());
  Flags.Excl(gfSources);
}

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.

                                                                                                  {
  TNode Src, Dst;
  if (! IsNode(SrcNId, Src)) { return false; } // no source node
  int* OutV1 = (int *)Pool.GetValVPt(Src.OutVId);
  const bool IsEdge = BinSearch(OutV1, OutV1+Pool.GetVLen(Src.OutVId), DstNId) != NULL;
  if (IsEdge && OnlySources()) { return true; }
  const bool IsDstNode = IsNode(DstNId, Dst);
  if (! IsDstNode) { return false; } // no destination node
  else if (IsEdge) { return true; } // destination and link found
  else if (! Dir) { // check for the undirected version of the edge
    int* OutV2 = (int *)Pool.GetValVPt(Dst.OutVId);
    return BinSearch(OutV2, OutV2+Pool.GetVLen(Dst.OutVId), SrcNId) != NULL; }
  else { return false; }
}

template<class TNodeData , bool IsDir>

bool TBigNet< TNodeData, IsDir >::IsIsoNode

(

const int &

NId

)

const

Definition at line 508 of file bignet.h.

                                                              {
  if (NId == DelNId) { return true; }
  TIntV OutV;
  GetOutNIdV(NId, OutV);
  if (OutV.Empty() || OutV[0] == DelNId) { return true; }
  return false;
}

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.

{ return NodeH.IsKeyGetDat(NId, Node); }

template<class TNodeData, bool IsDir>

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

inline

Definition at line 166 of file bignet.h.

{ return NodeH.IsKey(NId); }

template<class TNodeData , bool IsDir>

bool TBigNet< TNodeData, IsDir >::IsOk

(

)

const

Definition at line 954 of file bignet.h.

                                           {
  // check the node pool
  TIntV ValV; TExeTm ExeTm;
  printf("Is ok network:\n  Check Vec...");
  for (uint id = 1; id < Pool.GetVecs(); id++) {
    Pool.GetV(id, ValV);
    if (! ValV.Empty()) {
      EAssert((0<=ValV[0] && ValV[0]<MxNId) || ValV[0]==DelNId);
      try {
      for (int i = 1; i < ValV.Len(); i++) {
        //if (ValV[i]==DelNId) { continue; }
        // sorted & no duplicates & no empty values (can have deleted nodes)
        EAssertR((ValV[i-1]<ValV[i]) || (ValV[i-1]==ValV[i] && ValV[i]==DelNId),
          TStr::Fmt("NId1: %d NId2:%d", ValV[i-1](),ValV[i]()));
        EAssertR((0<=ValV[i] && ValV[i]<MxNId) || ValV[i]==DelNId,
          TStr::Fmt("NId1: %dm MxNId: %d", ValV[i](), MxNId));
        if (! OnlySources()) {
          EAssertR(IsNode(ValV[i]) || ValV[i]==DelNId,
            TStr::Fmt("NId1: %dm MxNId: %d", ValV[i](), MxNId)); } // every link is a node
      }
      } catch (PExcept Except){
        printf("  %s\n", Except->GetStr().CStr());
        printf("  vec id: %d, lenght: %d\n", id, ValV.Len());
        for (int i = 1; i < ValV.Len(); i++) {
          printf("  %d", ValV[i]());
          if (!((ValV[i-1]<ValV[i]) || (ValV[i-1]==ValV[i] && ValV[i]==DelNId))) { printf("*"); }
        }
        printf("\n");
        return false;
      }
    }
    if (id % 10000 == 0) {
      printf("\r  %dk / %dk [%s]", id/1000, Pool.GetVecs()/1000, ExeTm.GetStr()); }
  }
  printf("[%s]\n  Check Edges...\n", ExeTm.GetStr());
  // check edges
  int ErrCnt = 0;
  if (! OnlySources()) {
    int Cnt=0;
    for (TNodeI NI = BegNI(); NI < EndNI(); NI++, Cnt++) {
      // nodes that point to NI, have it on out-list
      for (int e = 0; e < NI.GetInDeg(); e++) {
        if (NI.GetInNId(e) == DelNId) { continue; } // skip deleted nodes
    if (! IsEdge(NI.GetInNId(e), NI.GetId())) {
      printf("\nno edge: %d --> %d", NI.GetInNId(e), NI.GetId());
      printf("NId: %d   deg %d,%d\n", NI.GetId(), NI.GetOutDeg(), NI.GetInDeg());
      for (int i = 0; i < NI.GetInDeg(); i++) { printf("  %d", NI.GetInNId(i)); }
      TNodeI NI2 = GetNI(NI.GetInNId(e));
      printf("\nNId2: %d   deg %d,%d\n", NI2.GetId(), NI2.GetOutDeg(), NI2.GetInDeg());
      for (int j = 0; j < NI2.GetOutDeg(); j++) { printf("  %d", NI2.GetOutNId(j)); }
      printf("\n");
      ErrCnt++;
    }
        //EAssertR(IsEdge(NI.GetInNId(e), NI.GetId()),
        //  TStr::Fmt("no edge: %d --> %d", NI.GetInNId(e), NI.GetId()));
    }
      // nodes NI points to, have it on in-list
      for (int e = 0; e < NI.GetOutDeg(); e++) {
        if (NI.GetOutNId(e) == DelNId) { continue; }
        const int InVId = GetNode(NI.GetOutNId(e)).InVId;
        int* DstInV = (int *)Pool.GetValVPt(InVId);
    if (BinSearch(DstInV, DstInV+Pool.GetVLen(InVId), NI.GetId()) == NULL) {
      printf("no edge: %d --> %d", NI.GetId(), NI.GetInNId(e));
      printf("NId: %d   deg %d,%d\n", NI.GetId(), NI.GetOutDeg(), NI.GetInDeg());
      for (int i = 0; i < NI.GetOutDeg(); i++) { printf("  %d", NI.GetOutNId(i)); }
      TNodeI NI2 = GetNI(NI.GetOutNId(e));
      printf("\nNId2: %d   deg %d,%d\n", NI2.GetId(), NI2.GetOutDeg(), NI2.GetInDeg());
      for (int j = 0; j < NI2.GetInDeg(); j++) { printf("  %d", NI2.GetInNId(j)); }
      printf("\n");  ErrCnt++;
    }
        //EAssertR(BinSearch(DstInV, DstInV+Pool.GetVLen(InVId), NI.GetId()) != NULL,
        //  TStr::Fmt("no edge: %d --> %d", NI.GetId(), NI.GetInNId(e)));
    }
    if (ErrCnt > 5) { FailR("error count too large!"); }
      if (Cnt % 100000 == 0) {
        printf("\r%s [%s]", TInt::GetMegaStr(Cnt).CStr(), ExeTm.GetStr()); }
    }
    printf("\r%s [%s]\n", TInt::GetMegaStr(Cnt).CStr(), ExeTm.GetStr());
  }
  return true;
}

template<class TNodeData , bool IsDir>

int TBigNet< TNodeData, IsDir >::IsolateNode

(

int

NId

)

Definition at line 454 of file bignet.h.

                                                   {
  TIntV OutV;
  int NDel = 0;
  // out-edges
  GetOutNIdV(NId, OutV);
  for (int i = 0; i < OutV.Len(); i++) {
    if (OutV[i] == DelNId) { break; } // because they are sorted
    // fast implementation
    const TNode& N = NodeH.GetDat(OutV[i]);
    int *InNIdV = (int *) Pool.GetValVPt(N.InVId);
    const int Deg = Pool.GetVLen(N.InVId);
    int* Val = (int *) BinSearch(InNIdV, InNIdV+Deg, NId);
    if (Val == NULL) {
      printf("BAD: Can't find: OUT: NId: %d -- OutNbrId: %d\n", NId, OutV[i]());
      continue;
    }
    IAssert(Val != 0);
    memcpy(Val, Val+1, sizeof(int)*int(InNIdV+Deg-Val));
    *(InNIdV+Deg-1) = DelNId;  NDel++;
  }
  OutV.PutAll(DelNId);
  // in-edges
  if (IsDir) {
    TIntV InV;
    GetInNIdV(NId, InV);
    for (int i = 0; i < InV.Len(); i++) {
      if (InV[i] == DelNId) { break; }
      // fast implementation
      const TNode& N = NodeH.GetDat(InV[i]);
      int *OutNIdV = (int *) Pool.GetValVPt(N.OutVId);
      const int Deg = Pool.GetVLen(N.OutVId);
      int* Val = (int *) BinSearch(OutNIdV, OutNIdV+Deg, NId);
      if (Val == NULL) {
        printf("IN: NId: %d -- InNbrId: %d\n", NId, OutV[i]());
        continue;
      }
      IAssert(Val != 0);
      memcpy(Val, Val+1, sizeof(int)*int(OutNIdV+Deg-Val));
      *(OutNIdV+Deg-1) = DelNId;  NDel++;
    }
    InV.PutAll(DelNId);
  }
  return NDel;
}

template<class TNodeData, bool IsDir>

static PBigNet TBigNet< TNodeData, IsDir >::Load ( TSIn &  SIn )

inlinestatic

Definition at line 141 of file bignet.h.

{ return PBigNet(new TBigNet(SIn)); }

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::LoadNodeDatH ( const TStr &  InFNm, TNodeH &  NodeH  )

static

Definition at line 1077 of file bignet.h.

                                                                             {
  TFIn SIn(InFNm);
  TInt MxNId(SIn);
  TB32Set Flags(SIn);
  printf("skipping Pool...\n");
  TBool FastCopy(SIn);
  uint64 _GrowBy, _MxVals, _Vals;
  SIn.Load(_GrowBy); SIn.Load(_MxVals);  SIn.Load(_Vals);
  TInt EmptyVal(SIn);
  int Tmp;
  for (TSize ValN = 0; ValN < _Vals; ValN++) { SIn.Load(Tmp); }
  TInt MxVals(SIn), Vals(SIn);
  uint64 Offset;
  for (int ValN = 0; ValN < Vals; ValN++) { SIn.Load(Offset); }
  printf("loading Hode hash table...\n");
  NodeH.Load(SIn);
}

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.

                                                                                      {
    return PBigNet(new TBigNet(Nodes, Edges, Sources)); }

template<class TNodeData, bool IsDir>

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

inline

Definition at line 145 of file bignet.h.

{ return Flags.In(gfSources); }

template<class TNodeData, bool IsDir>

TBigNet& TBigNet< TNodeData, IsDir >::operator= ( const TBigNet< TNodeData, IsDir > &  Net )

inline

Definition at line 142 of file bignet.h.

                                           { if (this!=&Net) {
    MxNId=Net.MxNId; Flags=Net.Flags; Pool=Net.Pool; NodeH=Net.NodeH; }  return *this; }

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::Reserve	(	const int &	Nodes,
		const TSize &	Edges
	)

Definition at line 947 of file bignet.h.

                                                                            {
  NodeH.Gen(TMath::Mx(int(1.1*Nodes), 100));
  Pool = TVPool(TMath::Mx(Edges, (TSize) Mega(1)), Mega(100), true);
}

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::Rewire

(

TRnd &

Rnd = TInt::Rnd

)

Definition at line 668 of file bignet.h.

                                                {
  uint64 NDup=0, NResolve=0, NAddit=0, cnt = 0;
  TExeTm ExeTm;
  IAssertR(! IsDir, "Only undirected networks are supported");
  printf("Rewiring the network... 1");
  Pool.ShuffleAll(Rnd);  printf("[%s]\n", ExeTm.GetStr());
  //Pool.ShuffleAll(Rnd);  printf(" done [%s]\n", ExeTm.GetStr());
  printf("  sorting edges...\n");
  SortEdgeV(); // sort individual edge vectors
  printf(" done [%s]\n", ExeTm.GetStr());
  // remove duplicates and self edges
  printf("  removing duplicates...\n");
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, cnt++) {
    const int VId = NI.GetOutVId();
    int Len = Pool.GetVLen(VId);
    int* V = (int *)Pool.GetValVPt(VId);
    for (int i = 0; i < Len-1 && V[i]!=DelNId; i++) {
      if (V[i] == V[i+1] || V[i]==NI.GetId()) {
        memcpy(V+i, V+i+1, sizeof(int)*(Len-i-1)); i--;
        V[Len-1] = DelNId;  NDup++;
      }
    }
    if (Len > 0 && V[Len-1]==NI.GetId()) { V[Len-1] = DelNId;  NDup++; }
    if (cnt % Mega(10) == 0) { printf(".");  fflush(stdout); }
  }
  printf("\n    %llu duplicate edges removed [%s]\n", NDup, ExeTm.GetStr());
  if (OnlySources()) { return; }
  // resolve one way edges
  printf("  resolving one way edges...\n"); cnt=0; fflush(stdout);
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++, cnt++) {
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      if (NI.GetOutNId(e) == DelNId) { continue; } // skip deleted nodes
      const int InVId = GetNode(NI.GetOutNId(e)).InVId;
      const int InVLen = Pool.GetVLen(InVId); IAssert(InVLen>=0 && InVLen < Mega(3));
      int* InV = (int *) Pool.GetValVPt(InVId);
      int* Val = (int *) BinSearch2(InV, InV+InVLen, NI.GetId());
      if (*Val == NI.GetId()) { continue; } // points back, everything is ok
      if (InVLen>0 && InV[InVLen-1] == DelNId) { // there is space at the end, insert
        IAssert((InVLen-(Val-InV)-1) >= 0);
        memmove(Val+1, Val, sizeof(int)*(InVLen-(Val-InV)-1));
        *Val = NI.GetId();
      } else { // the other end could point at us but it doesn't
        memmove(NI.OutNIdV+e, NI.OutNIdV+e+1, sizeof(int)*(NI.GetOutDeg()-e-1));
        NI.OutNIdV[NI.GetOutDeg()-1]=DelNId;  e--;
      }
      NResolve++;
    }
    if (cnt % Mega(10) == 0) { printf(".");  fflush(stdout); }
  }
  printf("\n    %llu resolved edges [%s]\n", NResolve, ExeTm.GetStr());
  // check if there are two nodes that still have space and are not yet connected and connect them
  printf("  filling empty edge slots...\n");
  TIntPrV SlotNIdV;
  THash<TInt, TInt> SlotNIdH;
  int CumSlots=0;
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
    if (NI.GetOutNId(NI.GetOutDeg()-1) == DelNId) {
      int NSlots = 0;
      for (int s = NI.GetOutDeg()-1; s >= 0; s--) {
        if (NI.GetOutNId(s) == DelNId) { NSlots++; }
        else { break; }
      }
      SlotNIdV.Add(TIntPr(NI.GetId(), NSlots));
      SlotNIdH.AddDat(NI.GetId(), NSlots);
      CumSlots+=NSlots;
    }
  }
  printf("    %d nodes, with %d spokes available, %d edges\n", SlotNIdH.Len(), CumSlots, CumSlots/2);
  TIntV NIdV;  SlotNIdH.GetKeyV(NIdV);
  for (int ni1 = 0; ni1 < NIdV.Len(); ni1++) {
    const int nid = NIdV[ni1];
    if (! SlotNIdH.IsKey(nid) || SlotNIdH.GetDat(nid) == 0) { continue; }
    const int NI1Slots = SlotNIdH.GetDat(nid);
    if ((SlotNIdH.GetMxKeyIds() - SlotNIdH.Len())/double(SlotNIdH.GetMxKeyIds()) > 0.5) { SlotNIdH.Defrag(); }
    TNodeI NI  = GetNI(nid);
    for (int NTries = 0; NTries < 4*NI1Slots && NI.GetOutNId(NI.GetOutDeg()-1) == DelNId; NTries++) {
      const int nid2 = SlotNIdH.GetKey(SlotNIdH.GetRndKeyId(Rnd));
      if (nid == nid2) { continue; }
      TNodeI NI2  = GetNI(nid2);
      // insert the edge
      if (NI2.GetOutNId(NI2.GetOutDeg()-1)==DelNId && ! NI2.IsInNId(NI.GetId())) {
        int *V1 = (int *) BinSearch2(NI.OutNIdV, NI.OutNIdV+NI.GetOutDeg(), NI2.GetId());
        int *V2 = (int *) BinSearch2(NI2.InNIdV, NI2.InNIdV+NI2.GetInDeg(), NI.GetId());
        if (*V1 != DelNId) { memmove(V1+1, V1, sizeof(int)*(NI.GetOutDeg()-(V1-NI.OutNIdV)-1)); }
        if (*V2 != DelNId) { memmove(V2+1, V2, sizeof(int)*(NI2.GetInDeg()-(V2-NI2.InNIdV)-1)); }
        *V1 = NI2.GetId();  *V2 = NI.GetId();
        NAddit++;
        SlotNIdH.GetDat(nid)--;  SlotNIdH.GetDat(nid2)--;
      }
      if (SlotNIdH.GetDat(nid2) == 0) { SlotNIdH.DelKey(nid2); continue; }
      if (SlotNIdH.GetDat(nid) == 0) { SlotNIdH.DelKey(nid); break; }
    }
    if (ni1 % Mega(1) == 0) { printf(".");  fflush(stdout); }
  }
  printf("    %llu edges added.\nDONE. TOTAL REWIRE TIME [%s]\n\n", NAddit, ExeTm.GetStr());
}

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::Save ( TSOut &  SOut ) const

virtual

Definition at line 301 of file bignet.h.

                                                      {
  MxNId.Save(SOut);
  Flags.Save(SOut);
  Pool.Save(SOut);
  NodeH.Save(SOut);
  TBool(IsDir).Save(SOut);
}

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::SaveForDisk

(

const TStr &

OutFNm

)

const

Definition at line 1055 of file bignet.h.

                                                                    {
  const bool IsDirected = IsDir;
  TFOut FOut(OutFNm);
  FOut.Save(GetNodes());
  FOut.Save(GetEdges());
  FOut.Save(IsDirected);
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
    FOut.Save(NI.GetId());
    NI.GetDat().Save(FOut);
    FOut.Save(NI.GetOutDeg());
    for (int i = 0; i < NI.GetOutDeg(); i++) {
      FOut.Save(NI.GetOutNId(i)); }
    if (IsDirected) {
      FOut.Save(NI.GetInDeg());
      for (int i = 0; i < NI.GetInDeg(); i++) {
        FOut.Save(NI.GetInNId(i)); }
    }
  }
}

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.

                                                                                                            {
  TFIn FIn(InFNm);
  TFOut FOut(OutFNm);
  { TInt MxNId(FIn);  MxNId.Save(FOut);
  TB32Set Flags(FIn);  Flags.Save(FOut);
  TVPool Pool(FIn);  Pool.Save(FOut); }
  { TNodeH NodeH(FIn);
  if (! SaveSparseHash) {
    THash<TInt, TNode> NewH(NodeH.Len(), true);
    for (typename TNodeH::TIter I = NodeH.BegI(); I < NodeH.EndI(); I++) {
      NewH.AddDat(I->Key, I->Dat);
    }
    NewH.Save(FOut);
  } else {
    FailR("Not implemented");
  } }
}

template<class TNodeData , bool IsDir>

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

Definition at line 424 of file bignet.h.

                                                                      {
  TNode Node;  EAssert(IsNode(NId, Node));
  TIntV InNodesV;  Pool.GetV(Node.InVId, InNodesV);
  EAssert(InNIdV.Len() == InNodesV.Len());
  memcpy(InNodesV.BegI(), InNIdV.BegI(), sizeof(TInt)*InNIdV.Len());
}

template<class TNodeData , bool IsDir>

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

Definition at line 432 of file bignet.h.

                                                                        {
  TNode Node;  EAssert(IsNode(NId, Node));
  TIntV OutNodesV;  Pool.GetV(Node.OutVId, OutNodesV);
  EAssert(OutNIdV.Len() == OutNodesV.Len());
  memcpy(OutNodesV.BegI(), OutNIdV.BegI(), sizeof(TInt)*OutNIdV.Len());
}

template<class TNodeData , bool IsDir>

void TBigNet< TNodeData, IsDir >::SortEdgeV

(

)

Definition at line 576 of file bignet.h.

                                          {
  printf("Sorting Edges... ");
  TExeTm ExeTm;
  TIntV OutV, InV;
  int cnt = 0;
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
    const int NId = NI.GetId();
    GetOutNIdV(NId, OutV);
    OutV.Sort();
    if (IsDir) {
      GetInNIdV(NId, InV);
      InV.Sort();
    }
    if (++cnt % Mega(1) == 0) { printf("\r  sort:%dm  %s", cnt/Mega(1), ExeTm.GetStr()); }
  }
  for (TNodeI NI = BegNI(); NI < EndNI(); NI++) {
    const int NId = NI.GetId();
    GetOutNIdV(NId, OutV);
    IAssert(OutV.IsSorted());
    GetInNIdV(NId, InV);
    IAssert(InV.IsSorted());
    if (++cnt % Mega(1) == 0) { printf("\r  check sorted:%dm  %s", cnt/Mega(1), ExeTm.GetStr()); }
  }
  printf("done. [%s]\n", ExeTm.GetStr());
}

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:

• snap-core/bignet.h