SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
graph.h
Go to the documentation of this file.
1 //#//////////////////////////////////////////////
3 
4 class TUNGraph;
5 class TBPGraph;
6 //TODO:class TUNEGraph; -- undirected multigraph
7 
9 typedef TPt<TUNGraph> PUNGraph;
12 
13 //#//////////////////////////////////////////////
15 class TNGraph;
16 class TNEGraph;
17 
19 typedef TPt<TNGraph> PNGraph;
22 
23 //#//////////////////////////////////////////////
25 
32 class TUNGraph {
33 public:
34  typedef TUNGraph TNet;
36 public:
37  class TNode {
38  private:
41  public:
42  TNode() : Id(-1), NIdV() { }
43  TNode(const int& NId) : Id(NId), NIdV() { }
44  TNode(const TNode& Node) : Id(Node.Id), NIdV(Node.NIdV) { }
45  TNode(TSIn& SIn) : Id(SIn), NIdV(SIn) { }
46  void LoadShM(TShMIn& ShMIn) {
47  Id = TInt(ShMIn);
48  NIdV.LoadShM(ShMIn);
49  }
50  void Save(TSOut& SOut) const { Id.Save(SOut); NIdV.Save(SOut); }
51  int GetId() const { return Id; }
52  int GetDeg() const { return NIdV.Len(); }
53  int GetInDeg() const { return GetDeg(); }
54  int GetOutDeg() const { return GetDeg(); }
55  int GetInNId(const int& NodeN) const { return GetNbrNId(NodeN); }
56  int GetOutNId(const int& NodeN) const { return GetNbrNId(NodeN); }
57  int GetNbrNId(const int& NodeN) const { return NIdV[NodeN]; }
58  bool IsNbrNId(const int& NId) const { return NIdV.SearchBin(NId)!=-1; }
59  bool IsInNId(const int& NId) const { return IsNbrNId(NId); }
60  bool IsOutNId(const int& NId) const { return IsNbrNId(NId); }
61  void PackOutNIdV() { NIdV.Pack(); }
62  void PackNIdV() { NIdV.Pack(); }
63  void SortNIdV() { NIdV.Sort();}
64  friend class TUNGraph;
65  friend class TUNGraphMtx;
66  };
68  class TNodeI {
69  private:
71  THashIter NodeHI;
72  public:
73  TNodeI() : NodeHI() { }
74  TNodeI(const THashIter& NodeHIter) : NodeHI(NodeHIter) { }
75  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI) { }
76  TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; return *this; }
77 
79  TNodeI& operator++ (int) { NodeHI++; return *this; }
81  TNodeI& operator-- (int) { NodeHI--; return *this; }
82 
83 
84  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
85  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
86 
88  int GetId() const { return NodeHI.GetDat().GetId(); }
90  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
92  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
94  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
96  void SortNIdV() { NodeHI.GetDat().SortNIdV(); }
98 
101  int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }
103 
106  int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }
108 
111  int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
113  bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
115  bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
117  bool IsNbrNId(const int& NId) const { return NodeHI.GetDat().IsNbrNId(NId); }
118  friend class TUNGraph;
119  };
121  class TEdgeI {
122  private:
124  int CurEdge;
125  public:
126  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
127  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
128  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
129  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
131  TEdgeI& operator++ (int) { do { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++; while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } } while (CurNode < EndNode && GetSrcNId()>GetDstNId()); return *this; }
132  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
133  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
135  int GetId() const { return -1; }
137  int GetSrcNId() const { return CurNode.GetId(); }
139  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
140  friend class TUNGraph;
141  };
142 private:
146 private:
148  public:
150  void operator() (TNode* Node, TShMIn& ShMIn) { Node->LoadShM(ShMIn);}
151  };
152 private:
153  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
154  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
155  void LoadGraphShM(TShMIn& ShMIn) {
156  MxNId = TInt(ShMIn);
157  NEdges = TInt(ShMIn);
159  NodeH.LoadShM(ShMIn, Fn);
160  }
161 public:
162  TUNGraph() : CRef(), MxNId(0), NEdges(0), NodeH() { }
164  explicit TUNGraph(const int& Nodes, const int& Edges) : MxNId(0), NEdges(0) { Reserve(Nodes, Edges); }
165  TUNGraph(const TUNGraph& Graph) : MxNId(Graph.MxNId), NEdges(Graph.NEdges), NodeH(Graph.NodeH) { }
167  TUNGraph(TSIn& SIn) : MxNId(SIn), NEdges(SIn), NodeH(SIn) { }
169 
170  void Save(TSOut& SOut) const { MxNId.Save(SOut); NEdges.Save(SOut); NodeH.Save(SOut); }
172  static PUNGraph New() { return new TUNGraph(); }
174 
176  static PUNGraph New(const int& Nodes, const int& Edges) { return new TUNGraph(Nodes, Edges); }
178  static PUNGraph Load(TSIn& SIn) { return PUNGraph(new TUNGraph(SIn)); }
180 
182  static PUNGraph LoadShM(TShMIn& ShMIn) {
183  TUNGraph* Graph = new TUNGraph();
184  Graph->LoadGraphShM(ShMIn);
185  return PUNGraph(Graph);
186  }
187  bool HasFlag(const TGraphFlag& Flag) const;
188  TUNGraph& operator = (const TUNGraph& Graph) {
189  if (this!=&Graph) { MxNId=Graph.MxNId; NEdges=Graph.NEdges; NodeH=Graph.NodeH; } return *this; }
190 
192  int GetNodes() const { return NodeH.Len(); }
194 
198  int AddNode(int NId = -1);
200 
204  int AddNodeUnchecked(int NId = -1);
206  int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId()); }
208 
217  int AddNode(const int& NId, const TIntV& NbrNIdV);
219 
227  int AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& NIdVId);
229 
231  void DelNode(const int& NId);
233  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
235  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
237  TNodeI BegNI() const { return TNodeI(NodeH.BegI()); }
239  TNodeI EndNI() const { return TNodeI(NodeH.EndI()); }
241  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId)); }
243  int GetMxNId() const { return MxNId; }
244 
246  int GetEdges() const;
248 
252  int AddEdge(const int& SrcNId, const int& DstNId);
254  int AddEdge(const int& SrcNId, const int& DstNId, const int& EId) { return AddEdge(SrcNId, DstNId); }
256 
263  int AddEdgeUnchecked(const int& SrcNId, const int& DstNId);
265  int AddEdge2(const int& SrcNId, const int& DstNId);
267  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
269 
272  void DelEdge(const int& SrcNId, const int& DstNId);
274  bool IsEdge(const int& SrcNId, const int& DstNId) const;
276  bool IsEdge(const int& EId) const { return false; }
278  TEdgeI BegEI() const { TNodeI NI = BegNI(); TEdgeI EI(NI, EndNI(), 0); if (GetNodes() != 0 && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { EI++; } return EI; }
280  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
282  TEdgeI GetEI(const int& EId) const;
284 
286  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;
287 
289  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
291  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
293  void GetNIdV(TIntV& NIdV) const;
294 
296  bool Empty() const { return GetNodes()==0; }
298  void Clr() { MxNId=0; NEdges=0; NodeH.Clr(); }
300  void SortNodeAdjV() { for (TNodeI NI = BegNI(); NI < EndNI(); NI++) { NI.SortNIdV();} }
302  void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) NodeH.Gen(Nodes/2); }
304  void ReserveNIdDeg(const int& NId, const int& Deg) { GetNode(NId).NIdV.Reserve(Deg); }
306 
310  void Defrag(const bool& OnlyNodeLinks=false);
312 
314  bool IsOk(const bool& ThrowExcept=true) const;
316  void Dump(FILE *OutF=stdout) const;
318 
324  static PUNGraph GetSmallGraph();
325 
326  friend class TUNGraphMtx;
327  friend class TPt<TUNGraph>;
328 };
329 
330 //#//////////////////////////////////////////////
332 
346 class TNGraph {
347 public:
348  typedef TNGraph TNet;
350 public:
351  class TNode {
352  private:
355  public:
356  TNode() : Id(-1), InNIdV(), OutNIdV() { }
357  TNode(const int& NId) : Id(NId), InNIdV(), OutNIdV() { }
358  TNode(const TNode& Node) : Id(Node.Id), InNIdV(Node.InNIdV), OutNIdV(Node.OutNIdV) { }
359  TNode(TSIn& SIn) : Id(SIn), InNIdV(SIn), OutNIdV(SIn) { }
360  void Save(TSOut& SOut) const { Id.Save(SOut); InNIdV.Save(SOut); OutNIdV.Save(SOut); }
361  int GetId() const { return Id; }
362  int GetDeg() const { return GetInDeg() + GetOutDeg(); }
363  int GetInDeg() const { return InNIdV.Len(); }
364  int GetOutDeg() const { return OutNIdV.Len(); }
365  int GetInNId(const int& NodeN) const { return InNIdV[NodeN]; }
366  int GetOutNId(const int& NodeN) const { return OutNIdV[NodeN]; }
367  int GetNbrNId(const int& NodeN) const { return NodeN<GetOutDeg()?GetOutNId(NodeN):GetInNId(NodeN-GetOutDeg()); }
368  bool IsInNId(const int& NId) const { return InNIdV.SearchBin(NId) != -1; }
369  bool IsOutNId(const int& NId) const { return OutNIdV.SearchBin(NId) != -1; }
370  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
371  void PackOutNIdV() { OutNIdV.Pack(); }
372  void PackNIdV() { InNIdV.Pack(); }
373  void SortNIdV() { InNIdV.Sort(); OutNIdV.Sort();}
374  void LoadShM(TShMIn& ShMIn) {
375  Id = TInt(ShMIn);
376  InNIdV.LoadShM(ShMIn);
377  OutNIdV.LoadShM(ShMIn);
378  }
379  friend class TNGraph;
380  friend class TNGraphMtx;
381  };
383  class TNodeI {
384  private:
386  THashIter NodeHI;
387  public:
388  TNodeI() : NodeHI() { }
389  TNodeI(const THashIter& NodeHIter) : NodeHI(NodeHIter) { }
390  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI) { }
391  TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; return *this; }
393  TNodeI& operator++ (int) { NodeHI++; return *this; }
395  TNodeI& operator-- (int) { NodeHI--; return *this; }
396 
397  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
398  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
400  int GetId() const { return NodeHI.GetDat().GetId(); }
402  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
404  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
406  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
408  void SortNIdV() { NodeHI.GetDat().SortNIdV(); }
410 
412  int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }
414 
416  int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }
418 
420  int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
422  bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
424  bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
426  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
427  friend class TNGraph;
428  };
430  class TEdgeI {
431  private:
433  int CurEdge;
434  public:
435  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
436  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
437  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
438  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
440  TEdgeI& operator++ (int) { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++;
441  while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; }
442  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
443  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
445  int GetId() const { return -1; }
447  int GetSrcNId() const { return CurNode.GetId(); }
449  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
450  friend class TNGraph;
451  };
452 private:
456 private:
458  public:
460  void operator() (TNode* Node, TShMIn& ShMIn) {Node->LoadShM(ShMIn);}
461  };
462 private:
463  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
464  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
465  void LoadGraphShM(TShMIn& ShMIn) {
466  MxNId = TInt(ShMIn);
468  NodeH.LoadShM(ShMIn, Fn);
469  }
470 
471 public:
472  TNGraph() : CRef(), MxNId(0), NodeH() { }
474  explicit TNGraph(const int& Nodes, const int& Edges) : MxNId(0) { Reserve(Nodes, Edges); }
475  TNGraph(const TNGraph& Graph) : MxNId(Graph.MxNId), NodeH(Graph.NodeH) { }
477  TNGraph(TSIn& SIn) : MxNId(SIn), NodeH(SIn) { }
479  void Save(TSOut& SOut) const { MxNId.Save(SOut); NodeH.Save(SOut); }
481  static PNGraph New() { return new TNGraph(); }
483 
485  static PNGraph New(const int& Nodes, const int& Edges) { return new TNGraph(Nodes, Edges); }
487  static PNGraph Load(TSIn& SIn) { return PNGraph(new TNGraph(SIn)); }
489 
492  static PNGraph LoadShM(TShMIn& ShMIn) {
493  TNGraph* Graph = new TNGraph();
494  Graph->LoadGraphShM(ShMIn);
495  return PNGraph(Graph);
496  }
498  bool HasFlag(const TGraphFlag& Flag) const;
499  TNGraph& operator = (const TNGraph& Graph) {
500  if (this!=&Graph) { MxNId=Graph.MxNId; NodeH=Graph.NodeH; } return *this; }
501 
503  int GetNodes() const { return NodeH.Len(); }
505 
509  int AddNode(int NId = -1);
511 
515  int AddNodeUnchecked(int NId = -1);
517  int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId()); }
519 
528  int AddNode(const int& NId, const TIntV& InNIdV, const TIntV& OutNIdV);
530 
538  int AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& SrcVId, const int& DstVId);
540 
542  void DelNode(const int& NId);
544  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
546  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
548  TNodeI BegNI() const { return TNodeI(NodeH.BegI()); }
550  TNodeI EndNI() const { return TNodeI(NodeH.EndI()); }
552  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId)); }
553  // GetNodeC() has been commented out. It was a quick shortcut, do not use.
554  //const TNode& GetNodeC(const int& NId) const { return NodeH.GetDat(NId); }
556  int GetMxNId() const { return MxNId; }
557 
559  int GetEdges() const;
561 
567  int AddEdge(const int& SrcNId, const int& DstNId);
569  int AddEdge(const int& SrcNId, const int& DstNId, const int& EId) { return AddEdge(SrcNId, DstNId); }
571 
578  int AddEdgeUnchecked(const int& SrcNId, const int& DstNId);
580  int AddEdge2(const int& SrcNId, const int& DstNId);
582  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
584 
588  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
590  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const;
592  bool IsEdge(const int& EId) const { return false; }
594  TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0){NI++;} return TEdgeI(NI, EndNI()); }
596  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
598  TEdgeI GetEI(const int& EId) const; // not supported
600  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;
601 
603  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
605  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
607  void GetNIdV(TIntV& NIdV) const;
608 
610  bool Empty() const { return GetNodes()==0; }
612  void Clr() { MxNId=0; NodeH.Clr(); }
614  void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) { NodeH.Gen(Nodes/2); } }
616  void ReserveNIdInDeg(const int& NId, const int& InDeg) { GetNode(NId).InNIdV.Reserve(InDeg); }
618  void ReserveNIdOutDeg(const int& NId, const int& OutDeg) { GetNode(NId).OutNIdV.Reserve(OutDeg); }
620  void SortNodeAdjV() { for (TNodeI NI = BegNI(); NI < EndNI(); NI++) { NI.SortNIdV();} }
622 
627  void Defrag(const bool& OnlyNodeLinks=false);
629 
632  bool IsOk(const bool& ThrowExcept=true) const;
634  void Dump(FILE *OutF=stdout) const;
636 
640  static PNGraph GetSmallGraph();
641  friend class TPt<TNGraph>;
642  friend class TNGraphMtx;
643 };
644 
645 // set flags
646 namespace TSnap {
647 template <> struct IsDirected<TNGraph> { enum { Val = 1 }; };
648 }
649 
650 //#//////////////////////////////////////////////
652 
665 class TNEGraph {
666 public:
667  typedef TNEGraph TNet;
669 public:
670  class TNode {
671  private:
674  public:
675  TNode() : Id(-1), InEIdV(), OutEIdV() { }
676  TNode(const int& NId) : Id(NId), InEIdV(), OutEIdV() { }
677  TNode(const TNode& Node) : Id(Node.Id), InEIdV(Node.InEIdV), OutEIdV(Node.OutEIdV) { }
678  TNode(TSIn& SIn) : Id(SIn), InEIdV(SIn), OutEIdV(SIn) { }
679  void Save(TSOut& SOut) const { Id.Save(SOut); InEIdV.Save(SOut); OutEIdV.Save(SOut); }
680  int GetId() const { return Id; }
681  int GetDeg() const { return GetInDeg() + GetOutDeg(); }
682  int GetInDeg() const { return InEIdV.Len(); }
683  int GetOutDeg() const { return OutEIdV.Len(); }
684  int GetInEId(const int& EdgeN) const { return InEIdV[EdgeN]; }
685  int GetOutEId(const int& EdgeN) const { return OutEIdV[EdgeN]; }
686  int GetNbrEId(const int& EdgeN) const { return EdgeN<GetOutDeg()?GetOutEId(EdgeN):GetInEId(EdgeN-GetOutDeg()); }
687  bool IsInEId(const int& EId) const { return InEIdV.SearchBin(EId) != -1; }
688  bool IsOutEId(const int& EId) const { return OutEIdV.SearchBin(EId) != -1; }
689  friend class TNEGraph;
690  };
691  class TEdge {
692  private:
694  public:
695  TEdge() : Id(-1), SrcNId(-1), DstNId(-1) { }
696  TEdge(const int& EId, const int& SourceNId, const int& DestNId) : Id(EId), SrcNId(SourceNId), DstNId(DestNId) { }
697  TEdge(const TEdge& Edge) : Id(Edge.Id), SrcNId(Edge.SrcNId), DstNId(Edge.DstNId) { }
698  TEdge(TSIn& SIn) : Id(SIn), SrcNId(SIn), DstNId(SIn) { }
699  void Save(TSOut& SOut) const { Id.Save(SOut); SrcNId.Save(SOut); DstNId.Save(SOut); }
700  int GetId() const { return Id; }
701  int GetSrcNId() const { return SrcNId; }
702  int GetDstNId() const { return DstNId; }
703  friend class TNEGraph;
704  };
706  class TNodeI {
707  private:
709  THashIter NodeHI;
710  const TNEGraph *Graph;
711  public:
712  TNodeI() : NodeHI(), Graph(NULL) { }
713  TNodeI(const THashIter& NodeHIter, const TNEGraph* GraphPt) : NodeHI(NodeHIter), Graph(GraphPt) { }
714  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Graph(NodeI.Graph) { }
715  TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; Graph=NodeI.Graph; return *this; }
717  TNodeI& operator++ (int) { NodeHI++; return *this; }
719  TNodeI& operator-- (int) { NodeHI--; return *this; }
720 
721  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
722  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
724  int GetId() const { return NodeHI.GetDat().GetId(); }
726  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
728  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
730  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
732 
734  int GetInNId(const int& EdgeN) const { return Graph->GetEdge(NodeHI.GetDat().GetInEId(EdgeN)).GetSrcNId(); }
736 
738  int GetOutNId(const int& EdgeN) const { return Graph->GetEdge(NodeHI.GetDat().GetOutEId(EdgeN)).GetDstNId(); }
740 
742  int GetNbrNId(const int& EdgeN) const { const TEdge& E = Graph->GetEdge(NodeHI.GetDat().GetNbrEId(EdgeN));
743  return GetId()==E.GetSrcNId() ? E.GetDstNId():E.GetSrcNId(); }
745  bool IsInNId(const int& NId) const;
747  bool IsOutNId(const int& NId) const;
749  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
750  // edges
752  int GetInEId(const int& EdgeN) const { return NodeHI.GetDat().GetInEId(EdgeN); }
754  int GetOutEId(const int& EdgeN) const { return NodeHI.GetDat().GetOutEId(EdgeN); }
756  int GetNbrEId(const int& EdgeN) const { return NodeHI.GetDat().GetNbrEId(EdgeN); }
758  bool IsInEId(const int& EId) const { return NodeHI.GetDat().IsInEId(EId); }
760  bool IsOutEId(const int& EId) const { return NodeHI.GetDat().IsOutEId(EId); }
762  bool IsNbrEId(const int& EId) const { return IsInEId(EId) || IsOutEId(EId); }
763  friend class TNEGraph;
764  };
766  class TEdgeI {
767  private:
769  THashIter EdgeHI;
770  const TNEGraph *Graph;
771  public:
772  TEdgeI() : EdgeHI(), Graph(NULL) { }
773  TEdgeI(const THashIter& EdgeHIter, const TNEGraph *GraphPt) : EdgeHI(EdgeHIter), Graph(GraphPt) { }
774  TEdgeI(const TEdgeI& EdgeI) : EdgeHI(EdgeI.EdgeHI), Graph(EdgeI.Graph) { }
775  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { EdgeHI=EdgeI.EdgeHI; Graph=EdgeI.Graph; } return *this; }
777  TEdgeI& operator++ (int) { EdgeHI++; return *this; }
778  bool operator < (const TEdgeI& EdgeI) const { return EdgeHI < EdgeI.EdgeHI; }
779  bool operator == (const TEdgeI& EdgeI) const { return EdgeHI == EdgeI.EdgeHI; }
781  int GetId() const { return EdgeHI.GetDat().GetId(); }
783  int GetSrcNId() const { return EdgeHI.GetDat().GetSrcNId(); }
785  int GetDstNId() const { return EdgeHI.GetDat().GetDstNId(); }
786  friend class TNEGraph;
787  };
788 
789 private:
790  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
791  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
792  TEdge& GetEdge(const int& EId) { return EdgeH.GetDat(EId); }
793  const TEdge& GetEdge(const int& EId) const { return EdgeH.GetDat(EId); }
794 private:
799 public:
800  TNEGraph() : CRef(), MxNId(0), MxEId(0) { }
802  explicit TNEGraph(const int& Nodes, const int& Edges) : CRef(), MxNId(0), MxEId(0) { Reserve(Nodes, Edges); }
803  TNEGraph(const TNEGraph& Graph) : MxNId(Graph.MxNId), MxEId(Graph.MxEId), NodeH(Graph.NodeH), EdgeH(Graph.EdgeH) { }
805  TNEGraph(TSIn& SIn) : MxNId(SIn), MxEId(SIn), NodeH(SIn), EdgeH(SIn) { }
807  void Save(TSOut& SOut) const { MxNId.Save(SOut); MxEId.Save(SOut); NodeH.Save(SOut); EdgeH.Save(SOut); }
809  static PNEGraph New() { return PNEGraph(new TNEGraph()); }
811 
813  static PNEGraph New(const int& Nodes, const int& Edges) { return PNEGraph(new TNEGraph(Nodes, Edges)); }
815  static PNEGraph Load(TSIn& SIn) { return PNEGraph(new TNEGraph(SIn)); }
817  bool HasFlag(const TGraphFlag& Flag) const;
818  TNEGraph& operator = (const TNEGraph& Graph) { if (this!=&Graph) {
819  MxNId=Graph.MxNId; MxEId=Graph.MxEId; NodeH=Graph.NodeH; EdgeH=Graph.EdgeH; } return *this; }
820 
822  int GetNodes() const { return NodeH.Len(); }
824 
828  int AddNode(int NId = -1);
830  int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId()); }
832 
834  void DelNode(const int& NId);
836  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
838  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
840  TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); }
842  TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); }
844  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); }
846  int GetMxNId() const { return MxNId; }
847 
849  int GetEdges() const { return EdgeH.Len(); }
851 
856  int AddEdge(const int& SrcNId, const int& DstNId, int EId = -1);
858  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI.GetId()); }
860  void DelEdge(const int& EId);
862 
866  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
868  bool IsEdge(const int& EId) const { return EdgeH.IsKey(EId); }
870  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const { int EId; return IsEdge(SrcNId, DstNId, EId, IsDir); }
872  bool IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir = true) const;
874  int GetEId(const int& SrcNId, const int& DstNId) const { int EId; return IsEdge(SrcNId, DstNId, EId)?EId:-1; }
876  TEdgeI BegEI() const { return TEdgeI(EdgeH.BegI(), this); }
878  TEdgeI EndEI() const { return TEdgeI(EdgeH.EndI(), this); }
880  TEdgeI GetEI(const int& EId) const { return TEdgeI(EdgeH.GetI(EId), this); }
882  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const { return GetEI(GetEId(SrcNId, DstNId)); }
883 
885  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
887  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
889  int GetRndEId(TRnd& Rnd=TInt::Rnd) { return EdgeH.GetKey(EdgeH.GetRndKeyId(Rnd, 0.8)); }
891  TEdgeI GetRndEI(TRnd& Rnd=TInt::Rnd) { return GetEI(GetRndEId(Rnd)); }
893  void GetNIdV(TIntV& NIdV) const;
895  void GetEIdV(TIntV& EIdV) const;
896 
898  bool Empty() const { return GetNodes()==0; }
900  void Clr() { MxNId=0; MxEId=0; NodeH.Clr(); EdgeH.Clr(); }
902  void Reserve(const int& Nodes, const int& Edges) {
903  if (Nodes>0) { NodeH.Gen(Nodes/2); } if (Edges>0) { EdgeH.Gen(Edges/2); } }
905 
910  void Defrag(const bool& OnlyNodeLinks=false);
912 
915  bool IsOk(const bool& ThrowExcept=true) const;
917  void Dump(FILE *OutF=stdout) const;
919 
923  static PNEGraph GetSmallGraph();
924  friend class TPt<TNEGraph>;
925 };
926 
927 // set flags
928 namespace TSnap {
929 template <> struct IsMultiGraph<TNEGraph> { enum { Val = 1 }; };
930 template <> struct IsDirected<TNEGraph> { enum { Val = 1 }; };
931 }
932 
933 //#//////////////////////////////////////////////
935 
936 class TBPGraph {
937 public:
938  typedef TBPGraph TNet;
940  typedef enum { bgsUndef, bgsLeft, bgsRight, bgsBoth } TNodeTy; // left or right hand side node
941 public:
942  class TNode {
943  private:
946  TNodeTy NodeTy; // remove
947  public:
948  TNode() : Id(-1), NIdV(), NodeTy(bgsUndef) { }
949  TNode(const int& NId) : Id(NId), NIdV(), NodeTy(true?bgsLeft:bgsRight) { }
950  TNode(const TNode& Node) : Id(Node.Id), NIdV(Node.NIdV), NodeTy(Node.NodeTy) { }
951  TNode(TSIn& SIn) : Id(SIn), NIdV(SIn), NodeTy(bgsUndef) { TInt Ty(SIn); NodeTy=(TNodeTy)Ty.Val; }
952  void Save(TSOut& SOut) const { Id.Save(SOut); NIdV.Save(SOut); TInt(NodeTy).Save(SOut); }
953  int GetId() const { return Id; }
954  int GetDeg() const { return NIdV.Len(); }
955  int GetInDeg() const { return GetDeg(); }
956  int GetOutDeg() const { return GetDeg(); }
957  int GetInNId(const int& NodeN) const { return GetNbrNId(NodeN); }
958  int GetOutNId(const int& NodeN) const { return GetNbrNId(NodeN); }
959  int GetNbrNId(const int& NodeN) const { return NIdV[NodeN]; }
960  bool IsNbrNId(const int& NId) const { return NIdV.SearchBin(NId)!=-1; }
961  bool IsInNId(const int& NId) const { return IsNbrNId(NId); }
962  bool IsOutNId(const int& NId) const { return IsNbrNId(NId); }
963  void PackOutNIdV() { NIdV.Pack(); }
964  void PackNIdV() { NIdV.Pack(); }
965  friend class TBPGraph;
966  };
968  class TNodeI {
969  private:
971  THashIter LeftHI, RightHI; // iterator over left and right hand-side nodes
972  private:
973  inline THashIter HI() const { return ! LeftHI.IsEnd()?LeftHI:RightHI; }
974  public:
975  TNodeI() : LeftHI(), RightHI() { }
976  TNodeI(const THashIter& LeftHIter, const THashIter& RightHIter) : LeftHI(LeftHIter), RightHI(RightHIter) { }
977  TNodeI(const TNodeI& NodeI) : LeftHI(NodeI.LeftHI), RightHI(NodeI.RightHI) { }
978  TNodeI& operator = (const TNodeI& NodeI) { LeftHI = NodeI.LeftHI; RightHI=NodeI.RightHI; return *this; }
981  if (! LeftHI.IsEnd()) {
982  LeftHI++; }
983  else if (! RightHI.IsEnd()) {
984  RightHI++; }
985  return *this; }
986  bool operator < (const TNodeI& NodeI) const { return LeftHI < NodeI.LeftHI || (LeftHI==NodeI.LeftHI && RightHI < NodeI.RightHI); }
987  bool operator == (const TNodeI& NodeI) const { return LeftHI==NodeI.LeftHI && RightHI==NodeI.RightHI; }
989  int GetId() const { return HI().GetDat().GetId(); }
991  bool IsLeft() const { return ! LeftHI.IsEnd(); }
993  bool IsRight() const { return ! IsLeft(); }
995  int GetDeg() const { return HI().GetDat().GetDeg(); }
997  int GetInDeg() const { return HI().GetDat().GetInDeg(); }
999  int GetOutDeg() const { return HI().GetDat().GetOutDeg(); }
1001 
1002  int GetInNId(const int& NodeN) const { return HI().GetDat().GetInNId(NodeN); }
1004 
1005  int GetOutNId(const int& NodeN) const { return HI().GetDat().GetOutNId(NodeN); }
1007 
1008  int GetNbrNId(const int& NodeN) const { return HI().GetDat().GetNbrNId(NodeN); }
1010  bool IsInNId(const int& NId) const { return HI().GetDat().IsInNId(NId); }
1012  bool IsOutNId(const int& NId) const { return HI().GetDat().IsOutNId(NId); }
1014  bool IsNbrNId(const int& NId) const { return HI().GetDat().IsNbrNId(NId); }
1015  friend class TBPGraph;
1016  };
1018  class TEdgeI {
1019  private:
1020  TNodeI CurNode, EndNode; // end node on the 'left'
1021  int CurEdge;
1022  public:
1023  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
1024  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
1025  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
1026  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
1028  TEdgeI& operator++ (int) { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++;
1029  while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; }
1030  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
1031  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
1033  int GetId() const { return -1; }
1035  int GetSrcNId() const { return CurNode.GetId(); }
1037  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
1039  int GetLNId() const { return GetSrcNId(); }
1041  int GetRNId() const { return GetDstNId(); }
1042  friend class TBPGraph;
1043  };
1044 private:
1046  TInt MxNId; // maximum node ID in the graph
1047  THash<TInt, TNode> LeftH; // 'left' nodes
1048  THash<TInt, TNode> RightH; // 'right' nodes
1049 private:
1050  //TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
1051  //const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
1052 public:
1053  TBPGraph() : CRef(), MxNId(0), LeftH(), RightH() { }
1055  explicit TBPGraph(const int& Nodes, const int& Edges) : MxNId(0) { }
1056  TBPGraph(const TBPGraph& BPGraph) : MxNId(BPGraph.MxNId), LeftH(BPGraph.LeftH), RightH(BPGraph.RightH) { }
1058  TBPGraph(TSIn& SIn) : MxNId(SIn), LeftH(SIn), RightH(SIn) { }
1060  void Save(TSOut& SOut) const { MxNId.Save(SOut); LeftH.Save(SOut); RightH.Save(SOut); }
1062  static PBPGraph New() { return new TBPGraph(); }
1064 
1065  static PBPGraph New(const int& Nodes, const int& Edges) { return new TBPGraph(Nodes, Edges); }
1067  static PBPGraph Load(TSIn& SIn) { return PBPGraph(new TBPGraph(SIn)); }
1069  bool HasFlag(const TGraphFlag& Flag) const;
1070  TBPGraph& operator = (const TBPGraph& BPGraph) {
1071  if (this!=&BPGraph) { MxNId=BPGraph.MxNId; LeftH=BPGraph.LeftH; RightH=BPGraph.RightH; } return *this; }
1072 
1074  int GetNodes() const { return GetLNodes() + GetRNodes(); }
1076  int GetLNodes() const { return LeftH.Len(); }
1078  int GetRNodes() const { return RightH.Len(); }
1080 
1081  int AddNode(int NId = -1, const bool& LeftNode=true);
1083  int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId(), NodeI.IsLeft()); }
1085 
1086  void DelNode(const int& NId);
1088  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
1090  bool IsNode(const int& NId) const { return IsLNode(NId) || IsRNode(NId); }
1092  bool IsLNode(const int& NId) const { return LeftH.IsKey(NId); }
1094  bool IsRNode(const int& NId) const { return RightH.IsKey(NId); }
1096  int GetMxNId() const { return MxNId; }
1097 
1099  TNodeI BegNI() const { return TNodeI(LeftH.BegI(), RightH.BegI()); }
1101  TNodeI EndNI() const { return TNodeI(LeftH.EndI(), RightH.EndI()); }
1103  TNodeI GetNI(const int& NId) const { return IsLNode(NId) ? TNodeI(LeftH.GetI(NId), RightH.EndI()) : TNodeI(LeftH.EndI(), RightH.GetI(NId)); }
1105  TNodeI BegLNI() const { return TNodeI(LeftH.BegI(), RightH.EndI()); }
1107  TNodeI EndLNI() const { return EndNI(); }
1109  TNodeI BegRNI() const { return TNodeI(LeftH.EndI(), RightH.BegI()); }
1111  TNodeI EndRNI() const { return EndNI(); }
1112 
1114  int GetEdges() const;
1116 
1117  int AddEdge(const int& LeftNId, const int& RightNId);
1119  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
1121 
1122  void DelEdge(const int& LeftNId, const int& RightNId);
1124  bool IsEdge(const int& LeftNId, const int& RightNId) const;
1126  TEdgeI BegEI() const { TNodeI NI=BegLNI(); while (NI<EndLNI() && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { NI++; } return TEdgeI(NI, EndLNI()); }
1128  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
1130  TEdgeI GetEI(const int& EId) const;
1132 
1133  TEdgeI GetEI(const int& LeftNId, const int& RightNId) const;
1134 
1136  int GetRndNId(TRnd& Rnd=TInt::Rnd);
1138  int GetRndLNId(TRnd& Rnd=TInt::Rnd);
1140  int GetRndRNId(TRnd& Rnd=TInt::Rnd);
1142  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
1144  void GetNIdV(TIntV& NIdV) const;
1146  void GetLNIdV(TIntV& NIdV) const;
1148  void GetRNIdV(TIntV& NIdV) const;
1149 
1151  bool Empty() const { return GetNodes()==0; }
1153  void Clr() { MxNId=0; LeftH.Clr(); RightH.Clr(); }
1155  void Reserve(const int& Nodes, const int& Edges);
1157 
1158  void Defrag(const bool& OnlyNodeLinks=false);
1160 
1161  bool IsOk(const bool& ThrowExcept=true) const;
1163  void Dump(FILE *OutF=stdout) const;
1165 
1166  static PBPGraph GetSmallGraph();
1167 
1168  friend class TPt<TBPGraph>;
1169 };
1170 
1171 // set flags
1172 namespace TSnap {
1173 template <> struct IsBipart<TBPGraph> { enum { Val = 1 }; };
1174 }
1175 
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graph.cpp:232
Definition: bd.h:440
static PBPGraph GetSmallGraph()
Returns a small graph on 2 'left', 3 'right' nodes and 4 edges.
Definition: graph.cpp:868
int AddEdge(const TEdgeI &EdgeI)
Adds an edge between EdgeI.GetLNId() and EdgeI.GetRNId() to the graph.
Definition: graph.h:1119
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
void LoadGraphShM(TShMIn &ShMIn)
Definition: graph.h:155
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:420
bool operator<(const TNodeI &NodeI) const
Definition: graph.h:986
Main namespace for all the Snap global entities.
Definition: alg.h:1
TBPGraph(const TBPGraph &BPGraph)
!! Reserve(Nodes, Edges); }
Definition: graph.h:1056
int GetDeg() const
Definition: graph.h:954
static PNGraph LoadShM(TShMIn &ShMIn)
Static constructor that loads the graph from a shared memory stream and returns pointer to it...
Definition: graph.h:492
int GetId() const
Gets edge ID. Always returns -1 since only edges in multigraphs have explicit IDs.
Definition: graph.h:1033
TPt< TBPGraph > PNet
Definition: graph.h:939
TUNGraph(const TUNGraph &Graph)
Definition: graph.h:165
THashIter NodeHI
Definition: graph.h:71
int AddNode(const TNodeI &NodeId)
Adds a node of ID NodeI.GetId() to the graph.
Definition: graph.h:517
int GetOutDeg() const
Definition: graph.h:364
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a biparite graph of Nodes nodes and Edges edges.
Definition: graph.cpp:790
int GetSrcNId() const
Definition: graph.h:701
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:376
static PUNGraph 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: graph.h:176
TNodeI CurNode
Definition: graph.h:432
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.cpp:468
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:497
int AddEdge(const int &SrcNId, const int &DstNId, int EId=-1)
Adds an edge with ID EId between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:516
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:586
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:280
void GetRNIdV(TIntV &NIdV) const
Gets a vector IDs of all 'right' nodes in the bipartite graph.
Definition: graph.cpp:784
TNode(const int &NId)
Definition: graph.h:43
bool IsOutNId(const int &NId) const
Definition: graph.h:60
bool operator==(const TEdgeI &EdgeI) const
Definition: graph.h:133
TNodeI & operator--(int)
Decrement iterator.
Definition: graph.h:81
TEdgeI & operator++(int)
Increment iterator.
Definition: graph.h:1028
TNodeI & operator=(const TNodeI &NodeI)
Definition: graph.h:978
static PBPGraph 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: graph.h:1065
TNode(const TNode &Node)
Definition: graph.h:950
bool Empty() const
Tests whether the graph is empty (has zero nodes).
Definition: graph.h:898
bool operator==(const TNodeI &NodeI) const
Definition: graph.h:987
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:1103
int GetInDeg() const
Returns in-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:997
static PUNGraph GetSmallGraph()
Returns a small graph on 5 nodes and 5 edges.
Definition: graph.cpp:221
Definition: dt.h:11
TNEGraph & operator=(const TNEGraph &Graph)
Definition: graph.h:818
THash< TInt, TNode >::TIter THashIter
Definition: graph.h:70
TNode & GetNode(const int &NId)
Definition: graph.h:153
bool operator==(const TEdgeI &EdgeI) const
Definition: graph.h:779
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: graph.h:117
int GetNbrEId(const int &EdgeN) const
Definition: graph.h:686
void LoadShM(TShMIn &ShMIn)
Definition: graph.h:46
TEdge(const int &EId, const int &SourceNId, const int &DestNId)
Definition: graph.h:696
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.cpp:754
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:1090
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:437
TNodeTy NodeTy
Definition: graph.h:946
int Val
Definition: dt.h:1139
const TNEGraph * Graph
Definition: graph.h:770
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
void Save(TSOut &SOut) const
Definition: dt.h:1153
int AddEdge(const int &SrcNId, const int &DstNId, const int &EId)
Adds an edge between node IDs SrcNId and DstNId to the graph, ignores EId (for compatibility with TNE...
Definition: graph.h:569
void ReserveNIdInDeg(const int &NId, const int &InDeg)
Reserves memory for node ID NId having InDeg in-edges.
Definition: graph.h:616
THashIter HI() const
Definition: graph.h:973
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:876
TNEGraph(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:802
int AddNode(const TNodeI &NodeI)
Adds a node of ID NodeI.GetId() to the graph.
Definition: graph.h:1083
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:153
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:596
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:730
int GetDstNId() const
Returns the destination of the edge. Since the graph is undirected, this is the node with a greater I...
Definition: graph.h:139
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:243
void PackNIdV()
Definition: graph.h:62
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.h:422
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:1092
TNEGraph(TSIn &SIn)
Constructor for loading the graph from a (binary) stream SIn.
Definition: graph.h:805
TUNGraph(TSIn &SIn)
Constructor that loads the graph from a (binary) stream SIn.
Definition: graph.h:167
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: graph.h:438
Tests (at compile time) if the graph is directed.
Definition: gbase.h:28
void LoadShM(TShMIn &ShMIn)
Definition: graph.h:374
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:1096
int GetNbrNId(const int &NodeN) const
Definition: graph.h:959
TIter BegI() const
Definition: hash.h:213
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:968
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
int GetDstNId() const
Gets destination ('right' side) of an edge. Since the graph is undirected this is the node with great...
Definition: graph.h:1037
THash< TInt, TNode > NodeH
Definition: graph.h:455
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
TNodeTy
Definition: graph.h:940
int AddEdge(const TEdgeI &EdgeI)
Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph.
Definition: graph.h:582
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool IsInEId(const int &EId) const
Definition: graph.h:687
int GetId() const
Definition: graph.h:680
TPt< TNEGraph > PNet
Definition: graph.h:668
TNodeI & operator=(const TNodeI &NodeI)
Definition: graph.h:76
bool operator<(const TEdgeI &EdgeI) const
Definition: graph.h:778
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
int GetId() const
Gets edge ID.
Definition: graph.h:781
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:1101
bool operator==(const TEdgeI &EdgeI) const
Definition: graph.h:1031
int AddEdgeUnchecked(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:330
void Save(TSOut &SOut) const
Definition: hash.h:183
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:1099
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: graph.h:870
TNodeI & operator--(int)
Decrement iterator.
Definition: graph.h:719
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:594
int GetInDeg() const
Definition: graph.h:682
TInt NEdges
Definition: graph.h:144
TEdgeI & operator++(int)
Increment iterator.
Definition: graph.h:440
TInt SrcNId
Definition: graph.h:693
void Save(TSOut &SOut) const
Definition: graph.h:699
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:391
int GetOutEId(const int &EdgeN) const
Definition: graph.h:685
int AddNode(int NId=-1, const bool &LeftNode=true)
Adds a node of ID NId to the graph.
Definition: graph.cpp:671
void LoadGraphShM(TShMIn &ShMIn)
Definition: graph.h:465
void PackOutNIdV()
Definition: graph.h:61
Directed multigraph.
Definition: graph.h:665
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:878
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:1128
THashIter NodeHI
Definition: graph.h:386
int GetInDeg() const
Definition: graph.h:53
void PackOutNIdV()
Definition: graph.h:371
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TCRef CRef
Definition: graph.h:795
Definition: fl.h:384
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:207
static PNEGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:815
TNGraph()
Definition: graph.h:472
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:766
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: graph.h:807
TNode(const int &NId)
Definition: graph.h:357
int GetSrcNId() const
Returns the source of the edge. Since the graph is undirected, this is the node with a smaller ID of ...
Definition: graph.h:137
bool IsEdge(const int &EId) const
Tests whether an edge EId exists in the graph (for compatibility with TNEANet), always returns false...
Definition: graph.h:276
TNodeI & operator--(int)
Decrement iterator.
Definition: graph.h:395
TCRef CRef
Definition: graph.h:1045
TNodeI EndNode
Definition: graph.h:123
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: graph.h:170
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: graph.h:426
const TNode & GetNode(const int &NId) const
Definition: graph.h:154
TIter EndI() const
Definition: hash.h:218
TNEGraph TNet
Definition: graph.h:667
THashIter NodeHI
Definition: graph.h:709
void SortNodeAdjV()
Sorts the adjacency lists of each node.
Definition: graph.h:300
static TRnd Rnd
Definition: dt.h:1146
int GetId() const
Definition: graph.h:51
bool IsInNId(const int &NId) const
Definition: graph.h:59
int GetRndLNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'left' node in the graph.
Definition: graph.cpp:762
TNodeI & operator++(int)
Increment iterator.
Definition: graph.h:717
TBPGraph(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a graph of Nodes (LeftNodes+RightNodes) nodes and Edges e...
Definition: graph.h:1055
bool IsNbrEId(const int &EId) const
Tests whether the edge with ID EId is an in or out-edge of current node.
Definition: graph.h:762
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:840
int GetId() const
Returns edge ID. Always returns -1 since only edges in multigraphs have explicit IDs.
Definition: graph.h:445
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: graph.h:836
THashIter EdgeHI
Definition: graph.h:769
void LoadShM(TShMIn &ShMIn)
Load THash from shared memory file. Copying/Deleting Keys is illegal.
Definition: hash.h:157
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.h:1010
TNodeI(const THashIter &NodeHIter, const TNEGraph *GraphPt)
Definition: graph.h:713
THash< TInt, TNode > NodeH
Definition: graph.h:797
int GetInNId(const int &EdgeN) const
Returns ID of EdgeN-th in-node (the node pointing to the current node).
Definition: graph.h:734
TNGraph(TSIn &SIn)
Constructor that loads the graph from a (binary) stream SIn.
Definition: graph.h:477
TNodeI EndNode
Definition: graph.h:432
int GetInNId(const int &NodeN) const
Definition: graph.h:957
int GetOutDeg() const
Definition: graph.h:683
TNode & GetNode(const int &NId)
Definition: graph.h:463
int AddEdge(const TEdgeI &EdgeI)
Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
Definition: graph.h:858
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:954
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:289
TEdgeI & operator++(int)
Increment iterator.
Definition: graph.h:777
int GetId() const
Returns ID of the current node.
Definition: graph.h:989
int GetOutNId(const int &NodeN) const
Definition: graph.h:958
int GetInDeg() const
Definition: graph.h:363
int GetDstNId() const
Gets destination of an edge.
Definition: graph.h:785
THash< TInt, TEdge > EdgeH
Definition: graph.h:798
int GetDstNId() const
Definition: graph.h:702
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:1076
TEdgeI(const TEdgeI &EdgeI)
Definition: graph.h:128
bool operator<(const TEdgeI &EdgeI) const
Definition: graph.h:132
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: graph.h:1024
static PBPGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:1067
TCRef CRef
Definition: graph.h:143
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:294
int GetOutEId(const int &EdgeN) const
Returns ID of EdgeN-th out-edge.
Definition: graph.h:754
void SortNodeAdjV()
Sorts the adjacency lists of each node.
Definition: graph.h:620
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:1008
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:90
void Clr()
Deletes all nodes and edges from the bipartite graph.
Definition: graph.h:1153
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:842
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
TNode(const int &NId)
Definition: graph.h:949
int GetInEId(const int &EdgeN) const
Definition: graph.h:684
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:844
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:999
int GetId() const
Definition: graph.h:361
int GetNbrNId(const int &EdgeN) const
Returns ID of EdgeN-th neighboring node.
Definition: graph.h:742
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:564
TEdgeI GetEI(const int &SrcNId, const int &DstNId) const
Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
Definition: graph.h:882
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:822
static PUNGraph LoadShM(TShMIn &ShMIn)
Static constructor that loads the graph from shared memory.
Definition: graph.h:182
TNodeI & operator++(int)
Increment iterator.
Definition: graph.h:79
THashIter LeftHI
Definition: graph.h:971
void SortNIdV()
Sorts the adjacency lists of the current node.
Definition: graph.h:408
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:94
bool Empty() const
Tests whether the bipartite graph is empty (has zero nodes).
Definition: graph.h:1151
void PackNIdV()
Definition: graph.h:372
TPt< TNEGraph > PNEGraph
Pointer to a directed multigraph (TNEGraph)
Definition: graph.h:21
TEdge & GetEdge(const int &EId)
Definition: graph.h:792
Undirected graph.
Definition: graph.h:32
int GetLNId() const
Gets the ID of the node on the 'left' side of the edge.
Definition: graph.h:1039
THash< TInt, TNode >::TIter THashIter
Definition: graph.h:385
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.cpp:477
TNodeI EndRNI() const
Returns an iterator referring to the past-the-end 'right' node in the graph.
Definition: graph.h:1111
TNodeI & operator++(int)
Increment iterator.
Definition: graph.h:393
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
bool IsOutNId(const int &NId) const
Definition: graph.h:962
void Gen(const int &ExpectVals)
Definition: hash.h:222
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:698
TInt MxNId
Definition: graph.h:144
TNodeI(const THashIter &LeftHIter, const THashIter &RightHIter)
Definition: graph.h:976
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
static PNEGraph GetSmallGraph()
Returns a small multigraph on 5 nodes and 6 edges.
Definition: graph.cpp:660
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:1074
bool IsInNId(const int &NId) const
Definition: graph.h:961
static PNGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:487
Definition: gsvd.h:5
TEdgeI(const THashIter &EdgeHIter, const TNEGraph *GraphPt)
Definition: graph.h:773
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: graph.h:233
void DelEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true)
Deletes an edge from node IDs SrcNId to DstNId from the graph.
Definition: graph.cpp:345
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 graph.
Definition: graph.cpp:363
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:302
TNGraph(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:474
bool Empty() const
Tests whether the graph is empty (has zero nodes).
Definition: graph.h:296
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:603
TNodeI BegLNI() const
Returns an iterator referring to the first 'left' node in the graph.
Definition: graph.h:1105
int GetInEId(const int &EdgeN) const
Returns ID of EdgeN-th in-edge.
Definition: graph.h:752
TNode(TSIn &SIn)
Definition: graph.h:678
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.h:424
TNode(TSIn &SIn)
Definition: graph.h:359
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:1078
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graph.cpp:464
THash< TInt, TNode >::TIter THashIter
Definition: graph.h:708
Tests (at compile time) if the graph is a multigraph with multiple edges between the same nodes...
Definition: gbase.h:30
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
TNodeI(const TNodeI &NodeI)
Definition: graph.h:75
TNode(const TNode &Node)
Definition: graph.h:677
int GetOutNId(const int &EdgeN) const
Returns ID of EdgeN-th out-node (the node the current node points to).
Definition: graph.h:738
TInt DstNId
Definition: graph.h:693
void operator()(TNode *Node, TShMIn &ShMIn)
Definition: graph.h:150
bool IsEdge(const int &LeftNId, const int &RightNId) const
Tests whether an edge between node IDs LeftNId and RightNId exists in the graph.
Definition: graph.cpp:735
bool operator<(const TEdgeI &EdgeI) const
Definition: graph.h:1030
TIntV NIdV
Definition: graph.h:40
int AddEdge(const TEdgeI &EdgeI)
Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
Definition: graph.h:267
TInt MxNId
Definition: graph.h:1046
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:278
void PackOutNIdV()
Definition: graph.h:963
void GetLNIdV(TIntV &NIdV) const
Gets a vector IDs of all 'left' nodes in the bipartite graph.
Definition: graph.cpp:778
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: graph.h:436
int AddEdge(const int &SrcNId, const int &DstNId, const int &EId)
Adds an edge between node IDs SrcNId and DstNId to the graph, ignores EId (for compatibility with TNE...
Definition: graph.h:254
TPt< TNGraph > PNGraph
Pointer to a directed graph (TNGraph)
Definition: graph.h:16
TNodeI CurNode
Definition: graph.h:123
bool operator<(const TNodeI &NodeI) const
Definition: graph.h:721
TBPGraph TNet
Definition: graph.h:938
int GetOutNId(const int &NodeN) const
Definition: graph.h:366
TBPGraph & operator=(const TBPGraph &BPGraph)
Definition: graph.h:1070
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:486
int AddNode(const TNodeI &NodeId)
Adds a node of ID NodeI.GetId() to the graph.
Definition: graph.h:830
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
TNodeI BegRNI() const
Returns an iterator referring to the first 'right' node in the graph.
Definition: graph.h:1109
int GetOutNId(const int &NodeN) const
Definition: graph.h:56
int AddNodeUnchecked(int NId=-1)
Adds a node of ID NId to the network, noop if the node already exists.
Definition: graph.cpp:20
TIntV OutEIdV
Definition: graph.h:673
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:639
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the graph.
Definition: graph.h:291
void Save(TSOut &SOut) const
Definition: graph.h:952
void Save(TSOut &SOut) const
Definition: graph.h:50
TUNGraph TNet
Definition: graph.h:34
TNodeI EndLNI() const
Returns an iterator referring to the past-the-end 'left' node in the graph.
Definition: graph.h:1107
void SortNIdV()
Definition: graph.h:63
int GetRNId() const
Gets the ID of the node on the 'right' side of the edge.
Definition: graph.h:1041
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the graph.
Definition: graph.h:605
TNodeI & operator=(const TNodeI &NodeI)
Definition: graph.h:391
bool operator==(const TNodeI &NodeI) const
Definition: graph.h:722
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:402
bool operator==(const TNodeI &NodeI) const
Definition: graph.h:85
Definition: fl.h:128
TNGraph(const TNGraph &Graph)
Definition: graph.h:475
THash< TInt, TNode >::TIter THashIter
Definition: graph.h:970
TIntV NIdV
Definition: graph.h:945
int GetDeg() const
Definition: graph.h:681
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: graph.h:1014
void operator()(TNode *Node, TShMIn &ShMIn)
Definition: graph.h:460
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:382
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
bool operator<(const TNodeI &NodeI) const
Definition: graph.h:397
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:995
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:612
TUNGraph()
Definition: graph.h:162
Definition: dt.h:1137
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:556
bool IsNbrNId(const int &NId) const
Definition: graph.h:960
TNEGraph(const TNEGraph &Graph)
Definition: graph.h:803
TNode & GetNode(const int &NId)
Definition: graph.h:790
static PUNGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:178
static PNEGraph New()
Static constructor that returns a pointer to the graph. Call: PNEGraph Graph = TNEGraph::New().
Definition: graph.h:809
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: graph.h:479
void Save(TSOut &SOut) const
Definition: graph.h:679
int AddEdge(const int &LeftNId, const int &RightNId)
Adds an edge between a node LeftNId on the left and a node RightNId on the right side of the bipartit...
Definition: graph.cpp:705
bool IsEdge(const int &EId) const
Tests whether an edge EId exists in the graph (for compatibility with TNEANet), always returns false...
Definition: graph.h:592
void DelEdge(const int &LeftNId, const int &RightNId)
Deletes an edge between a node LeftNId on the left and a node RightNId on the right side of the bipar...
Definition: graph.cpp:719
THashIter RightHI
Definition: graph.h:971
int GetSrcNId() const
Gets the source ('left' side) of an edge. Since the graph is undirected this is the node with smaller...
Definition: graph.h:1035
TEdge(const TEdge &Edge)
Definition: graph.h:697
Directed graph.
Definition: graph.h:346
bool IsNbrNId(const int &NId) const
Definition: graph.h:58
void LoadShM(TShMIn &ShMIn)
Constructs the vector from a shared memory input.
Definition: ds.h:932
int GetNbrNId(const int &NodeN) const
Definition: graph.h:57
TEdgeI GetEI(const int &EId) const
Returns an iterator referring to edge with edge ID EId.
Definition: graph.h:880
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:682
TNode(const TNode &Node)
Definition: graph.h:358
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: graph.h:1026
bool IsEdge(const int &EId) const
Tests whether an edge with edge ID EId exists in the graph.
Definition: graph.h:868
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
int GetId() const
Returns ID of the current node.
Definition: graph.h:400
TBPGraph()
Definition: graph.h:1053
static PNGraph GetSmallGraph()
Returns a small graph on 5 nodes and 6 edges.
Definition: graph.cpp:454
TNode(const int &NId)
Definition: graph.h:676
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:106
int GetRndRNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'right' node in the graph.
Definition: graph.cpp:766
const TNode & GetNode(const int &NId) const
Definition: graph.h:791
int GetId() const
Returns edge ID. Always returns -1 since only edges in multigraphs have explicit IDs.
Definition: graph.h:135
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:902
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
Bipartite graph.
Definition: graph.h:936
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: graph.h:874
int GetSrcNId() const
Gets the source of an edge.
Definition: graph.h:783
int AddEdge2(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph. If nodes do not exists, create them.
Definition: graph.cpp:112
TNodeI & operator=(const TNodeI &NodeI)
Definition: graph.h:715
THash< TInt, TNode > NodeH
Definition: graph.h:145
TEdge(TSIn &SIn)
Definition: graph.h:698
TNode(const TNode &Node)
Definition: graph.h:44
bool IsOutEId(const int &EId) const
Definition: graph.h:688
static PNGraph 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: graph.h:485
void GetEIdV(TIntV &EIdV) const
Gets a vector IDs of all edges in the graph.
Definition: graph.cpp:570
TNode(TSIn &SIn)
Definition: graph.h:951
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
int GetId() const
Definition: graph.h:953
int GetRndEId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random edge in the graph.
Definition: graph.h:889
enum TGraphFlag_ TGraphFlag
Graph Flags, used for quick testing of graph types.
bool IsRNode(const int &NId) const
Tests whether ID NId is a 'right' side node.
Definition: graph.h:1094
bool IsRight() const
Tests whether the node is right hand side node.
Definition: graph.h:993
TCRef CRef
Definition: graph.h:453
THash< TInt, TNode > RightH
Definition: graph.h:1048
Definition: hash.h:97
TNodeI(const THashIter &NodeHIter)
Definition: graph.h:389
static PNEGraph 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: graph.h:813
TPt< TNGraph > PNet
Definition: graph.h:349
int GetNbrEId(const int &EdgeN) const
Returns ID of EdgeN-th in or out-edge.
Definition: graph.h:756
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.h:849
int GetInDeg() const
Returns in-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:92
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:160
const TEdge & GetEdge(const int &EId) const
Definition: graph.h:793
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
int GetOutDeg() const
Definition: graph.h:956
const TNEGraph * Graph
Definition: graph.h:710
TIntV InNIdV
Definition: graph.h:354
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.h:1012
TPt< TUNGraph > PNet
Definition: graph.h:35
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:885
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:614
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:1062
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:111
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
THash< TInt, TNode > LeftH
Definition: graph.h:1047
TNode(TSIn &SIn)
Definition: graph.h:45
TInt MxNId
Definition: graph.h:796
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
TInt MxNId
Definition: graph.h:454
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:1005
TPt< TBPGraph > PBPGraph
Pointer to a bipartitegraph graph (TBPGraph)
Definition: graph.h:11
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graph.cpp:3
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the graph.
Definition: graph.h:887
int GetRndKeyId(TRnd &Rnd) const
Get an index of a random element. If the hash table has many deleted keys, this may take a long time...
Definition: hash.h:444
bool operator==(const TNodeI &NodeI) const
Definition: graph.h:398
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:900
TNodeI CurNode
Definition: graph.h:1020
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the bipartite graph.
Definition: graph.cpp:770
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:298
TNodeI & operator++(int)
Increment iterator.
Definition: graph.h:980
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:170
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
TEdgeI GetRndEI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random edge in the graph.
Definition: graph.h:891
TIntV OutNIdV
Definition: graph.h:354
int GetOutDeg() const
Definition: graph.h:54
const TNode & GetNode(const int &NId) const
Definition: graph.h:464
int AddNodeUnchecked(int NId=-1)
Adds a node of ID NId to the network, noop if the node already exists.
Definition: graph.cpp:247
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
void SortNIdV()
Sorts the adjacency lists of the current node.
Definition: graph.h:96
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:577
void SortNIdV()
Definition: graph.h:373
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:1126
TNodeI EndNode
Definition: graph.h:1020
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:404
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: graph.h:544
void Dump(FILE *OutF=stdout) const
Print the biparite graph in a human readable form to an output stream OutF.
Definition: graph.cpp:845
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: graph.h:1088
int GetSrcNId() const
Returns the source node of the edge.
Definition: graph.h:447
int GetId() const
Returns ID of the current node.
Definition: graph.h:724
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the biparite graph.
Definition: graph.cpp:794
int GetId() const
Returns ID of the current node.
Definition: graph.h:88
bool IsEdge(const int &SrcNId, const int &DstNId) const
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition: graph.cpp:137
TEdgeI(const TEdgeI &EdgeI)
Definition: graph.h:1025
bool IsKey(const TKey &Key) const
Definition: hash.h:258
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:412
void PackNIdV()
Definition: graph.h:964
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.h:115
void DelEdge(const int &EId)
Deletes an edge with edge ID EId from the graph.
Definition: graph.cpp:527
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
int GetInNId(const int &NodeN) const
Definition: graph.h:55
bool IsOutEId(const int &EId) const
Tests whether the edge with ID EId is an out-edge of current node.
Definition: graph.h:760
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
int GetInNId(const int &NodeN) const
Definition: graph.h:365
int GetDeg() const
Definition: graph.h:362
int GetDeg() const
Definition: graph.h:52
bool operator<(const TEdgeI &EdgeI) const
Definition: graph.h:442
void ReserveNIdDeg(const int &NId, const int &Deg)
Reserves memory for node ID NId having Deg edges.
Definition: graph.h:304
bool IsOutNId(const int &NId) const
Definition: graph.h:369
int GetNbrNId(const int &NodeN) const
Definition: graph.h:367
int Len() const
Definition: hash.h:228
TNodeI(const TNodeI &NodeI)
Definition: graph.h:977
TInt MxEId
Definition: graph.h:796
int AddNode(const TNodeI &NodeI)
Adds a node of ID NodeI.GetId() to the graph.
Definition: graph.h:206
TNodeI(const THashIter &NodeHIter)
Definition: graph.h:74
TNodeI(const TNodeI &NodeI)
Definition: graph.h:714
bool IsInEId(const int &EId) const
Tests whether the edge with ID EId is an in-edge of current node.
Definition: graph.h:758
bool IsNbrNId(const int &NId) const
Definition: graph.h:370
bool operator==(const TEdgeI &EdgeI) const
Definition: graph.h:443
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the graph.
Definition: graph.h:1142
bool IsOk(const bool &ThrowExcept=true) const
Checks the bipartite graph data structure for internal consistency.
Definition: graph.cpp:803
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:67
Tests (at compile time) if the graph is a bipartite graph type.
Definition: gbase.h:38
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: graph.h:775
TEdgeI(const TEdgeI &EdgeI)
Definition: graph.h:774
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:1018
void Save(TSOut &SOut) const
Definition: graph.h:360
TNGraph & operator=(const TNGraph &Graph)
Definition: graph.h:499
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:706
int AddEdge2(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph. If nodes do not exist, create them.
Definition: graph.cpp:336
int GetDstNId() const
Returns the destination node of the edge.
Definition: graph.h:449
bool IsInNId(const int &NId) const
Definition: graph.h:368
bool operator<(const TNodeI &NodeI) const
Definition: graph.h:84
int GetInDeg() const
Definition: graph.h:955
TUNGraph & operator=(const TUNGraph &Graph)
Definition: graph.h:188
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:726
bool Empty() const
Tests whether the graph is empty (has zero nodes).
Definition: graph.h:610
TEdgeI & operator++(int)
Increment iterator.
Definition: graph.h:131
THash< TInt, TEdge >::TIter THashIter
Definition: graph.h:768
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:728
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: graph.h:127
bool IsLeft() const
Tests whether the node is left hand side node.
Definition: graph.h:991
TUNGraph(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:164
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:838
TEdgeI(const TEdgeI &EdgeI)
Definition: graph.h:437
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: graph.h:129
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:101
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: graph.h:1060
TBPGraph(TSIn &SIn)
Constructor for loading the graph from a (binary) stream SIn.
Definition: graph.h:1058
TNodeI(const TNodeI &NodeI)
Definition: graph.h:390
void ReserveNIdOutDeg(const int &NId, const int &OutDeg)
Reserves memory for node ID NId having OutDeg out-edges.
Definition: graph.h:618
TNEGraph()
Definition: graph.h:800
int AddEdgeUnchecked(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:103
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: graph.h:749
TPt< TUNGraph > PUNGraph
Pointer to an undirected graph (TUNGraph)
Definition: graph.h:5
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:846
TIter GetI(const TKey &Key) const
Definition: hash.h:220
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:1002
TIntV InEIdV
Definition: graph.h:673
int GetId() const
Definition: graph.h:700
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.h:113
TNGraph TNet
Definition: graph.h:348