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
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 Save(TSOut& SOut) const { Id.Save(SOut); NIdV.Save(SOut); }
47  int GetId() const { return Id; }
48  int GetDeg() const { return NIdV.Len(); }
49  int GetInDeg() const { return GetDeg(); }
50  int GetOutDeg() const { return GetDeg(); }
51  int GetInNId(const int& NodeN) const { return GetNbrNId(NodeN); }
52  int GetOutNId(const int& NodeN) const { return GetNbrNId(NodeN); }
53  int GetNbrNId(const int& NodeN) const { return NIdV[NodeN]; }
54  bool IsNbrNId(const int& NId) const { return NIdV.SearchBin(NId)!=-1; }
55  bool IsInNId(const int& NId) const { return IsNbrNId(NId); }
56  bool IsOutNId(const int& NId) const { return IsNbrNId(NId); }
57  void PackOutNIdV() { NIdV.Pack(); }
58  void PackNIdV() { NIdV.Pack(); }
59  friend class TUNGraph;
60  friend class TUNGraphMtx;
61  };
63  class TNodeI {
64  private:
67  public:
68  TNodeI() : NodeHI() { }
69  TNodeI(const THashIter& NodeHIter) : NodeHI(NodeHIter) { }
70  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI) { }
71  TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; return *this; }
72 
74  TNodeI& operator++ (int) { NodeHI++; return *this; }
76  TNodeI& operator-- (int) { NodeHI--; return *this; }
77 
78 
79  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
80  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
81 
83  int GetId() const { return NodeHI.GetDat().GetId(); }
85  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
87  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
89  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
91 
94  int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }
96 
99  int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }
101 
104  int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
106  bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
108  bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
110  bool IsNbrNId(const int& NId) const { return NodeHI.GetDat().IsNbrNId(NId); }
111  friend class TUNGraph;
112  };
114  class TEdgeI {
115  private:
117  int CurEdge;
118  public:
119  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
120  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
121  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
122  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
124  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; }
125  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
126  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
128  int GetId() const { return -1; }
130  int GetSrcNId() const { return CurNode.GetId(); }
132  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
133  friend class TUNGraph;
134  };
135 private:
139 private:
140  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
141  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
142 public:
143  TUNGraph() : CRef(), MxNId(0), NEdges(0), NodeH() { }
145  explicit TUNGraph(const int& Nodes, const int& Edges) : MxNId(0), NEdges(0) { Reserve(Nodes, Edges); }
146  TUNGraph(const TUNGraph& Graph) : MxNId(Graph.MxNId), NEdges(Graph.NEdges), NodeH(Graph.NodeH) { }
148  TUNGraph(TSIn& SIn) : MxNId(SIn), NEdges(SIn), NodeH(SIn) { }
150  void Save(TSOut& SOut) const { MxNId.Save(SOut); NEdges.Save(SOut); NodeH.Save(SOut); }
152  static PUNGraph New() { return new TUNGraph(); }
154 
156  static PUNGraph New(const int& Nodes, const int& Edges) { return new TUNGraph(Nodes, Edges); }
158  static PUNGraph Load(TSIn& SIn) { return PUNGraph(new TUNGraph(SIn)); }
160  bool HasFlag(const TGraphFlag& Flag) const;
161  TUNGraph& operator = (const TUNGraph& Graph) {
162  if (this!=&Graph) { MxNId=Graph.MxNId; NEdges=Graph.NEdges; NodeH=Graph.NodeH; } return *this; }
163 
165  int GetNodes() const { return NodeH.Len(); }
167 
171  int AddNode(int NId = -1);
173  int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId()); }
175 
184  int AddNode(const int& NId, const TIntV& NbrNIdV);
186 
194  int AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& NIdVId);
196 
198  void DelNode(const int& NId);
200  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
202  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
204  TNodeI BegNI() const { return TNodeI(NodeH.BegI()); }
206  TNodeI EndNI() const { return TNodeI(NodeH.EndI()); }
208  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId)); }
210  int GetMxNId() const { return MxNId; }
211 
213  int GetEdges() const;
215 
219  int AddEdge(const int& SrcNId, const int& DstNId);
221  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
223 
226  void DelEdge(const int& SrcNId, const int& DstNId);
228  bool IsEdge(const int& SrcNId, const int& DstNId) const;
230  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; }
232  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
234  TEdgeI GetEI(const int& EId) const;
236 
238  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;
239 
241  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
243  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
245  void GetNIdV(TIntV& NIdV) const;
246 
248  bool Empty() const { return GetNodes()==0; }
250  void Clr() { MxNId=0; NEdges=0; NodeH.Clr(); }
252  void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) NodeH.Gen(Nodes/2); }
254  void ReserveNIdDeg(const int& NId, const int& Deg) { GetNode(NId).NIdV.Reserve(Deg); }
256 
260  void Defrag(const bool& OnlyNodeLinks=false);
262 
264  bool IsOk(const bool& ThrowExcept=true) const;
266  void Dump(FILE *OutF=stdout) const;
268 
274  static PUNGraph GetSmallGraph();
275 
276  friend class TUNGraphMtx;
277  friend class TPt<TUNGraph>;
278 };
279 
280 //#//////////////////////////////////////////////
282 
296 class TNGraph {
297 public:
298  typedef TNGraph TNet;
300 public:
301  class TNode {
302  private:
305  public:
306  TNode() : Id(-1), InNIdV(), OutNIdV() { }
307  TNode(const int& NId) : Id(NId), InNIdV(), OutNIdV() { }
308  TNode(const TNode& Node) : Id(Node.Id), InNIdV(Node.InNIdV), OutNIdV(Node.OutNIdV) { }
309  TNode(TSIn& SIn) : Id(SIn), InNIdV(SIn), OutNIdV(SIn) { }
310  void Save(TSOut& SOut) const { Id.Save(SOut); InNIdV.Save(SOut); OutNIdV.Save(SOut); }
311  int GetId() const { return Id; }
312  int GetDeg() const { return GetInDeg() + GetOutDeg(); }
313  int GetInDeg() const { return InNIdV.Len(); }
314  int GetOutDeg() const { return OutNIdV.Len(); }
315  int GetInNId(const int& NodeN) const { return InNIdV[NodeN]; }
316  int GetOutNId(const int& NodeN) const { return OutNIdV[NodeN]; }
317  int GetNbrNId(const int& NodeN) const { return NodeN<GetOutDeg()?GetOutNId(NodeN):GetInNId(NodeN-GetOutDeg()); }
318  bool IsInNId(const int& NId) const { return InNIdV.SearchBin(NId) != -1; }
319  bool IsOutNId(const int& NId) const { return OutNIdV.SearchBin(NId) != -1; }
320  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
321  void PackOutNIdV() { OutNIdV.Pack(); }
322  void PackNIdV() { InNIdV.Pack(); }
323  friend class TNGraph;
324  friend class TNGraphMtx;
325  };
327  class TNodeI {
328  private:
331  public:
332  TNodeI() : NodeHI() { }
333  TNodeI(const THashIter& NodeHIter) : NodeHI(NodeHIter) { }
334  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI) { }
335  TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; return *this; }
337  TNodeI& operator++ (int) { NodeHI++; return *this; }
339  TNodeI& operator-- (int) { NodeHI--; return *this; }
340 
341  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
342  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
344  int GetId() const { return NodeHI.GetDat().GetId(); }
346  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
348  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
350  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
352 
354  int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }
356 
358  int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }
360 
362  int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
364  bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
366  bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
368  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
369  friend class TNGraph;
370  };
372  class TEdgeI {
373  private:
375  int CurEdge;
376  public:
377  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
378  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
379  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
380  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
383  while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; }
384  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
385  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
387  int GetId() const { return -1; }
389  int GetSrcNId() const { return CurNode.GetId(); }
391  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
392  friend class TNGraph;
393  };
394 private:
398 private:
399  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
400  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
401 public:
402  TNGraph() : CRef(), MxNId(0), NodeH() { }
404  explicit TNGraph(const int& Nodes, const int& Edges) : MxNId(0) { Reserve(Nodes, Edges); }
405  TNGraph(const TNGraph& Graph) : MxNId(Graph.MxNId), NodeH(Graph.NodeH) { }
407  TNGraph(TSIn& SIn) : MxNId(SIn), NodeH(SIn) { }
409  void Save(TSOut& SOut) const { MxNId.Save(SOut); NodeH.Save(SOut); }
411  static PNGraph New() { return new TNGraph(); }
413 
415  static PNGraph New(const int& Nodes, const int& Edges) { return new TNGraph(Nodes, Edges); }
417  static PNGraph Load(TSIn& SIn) { return PNGraph(new TNGraph(SIn)); }
419  bool HasFlag(const TGraphFlag& Flag) const;
420  TNGraph& operator = (const TNGraph& Graph) {
421  if (this!=&Graph) { MxNId=Graph.MxNId; NodeH=Graph.NodeH; } return *this; }
422 
424  int GetNodes() const { return NodeH.Len(); }
426 
430  int AddNode(int NId = -1);
432  int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId()); }
434 
443  int AddNode(const int& NId, const TIntV& InNIdV, const TIntV& OutNIdV);
445 
453  int AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& SrcVId, const int& DstVId);
455 
457  void DelNode(const int& NId);
459  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
461  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
463  TNodeI BegNI() const { return TNodeI(NodeH.BegI()); }
465  TNodeI EndNI() const { return TNodeI(NodeH.EndI()); }
467  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId)); }
468  // GetNodeC() has been commented out. It was a quick shortcut, do not use.
469  //const TNode& GetNodeC(const int& NId) const { return NodeH.GetDat(NId); }
471  int GetMxNId() const { return MxNId; }
472 
474  int GetEdges() const;
476 
482  int AddEdge(const int& SrcNId, const int& DstNId);
484  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
486 
490  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
492  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const;
494  TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0){NI++;} return TEdgeI(NI, EndNI()); }
496  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
498  TEdgeI GetEI(const int& EId) const; // not supported
500  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;
501 
503  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
505  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
507  void GetNIdV(TIntV& NIdV) const;
508 
510  bool Empty() const { return GetNodes()==0; }
512  void Clr() { MxNId=0; NodeH.Clr(); }
514  void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) { NodeH.Gen(Nodes/2); } }
516  void ReserveNIdInDeg(const int& NId, const int& InDeg) { GetNode(NId).InNIdV.Reserve(InDeg); }
518  void ReserveNIdOutDeg(const int& NId, const int& OutDeg) { GetNode(NId).OutNIdV.Reserve(OutDeg); }
520 
525  void Defrag(const bool& OnlyNodeLinks=false);
527 
530  bool IsOk(const bool& ThrowExcept=true) const;
532  void Dump(FILE *OutF=stdout) const;
534 
538  static PNGraph GetSmallGraph();
539  friend class TPt<TNGraph>;
540  friend class TNGraphMtx;
541 };
542 
543 // set flags
544 namespace TSnap {
545 template <> struct IsDirected<TNGraph> { enum { Val = 1 }; };
546 }
547 
548 //#//////////////////////////////////////////////
550 
563 class TNEGraph {
564 public:
565  typedef TNEGraph TNet;
567 public:
568  class TNode {
569  private:
572  public:
573  TNode() : Id(-1), InEIdV(), OutEIdV() { }
574  TNode(const int& NId) : Id(NId), InEIdV(), OutEIdV() { }
575  TNode(const TNode& Node) : Id(Node.Id), InEIdV(Node.InEIdV), OutEIdV(Node.OutEIdV) { }
576  TNode(TSIn& SIn) : Id(SIn), InEIdV(SIn), OutEIdV(SIn) { }
577  void Save(TSOut& SOut) const { Id.Save(SOut); InEIdV.Save(SOut); OutEIdV.Save(SOut); }
578  int GetId() const { return Id; }
579  int GetDeg() const { return GetInDeg() + GetOutDeg(); }
580  int GetInDeg() const { return InEIdV.Len(); }
581  int GetOutDeg() const { return OutEIdV.Len(); }
582  int GetInEId(const int& EdgeN) const { return InEIdV[EdgeN]; }
583  int GetOutEId(const int& EdgeN) const { return OutEIdV[EdgeN]; }
584  int GetNbrEId(const int& EdgeN) const { return EdgeN<GetOutDeg()?GetOutEId(EdgeN):GetInEId(EdgeN-GetOutDeg()); }
585  bool IsInEId(const int& EId) const { return InEIdV.SearchBin(EId) != -1; }
586  bool IsOutEId(const int& EId) const { return OutEIdV.SearchBin(EId) != -1; }
587  friend class TNEGraph;
588  };
589  class TEdge {
590  private:
592  public:
593  TEdge() : Id(-1), SrcNId(-1), DstNId(-1) { }
594  TEdge(const int& EId, const int& SourceNId, const int& DestNId) : Id(EId), SrcNId(SourceNId), DstNId(DestNId) { }
595  TEdge(const TEdge& Edge) : Id(Edge.Id), SrcNId(Edge.SrcNId), DstNId(Edge.DstNId) { }
596  TEdge(TSIn& SIn) : Id(SIn), SrcNId(SIn), DstNId(SIn) { }
597  void Save(TSOut& SOut) const { Id.Save(SOut); SrcNId.Save(SOut); DstNId.Save(SOut); }
598  int GetId() const { return Id; }
599  int GetSrcNId() const { return SrcNId; }
600  int GetDstNId() const { return DstNId; }
601  friend class TNEGraph;
602  };
604  class TNodeI {
605  private:
608  const TNEGraph *Graph;
609  public:
610  TNodeI() : NodeHI(), Graph(NULL) { }
611  TNodeI(const THashIter& NodeHIter, const TNEGraph* GraphPt) : NodeHI(NodeHIter), Graph(GraphPt) { }
612  TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Graph(NodeI.Graph) { }
613  TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; Graph=NodeI.Graph; return *this; }
615  TNodeI& operator++ (int) { NodeHI++; return *this; }
617  TNodeI& operator-- (int) { NodeHI--; return *this; }
618 
619  bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
620  bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
622  int GetId() const { return NodeHI.GetDat().GetId(); }
624  int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
626  int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
628  int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
630 
632  int GetInNId(const int& EdgeN) const { return Graph->GetEdge(NodeHI.GetDat().GetInEId(EdgeN)).GetSrcNId(); }
634 
636  int GetOutNId(const int& EdgeN) const { return Graph->GetEdge(NodeHI.GetDat().GetOutEId(EdgeN)).GetDstNId(); }
638 
640  int GetNbrNId(const int& EdgeN) const { const TEdge& E = Graph->GetEdge(NodeHI.GetDat().GetNbrEId(EdgeN));
641  return GetId()==E.GetSrcNId() ? E.GetDstNId():E.GetSrcNId(); }
643  bool IsInNId(const int& NId) const;
645  bool IsOutNId(const int& NId) const;
647  bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
648  // edges
650  int GetInEId(const int& EdgeN) const { return NodeHI.GetDat().GetInEId(EdgeN); }
652  int GetOutEId(const int& EdgeN) const { return NodeHI.GetDat().GetOutEId(EdgeN); }
654  int GetNbrEId(const int& EdgeN) const { return NodeHI.GetDat().GetNbrEId(EdgeN); }
656  bool IsInEId(const int& EId) const { return NodeHI.GetDat().IsInEId(EId); }
658  bool IsOutEId(const int& EId) const { return NodeHI.GetDat().IsOutEId(EId); }
660  bool IsNbrEId(const int& EId) const { return IsInEId(EId) || IsOutEId(EId); }
661  friend class TNEGraph;
662  };
664  class TEdgeI {
665  private:
668  const TNEGraph *Graph;
669  public:
670  TEdgeI() : EdgeHI(), Graph(NULL) { }
671  TEdgeI(const THashIter& EdgeHIter, const TNEGraph *GraphPt) : EdgeHI(EdgeHIter), Graph(GraphPt) { }
672  TEdgeI(const TEdgeI& EdgeI) : EdgeHI(EdgeI.EdgeHI), Graph(EdgeI.Graph) { }
673  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { EdgeHI=EdgeI.EdgeHI; Graph=EdgeI.Graph; } return *this; }
675  TEdgeI& operator++ (int) { EdgeHI++; return *this; }
676  bool operator < (const TEdgeI& EdgeI) const { return EdgeHI < EdgeI.EdgeHI; }
677  bool operator == (const TEdgeI& EdgeI) const { return EdgeHI == EdgeI.EdgeHI; }
679  int GetId() const { return EdgeHI.GetDat().GetId(); }
681  int GetSrcNId() const { return EdgeHI.GetDat().GetSrcNId(); }
683  int GetDstNId() const { return EdgeHI.GetDat().GetDstNId(); }
684  friend class TNEGraph;
685  };
686 
687 private:
688  TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
689  const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
690  TEdge& GetEdge(const int& EId) { return EdgeH.GetDat(EId); }
691  const TEdge& GetEdge(const int& EId) const { return EdgeH.GetDat(EId); }
692 private:
697 public:
698  TNEGraph() : CRef(), MxNId(0), MxEId(0) { }
700  explicit TNEGraph(const int& Nodes, const int& Edges) : CRef(), MxNId(0), MxEId(0) { Reserve(Nodes, Edges); }
701  TNEGraph(const TNEGraph& Graph) : MxNId(Graph.MxNId), MxEId(Graph.MxEId), NodeH(Graph.NodeH), EdgeH(Graph.EdgeH) { }
703  TNEGraph(TSIn& SIn) : MxNId(SIn), MxEId(SIn), NodeH(SIn), EdgeH(SIn) { }
705  void Save(TSOut& SOut) const { MxNId.Save(SOut); MxEId.Save(SOut); NodeH.Save(SOut); EdgeH.Save(SOut); }
707  static PNEGraph New() { return PNEGraph(new TNEGraph()); }
709 
711  static PNEGraph New(const int& Nodes, const int& Edges) { return PNEGraph(new TNEGraph(Nodes, Edges)); }
713  static PNEGraph Load(TSIn& SIn) { return PNEGraph(new TNEGraph(SIn)); }
715  bool HasFlag(const TGraphFlag& Flag) const;
716  TNEGraph& operator = (const TNEGraph& Graph) { if (this!=&Graph) {
717  MxNId=Graph.MxNId; MxEId=Graph.MxEId; NodeH=Graph.NodeH; EdgeH=Graph.EdgeH; } return *this; }
718 
720  int GetNodes() const { return NodeH.Len(); }
722 
726  int AddNode(int NId = -1);
728  int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId()); }
730 
732  void DelNode(const int& NId);
734  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
736  bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
738  TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); }
740  TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); }
742  TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); }
744  int GetMxNId() const { return MxNId; }
745 
747  int GetEdges() const { return EdgeH.Len(); }
749 
754  int AddEdge(const int& SrcNId, const int& DstNId, int EId = -1);
756  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI.GetId()); }
758  void DelEdge(const int& EId);
760 
764  void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
766  bool IsEdge(const int& EId) const { return EdgeH.IsKey(EId); }
768  bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const { int EId; return IsEdge(SrcNId, DstNId, EId, IsDir); }
770  bool IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir = true) const;
772  int GetEId(const int& SrcNId, const int& DstNId) const { int EId; return IsEdge(SrcNId, DstNId, EId)?EId:-1; }
774  TEdgeI BegEI() const { return TEdgeI(EdgeH.BegI(), this); }
776  TEdgeI EndEI() const { return TEdgeI(EdgeH.EndI(), this); }
778  TEdgeI GetEI(const int& EId) const { return TEdgeI(EdgeH.GetI(EId), this); }
780  TEdgeI GetEI(const int& SrcNId, const int& DstNId) const { return GetEI(GetEId(SrcNId, DstNId)); }
781 
783  int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
785  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
787  int GetRndEId(TRnd& Rnd=TInt::Rnd) { return EdgeH.GetKey(EdgeH.GetRndKeyId(Rnd, 0.8)); }
789  TEdgeI GetRndEI(TRnd& Rnd=TInt::Rnd) { return GetEI(GetRndEId(Rnd)); }
791  void GetNIdV(TIntV& NIdV) const;
793  void GetEIdV(TIntV& EIdV) const;
794 
796  bool Empty() const { return GetNodes()==0; }
798  void Clr() { MxNId=0; MxEId=0; NodeH.Clr(); EdgeH.Clr(); }
800  void Reserve(const int& Nodes, const int& Edges) {
801  if (Nodes>0) { NodeH.Gen(Nodes/2); } if (Edges>0) { EdgeH.Gen(Edges/2); } }
803 
808  void Defrag(const bool& OnlyNodeLinks=false);
810 
813  bool IsOk(const bool& ThrowExcept=true) const;
815  void Dump(FILE *OutF=stdout) const;
817 
821  static PNEGraph GetSmallGraph();
822  friend class TPt<TNEGraph>;
823 };
824 
825 // set flags
826 namespace TSnap {
827 template <> struct IsMultiGraph<TNEGraph> { enum { Val = 1 }; };
828 template <> struct IsDirected<TNEGraph> { enum { Val = 1 }; };
829 }
830 
831 //#//////////////////////////////////////////////
833 
834 class TBPGraph {
835 public:
836  typedef TBPGraph TNet;
838  typedef enum { bgsUndef, bgsLeft, bgsRight, bgsBoth } TNodeTy; // left or right hand side node
839 public:
840  class TNode {
841  private:
844  TNodeTy NodeTy; // remove
845  public:
846  TNode() : Id(-1), NIdV(), NodeTy(bgsUndef) { }
847  TNode(const int& NId) : Id(NId), NIdV(), NodeTy(true?bgsLeft:bgsRight) { }
848  TNode(const TNode& Node) : Id(Node.Id), NIdV(Node.NIdV), NodeTy(Node.NodeTy) { }
849  TNode(TSIn& SIn) : Id(SIn), NIdV(SIn), NodeTy(bgsUndef) { TInt Ty(SIn); NodeTy=(TNodeTy)Ty.Val; }
850  void Save(TSOut& SOut) const { Id.Save(SOut); NIdV.Save(SOut); TInt(NodeTy).Save(SOut); }
851  int GetId() const { return Id; }
852  int GetDeg() const { return NIdV.Len(); }
853  int GetInDeg() const { return GetDeg(); }
854  int GetOutDeg() const { return GetDeg(); }
855  int GetInNId(const int& NodeN) const { return GetNbrNId(NodeN); }
856  int GetOutNId(const int& NodeN) const { return GetNbrNId(NodeN); }
857  int GetNbrNId(const int& NodeN) const { return NIdV[NodeN]; }
858  bool IsNbrNId(const int& NId) const { return NIdV.SearchBin(NId)!=-1; }
859  bool IsInNId(const int& NId) const { return IsNbrNId(NId); }
860  bool IsOutNId(const int& NId) const { return IsNbrNId(NId); }
861  void PackOutNIdV() { NIdV.Pack(); }
862  void PackNIdV() { NIdV.Pack(); }
863  friend class TBPGraph;
864  };
866  class TNodeI {
867  private:
869  THashIter LeftHI, RightHI; // iterator over left and right hand-side nodes
870  private:
871  inline THashIter HI() const { return ! LeftHI.IsEnd()?LeftHI:RightHI; }
872  public:
873  TNodeI() : LeftHI(), RightHI() { }
874  TNodeI(const THashIter& LeftHIter, const THashIter& RightHIter) : LeftHI(LeftHIter), RightHI(RightHIter) { }
875  TNodeI(const TNodeI& NodeI) : LeftHI(NodeI.LeftHI), RightHI(NodeI.RightHI) { }
876  TNodeI& operator = (const TNodeI& NodeI) { LeftHI = NodeI.LeftHI; RightHI=NodeI.RightHI; return *this; }
879  if (! LeftHI.IsEnd()) {
880  LeftHI++; }
881  else if (! RightHI.IsEnd()) {
882  RightHI++; }
883  return *this; }
884  bool operator < (const TNodeI& NodeI) const { return LeftHI < NodeI.LeftHI || (LeftHI==NodeI.LeftHI && RightHI < NodeI.RightHI); }
885  bool operator == (const TNodeI& NodeI) const { return LeftHI==NodeI.LeftHI && RightHI==NodeI.RightHI; }
887  int GetId() const { return HI().GetDat().GetId(); }
889  bool IsLeft() const { return ! LeftHI.IsEnd(); }
891  bool IsRight() const { return ! IsLeft(); }
893  int GetDeg() const { return HI().GetDat().GetDeg(); }
895  int GetInDeg() const { return HI().GetDat().GetInDeg(); }
897  int GetOutDeg() const { return HI().GetDat().GetOutDeg(); }
899 
900  int GetInNId(const int& NodeN) const { return HI().GetDat().GetInNId(NodeN); }
902 
903  int GetOutNId(const int& NodeN) const { return HI().GetDat().GetOutNId(NodeN); }
905 
906  int GetNbrNId(const int& NodeN) const { return HI().GetDat().GetNbrNId(NodeN); }
908  bool IsInNId(const int& NId) const { return HI().GetDat().IsInNId(NId); }
910  bool IsOutNId(const int& NId) const { return HI().GetDat().IsOutNId(NId); }
912  bool IsNbrNId(const int& NId) const { return HI().GetDat().IsNbrNId(NId); }
913  friend class TBPGraph;
914  };
916  class TEdgeI {
917  private:
918  TNodeI CurNode, EndNode; // end node on the 'left'
919  int CurEdge;
920  public:
921  TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
922  TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
923  TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
924  TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
927  while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } } return *this; }
928  bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
929  bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
931  int GetId() const { return -1; }
933  int GetSrcNId() const { return CurNode.GetId(); }
935  int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
937  int GetLNId() const { return GetSrcNId(); }
939  int GetRNId() const { return GetDstNId(); }
940  friend class TBPGraph;
941  };
942 private:
944  TInt MxNId; // maximum node ID in the graph
945  THash<TInt, TNode> LeftH; // 'left' nodes
946  THash<TInt, TNode> RightH; // 'right' nodes
947 private:
948  //TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
949  //const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
950 public:
951  TBPGraph() : CRef(), MxNId(0), LeftH(), RightH() { }
953  explicit TBPGraph(const int& Nodes, const int& Edges) : MxNId(0) { }
954  TBPGraph(const TBPGraph& BPGraph) : MxNId(BPGraph.MxNId), LeftH(BPGraph.LeftH), RightH(BPGraph.RightH) { }
956  TBPGraph(TSIn& SIn) : MxNId(SIn), LeftH(SIn), RightH(SIn) { }
958  void Save(TSOut& SOut) const { MxNId.Save(SOut); LeftH.Save(SOut); RightH.Save(SOut); }
960  static PBPGraph New() { return new TBPGraph(); }
962 
963  static PBPGraph New(const int& Nodes, const int& Edges) { return new TBPGraph(Nodes, Edges); }
965  static PBPGraph Load(TSIn& SIn) { return PBPGraph(new TBPGraph(SIn)); }
967  bool HasFlag(const TGraphFlag& Flag) const;
968  TBPGraph& operator = (const TBPGraph& BPGraph) {
969  if (this!=&BPGraph) { MxNId=BPGraph.MxNId; LeftH=BPGraph.LeftH; RightH=BPGraph.RightH; } return *this; }
970 
972  int GetNodes() const { return GetLNodes() + GetRNodes(); }
974  int GetLNodes() const { return LeftH.Len(); }
976  int GetRNodes() const { return RightH.Len(); }
978 
979  int AddNode(int NId = -1, const bool& LeftNode=true);
981  int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId(), NodeI.IsLeft()); }
983 
984  void DelNode(const int& NId);
986  void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
988  bool IsNode(const int& NId) const { return IsLNode(NId) || IsRNode(NId); }
990  bool IsLNode(const int& NId) const { return LeftH.IsKey(NId); }
992  bool IsRNode(const int& NId) const { return RightH.IsKey(NId); }
994  int GetMxNId() const { return MxNId; }
995 
997  TNodeI BegNI() const { return TNodeI(LeftH.BegI(), RightH.BegI()); }
999  TNodeI EndNI() const { return TNodeI(LeftH.EndI(), RightH.EndI()); }
1001  TNodeI GetNI(const int& NId) const { return IsLNode(NId) ? TNodeI(LeftH.GetI(NId), RightH.EndI()) : TNodeI(LeftH.EndI(), RightH.GetI(NId)); }
1003  TNodeI BegLNI() const { return TNodeI(LeftH.BegI(), RightH.EndI()); }
1005  TNodeI EndLNI() const { return EndNI(); }
1007  TNodeI BegRNI() const { return TNodeI(LeftH.EndI(), RightH.BegI()); }
1009  TNodeI EndRNI() const { return EndNI(); }
1010 
1012  int GetEdges() const;
1014 
1015  int AddEdge(const int& LeftNId, const int& RightNId);
1017  int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
1019 
1020  void DelEdge(const int& LeftNId, const int& RightNId);
1022  bool IsEdge(const int& LeftNId, const int& RightNId) const;
1024  TEdgeI BegEI() const { TNodeI NI=BegLNI(); while (NI<EndLNI() && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { NI++; } return TEdgeI(NI, EndLNI()); }
1026  TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
1028  TEdgeI GetEI(const int& EId) const;
1030 
1031  TEdgeI GetEI(const int& LeftNId, const int& RightNId) const;
1032 
1034  int GetRndNId(TRnd& Rnd=TInt::Rnd);
1036  int GetRndLNId(TRnd& Rnd=TInt::Rnd);
1038  int GetRndRNId(TRnd& Rnd=TInt::Rnd);
1040  TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
1042  void GetNIdV(TIntV& NIdV) const;
1044  void GetLNIdV(TIntV& NIdV) const;
1046  void GetRNIdV(TIntV& NIdV) const;
1047 
1049  bool Empty() const { return GetNodes()==0; }
1051  void Clr() { MxNId=0; LeftH.Clr(); RightH.Clr(); }
1053  void Reserve(const int& Nodes, const int& Edges);
1055 
1056  void Defrag(const bool& OnlyNodeLinks=false);
1058 
1059  bool IsOk(const bool& ThrowExcept=true) const;
1061  void Dump(FILE *OutF=stdout) const;
1063 
1064  static PBPGraph GetSmallGraph();
1065 
1066  friend class TPt<TBPGraph>;
1067 };
1068 
1069 // set flags
1070 namespace TSnap {
1071 template <> struct IsBipart<TBPGraph> { enum { Val = 1 }; };
1072 }
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graph.cpp:204
Definition: bd.h:440
static PBPGraph GetSmallGraph()
Returns a small graph on 2 'left', 3 'right' nodes and 4 edges.
Definition: graph.cpp:818
int AddEdge(const TEdgeI &EdgeI)
Adds an edge between EdgeI.GetLNId() and EdgeI.GetRNId() to the graph.
Definition: graph.h:1017
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:114
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:362
bool operator<(const TNodeI &NodeI) const
Definition: graph.h:884
TBPGraph(const TBPGraph &BPGraph)
!! Reserve(Nodes, Edges); }
Definition: graph.h:954
int GetDeg() const
Definition: graph.h:852
int GetId() const
Gets edge ID. Always returns -1 since only edges in multigraphs have explicit IDs.
Definition: graph.h:931
TPt< TBPGraph > PNet
Definition: graph.h:837
TUNGraph(const TUNGraph &Graph)
Definition: graph.h:146
THashIter NodeHI
Definition: graph.h:66
int AddNode(const TNodeI &NodeId)
Adds a node of ID NodeI.GetId() to the graph.
Definition: graph.h:432
int GetOutDeg() const
Definition: graph.h:314
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a biparite graph of Nodes nodes and Edges edges.
Definition: graph.cpp:740
int GetSrcNId() const
Definition: graph.h:599
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:326
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:156
TNodeI CurNode
Definition: graph.h:374
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.cpp:418
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:447
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:466
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:463
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:536
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:232
void GetRNIdV(TIntV &NIdV) const
Gets a vector IDs of all 'right' nodes in the bipartite graph.
Definition: graph.cpp:734
TNode(const int &NId)
Definition: graph.h:43
bool IsOutNId(const int &NId) const
Definition: graph.h:56
bool operator==(const TEdgeI &EdgeI) const
Definition: graph.h:126
TNodeI & operator--(int)
Decrement iterator.
Definition: graph.h:76
TEdgeI & operator++(int)
Increment iterator.
Definition: graph.h:926
TNodeI & operator=(const TNodeI &NodeI)
Definition: graph.h:876
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:963
TNode(const TNode &Node)
Definition: graph.h:848
bool Empty() const
Tests whether the graph is empty (has zero nodes).
Definition: graph.h:796
bool operator==(const TNodeI &NodeI) const
Definition: graph.h:885
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:1001
int GetInDeg() const
Returns in-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:895
static PUNGraph GetSmallGraph()
Returns a small graph on 5 nodes and 5 edges.
Definition: graph.cpp:193
Definition: dt.h:11
TNEGraph & operator=(const TNEGraph &Graph)
Definition: graph.h:716
THash< TInt, TNode >::TIter THashIter
Definition: graph.h:65
TNode & GetNode(const int &NId)
Definition: graph.h:140
bool operator==(const TEdgeI &EdgeI) const
Definition: graph.h:677
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: graph.h:110
int GetNbrEId(const int &EdgeN) const
Definition: graph.h:584
TEdge(const int &EId, const int &SourceNId, const int &DestNId)
Definition: graph.h:594
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.cpp:704
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:988
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:387
TNodeTy NodeTy
Definition: graph.h:844
int Val
Definition: dt.h:1044
const TNEGraph * Graph
Definition: graph.h:668
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:411
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:467
void Save(TSOut &SOut) const
Definition: dt.h:1058
void ReserveNIdInDeg(const int &NId, const int &InDeg)
Reserves memory for node ID NId having InDeg in-edges.
Definition: graph.h:516
THashIter HI() const
Definition: graph.h:871
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:774
TNEGraph(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:700
int AddNode(const TNodeI &NodeI)
Adds a node of ID NodeI.GetId() to the graph.
Definition: graph.h:981
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:125
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:496
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:628
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:132
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:210
void PackNIdV()
Definition: graph.h:58
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.h:364
bool IsLNode(const int &NId) const
Tests whether ID NId is a 'left' side node.
Definition: graph.h:990
TNEGraph(TSIn &SIn)
Constructor for loading the graph from a (binary) stream SIn.
Definition: graph.h:703
TUNGraph(TSIn &SIn)
Constructor that loads the graph from a (binary) stream SIn.
Definition: graph.h:148
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: graph.h:380
Tests (at compile time) if the graph is directed.
Definition: gbase.h:25
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:994
int GetNbrNId(const int &NodeN) const
Definition: graph.h:857
TIter BegI() const
Definition: hash.h:171
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:278
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:866
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:935
THash< TInt, TNode > NodeH
Definition: graph.h:397
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:74
TNodeTy
Definition: graph.h:838
int AddEdge(const TEdgeI &EdgeI)
Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph.
Definition: graph.h:484
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
bool IsInEId(const int &EId) const
Definition: graph.h:585
int GetId() const
Definition: graph.h:578
TPt< TNEGraph > PNet
Definition: graph.h:566
TNodeI & operator=(const TNodeI &NodeI)
Definition: graph.h:71
bool operator<(const TEdgeI &EdgeI) const
Definition: graph.h:676
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:63
int GetId() const
Gets edge ID.
Definition: graph.h:679
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:999
bool operator==(const TEdgeI &EdgeI) const
Definition: graph.h:929
void Save(TSOut &SOut) const
Definition: hash.h:141
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:997
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:768
TNodeI & operator--(int)
Decrement iterator.
Definition: graph.h:617
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:494
int GetInDeg() const
Definition: graph.h:580
TInt NEdges
Definition: graph.h:137
TEdgeI & operator++(int)
Increment iterator.
Definition: graph.h:382
TInt SrcNId
Definition: graph.h:591
void Save(TSOut &SOut) const
Definition: graph.h:597
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:341
int GetOutEId(const int &EdgeN) const
Definition: graph.h:583
int AddNode(int NId=-1, const bool &LeftNode=true)
Adds a node of ID NId to the graph.
Definition: graph.cpp:621
void PackOutNIdV()
Definition: graph.h:57
Directed multigraph.
Definition: graph.h:563
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:776
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:424
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:1026
THashIter NodeHI
Definition: graph.h:330
int GetInDeg() const
Definition: graph.h:49
void PackOutNIdV()
Definition: graph.h:321
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:208
TCRef CRef
Definition: graph.h:693
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:179
static PNEGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:713
TNGraph()
Definition: graph.h:402
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:664
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: graph.h:705
TNode(const int &NId)
Definition: graph.h:307
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:130
TNodeI & operator--(int)
Decrement iterator.
Definition: graph.h:339
TCRef CRef
Definition: graph.h:943
TNodeI EndNode
Definition: graph.h:116
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: graph.h:150
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: graph.h:368
const TNode & GetNode(const int &NId) const
Definition: graph.h:141
TIter EndI() const
Definition: hash.h:176
TNEGraph TNet
Definition: graph.h:565
THashIter NodeHI
Definition: graph.h:607
static TRnd Rnd
Definition: dt.h:1051
int GetId() const
Definition: graph.h:47
bool IsInNId(const int &NId) const
Definition: graph.h:55
int GetRndLNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'left' node in the graph.
Definition: graph.cpp:712
TNodeI & operator++(int)
Increment iterator.
Definition: graph.h:615
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:953
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:660
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:738
int GetId() const
Returns edge ID. Always returns -1 since only edges in multigraphs have explicit IDs.
Definition: graph.h:387
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: graph.h:734
THashIter EdgeHI
Definition: graph.h:667
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:165
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.h:908
TNodeI(const THashIter &NodeHIter, const TNEGraph *GraphPt)
Definition: graph.h:611
THash< TInt, TNode > NodeH
Definition: graph.h:695
int GetInNId(const int &EdgeN) const
Returns ID of EdgeN-th in-node (the node pointing to the current node).
Definition: graph.h:632
TNGraph(TSIn &SIn)
Constructor that loads the graph from a (binary) stream SIn.
Definition: graph.h:407
TNodeI EndNode
Definition: graph.h:374
int GetInNId(const int &NodeN) const
Definition: graph.h:855
int GetOutDeg() const
Definition: graph.h:581
TNode & GetNode(const int &NId)
Definition: graph.h:399
int AddEdge(const TEdgeI &EdgeI)
Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
Definition: graph.h:756
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:885
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:241
TEdgeI & operator++(int)
Increment iterator.
Definition: graph.h:675
int GetId() const
Returns ID of the current node.
Definition: graph.h:887
int GetOutNId(const int &NodeN) const
Definition: graph.h:856
int GetInDeg() const
Definition: graph.h:313
int GetDstNId() const
Gets destination of an edge.
Definition: graph.h:683
THash< TInt, TEdge > EdgeH
Definition: graph.h:696
int GetDstNId() const
Definition: graph.h:600
int GetLNodes() const
Returns the number of nodes on the 'left' side of the biparite graph.
Definition: graph.h:974
TEdgeI(const TEdgeI &EdgeI)
Definition: graph.h:121
bool operator<(const TEdgeI &EdgeI) const
Definition: graph.h:125
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: graph.h:922
static PBPGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:965
TCRef CRef
Definition: graph.h:136
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:259
int GetOutEId(const int &EdgeN) const
Returns ID of EdgeN-th out-edge.
Definition: graph.h:652
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:906
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:85
void Clr()
Deletes all nodes and edges from the bipartite graph.
Definition: graph.h:1051
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:740
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
TNode(const int &NId)
Definition: graph.h:847
int GetInEId(const int &EdgeN) const
Definition: graph.h:582
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:742
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:897
int GetId() const
Definition: graph.h:311
int GetNbrNId(const int &EdgeN) const
Returns ID of EdgeN-th neighboring node.
Definition: graph.h:640
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the graph.
Definition: graph.cpp:514
TEdgeI GetEI(const int &SrcNId, const int &DstNId) const
Returns an iterator referring to edge (SrcNId, DstNId) in the graph.
Definition: graph.h:780
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:720
TNodeI & operator++(int)
Increment iterator.
Definition: graph.h:74
THashIter LeftHI
Definition: graph.h:869
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:89
bool Empty() const
Tests whether the bipartite graph is empty (has zero nodes).
Definition: graph.h:1049
void PackNIdV()
Definition: graph.h:322
TPt< TNEGraph > PNEGraph
Pointer to a directed multigraph (TNEGraph)
Definition: graph.h:21
TEdge & GetEdge(const int &EId)
Definition: graph.h:690
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:937
THash< TInt, TNode >::TIter THashIter
Definition: graph.h:329
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.cpp:427
TNodeI EndRNI() const
Returns an iterator referring to the past-the-end 'right' node in the graph.
Definition: graph.h:1009
TNodeI & operator++(int)
Increment iterator.
Definition: graph.h:337
bool IsOutNId(const int &NId) const
Definition: graph.h:860
void Gen(const int &ExpectVals)
Definition: hash.h:180
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:372
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:648
TInt MxNId
Definition: graph.h:137
TNodeI(const THashIter &LeftHIter, const THashIter &RightHIter)
Definition: graph.h:874
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph.
Definition: graph.cpp:286
static PNEGraph GetSmallGraph()
Returns a small multigraph on 5 nodes and 6 edges.
Definition: graph.cpp:610
int GetNodes() const
Returns the total number of nodes in the graph.
Definition: graph.h:972
bool IsInNId(const int &NId) const
Definition: graph.h:859
static PNGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:417
Definition: gsvd.h:5
TEdgeI(const THashIter &EdgeHIter, const TNEGraph *GraphPt)
Definition: graph.h:671
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: graph.h:200
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:295
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:313
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:252
TNGraph(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:404
bool Empty() const
Tests whether the graph is empty (has zero nodes).
Definition: graph.h:248
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:503
TNodeI BegLNI() const
Returns an iterator referring to the first 'left' node in the graph.
Definition: graph.h:1003
int GetInEId(const int &EdgeN) const
Returns ID of EdgeN-th in-edge.
Definition: graph.h:650
TNode(TSIn &SIn)
Definition: graph.h:576
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.h:366
TNode(TSIn &SIn)
Definition: graph.h:309
int GetRNodes() const
Returns the number of nodes on the 'right' side of the biparite graph.
Definition: graph.h:976
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:208
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
Definition: graph.cpp:414
THash< TInt, TNode >::TIter THashIter
Definition: graph.h:606
Tests (at compile time) if the graph is a multigraph with multiple edges between the same nodes...
Definition: gbase.h:27
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:461
TNodeI(const TNodeI &NodeI)
Definition: graph.h:70
TNode(const TNode &Node)
Definition: graph.h:575
int GetOutNId(const int &EdgeN) const
Returns ID of EdgeN-th out-node (the node the current node points to).
Definition: graph.h:636
TInt DstNId
Definition: graph.h:591
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:685
bool operator<(const TEdgeI &EdgeI) const
Definition: graph.h:928
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:221
TInt MxNId
Definition: graph.h:944
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:230
void PackOutNIdV()
Definition: graph.h:861
void GetLNIdV(TIntV &NIdV) const
Gets a vector IDs of all 'left' nodes in the bipartite graph.
Definition: graph.cpp:728
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:152
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: graph.h:378
TPt< TNGraph > PNGraph
Pointer to a directed graph (TNGraph)
Definition: graph.h:16
TNodeI CurNode
Definition: graph.h:116
bool operator<(const TNodeI &NodeI) const
Definition: graph.h:619
TBPGraph TNet
Definition: graph.h:836
int GetOutNId(const int &NodeN) const
Definition: graph.h:316
TBPGraph & operator=(const TBPGraph &BPGraph)
Definition: graph.h:968
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:436
int AddNode(const TNodeI &NodeId)
Adds a node of ID NodeI.GetId() to the graph.
Definition: graph.h:728
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:95
TNodeI BegRNI() const
Returns an iterator referring to the first 'right' node in the graph.
Definition: graph.h:1007
int GetOutNId(const int &NodeN) const
Definition: graph.h:52
TIntV OutEIdV
Definition: graph.h:571
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:589
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the graph.
Definition: graph.h:243
void Save(TSOut &SOut) const
Definition: graph.h:850
void Save(TSOut &SOut) const
Definition: graph.h:46
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:1005
int GetRNId() const
Gets the ID of the node on the 'right' side of the edge.
Definition: graph.h:939
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the graph.
Definition: graph.h:505
TNodeI & operator=(const TNodeI &NodeI)
Definition: graph.h:335
bool operator==(const TNodeI &NodeI) const
Definition: graph.h:620
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:346
bool operator==(const TNodeI &NodeI) const
Definition: graph.h:80
Definition: fl.h:128
TNGraph(const TNGraph &Graph)
Definition: graph.h:405
THash< TInt, TNode >::TIter THashIter
Definition: graph.h:868
TIntV NIdV
Definition: graph.h:843
int GetDeg() const
Definition: graph.h:579
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: graph.h:912
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:332
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:84
bool operator<(const TNodeI &NodeI) const
Definition: graph.h:341
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:893
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:512
TUNGraph()
Definition: graph.h:143
Definition: dt.h:1042
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:471
bool IsNbrNId(const int &NId) const
Definition: graph.h:858
TNEGraph(const TNEGraph &Graph)
Definition: graph.h:701
TNode & GetNode(const int &NId)
Definition: graph.h:688
static PUNGraph Load(TSIn &SIn)
Static constructor that loads the graph from a stream SIn and returns a pointer to it...
Definition: graph.h:158
static PNEGraph New()
Static constructor that returns a pointer to the graph. Call: PNEGraph Graph = TNEGraph::New().
Definition: graph.h:707
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: graph.h:409
void Save(TSOut &SOut) const
Definition: graph.h:577
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:655
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:669
THashIter RightHI
Definition: graph.h:869
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:933
TEdge(const TEdge &Edge)
Definition: graph.h:595
Directed graph.
Definition: graph.h:296
bool IsNbrNId(const int &NId) const
Definition: graph.h:54
int GetNbrNId(const int &NodeN) const
Definition: graph.h:53
TEdgeI GetEI(const int &EId) const
Returns an iterator referring to edge with edge ID EId.
Definition: graph.h:778
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:632
TNode(const TNode &Node)
Definition: graph.h:308
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: graph.h:924
bool IsEdge(const int &EId) const
Tests whether an edge with edge ID EId exists in the graph.
Definition: graph.h:766
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:465
int GetId() const
Returns ID of the current node.
Definition: graph.h:344
TBPGraph()
Definition: graph.h:951
static PNGraph GetSmallGraph()
Returns a small graph on 5 nodes and 6 edges.
Definition: graph.cpp:404
TNode(const int &NId)
Definition: graph.h:574
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:99
int GetRndRNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random 'right' node in the graph.
Definition: graph.cpp:716
const TNode & GetNode(const int &NId) const
Definition: graph.h:689
int GetId() const
Returns edge ID. Always returns -1 since only edges in multigraphs have explicit IDs.
Definition: graph.h:128
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:800
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:350
Bipartite graph.
Definition: graph.h:834
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:772
int GetSrcNId() const
Gets the source of an edge.
Definition: graph.h:681
TNodeI & operator=(const TNodeI &NodeI)
Definition: graph.h:613
THash< TInt, TNode > NodeH
Definition: graph.h:138
TEdge(TSIn &SIn)
Definition: graph.h:596
TNode(const TNode &Node)
Definition: graph.h:44
bool IsOutEId(const int &EId) const
Definition: graph.h:586
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:415
void GetEIdV(TIntV &EIdV) const
Gets a vector IDs of all edges in the graph.
Definition: graph.cpp:520
TNode(TSIn &SIn)
Definition: graph.h:849
void Pack()
The vector reduces its capacity (frees memory) to match its size.
Definition: ds.h:987
int GetId() const
Definition: graph.h:851
int GetRndEId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random edge in the graph.
Definition: graph.h:787
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:992
bool IsRight() const
Tests whether the node is right hand side node.
Definition: graph.h:891
TCRef CRef
Definition: graph.h:395
THash< TInt, TNode > RightH
Definition: graph.h:946
Definition: hash.h:88
TNodeI(const THashIter &NodeHIter)
Definition: graph.h:333
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:711
TPt< TNGraph > PNet
Definition: graph.h:299
int GetNbrEId(const int &EdgeN) const
Returns ID of EdgeN-th in or out-edge.
Definition: graph.h:654
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.h:747
int GetInDeg() const
Returns in-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:87
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:327
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:132
const TEdge & GetEdge(const int &EId) const
Definition: graph.h:691
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:206
int GetOutDeg() const
Definition: graph.h:854
const TNEGraph * Graph
Definition: graph.h:608
TIntV InNIdV
Definition: graph.h:304
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.h:910
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:783
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:514
static PBPGraph New()
Static constructor that returns a pointer to the graph. Call: PBPGraph BPGraph = TBPGraph::New();.
Definition: graph.h:960
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:104
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:315
THash< TInt, TNode > LeftH
Definition: graph.h:945
TNode(TSIn &SIn)
Definition: graph.h:45
TInt MxNId
Definition: graph.h:694
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:202
TInt MxNId
Definition: graph.h:396
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:903
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:785
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 operator==(const TNodeI &NodeI) const
Definition: graph.h:342
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:798
TNodeI CurNode
Definition: graph.h:918
void GetNIdV(TIntV &NIdV) const
Gets a vector IDs of all nodes in the bipartite graph.
Definition: graph.cpp:720
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:250
TNodeI & operator++(int)
Increment iterator.
Definition: graph.h:878
bool IsOk(const bool &ThrowExcept=true) const
Checks the graph data structure for internal consistency.
Definition: graph.cpp:142
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:506
TEdgeI GetRndEI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random edge in the graph.
Definition: graph.h:789
TIntV OutNIdV
Definition: graph.h:304
int GetOutDeg() const
Definition: graph.h:50
const TNode & GetNode(const int &NId) const
Definition: graph.h:400
bool HasFlag(const TGraphFlag &Flag) const
Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the graph.
Definition: graph.cpp:527
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:1024
TNodeI EndNode
Definition: graph.h:918
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:348
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: graph.h:459
void Dump(FILE *OutF=stdout) const
Print the biparite graph in a human readable form to an output stream OutF.
Definition: graph.cpp:795
void DelNode(const TNode &NodeI)
Deletes node of ID NodeI.GetId() from the graph.
Definition: graph.h:986
int GetSrcNId() const
Returns the source node of the edge.
Definition: graph.h:389
int GetId() const
Returns ID of the current node.
Definition: graph.h:622
void Defrag(const bool &OnlyNodeLinks=false)
Defragments the biparite graph.
Definition: graph.cpp:744
int GetId() const
Returns ID of the current node.
Definition: graph.h:83
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:108
TEdgeI(const TEdgeI &EdgeI)
Definition: graph.h:923
bool IsKey(const TKey &Key) const
Definition: hash.h:216
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:354
void PackNIdV()
Definition: graph.h:862
bool IsOutNId(const int &NId) const
Tests whether the current node points to node with ID NId.
Definition: graph.h:108
void DelEdge(const int &EId)
Deletes an edge with edge ID EId from the graph.
Definition: graph.cpp:477
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
int GetInNId(const int &NodeN) const
Definition: graph.h:51
bool IsOutEId(const int &EId) const
Tests whether the edge with ID EId is an out-edge of current node.
Definition: graph.h:658
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:204
int GetInNId(const int &NodeN) const
Definition: graph.h:315
int GetDeg() const
Definition: graph.h:312
int GetDeg() const
Definition: graph.h:48
bool operator<(const TEdgeI &EdgeI) const
Definition: graph.h:384
void ReserveNIdDeg(const int &NId, const int &Deg)
Reserves memory for node ID NId having Deg edges.
Definition: graph.h:254
bool IsOutNId(const int &NId) const
Definition: graph.h:319
int GetNbrNId(const int &NodeN) const
Definition: graph.h:317
int Len() const
Definition: hash.h:186
TNodeI(const TNodeI &NodeI)
Definition: graph.h:875
TInt MxEId
Definition: graph.h:694
int AddNode(const TNodeI &NodeI)
Adds a node of ID NodeI.GetId() to the graph.
Definition: graph.h:173
TNodeI(const THashIter &NodeHIter)
Definition: graph.h:69
TNodeI(const TNodeI &NodeI)
Definition: graph.h:612
bool IsInEId(const int &EId) const
Tests whether the edge with ID EId is an in-edge of current node.
Definition: graph.h:656
bool IsNbrNId(const int &NId) const
Definition: graph.h:320
bool operator==(const TEdgeI &EdgeI) const
Definition: graph.h:385
TNodeI GetRndNI(TRnd &Rnd=TInt::Rnd)
Returns an interator referring to a random node in the graph.
Definition: graph.h:1040
bool IsOk(const bool &ThrowExcept=true) const
Checks the bipartite graph data structure for internal consistency.
Definition: graph.cpp:753
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:59
Tests (at compile time) if the graph is a bipartite graph type.
Definition: gbase.h:35
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: graph.h:673
TEdgeI(const TEdgeI &EdgeI)
Definition: graph.h:672
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:916
void Save(TSOut &SOut) const
Definition: graph.h:310
TNGraph & operator=(const TNGraph &Graph)
Definition: graph.h:420
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:604
int GetDstNId() const
Returns the destination node of the edge.
Definition: graph.h:391
bool IsInNId(const int &NId) const
Definition: graph.h:318
bool operator<(const TNodeI &NodeI) const
Definition: graph.h:79
int GetInDeg() const
Definition: graph.h:853
TUNGraph & operator=(const TUNGraph &Graph)
Definition: graph.h:161
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:358
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:624
bool Empty() const
Tests whether the graph is empty (has zero nodes).
Definition: graph.h:510
TEdgeI & operator++(int)
Increment iterator.
Definition: graph.h:124
THash< TInt, TEdge >::TIter THashIter
Definition: graph.h:666
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:626
TEdgeI GetEI(const int &EId) const
Not supported/implemented!
TEdgeI(const TNodeI &NodeI, const TNodeI &EndNodeI, const int &EdgeN=0)
Definition: graph.h:120
bool IsLeft() const
Tests whether the node is left hand side node.
Definition: graph.h:889
TUNGraph(const int &Nodes, const int &Edges)
Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:145
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:736
TEdgeI(const TEdgeI &EdgeI)
Definition: graph.h:379
TEdgeI & operator=(const TEdgeI &EdgeI)
Definition: graph.h:122
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:94
void Save(TSOut &SOut) const
Saves the graph to a (binary) stream SOut.
Definition: graph.h:958
TBPGraph(TSIn &SIn)
Constructor for loading the graph from a (binary) stream SIn.
Definition: graph.h:956
TNodeI(const TNodeI &NodeI)
Definition: graph.h:334
void ReserveNIdOutDeg(const int &NId, const int &OutDeg)
Reserves memory for node ID NId having OutDeg out-edges.
Definition: graph.h:518
TNEGraph()
Definition: graph.h:698
bool IsNbrNId(const int &NId) const
Tests whether node with ID NId is a neighbor of the current node.
Definition: graph.h:647
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:744
TIter GetI(const TKey &Key) const
Definition: hash.h:178
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:900
TIntV InEIdV
Definition: graph.h:571
int GetId() const
Definition: graph.h:598
bool IsInNId(const int &NId) const
Tests whether node with ID NId points to the current node.
Definition: graph.h:106
TNGraph TNet
Definition: graph.h:298