SNAP Library 2.4, Developer Reference  2015-05-11 19:40:56
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
network.h
Go to the documentation of this file.
1 // Node Data
3 // TNodeData has to implement the following methods:
4 // class TNodeData {
5 // public:
6 // TNodeData() { }
7 // TNodeData(TSIn& SIn) { }
8 // void Save(TSOut& SOut) const { }
9 // };
10 
11 //#//////////////////////////////////////////////
13 template <class TNodeData>
14 class TNodeNet {
15 public:
16  typedef TNodeData TNodeDat;
18  typedef TPt<TNet> PNet;
19 public:
20  class TNode {
21  private:
23  TNodeData NodeDat;
25  public:
26  TNode() : Id(-1), NodeDat(), InNIdV(), OutNIdV() { }
27  TNode(const int& NId) : Id(NId), NodeDat(), InNIdV(), OutNIdV() { }
28  TNode(const int& NId, const TNodeData& NodeData) : Id(NId), NodeDat(NodeData), InNIdV(), OutNIdV() { }
29  TNode(const TNode& Node) : Id(Node.Id), NodeDat(Node.NodeDat), InNIdV(Node.InNIdV), OutNIdV(Node.OutNIdV) { }
30  TNode(TSIn& SIn) : Id(SIn), NodeDat(SIn), InNIdV(SIn), OutNIdV(SIn) { }
31  void Save(TSOut& SOut) const { Id.Save(SOut); NodeDat.Save(SOut); InNIdV.Save(SOut); OutNIdV.Save(SOut); }
32  int GetId() const { return Id; }
33  int GetDeg() const { return GetInDeg() + GetOutDeg(); }
34  int GetInDeg() const { return InNIdV.Len(); }
35  int GetOutDeg() const { return OutNIdV.Len(); }
36  const TNodeData& GetDat() const { return NodeDat; }
37  TNodeData& GetDat() { return NodeDat; }
38  int GetInNId(const int& NodeN) const { return InNIdV[NodeN]; }
39  int GetOutNId(const int& NodeN) const { return OutNIdV[NodeN]; }
40  int GetNbrNId(const int& NodeN) const { return NodeN<GetOutDeg() ? GetOutNId(NodeN):GetInNId(NodeN-GetOutDeg()); }
41  bool IsInNId(const int& NId) const { return InNIdV.SearchBin(NId) != -1; }
42  bool IsOutNId(const int& NId) const { return OutNIdV.SearchBin(NId) != -1; }
43  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
44  bool operator < (const TNode& Node) const { return NodeDat < Node.NodeDat; }
45  friend class TNodeNet<TNodeData>;
46  };
47 
49  class TNodeI {
50  private:
54  public:
55  TNodeI() : NodeHI(), Net(NULL) { }
56  TNodeI(const THashIter& NodeHIter, const TNodeNet* NetPt) : NodeHI(NodeHIter), Net((TNodeNet *) NetPt) { }
57  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Net(NodeI.Net) { }
58  TNodeI& operator = (const TNodeI& NodeI) { NodeHI=NodeI.NodeHI; Net=NodeI.Net; return *this; }
60  TNodeI& operator++ (int) { NodeHI++; return *this; }
61  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
62  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
63 
65  int GetId() const { return NodeHI.GetDat().GetId(); }
67  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
69  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
71  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
73 
75  int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }
77 
79  int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }
81 
83  int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
85  bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
87  bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
89  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
90  const TNodeData& operator () () const { return NodeHI.GetDat().NodeDat; }
91  TNodeData& operator () () { return NodeHI.GetDat().GetDat(); }
92  const TNodeData& GetDat() const { return NodeHI.GetDat().GetDat(); }
93  TNodeData& GetDat() { return NodeHI.GetDat().GetDat(); }
94  const TNodeData& GetInNDat(const int& NodeN) const { return Net->GetNDat(GetInNId(NodeN)); }
95  TNodeData& GetInNDat(const int& NodeN) { return Net->GetNDat(GetInNId(NodeN)); }
96  const TNodeData& GetOutNDat(const int& NodeN) const { return Net->GetNDat(GetOutNId(NodeN)); }
97  TNodeData& GetOutNDat(const int& NodeN) { return Net->GetNDat(GetOutNId(NodeN)); }
98  const TNodeData& GetNbrNDat(const int& NodeN) const { return Net->GetNDat(GetNbrNId(NodeN)); }
99  TNodeData& GetNbrNDat(const int& NodeN) { return Net->GetNDat(GetNbrNId(NodeN)); }
100  friend class TNodeNet<TNodeData>;
101  };
102 
104  class TEdgeI {
105  private:
107  int CurEdge;
108  public:
109  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
110  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
111  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
112  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
115  while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; }
116  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
117  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
119  int GetId() const { return -1; }
121  int GetSrcNId() const { return CurNode.GetId(); }
123  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
124  const TNodeData& GetSrcNDat() const { return CurNode.GetDat(); }
125  TNodeData& GetDstNDat() { return CurNode.GetOutNDat(CurEdge); }
126  friend class TNodeNet<TNodeData>;
127  };
128 
129 protected:
130  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
131 
132 protected:
136 
137 public:
138  TNodeNet() : CRef(), MxNId(0), NodeH() { }
140  explicit TNodeNet(const int& Nodes, const int& Edges) : MxNId(0) { Reserve(Nodes, Edges); }
141  TNodeNet(const TNodeNet& NodeNet) : MxNId(NodeNet.MxNId), NodeH(NodeNet.NodeH) { }
143  TNodeNet(TSIn& SIn) : MxNId(SIn), NodeH(SIn) { }
144  virtual ~TNodeNet() { }
146  virtual void Save(TSOut& SOut) const { MxNId.Save(SOut); NodeH.Save(SOut); }
148  static PNet New() { return PNet(new TNodeNet()); }
150  static PNet Load(TSIn& SIn) { return PNet(new TNodeNet(SIn)); }
152  bool HasFlag(const TGraphFlag& Flag) const;
153  TNodeNet& operator = (const TNodeNet& NodeNet) {
154  if (this!=&NodeNet) { NodeH=NodeNet.NodeH; MxNId=NodeNet.MxNId; } return *this; }
155  // nodes
157  int GetNodes() const { return NodeH.Len(); }
159 
163  int AddNode(int NId = -1);
165 
169  int AddNode(int NId, const TNodeData& NodeDat);
171  int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId(), NodeI.GetDat()); }
173 
175  void DelNode(const int& NId);
177  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
179  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
181  TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); }
183  TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); }
185  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); }
187  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
189  void SetNDat(const int& NId, const TNodeData& NodeDat);
191  TNodeData& GetNDat(const int& NId) { return NodeH.GetDat(NId).NodeDat; }
193  const TNodeData& GetNDat(const int& NId) const { return NodeH.GetDat(NId).NodeDat; }
195  int GetMxNId() const { return MxNId; }
196 
197  // edges
199  int GetEdges() const;
201 
207  int AddEdge(const int& SrcNId, const int& DstNId);
209  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
211 
215  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
217  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const;
219  TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0) NI++; return TEdgeI(NI, EndNI()); }
221  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
223  TEdgeI GetEI(const int& EId) const;
225  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;
226 
228  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
230  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
232  void GetNIdV(TIntV& NIdV) const;
233 
235  bool Empty() const { return GetNodes()==0; }
237  void Clr(const bool& DoDel=true, const bool& ResetDat=true) {
238  MxNId = 0; NodeH.Clr(DoDel, -1, ResetDat); }
240  void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) { NodeH.Gen(Nodes/2); } }
242  void SortNIdById(const bool& Asc=true) { NodeH.SortByKey(Asc); }
244  void SortNIdByDat(const bool& Asc=true) { NodeH.SortByDat(Asc); }
246 
251  void Defrag(const bool& OnlyNodeLinks=false);
253 
256  bool IsOk(const bool& ThrowExcept=true) const;
257 
258  friend class TPt<TNodeNet<TNodeData> >;
259 };
260 
261 // set flags
262 namespace TSnap {
263 template <class TNodeData> struct IsDirected<TNodeNet<TNodeData> > { enum { Val = 1 }; };
264 template <class TNodeData> struct IsNodeDat<TNodeNet<TNodeData> > { enum { Val = 1 }; };
265 }
266 
267 template <class TNodeData>
268 bool TNodeNet<TNodeData>::HasFlag(const TGraphFlag& Flag) const {
269  return HasGraphFlag(typename TNet, Flag);
270 }
271 
272 template <class TNodeData>
274  if (NId == -1) {
275  NId = MxNId; MxNId++;
276  } else {
277  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
278  MxNId = TMath::Mx(NId+1, MxNId());
279  }
280  NodeH.AddDat(NId, TNode(NId));
281  return NId;
282 }
283 
284 template <class TNodeData>
285 int TNodeNet<TNodeData>::AddNode(int NId, const TNodeData& NodeDat) {
286  if (NId == -1) {
287  NId = MxNId; MxNId++;
288  } else {
289  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
290  MxNId = TMath::Mx(NId+1, MxNId());
291  }
292  NodeH.AddDat(NId, TNode(NId, NodeDat));
293  return NId;
294 }
295 
296 template <class TNodeData>
297 void TNodeNet<TNodeData>::DelNode(const int& NId) {
298  { TNode& Node = GetNode(NId);
299  for (int e = 0; e < Node.GetOutDeg(); e++) {
300  const int nbr = Node.GetOutNId(e);
301  if (nbr == NId) { continue; }
302  TNode& N = GetNode(nbr);
303  int n = N.InNIdV.SearchBin(NId);
304  if (n!= -1) { N.InNIdV.Del(n); }
305  }
306  for (int e = 0; e < Node.GetInDeg(); e++) {
307  const int nbr = Node.GetInNId(e);
308  if (nbr == NId) { continue; }
309  TNode& N = GetNode(nbr);
310  int n = N.OutNIdV.SearchBin(NId);
311  if (n!= -1) { N.OutNIdV.Del(n); }
312  } }
313  NodeH.DelKey(NId);
314 }
315 
316 template <class TNodeData>
317 void TNodeNet<TNodeData>::SetNDat(const int& NId, const TNodeData& NodeDat) {
318  IAssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist.", NId).CStr());
319  NodeH.GetDat(NId).NodeDat = NodeDat;
320 }
321 
322 template <class TNodeData>
324  int edges=0;
325  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N);) {
326  edges+=NodeH[N].GetOutDeg(); }
327  return edges;
328 }
329 
330 template <class TNodeData>
331 int TNodeNet<TNodeData>::AddEdge(const int& SrcNId, const int& DstNId) {
332  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
333  if (IsEdge(SrcNId, DstNId)) { return -2; }
334  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
335  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
336  return -1; // edge id
337 }
338 
339 template <class TNodeData>
340 void TNodeNet<TNodeData>::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) {
341  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
342  GetNode(SrcNId).OutNIdV.DelIfIn(DstNId);
343  GetNode(DstNId).InNIdV.DelIfIn(SrcNId);
344  if (! IsDir) {
345  GetNode(DstNId).OutNIdV.DelIfIn(SrcNId);
346  GetNode(SrcNId).InNIdV.DelIfIn(DstNId);
347  }
348 }
349 
350 template <class TNodeData>
351 bool TNodeNet<TNodeData>::IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) const {
352  if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
353  if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
354  else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
355 }
356 
357 template <class TNodeData>
359  NIdV.Reserve(GetNodes(), 0);
360  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
361  NIdV.Add(NodeH.GetKey(N)); }
362 }
363 
364 template <class TNodeData>
365 typename TNodeNet<TNodeData>::TEdgeI TNodeNet<TNodeData>::GetEI(const int& SrcNId, const int& DstNId) const {
366  const TNodeI SrcNI = GetNI(SrcNId);
367  const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
368  if (NodeN == -1) { return EndEI(); }
369  return TEdgeI(SrcNI, EndNI(), NodeN);
370 }
371 
372 template <class TNodeData>
373 void TNodeNet<TNodeData>::Defrag(const bool& OnlyNodeLinks) {
374  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
375  TNode& Node = NodeH[n];
376  Node.InNIdV.Pack(); Node.OutNIdV.Pack();
377  }
378  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
379  NodeH.Defrag(); }
380 }
381 
382 template <class TNodeData>
383 bool TNodeNet<TNodeData>::IsOk(const bool& ThrowExcept) const {
384  bool RetVal = true;
385  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
386  const TNode& Node = NodeH[N];
387  if (! Node.OutNIdV.IsSorted()) {
388  const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
389  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
390  }
391  if (! Node.InNIdV.IsSorted()) {
392  const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
393  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
394  }
395  // check out-edges
396  int prevNId = -1;
397  for (int e = 0; e < Node.GetOutDeg(); e++) {
398  if (! IsNode(Node.GetOutNId(e))) {
399  const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
400  Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
401  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
402  }
403  if (e > 0 && prevNId == Node.GetOutNId(e)) {
404  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
405  Node.GetId(), Node.GetId(), Node.GetOutNId(e));
406  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
407  }
408  prevNId = Node.GetOutNId(e);
409  }
410  // check in-edges
411  prevNId = -1;
412  for (int e = 0; e < Node.GetInDeg(); e++) {
413  if (! IsNode(Node.GetInNId(e))) {
414  const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
415  Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
416  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
417  }
418  if (e > 0 && prevNId == Node.GetInNId(e)) {
419  const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
420  Node.GetId(), Node.GetId(), Node.GetInNId(e));
421  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
422  }
423  prevNId = Node.GetInNId(e);
424  }
425  }
426  return RetVal;
427 }
428 
430 // Common network types
437 
438 //#//////////////////////////////////////////////
440 template <class TNodeData, class TEdgeData>
442 public:
443  typedef TNodeData TNodeDat;
444  typedef TEdgeData TEdgeDat;
446  typedef TPt<TNet> PNet;
448 public:
449  class TNode {
450  private:
452  TNodeData NodeDat;
455  public:
456  TNode() : Id(-1), NodeDat(), InNIdV(), OutNIdV() { }
457  TNode(const int& NId) : Id(NId), NodeDat(), InNIdV(), OutNIdV() { }
458  TNode(const int& NId, const TNodeData& NodeData) : Id(NId), NodeDat(NodeData), InNIdV(), OutNIdV() { }
459  TNode(const TNode& Node) : Id(Node.Id), NodeDat(Node.NodeDat), InNIdV(Node.InNIdV), OutNIdV(Node.OutNIdV) { }
460  TNode(TSIn& SIn) : Id(SIn), NodeDat(SIn), InNIdV(SIn), OutNIdV(SIn) { }
461  void Save(TSOut& SOut) const { Id.Save(SOut); NodeDat.Save(SOut); InNIdV.Save(SOut); OutNIdV.Save(SOut); }
462  int GetId() const { return Id; }
463  int GetDeg() const { return GetInDeg() + GetOutDeg(); }
464  int GetInDeg() const { return InNIdV.Len(); }
465  int GetOutDeg() const { return OutNIdV.Len(); }
466  const TNodeData& GetDat() const { return NodeDat; }
467  TNodeData& GetDat() { return NodeDat; }
468  int GetInNId(const int& EdgeN) const { return InNIdV[EdgeN]; }
469  int GetOutNId(const int& EdgeN) const { return OutNIdV[EdgeN].Val1; }
470  int GetNbrNId(const int& EdgeN) const { return EdgeN<GetOutDeg() ? GetOutNId(EdgeN):GetInNId(EdgeN-GetOutDeg()); }
471  TEdgeData& GetOutEDat(const int& EdgeN) { return OutNIdV[EdgeN].Val2; }
472  const TEdgeData& GetOutEDat(const int& EdgeN) const { return OutNIdV[EdgeN].Val2; }
473  bool IsInNId(const int& NId) const { return InNIdV.SearchBin(NId)!=-1; }
474  bool IsOutNId(const int& NId) const { return TNodeEDatNet::GetNIdPos(OutNIdV, NId)!=-1; }
475  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
476  bool operator < (const TNode& Node) const { return NodeDat < Node.NodeDat; }
477  friend class TNodeEDatNet<TNodeData, TEdgeData>;
478  };
479 
481  class TNodeI {
482  private:
486  public:
487  TNodeI() : NodeHI(), Net(NULL) { }
488  TNodeI(const THashIter& NodeHIter, const TNodeEDatNet* NetPt) : NodeHI(NodeHIter), Net((TNodeEDatNet *) NetPt) { }
489  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Net(NodeI.Net) { }
490  TNodeI& operator = (const TNodeI& NodeI) { NodeHI=NodeI.NodeHI; Net=NodeI.Net; return *this; }
492  TNodeI& operator++ (int) { NodeHI++; return *this; }
493  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
494  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
495 
497  int GetId() const { return NodeHI.GetDat().GetId(); }
499  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
501  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
503  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
505 
507  int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }
509 
511  int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }
513 
515  int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
517  bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
519  bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
521  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
522  // node data
523  const TNodeData& operator () () const { return NodeHI.GetDat().NodeDat; }
524  TNodeData& operator () () { return NodeHI.GetDat().GetDat(); }
525  const TNodeData& GetDat() const { return NodeHI.GetDat().GetDat(); }
526  TNodeData& GetDat() { return NodeHI.GetDat().GetDat(); }
527  const TNodeData& GetOutNDat(const int& NodeN) const { return Net->GetNDat(GetOutNId(NodeN)); }
528  TNodeData& GetOutNDat(const int& NodeN) { return Net->GetNDat(GetOutNId(NodeN)); }
529  const TNodeData& GetInNDat(const int& NodeN) const { return Net->GetNDat(GetInNId(NodeN)); }
530  TNodeData& GetInNDat(const int& NodeN) { return Net->GetNDat(GetInNId(NodeN)); }
531  const TNodeData& GetNbrNDat(const int& NodeN) const { return Net->GetNDat(GetNbrNId(NodeN)); }
532  TNodeData& GetNbrNDat(const int& NodeN) { return Net->GetNDat(GetNbrNId(NodeN)); }
533  // edge data
534  TEdgeData& GetOutEDat(const int& EdgeN) { return NodeHI.GetDat().GetOutEDat(EdgeN); }
535  const TEdgeData& GetOutEDat(const int& EdgeN) const { return NodeHI.GetDat().GetOutEDat(EdgeN); }
536  TEdgeData& GetInEDat(const int& EdgeN) { return Net->GetEDat(GetInNId(EdgeN), GetId()); }
537  const TEdgeData& GetInEDat(const int& EdgeN) const { return Net->GetEDat(GetInNId(EdgeN), GetId()); }
538  TEdgeData& GetNbrEDat(const int& EdgeN) { return EdgeN<GetOutDeg() ? GetOutEDat(EdgeN) : GetInEDat(EdgeN-GetOutDeg()); }
539  const TEdgeData& GetNbrEDat(const int& EdgeN) const { return EdgeN<GetOutDeg() ? GetOutEDat(EdgeN) : GetInEDat(EdgeN-GetOutDeg()); }
540  friend class TNodeEDatNet<TNodeData, TEdgeData>;
541  };
542 
544  class TEdgeI {
545  private:
547  int CurEdge;
548  public:
549  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
550  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
551  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
552  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
555  while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; }
556  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
557  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
559  int GetId() const { return -1; }
561  int GetSrcNId() const { return CurNode.GetId(); }
563  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
564  TEdgeData& operator () () { return CurNode.GetOutEDat(CurEdge); }
565  const TEdgeData& operator () () const { return CurNode.GetOutEDat(CurEdge); }
566  TEdgeData& GetDat() { return CurNode.GetOutEDat(CurEdge); }
567  const TEdgeData& GetDat() const { return CurNode.GetOutEDat(CurEdge); }
568  TNodeData& GetSrcNDat() { return CurNode(); }
569  const TNodeData& GetSrcNDat() const { return CurNode(); }
570  TNodeData& GetDstNDat() { return CurNode.GetOutNDat(CurEdge); }
571  const TNodeData& GetDstNDat() const { return CurNode.GetOutNDat(CurEdge); }
572  friend class TNodeEDatNet<TNodeData, TEdgeData>;
573  };
574 
575 protected:
576  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
577  static int GetNIdPos(const TVec<TPair<TInt, TEdgeData> >& NIdV, const int& NId);
578 protected:
582 public:
583  TNodeEDatNet() : CRef(), MxNId(0), NodeH() { }
585  explicit TNodeEDatNet(const int& Nodes, const int& Edges) : MxNId(0) { Reserve(Nodes, Edges); }
586  TNodeEDatNet(const TNodeEDatNet& NodeNet) : MxNId(NodeNet.MxNId), NodeH(NodeNet.NodeH) { }
588  TNodeEDatNet(TSIn& SIn) : MxNId(SIn), NodeH(SIn) { }
589  virtual ~TNodeEDatNet() { }
591  virtual void Save(TSOut& SOut) const { MxNId.Save(SOut); NodeH.Save(SOut); }
593  static PNet New() { return PNet(new TNet()); }
595  static PNet Load(TSIn& SIn) { return PNet(new TNet(SIn)); }
597  bool HasFlag(const TGraphFlag& Flag) const;
598  TNodeEDatNet& operator = (const TNodeEDatNet& NodeNet) { if (this!=&NodeNet) {
599  NodeH=NodeNet.NodeH; MxNId=NodeNet.MxNId; } return *this; }
600  // nodes
602  int GetNodes() const { return NodeH.Len(); }
604 
608  int AddNode(int NId = -1);
610 
614  int AddNode(int NId, const TNodeData& NodeDat);
616  int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId(), NodeI.GetDat()); }
618 
620  void DelNode(const int& NId);
622  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
624  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
626  TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); }
628  TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); }
630  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); }
632  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
634  void SetNDat(const int& NId, const TNodeData& NodeDat);
636  TNodeData& GetNDat(const int& NId) { return NodeH.GetDat(NId).NodeDat; }
638  const TNodeData& GetNDat(const int& NId) const { return NodeH.GetDat(NId).NodeDat; }
640  int GetMxNId() const { return MxNId; }
641 
642  // edges
644  int GetEdges() const;
646 
652  int AddEdge(const int& SrcNId, const int& DstNId);
654 
660  int AddEdge(const int& SrcNId, const int& DstNId, const TEdgeData& EdgeDat);
662  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI()); }
664 
668  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
670  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const;
672  TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0) NI++; return TEdgeI(NI, EndNI()); }
674  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
676  TEdgeI GetEI(const int& EId) const; // not supported
678  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;
680  void SetEDat(const int& SrcNId, const int& DstNId, const TEdgeData& EdgeDat);
682 
684  bool GetEDat(const int& SrcNId, const int& DstNId, TEdgeData& EdgeDat) const;
686  TEdgeData& GetEDat(const int& SrcNId, const int& DstNId);
688  const TEdgeData& GetEDat(const int& SrcNId, const int& DstNId) const;
690  void SetAllEDat(const TEdgeData& EdgeDat);
691 
693  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
695  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
697  void GetNIdV(TIntV& NIdV) const;
698 
700  bool Empty() const { return GetNodes()==0; }
702  void Clr(const bool& DoDel=true, const bool& ResetDat=true) {
703  MxNId = 0; NodeH.Clr(DoDel, -1, ResetDat); }
705  void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) { NodeH.Gen(Nodes/2); } }
707  void SortNIdById(const bool& Asc=true) { NodeH.SortByKey(Asc); }
709  void SortNIdByDat(const bool& Asc=true) { NodeH.SortByDat(Asc); }
711 
716  void Defrag(const bool& OnlyNodeLinks=false);
718 
721  bool IsOk(const bool& ThrowExcept=true) const;
722 
723  friend class TPt<TNodeEDatNet<TNodeData, TEdgeData> >;
724 };
725 
726 // set flags
727 namespace TSnap {
728 template <class TNodeData, class TEdgeData> struct IsDirected<TNodeEDatNet<TNodeData, TEdgeData> > { enum { Val = 1 }; };
729 template <class TNodeData, class TEdgeData> struct IsNodeDat<TNodeEDatNet<TNodeData, TEdgeData> > { enum { Val = 1 }; };
730 template <class TNodeData, class TEdgeData> struct IsEdgeDat<TNodeEDatNet<TNodeData, TEdgeData> > { enum { Val = 1 }; };
731 }
732 
733 template <class TNodeData, class TEdgeData>
735  return HasGraphFlag(typename TNet, Flag);
736 }
737 
738 template <class TNodeData, class TEdgeData>
740  int LValN=0, RValN = NIdV.Len()-1;
741  while (RValN >= LValN) {
742  const int ValN = (LValN+RValN)/2;
743  const int CurNId = NIdV[ValN].Val1;
744  if (NId == CurNId) { return ValN; }
745  if (NId < CurNId) { RValN=ValN-1; }
746  else { LValN=ValN+1; }
747  }
748  return -1;
749 }
750 
751 template <class TNodeData, class TEdgeData>
753  if (NId == -1) {
754  NId = MxNId; MxNId++;
755  } else {
756  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
757  MxNId = TMath::Mx(NId+1, MxNId());
758  }
759  NodeH.AddDat(NId, TNode(NId));
760  return NId;
761 }
762 
763 template <class TNodeData, class TEdgeData>
764 int TNodeEDatNet<TNodeData, TEdgeData>::AddNode(int NId, const TNodeData& NodeDat) {
765  if (NId == -1) {
766  NId = MxNId; MxNId++;
767  } else {
768  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
769  MxNId = TMath::Mx(NId+1, MxNId());
770  }
771  NodeH.AddDat(NId, TNode(NId, NodeDat));
772  return NId;
773 }
774 
775 template <class TNodeData, class TEdgeData>
776 void TNodeEDatNet<TNodeData, TEdgeData>::SetNDat(const int& NId, const TNodeData& NodeDat) {
777  IAssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist.", NId).CStr());
778  NodeH.GetDat(NId).NodeDat = NodeDat;
779 }
780 
781 template <class TNodeData, class TEdgeData>
783  const TNode& Node = GetNode(NId);
784  for (int out = 0; out < Node.GetOutDeg(); out++) {
785  const int nbr = Node.GetOutNId(out);
786  if (nbr == NId) { continue; }
787  TIntV& NIdV = GetNode(nbr).InNIdV;
788  const int pos = NIdV.SearchBin(NId);
789  if (pos != -1) { NIdV.Del(pos); }
790  }
791  for (int in = 0; in < Node.GetInDeg(); in++) {
792  const int nbr = Node.GetInNId(in);
793  if (nbr == NId) { continue; }
794  TNIdDatPrV& NIdDatV = GetNode(nbr).OutNIdV;
795  const int pos = GetNIdPos(NIdDatV, NId);
796  if (pos != -1) { NIdDatV.Del(pos); }
797  }
798  NodeH.DelKey(NId);
799 }
800 
801 template <class TNodeData, class TEdgeData>
803  int edges=0;
804  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
805  edges+=NodeH[N].GetOutDeg(); }
806  return edges;
807 }
808 
809 template <class TNodeData, class TEdgeData>
810 int TNodeEDatNet<TNodeData, TEdgeData>::AddEdge(const int& SrcNId, const int& DstNId) {
811  return AddEdge(SrcNId, DstNId, TEdgeData());
812 }
813 
814 template <class TNodeData, class TEdgeData>
815 int TNodeEDatNet<TNodeData, TEdgeData>::AddEdge(const int& SrcNId, const int& DstNId, const TEdgeData& EdgeDat) {
816  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
817  //IAssert(! IsEdge(SrcNId, DstNId));
818  if (IsEdge(SrcNId, DstNId)) {
819  GetEDat(SrcNId, DstNId) = EdgeDat;
820  return -2;
821  }
822  GetNode(SrcNId).OutNIdV.AddSorted(TPair<TInt, TEdgeData>(DstNId, EdgeDat));
823  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
824  return -1; // edge id
825 }
826 
827 template <class TNodeData, class TEdgeData>
828 void TNodeEDatNet<TNodeData, TEdgeData>::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) {
829  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
830  int pos = GetNIdPos(GetNode(SrcNId).OutNIdV, DstNId);
831  if (pos != -1) { GetNode(SrcNId).OutNIdV.Del(pos); }
832  pos = GetNode(DstNId).InNIdV.SearchBin(SrcNId);
833  if (pos != -1) { GetNode(DstNId).InNIdV.Del(pos); }
834  if (! IsDir) {
835  pos = GetNIdPos(GetNode(DstNId).OutNIdV, SrcNId);
836  if (pos != -1) { GetNode(DstNId).OutNIdV.Del(pos); }
837  pos = GetNode(SrcNId).InNIdV.SearchBin(DstNId);
838  if (pos != -1) { GetNode(SrcNId).InNIdV.Del(pos); }
839  }
840 }
841 
842 template <class TNodeData, class TEdgeData>
843 bool TNodeEDatNet<TNodeData, TEdgeData>::IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) const {
844  if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
845  if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
846  else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
847 }
848 
849 template <class TNodeData, class TEdgeData>
850 void TNodeEDatNet<TNodeData, TEdgeData>::SetEDat(const int& SrcNId, const int& DstNId, const TEdgeData& EdgeDat) {
851  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
852  IAssertR(IsEdge(SrcNId, DstNId), TStr::Fmt("Edge between %d and %d does not exist.", SrcNId, DstNId).CStr());
853  GetEDat(SrcNId, DstNId) = EdgeDat;
854 }
855 
856 template <class TNodeData, class TEdgeData>
857 bool TNodeEDatNet<TNodeData, TEdgeData>::GetEDat(const int& SrcNId, const int& DstNId, TEdgeData& EdgeDat) const {
858  if (! IsEdge(SrcNId, DstNId)) { return false; }
859  const TNode& N = GetNode(SrcNId);
860  EdgeDat = N.GetOutEDat(GetNIdPos(N.OutNIdV, DstNId));
861  return true;
862 }
863 
864 template <class TNodeData, class TEdgeData>
865 TEdgeData& TNodeEDatNet<TNodeData, TEdgeData>::GetEDat(const int& SrcNId, const int& DstNId) {
866  Assert(IsEdge(SrcNId, DstNId));
867  TNode& N = GetNode(SrcNId);
868  return N.GetOutEDat(GetNIdPos(N.OutNIdV, DstNId));
869 }
870 
871 template <class TNodeData, class TEdgeData>
872 const TEdgeData& TNodeEDatNet<TNodeData, TEdgeData>::GetEDat(const int& SrcNId, const int& DstNId) const {
873  Assert(IsEdge(SrcNId, DstNId));
874  const TNode& N = GetNode(SrcNId);
875  return N.GetOutEDat(GetNIdPos(N.OutNIdV, DstNId));
876 }
877 
878 template <class TNodeData, class TEdgeData>
879 void TNodeEDatNet<TNodeData, TEdgeData>::SetAllEDat(const TEdgeData& EdgeDat) {
880  for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) {
881  EI() = EdgeDat;
882  }
883 }
884 
885 template <class TNodeData, class TEdgeData>
886 typename TNodeEDatNet<TNodeData, TEdgeData>::TEdgeI TNodeEDatNet<TNodeData, TEdgeData>::GetEI(const int& SrcNId, const int& DstNId) const {
887  const TNodeI SrcNI = GetNI(SrcNId);
888  int NodeN = -1;
889  //SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
890  const TNIdDatPrV& NIdDatV = SrcNI.NodeHI.GetDat().OutNIdV;
891  int LValN=0, RValN=NIdDatV.Len()-1;
892  while (RValN>=LValN){
893  int ValN=(LValN+RValN)/2;
894  if (DstNId==NIdDatV[ValN].Val1){ NodeN=ValN; break; }
895  if (DstNId<NIdDatV[ValN].Val1){RValN=ValN-1;} else {LValN=ValN+1;}
896  }
897  if (NodeN == -1) { return EndEI(); }
898  else { return TEdgeI(SrcNI, EndNI(), NodeN); }
899 }
900 
901 template <class TNodeData, class TEdgeData>
903  NIdV.Reserve(GetNodes(), 0);
904  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
905  NIdV.Add(NodeH.GetKey(N)); }
906 }
907 
908 template <class TNodeData, class TEdgeData>
909 void TNodeEDatNet<TNodeData, TEdgeData>::Defrag(const bool& OnlyNodeLinks) {
910  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n);) {
911  TNode& Node = NodeH[n];
912  Node.InNIdV.Pack(); Node.OutNIdV.Pack();
913  }
914  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
915  NodeH.Defrag();
916  }
917 }
918 
919 template <class TNodeData, class TEdgeData>
920 bool TNodeEDatNet<TNodeData, TEdgeData>::IsOk(const bool& ThrowExcept) const {
921  bool RetVal = true;
922  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
923  const TNode& Node = NodeH[N];
924  if (! Node.OutNIdV.IsSorted()) {
925  const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
926  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
927  }
928  if (! Node.InNIdV.IsSorted()) {
929  const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
930  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
931  }
932  // check out-edges
933  int prevNId = -1;
934  for (int e = 0; e < Node.GetOutDeg(); e++) {
935  if (! IsNode(Node.GetOutNId(e))) {
936  const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
937  Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
938  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
939  }
940  if (e > 0 && prevNId == Node.GetOutNId(e)) {
941  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
942  Node.GetId(), Node.GetId(), Node.GetOutNId(e));
943  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
944  }
945  prevNId = Node.GetOutNId(e);
946  }
947  // check in-edges
948  prevNId = -1;
949  for (int e = 0; e < Node.GetInDeg(); e++) {
950  if (! IsNode(Node.GetInNId(e))) {
951  const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
952  Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
953  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
954  }
955  if (e > 0 && prevNId == Node.GetInNId(e)) {
956  const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
957  Node.GetId(), Node.GetId(), Node.GetInNId(e));
958  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
959  }
960  prevNId = Node.GetInNId(e);
961  }
962  }
963  return RetVal;
964 }
965 
967 // Common network types
974 
975 //#//////////////////////////////////////////////
977 template <class TNodeData, class TEdgeData>
979 public:
980  typedef TNodeData TNodeDat;
981  typedef TEdgeData TEdgeDat;
983  typedef TPt<TNet> PNet;
984 public:
985  class TNode {
986  private:
989  TNodeData NodeDat;
990  public:
991  TNode() : Id(-1), InEIdV(), OutEIdV(), NodeDat() { }
992  TNode(const int& NId) : Id(NId), InEIdV(), OutEIdV(), NodeDat() { }
993  TNode(const int& NId, const TNodeData& NodeData) : Id(NId), InEIdV(), OutEIdV(), NodeDat(NodeData) { }
994  TNode(const TNode& Node) : Id(Node.Id), InEIdV(Node.InEIdV), OutEIdV(Node.OutEIdV), NodeDat(Node.NodeDat) { }
995  TNode(TSIn& SIn) : Id(SIn), InEIdV(SIn), OutEIdV(SIn), NodeDat(SIn) { }
996  void Save(TSOut& SOut) const { Id.Save(SOut); InEIdV.Save(SOut); OutEIdV.Save(SOut); NodeDat.Save(SOut); }
997  bool operator < (const TNode& Node) const { return NodeDat < Node.NodeDat; }
998  int GetId() const { return Id; }
999  int GetDeg() const { return GetInDeg() + GetOutDeg(); }
1000  int GetInDeg() const { return InEIdV.Len(); }
1001  int GetOutDeg() const { return OutEIdV.Len(); }
1002  const TNodeData& GetDat() const { return NodeDat; }
1003  TNodeData& GetDat() { return NodeDat; }
1004  int GetInEId(const int& NodeN) const { return InEIdV[NodeN]; }
1005  int GetOutEId(const int& NodeN) const { return OutEIdV[NodeN]; }
1006  int GetNbrEId(const int& EdgeN) const { return EdgeN<GetOutDeg()?GetOutEId(EdgeN):GetInEId(EdgeN-GetOutDeg()); }
1007  bool IsInEId(const int& EId) const { return InEIdV.SearchBin(EId) != -1; }
1008  bool IsOutEId(const int& EId) const { return OutEIdV.SearchBin(EId) != -1; }
1009  bool IsNbrEId(const int& EId) const { return IsInEId(EId) || IsOutEId(EId); }
1010  friend class TNodeEdgeNet<TNodeData, TEdgeData>;
1011  };
1012 
1013  class TEdge {
1014  private:
1016  TEdgeData EdgeDat;
1017  public:
1018  TEdge() : Id(-1), SrcNId(-1), DstNId(-1), EdgeDat() { }
1019  TEdge(const int& EId, const int& SourceNId, const int& DestNId) : Id(EId), SrcNId(SourceNId), DstNId(DestNId), EdgeDat() { }
1020  TEdge(const int& EId, const int& SourceNId, const int& DestNId, const TEdgeData& EdgeData) : Id(EId), SrcNId(SourceNId), DstNId(DestNId), EdgeDat(EdgeData) { }
1021  TEdge(const TEdge& Edge) : Id(Edge.Id), SrcNId(Edge.SrcNId), DstNId(Edge.DstNId), EdgeDat(Edge.EdgeDat) { }
1022  TEdge(TSIn& SIn) : Id(SIn), SrcNId(SIn), DstNId(SIn), EdgeDat(SIn) { }
1023  void Save(TSOut& SOut) const { Id.Save(SOut); SrcNId.Save(SOut); DstNId.Save(SOut); EdgeDat.Save(SOut); }
1024  bool operator < (const TEdge& Edge) const { return EdgeDat < Edge.EdgeDat; }
1025  int GetId() const { return Id; }
1026  int GetSrcNId() const { return SrcNId; }
1027  int GetDstNId() const { return DstNId; }
1028  const TEdgeData& GetDat() const { return EdgeDat; }
1029  TEdgeData& GetDat() { return EdgeDat; }
1030  friend class TNodeEdgeNet;
1031  };
1032 
1034  class TNodeI {
1035  private:
1039  public:
1040  TNodeI() : NodeHI(), Net(NULL) { }
1041  TNodeI(const THashIter& NodeHIter, const TNodeEdgeNet* NetPt) : NodeHI(NodeHIter), Net((TNodeEdgeNet *)NetPt) { }
1042  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Net(NodeI.Net) { }
1043  TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; Net=NodeI.Net; return *this; }
1045  TNodeI& operator++ (int) { NodeHI++; return *this; }
1046  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
1047  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
1049  int GetId() const { return NodeHI.GetDat().GetId(); }
1051  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
1053  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
1055  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
1057 
1059  int GetInNId(const int& EdgeN) const { return Net->GetEdge(NodeHI.GetDat().GetInEId(EdgeN)).GetSrcNId(); }
1061 
1063  int GetOutNId(const int& EdgeN) const { return Net->GetEdge(NodeHI.GetDat().GetOutEId(EdgeN)).GetDstNId(); }
1065 
1067  int GetNbrNId(const int& EdgeN) const { const TEdge& E = Net->GetEdge(NodeHI.GetDat().GetNbrEId(EdgeN));
1068  return GetId()==E.GetSrcNId() ? E.GetDstNId():E.GetSrcNId(); }
1070  bool IsInNId(const int& NId) const;
1072  bool IsOutNId(const int& NId) const;
1074  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
1075  // node data
1076  const TNodeData& operator () () const { return NodeHI.GetDat().GetDat(); }
1077  TNodeData& operator () () { return NodeHI.GetDat().GetDat(); }
1078  const TNodeData& GetDat() const { return NodeHI.GetDat().GetDat(); }
1079  TNodeData& GetDat() { return NodeHI.GetDat().GetDat(); }
1080  const TNodeData& GetInNDat(const int& EdgeN) const { return Net->GetNDat(GetInNId(EdgeN)); }
1081  TNodeData& GetInNDat(const int& EdgeN) { return Net->GetNodeDat(GetInNId(EdgeN)); }
1082  const TNodeData& GetOutNDat(const int& EdgeN) const { return Net->GetNDat(GetOutNId(EdgeN)); }
1083  TNodeData& GetOutNDat(const int& EdgeN) { return Net->GetNDat(GetOutNId(EdgeN)); }
1084  const TNodeData& GetNbrNDat(const int& EdgeN) const { return Net->GetNDat(GetNbrNId(EdgeN)); }
1085  TNodeData& GetNbrNDat(const int& EdgeN) { return Net->GetNDat(GetNbrNId(EdgeN)); }
1086  // edges
1088  int GetInEId(const int& EdgeN) const { return NodeHI.GetDat().GetInEId(EdgeN); }
1090  int GetOutEId(const int& EdgeN) const { return NodeHI.GetDat().GetOutEId(EdgeN); }
1092  int GetNbrEId(const int& EdgeN) const { return NodeHI.GetDat().GetNbrEId(EdgeN); }
1094  bool IsInEId(const int& EId) const { return NodeHI.GetDat().IsInEId(EId); }
1096  bool IsOutEId(const int& EId) const { return NodeHI.GetDat().IsOutEId(EId); }
1098  bool IsNbrEId(const int& EId) const { return NodeHI.GetDat().IsNbrEId(EId); }
1099  // edge data
1100  TEdgeDat& GetInEDat(const int& EdgeN) { return Net->GetEDat(GetInEId(EdgeN)); }
1101  const TEdgeDat& GetInEDat(const int& EdgeN) const { return Net->GetEDat(GetInEId(EdgeN)); }
1102  TEdgeDat& GetOutEDat(const int& EdgeN) { return Net->GetEDat(GetOutEId(EdgeN)); }
1103  const TEdgeDat& GetOutEDat(const int& EdgeN) const { return Net->GetEDat(GetOutEId(EdgeN)); }
1104  TEdgeDat& GetNbrEDat(const int& EdgeN) { return Net->GetEDat(GetNbrEId(EdgeN)); }
1105  const TEdgeDat& GetNbrEDat(const int& EdgeN) const { return Net->GetEDat(GetNbrEId(EdgeN)); }
1106  friend class TNodeEdgeNet;
1107  };
1108 
1110  class TEdgeI {
1111  private:
1115  public:
1116  TEdgeI() : EdgeHI(), Net(NULL) { }
1117  TEdgeI(const THashIter& EdgeHIter, const TNodeEdgeNet *NetPt) : EdgeHI(EdgeHIter), Net((TNodeEdgeNet *) NetPt) { }
1118  TEdgeI(const TEdgeI& EdgeI) : EdgeHI(EdgeI.EdgeHI), Net(EdgeI.Net) { }
1119  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { EdgeHI=EdgeI.EdgeHI; Net=EdgeI.Net; } return *this; }
1120  TEdgeI& operator++ (int) { EdgeHI++; return *this; }
1121  bool operator < (const TEdgeI& EdgeI) const { return EdgeHI < EdgeI.EdgeHI; }
1122  bool operator == (const TEdgeI& EdgeI) const { return EdgeHI == EdgeI.EdgeHI; }
1124  int GetId() const { return EdgeHI.GetDat().GetId(); }
1126  int GetSrcNId() const { return EdgeHI.GetDat().GetSrcNId(); }
1128  int GetDstNId() const { return EdgeHI.GetDat().GetDstNId(); }
1129  const TEdgeData& operator () () const { return EdgeHI.GetDat().GetDat(); }
1130  TEdgeData& operator () () { return EdgeHI.GetDat().GetDat(); }
1131  const TEdgeData& GetDat() const { return EdgeHI.GetDat().GetDat(); }
1132  TEdgeData& GetDat() { return EdgeHI.GetDat().GetDat(); }
1133  const TNodeData& GetSrcNDat() const { return Net->GetNDat(GetSrcNId()); }
1134  TNodeData& GetSrcNDat() { return Net->GetNDat(GetSrcNId()); }
1135  const TNodeData& GetDstNDat() const { return Net->GetNDat(GetDstNId()); }
1136  TNodeData& GetDstNDat() { return Net->GetNDat(GetDstNId()); }
1137  friend class TNodeEdgeNet;
1138  };
1139 
1140 private:
1141  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
1142  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
1143  const TNode& GetNodeKId(const int& NodeKeyId) const { return NodeH[NodeKeyId]; }
1144  TEdge& GetEdge(const int& EId) { return EdgeH.GetDat(EId); }
1145  const TEdge& GetEdge(const int& EId) const { return EdgeH.GetDat(EId); }
1146  const TEdge& GetEdgeKId(const int& EdgeKeyId) const { return EdgeH[EdgeKeyId]; }
1147 protected:
1152 public:
1153  TNodeEdgeNet() : CRef(), MxNId(0), MxEId(0) { }
1155  explicit TNodeEdgeNet(const int& Nodes, const int& Edges) : CRef(), MxNId(0), MxEId(0) { Reserve(Nodes, Edges); }
1156  TNodeEdgeNet(const TNodeEdgeNet& Net) : MxNId(Net.MxNId), MxEId(Net.MxEId), NodeH(Net.NodeH), EdgeH(Net.EdgeH) { }
1158  TNodeEdgeNet(TSIn& SIn) : MxNId(SIn), MxEId(SIn), NodeH(SIn), EdgeH(SIn) { }
1159  virtual ~TNodeEdgeNet() { }
1161  virtual void Save(TSOut& SOut) const { MxNId.Save(SOut); MxEId.Save(SOut); NodeH.Save(SOut); EdgeH.Save(SOut); }
1163  static PNet New() { return PNet(new TNet()); }
1165  static PNet Load(TSIn& SIn) { return PNet(new TNet(SIn)); }
1167  bool HasFlag(const TGraphFlag& Flag) const;
1169  if (this!=&Net) { NodeH=Net.NodeH; EdgeH=Net.EdgeH; MxNId=Net.MxNId; MxEId=Net.MxEId; } return *this; }
1170  // nodes
1172  int GetNodes() const { return NodeH.Len(); }
1174 
1178  int AddNode(int NId = -1);
1180 
1184  int AddNode(int NId, const TNodeData& NodeDat);
1186  int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId(), NodeI.GetDat()); }
1188 
1190  void DelNode(const int& NId);
1192  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
1194  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
1196  TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); }
1198  TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); }
1200  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); }
1202  void SetNDat(const int& NId, const TNodeData& NodeDat);
1204  TNodeData& GetNDat(const int& NId) { return NodeH.GetDat(NId).NodeDat; }
1206  const TNodeData& GetNDat(const int& NId) const { return NodeH.GetDat(NId).NodeDat; }
1208  int GetMxNId() const { return MxNId; }
1209 
1210  // edges
1212  int GetEdges() const { return EdgeH.Len(); }
1214  int GetUniqEdges(const bool& IsDir=true) const;
1216 
1221  int AddEdge(const int& SrcNId, const int& DstNId, int EId = -1);
1223 
1228  int AddEdge(const int& SrcNId, const int& DstNId, int EId, const TEdgeData& EdgeDat);
1230  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI.GetId(), EdgeI.GetDat()); }
1232  void DelEdge(const int& EId);
1234 
1238  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
1240  bool IsEdge(const int& EId) const { return EdgeH.IsKey(EId); }
1242  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const { int EId; return IsEdge(SrcNId, DstNId, EId, IsDir); }
1244  bool IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir = true) const;
1245  int GetEId(const int& SrcNId, const int& DstNId) const { int EId; return IsEdge(SrcNId, DstNId, EId)?EId:-1; }
1247  TEdgeI BegEI() const { return TEdgeI(EdgeH.BegI(), this); }
1249  TEdgeI EndEI() const { return TEdgeI(EdgeH.EndI(), this); }
1251  TEdgeI GetEI(const int& EId) const { return TEdgeI(EdgeH.GetI(EId), this); }
1253  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const { return GetEI(GetEId(SrcNId, DstNId)); }
1255  void SetEDat(const int& EId, const TEdgeData& EdgeDat);
1257  TEdgeData& GetEDat(const int& EId) { return EdgeH.GetDat(EId).EdgeDat; }
1259  const TEdgeData& GetEDat(const int& EId) const { return EdgeH.GetDat(EId).EdgeDat; }
1261  void SetAllEDat(const TEdgeData& EdgeDat);
1262 
1264  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
1266  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
1268  int GetRndEId(TRnd& Rnd=TInt::Rnd) { return EdgeH.GetKey(EdgeH.GetRndKeyId(Rnd, 0.8)); }
1270  TEdgeI GetRndEI(TRnd& Rnd=TInt::Rnd) { return GetEI(GetRndEId(Rnd)); }
1272  void GetNIdV(TIntV& NIdV) const;
1274  void GetEIdV(TIntV& EIdV) const;
1275 
1277  bool Empty() const { return GetNodes()==0; }
1279  void Clr() { MxNId=0; MxEId=0; NodeH.Clr(); EdgeH.Clr(); }
1281  void Reserve(const int& Nodes, const int& Edges) {
1282  if (Nodes>0) { NodeH.Gen(Nodes/2); } if (Edges>0) { EdgeH.Gen(Edges/2); } }
1284  void SortNIdById(const bool& Asc=true) { NodeH.SortByKey(Asc); }
1286  void SortNIdByDat(const bool& Asc=true) { NodeH.SortByDat(Asc); }
1288  void SortEIdById(const bool& Asc=true) { EdgeH.SortByKey(Asc); }
1290  void SortEIdByDat(const bool& Asc=true) { EdgeH.SortByDat(Asc); }
1292 
1297  void Defrag(const bool& OnlyNodeLinks=false);
1299 
1302  bool IsOk(const bool& ThrowExcept=true) const;
1303 
1304  friend class TPt<TNodeEdgeNet<TNodeData, TEdgeData> >;
1305 };
1306 
1307 // set flags
1308 namespace TSnap {
1309 template <class TNodeData, class TEdgeData> struct IsMultiGraph<TNodeEdgeNet<TNodeData, TEdgeData> > { enum { Val = 1 }; };
1310 template <class TNodeData, class TEdgeData> struct IsDirected<TNodeEdgeNet<TNodeData, TEdgeData> > { enum { Val = 1 }; };
1311 template <class TNodeData, class TEdgeData> struct IsNodeDat<TNodeEdgeNet<TNodeData, TEdgeData> > { enum { Val = 1 }; };
1312 template <class TNodeData, class TEdgeData> struct IsEdgeDat<TNodeEdgeNet<TNodeData, TEdgeData> > { enum { Val = 1 }; };
1313 }
1314 
1315 template <class TNodeData, class TEdgeData>
1317  return HasGraphFlag(typename TNet, Flag);
1318 }
1319 
1320 template <class TNodeData, class TEdgeData>
1322  const TNode& Node = NodeHI.GetDat();
1323  for (int edge = 0; edge < Node.GetInDeg(); edge++) {
1324  if (NId == Net->GetEdge(Node.GetInEId(edge)).GetSrcNId())
1325  return true;
1326  }
1327  return false;
1328 }
1329 
1330 template <class TNodeData, class TEdgeData>
1332  const TNode& Node = NodeHI.GetDat();
1333  for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
1334  if (NId == Net->GetEdge(Node.GetOutEId(edge)).GetDstNId())
1335  return true;
1336  }
1337  return false;
1338 }
1339 
1340 template <class TNodeData, class TEdgeData>
1342  if (NId == -1) {
1343  NId = MxNId; MxNId++;
1344  } else {
1345  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
1346  MxNId = TMath::Mx(NId+1, MxNId());
1347  }
1348  NodeH.AddDat(NId, TNode(NId));
1349  return NId;
1350 }
1351 
1352 template <class TNodeData, class TEdgeData>
1353 int TNodeEdgeNet<TNodeData, TEdgeData>::AddNode(int NId, const TNodeData& NodeDat) {
1354  if (NId == -1) {
1355  NId = MxNId; MxNId++;
1356  } else {
1357  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
1358  MxNId = TMath::Mx(NId+1, MxNId());
1359  }
1360  NodeH.AddDat(NId, TNode(NId, NodeDat));
1361  return NId;
1362 }
1363 
1364 template <class TNodeData, class TEdgeData>
1366  const TNode& Node = GetNode(NId);
1367  for (int out = 0; out < Node.GetOutDeg(); out++) {
1368  const int EId = Node.GetOutEId(out);
1369  const TEdge& Edge = GetEdge(EId);
1370  IAssert(Edge.GetSrcNId() == NId);
1371  GetNode(Edge.GetDstNId()).InEIdV.DelIfIn(EId);
1372  EdgeH.DelKey(EId);
1373  }
1374  for (int in = 0; in < Node.GetInDeg(); in++) {
1375  const int EId = Node.GetInEId(in);
1376  const TEdge& Edge = GetEdge(EId);
1377  IAssert(Edge.GetDstNId() == NId);
1378  GetNode(Edge.GetSrcNId()).OutEIdV.DelIfIn(EId);
1379  EdgeH.DelKey(EId);
1380  }
1381  NodeH.DelKey(NId);
1382 }
1383 
1384 template <class TNodeData, class TEdgeData>
1385 void TNodeEdgeNet<TNodeData, TEdgeData>::SetNDat(const int& NId, const TNodeData& NodeDat) {
1386  IAssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist.", NId).CStr());
1387  NodeH.GetDat(NId).NodeDat = NodeDat;
1388 }
1389 
1390 template <class TNodeData, class TEdgeData>
1392  TIntPrSet UniqESet(GetEdges());
1393  for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) {
1394  const int Src = EI.GetSrcNId();
1395  const int Dst = EI.GetDstNId();
1396  if (IsDir) { UniqESet.AddKey(TIntPr(Src, Dst)); }
1397  else { UniqESet.AddKey(TIntPr(TMath::Mn(Src, Dst), TMath::Mx(Src, Dst))); }
1398  }
1399  return UniqESet.Len();
1400 }
1401 
1402 template <class TNodeData, class TEdgeData>
1403 int TNodeEdgeNet<TNodeData, TEdgeData>::AddEdge(const int& SrcNId, const int& DstNId, int EId) {
1404  if (EId == -1) { EId = MxEId; MxEId++; }
1405  else { MxEId = TMath::Mx(EId+1, MxEId()); }
1406  IAssertR(!IsEdge(EId), TStr::Fmt("EdgeId %d already exists", EId));
1407  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
1408  EdgeH.AddDat(EId, TEdge(EId, SrcNId, DstNId));
1409  GetNode(SrcNId).OutEIdV.AddSorted(EId);
1410  GetNode(DstNId).InEIdV.AddSorted(EId);
1411  return EId;
1412 }
1413 
1414 template <class TNodeData, class TEdgeData>
1415 int TNodeEdgeNet<TNodeData, TEdgeData>::AddEdge(const int& SrcNId, const int& DstNId, int EId, const TEdgeData& EdgeDat) {
1416  if (EId == -1) { EId = MxEId; MxEId++; }
1417  else { MxEId = TMath::Mx(EId+1, MxEId()); }
1418  IAssertR(!IsEdge(EId), TStr::Fmt("EdgeId %d already exists", EId));
1419  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
1420  EdgeH.AddDat(EId, TEdge(EId, SrcNId, DstNId, EdgeDat));
1421  GetNode(SrcNId).OutEIdV.AddSorted(EId);
1422  GetNode(DstNId).InEIdV.AddSorted(EId);
1423  return EId;
1424 }
1425 
1426 template <class TNodeData, class TEdgeData>
1428  IAssert(IsEdge(EId));
1429  const int SrcNId = GetEdge(EId).GetSrcNId();
1430  const int DstNId = GetEdge(EId).GetDstNId();
1431  GetNode(SrcNId).OutEIdV.DelIfIn(EId);
1432  GetNode(DstNId).InEIdV.DelIfIn(EId);
1433  EdgeH.DelKey(EId);
1434 }
1435 
1436 template <class TNodeData, class TEdgeData>
1437 void TNodeEdgeNet<TNodeData, TEdgeData>::DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir) {
1438  int EId;
1439  IAssert(IsEdge(SrcNId, DstNId, EId, IsDir));
1440  GetNode(SrcNId).OutEIdV.DelIfIn(EId);
1441  GetNode(DstNId).InEIdV.DelIfIn(EId);
1442  EdgeH.DelKey(EId);
1443 }
1444 
1445 template <class TNodeData, class TEdgeData>
1446 bool TNodeEdgeNet<TNodeData, TEdgeData>::IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir) const {
1447  if (! IsNode(SrcNId)) { return false; }
1448  if (! IsNode(DstNId)) { return false; }
1449  const TNode& SrcNode = GetNode(SrcNId);
1450  for (int edge = 0; edge < SrcNode.GetOutDeg(); edge++) {
1451  const TEdge& Edge = GetEdge(SrcNode.GetOutEId(edge));
1452  if (DstNId == Edge.GetDstNId()) {
1453  EId = Edge.GetId(); return true; }
1454  }
1455  if (! IsDir) {
1456  for (int edge = 0; edge < SrcNode.GetInDeg(); edge++) {
1457  const TEdge& Edge = GetEdge(SrcNode.GetInEId(edge));
1458  if (DstNId == Edge.GetSrcNId()) {
1459  EId = Edge.GetId(); return true; }
1460  }
1461  }
1462  return false;
1463 }
1464 
1465 template <class TNodeData, class TEdgeData>
1466 void TNodeEdgeNet<TNodeData, TEdgeData>::SetEDat(const int& EId, const TEdgeData& EdgeDat) {
1467  IAssertR(IsEdge(EId), TStr::Fmt("EdgeId %d does not exist.", EId).CStr());
1468  GetEI(EId).GetDat() = EdgeDat;
1469 }
1470 
1471 template <class TNodeData, class TEdgeData>
1472 void TNodeEdgeNet<TNodeData, TEdgeData>::SetAllEDat(const TEdgeData& EdgeDat) {
1473  for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) {
1474  EI() = EdgeDat;
1475  }
1476 }
1477 
1478 
1479 template <class TNodeData, class TEdgeData>
1481  NIdV.Gen(GetNodes(), 0);
1482  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N);) {
1483  NIdV.Add(NodeH.GetKey(N));
1484  }
1485 }
1486 
1487 template <class TNodeData, class TEdgeData>
1489  EIdV.Gen(GetEdges(), 0);
1490  for (int E=EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E);) {
1491  EIdV.Add(EdgeH.GetKey(E));
1492  }
1493 }
1494 
1495 template <class TNodeData, class TEdgeData>
1496 void TNodeEdgeNet<TNodeData, TEdgeData>::Defrag(const bool& OnlyNodeLinks) {
1497  for (int kid = NodeH.FFirstKeyId(); NodeH.FNextKeyId(kid);) {
1498  TNode& Node = NodeH[kid];
1499  Node.InEIdV.Pack(); Node.OutEIdV.Pack();
1500  }
1501  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) { NodeH.Defrag(); }
1502  if (! OnlyNodeLinks && ! EdgeH.IsKeyIdEqKeyN()) { EdgeH.Defrag(); }
1503 }
1504 
1505 template <class TNodeData, class TEdgeData>
1506 bool TNodeEdgeNet<TNodeData, TEdgeData>::IsOk(const bool& ThrowExcept) const {
1507  bool RetVal = true;
1508  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
1509  const TNode& Node = NodeH[N];
1510  if (! Node.OutEIdV.IsSorted()) {
1511  const TStr Msg = TStr::Fmt("Out-edge list of node %d is not sorted.", Node.GetId());
1512  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
1513  }
1514  if (! Node.InEIdV.IsSorted()) {
1515  const TStr Msg = TStr::Fmt("In-edge list of node %d is not sorted.", Node.GetId());
1516  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
1517  }
1518  // check out-edge ids
1519  int prevEId = -1;
1520  for (int e = 0; e < Node.GetOutDeg(); e++) {
1521  if (! IsEdge(Node.GetOutEId(e))) {
1522  const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.", Node.GetOutEId(e), Node.GetId());
1523  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
1524  }
1525  if (e > 0 && prevEId == Node.GetOutEId(e)) {
1526  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetOutEId(e));
1527  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
1528  }
1529  prevEId = Node.GetOutEId(e);
1530  }
1531  // check in-edge ids
1532  prevEId = -1;
1533  for (int e = 0; e < Node.GetInDeg(); e++) {
1534  if (! IsEdge(Node.GetInEId(e))) {
1535  const TStr Msg = TStr::Fmt("Out-edge id %d of node %d does not exist.", Node.GetInEId(e), Node.GetId());
1536  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
1537  }
1538  if (e > 0 && prevEId == Node.GetInEId(e)) {
1539  const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge id %d.", Node.GetId(), Node.GetInEId(e));
1540  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
1541  }
1542  prevEId = Node.GetInEId(e);
1543  }
1544  }
1545  for (int E = EdgeH.FFirstKeyId(); EdgeH.FNextKeyId(E); ) {
1546  const TEdge& Edge = EdgeH[E];
1547  if (! IsNode(Edge.GetSrcNId())) {
1548  const TStr Msg = TStr::Fmt("Edge %d source node %d does not exist.", Edge.GetId(), Edge.GetSrcNId());
1549  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
1550  }
1551  if (! IsNode(Edge.GetDstNId())) {
1552  const TStr Msg = TStr::Fmt("Edge %d destination node %d does not exist.", Edge.GetId(), Edge.GetDstNId());
1553  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
1554  }
1555  }
1556  return RetVal;
1557 }
1558 
1560 // Common Node-Edge Network Types
1565 
1566 class TNEANet;
1568 typedef TPt<TNEANet> PNEANet;
1569 
1570 //#//////////////////////////////////////////////
1572 
1587 class TNEANet {
1588 public:
1589  typedef TNEANet TNet;
1591 public:
1592  class TNode {
1593  private:
1595  TIntV InEIdV, OutEIdV;
1596  public:
1597  TNode() : Id(-1), InEIdV(), OutEIdV() { }
1598  TNode(const int& NId) : Id(NId), InEIdV(), OutEIdV() { }
1599  TNode(const TNode& Node) : Id(Node.Id), InEIdV(Node.InEIdV), OutEIdV(Node.OutEIdV) { }
1600  TNode(TSIn& SIn) : Id(SIn), InEIdV(SIn), OutEIdV(SIn) { }
1601  void Save(TSOut& SOut) const { Id.Save(SOut); InEIdV.Save(SOut); OutEIdV.Save(SOut); }
1602  int GetId() const { return Id; }
1603  int GetDeg() const { return GetInDeg() + GetOutDeg(); }
1604  int GetInDeg() const { return InEIdV.Len(); }
1605  int GetOutDeg() const { return OutEIdV.Len(); }
1606  int GetInEId(const int& EdgeN) const { return InEIdV[EdgeN]; }
1607  int GetOutEId(const int& EdgeN) const { return OutEIdV[EdgeN]; }
1608  int GetNbrEId(const int& EdgeN) const { return EdgeN<GetOutDeg()?GetOutEId(EdgeN):GetInEId(EdgeN-GetOutDeg()); }
1609  bool IsInEId(const int& EId) const { return InEIdV.SearchBin(EId) != -1; }
1610  bool IsOutEId(const int& EId) const { return OutEIdV.SearchBin(EId) != -1; }
1611  friend class TNEANet;
1612  };
1613  class TEdge {
1614  private:
1615  TInt Id, SrcNId, DstNId;
1616  public:
1617  TEdge() : Id(-1), SrcNId(-1), DstNId(-1) { }
1618  TEdge(const int& EId, const int& SourceNId, const int& DestNId) : Id(EId), SrcNId(SourceNId), DstNId(DestNId) { }
1619  TEdge(const TEdge& Edge) : Id(Edge.Id), SrcNId(Edge.SrcNId), DstNId(Edge.DstNId) { }
1620  TEdge(TSIn& SIn) : Id(SIn), SrcNId(SIn), DstNId(SIn) { }
1621  void Save(TSOut& SOut) const { Id.Save(SOut); SrcNId.Save(SOut); DstNId.Save(SOut); }
1622  int GetId() const { return Id; }
1623  int GetSrcNId() const { return SrcNId; }
1624  int GetDstNId() const { return DstNId; }
1625  friend class TNEANet;
1626  };
1628  class TNodeI {
1629  private:
1632  const TNEANet *Graph;
1633  public:
1634  TNodeI() : NodeHI(), Graph(NULL) { }
1635  TNodeI(const THashIter& NodeHIter, const TNEANet* GraphPt) : NodeHI(NodeHIter), Graph(GraphPt) { }
1636  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Graph(NodeI.Graph) { }
1637  TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; Graph=NodeI.Graph; return *this; }
1639  TNodeI& operator++ (int) { NodeHI++; return *this; }
1640  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
1641  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
1643  int GetId() const { return NodeHI.GetDat().GetId(); }
1645  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
1647  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
1649  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
1651 
1653  int GetInNId(const int& EdgeN) const { return Graph->GetEdge(NodeHI.GetDat().GetInEId(EdgeN)).GetSrcNId(); }
1655 
1657  int GetOutNId(const int& EdgeN) const { return Graph->GetEdge(NodeHI.GetDat().GetOutEId(EdgeN)).GetDstNId(); }
1659 
1661  int GetNbrNId(const int& EdgeN) const { const TEdge& E = Graph->GetEdge(NodeHI.GetDat().GetNbrEId(EdgeN)); return GetId()==E.GetSrcNId() ? E.GetDstNId():E.GetSrcNId(); }
1663  bool IsInNId(const int& NId) const;
1665  bool IsOutNId(const int& NId) const;
1667  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
1669  int GetInEId(const int& EdgeN) const { return NodeHI.GetDat().GetInEId(EdgeN); }
1671  int GetOutEId(const int& EdgeN) const { return NodeHI.GetDat().GetOutEId(EdgeN); }
1673  int GetNbrEId(const int& EdgeN) const { return NodeHI.GetDat().GetNbrEId(EdgeN); }
1675  bool IsInEId(const int& EId) const { return NodeHI.GetDat().IsInEId(EId); }
1677  bool IsOutEId(const int& EId) const { return NodeHI.GetDat().IsOutEId(EId); }
1679  bool IsNbrEId(const int& EId) const { return IsInEId(EId) || IsOutEId(EId); }
1681  void GetAttrNames(TStrV& Names) const { Graph->AttrNameNI(GetId(), Names); }
1683  void GetAttrVal(TStrV& Val) const { Graph->AttrValueNI(GetId(), Val); }
1685  void GetIntAttrNames(TStrV& Names) const { Graph->IntAttrNameNI(GetId(), Names); }
1687  void GetIntAttrVal(TIntV& Val) const { Graph->IntAttrValueNI(GetId(), Val); }
1689  void GetStrAttrNames(TStrV& Names) const { Graph->StrAttrNameNI(GetId(), Names); }
1691  void GetStrAttrVal(TStrV& Val) const { Graph->StrAttrValueNI(GetId(), Val); }
1693  void GetFltAttrNames(TStrV& Names) const { Graph->FltAttrNameNI(GetId(), Names); }
1695  void GetFltAttrVal(TFltV& Val) const { Graph->FltAttrValueNI(GetId(), Val); }
1696  friend class TNEANet;
1697  };
1699  class TEdgeI {
1700  private:
1703  const TNEANet *Graph;
1704  public:
1705  TEdgeI() : EdgeHI(), Graph(NULL) { }
1706  TEdgeI(const THashIter& EdgeHIter, const TNEANet *GraphPt) : EdgeHI(EdgeHIter), Graph(GraphPt) { }
1707  TEdgeI(const TEdgeI& EdgeI) : EdgeHI(EdgeI.EdgeHI), Graph(EdgeI.Graph) { }
1708  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { EdgeHI=EdgeI.EdgeHI; Graph=EdgeI.Graph; } return *this; }
1710  TEdgeI& operator++ (int) { EdgeHI++; return *this; }
1711  bool operator < (const TEdgeI& EdgeI) const { return EdgeHI < EdgeI.EdgeHI; }
1712  bool operator == (const TEdgeI& EdgeI) const { return EdgeHI == EdgeI.EdgeHI; }
1714  int GetId() const { return EdgeHI.GetDat().GetId(); }
1716  int GetSrcNId() const { return EdgeHI.GetDat().GetSrcNId(); }
1718  int GetDstNId() const { return EdgeHI.GetDat().GetDstNId(); }
1720  void GetAttrNames(TStrV& Names) const { Graph->AttrNameEI(GetId(), Names); }
1722  void GetAttrVal(TStrV& Val) const { Graph->AttrValueEI(GetId(), Val); }
1724  void GetIntAttrNames(TStrV& Names) const { Graph->IntAttrNameEI(GetId(), Names); }
1726  void GetIntAttrVal(TIntV& Val) const { Graph->IntAttrValueEI(GetId(), Val); }
1728  void GetStrAttrNames(TStrV& Names) const { Graph->StrAttrNameEI(GetId(), Names); }
1730  void GetStrAttrVal(TStrV& Val) const { Graph->StrAttrValueEI(GetId(), Val); }
1732  void GetFltAttrNames(TStrV& Names) const { Graph->FltAttrNameEI(GetId(), Names); }
1734  void GetFltAttrVal(TFltV& Val) const { Graph->FltAttrValueEI(GetId(), Val); }
1735  friend class TNEANet;
1736  };
1737 
1739  class TAIntI {
1740  private:
1743  bool isNode;
1745  const TNEANet *Graph;
1746  public:
1747  TAIntI() : HI(), attr(), Graph(NULL) { }
1748  TAIntI(const TIntVecIter& HIter, TStr attribute, bool isEdgeIter, const TNEANet* GraphPt) : HI(HIter), attr(), Graph(GraphPt) { isNode = !isEdgeIter; attr = attribute; }
1749  TAIntI(const TAIntI& I) : HI(I.HI), attr(I.attr), Graph(I.Graph) { isNode = I.isNode; }
1750  TAIntI& operator = (const TAIntI& I) { HI = I.HI; Graph=I.Graph; isNode = I.isNode; attr = I.attr; return *this; }
1751  bool operator < (const TAIntI& I) const { return HI < I.HI; }
1752  bool operator == (const TAIntI& I) const { return HI == I.HI; }
1754  TInt GetDat() const { return HI[0]; }
1756  bool IsDeleted() const { return isNode ? GetDat() == Graph->GetIntAttrDefaultN(attr) : GetDat() == Graph->GetIntAttrDefaultE(attr); };
1757  TAIntI& operator++(int) { HI++; return *this; }
1758  friend class TNEANet;
1759  };
1760 
1762  class TAStrI {
1763  private:
1766  bool isNode;
1768  const TNEANet *Graph;
1769  public:
1770  TAStrI() : HI(), attr(), Graph(NULL) { }
1771  TAStrI(const TStrVecIter& HIter, TStr attribute, bool isEdgeIter, const TNEANet* GraphPt) : HI(HIter), attr(), Graph(GraphPt) { isNode = !isEdgeIter; attr = attribute; }
1772  TAStrI(const TAStrI& I) : HI(I.HI), attr(I.attr), Graph(I.Graph) { isNode = I.isNode; }
1773  TAStrI& operator = (const TAStrI& I) { HI = I.HI; Graph=I.Graph; isNode = I.isNode; attr = I.attr; return *this; }
1774  bool operator < (const TAStrI& I) const { return HI < I.HI; }
1775  bool operator == (const TAStrI& I) const { return HI == I.HI; }
1777  TStr GetDat() const { return HI[0]; }
1779  bool IsDeleted() const { return isNode ? GetDat() == Graph->GetStrAttrDefaultN(attr) : GetDat() == Graph->GetStrAttrDefaultE(attr); };
1780  TAStrI& operator++(int) { HI++; return *this; }
1781  friend class TNEANet;
1782  };
1783 
1785  class TAFltI {
1786  private:
1789  bool isNode;
1791  const TNEANet *Graph;
1792  public:
1793  TAFltI() : HI(), attr(), Graph(NULL) { }
1794  TAFltI(const TFltVecIter& HIter, TStr attribute, bool isEdgeIter, const TNEANet* GraphPt) : HI(HIter), attr(), Graph(GraphPt) { isNode = !isEdgeIter; attr = attribute; }
1795  TAFltI(const TAFltI& I) : HI(I.HI), attr(I.attr), Graph(I.Graph) { isNode = I.isNode; }
1796  TAFltI& operator = (const TAFltI& I) { HI = I.HI; Graph=I.Graph; isNode = I.isNode; attr = I.attr; return *this; }
1797  bool operator < (const TAFltI& I) const { return HI < I.HI; }
1798  bool operator == (const TAFltI& I) const { return HI == I.HI; }
1800  TFlt GetDat() const { return HI[0]; }
1802  bool IsDeleted() const { return isNode ? GetDat() == Graph->GetFltAttrDefaultN(attr) : GetDat() == Graph->GetFltAttrDefaultE(attr); };
1803  TAFltI& operator++(int) { HI++; return *this; }
1804  friend class TNEANet;
1805  };
1806 
1807 private:
1808  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
1809  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
1810  TEdge& GetEdge(const int& EId) { return EdgeH.GetDat(EId); }
1811  const TEdge& GetEdge(const int& EId) const { return EdgeH.GetDat(EId); }
1812 
1814  TInt GetIntAttrDefaultN(const TStr& attribute) const { return IntDefaultsN.IsKey(attribute) ? IntDefaultsN.GetDat(attribute) : (TInt) TInt::Mn; }
1816  TStr GetStrAttrDefaultN(const TStr& attribute) const { return StrDefaultsN.IsKey(attribute) ? StrDefaultsN.GetDat(attribute) : (TStr) TStr::GetNullStr(); }
1818  TFlt GetFltAttrDefaultN(const TStr& attribute) const { return FltDefaultsN.IsKey(attribute) ? FltDefaultsN.GetDat(attribute) : (TFlt) TFlt::Mn; }
1820  TInt GetIntAttrDefaultE(const TStr& attribute) const { return IntDefaultsE.IsKey(attribute) ? IntDefaultsE.GetDat(attribute) : (TInt) TInt::Mn; }
1822  TStr GetStrAttrDefaultE(const TStr& attribute) const { return StrDefaultsE.IsKey(attribute) ? StrDefaultsE.GetDat(attribute) : (TStr) TStr::GetNullStr(); }
1824  TFlt GetFltAttrDefaultE(const TStr& attribute) const { return FltDefaultsE.IsKey(attribute) ? FltDefaultsE.GetDat(attribute) : (TFlt) TFlt::Mn; }
1825 
1826 private:
1833 
1841 public:
1842  TNEANet() : CRef(), MxNId(0), MxEId(0), NodeH(), EdgeH(),
1846  VecOfFltVecsN(), VecOfFltVecsE() { }
1848  explicit TNEANet(const int& Nodes, const int& Edges) : CRef(),
1853  { Reserve(Nodes, Edges); }
1854  TNEANet(const TNEANet& Graph) : MxNId(Graph.MxNId), MxEId(Graph.MxEId),
1855  NodeH(Graph.NodeH), EdgeH(Graph.EdgeH), KeyToIndexTypeN(), KeyToIndexTypeE(),
1860  TNEANet(TSIn& SIn) : MxNId(SIn), MxEId(SIn), NodeH(SIn), EdgeH(SIn),
1862  StrDefaultsN(SIn), StrDefaultsE(SIn), FltDefaultsN(SIn), FltDefaultsE(SIn),
1864  VecOfFltVecsN(SIn), VecOfFltVecsE(SIn) { }
1866  void Save(TSOut& SOut) const {
1867  MxNId.Save(SOut); MxEId.Save(SOut); NodeH.Save(SOut); EdgeH.Save(SOut);
1869  IntDefaultsN.Save(SOut); IntDefaultsE.Save(SOut);
1870  StrDefaultsN.Save(SOut); StrDefaultsE.Save(SOut);
1871  FltDefaultsN.Save(SOut); FltDefaultsE.Save(SOut);
1872  VecOfIntVecsN.Save(SOut); VecOfIntVecsE.Save(SOut);
1873  VecOfStrVecsN.Save(SOut); VecOfStrVecsE.Save(SOut);
1874  VecOfFltVecsN.Save(SOut); VecOfFltVecsE.Save(SOut); }
1876  static PNEANet New() { return PNEANet(new TNEANet()); }
1878 
1880  static PNEANet New(const int& Nodes, const int& Edges) { return PNEANet(new TNEANet(Nodes, Edges)); }
1882  static PNEANet Load(TSIn& SIn) { return PNEANet(new TNEANet(SIn)); }
1884  bool HasFlag(const TGraphFlag& Flag) const;
1885  TNEANet& operator = (const TNEANet& Graph) { if (this!=&Graph) {
1886  MxNId=Graph.MxNId; MxEId=Graph.MxEId; NodeH=Graph.NodeH; EdgeH=Graph.EdgeH; }
1887  return *this; }
1888 
1890  int GetNodes() const { return NodeH.Len(); }
1892 
1896  int AddNode(int NId = -1);
1898  int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId()); }
1900 
1902  void DelNode(const int& NId);
1904  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
1906  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
1908  TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); }
1910  TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); }
1912  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); }
1914  TAIntI BegNAIntI(const TStr& attr) const {
1915  return TAIntI(VecOfIntVecsN[KeyToIndexTypeN.GetDat(attr).Val2].BegI(), attr, false, this); }
1917  TAIntI EndNAIntI(const TStr& attr) const {
1918  return TAIntI(VecOfIntVecsN[KeyToIndexTypeN.GetDat(attr).Val2].EndI(), attr, false, this); }
1920  TAIntI GetNAIntI(const TStr& attr, const int& NId) const {
1921  return TAIntI(VecOfIntVecsN[KeyToIndexTypeN.GetDat(attr).Val2].GetI(NodeH.GetKeyId(NId)), attr, false, this); }
1923  TAStrI BegNAStrI(const TStr& attr) const {
1924 
1925  return TAStrI(VecOfStrVecsN[KeyToIndexTypeN.GetDat(attr).Val2].BegI(), attr, false, this); }
1927  TAStrI EndNAStrI(const TStr& attr) const {
1928  return TAStrI(VecOfStrVecsN[KeyToIndexTypeN.GetDat(attr).Val2].EndI(), attr, false, this); }
1930  TAStrI GetNAStrI(const TStr& attr, const int& NId) const {
1931  return TAStrI(VecOfStrVecsN[KeyToIndexTypeN.GetDat(attr).Val2].GetI(NodeH.GetKeyId(NId)), attr, false, this); }
1933  TAFltI BegNAFltI(const TStr& attr) const {
1934  return TAFltI(VecOfFltVecsN[KeyToIndexTypeN.GetDat(attr).Val2].BegI(), attr, false, this); }
1936  TAFltI EndNAFltI(const TStr& attr) const {
1937  return TAFltI(VecOfFltVecsN[KeyToIndexTypeN.GetDat(attr).Val2].EndI(), attr, false, this); }
1939  TAFltI GetNAFltI(const TStr& attr, const int& NId) const {
1940  return TAFltI(VecOfFltVecsN[KeyToIndexTypeN.GetDat(attr).Val2].GetI(NodeH.GetKeyId(NId)), attr, false, this); }
1941 
1943  void AttrNameNI(const TInt& NId, TStrV& Names) const {
1944  AttrNameNI(NId, KeyToIndexTypeN.BegI(), Names);}
1945  void AttrNameNI(const TInt& NId, TStrIntPrH::TIter NodeHI, TStrV& Names) const;
1947  void AttrValueNI(const TInt& NId, TStrV& Values) const {
1948  AttrValueNI(NId, KeyToIndexTypeN.BegI(), Values);}
1949  void AttrValueNI(const TInt& NId, TStrIntPrH::TIter NodeHI, TStrV& Values) const;
1951  void IntAttrNameNI(const TInt& NId, TStrV& Names) const {
1952  IntAttrNameNI(NId, KeyToIndexTypeN.BegI(), Names);}
1953  void IntAttrNameNI(const TInt& NId, TStrIntPrH::TIter NodeHI, TStrV& Names) const;
1955  void IntAttrValueNI(const TInt& NId, TIntV& Values) const {
1956  IntAttrValueNI(NId, KeyToIndexTypeN.BegI(), Values);}
1957  void IntAttrValueNI(const TInt& NId, TStrIntPrH::TIter NodeHI, TIntV& Values) const;
1959  void StrAttrNameNI(const TInt& NId, TStrV& Names) const {
1960  StrAttrNameNI(NId, KeyToIndexTypeN.BegI(), Names);}
1961  void StrAttrNameNI(const TInt& NId, TStrIntPrH::TIter NodeHI, TStrV& Names) const;
1963  void StrAttrValueNI(const TInt& NId, TStrV& Values) const {
1964  StrAttrValueNI(NId, KeyToIndexTypeN.BegI(), Values);}
1965  void StrAttrValueNI(const TInt& NId, TStrIntPrH::TIter NodeHI, TStrV& Values) const;
1967  void FltAttrNameNI(const TInt& NId, TStrV& Names) const {
1968  FltAttrNameNI(NId, KeyToIndexTypeN.BegI(), Names);}
1969  void FltAttrNameNI(const TInt& NId, TStrIntPrH::TIter NodeHI, TStrV& Names) const;
1971  void FltAttrValueNI(const TInt& NId, TFltV& Values) const {
1972  FltAttrValueNI(NId, KeyToIndexTypeN.BegI(), Values);}
1973  void FltAttrValueNI(const TInt& NId, TStrIntPrH::TIter NodeHI, TFltV& Values) const;
1974 
1976  void AttrNameEI(const TInt& EId, TStrV& Names) const {
1977  AttrNameEI(EId, KeyToIndexTypeE.BegI(), Names);}
1978  void AttrNameEI(const TInt& EId, TStrIntPrH::TIter EdgeHI, TStrV& Names) const;
1980  void AttrValueEI(const TInt& EId, TStrV& Values) const {
1981  AttrValueEI(EId, KeyToIndexTypeE.BegI(), Values);}
1982  void AttrValueEI(const TInt& EId, TStrIntPrH::TIter EdgeHI, TStrV& Values) const;
1984  void IntAttrNameEI(const TInt& EId, TStrV& Names) const {
1985  IntAttrNameEI(EId, KeyToIndexTypeE.BegI(), Names);}
1986  void IntAttrNameEI(const TInt& EId, TStrIntPrH::TIter EdgeHI, TStrV& Names) const;
1988  void IntAttrValueEI(const TInt& EId, TIntV& Values) const {
1989  IntAttrValueEI(EId, KeyToIndexTypeE.BegI(), Values);}
1990  void IntAttrValueEI(const TInt& EId, TStrIntPrH::TIter EdgeHI, TIntV& Values) const;
1992  void StrAttrNameEI(const TInt& EId, TStrV& Names) const {
1993  StrAttrNameEI(EId, KeyToIndexTypeE.BegI(), Names);}
1994  void StrAttrNameEI(const TInt& EId, TStrIntPrH::TIter EdgeHI, TStrV& Names) const;
1996  void StrAttrValueEI(const TInt& EId, TStrV& Values) const {
1997  StrAttrValueEI(EId, KeyToIndexTypeE.BegI(), Values);}
1998  void StrAttrValueEI(const TInt& EId, TStrIntPrH::TIter EdgeHI, TStrV& Values) const;
2000  void FltAttrNameEI(const TInt& EId, TStrV& Names) const {
2001  FltAttrNameEI(EId, KeyToIndexTypeE.BegI(), Names);}
2002  void FltAttrNameEI(const TInt& EId, TStrIntPrH::TIter EdgeHI, TStrV& Names) const;
2004  void FltAttrValueEI(const TInt& EId, TFltV& Values) const {
2005  FltAttrValueEI(EId, KeyToIndexTypeE.BegI(), Values);}
2006  void FltAttrValueEI(const TInt& EId, TStrIntPrH::TIter EdgeHI, TFltV& Values) const;
2007 
2009  TAIntI BegEAIntI(const TStr& attr) const {
2010  return TAIntI(VecOfIntVecsE[KeyToIndexTypeE.GetDat(attr).Val2].BegI(), attr, true, this);
2011  }
2013  TAIntI EndEAIntI(const TStr& attr) const {
2014  return TAIntI(VecOfIntVecsE[KeyToIndexTypeE.GetDat(attr).Val2].EndI(), attr, true, this);
2015  }
2017  TAIntI GetEAIntI(const TStr& attr, const int& EId) const {
2018  return TAIntI(VecOfIntVecsE[KeyToIndexTypeE.GetDat(attr).Val2].GetI(EdgeH.GetKeyId(EId)), attr, true, this);
2019  }
2021  TAStrI BegEAStrI(const TStr& attr) const {
2022  return TAStrI(VecOfStrVecsE[KeyToIndexTypeE.GetDat(attr).Val2].BegI(), attr, true, this); }
2024  TAStrI EndEAStrI(const TStr& attr) const {
2025  return TAStrI(VecOfStrVecsE[KeyToIndexTypeE.GetDat(attr).Val2].EndI(), attr, true, this);
2026  }
2028  TAStrI GetEAStrI(const TStr& attr, const int& EId) const {
2029  return TAStrI(VecOfStrVecsE[KeyToIndexTypeE.GetDat(attr).Val2].GetI(EdgeH.GetKeyId(EId)), attr, true, this);
2030  }
2032  TAFltI BegEAFltI(const TStr& attr) const {
2033  return TAFltI(VecOfFltVecsE[KeyToIndexTypeE.GetDat(attr).Val2].BegI(), attr, true, this);
2034  }
2036  TAFltI EndEAFltI(const TStr& attr) const {
2037  return TAFltI(VecOfFltVecsE[KeyToIndexTypeE.GetDat(attr).Val2].EndI(), attr, true, this);
2038  }
2040  TAFltI GetEAFltI(const TStr& attr, const int& EId) const {
2041  return TAFltI(VecOfFltVecsE[KeyToIndexTypeE.GetDat(attr).Val2].GetI(EdgeH.GetKeyId(EId)), attr, true, this);
2042  }
2044  int GetMxNId() const { return MxNId; }
2046  int GetMxEId() const { return MxEId; }
2047 
2049  int GetEdges() const { return EdgeH.Len(); }
2051 
2056  int AddEdge(const int& SrcNId, const int& DstNId, int EId = -1);
2058  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI.GetId()); }
2060  void DelEdge(const int& EId);
2062 
2066  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
2068  bool IsEdge(const int& EId) const { return EdgeH.IsKey(EId); }
2070  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const { int EId; return IsEdge(SrcNId, DstNId, EId, IsDir); }
2072  bool IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir = true) const;
2074  int GetEId(const int& SrcNId, const int& DstNId) const { int EId; return IsEdge(SrcNId, DstNId, EId)?EId:-1; }
2076  TEdgeI BegEI() const { return TEdgeI(EdgeH.BegI(), this); }
2078  TEdgeI EndEI() const { return TEdgeI(EdgeH.EndI(), this); }
2080  TEdgeI GetEI(const int& EId) const { return TEdgeI(EdgeH.GetI(EId), this); }
2082  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const { return GetEI(GetEId(SrcNId, DstNId)); }
2083 
2085  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
2087  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
2089  int GetRndEId(TRnd& Rnd=TInt::Rnd) { return EdgeH.GetKey(EdgeH.GetRndKeyId(Rnd, 0.8)); }
2091  TEdgeI GetRndEI(TRnd& Rnd=TInt::Rnd) { return GetEI(GetRndEId(Rnd)); }
2093  void GetNIdV(TIntV& NIdV) const;
2095  void GetEIdV(TIntV& EIdV) const;
2096 
2098  bool Empty() const { return GetNodes()==0; }
2100  void Clr() { MxNId=0; MxEId=0; NodeH.Clr(); EdgeH.Clr(),
2103  VecOfIntVecsN.Clr(), VecOfIntVecsE.Clr(), VecOfStrVecsN.Clr(), VecOfStrVecsE.Clr(),
2104  VecOfFltVecsN.Clr(), VecOfFltVecsE.Clr();}
2106  void Reserve(const int& Nodes, const int& Edges) {
2107  if (Nodes>0) { NodeH.Gen(Nodes/2); } if (Edges>0) { EdgeH.Gen(Edges/2); } }
2109 
2114  void Defrag(const bool& OnlyNodeLinks=false);
2116 
2119  bool IsOk(const bool& ThrowExcept=true) const;
2121  void Dump(FILE *OutF=stdout) const;
2122 
2124 
2126  int AddIntAttrDatN(const TNodeI& NodeI, const TInt& value, const TStr& attr) { return AddIntAttrDatN(NodeI.GetId(), value, attr); }
2127  int AddIntAttrDatN(const int& NId, const TInt& value, const TStr& attr);
2129 
2131  int AddStrAttrDatN(const TNodeI& NodeI, const TStr& value, const TStr& attr) { return AddStrAttrDatN(NodeI.GetId(), value, attr); }
2132  int AddStrAttrDatN(const int& NId, const TStr& value, const TStr& attr);
2134 
2136  int AddFltAttrDatN(const TNodeI& NodeI, const TFlt& value, const TStr& attr) { return AddFltAttrDatN(NodeI.GetId(), value, attr); }
2137  int AddFltAttrDatN(const int& NId, const TFlt& value, const TStr& attr);
2138 
2140 
2142  int AddIntAttrDatE(const TEdgeI& EdgeI, const TInt& value, const TStr& attr) { return AddIntAttrDatE(EdgeI.GetId(), value, attr); }
2143  int AddIntAttrDatE(const int& EId, const TInt& value, const TStr& attr);
2145 
2147  int AddStrAttrDatE(const TEdgeI& EdgeI, const TStr& value, const TStr& attr) { return AddStrAttrDatE(EdgeI.GetId(), value, attr); }
2148  int AddStrAttrDatE(const int& EId, const TStr& value, const TStr& attr);
2150 
2152  int AddFltAttrDatE(const TEdgeI& EdgeI, const TFlt& value, const TStr& attr) { return AddFltAttrDatE(EdgeI.GetId(), value, attr); }
2153  int AddFltAttrDatE(const int& EId, const TFlt& value, const TStr& attr);
2154 
2156  TInt GetIntAttrDatN(const TNodeI& NodeI, const TStr& attr) { return GetIntAttrDatN(NodeI.GetId(), attr); }
2157  TInt GetIntAttrDatN(const int& NId, const TStr& attr);
2158 
2160  TStr GetStrAttrDatN(const TNodeI& NodeI, const TStr& attr) { return GetStrAttrDatN(NodeI.GetId(), attr); }
2161  TStr GetStrAttrDatN(const int& NId, const TStr& attr);
2163  TFlt GetFltAttrDatN(const TNodeI& NodeI, const TStr& attr) { return GetFltAttrDatN(NodeI.GetId(), attr); }
2164  TFlt GetFltAttrDatN(const int& NId, const TStr& attr);
2165 
2167  int GetIntAttrIndN(const TStr& attr);
2169  int GetAttrIndN(const TStr& attr);
2170 
2172  TInt GetIntAttrIndDatN(const TNodeI& NodeI, const int& index) { return GetIntAttrIndDatN(NodeI.GetId(), index); }
2174  TInt GetIntAttrIndDatN(const int& NId, const int& index);
2175 
2177  TStr GetStrAttrIndDatN(const TNodeI& NodeI, const int& index) { return GetStrAttrIndDatN(NodeI.GetId(), index); }
2179  TStr GetStrAttrIndDatN(const int& NId, const int& index);
2180 
2182  TFlt GetFltAttrIndDatN(const TNodeI& NodeI, const int& index) { return GetFltAttrIndDatN(NodeI.GetId(), index); }
2184  TFlt GetFltAttrIndDatN(const int& NId, const int& index);
2185 
2187  TInt GetIntAttrDatE(const TEdgeI& EdgeI, const TStr& attr) { return GetIntAttrDatE(EdgeI.GetId(), attr); }
2188  TInt GetIntAttrDatE(const int& EId, const TStr& attr);
2190  TStr GetStrAttrDatE(const TEdgeI& EdgeI, const TStr& attr) { return GetStrAttrDatE(EdgeI.GetId(), attr); }
2191  TStr GetStrAttrDatE(const int& EId, const TStr& attr);
2193  TFlt GetFltAttrDatE(const TEdgeI& EdgeI, const TStr& attr) { return GetFltAttrDatE(EdgeI.GetId(), attr); }
2194  TFlt GetFltAttrDatE(const int& EId, const TStr& attr);
2195 
2197  int GetIntAttrIndE(const TStr& attr);
2199  int GetAttrIndE(const TStr& attr);
2200 
2202  TInt GetIntAttrIndDatE(const TEdgeI& EdgeI, const int& index) { return GetIntAttrIndDatE(EdgeI.GetId(), index); }
2204  TInt GetIntAttrIndDatE(const int& EId, const int& index);
2205 
2207  TFlt GetFltAttrIndDatE(const TEdgeI& EdgeI, const int& index) { return GetFltAttrIndDatE(EdgeI.GetId(), index); }
2209  TFlt GetFltAttrIndDatE(const int& EId, const int& index);
2210 
2212  TStr GetStrAttrIndDatE(const TEdgeI& EdgeI, const int& index) { return GetStrAttrIndDatE(EdgeI.GetId(), index); }
2214  TStr GetStrAttrIndDatE(const int& EId, const int& index);
2215 
2217  int DelAttrDatN(const TNodeI& NodeI, const TStr& attr) { return DelAttrDatN(NodeI.GetId(), attr); }
2218  int DelAttrDatN(const int& NId, const TStr& attr);
2220  int DelAttrDatE(const TEdgeI& EdgeI, const TStr& attr) { return DelAttrDatE(EdgeI.GetId(), attr); }
2221  int DelAttrDatE(const int& EId, const TStr& attr);
2222 
2224  int AddIntAttrN(const TStr& attr, TInt defaultValue=TInt::Mn);
2226  int AddStrAttrN(const TStr& attr, TStr defaultValue=TStr::GetNullStr());
2228  int AddFltAttrN(const TStr& attr, TFlt defaultValue=TFlt::Mn);
2229 
2231  int AddIntAttrE(const TStr& attr, TInt defaultValue=TInt::Mn);
2233  int AddStrAttrE(const TStr& attr, TStr defaultValue=TStr::GetNullStr());
2235  int AddFltAttrE(const TStr& attr, TFlt defaultValue=TFlt::Mn);
2236 
2238  int DelAttrN(const TStr& attr);
2240  int DelAttrE(const TStr& attr);
2241 
2242  // Returns true if \c attr exists for node \c NId and has default value.
2243  bool IsAttrDeletedN(const int& NId, const TStr& attr) const;
2244  // Returns true if Int \c attr exists for node \c NId and has default value.
2245  bool IsIntAttrDeletedN(const int& NId, const TStr& attr) const;
2246  // Returns true if Str \c attr exists for node \c NId and has default value.
2247  bool IsStrAttrDeletedN(const int& NId, const TStr& attr) const;
2248  // Returns true if Flt \c attr exists for node \c NId and has default value.
2249  bool IsFltAttrDeletedN(const int& NId, const TStr& attr) const;
2250 
2251  // Returns true if NId attr deleted for current node attr iterator.
2252  bool NodeAttrIsDeleted(const int& NId, const TStrIntPrH::TIter& NodeHI) const;
2253  // Returns true if NId attr deleted value for current node int attr iterator.
2254  bool NodeAttrIsIntDeleted(const int& NId, const TStrIntPrH::TIter& NodeHI) const;
2255  // Returns true if NId attr deleted value for current node str attr iterator.
2256  bool NodeAttrIsStrDeleted(const int& NId, const TStrIntPrH::TIter& NodeHI) const;
2257  // Returns true if NId attr deleted value for current node flt attr iterator.
2258  bool NodeAttrIsFltDeleted(const int& NId, const TStrIntPrH::TIter& NodeHI) const;
2259 
2260  // Returns true if \c attr exists for edge \c EId and has default value.
2261  bool IsAttrDeletedE(const int& EId, const TStr& attr) const;
2262  // Returns true if Int \c attr exists for edge \c EId and has default value.
2263  bool IsIntAttrDeletedE(const int& EId, const TStr& attr) const;
2264  // Returns true if Str \c attr exists for edge \c NId and has default value.
2265  bool IsStrAttrDeletedE(const int& EId, const TStr& attr) const;
2266  // Returns true if Flt \c attr exists for edge \c NId and has default value.
2267  bool IsFltAttrDeletedE(const int& EId, const TStr& attr) const;
2268 
2269  // Returns true if EId attr deleted for current edge attr iterator.
2270  bool EdgeAttrIsDeleted(const int& EId, const TStrIntPrH::TIter& EdgeHI) const;
2271  // Returns true if EId attr deleted for current edge int attr iterator.
2272  bool EdgeAttrIsIntDeleted(const int& EId, const TStrIntPrH::TIter& EdgeHI) const;
2273  // Returns true if EId attr deleted for current edge str attr iterator.
2274  bool EdgeAttrIsStrDeleted(const int& EId, const TStrIntPrH::TIter& EdgeHI) const;
2275  // Returns true if EId attr deleted for current edge flt attr iterator.
2276  bool EdgeAttrIsFltDeleted(const int& EId, const TStrIntPrH::TIter& EdgeHI) const;
2277 
2278  // Returns node attribute value, converted to Str type.
2279  TStr GetNodeAttrValue(const int& NId, const TStrIntPrH::TIter& NodeHI) const;
2280  // Returns edge attribute value, converted to Str type.
2281  TStr GetEdgeAttrValue(const int& EId, const TStrIntPrH::TIter& EdgeHI) const;
2282 
2284  void GetAttrNNames(TStrV& IntAttrNames, TStrV& FltAttrNames, TStrV& StrAttrNames) const;
2286  void GetAttrENames(TStrV& IntAttrNames, TStrV& FltAttrNames, TStrV& StrAttrNames) const;
2287 
2289 
2293  static PNEANet GetSmallGraph();
2294  friend class TPt<TNEANet>;
2295 };
2296 
2297 // set flags
2298 namespace TSnap {
2299 template <> struct IsMultiGraph<TNEANet> { enum { Val = 1 }; };
2300 template <> struct IsDirected<TNEANet> { enum { Val = 1 }; };
2301 }
int GetNbrEId(const int &EdgeN) const
Definition: network.h:1006
int AddEdge(const TEdgeI &EdgeI)
Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the network.
Definition: network.h:209
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:624
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
Definition: bd.h:440
TEdgeDat & GetOutEDat(const int &EdgeN)
Definition: network.h:1102
#define IAssert(Cond)
Definition: bd.h:262
static int GetNIdPos(const TVec< TPair< TInt, TEdgeData > > &NIdV, const int &NId)
Definition: network.h:739
TVec< TIntV > VecOfIntVecsN
Definition: network.h:1837
TNEANet(TSIn &SIn)
Constructor for loading the graph from a (binary) stream SIn.
Definition: network.h:1860
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: network.h:1667
TInt MxEId
Definition: network.h:1149
TNodeData TNodeDat
Definition: network.h:980
TEdgeI(const THashIter &EdgeHIter, const TNodeEdgeNet *NetPt)
Definition: network.h:1117
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TNodeI & operator++(int)
Increment iterator.
Definition: network.h:492
TNodeNet(const TNodeNet &NodeNet)
Definition: network.h:141
TEdgeI & operator++(int)
Definition: network.h:1120
TNodeI(const THashIter &NodeHIter, const TNodeNet *NetPt)
Definition: network.h:56
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TNodeData & GetDat()
Definition: network.h:467
Tests (at compile time) if the graph is a network with data on nodes.
Definition: gbase.h:29
TEdge(const TEdge &Edge)
Definition: network.h:1021
TNodeData & GetOutNDat(const int &EdgeN)
Definition: network.h:1083
bool IsDeleted() const
Returns true if the attribute has been deleted.
Definition: network.h:1756
TInt GetIntAttrDatN(const TNodeI &NodeI, const TStr &attr)
Gets the value of int attr from the node attr value vector.
Definition: network.h:2156
bool IsOutNId(const int &NId) const
Definition: network.h:42
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: network.h:2085
int GetAttrIndE(const TStr &attr)
Gets the index of the edge attr value vector specified by attr.
Definition: network.cpp:858
bool DelIfIn(const TVal &Val)
Removes the first occurrence of element Val.
Definition: ds.h:1115
void Clr()
Deletes all nodes and edges from the network.
Definition: network.h:1279
int GetInEId(const int &EdgeN) const
Returns ID of EdgeN-th in-edge.
Definition: network.h:1088
const TNodeData & GetInNDat(const int &EdgeN) const
Definition: network.h:1080
int GetId() const
Definition: network.h:1622
int GetNbrEId(const int &EdgeN) const
Returns ID of EdgeN-th in or out-edge.
Definition: network.h:1092
void GetAttrENames(TStrV &IntAttrNames, TStrV &FltAttrNames, TStrV &StrAttrNames) const
Fills each of the vectors with the names of edge attributes of the given type.
Definition: network.cpp:1079
int GetNodes() const
Returns the number of nodes in the graph.
Definition: network.h:1890
TPt< TIntNEDNet > PIntNEDNet
Definition: network.h:969
const TEdgeDat & GetOutEDat(const int &EdgeN) const
Definition: network.h:1103
void SetNDat(const int &NId, const TNodeData &NodeDat)
Sets node data for the node of ID NId in the network.
Definition: network.h:1385
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
TPt< TIntFltNEDNet > PIntFltNEDNet
Definition: network.h:971
void SortEIdByDat(const bool &Asc=true)
Sorts edges by edge data.
Definition: network.h:1290
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int GetOutNId(const int &EdgeN) const
Returns ID of EdgeN-th out-node (the node the current node points to).
Definition: network.h:1063
int GetSrcNId() const
Definition: network.h:1623
TNodeData TNodeDat
Definition: network.h:16
TStr GetStrAttrDatN(const TNodeI &NodeI, const TStr &attr)
Gets the value of str attr from the node attr value vector.
Definition: network.h:2160
THash< TStr, TFlt > FltDefaultsE
Definition: network.h:1836
TNode(TSIn &SIn)
Definition: network.h:995
virtual void Save(TSOut &SOut) const
Saves the network to a (binary) stream SOut.
Definition: network.h:591
int GetDeg() const
Returns degree of the current node.
Definition: network.h:67
int AddFltAttrDatE(const TEdgeI &EdgeI, const TFlt &value, const TStr &attr)
Attribute based add function for attr to Flt value.
Definition: network.h:2152
TNode(const int &NId, const TNodeData &NodeData)
Definition: network.h:993
int GetOutNId(const int &EdgeN) const
Returns ID of EdgeN-th out-node (the node the current node points to).
Definition: network.h:1657
int GetDeg() const
Definition: network.h:33
TNode & GetNode(const int &NId)
Definition: network.h:130
TAStrI GetNAStrI(const TStr &attr, const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: network.h:1930
TStr GetEdgeAttrValue(const int &EId, const TStrIntPrH::TIter &EdgeHI) const
Definition: network.cpp:299
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:1649
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: network.h:110
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the network.
Definition: network.h:1247
const TNodeData & GetNDat(const int &NId) const
Returns node data for the node of ID NId in the network.
Definition: network.h:1206
const TNodeData & GetDat() const
Definition: network.h:466
TVec< TStrV > VecOfStrVecsE
Definition: network.h:1838
TCRef CRef
Definition: network.h:579
THash< TStr, TInt > IntDefaultsE
Definition: network.h:1834
int GetInNId(const int &EdgeN) const
Returns ID of EdgeN-th in-node (the node pointing to the current node).
Definition: network.h:1059
void Save(TSOut &SOut) const
Definition: network.h:996
TNodeEDatNet & operator=(const TNodeEDatNet &NodeNet)
Definition: network.h:598
const TNodeData & operator()() const
Definition: network.h:523
int GetIntAttrIndN(const TStr &attr)
Gets the index of the node attr value vector specified by attr (same as GetAttrIndN for compatibility...
Definition: network.cpp:822
void Save(TSOut &SOut) const
Definition: network.h:1601
bool NodeAttrIsStrDeleted(const int &NId, const TStrIntPrH::TIter &NodeHI) const
Definition: network.cpp:142
int AddNode(const TNodeI &NodeI)
Adds a node NodeI and its node data to the network.
Definition: network.h:616
int DelAttrN(const TStr &attr)
Removes all the values for node attr.
Definition: network.cpp:1007
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: network.h:507
int AddEdge(const TEdgeI &EdgeI)
Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() and its edge data to the network...
Definition: network.h:1230
bool NodeAttrIsDeleted(const int &NId, const TStrIntPrH::TIter &NodeHI) const
Definition: network.cpp:127
void SortNIdById(const bool &Asc=true)
Sorts nodes by node IDs.
Definition: network.h:1284
bool Empty() const
Tests whether the network is empty (has zero nodes).
Definition: network.h:235
int GetInNId(const int &NodeN) const
Definition: network.h:38
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a network of Nodes nodes and Edges edges.
Definition: network.h:1281
TEdgeI GetEI(const int &EId) const
Returns an iterator referring to edge with edge ID EId.
Definition: network.h:2080
void DelNode(const int &NId)
Deletes node of ID NId from the network.
Definition: network.h:782
TNodeData & GetDat()
Definition: network.h:1079
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:802
void DelEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true)
Deletes an edge from node IDs SrcNId to DstNId from the network.
Definition: network.h:340
int AddEdge(const TEdgeI &EdgeI)
Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
Definition: network.h:2058
bool operator<(const TEdgeI &EdgeI) const
Definition: network.h:116
Definition: dt.h:11
TAFltI & operator++(int)
Definition: network.h:1803
const TNode & GetNode(const int &NId) const
Returns node element for the node of ID NId in the network.
Definition: network.h:187
bool IsStrAttrDeletedN(const int &NId, const TStr &attr) const
Definition: network.cpp:119
bool IsNbrEId(const int &EId) const
Definition: network.h:1009
TEdgeI(const THashIter &EdgeHIter, const TNEANet *GraphPt)
Definition: network.h:1706
TPt< TStrIntNEDNet > PStrIntNEDNet
Definition: network.h:973
THash< TInt, TNode >::TIter THashIter
Definition: network.h:483
TNodeData & GetNDat(const int &NId)
Returns node data for the node of ID NId in the network.
Definition: network.h:636
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1094
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the network.
Definition: network.h:674
THashIter EdgeHI
Definition: network.h:1113
void AttrNameEI(const TInt &EId, TStrV &Names) const
Returns a vector of attr names for edge EId.
Definition: network.h:1976
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
void SortNIdByDat(const bool &Asc=true)
Sorts nodes by node data.
Definition: network.h:244
TNodeData & GetOutNDat(const int &NodeN)
Definition: network.h:97
TStrVecIter HI
Definition: network.h:1765
void GetNIdV(TIntV &NIdV) const
Returns a vector of all node IDs in the network.
Definition: network.h:1480
const TNodeData & GetDat() const
Definition: network.h:36
void Save(TSOut &SOut) const
Definition: dt.h:1058
static PNEANet Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: network.h:1882
TEdgeData & GetInEDat(const int &EdgeN)
Definition: network.h:536
TNode & GetNode(const int &NId)
Definition: network.h:1808
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:1196
int AddNode(const TNodeI &NodeI)
Adds a node NodeI and its node data to the network.
Definition: network.h:1186
void StrAttrNameNI(const TInt &NId, TStrV &Names) const
Returns a vector of str attr names for node NId.
Definition: network.h:1959
TNodeI(const TNodeI &NodeI)
Definition: network.h:1636
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the network.
Definition: network.h:622
void FltAttrNameNI(const TInt &NId, TStrV &Names) const
Returns a vector of int attr names for node NId.
Definition: network.h:1967
bool IsInEId(const int &EId) const
Tests whether the edge with ID EId is an in-edge of current node.
Definition: network.h:1675
TNodeI(const THashIter &NodeHIter, const TNodeEdgeNet *NetPt)
Definition: network.h:1041
bool operator<(const TNodeI &NodeI) const
Definition: network.h:1046
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:752
bool EdgeAttrIsFltDeleted(const int &EId, const TStrIntPrH::TIter &EdgeHI) const
Definition: network.cpp:293
bool IsOutNId(const int &NId) const
Definition: network.h:474
virtual ~TNodeEDatNet()
Definition: network.h:589
const TNodeData & GetOutNDat(const int &EdgeN) const
Definition: network.h:1082
TInt GetIntAttrDefaultE(const TStr &attribute) const
Get Int edge attribute val. If not a proper attr, return default.
Definition: network.h:1820
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: network.h:89
TNodeData & GetDat()
Definition: network.h:37
bool EdgeAttrIsDeleted(const int &EId, const TStrIntPrH::TIter &EdgeHI) const
Definition: network.cpp:274
TNodeI(const TNodeI &NodeI)
Definition: network.h:489
TNodeEdgeNet< TFlt, TFlt > TFltNENet
Definition: network.h:1563
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition: network.h:2070
TFlt GetFltAttrDatE(const TEdgeI &EdgeI, const TStr &attr)
Gets the value of flt attr from the edge attr value vector.
Definition: network.h:2193
bool operator<(const TEdgeI &EdgeI) const
Definition: network.h:556
TNodeEDatNet(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a network of Nodes nodes and Edges edges.
Definition: network.h:585
THash< TInt, TNode >::TIter THashIter
Definition: network.h:1630
TNodeData & GetDat()
Definition: network.h:1003
TPt< TIntNENet > PIntNENet
Definition: network.h:1562
void DelEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true)
Deletes an edge from node IDs SrcNId to DstNId from the network.
Definition: network.h:828
Tests (at compile time) if the graph is directed.
Definition: gbase.h:25
const TNEANet * Graph
Definition: network.h:1703
int GetInNId(const int &EdgeN) const
Returns ID of EdgeN-th in-node (the node pointing to the current node).
Definition: network.h:1653
TIter BegI() const
Definition: hash.h:171
TPt< TFltNNet > PFltNNet
Definition: network.h:434
bool operator<(const TNodeI &NodeI) const
Definition: network.h:61
bool IsAttrDeletedE(const int &EId, const TStr &attr) const
Definition: network.cpp:255
const TEdge & GetEdgeKId(const int &EdgeKeyId) const
Definition: network.h:1146
bool IsFltAttrDeletedE(const int &EId, const TStr &attr) const
Definition: network.cpp:270
const TNode & GetNode(const int &NId) const
Definition: network.h:1142
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: network.h:517
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the network.
Definition: network.h:1266
TNode(const TNode &Node)
Definition: network.h:459
void GetFltAttrVal(TFltV &Val) const
Gets vector of flt attribute values.
Definition: network.h:1734
TEdgeI(const TEdgeI &EdgeI)
Definition: network.h:551
const TNEANet * Graph
Definition: network.h:1632
bool EdgeAttrIsIntDeleted(const int &EId, const TStrIntPrH::TIter &EdgeHI) const
Definition: network.cpp:281
int GetDeg() const
Definition: network.h:999
void SetEDat(const int &SrcNId, const int &DstNId, const TEdgeData &EdgeDat)
Sets edge data for the edge between nodes SrcNId and DstNId in the network.
Definition: network.h:850
bool operator<(const TNode &Node) const
Definition: network.h:997
void Save(TSOut &SOut) const
Definition: hash.h:141
virtual ~TNodeEdgeNet()
Definition: network.h:1159
int GetMxNId() const
Returns an ID that is larger than any node ID in the network.
Definition: network.h:1208
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:1194
TEdge(const int &EId, const int &SourceNId, const int &DestNId, const TEdgeData &EdgeData)
Definition: network.h:1020
int DelAttrE(const TStr &attr)
Removes all the values for edge attr.
Definition: network.cpp:1031
TNodeEdgeNet(const TNodeEdgeNet &Net)
Definition: network.h:1156
void StrAttrValueNI(const TInt &NId, TStrV &Values) const
Returns a vector of attr values for node NId.
Definition: network.h:1963
static PNet New()
Static constructor that returns a pointer to the network. Call: TPt > Net = TNod...
Definition: network.h:148
const TNodeData & GetInNDat(const int &NodeN) const
Definition: network.h:94
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:1172
TNodeI & operator++(int)
Increment iterator.
Definition: network.h:1045
TStrIntPrH KeyToIndexTypeE
Definition: network.h:1832
const TNodeData & GetInNDat(const int &NodeN) const
Definition: network.h:529
TEdgeData & GetOutEDat(const int &EdgeN)
Definition: network.h:471
TStr GetStrAttrDatE(const TEdgeI &EdgeI, const TStr &attr)
Gets the value of str attr from the edge attr value vector.
Definition: network.h:2190
Edge iterator. Only forward iteration (operator++) is supported.
Definition: network.h:104
void SetAllEDat(const TEdgeData &EdgeDat)
Sets edge data for all the edges in the network to EDat.
Definition: network.h:879
bool IsInNId(const int &NId) const
Definition: network.h:41
TEdgeData EdgeDat
Definition: network.h:1016
TNodeI & operator=(const TNodeI &NodeI)
Definition: network.h:58
TEdgeI GetEI(const int &SrcNId, const int &DstNId) const
Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
Definition: network.h:2082
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:183
TNodeI(const TNodeI &NodeI)
Definition: network.h:57
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:323
int GetRndEId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random edge in the graph.
Definition: network.h:2089
bool IsOutEId(const int &EId) const
Tests whether the edge with ID EId is an out-edge of current node.
Definition: network.h:1096
int GetOutEId(const int &EdgeN) const
Returns ID of EdgeN-th out-edge.
Definition: network.h:1671
TNode(TSIn &SIn)
Definition: network.h:30
THash< TInt, TNode > NodeH
Definition: network.h:135
TStr GetDat() const
Returns an attribute of the node.
Definition: network.h:1777
int GetOutNId(const int &NodeN) const
Definition: network.h:39
TFltVecIter HI
Definition: network.h:1788
TEdge(const TEdge &Edge)
Definition: network.h:1619
TNodeData & GetNbrNDat(const int &NodeN)
Definition: network.h:532
TNodeI & operator++(int)
Increment iterator.
Definition: network.h:60
TCRef CRef
Definition: network.h:1148
TInt GetDat() const
Returns an attribute of the node.
Definition: network.h:1754
int GetOutDeg() const
Definition: network.h:1001
bool IsNbrNId(const int &NId) const
Definition: network.h:475
THash< TStr, TFlt > FltDefaultsN
Definition: network.h:1836
void SortNIdById(const bool &Asc=true)
Sorts nodes by node IDs.
Definition: network.h:707
TEdgeI GetRndEI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random edge in the graph.
Definition: network.h:2091
const TEdge & GetEdge(const int &EId) const
Definition: network.h:1145
bool IsEdge(const int &EId) const
Tests whether an edge with edge ID EId exists in the graph.
Definition: network.h:2068
TEdgeData TEdgeDat
Definition: network.h:444
const TNodeData & GetNbrNDat(const int &NodeN) const
Definition: network.h:531
int GetUniqEdges(const bool &IsDir=true) const
Returns the number of edges in the network with a unique pair of nodes.
Definition: network.h:1391
TNodeEDatNet< TInt, TFlt > TIntFltNEDNet
Definition: network.h:970
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:1341
TNodeData & GetNbrNDat(const int &EdgeN)
Definition: network.h:1085
TNodeData & GetInNDat(const int &NodeN)
Definition: network.h:530
void IntAttrValueEI(const TInt &EId, TIntV &Values) const
Returns a vector of attr values for edge EId.
Definition: network.h:1988
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
int AddIntAttrDatE(const TEdgeI &EdgeI, const TInt &value, const TStr &attr)
Attribute based add function for attr to Int value.
Definition: network.h:2142
TInt MxNId
Definition: network.h:1828
TIntV OutEIdV
Definition: network.h:1595
int GetNbrNId(const int &EdgeN) const
Returns ID of EdgeN-th neighboring node.
Definition: network.h:1067
TNodeData & GetNDat(const int &NId)
Returns node data for the node of ID NId in the network.
Definition: network.h:1204
TFlt GetDat() const
Returns an attribute of the node.
Definition: network.h:1800
TNodeData & GetNDat(const int &NId)
Returns node data for the node of ID NId in the network.
Definition: network.h:191
bool IsOutEId(const int &EId) const
Definition: network.h:1610
TAIntI BegNAIntI(const TStr &attr) const
Returns an iterator referring to the first node's int attribute.
Definition: network.h:1914
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1628
Node/edge integer attribute iterator. Iterates through all nodes/edges for one integer attribute...
Definition: network.h:1739
int GetInNId(const int &EdgeN) const
Definition: network.h:468
TAFltI(const TAFltI &I)
Definition: network.h:1795
void AttrValueNI(const TInt &NId, TStrV &Values) const
Returns a vector of attr values for node NId.
Definition: network.h:1947
int GetSrcNId() const
Gets the source node of an edge.
Definition: network.h:121
TEdgeData & operator()()
Definition: network.h:564
void GetStrAttrNames(TStrV &Names) const
Gets vector of str attribute names.
Definition: network.h:1728
bool GetEDat(const int &SrcNId, const int &DstNId, TEdgeData &EdgeDat) const
Returns edge data in Data for the edge from node IDs SrcNId to DstNId.
Definition: network.h:857
TVec< TIntV > VecOfIntVecsE
Definition: network.h:1837
TIter EndI() const
Definition: hash.h:176
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the network.
Definition: network.h:1496
TNodeI & operator=(const TNodeI &NodeI)
Definition: network.h:1043
const TEdgeData & GetInEDat(const int &EdgeN) const
Definition: network.h:537
bool IsNbrEId(const int &EId) const
Tests whether the edge with ID EId is an in or out-edge of current node.
Definition: network.h:1679
void IntAttrNameNI(const TInt &NId, TStrV &Names) const
Returns a vector of int attr names for node NId.
Definition: network.h:1951
int GetSrcNId() const
Gets the source node of an edge.
Definition: network.h:561
TNodeData NodeDat
Definition: network.h:23
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the network.
Definition: network.h:230
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:157
bool IsNbrNId(const int &NId) const
Definition: network.h:43
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
Definition: network.h:1251
TNodeData NodeDat
Definition: network.h:989
static TRnd Rnd
Definition: dt.h:1051
TAFltI GetEAFltI(const TStr &attr, const int &EId) const
Returns an iterator referring to the edge of ID EId in the graph.
Definition: network.h:2040
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:181
int GetNbrEId(const int &EdgeN) const
Definition: network.h:1608
bool IsDeleted() const
Returns true if the attribute has been deleted.
Definition: network.h:1802
int GetInDeg() const
Returns in-degree of the current node.
Definition: network.h:501
TAFltI BegEAFltI(const TStr &attr) const
Returns an iterator referring to the first edge's flt attribute.
Definition: network.h:2032
void SetNDat(const int &NId, const TNodeData &NodeDat)
Sets node data for the node of ID NId in the network.
Definition: network.h:317
TAStrI GetEAStrI(const TStr &attr, const int &EId) const
Returns an iterator referring to the edge of ID EId in the graph.
Definition: network.h:2028
Node/edge float attribute iterator. Iterates through all nodes/edges for one float attribute...
Definition: network.h:1785
int AddNode(const TNodeI &NodeI)
Adds a node of ID NodeI.GetId() to the graph.
Definition: network.h:1898
TIntV InNIdV
Definition: network.h:24
Node Edge Network (directed multigraph, TNEGraph with data on nodes and edges).
Definition: network.h:978
int GetId() const
Returns edge ID.
Definition: network.h:1714
int GetOutNId(const int &EdgeN) const
Definition: network.h:469
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1027
void ErrNotify(const char *NotifyCStr)
Definition: bd.h:74
TNodeEDatNet< TInt, TInt > TIntNEDNet
Definition: network.h:968
void Defrag()
Definition: hash.h:509
bool IsOutEId(const int &EId) const
Definition: network.h:1008
TAIntI BegEAIntI(const TStr &attr) const
Returns an iterator referring to the first edge's int attribute.
Definition: network.h:2009
virtual void Save(TSOut &SOut) const
Saves the network to a (binary) stream SOut.
Definition: network.h:1161
const TNodeData & GetNDat(const int &NId) const
Returns node data for the node of ID NId in the network.
Definition: network.h:193
bool operator==(const TEdgeI &EdgeI) const
Definition: network.h:557
Definition: dt.h:1291
TEdge(const int &EId, const int &SourceNId, const int &DestNId)
Definition: network.h:1019
TVec< TStrV > VecOfStrVecsN
Definition: network.h:1838
void GetStrAttrVal(TStrV &Val) const
Gets vector of str attribute values.
Definition: network.h:1730
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:179
TPt< TNet > PNet
Definition: network.h:446
TNodeEDatNet(const TNodeEDatNet &NodeNet)
Definition: network.h:586
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: network.h:515
Definition: fl.h:58
bool IsIntAttrDeletedE(const int &EId, const TStr &attr) const
Definition: network.cpp:262
void Save(TSOut &SOut) const
Definition: ds.h:885
TEdgeI & operator++(int)
Increment iterator.
Definition: network.h:114
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:185
int AddEdge(const int &SrcNId, const int &DstNId, int EId=-1)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: network.h:1403
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: network.h:1645
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: network.cpp:601
bool IsFltAttrDeletedN(const int &NId, const TStr &attr) const
Definition: network.cpp:123
int AddFltAttrDatN(const TNodeI &NodeI, const TFlt &value, const TStr &attr)
Attribute based add function for attr to Flt value.
Definition: network.h:2136
int GetInEId(const int &EdgeN) const
Returns ID of EdgeN-th in-edge.
Definition: network.h:1669
bool NodeAttrIsFltDeleted(const int &NId, const TStrIntPrH::TIter &NodeHI) const
Definition: network.cpp:150
int GetInDeg() const
Returns in-degree of the current node.
Definition: network.h:69
TEdge(TSIn &SIn)
Definition: network.h:1022
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: network.h:519
THash< TInt, TEdge > EdgeH
Definition: network.h:1830
static PNet New()
Static constructor that returns a pointer to the network. Call: TPt > Net = TNodeEDatNet::New().
Definition: network.h:593
TAIntI GetEAIntI(const TStr &attr, const int &EId) const
Returns an iterator referring to the edge of ID EId in the graph.
Definition: network.h:2017
void GetAttrNNames(TStrV &IntAttrNames, TStrV &FltAttrNames, TStrV &StrAttrNames) const
Fills each of the vectors with the names of node attributes of the given type.
Definition: network.cpp:1065
const TNodeData & GetSrcNDat() const
Definition: network.h:569
TAStrI EndEAStrI(const TStr &attr) const
Returns an iterator referring to the past-the-end edge's attribute.
Definition: network.h:2024
int GetDstNId() const
Returns the destination of the edge.
Definition: network.h:1718
TNode(const int &NId, const TNodeData &NodeData)
Definition: network.h:458
int GetId() const
Definition: network.h:462
int GetAttrIndN(const TStr &attr)
Gets the index of the node attr value vector specified by attr.
Definition: network.cpp:826
const TEdgeData & GetOutEDat(const int &EdgeN) const
Definition: network.h:472
TStr GetStrAttrIndDatE(const TEdgeI &EdgeI, const int &index)
Gets the value of a string edge attr specified by edge iterator EdgeI and the attr index...
Definition: network.h:2212
bool operator==(const TNodeI &NodeI) const
Definition: network.h:62
bool operator==(const TEdgeI &EdgeI) const
Definition: network.h:1122
TEdgeI(const TEdgeI &EdgeI)
Definition: network.h:111
TAStrI BegEAStrI(const TStr &attr) const
Returns an iterator referring to the first edge's str attribute.
Definition: network.h:2021
void DelNode(const int &NId)
Deletes node of ID NId from the network.
Definition: network.h:297
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the network.
Definition: network.h:810
const TNodeData & GetDat() const
Definition: network.h:1078
TNodeData & GetInNDat(const int &EdgeN)
Definition: network.h:1081
TAStrI EndNAStrI(const TStr &attr) const
Returns an iterator referring to the past-the-end node's attribute.
Definition: network.h:1927
void Save(TSOut &SOut) const
Definition: network.h:461
bool IsStrAttrDeletedE(const int &EId, const TStr &attr) const
Definition: network.cpp:266
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: network.h:550
TNodeData & GetInNDat(const int &NodeN)
Definition: network.h:95
THash< TInt, TNode > NodeH
Definition: network.h:581
THashIter NodeHI
Definition: network.h:52
void DelKey(const TKey &Key)
Definition: hash.h:358
Edge iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1110
TAIntI EndNAIntI(const TStr &attr) const
Returns an iterator referring to the past-the-end node's attribute.
Definition: network.h:1917
TNodeEDatNet * Net
Definition: network.h:485
Edge iterator. Only forward iteration (operator++) is supported.
Definition: network.h:544
int GetId() const
Returns ID of the current node.
Definition: network.h:1643
static const int Mn
Definition: dt.h:1046
void GetStrAttrVal(TStrV &Val) const
Gets vector of str attribute values.
Definition: network.h:1691
bool IsOutEId(const int &EId) const
Tests whether the edge with ID EId is an out-edge of current node.
Definition: network.h:1677
TAIntI EndEAIntI(const TStr &attr) const
Returns an iterator referring to the past-the-end edge's attribute.
Definition: network.h:2013
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:503
TInt MxNId
Definition: network.h:1149
TAFltI BegNAFltI(const TStr &attr) const
Returns an iterator referring to the first node's flt attribute.
Definition: network.h:1933
TCRef CRef
Definition: network.h:133
void Clr(const bool &DoDel=true, const bool &ResetDat=true)
Deletes all nodes and edges from the network.
Definition: network.h:702
const TNodeData & GetDat() const
Definition: network.h:92
Node Edge Network (directed graph, TNGraph with data on nodes and edges).
Definition: network.h:441
TVec< TFltV > VecOfFltVecsE
Definition: network.h:1839
TNode & GetNode(const int &NId)
Definition: network.h:576
int GetId() const
Definition: network.h:998
TStrIntPrH KeyToIndexTypeN
KeyToIndexType[N|E]: Key->(Type,Index).
Definition: network.h:1832
TAFltI EndNAFltI(const TStr &attr) const
Returns an iterator referring to the past-the-end node's attribute.
Definition: network.h:1936
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:630
TNodeData & GetDstNDat()
Definition: network.h:1136
TInt GetIntAttrDatE(const TEdgeI &EdgeI, const TStr &attr)
Gets the value of int attr from the edge attr value vector.
Definition: network.h:2187
virtual void Save(TSOut &SOut) const
Saves the network to a (binary) stream SOut.
Definition: network.h:146
int AddStrAttrDatN(const TNodeI &NodeI, const TStr &value, const TStr &attr)
Attribute based add function for attr to Str value.
Definition: network.h:2131
void Gen(const int &ExpectVals)
Definition: hash.h:180
void StrAttrValueEI(const TInt &EId, TStrV &Values) const
Returns a vector of attr values for node NId.
Definition: network.h:1996
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:38
TNode & GetNode(const int &NId)
Definition: network.h:1141
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the network.
Definition: network.h:672
Tests (at compile time) if the graph is a network with data on edges.
Definition: gbase.h:31
TAIntI(const TIntVecIter &HIter, TStr attribute, bool isEdgeIter, const TNEANet *GraphPt)
Definition: network.h:1748
bool Empty() const
Tests whether the network is empty (has zero nodes).
Definition: network.h:700
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: network.h:75
void FltAttrValueEI(const TInt &EId, TFltV &Values) const
Returns a vector of attr values for node NId.
Definition: network.h:2004
TEdgeDat & GetNbrEDat(const int &EdgeN)
Definition: network.h:1104
static PNet Load(TSIn &SIn)
Static constructor that loads the network from a stream SIn and returns a pointer to it...
Definition: network.h:150
TNodeData & GetDstNDat()
Definition: network.h:125
void SortNIdByDat(const bool &Asc=true)
Sorts nodes by node data.
Definition: network.h:1286
int GetId() const
Gets edge ID. Always returns -1 since only edges in multigraphs have explicit IDs.
Definition: network.h:559
int GetNbrNId(const int &EdgeN) const
Returns ID of EdgeN-th neighboring node.
Definition: network.h:1661
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: network.h:2106
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: network.h:552
TFltV::TIter TFltVecIter
Definition: network.h:1787
TEdgeI & operator++(int)
Increment iterator.
Definition: network.h:554
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the network.
Definition: network.h:331
TEdgeI GetRndEI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random edge in the network.
Definition: network.h:1270
int GetDstNId() const
Gets the destination node of an edge.
Definition: network.h:123
int GetId() const
Definition: network.h:1025
TCRef CRef
Definition: network.h:1827
bool operator<(const TNode &Node) const
Definition: network.h:44
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
Definition: network.h:843
TNode(TSIn &SIn)
Definition: network.h:460
TAStrI & operator++(int)
Definition: network.h:1780
int AddIntAttrN(const TStr &attr, TInt defaultValue=TInt::Mn)
Adds a new Int node attribute to the hashmap.
Definition: network.cpp:891
const TNodeData & GetDat() const
Definition: network.h:1002
TStr GetStrAttrDefaultE(const TStr &attribute) const
Get Str edge attribute val. If not a proper attr, return default.
Definition: network.h:1822
const TNodeData & GetSrcNDat() const
Definition: network.h:124
void SortNIdById(const bool &Asc=true)
Sorts nodes by node IDs.
Definition: network.h:242
TNEANet(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a graph of nodes and edges.
Definition: network.h:1848
TAStrI(const TAStrI &I)
Definition: network.h:1772
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: network.h:87
TNEANet()
Definition: network.h:1842
int GetMxNId() const
Returns an ID that is larger than any node ID in the network.
Definition: network.h:195
TNodeData & GetDstNDat()
Definition: network.h:570
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash< TStr, TStr > StrDefaultsN
Definition: network.h:1835
void AttrNameNI(const TInt &NId, TStrV &Names) const
Returns a vector of attr names for node NId.
Definition: network.h:1943
const TEdgeData & GetDat() const
Definition: network.h:1131
Tests (at compile time) if the graph is a multigraph with multiple edges between the same nodes...
Definition: gbase.h:27
#define Assert(Cond)
Definition: bd.h:251
THash< TInt, TNode > NodeH
Definition: network.h:1150
TNodeNet * Net
Definition: network.h:53
TNodeI EndNode
Definition: network.h:106
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: network.h:1904
TNodeNet(TSIn &SIn)
Constructor that loads the network from a (binary) stream SIn.
Definition: network.h:143
int AddStrAttrE(const TStr &attr, TStr defaultValue=TStr::GetNullStr())
Adds a new Str edge attribute to the hashmap.
Definition: network.cpp:969
TEdgeData & GetDat()
Definition: network.h:1132
TFlt GetFltAttrDatN(const TNodeI &NodeI, const TStr &attr)
Gets the value of flt attr from the node attr value vector.
Definition: network.h:2163
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: network.h:2076
TNodeEDatNet(TSIn &SIn)
Constructor that loads the network from a (binary) stream SIn.
Definition: network.h:588
void SortNIdByDat(const bool &Asc=true)
Sorts nodes by node data.
Definition: network.h:709
const TNodeData & operator()() const
Definition: network.h:1076
bool IsOk(const bool &ThrowExcept=true) const
Checks the network data structure for internal consistency.
Definition: network.h:920
TNodeEDatNet< TNodeData, TEdgeData > TNet
Definition: network.h:445
TInt GetIntAttrIndDatN(const TNodeI &NodeI, const int &index)
Gets the value of an int node attr specified by node iterator NodeI and the attr index.
Definition: network.h:2172
THashIter NodeHI
Definition: network.h:484
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: network.h:85
int AddKey(const TKey &Key)
Definition: shash.h:1254
TInt MxNId
Definition: network.h:134
int FFirstKeyId() const
Definition: hash.h:232
int GetId() const
Gets edge ID. Always returns -1 since only edges in multigraphs have explicit IDs.
Definition: network.h:119
TAIntI GetNAIntI(const TStr &attr, const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: network.h:1920
int GetOutEId(const int &EdgeN) const
Returns ID of EdgeN-th out-edge.
Definition: network.h:1090
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: network.h:2078
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the network (see the TGraphFlag for flags).
Definition: network.h:268
int GetInDeg() const
Returns in-degree of the current node.
Definition: network.h:1647
int GetDstNId() const
Definition: network.h:1624
TNode(const int &NId)
Definition: network.h:27
TNodeI(const THashIter &NodeHIter, const TNodeEDatNet *NetPt)
Definition: network.h:488
TEdge(TSIn &SIn)
Definition: network.h:1620
TNodeData & GetSrcNDat()
Definition: network.h:568
TVec< TPair< TInt, TEdgeData > > TNIdDatPrV
Definition: network.h:447
TNodeData & GetDat()
Definition: network.h:93
TNode(const TNode &Node)
Definition: network.h:1599
TStr GetStrAttrDefaultN(const TStr &attribute) const
Get Str node attribute val. If not a proper attr, return default.
Definition: network.h:1816
int GetSrcNId() const
Returns the source of the edge.
Definition: network.h:1716
TEdgeData & GetDat()
Definition: network.h:1029
TNodeNet()
Definition: network.h:138
TStr GetNodeAttrValue(const int &NId, const TStrIntPrH::TIter &NodeHI) const
Definition: network.cpp:158
const TNodeData & GetNDat(const int &NId) const
Returns node data for the node of ID NId in the network.
Definition: network.h:638
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the network.
Definition: network.h:693
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:481
TNodeEdgeNet & operator=(const TNodeEdgeNet &Net)
Definition: network.h:1168
void GetAttrVal(TStrV &Val) const
Gets vector of attribute values.
Definition: network.h:1722
static TStr GetNullStr()
Definition: dt.cpp:1626
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the network.
Definition: network.h:228
bool IsInNId(const int &NId) const
Definition: network.h:473
THash< TInt, TEdge > EdgeH
Definition: network.h:1151
void SetAllEDat(const TEdgeData &EdgeDat)
Sets edge data for all the edges in the network to EDat.
Definition: network.h:1472
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the network (see the TGraphFlag for flags).
Definition: network.h:734
void AttrValueEI(const TInt &EId, TStrV &Values) const
Returns a vector of attr values for edge EId.
Definition: network.h:1980
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:1055
void FltAttrValueNI(const TInt &NId, TFltV &Values) const
Returns a vector of attr values for node NId.
Definition: network.h:1971
TInt MxNId
Definition: network.h:580
Directed multigraph with node edge attributes.
Definition: network.h:1587
Definition: fl.h:128
bool operator==(const TEdgeI &EdgeI) const
Definition: network.h:117
TPt< TNEANet > PNet
Definition: network.h:1590
TEdgeData & GetOutEDat(const int &EdgeN)
Definition: network.h:534
void GetAttrNames(TStrV &Names) const
Gets vector of attribute names.
Definition: network.h:1681
void GetFltAttrVal(TFltV &Val) const
Gets vector of flt attribute values.
Definition: network.h:1695
bool Empty() const
Tests whether the graph is empty (has zero nodes).
Definition: network.h:2098
TInt MxEId
Definition: network.h:1828
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
TAStrI BegNAStrI(const TStr &attr) const
Returns an iterator referring to the first node's str attribute.
Definition: network.h:1923
void GetFltAttrNames(TStrV &Names) const
Gets vector of flt attribute names.
Definition: network.h:1732
TNodeNet(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a network of Nodes nodes and Edges edges.
Definition: network.h:140
bool IsEdge(const int &EId) const
Tests whether an edge with ID EId exists in the network.
Definition: network.h:1240
bool IsDeleted() const
Returns true if the attribute has been deleted.
Definition: network.h:1779
int GetInDeg() const
Definition: network.h:1000
TStrV::TIter TStrVecIter
Definition: network.h:1764
const TNodeData & operator()() const
Definition: network.h:90
TEdgeData & GetEDat(const int &EId)
Returns edge data for the edge with ID EId.
Definition: network.h:1257
int AddNode(const TNodeI &NodeI)
Adds a node NodeI and its node data to the network.
Definition: network.h:171
int GetSrcNId() const
Gets the source of an edge.
Definition: network.h:1126
TPt< TNet > PNet
Definition: network.h:18
bool IsInEId(const int &EId) const
Definition: network.h:1609
static PNEANet GetSmallGraph()
Returns a small multigraph on 5 nodes and 6 edges.
Definition: network.cpp:1056
void SortByKey(const bool &Asc=true)
Definition: hash.h:245
void SetEDat(const int &EId, const TEdgeData &EdgeDat)
Sets edge data for the edge of ID NId in the network.
Definition: network.h:1466
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
Definition: network.h:351
Definition: dt.h:1042
TEdge & GetEdge(const int &EId)
Definition: network.h:1810
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:422
int GetOutDeg() const
Definition: network.h:1605
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: network.h:83
int GetNbrNId(const int &EdgeN) const
Definition: network.h:470
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the network.
Definition: network.h:177
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the graph.
Definition: network.h:2087
int GetEId(const int &SrcNId, const int &DstNId) const
Definition: network.h:1245
int GetId() const
Returns ID of the current node.
Definition: network.h:65
int GetKeyId(const TKey &Key) const
Definition: hash.h:420
THash< TInt, TEdge >::TIter THashIter
Definition: network.h:1112
void IntAttrValueNI(const TInt &NId, TIntV &Values) const
Returns a vector of attr values for node NId.
Definition: network.h:1955
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: network.h:1910
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the network.
Definition: network.h:1264
void GetIntAttrNames(TStrV &Names) const
Gets vector of int attribute names.
Definition: network.h:1685
int AddStrAttrN(const TStr &attr, TStr defaultValue=TStr::GetNullStr())
Adds a new Str node attribute to the hashmap.
Definition: network.cpp:910
const TNodeData & GetOutNDat(const int &NodeN) const
Definition: network.h:96
const TEdgeData & operator()() const
Definition: network.h:1129
int GetId() const
Gets edge ID.
Definition: network.h:1124
const TEdgeDat & GetNbrEDat(const int &EdgeN) const
Definition: network.h:1105
TNode(const int &NId)
Definition: network.h:1598
TNodeNet< TInt > TIntNNet
Definition: network.h:431
TNodeNet< TFlt > TFltNNet
Definition: network.h:433
TNodeData & GetDat()
Definition: network.h:526
int AddNode(int NId=-1)
Adds a node of ID NId to the network.
Definition: network.h:273
bool IsIntAttrDeletedN(const int &NId, const TStr &attr) const
Definition: network.cpp:115
Edge iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1699
TNode(const TNode &Node)
Definition: network.h:29
int DelAttrDatE(const TEdgeI &EdgeI, const TStr &attr)
Deletes the edge attribute for NodeI.
Definition: network.h:2220
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a network of Nodes nodes and Edges edges.
Definition: network.h:705
TNode(const int &NId)
Definition: network.h:457
int Len() const
Definition: shash.h:1121
TNode(const TNode &Node)
Definition: network.h:994
TPt< TStrNNet > PStrNNet
Definition: network.h:436
void SortEIdById(const bool &Asc=true)
Sorts edges by edge IDs.
Definition: network.h:1288
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: network.h:1331
THash< TInt, TEdge >::TIter THashIter
Definition: network.h:1701
void FltAttrNameEI(const TInt &EId, TStrV &Names) const
Returns a vector of int attr names for node NId.
Definition: network.h:2000
TNode(const int &NId)
Definition: network.h:992
TNodeEdgeNet(TSIn &SIn)
Constructor that loads the network from a (binary) stream SIn.
Definition: network.h:1158
TNodeI BegNI() const
Returns an iterator referring to the first node in the network.
Definition: network.h:626
TNodeData TNodeDat
Definition: network.h:443
TEdgeData TEdgeDat
Definition: network.h:981
TNodeEdgeNet< TNodeData, TEdgeData > TNet
Definition: network.h:982
int GetId() const
Definition: network.h:32
bool operator<(const TEdgeI &EdgeI) const
Definition: network.h:1121
THash< TStr, TStr > StrDefaultsE
Definition: network.h:1835
const TEdgeData & GetDat() const
Definition: network.h:567
int GetOutDeg() const
Definition: network.h:465
int GetInEId(const int &NodeN) const
Definition: network.h:1004
void SetNDat(const int &NId, const TNodeData &NodeDat)
Sets node data for the node of ID NId in the network.
Definition: network.h:776
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the network.
Definition: network.h:1200
const TNode & GetNodeKId(const int &NodeKeyId) const
Definition: network.h:1143
const TNodeData & GetSrcNDat() const
Definition: network.h:1133
void StrAttrNameEI(const TInt &EId, TStrV &Names) const
Returns a vector of str attr names for node NId.
Definition: network.h:1992
TFlt GetFltAttrDefaultE(const TStr &attribute) const
Get Flt edge attribute val. If not a proper attr, return default.
Definition: network.h:1824
int GetEdges() const
Returns the number of edges in the graph.
Definition: network.h:2049
void Save(TSOut &SOut) const
Definition: network.h:1621
TNodeNet< TNodeData > TNet
Definition: network.h:17
TNodeNet< TStr > TStrNNet
Definition: network.h:435
int GetOutEId(const int &EdgeN) const
Definition: network.h:1607
THashIter NodeHI
Definition: network.h:1037
int GetInDeg() const
Returns in-degree of the current node.
Definition: network.h:1053
TNodeI CurNode
Definition: network.h:106
bool EdgeAttrIsStrDeleted(const int &EId, const TStrIntPrH::TIter &EdgeHI) const
Definition: network.cpp:287
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: network.h:1866
void GetEIdV(TIntV &EIdV) const
Returns a vector of all edge IDs in the network.
Definition: network.h:1488
bool IsInEId(const int &EId) const
Definition: network.h:1007
TEdgeI(const TEdgeI &EdgeI)
Definition: network.h:1118
Definition: dt.h:412
int AddStrAttrDatE(const TEdgeI &EdgeI, const TStr &value, const TStr &attr)
Attribute based add function for attr to Str value.
Definition: network.h:2147
void GetAttrVal(TStrV &Val) const
Gets vector of attribute values.
Definition: network.h:1683
const TEdgeDat & GetInEDat(const int &EdgeN) const
Definition: network.h:1101
const TNodeData & GetDstNDat() const
Definition: network.h:571
TNodeNet & operator=(const TNodeNet &NodeNet)
Definition: network.h:153
const TNodeData & GetNbrNDat(const int &NodeN) const
Definition: network.h:98
TNEANet(const TNEANet &Graph)
Definition: network.h:1854
TEdgeI(const TEdgeI &EdgeI)
Definition: network.h:1707
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1223
void Pack()
The vector reduces its capacity (frees memory) to match its size.
Definition: ds.h:987
static PNet New()
Static constructor that returns a pointer to the network. Call: TPt > Net = TNodeEdgeNet::New().
Definition: network.h:1163
void DelEdge(const int &EId)
Deletes an edge with ID EId from the network.
Definition: network.h:1427
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
TPt< TIntNNet > PIntNNet
Definition: network.h:432
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: network.h:79
bool operator<(const TEdge &Edge) const
Definition: network.h:1024
TNodeEdgeNet * Net
Definition: network.h:1038
TNode(TSIn &SIn)
Definition: network.h:1600
const TNode & GetNode(const int &NId) const
Definition: network.h:1809
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: network.h:511
int GetMxEId() const
Returns an ID that is larger than any edge ID in the network.
Definition: network.h:2046
Definition: hash.h:88
int GetEdges() const
Returns the number of edges in the network.
Definition: network.h:1212
int GetInDeg() const
Definition: network.h:34
int GetNbrEId(const int &EdgeN) const
Returns ID of EdgeN-th in or out-edge.
Definition: network.h:1673
TAIntI & operator++(int)
Definition: network.h:1757
bool IsAttrDeletedN(const int &NId, const TStr &attr) const
Definition: network.cpp:108
const TEdgeData & GetDat() const
Definition: network.h:1028
int GetDeg() const
Definition: network.h:1603
TVec< TFltV > VecOfFltVecsN
Definition: network.h:1839
int GetInDeg() const
Definition: network.h:1604
TAFltI EndEAFltI(const TStr &attr) const
Returns an iterator referring to the past-the-end edge's attribute.
Definition: network.h:2036
TIntV::TIter TIntVecIter
Definition: network.h:1741
TAFltI GetNAFltI(const TStr &attr, const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: network.h:1939
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the network (see the TGraphFlag for flags).
Definition: network.h:1316
void Clr()
Deletes all nodes and edges from the graph.
Definition: network.h:2100
void Clr(const bool &DoDel=true, const bool &ResetDat=true)
Deletes all nodes and edges from the network.
Definition: network.h:237
TEdgeData & GetNbrEDat(const int &EdgeN)
Definition: network.h:538
int GetId() const
Definition: network.h:1602
const TNodeData & GetNbrNDat(const int &EdgeN) const
Definition: network.h:1084
int GetDeg() const
Definition: network.h:463
TNodeData NodeDat
Definition: network.h:452
int GetEId(const int &SrcNId, const int &DstNId) const
Returns an edge ID between node IDs SrcNId and DstNId, if such an edge exists. Otherwise, return -1.
Definition: network.h:2074
bool Empty() const
Tests whether the network is empty (has zero nodes).
Definition: network.h:1277
virtual ~TNodeNet()
Definition: network.h:144
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: network.h:521
const TNodeData & GetOutNDat(const int &NodeN) const
Definition: network.h:527
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the network.
Definition: network.h:1192
TEdgeI GetEI(const int &SrcNId, const int &DstNId) const
Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
Definition: network.h:1253
TVal2 Val2
Definition: ds.h:35
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:315
bool IsInEId(const int &EId) const
Tests whether the edge with ID EId is an in-edge of current node.
Definition: network.h:1094
bool operator<(const TNode &Node) const
Definition: network.h:476
Definition: bd.h:196
int AddEdge(const TEdgeI &EdgeI)
Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() and its edge data to the network...
Definition: network.h:662
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the network.
Definition: network.h:358
THash< TStr, TInt > IntDefaultsN
Definition: network.h:1834
int GetDstNId() const
Definition: network.h:1027
TNodeI(const THashIter &NodeHIter, const TNEANet *GraphPt)
Definition: network.h:1635
TNodeEdgeNet * Net
Definition: network.h:1114
const TNode & GetNode(const int &NId) const
Returns node element for the node of ID NId in the network.
Definition: network.h:632
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: network.h:1906
const TNEANet * Graph
Definition: network.h:1791
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the network.
Definition: network.h:373
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the network.
Definition: network.h:909
void DelNode(const int &NId)
Deletes node of ID NId from the network.
Definition: network.h:1365
bool NodeAttrIsIntDeleted(const int &NId, const TStrIntPrH::TIter &NodeHI) const
Definition: network.cpp:134
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:71
THash< TInt, TNode > NodeH
Definition: network.h:1829
int GetSrcNId() const
Definition: network.h:1026
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:398
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: network.h:1074
TEdge & GetEdge(const int &EId)
Definition: network.h:1144
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: network.h:1119
TFlt GetFltAttrIndDatN(const TNodeI &NodeI, const int &index)
Gets the value of a float node attr specified by node iterator NodeI and the attr index...
Definition: network.h:2182
int GetDstNId() const
Gets the destination node of an edge.
Definition: network.h:563
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: network.h:112
TPt< TNet > PNet
Definition: network.h:983
bool IsNbrEId(const int &EId) const
Tests whether the edge with ID EId is an in or out-edge of current node.
Definition: network.h:1098
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: network.h:1908
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the network.
Definition: network.h:902
int GetInDeg() const
Definition: network.h:464
int AddIntAttrE(const TStr &attr, TInt defaultValue=TInt::Mn)
Adds a new Int edge attribute to the hashmap.
Definition: network.cpp:949
THashIter EdgeHI
Definition: network.h:1702
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the network.
Definition: network.h:219
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:506
TEdge(const int &EId, const int &SourceNId, const int &DestNId)
Definition: network.h:1618
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: network.h:1912
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:628
const TEdgeData & GetOutEDat(const int &EdgeN) const
Definition: network.h:535
TFlt GetFltAttrDefaultN(const TStr &attribute) const
Get Flt node attribute val. If not a proper attr, return default.
Definition: network.h:1818
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: network.h:1321
int GetInEId(const int &EdgeN) const
Definition: network.h:1606
void IntAttrNameEI(const TInt &EId, TStrV &Names) const
Returns a vector of int attr names for edge EId.
Definition: network.h:1984
TEdgeData & GetDat()
Definition: network.h:566
void GetIntAttrNames(TStrV &Names) const
Gets vector of int attribute names.
Definition: network.h:1724
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a network of Nodes nodes and Edges edges.
Definition: network.h:240
TNodeI & operator=(const TNodeI &NodeI)
Definition: network.h:490
TInt GetIntAttrDefaultN(const TStr &attribute) const
Get Int node attribute val. If not a proper attr, return default.
Definition: network.h:1814
TAStrI(const TStrVecIter &HIter, TStr attribute, bool isEdgeIter, const TNEANet *GraphPt)
Definition: network.h:1771
TNodeEdgeNet< TInt, TInt > TIntNENet
Definition: network.h:1561
static PNet Load(TSIn &SIn)
Static constructor that loads the network from a stream SIn and returns a pointer to it...
Definition: network.h:595
bool IsOk(const bool &ThrowExcept=true) const
Checks the network data structure for internal consistency.
Definition: network.h:383
TIntVecIter HI
Definition: network.h:1742
char * CStr()
Definition: dt.h:476
TNodeData & GetNbrNDat(const int &NodeN)
Definition: network.h:99
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:49
THashIter NodeHI
Definition: network.h:1631
TPt< TNEANet > PNEANet
Pointer to a directed attribute multigraph (TNEANet)
Definition: network.h:1566
bool IsKey(const TKey &Key) const
Definition: hash.h:216
TNEANet TNet
Definition: network.h:1589
const TEdge & GetEdge(const int &EId) const
Definition: network.h:1811
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
static PNEANet New()
Static cons returns pointer to graph. Ex: PNEANet Graph=TNEANet::New().
Definition: network.h:1876
void GetFltAttrNames(TStrV &Names) const
Gets vector of flt attribute names.
Definition: network.h:1693
bool IsOk(const bool &ThrowExcept=true) const
Checks the network data structure for internal consistency.
Definition: network.h:1506
TIntV OutNIdV
Definition: network.h:24
TNodeI(const TNodeI &NodeI)
Definition: network.h:1042
int Len() const
Definition: hash.h:186
TNodeData & GetOutNDat(const int &NodeN)
Definition: network.h:528
int DelAttrDatN(const TNodeI &NodeI, const TStr &attr)
Deletes the node attribute for NodeI.
Definition: network.h:2217
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: network.h:1051
void GetStrAttrNames(TStrV &Names) const
Gets vector of str attribute names.
Definition: network.h:1689
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
Definition: network.h:1242
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the network.
Definition: network.h:1249
bool operator==(const TNodeI &NodeI) const
Definition: network.h:494
TEdgeDat & GetInEDat(const int &EdgeN)
Definition: network.h:1100
void Save(TSOut &SOut) const
Definition: network.h:31
Node/edge string attribute iterator. Iterates through all nodes/edges for one string attribute...
Definition: network.h:1762
bool operator<(const TNodeI &NodeI) const
Definition: network.h:493
void GetAttrNames(TStrV &Names) const
Gets vector of attribute names.
Definition: network.h:1720
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1034
int AddIntAttrDatN(const TNodeI &NodeI, const TInt &value, const TStr &attr)
Attribute based add function for attr to Int value.
Definition: network.h:2126
void GetIntAttrVal(TIntV &Val) const
Gets vector of int attribute values.
Definition: network.h:1726
int GetIntAttrIndE(const TStr &attr)
Gets the index of the edge attr value vector specified by attr (same as GetAttrIndE for compatibility...
Definition: network.cpp:854
TAFltI(const TFltVecIter &HIter, TStr attribute, bool isEdgeIter, const TNEANet *GraphPt)
Definition: network.h:1794
const TNEANet * Graph
Definition: network.h:1745
void Save(TSOut &SOut) const
Definition: network.h:1023
TAIntI(const TAIntI &I)
Definition: network.h:1749
TStr GetStrAttrIndDatN(const TNodeI &NodeI, const int &index)
Gets the value of a string node attr specified by node iterator NodeI and the attr index...
Definition: network.h:2177
THash< TInt, TNode >::TIter THashIter
Definition: network.h:51
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the network.
Definition: network.h:1198
void GetIntAttrVal(TIntV &Val) const
Gets vector of int attribute values.
Definition: network.h:1687
TNIdDatPrV OutNIdV
Definition: network.h:454
const TNEANet * Graph
Definition: network.h:1768
int GetOutEId(const int &NodeN) const
Definition: network.h:1005
static PNEANet New(const int &Nodes, const int &Edges)
Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and...
Definition: network.h:1880
int GetRndEId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random edge in the network.
Definition: network.h:1268
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
int GetMxNId() const
Returns an ID that is larger than any node ID in the network.
Definition: network.h:2044
THash< TInt, TNode >::TIter THashIter
Definition: network.h:1036
Node Network (directed graph, TNGraph with data on nodes only).
Definition: network.h:14
int GetId() const
Returns ID of the current node.
Definition: network.h:1049
int GetDeg() const
Returns degree of the current node.
Definition: network.h:499
const TEdgeData & GetEDat(const int &EId) const
Returns edge data for the edge with ID EId.
Definition: network.h:1259
TNodeEDatNet< TStr, TInt > TStrIntNEDNet
Definition: network.h:972
const TEdgeData & GetNbrEDat(const int &EdgeN) const
Definition: network.h:539
int GetId() const
Returns ID of the current node.
Definition: network.h:497
const TNodeData & GetDstNDat() const
Definition: network.h:1135
const TNodeData & GetDat() const
Definition: network.h:525
int AddFltAttrE(const TStr &attr, TFlt defaultValue=TFlt::Mn)
Adds a new Flt edge attribute to the hashmap.
Definition: network.cpp:988
TNode(const int &NId, const TNodeData &NodeData)
Definition: network.h:28
int GetDstNId() const
Gets destination of an edge.
Definition: network.h:1128
static const double Mn
Definition: dt.h:1295
TNodeEDatNet()
Definition: network.h:583
int GetNbrNId(const int &NodeN) const
Definition: network.h:40
bool operator==(const TNodeI &NodeI) const
Definition: network.h:1047
int GetOutDeg() const
Definition: network.h:35
static PNet Load(TSIn &SIn)
Static constructor that loads the network from a stream SIn and returns a pointer to it...
Definition: network.h:1165
TFlt GetFltAttrIndDatE(const TEdgeI &EdgeI, const int &index)
Gets the value of a float edge attr specified by edge iterator EdgeI and the attr index...
Definition: network.h:2207
TNodeEdgeNet(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a network of Nodes nodes and Edges edges.
Definition: network.h:1155
int GetNodes() const
Returns the number of nodes in the network.
Definition: network.h:602
TInt GetIntAttrIndDatE(const TEdgeI &EdgeI, const int &index)
Gets the value of an int edge attr specified by edge iterator EdgeI and the attr index.
Definition: network.h:2202
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the network.
Definition: network.h:695
TIter GetI(const TKey &Key) const
Definition: hash.h:178
void SortByDat(const bool &Asc=true)
Definition: hash.h:246
TPt< TFltNENet > PFltNENet
Definition: network.h:1564
int GetMxNId() const
Returns an ID that is larger than any node ID in the network.
Definition: network.h:640
TNodeData & GetSrcNDat()
Definition: network.h:1134
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the network.
Definition: network.h:221
int AddFltAttrN(const TStr &attr, TFlt defaultValue=TFlt::Mn)
Adds a new Flt node attribute to the hashmap.
Definition: network.cpp:929