SNAP Library 4.0, User Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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
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
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:487
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:1223
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
TMath::Mx
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:477
TBigNet::TNodeI::operator=
TNodeI & operator=(const TNodeI &NI)
Definition: bignet.h:64
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1150
TNGraph::ReserveNIdInDeg
void ReserveNIdInDeg(const int &NId, const int &InDeg)
Reserves memory for node ID NId having InDeg in-edges.
Definition: graph.h:608
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:1139
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
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:1834
TBigNet::TNodeDat
TNodeData TNodeDat
Definition: bignet.h:13
TBool::Save
void Save(TSOut &SOut) const
Definition: dt.h:992
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
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:1143
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:1706
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
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:1730
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
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:1728
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:1759
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:542
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:1134
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
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:488
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
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
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:606
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
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
TVec::GetV
static TVec< TVal, TSizeTy > GetV(const TVal &Val1)
Returns a vector on element Val1.
Definition: ds.h:848
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TStr::CStr
char * CStr()
Definition: dt.h:476
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:1708
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:971
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
THashKeyDatI::EndI
THKeyDat * EndI
Definition: hash.h:54
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:610
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