SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
bignet.h
Go to the documentation of this file.
1 //#//////////////////////////////////////////////
3 
10 template <class TNodeData, bool IsDir>
11 class TBigNet {
12 public:
13  typedef TNodeData TNodeDat;
14  typedef TBigNet<TNodeData, IsDir> TNet;
15  typedef TPt<TNet> PNet;
16 public:
17  class TNode;
18  typedef THash<TInt, TNode> TNodeH; // use SaveToDisk to convert between the two hash table types
19  typedef TPt<TBigNet<TNodeData, IsDir> > PBigNet;
20  typedef TVecPool<TInt> TVPool;
21  typedef TPt<TVPool> PVPool;
22 
24 
26  class TNode {
27  public:
29  TInt InVId;
31 
33  TInt OutVId;
35  TNodeDat Dat;
36  public:
37  TNode() : InVId(-1), OutVId(-1), Dat() { }
38  TNode(const int& InVecId, const int& OutVecId) : InVId(InVecId), OutVId(OutVecId), Dat() { }
39  TNode(const int& InVecId, const int& OutVecId, const TNodeDat& NodeDat) :
40  InVId(InVecId), OutVId(OutVecId), Dat(NodeDat) { }
41  TNode(const TNode& Node) : InVId(Node.InVId), OutVId(Node.OutVId), Dat(Node.Dat) { }
42  TNode(TSIn& SIn) : InVId(SIn), OutVId(SIn), Dat(SIn) { }
43  void Save(TSOut& SOut) const { SOut.Save(InVId); SOut.Save(OutVId); Dat.Save(SOut); }
45  bool IsUnused() const { return InVId==-1 && OutVId==-1; }
46  };
48 
50  class TNodeI {
51  protected:
52  typedef typename TNodeH::TIter THashIter;
53  THashIter NodeHI;
54  TVPool *Pool;
55  int InDeg, OutDeg, *InNIdV, *OutNIdV; // if undirected, InNIdV==OutNIdV
56  public:
57  inline void GetInOutNIdV();
58  int GetInVId() const { return NodeHI->Dat.InVId; }
59  int GetOutVId() const { return NodeHI->Dat.OutVId; }
60  public:
61  TNodeI() : NodeHI(), Pool(NULL), InDeg(0), OutDeg(0), InNIdV(NULL), OutNIdV(NULL) { }
62  TNodeI(const THashIter& NodeHIter, TVPool *PoolPt) : NodeHI(NodeHIter), Pool(PoolPt) { GetInOutNIdV(); }
63  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Pool(NodeI.Pool) { GetInOutNIdV(); }
64  TNodeI& operator = (const TNodeI& NI) { NodeHI=NI.NodeHI; Pool=NI.Pool; GetInOutNIdV(); return *this; }
66  TNodeI& operator++ (int) { NodeHI++; GetInOutNIdV(); return *this; }
67  bool operator < (const TNodeI& NI) const { return NodeHI < NI.NodeHI; }
68  bool operator == (const TNodeI& NI) const { return NodeHI == NI.NodeHI; }
69  int GetId() const { return NodeHI->Key(); }
70  int GetDeg() const { return GetInDeg()+(InNIdV!=OutNIdV?GetOutDeg():0); }
71  int GetInDeg() const { return InDeg; }
72  int GetOutDeg() const { return OutDeg; }
73  int GetInNId(const int& NodeN) const { return InNIdV[NodeN]; }
74  int GetOutNId(const int& NodeN) const { return OutNIdV[NodeN]; }
75  int GetOutNbrId(const int& NodeN) const { return NodeN<OutDeg ? OutNIdV[NodeN]:InNIdV[NodeN-OutDeg]; }
76  bool IsInNId(const int& NId) const { return BinSearch(InNIdV, InNIdV+InDeg, NId)!=NULL; }
77  bool IsOutNId(const int& NId) const { return BinSearch(OutNIdV, OutNIdV+OutDeg, NId)!=NULL; }
78  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
79  const TNodeData& operator () () const { return GetDat(); }
80  TNodeData& operator () () { return GetDat(); }
81  const TNodeData& GetDat() const { return NodeHI->Dat.Dat; }
82  TNodeData& GetDat() { return NodeHI->Dat.Dat; }
83  // requires pointer back to the network (see as in TNodeNet)
84  //const TNodeData& GetInNDat(const int& NodeN) const { return Net->GetNDat(GetInNId(NodeN)); }
85  //TNodeData& GetInNDat(const int& NodeN) { return Net->GetNDat(GetInNId(NodeN)); }
86  //const TNodeData& GetOutNDat(const int& NodeN) const { return Net->GetNDat(GetOutNId(NodeN)); }
87  //TNodeData& GetOutNDat(const int& NodeN) { return Net->GetNDat(GetOutNId(NodeN)); }
88  //const TNodeData& GetNbrNDat(const int& NodeN) const { return Net->GetNDat(GetNbrNId(NodeN)); }
89  //TNodeData& GetNbrNDat(const int& NodeN) { return Net->GetNDat(GetNbrNId(NodeN)); }
90  void Dump() const;
91  friend class TBigNet<TNodeData, IsDir>;
92  };
93 
95 
97  class TEdgeI {
98  private:
99  TNodeI CurNode, EndNode;
100  int CurEdge;
101  public:
102  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
103  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(0) { }
104  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
105  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
106  TEdgeI& operator++ (int) { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++;
107  while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; }
108  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
109  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
110  int GetId() const { return -1; }
111  int GetSrcNId() const { return CurNode.GetId(); }
112  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
113  const TNodeData& GetSrcNDat() const { return CurNode.GetNDat(); }
114  TNodeData& GetDstNDat() { return CurNode.GetOutNDat(CurEdge); }
115  friend class TNodeNet<TNodeData>;
116  };
117 protected:
118  bool IsNode(const int& NId, TNode& Node) const { return NodeH.IsKeyGetDat(NId, Node); }
119  int* GetInNIdVPt(const int& NId) const { return (int *) Pool.GetValVPt(GetNode(NId).InVId); }
120  int* GetOutNIdVPt(const int& NId) const { return (int *) Pool.GetValVPt(GetNode(NId).OutVId); }
121  static void AddSorted(int* Beg, int* End, const int& Val);
122  static const int* BinSearch(const int* Beg, const int* End, const int& Val);
123  static const int* BinSearch2(const int* Beg, const int* End, const int& Val);
124  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
125  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
126 public:
127  enum { DelNId = INT_MAX }; // id of a deleted node
128 protected:
129  TCRef CRef;
130  TInt MxNId;
131  TB32Set Flags;
132  TVPool Pool;
133  TNodeH NodeH;
134 public:
135  TBigNet(const int& Nodes, const TSize& Edges, const bool& Sources=false);
136  TBigNet(TSIn& SIn) : MxNId(SIn), Flags(SIn), Pool(SIn), NodeH(SIn) { TBool Dir(SIn); IAssert(Dir()==IsDir); }
137  virtual ~TBigNet() { }
138  virtual void Save(TSOut& SOut) const;
139  static PBigNet New(const int& Nodes, const TSize& Edges, const bool& Sources=false) {
140  return PBigNet(new TBigNet(Nodes, Edges, Sources)); }
141  static PBigNet Load(TSIn& SIn) { return PBigNet(new TBigNet(SIn)); }
142  TBigNet& operator = (const TBigNet& Net) { if (this!=&Net) {
143  MxNId=Net.MxNId; Flags=Net.Flags; Pool=Net.Pool; NodeH=Net.NodeH; } return *this; }
144 
145  bool OnlySources() const { return Flags.In(gfSources); }
146  bool HasFlag(const TGraphFlag& Flag) const {
147  return HasGraphFlag(typename TBigNet, Flag) || (Flag==gfSources && OnlySources()); }
148  void DumpFlags() const;
149 
150  // vertices
151  int GetNodes() const { return NodeH.Len(); }
153  int GetMxNId() const { return MxNId; }
154  int AddNode(int NId, const int& InDeg, const int& OutDeg);
155  int AddNode(int NId, const int& InDeg, const int& OutDeg, const TNodeDat& NodeDat);
156  int AddNode(int NId, const TIntV& InNIdV, const TIntV& OutNIdV);
157  int AddNode(int NId, const TIntV& InNIdV, const TIntV& OutNIdV, const TNodeDat& NodeDat);
158  int AddUndirNode(int NId, const int& Deg);
159  int AddUndirNode(int NId, const int& Deg, const TNodeDat& NodeDat);
160  int AddUndirNode(int NId, const TIntV& EdgeNIdV);
161  int AddUndirNode(int NId, const TIntV& EdgeNIdV, const TNodeDat& NodeDat);
162  void SetInNIdV(int NId, const TIntV& InNIdV);
163  void SetOutNIdV(int NId, const TIntV& OutNIdV);
164  void GetInNIdV(int NId, TIntV& OutNIdV) const;
165  void GetOutNIdV(int NId, TIntV& OutNIdV) const;
166  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
167  TNodeI BegNI() const { return TNodeI(NodeH.BegI(), (TVPool *)&Pool); }
168  TNodeI EndNI() const { return TNodeI(NodeH.EndI(), (TVPool *)&Pool); }
169  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), (TVPool *)&Pool); }
170  TNodeDat& GetNDat(const int& NId) { return NodeH.GetDat(NId).Dat; }
171  const TNodeDat& GetNDat(const int& NId) const { return NodeH.GetDat(NId).Dat; }
172  // edges
173  TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0) NI++; return TEdgeI(NI, EndNI()); }
174  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
175  TEdgeI GetEI(const int& EId) const; // not supported
176 
177  // delete nodes
178  int IsolateNode(int NId); // isolate the node by setting edge endpoints to point to node id DelNId, IsNode(DelNId)==false)
179  int DelNode(int NId); // set neighbors to point to DelNId, delete node from the node table
180  bool IsIsoNode(const int& NId) const;
181  uint GetDelEdges(); // the number deleted edges
182  void CompactEdgePool(); // after nodes are isolated and deleted, we compact the empty space
183 
184  // edges
185  ::TSize GetEdges() const { return Pool.GetVals(); }
186  int AddEdge(const int& SrcNId, const int& DstNId);
187  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& Dir=true) const;
188 
189  void SortEdgeV();
190  void InvertFromSources(uint ExpectNodes=0); // add missing nodes and in-links
191  void Rewire(TRnd& Rnd = TInt::Rnd); // create a random network with same degree distribution (configuration model)
192 
193  // manipulation
194  PNGraph GetNGraph(const bool& RenumberNodes=false) const;
195  PNGraph GetSubNGraph(const TIntV& NIdV) const;
196  PBigNet GetSubGraph(const TIntV& NIdV, const bool& RenumberNodes=false) const;
197  void GetSubGraph(const TIntV& NIdV, TBigNet* NewNet, const bool& RenumberNodes=false) const;
198 
199  int GetRndNId(TRnd& Rnd=TInt::Rnd) const { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd)); }
200  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) const { return GetNI(GetRndNId(Rnd)); }
201  void GetNIdV(TIntV& NIdV) const;
202 
203  bool Empty() const { return GetNodes()==0; }
204  void Clr(const bool& DoDel = true) { MxNId = 0; NodeH.Clr(DoDel); Pool.Clr(DoDel); }
205  void Reserve(const int& Nodes, const TSize& Edges);
206  void Defrag(const bool& OnlyNodeLinks = false) { }
207  bool IsOk() const;
208  void Dump(const TStr& Desc = TStr()) const;
209  void SaveForDisk(const TStr& OutFNm) const;
210 
211  static void LoadNodeDatH(const TStr& InFNm, TNodeH& NodeH);
212  static void SaveToDisk(const TStr& InFNm, const TStr& OutFNm, const bool& SaveSparseHash);
213  friend class TPt<TBigNet>;
214 };
215 
216 // set flags
217 namespace TSnap {
218 template <class TNodeData, bool IsDir> struct IsDirected<TBigNet<TNodeData, IsDir> > { enum { Val = 0 }; };
219 template <class TNodeData> struct IsDirected<TBigNet<TNodeData, true> > { enum { Val = 1 }; };
220 template <class TNodeData, bool IsDir> struct IsNodeDat<TBigNet<TNodeData, IsDir> > { enum { Val = 1 }; };
221 }
222 
223 template <class TNodeData, bool IsDir>
224 inline void TBigNet<TNodeData, IsDir>::TNodeI::GetInOutNIdV() {
225  if (NodeHI.IsEnd()) return;
226  const TNode& N = NodeHI->Dat;
227  if (! Pool->IsVId(N.InVId)) {
228  InDeg=0; OutDeg=0; }
229  else {
230  InDeg=Pool->GetVLen(N.InVId);
231  OutDeg=Pool->GetVLen(N.OutVId);
232  InNIdV=(int *)Pool->GetValVPt(N.InVId);
233  OutNIdV=(int *)Pool->GetValVPt(N.OutVId);
234  }
235 }
236 
237 template <class TNodeData, bool IsDir>
238 void TBigNet<TNodeData, IsDir>::TNodeI::Dump() const {
239  printf("NodeId: %d\n", GetId());
240  printf(" I:%4d]", GetInDeg());
241  for (int i = 0; i < GetInDeg(); i++) { printf(" %d", GetInNId(i)); }
242  printf("\n O:%4d]", GetOutDeg());
243  for (int i = 0; i < GetOutDeg(); i++) { printf(" %d", GetOutNId(i)); }
244  printf("\n");
245 }
246 
247 template <class TNodeData, bool IsDir>
248 void TBigNet<TNodeData, IsDir>::AddSorted(int* Beg, int* End, const int& Val) {
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 }
262 
263 template <class TNodeData, bool IsDir>
264 const int* TBigNet<TNodeData, IsDir>::BinSearch(const int* Beg, const int* End, const int& Val) {
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 }
272 
273 template <class TNodeData, bool IsDir>
274 const int* TBigNet<TNodeData, IsDir>::BinSearch2(const int* Beg, const int* End, const int& Val) {
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 }
286 
287 template <class TNodeData, bool IsDir>
288 TBigNet<TNodeData, IsDir>::TBigNet(const int& Nodes, const TSize& Edges, const bool& Sources) :
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 }
299 
300 template <class TNodeData, bool IsDir>
301 void TBigNet<TNodeData, IsDir>::Save(TSOut& SOut) const {
302  MxNId.Save(SOut);
303  Flags.Save(SOut);
304  Pool.Save(SOut);
305  NodeH.Save(SOut);
306  TBool(IsDir).Save(SOut);
307 }
308 
309 template <class TNodeData, bool IsDir>
310 void TBigNet<TNodeData, IsDir>::DumpFlags() const {
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 }
318 
319 template <class TNodeData, bool IsDir>
320 int TBigNet<TNodeData, IsDir>::AddNode(int NId, const int& InDeg, const int& OutDeg) {
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 }
330 
331 template <class TNodeData, bool IsDir>
332 int TBigNet<TNodeData, IsDir>::AddNode(int NId, const int& InDeg, const int& OutDeg, const TNodeData& NodeDat) {
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 }
343 
344 template <class TNodeData, bool IsDir>
345 int TBigNet<TNodeData, IsDir>::AddUndirNode(int NId, const int& Deg) {
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 }
355 
356 template <class TNodeData, bool IsDir>
357 int TBigNet<TNodeData, IsDir>::AddUndirNode(int NId, const int& Deg, const TNodeData& NodeDat) {
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 }
368 
369 template <class TNodeData, bool IsDir>
370 int TBigNet<TNodeData, IsDir>::AddNode(int NId, const TIntV& InNIdV, const TIntV& OutNIdV) {
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 }
381 
382 template <class TNodeData, bool IsDir>
383 int TBigNet<TNodeData, IsDir>::AddNode(int NId, const TIntV& InNIdV, const TIntV& OutNIdV, const TNodeData& NodeDat) {
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 }
395 
396 template <class TNodeData, bool IsDir>
397 int TBigNet<TNodeData, IsDir>::AddUndirNode(int NId, const TIntV& EdgeNIdV) {
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 }
408 
409 template <class TNodeData, bool IsDir>
410 int TBigNet<TNodeData, IsDir>::AddUndirNode(int NId, const TIntV& EdgeNIdV, const TNodeData& NodeDat) {
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 }
422 
423 template <class TNodeData, bool IsDir>
424 void TBigNet<TNodeData, IsDir>::SetInNIdV(int NId, const TIntV& InNIdV) {
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 }
430 
431 template <class TNodeData, bool IsDir>
432 void TBigNet<TNodeData, IsDir>::SetOutNIdV(int NId, const TIntV& OutNIdV) {
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 }
438 
439 template <class TNodeData, bool IsDir>
440 void TBigNet<TNodeData, IsDir>::GetInNIdV(int NId, TIntV& InNIdV) const {
441  TNode Node; EAssertR(IsNode(NId, Node), TStr::Fmt("Not node: NId=%d\n", NId).CStr());
442  Pool.GetV(Node.InVId, InNIdV);
443 }
444 
445 template <class TNodeData, bool IsDir>
446 void TBigNet<TNodeData, IsDir>::GetOutNIdV(int NId, TIntV& OutNIdV) const {
447  TNode Node; EAssert(IsNode(NId, Node));
448  Pool.GetV(Node.OutVId, OutNIdV);
449 }
450 
451 // Node is deleted by setting edge endpoints to point to node id -1 (DelNId)
452 // No memory is freed
453 template <class TNodeData, bool IsDir>
454 int TBigNet<TNodeData, IsDir>::IsolateNode(int NId) {
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 }
498 
499 // set neigbors to point to DelNId, delete node from the node table
500 template <class TNodeData, bool IsDir>
501 int TBigNet<TNodeData, IsDir>::DelNode(int NId) {
502  const int DelEdges = IsolateNode(NId);
503  NodeH.DelKey(NId);
504  return DelEdges;
505 }
506 
507 template <class TNodeData, bool IsDir>
508 bool TBigNet<TNodeData, IsDir>::IsIsoNode(const int& NId) const {
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 }
515 
516 // the number deleted edges
517 template <class TNodeData, bool IsDir>
518 uint TBigNet<TNodeData, IsDir>::GetDelEdges() {
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 }
530 
531 template <class TNodeData, bool IsDir>
532 void TBigNet<TNodeData, IsDir>::CompactEdgePool() {
533  Pool.CompactPool(DelNId);
534 }
535 
536 template <class TNodeData, bool IsDir>
537 int TBigNet<TNodeData, IsDir>::AddEdge(const int& SrcNId, const int& DstNId) {
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 }
551 
552 template <class TNodeData, bool IsDir>
553 bool TBigNet<TNodeData, IsDir>::IsEdge(const int& SrcNId, const int& DstNId, const bool& Dir) const {
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 }
567 
568 template <class TNodeData, bool IsDir>
569 void TBigNet<TNodeData, IsDir>::GetNIdV(TIntV& NIdV) const {
570  NIdV.Reserve(GetNodes(), 0);
571  for (typename TNodeH::TIter I = NodeH.BegI(); I < NodeH.EndI(); I++) {
572  NIdV.Add(I->Key); }
573 }
574 
575 template <class TNodeData, bool IsDir>
576 void TBigNet<TNodeData, IsDir>::SortEdgeV() {
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 }
601 
602 // add missing nodes and in-links from a network of sources
603 template <class TNodeData, bool IsDir>
604 void TBigNet<TNodeData, IsDir>::InvertFromSources(uint ExpectNodes) {
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 }
666 
667 template <class TNodeData, bool IsDir>
668 void TBigNet<TNodeData, IsDir>::Rewire(TRnd& Rnd) {
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 }
764 
765 template <class TNodeData, bool IsDir>
766 PNGraph TBigNet<TNodeData, IsDir>::GetNGraph(const bool& RenumberNodes) const {
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 }
775 
776 template <class TNodeData, bool IsDir>
777 PNGraph TBigNet<TNodeData, IsDir>::GetSubNGraph(const TIntV& NIdV) const {
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 }
804 
805 template <class TNodeData, bool IsDir>
806 TPt<TBigNet<TNodeData, IsDir> > TBigNet<TNodeData, IsDir>::GetSubGraph(const TIntV& NIdV, const bool& RenumberNodes) const {
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 }
866 
867 template <class TNodeData, bool IsDir>
868 void TBigNet<TNodeData, IsDir>::GetSubGraph(const TIntV& NIdV, TBigNet* NewNetPt, const bool& RenumberNodes) const {
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 }
945 
946 template <class TNodeData, bool IsDir>
947 void TBigNet<TNodeData, IsDir>::Reserve(const int& Nodes, const TSize& Edges) {
948  NodeH.Gen(TMath::Mx(int(1.1*Nodes), 100));
949  Pool = TVPool(TMath::Mx(Edges, (TSize) Mega(1)), Mega(100), true);
950 }
951 
952 // check that in- and out-edges matchs, the table is sorted and so on
953 template <class TNodeData, bool IsDir>
954 bool TBigNet<TNodeData, IsDir>::IsOk() const {
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 }
1035 
1036 template <class TNodeData, bool IsDir>
1037 void TBigNet<TNodeData, IsDir>::Dump(const TStr& Desc) const {
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 }
1050 
1051 // header: <Nodes, Edges, IsDir>
1052 // format: undirected <NId, Dat, OutDeg, OutNodeV>
1053 // format: directed <NId, Dat, OutDeg, OutNodeV, InDeg, InNodeV>
1054 template <class TNodeData, bool IsDir>
1055 void TBigNet<TNodeData, IsDir>::SaveForDisk(const TStr& OutFNm) const {
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 }
1074 
1075 // skip the edge pool and only load the node data hash table
1076 template <class TNodeData, bool IsDir>
1077 void TBigNet<TNodeData, IsDir>::LoadNodeDatH(const TStr& InFNm, TNodeH& NodeH) {
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 }
1094 
1095 // Save the network without loading it. Save the node hash table as THash or TSparseHash
1096 template <class TNodeData, bool IsDir>
1097 void TBigNet<TNodeData, IsDir>::SaveToDisk(const TStr& InFNm, const TStr& OutFNm, const bool& SaveSparseHash) {
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 }
TCRef
Definition: bd.h:440
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TBigNet::Defrag
void Defrag(const bool &OnlyNodeLinks=false)
Definition: bignet.h:206
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
TBigNet::PBigNet
TPt< TBigNet< TNodeData, IsDir > > PBigNet
Definition: bignet.h:19
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TSnap::IsNodeDat
Tests (at compile time) if the graph is a network with data on nodes.
Definition: gbase.h:32
TBigNet::GetInNIdV
void GetInNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:440
TSnap
Main namespace for all the Snap global entities.
Definition: alg.h:1
TBigNet::AddUndirNode
int AddUndirNode(int NId, const int &Deg)
Definition: bignet.h:345
TBigNet::TEdgeI::GetSrcNDat
const TNodeData & GetSrcNDat() const
Definition: bignet.h:113
TBigNet::IsolateNode
int IsolateNode(int NId)
Definition: bignet.h:454
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TBigNet::GetNDat
TNodeDat & GetNDat(const int &NId)
Definition: bignet.h:170
TStr::Len
int Len() const
Definition: dt.h:490
TBigNet::TNodeI::OutNIdV
int * OutNIdV
Definition: bignet.h:55
TExeTm
Definition: tm.h:355
TInt::GetMegaStr
static TStr GetMegaStr(const int &Val)
Definition: dt.h:1226
TBigNet::IsIsoNode
bool IsIsoNode(const int &NId) const
Definition: bignet.h:508
TBigNet::TEdgeI::GetDstNId
int GetDstNId() const
Definition: bignet.h:112
TBigNet::~TBigNet
virtual ~TBigNet()
Definition: bignet.h:137
TRnd
Definition: dt.h:11
TBigNet::TNode::TNode
TNode(const int &InVecId, const int &OutVecId)
Definition: bignet.h:38
TVecPool::Reserved
uint64 Reserved() const
Returns the total capacity of the pool.
Definition: ds.h:1711
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:1139
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TBigNet::TNodeI::operator=
TNodeI & operator=(const TNodeI &NI)
Definition: bignet.h:64
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1153
TNGraph::ReserveNIdInDeg
void ReserveNIdInDeg(const int &NId, const int &InDeg)
Reserves memory for node ID NId having InDeg in-edges.
Definition: graph.h:616
TBigNet::Empty
bool Empty() const
Definition: bignet.h:203
TBigNet::SaveForDisk
void SaveForDisk(const TStr &OutFNm) const
Definition: bignet.h:1055
uint
unsigned int uint
Definition: bd.h:11
TBigNet::New
static PBigNet New(const int &Nodes, const TSize &Edges, const bool &Sources=false)
Definition: bignet.h:139
THashSet::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
TBigNet::LoadNodeDatH
static void LoadNodeDatH(const TStr &InFNm, TNodeH &NodeH)
Definition: bignet.h:1077
TInt::Mx
static const int Mx
Definition: dt.h:1142
TBigNet::TEdgeI::EndNode
TNodeI EndNode
Definition: bignet.h:99
TBigNet::TNodeI::GetOutDeg
int GetOutDeg() const
Definition: bignet.h:72
TBigNet::TNodeI::GetOutVId
int GetOutVId() const
Definition: bignet.h:59
TBigNet::TEdgeI::operator++
TEdgeI & operator++(int)
Definition: bignet.h:106
TSnap::IsDirected
Tests (at compile time) if the graph is directed.
Definition: gbase.h:28
THash::BegI
TIter BegI() const
Definition: hash.h:213
TBigNet::SetOutNIdV
void SetOutNIdV(int NId, const TIntV &OutNIdV)
Definition: bignet.h:432
TFOut
Definition: fl.h:319
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TBigNet::GetDelEdges
uint GetDelEdges()
Definition: bignet.h:518
THash::Save
void Save(TSOut &SOut) const
Definition: hash.h:183
TBigNet::CRef
TCRef CRef
Definition: bignet.h:129
THashSet::Gen
void Gen(const int &ExpectVals)
Definition: shash.h:1115
TBigNet::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Definition: bignet.h:537
TBigNet::CompactEdgePool
void CompactEdgePool()
Definition: bignet.h:532
TBigNet::Clr
void Clr(const bool &DoDel=true)
Definition: bignet.h:204
TBigNet::GetNode
TNode & GetNode(const int &NId)
Definition: bignet.h:125
TVecPool::Save
void Save(TSOut &SOut) const
Definition: ds.h:1835
TBigNet::TNodeDat
TNodeData TNodeDat
Definition: bignet.h:13
TBool::Save
void Save(TSOut &SOut) const
Definition: dt.h:995
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TBigNet::TNodeI::IsOutNId
bool IsOutNId(const int &NId) const
Definition: bignet.h:77
TBigNet::Reserve
void Reserve(const int &Nodes, const TSize &Edges)
Definition: bignet.h:947
TBigNet::TNodeI::GetDat
TNodeData & GetDat()
Definition: bignet.h:82
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TBigNet::EndNI
TNodeI EndNI() const
Definition: bignet.h:168
TVecPool::CompactPool
void CompactPool(const TVal &DelVal)
Deletes all elements of value DelVal from all vectors.
Definition: ds.h:1890
THash::EndI
TIter EndI() const
Definition: hash.h:218
TBigNet::TEdgeI::GetSrcNId
int GetSrcNId() const
Definition: bignet.h:111
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1146
TBigNet::TEdgeI::operator==
bool operator==(const TEdgeI &EdgeI) const
Definition: bignet.h:109
TFIn
Definition: fl.h:275
TBigNet::TNode::IsUnused
bool IsUnused() const
Tests whether the node is deleted then it is unused (and its InVId==OutVId==-1)
Definition: bignet.h:45
TBigNet::TNode::Save
void Save(TSOut &SOut) const
Definition: bignet.h:43
TBigNet::TNodeI::THashIter
TNodeH::TIter THashIter
Definition: bignet.h:52
TVecPool::GetVals
TSize GetVals() const
Returns the total number of values stored in the vector pool.
Definition: ds.h:1707
TBigNet::TNodeI
Node iterator.
Definition: bignet.h:50
THash::Load
void Load(TSIn &SIn)
Definition: hash.h:177
TBigNet::TNode::InVId
TInt InVId
Id of the vector storing nodes that point to the current node.
Definition: bignet.h:29
TBigNet::TEdgeI::CurNode
TNodeI CurNode
Definition: bignet.h:99
TBigNet::GetMxNId
int GetMxNId() const
Returns an id that is larger than any node id in the network.
Definition: bignet.h:153
TBigNet::TEdgeI::TEdgeI
TEdgeI(const TEdgeI &EdgeI)
Definition: bignet.h:104
THash::Defrag
void Defrag()
Definition: hash.h:555
TVecPool::AddEmptyV
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1881
TSIn
Definition: fl.h:58
TBigNet::SortEdgeV
void SortEdgeV()
Definition: bignet.h:576
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TSnap::GetFlagStr
TStr GetFlagStr(const TGraphFlag &GraphFlag)
Returns a string representation of a flag.
Definition: gbase.cpp:5
TBigNet::TBigNet
TBigNet(const int &Nodes, const TSize &Edges, const bool &Sources=false)
Definition: bignet.h:288
TB32Set::Save
void Save(TSOut &SOut) const
Definition: bits.h:248
TBigNet::TNode::TNode
TNode(const TNode &Node)
Definition: bignet.h:41
TBigNet::PNet
TPt< TNet > PNet
Definition: bignet.h:15
TBigNet::Dump
void Dump(const TStr &Desc=TStr()) const
Definition: bignet.h:1037
TBigNet::GetNI
TNodeI GetNI(const int &NId) const
Definition: bignet.h:169
TBigNet::TNodeI::GetInDeg
int GetInDeg() const
Definition: bignet.h:71
TBigNet::IsNode
bool IsNode(const int &NId, TNode &Node) const
Definition: bignet.h:118
TBigNet::Load
static PBigNet Load(TSIn &SIn)
Definition: bignet.h:141
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:404
TBigNet::TNodeI::GetInNId
int GetInNId(const int &NodeN) const
Definition: bignet.h:73
TBigNet::TNodeI::operator==
bool operator==(const TNodeI &NI) const
Definition: bignet.h:68
TBigNet::DelNode
int DelNode(int NId)
Definition: bignet.h:501
TBigNet::TNodeI::GetOutNbrId
int GetOutNbrId(const int &NodeN) const
Definition: bignet.h:75
TBigNet::TNodeI::TNodeI
TNodeI(const THashIter &NodeHIter, TVPool *PoolPt)
Definition: bignet.h:62
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
THash::Gen
void Gen(const int &ExpectVals)
Definition: hash.h:222
HasGraphFlag
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
TBigNet::DumpFlags
void DumpFlags() const
Definition: bignet.h:310
TBigNet::TNodeI::IsInNId
bool IsInNId(const int &NId) const
Definition: bignet.h:76
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
TBigNet::GetOutNIdVPt
int * GetOutNIdVPt(const int &NId) const
Definition: bignet.h:120
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
TBigNet::TNode::Dat
TNodeDat Dat
Data associated with the node.
Definition: bignet.h:35
uint64
unsigned long long uint64
Definition: bd.h:38
TBigNet::TNode::TNode
TNode(const int &InVecId, const int &OutVecId, const TNodeDat &NodeDat)
Definition: bignet.h:39
TBigNet::TNodeH
THash< TInt, TNode > TNodeH
Definition: bignet.h:17
TSIn::Load
void Load(bool &Bool)
Definition: fl.h:84
TVecPool::GetVLen
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
TBigNet::GetRndNI
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd) const
Definition: bignet.h:200
TVecPool::Clr
void Clr(bool DoDel=true)
Clears the contents of the pool.
Definition: ds.h:1760
TSize
size_t TSize
Definition: bd.h:58
TBigNet::TNodeI::Dump
void Dump() const
Definition: bignet.h:238
Mega
#define Mega(n)
Definition: gbase.h:4
Assert
#define Assert(Cond)
Definition: bd.h:251
TNGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
THash::IsKeyGetDat
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
TBigNet
Big Network.
Definition: bignet.h:11
TBigNet::TNodeI::operator<
bool operator<(const TNodeI &NI) const
Definition: bignet.h:67
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TB32Set::In
bool In(const int &BitN) const
Definition: bits.h:268
TBigNet::TNodeI::operator++
TNodeI & operator++(int)
Increment iterator.
Definition: bignet.h:66
TB32Set::Incl
void Incl(const int &BitN)
Definition: bits.h:262
TBigNet::OnlySources
bool OnlySources() const
Definition: bignet.h:145
TBigNet::operator=
TBigNet & operator=(const TBigNet &Net)
Definition: bignet.h:142
TBigNet::TBigNet
TBigNet(TSIn &SIn)
Definition: bignet.h:136
TBigNet::GetNDat
const TNodeDat & GetNDat(const int &NId) const
Definition: bignet.h:171
TBigNet::GetNodes
int GetNodes() const
Definition: bignet.h:151
TBigNet::PVPool
TPt< TVPool > PVPool
Definition: bignet.h:21
TBigNet::TNodeI::IsNbrNId
bool IsNbrNId(const int &NId) const
Definition: bignet.h:78
FailR
#define FailR(Reason)
Definition: bd.h:240
TBigNet::TEdgeI
Edge iterator.
Definition: bignet.h:97
TBigNet::TEdgeI::operator=
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: bignet.h:105
TBigNet::GetEdges
::TSize GetEdges() const
Definition: bignet.h:185
TSOut
Definition: fl.h:128
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
TBigNet::BegNI
TNodeI BegNI() const
Definition: bignet.h:167
TSOut::Save
void Save(const bool &Bool)
Definition: fl.h:173
THash::GetMxKeyIds
int GetMxKeyIds() const
Definition: hash.h:231
TInt
Definition: dt.h:1137
TBigNet::TNodeI::TNodeI
TNodeI(const TNodeI &NodeI)
Definition: bignet.h:63
TBigNet::TNodeI::operator()
const TNodeData & operator()() const
Definition: bignet.h:79
TBigNet::TNode
Node container class.
Definition: bignet.h:26
gfDirected
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
TBigNet::BinSearch2
static const int * BinSearch2(const int *Beg, const int *End, const int &Val)
Definition: bignet.h:274
EAssert
#define EAssert(Cond)
Definition: bd.h:280
TBigNet::SetInNIdV
void SetInNIdV(int NId, const TIntV &InNIdV)
Definition: bignet.h:424
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
TPair
Definition: ds.h:32
TBigNet::TNodeI::GetInOutNIdV
void GetInOutNIdV()
Definition: bignet.h:224
TBigNet::TNodeI::InNIdV
int * InNIdV
Definition: bignet.h:55
TBigNet::GetNIdV
void GetNIdV(TIntV &NIdV) const
Definition: bignet.h:569
TBigNet::GetNGraph
PNGraph GetNGraph(const bool &RenumberNodes=false) const
Definition: bignet.h:766
THash::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
TBigNet::GetSubGraph
PBigNet GetSubGraph(const TIntV &NIdV, const bool &RenumberNodes=false) const
Definition: bignet.h:806
TBigNet::AddNode
int AddNode(int NId, const int &InDeg, const int &OutDeg)
Definition: bignet.h:320
TBigNet::TNodeI::GetId
int GetId() const
Definition: bignet.h:69
TBigNet::TNodeI::Pool
TVPool * Pool
Definition: bignet.h:54
TSparseHash::AddDat
TDat & AddDat(const TKey &Key)
Definition: shash.h:687
TBigNet::TEdgeI::GetId
int GetId() const
Definition: bignet.h:110
TBigNet::InvertFromSources
void InvertFromSources(uint ExpectNodes=0)
Definition: bignet.h:604
TBigNet::SaveToDisk
static void SaveToDisk(const TStr &InFNm, const TStr &OutFNm, const bool &SaveSparseHash)
Definition: bignet.h:1097
TStr
Definition: dt.h:412
TBigNet::GetInNIdVPt
int * GetInNIdVPt(const int &NId) const
Definition: bignet.h:119
TStr::Empty
bool Empty() const
Definition: dt.h:491
gfMx
sentinel, last value for iteration
Definition: gbase.h:19
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
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
TGraphFlag
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
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
TBigNet::TNodeI::GetOutNId
int GetOutNId(const int &NodeN) const
Definition: bignet.h:74
TBigNet::IsNode
bool IsNode(const int &NId) const
Definition: bignet.h:166
TBigNet::Save
virtual void Save(TSOut &SOut) const
Definition: bignet.h:301
TBigNet::GetEI
TEdgeI GetEI(const int &EId) const
TBigNet::TNodeI::NodeHI
THashIter NodeHI
Definition: bignet.h:53
TBigNet::TEdgeI::operator<
bool operator<(const TEdgeI &EdgeI) const
Definition: bignet.h:108
TBigNet::NodeH
TNodeH NodeH
Definition: bignet.h:133
TVecPool::ShuffleAll
void ShuffleAll(TRnd &Rnd=TInt::Rnd)
Shuffles the order of all elements in the pool.
Definition: ds.h:1919
EAssertR
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TExeTm::GetSecs
double GetSecs() const
Definition: tm.h:366
TBigNet::BegEI
TEdgeI BegEI() const
Definition: bignet.h:173
TBigNet::AddSorted
static void AddSorted(int *Beg, int *End, const int &Val)
Definition: bignet.h:248
TBigNet::Rewire
void Rewire(TRnd &Rnd=TInt::Rnd)
Definition: bignet.h:668
gfSources
nodes only store out-edges (but not in-edges). See TBigNet
Definition: gbase.h:17
TPair::Val1
TVal1 Val1
Definition: ds.h:34
TNGraph::Reserve
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:614
TPair::Val2
TVal2 Val2
Definition: ds.h:35
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
TBigNet::TEdgeI::TEdgeI
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: bignet.h:103
TPt
Definition: bd.h:196
TBigNet::MxNId
TInt MxNId
Definition: bignet.h:130
TBigNet::TNode::TNode
TNode(TSIn &SIn)
Definition: bignet.h:42
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
TBigNet::GetRndNId
int GetRndNId(TRnd &Rnd=TInt::Rnd) const
Definition: bignet.h:199
TVec::Reserve
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
TB32Set::Excl
void Excl(const int &BitN)
Definition: bits.h:265
TBigNet::IsEdge
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &Dir=true) const
Definition: bignet.h:553
TBigNet::GetSubNGraph
PNGraph GetSubNGraph(const TIntV &NIdV) const
Definition: bignet.h:777
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TStr::CStr
char * CStr()
Definition: dt.h:479
TBigNet::GetOutNIdV
void GetOutNIdV(int NId, TIntV &OutNIdV) const
Definition: bignet.h:446
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TVecPool::IsVId
bool IsVId(const int &VId) const
Tests whether vector of id VId is in the pool.
Definition: ds.h:1709
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TBool
Definition: dt.h:974
TBigNet::TNodeI::GetDeg
int GetDeg() const
Definition: bignet.h:70
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
TBigNet::EndEI
TEdgeI EndEI() const
Definition: bignet.h:174
TBigNet::TNodeI::GetInVId
int GetInVId() const
Definition: bignet.h:58
TBigNet::IsOk
bool IsOk() const
Definition: bignet.h:954
TNodeNet
Node Network (directed graph, TNGraph with data on nodes only).
Definition: network.h:17
TBigNet::TNet
TBigNet< TNodeData, IsDir > TNet
Definition: bignet.h:14
TBigNet::TNodeI::GetDat
const TNodeData & GetDat() const
Definition: bignet.h:81
TBigNet::TNode::OutVId
TInt OutVId
Id of the vector storing nodes that the current node points to.
Definition: bignet.h:33
TNGraph::ReserveNIdOutDeg
void ReserveNIdOutDeg(const int &NId, const int &OutDeg)
Reserves memory for node ID NId having OutDeg out-edges.
Definition: graph.h:618
TBigNet::HasFlag
bool HasFlag(const TGraphFlag &Flag) const
Definition: bignet.h:146
THash::GetI
TIter GetI(const TKey &Key) const
Definition: hash.h:220
TBigNet::TEdgeI::GetDstNDat
TNodeData & GetDstNDat()
Definition: bignet.h:114