SNAP Library 2.0, User Reference  2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
graph.h
Go to the documentation of this file.
00001 //#//////////////////////////////////////////////
00003 
00004 class TUNGraph;
00005 class TBPGraph;
00006 //TODO:class TUNEGraph; -- undirected multigraph
00007 
00009 typedef TPt<TUNGraph> PUNGraph;
00011 typedef TPt<TBPGraph> PBPGraph;
00012 
00014 // Directed graphs
00015 class TNGraph;
00016 class TNEGraph;
00017 
00019 typedef TPt<TNGraph> PNGraph;
00021 typedef TPt<TNEGraph> PNEGraph;
00022 
00023 //#//////////////////////////////////////////////
00025 
00032 class TUNGraph {
00033 public:
00034   typedef TUNGraph TNet;
00035   typedef TPt<TUNGraph> PNet;
00036 public:
00037   class TNode {
00038   private:
00039     TInt Id;
00040     TIntV NIdV;
00041   public:
00042     TNode() : Id(-1), NIdV() { }
00043     TNode(const int& NId) : Id(NId), NIdV() { }
00044     TNode(const TNode& Node) : Id(Node.Id), NIdV(Node.NIdV) { }
00045     TNode(TSIn& SIn) : Id(SIn), NIdV(SIn) { }
00046     void Save(TSOut& SOut) const { Id.Save(SOut); NIdV.Save(SOut); }
00047     int GetId() const { return Id; }
00048     int GetDeg() const { return NIdV.Len(); }
00049     int GetInDeg() const { return GetDeg(); }
00050     int GetOutDeg() const { return GetDeg(); }
00051     int GetInNId(const int& NodeN) const { return GetNbrNId(NodeN); }
00052     int GetOutNId(const int& NodeN) const { return GetNbrNId(NodeN); }
00053     int GetNbrNId(const int& NodeN) const { return NIdV[NodeN]; }
00054     bool IsNbrNId(const int& NId) const { return NIdV.SearchBin(NId)!=-1; }
00055     bool IsInNId(const int& NId) const { return IsNbrNId(NId); }
00056     bool IsOutNId(const int& NId) const { return IsNbrNId(NId); }
00057     void PackOutNIdV() { NIdV.Pack(); }
00058     void PackNIdV() { NIdV.Pack(); }
00059     friend class TUNGraph;
00060     friend class TUNGraphMtx;
00061   };
00063   class TNodeI {
00064   private:
00065     typedef THash<TInt, TNode>::TIter THashIter;
00066     THashIter NodeHI;
00067   public:
00068     TNodeI() : NodeHI() { }
00069     TNodeI(const THashIter& NodeHIter) : NodeHI(NodeHIter) { }
00070     TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI) { }
00071     TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; return *this; }
00072 
00074     TNodeI& operator++ (int) { NodeHI++; return *this; }
00075 
00076     bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
00077     bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
00078 
00080     int GetId() const { return NodeHI.GetDat().GetId(); }
00082     int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
00084     int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
00086     int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
00088 
00091     int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }
00093 
00096     int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }
00098 
00101     int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
00103     bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
00105     bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
00107     bool IsNbrNId(const int& NId) const { return NodeHI.GetDat().IsNbrNId(NId); }
00108     friend class TUNGraph;
00109   };
00111   class TEdgeI {
00112   private:
00113     TNodeI CurNode, EndNode;
00114     int CurEdge;
00115   public:
00116     TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
00117     TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
00118     TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
00119     TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; } return *this; }
00121     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; }
00122     bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
00123     bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
00125     int GetId() const { return -1; }
00127     int GetSrcNId() const { return CurNode.GetId(); }
00129     int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
00130     friend class TUNGraph;
00131   };
00132 private:
00133   TCRef CRef;
00134   TInt MxNId, NEdges;
00135   THash<TInt, TNode> NodeH;
00136 private:
00137   TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
00138   const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
00139 public:
00140   TUNGraph() : CRef(), MxNId(0), NEdges(0), NodeH() { }
00142   explicit TUNGraph(const int& Nodes, const int& Edges) : MxNId(0), NEdges(0) { Reserve(Nodes, Edges); }
00143   TUNGraph(const TUNGraph& Graph) : MxNId(Graph.MxNId), NEdges(Graph.NEdges), NodeH(Graph.NodeH) { }
00145   TUNGraph(TSIn& SIn) : MxNId(SIn), NEdges(SIn), NodeH(SIn) { }
00147   void Save(TSOut& SOut) const { MxNId.Save(SOut); NEdges.Save(SOut); NodeH.Save(SOut); }
00149   static PUNGraph New() { return new TUNGraph(); }
00151 
00153   static PUNGraph New(const int& Nodes, const int& Edges) { return new TUNGraph(Nodes, Edges); }
00155   static PUNGraph Load(TSIn& SIn) { return PUNGraph(new TUNGraph(SIn)); }
00157   bool HasFlag(const TGraphFlag& Flag) const;
00158   TUNGraph& operator = (const TUNGraph& Graph) {
00159     if (this!=&Graph) { MxNId=Graph.MxNId; NEdges=Graph.NEdges; NodeH=Graph.NodeH; } return *this; }
00160   
00162   int GetNodes() const { return NodeH.Len(); }
00164 
00168   int AddNode(int NId = -1);
00170   int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId()); }
00172 
00181   int AddNode(const int& NId, const TIntV& NbrNIdV);
00183 
00191   int AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& NIdVId);
00193 
00195   void DelNode(const int& NId);
00197   void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
00199   bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
00201   TNodeI BegNI() const { return TNodeI(NodeH.BegI()); }
00203   TNodeI EndNI() const { return TNodeI(NodeH.EndI()); }
00205   TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId)); }
00207   int GetMxNId() const { return MxNId; }
00208 
00210   int GetEdges() const;
00212 
00216   int AddEdge(const int& SrcNId, const int& DstNId);
00218   int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
00220 
00223   void DelEdge(const int& SrcNId, const int& DstNId);
00225   bool IsEdge(const int& SrcNId, const int& DstNId) const;
00227   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; }
00229   TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
00231   TEdgeI GetEI(const int& EId) const;
00233 
00235   TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;
00236 
00238   int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
00240   TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
00242   void GetNIdV(TIntV& NIdV) const;
00243 
00245   bool Empty() const { return GetNodes()==0; }
00247   void Clr() { MxNId=0; NEdges=0; NodeH.Clr(); }
00249   void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) NodeH.Gen(Nodes/2); }
00251   void ReserveNIdDeg(const int& NId, const int& Deg) { GetNode(NId).NIdV.Reserve(Deg); }
00253 
00257   void Defrag(const bool& OnlyNodeLinks=false);
00259 
00261   bool IsOk(const bool& ThrowExcept=true) const;
00263   void Dump(FILE *OutF=stdout) const;
00265 
00271   static PUNGraph GetSmallGraph();
00272 
00273   friend class TUNGraphMtx;
00274   friend class TPt<TUNGraph>;
00275 };
00276 
00278 // Directed Node Graph
00279 
00281 
00295 class TNGraph {
00296 public:
00297   typedef TNGraph TNet;
00298   typedef TPt<TNGraph> PNet;
00299 public:
00300   class TNode {
00301   private:
00302     TInt Id;
00303     TIntV InNIdV, OutNIdV;
00304   public:
00305     TNode() : Id(-1), InNIdV(), OutNIdV() { }
00306     TNode(const int& NId) : Id(NId), InNIdV(), OutNIdV() { }
00307     TNode(const TNode& Node) : Id(Node.Id), InNIdV(Node.InNIdV), OutNIdV(Node.OutNIdV) { }
00308     TNode(TSIn& SIn) : Id(SIn), InNIdV(SIn), OutNIdV(SIn) { }
00309     void Save(TSOut& SOut) const { Id.Save(SOut); InNIdV.Save(SOut); OutNIdV.Save(SOut); }
00310     int GetId() const { return Id; }
00311     int GetDeg() const { return GetInDeg() + GetOutDeg(); }
00312     int GetInDeg() const { return InNIdV.Len(); }
00313     int GetOutDeg() const { return OutNIdV.Len(); }
00314     int GetInNId(const int& NodeN) const { return InNIdV[NodeN]; }
00315     int GetOutNId(const int& NodeN) const { return OutNIdV[NodeN]; }
00316     int GetNbrNId(const int& NodeN) const { return NodeN<GetOutDeg()?GetOutNId(NodeN):GetInNId(NodeN-GetOutDeg()); }
00317     bool IsInNId(const int& NId) const { return InNIdV.SearchBin(NId) != -1; }
00318     bool IsOutNId(const int& NId) const { return OutNIdV.SearchBin(NId) != -1; }
00319     bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
00320     void PackOutNIdV() { OutNIdV.Pack(); }
00321     void PackNIdV() { InNIdV.Pack(); }
00322     friend class TNGraph;
00323     friend class TNGraphMtx;
00324   };
00326   class TNodeI {
00327   private:
00328     typedef THash<TInt, TNode>::TIter THashIter;
00329     THashIter NodeHI;
00330   public:
00331     TNodeI() : NodeHI() { }
00332     TNodeI(const THashIter& NodeHIter) : NodeHI(NodeHIter) { }
00333     TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI) { }
00334     TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; return *this; }
00336     TNodeI& operator++ (int) { NodeHI++; return *this; }
00337     bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
00338     bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
00340     int GetId() const { return NodeHI.GetDat().GetId(); }
00342     int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
00344     int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
00346     int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
00348 
00350     int GetInNId(const int& NodeN) const { return NodeHI.GetDat().GetInNId(NodeN); }
00352 
00354     int GetOutNId(const int& NodeN) const { return NodeHI.GetDat().GetOutNId(NodeN); }
00356 
00358     int GetNbrNId(const int& NodeN) const { return NodeHI.GetDat().GetNbrNId(NodeN); }
00360     bool IsInNId(const int& NId) const { return NodeHI.GetDat().IsInNId(NId); }
00362     bool IsOutNId(const int& NId) const { return NodeHI.GetDat().IsOutNId(NId); }
00364     bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
00365     friend class TNGraph;
00366   };
00368   class TEdgeI {
00369   private:
00370     TNodeI CurNode, EndNode;
00371     int CurEdge;
00372   public:
00373     TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
00374     TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
00375     TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
00376     TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; }  return *this; }
00378     TEdgeI& operator++ (int) { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++;
00379       while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } }  return *this; }
00380     bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
00381     bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
00383     int GetId() const { return -1; }
00385     int GetSrcNId() const { return CurNode.GetId(); }
00387     int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
00388     friend class TNGraph;
00389   };
00390 private:
00391   TCRef CRef;
00392   TInt MxNId;
00393   THash<TInt, TNode> NodeH;
00394 private:
00395   TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
00396   const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
00397 public:
00398   TNGraph() : CRef(), MxNId(0), NodeH() { }
00400   explicit TNGraph(const int& Nodes, const int& Edges) : MxNId(0) { Reserve(Nodes, Edges); }
00401   TNGraph(const TNGraph& Graph) : MxNId(Graph.MxNId), NodeH(Graph.NodeH) { }
00403   TNGraph(TSIn& SIn) : MxNId(SIn), NodeH(SIn) { }
00405   void Save(TSOut& SOut) const { MxNId.Save(SOut); NodeH.Save(SOut); }
00407   static PNGraph New() { return new TNGraph(); }
00409 
00411   static PNGraph New(const int& Nodes, const int& Edges) { return new TNGraph(Nodes, Edges); }
00413   static PNGraph Load(TSIn& SIn) { return PNGraph(new TNGraph(SIn)); }
00415   bool HasFlag(const TGraphFlag& Flag) const;
00416   TNGraph& operator = (const TNGraph& Graph) {
00417     if (this!=&Graph) { MxNId=Graph.MxNId; NodeH=Graph.NodeH; }  return *this; }
00418   
00420   int GetNodes() const { return NodeH.Len(); }
00422 
00426   int AddNode(int NId = -1);
00428   int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId()); }
00430 
00439   int AddNode(const int& NId, const TIntV& InNIdV, const TIntV& OutNIdV);
00441 
00449   int AddNode(const int& NId, const TVecPool<TInt>& Pool, const int& SrcVId, const int& DstVId);
00451 
00453   void DelNode(const int& NId);
00455   void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
00457   bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
00459   TNodeI BegNI() const { return TNodeI(NodeH.BegI()); }
00461   TNodeI EndNI() const { return TNodeI(NodeH.EndI()); }
00463   TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId)); }
00464   // GetNodeC() has been commented out. It was a quick shortcut, do not use.
00465   //const TNode& GetNodeC(const int& NId) const { return NodeH.GetDat(NId); }
00467   int GetMxNId() const { return MxNId; }
00468 
00470   int GetEdges() const;
00472 
00478   int AddEdge(const int& SrcNId, const int& DstNId);
00480   int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
00482 
00486   void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
00488   bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const;
00490   TEdgeI BegEI() const { TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0){NI++;} return TEdgeI(NI, EndNI()); }
00492   TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
00494   TEdgeI GetEI(const int& EId) const; // not supported
00496   TEdgeI GetEI(const int& SrcNId, const int& DstNId) const;
00497 
00499   int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
00501   TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
00503   void GetNIdV(TIntV& NIdV) const;
00504 
00506   bool Empty() const { return GetNodes()==0; }
00508   void Clr() { MxNId=0; NodeH.Clr(); }
00510   void Reserve(const int& Nodes, const int& Edges) { if (Nodes>0) { NodeH.Gen(Nodes/2); } }
00512   void ReserveNIdInDeg(const int& NId, const int& InDeg) { GetNode(NId).InNIdV.Reserve(InDeg); }
00514   void ReserveNIdOutDeg(const int& NId, const int& OutDeg) { GetNode(NId).OutNIdV.Reserve(OutDeg); }
00516 
00521   void Defrag(const bool& OnlyNodeLinks=false);
00523 
00526   bool IsOk(const bool& ThrowExcept=true) const;
00528   void Dump(FILE *OutF=stdout) const;
00530 
00534   static PNGraph GetSmallGraph();
00535   friend class TPt<TNGraph>;
00536   friend class TNGraphMtx;
00537 };
00538 
00539 // set flags
00540 namespace TSnap {
00541 template <> struct IsDirected<TNGraph> { enum { Val = 1 }; };
00542 }
00543 
00545 // Node Edge Graph
00546 
00547 // TODO TNEGraph describe time complexity for basic operations
00549 
00556 class TNEGraph {
00557 public:
00558   typedef TNEGraph TNet;
00559   typedef TPt<TNEGraph> PNet;
00560 public:
00561   class TNode {
00562   private:
00563     TInt Id;
00564     TIntV InEIdV, OutEIdV;
00565   public:
00566     TNode() : Id(-1), InEIdV(), OutEIdV() { }
00567     TNode(const int& NId) : Id(NId), InEIdV(), OutEIdV() { }
00568     TNode(const TNode& Node) : Id(Node.Id), InEIdV(Node.InEIdV), OutEIdV(Node.OutEIdV) { }
00569     TNode(TSIn& SIn) : Id(SIn), InEIdV(SIn), OutEIdV(SIn) { }
00570     void Save(TSOut& SOut) const { Id.Save(SOut); InEIdV.Save(SOut); OutEIdV.Save(SOut); }
00571     int GetId() const { return Id; }
00572     int GetDeg() const { return GetInDeg() + GetOutDeg(); }
00573     int GetInDeg() const { return InEIdV.Len(); }
00574     int GetOutDeg() const { return OutEIdV.Len(); }
00575     int GetInEId(const int& EdgeN) const { return InEIdV[EdgeN]; }
00576     int GetOutEId(const int& EdgeN) const { return OutEIdV[EdgeN]; }
00577     int GetNbrEId(const int& EdgeN) const { return EdgeN<GetOutDeg()?GetOutEId(EdgeN):GetInEId(EdgeN-GetOutDeg()); }
00578     bool IsInEId(const int& EId) const { return InEIdV.SearchBin(EId) != -1; }
00579     bool IsOutEId(const int& EId) const { return OutEIdV.SearchBin(EId) != -1; }
00580     friend class TNEGraph;
00581   };
00582   class TEdge {
00583   private:
00584     TInt Id, SrcNId, DstNId;
00585   public:
00586     TEdge() : Id(-1), SrcNId(-1), DstNId(-1) { }
00587     TEdge(const int& EId, const int& SourceNId, const int& DestNId) : Id(EId), SrcNId(SourceNId), DstNId(DestNId) { }
00588     TEdge(const TEdge& Edge) : Id(Edge.Id), SrcNId(Edge.SrcNId), DstNId(Edge.DstNId) { }
00589     TEdge(TSIn& SIn) : Id(SIn), SrcNId(SIn), DstNId(SIn) { }
00590     void Save(TSOut& SOut) const { Id.Save(SOut); SrcNId.Save(SOut); DstNId.Save(SOut); }
00591     int GetId() const { return Id; }
00592     int GetSrcNId() const { return SrcNId; }
00593     int GetDstNId() const { return DstNId; }
00594     friend class TNEGraph;
00595   };
00597   class TNodeI {
00598   private:
00599     typedef THash<TInt, TNode>::TIter THashIter;
00600     THashIter NodeHI;
00601     const TNEGraph *Graph;
00602   public:
00603     TNodeI() : NodeHI(), Graph(NULL) { }
00604     TNodeI(const THashIter& NodeHIter, const TNEGraph* GraphPt) : NodeHI(NodeHIter), Graph(GraphPt) { }
00605     TNodeI(const TNodeI& NodeI) : NodeHI(NodeI.NodeHI), Graph(NodeI.Graph) { }
00606     TNodeI& operator = (const TNodeI& NodeI) { NodeHI = NodeI.NodeHI; Graph=NodeI.Graph; return *this; }
00608     TNodeI& operator++ (int) { NodeHI++; return *this; }
00609     bool operator < (const TNodeI& NodeI) const { return NodeHI < NodeI.NodeHI; }
00610     bool operator == (const TNodeI& NodeI) const { return NodeHI == NodeI.NodeHI; }
00612     int GetId() const { return NodeHI.GetDat().GetId(); }
00614     int GetDeg() const { return NodeHI.GetDat().GetDeg(); }
00616     int GetInDeg() const { return NodeHI.GetDat().GetInDeg(); }
00618     int GetOutDeg() const { return NodeHI.GetDat().GetOutDeg(); }
00620 
00622     int GetInNId(const int& EdgeN) const { return Graph->GetEdge(NodeHI.GetDat().GetInEId(EdgeN)).GetSrcNId(); }
00624 
00626     int GetOutNId(const int& EdgeN) const { return Graph->GetEdge(NodeHI.GetDat().GetOutEId(EdgeN)).GetDstNId(); }
00628 
00630     int GetNbrNId(const int& EdgeN) const { const TEdge& E = Graph->GetEdge(NodeHI.GetDat().GetNbrEId(EdgeN));
00631       return GetId()==E.GetSrcNId() ? E.GetDstNId():E.GetSrcNId(); }
00633     bool IsInNId(const int& NId) const;
00635     bool IsOutNId(const int& NId) const;
00637     bool IsNbrNId(const int& NId) const { return IsOutNId(NId) || IsInNId(NId); }
00638     // edges
00640     int GetInEId(const int& EdgeN) const { return NodeHI.GetDat().GetInEId(EdgeN); }
00642     int GetOutEId(const int& EdgeN) const { return NodeHI.GetDat().GetOutEId(EdgeN); }
00644     int GetNbrEId(const int& EdgeN) const { return NodeHI.GetDat().GetNbrEId(EdgeN); }
00646     bool IsInEId(const int& EId) const { return NodeHI.GetDat().IsInEId(EId); }
00648     bool IsOutEId(const int& EId) const { return NodeHI.GetDat().IsOutEId(EId); }
00650     bool IsNbrEId(const int& EId) const { return IsInEId(EId) || IsOutEId(EId); }
00651     friend class TNEGraph;
00652   };
00654   class TEdgeI {
00655   private:
00656     typedef THash<TInt, TEdge>::TIter THashIter;
00657     THashIter EdgeHI;
00658     const TNEGraph *Graph;
00659   public:
00660     TEdgeI() : EdgeHI(), Graph(NULL) { }
00661     TEdgeI(const THashIter& EdgeHIter, const TNEGraph *GraphPt) : EdgeHI(EdgeHIter), Graph(GraphPt) { }
00662     TEdgeI(const TEdgeI& EdgeI) : EdgeHI(EdgeI.EdgeHI), Graph(EdgeI.Graph) { }
00663     TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { EdgeHI=EdgeI.EdgeHI; Graph=EdgeI.Graph; }  return *this; }
00665     TEdgeI& operator++ (int) { EdgeHI++; return *this; }
00666     bool operator < (const TEdgeI& EdgeI) const { return EdgeHI < EdgeI.EdgeHI; }
00667     bool operator == (const TEdgeI& EdgeI) const { return EdgeHI == EdgeI.EdgeHI; }
00669     int GetId() const { return EdgeHI.GetDat().GetId(); }
00671     int GetSrcNId() const { return EdgeHI.GetDat().GetSrcNId(); }
00673     int GetDstNId() const { return EdgeHI.GetDat().GetDstNId(); }
00674     friend class TNEGraph;
00675   };
00676 
00677 private:
00678   TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
00679   const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
00680   TEdge& GetEdge(const int& EId) { return EdgeH.GetDat(EId); }
00681   const TEdge& GetEdge(const int& EId) const { return EdgeH.GetDat(EId); }
00682 private:
00683   TCRef CRef;
00684   TInt MxNId, MxEId;
00685   THash<TInt, TNode> NodeH;
00686   THash<TInt, TEdge> EdgeH;
00687 public:
00688   TNEGraph() : CRef(), MxNId(0), MxEId(0) { }
00690   explicit TNEGraph(const int& Nodes, const int& Edges) : CRef(), MxNId(0), MxEId(0) { Reserve(Nodes, Edges); }
00691   TNEGraph(const TNEGraph& Graph) : MxNId(Graph.MxNId), MxEId(Graph.MxEId), NodeH(Graph.NodeH), EdgeH(Graph.EdgeH) { }
00693   TNEGraph(TSIn& SIn) : MxNId(SIn), MxEId(SIn), NodeH(SIn), EdgeH(SIn) { }
00695   void Save(TSOut& SOut) const { MxNId.Save(SOut); MxEId.Save(SOut); NodeH.Save(SOut); EdgeH.Save(SOut); }
00697   static PNEGraph New() { return PNEGraph(new TNEGraph()); }
00699 
00701   static PNEGraph New(const int& Nodes, const int& Edges) { return PNEGraph(new TNEGraph(Nodes, Edges)); }
00703   static PNEGraph Load(TSIn& SIn) { return PNEGraph(new TNEGraph(SIn)); }
00705   bool HasFlag(const TGraphFlag& Flag) const;
00706   TNEGraph& operator = (const TNEGraph& Graph) { if (this!=&Graph) {
00707     MxNId=Graph.MxNId; MxEId=Graph.MxEId; NodeH=Graph.NodeH; EdgeH=Graph.EdgeH; }  return *this; }
00708 
00710   int GetNodes() const { return NodeH.Len(); }
00712 
00716   int AddNode(int NId = -1);
00718   int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId()); }
00720 
00722   void DelNode(const int& NId);
00724   void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
00726   bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
00728   TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); }
00730   TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); }
00732   TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); }
00734   int GetMxNId() const { return MxNId; }
00735 
00737   int GetEdges() const { return EdgeH.Len(); }
00739 
00744   int AddEdge(const int& SrcNId, const int& DstNId, int EId  = -1);
00746   int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI.GetId()); }
00748   void DelEdge(const int& EId);
00750 
00754   void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
00756   bool IsEdge(const int& EId) const { return EdgeH.IsKey(EId); }
00758   bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const { int EId; return IsEdge(SrcNId, DstNId, EId, IsDir); }
00760   bool IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir = true) const;
00762   int GetEId(const int& SrcNId, const int& DstNId) const { int EId; return IsEdge(SrcNId, DstNId, EId)?EId:-1; }
00764   TEdgeI BegEI() const { return TEdgeI(EdgeH.BegI(), this); }
00766   TEdgeI EndEI() const { return TEdgeI(EdgeH.EndI(), this); }
00767   // TODO document TNEGraph::GetEI()
00768   TEdgeI GetEI(const int& EId) const { return TEdgeI(EdgeH.GetI(EId), this); }
00769   // TODO document TNEGraph::GetEI()
00770   TEdgeI GetEI(const int& SrcNId, const int& DstNId) const { return GetEI(GetEId(SrcNId, DstNId)); }
00771 
00773   int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
00775   TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
00777   int GetRndEId(TRnd& Rnd=TInt::Rnd) { return EdgeH.GetKey(EdgeH.GetRndKeyId(Rnd, 0.8)); }
00779   TEdgeI GetRndEI(TRnd& Rnd=TInt::Rnd) { return GetEI(GetRndEId(Rnd)); }
00781   void GetNIdV(TIntV& NIdV) const;
00783   void GetEIdV(TIntV& EIdV) const;
00784 
00786   bool Empty() const { return GetNodes()==0; }
00788   void Clr() { MxNId=0; MxEId=0; NodeH.Clr(); EdgeH.Clr(); }
00790   void Reserve(const int& Nodes, const int& Edges) {
00791     if (Nodes>0) { NodeH.Gen(Nodes/2); } if (Edges>0) { EdgeH.Gen(Edges/2); } }
00793 
00798   void Defrag(const bool& OnlyNodeLinks=false);
00800 
00803   bool IsOk(const bool& ThrowExcept=true) const;
00805   void Dump(FILE *OutF=stdout) const;
00806   // TODO implement and document TNEGraph::GetSmallGraph()
00807   static PNEGraph GetSmallGraph();
00808   friend class TPt<TNEGraph>;
00809 };
00810 
00811 // set flags
00812 namespace TSnap {
00813 template <> struct IsMultiGraph<TNEGraph> { enum { Val = 1 }; };
00814 template <> struct IsDirected<TNEGraph> { enum { Val = 1 }; };
00815 }
00816 
00817 //#//////////////////////////////////////////////
00819 
00820 class TBPGraph {
00821 public:
00822   typedef TBPGraph TNet;
00823   typedef TPt<TBPGraph> PNet;
00824   typedef enum { bgsUndef, bgsLeft, bgsRight, bgsBoth } TNodeTy; // left or right hand side node
00825 public:
00826   class TNode {
00827   private:
00828     TInt Id;
00829     TIntV NIdV;
00830     TNodeTy NodeTy; // remove
00831   public:
00832     TNode() : Id(-1), NIdV(), NodeTy(bgsUndef) { }
00833     TNode(const int& NId) : Id(NId), NIdV(), NodeTy(true?bgsLeft:bgsRight) { }
00834     TNode(const TNode& Node) : Id(Node.Id), NIdV(Node.NIdV), NodeTy(Node.NodeTy) { }
00835     TNode(TSIn& SIn) : Id(SIn), NIdV(SIn), NodeTy(bgsUndef) { TInt Ty(SIn); NodeTy=(TNodeTy)Ty.Val; }
00836     void Save(TSOut& SOut) const { Id.Save(SOut); NIdV.Save(SOut); TInt(NodeTy).Save(SOut); }
00837     int GetId() const { return Id; }
00838     int GetDeg() const { return NIdV.Len(); }
00839     int GetInDeg() const { return GetDeg(); }
00840     int GetOutDeg() const { return GetDeg(); }
00841     int GetInNId(const int& NodeN) const { return GetNbrNId(NodeN); }
00842     int GetOutNId(const int& NodeN) const { return GetNbrNId(NodeN); }
00843     int GetNbrNId(const int& NodeN) const { return NIdV[NodeN]; }
00844     bool IsNbrNId(const int& NId) const { return NIdV.SearchBin(NId)!=-1; }
00845     bool IsInNId(const int& NId) const { return IsNbrNId(NId); }
00846     bool IsOutNId(const int& NId) const { return IsNbrNId(NId); }
00847     void PackOutNIdV() { NIdV.Pack(); }
00848     void PackNIdV() { NIdV.Pack(); }
00849     friend class TBPGraph;
00850   };
00852   class TNodeI {
00853   private:
00854     typedef THash<TInt, TNode>::TIter THashIter;
00855     THashIter LeftHI, RightHI; // iterator over left and right hand-side nodes
00856   private:
00857     inline THashIter HI() const { return ! LeftHI.IsEnd()?LeftHI:RightHI; }
00858   public:
00859     TNodeI() : LeftHI(), RightHI() { }
00860     TNodeI(const THashIter& LeftHIter, const THashIter& RightHIter) : LeftHI(LeftHIter), RightHI(RightHIter) { }
00861     TNodeI(const TNodeI& NodeI) : LeftHI(NodeI.LeftHI), RightHI(NodeI.RightHI) { }
00862     TNodeI& operator = (const TNodeI& NodeI) { LeftHI = NodeI.LeftHI; RightHI=NodeI.RightHI; return *this; }
00864     TNodeI& operator++ (int) { 
00865       if (! LeftHI.IsEnd()) { 
00866         LeftHI++; } 
00867       else if (! RightHI.IsEnd()) { 
00868         RightHI++; } 
00869       return *this; }
00870     bool operator < (const TNodeI& NodeI) const { return LeftHI < NodeI.LeftHI || (LeftHI==NodeI.LeftHI && RightHI < NodeI.RightHI); }
00871     bool operator == (const TNodeI& NodeI) const { return LeftHI==NodeI.LeftHI && RightHI==NodeI.RightHI; }
00873     int GetId() const { return HI().GetDat().GetId(); }
00875     bool IsLeft() const { return ! LeftHI.IsEnd(); }
00877     bool IsRight() const { return ! IsLeft(); }
00879     int GetDeg() const { return HI().GetDat().GetDeg(); }
00881     int GetInDeg() const { return HI().GetDat().GetInDeg(); }
00883     int GetOutDeg() const { return HI().GetDat().GetOutDeg(); }
00885 
00886     int GetInNId(const int& NodeN) const { return HI().GetDat().GetInNId(NodeN); }
00888 
00889     int GetOutNId(const int& NodeN) const { return HI().GetDat().GetOutNId(NodeN); }
00891 
00892     int GetNbrNId(const int& NodeN) const { return HI().GetDat().GetNbrNId(NodeN); }
00894     bool IsInNId(const int& NId) const { return HI().GetDat().IsInNId(NId); }
00896     bool IsOutNId(const int& NId) const { return HI().GetDat().IsOutNId(NId); }
00898     bool IsNbrNId(const int& NId) const { return HI().GetDat().IsNbrNId(NId); }
00899     friend class TBPGraph;
00900   };
00902   class TEdgeI {
00903   private:
00904     TNodeI CurNode, EndNode; // end node on the 'left'
00905     int CurEdge;
00906   public:
00907     TEdgeI() : CurNode(), EndNode(), CurEdge(0) { }
00908     TEdgeI(const TNodeI& NodeI, const TNodeI& EndNodeI, const int& EdgeN=0) : CurNode(NodeI), EndNode(EndNodeI), CurEdge(EdgeN) { }
00909     TEdgeI(const TEdgeI& EdgeI) : CurNode(EdgeI.CurNode), EndNode(EdgeI.EndNode), CurEdge(EdgeI.CurEdge) { }
00910     TEdgeI& operator = (const TEdgeI& EdgeI) { if (this!=&EdgeI) { CurNode=EdgeI.CurNode; EndNode=EdgeI.EndNode; CurEdge=EdgeI.CurEdge; }  return *this; }
00912     TEdgeI& operator++ (int) { CurEdge++; if (CurEdge >= CurNode.GetOutDeg()) { CurEdge=0; CurNode++;
00913       while (CurNode < EndNode && CurNode.GetOutDeg()==0) { CurNode++; } }  return *this; }
00914     bool operator < (const TEdgeI& EdgeI) const { return CurNode<EdgeI.CurNode || (CurNode==EdgeI.CurNode && CurEdge<EdgeI.CurEdge); }
00915     bool operator == (const TEdgeI& EdgeI) const { return CurNode == EdgeI.CurNode && CurEdge == EdgeI.CurEdge; }
00917     int GetId() const { return -1; }
00919     int GetSrcNId() const { return CurNode.GetId(); }
00921     int GetDstNId() const { return CurNode.GetOutNId(CurEdge); }
00923     int GetLNId() const { return GetSrcNId(); }
00925     int GetRNId() const { return GetDstNId(); }
00926     friend class TBPGraph;
00927   };
00928 private:
00929   TCRef CRef;
00930   TInt MxNId;                 // maximum node id in the graph
00931   THash<TInt, TNode> LeftH;   // 'left' nodes
00932   THash<TInt, TNode> RightH;  // 'right' nodes
00933 private:
00934   //TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
00935   //const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
00936 public:
00937   TBPGraph() : CRef(), MxNId(0), LeftH(), RightH() { }
00939   explicit TBPGraph(const int& Nodes, const int& Edges) : MxNId(0) { } 
00940   TBPGraph(const TBPGraph& BPGraph) : MxNId(BPGraph.MxNId), LeftH(BPGraph.LeftH), RightH(BPGraph.RightH) { }
00942   TBPGraph(TSIn& SIn) : MxNId(SIn), LeftH(SIn), RightH(SIn) { }
00944   void Save(TSOut& SOut) const { MxNId.Save(SOut); LeftH.Save(SOut); RightH.Save(SOut); }
00946   static PBPGraph New() { return new TBPGraph(); }
00948 
00949   static PBPGraph New(const int& Nodes, const int& Edges) { return new TBPGraph(Nodes, Edges); }
00951   static PBPGraph Load(TSIn& SIn) { return PBPGraph(new TBPGraph(SIn)); }
00953   bool HasFlag(const TGraphFlag& Flag) const;
00954   TBPGraph& operator = (const TBPGraph& BPGraph) {
00955     if (this!=&BPGraph) { MxNId=BPGraph.MxNId; LeftH=BPGraph.LeftH; RightH=BPGraph.RightH; }  return *this; }
00956   
00958   int GetNodes() const { return GetLNodes() + GetRNodes(); }
00960   int GetLNodes() const { return LeftH.Len(); }
00962   int GetRNodes() const { return RightH.Len(); }
00964 
00965   int AddNode(int NId = -1, const bool& LeftNode=true);
00967   int AddNode(const TNodeI& NodeI) { return AddNode(NodeI.GetId(), NodeI.IsLeft()); }
00969 
00970   void DelNode(const int& NId);
00972   void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
00974   bool IsNode(const int& NId) const { return IsLNode(NId) || IsRNode(NId); }
00976   bool IsLNode(const int& NId) const { return LeftH.IsKey(NId); }
00978   bool IsRNode(const int& NId) const { return RightH.IsKey(NId); }
00980   int GetMxNId() const { return MxNId; }
00981     
00983   TNodeI BegNI() const { return TNodeI(LeftH.BegI(), RightH.BegI()); }
00985   TNodeI EndNI() const { return TNodeI(LeftH.EndI(), RightH.EndI()); }
00987   TNodeI GetNI(const int& NId) const { return IsLNode(NId) ? TNodeI(LeftH.GetI(NId), RightH.EndI()) : TNodeI(LeftH.EndI(), RightH.GetI(NId)); }
00989   TNodeI BegLNI() const { return TNodeI(LeftH.BegI(), RightH.EndI()); }
00991   TNodeI EndLNI() const { return EndNI(); }
00993   TNodeI BegRNI() const { return TNodeI(LeftH.EndI(), RightH.BegI()); }
00995   TNodeI EndRNI() const { return EndNI(); }
00996 
00998   int GetEdges() const;
01000 
01001   int AddEdge(const int& LeftNId, const int& RightNId);
01003   int AddEdge(const TEdgeI& EdgeI) { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
01005 
01006   void DelEdge(const int& LeftNId, const int& RightNId);
01008   bool IsEdge(const int& LeftNId, const int& RightNId) const;
01010   TEdgeI BegEI() const { TNodeI NI=BegLNI(); while (NI<EndLNI() && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { NI++; } return TEdgeI(NI, EndLNI()); }
01012   TEdgeI EndEI() const { return TEdgeI(EndNI(), EndNI()); }
01014   TEdgeI GetEI(const int& EId) const;
01016 
01017   TEdgeI GetEI(const int& LeftNId, const int& RightNId) const;
01018     
01020   int GetRndNId(TRnd& Rnd=TInt::Rnd);
01022   int GetRndLNId(TRnd& Rnd=TInt::Rnd);
01024   int GetRndRNId(TRnd& Rnd=TInt::Rnd);
01026   TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
01028   void GetNIdV(TIntV& NIdV) const;
01030   void GetLNIdV(TIntV& NIdV) const;
01032   void GetRNIdV(TIntV& NIdV) const;
01033 
01035   bool Empty() const { return GetNodes()==0; }
01037   void Clr() { MxNId=0; LeftH.Clr(); RightH.Clr(); }
01039   void Reserve(const int& Nodes, const int& Edges);
01041 
01042   void Defrag(const bool& OnlyNodeLinks=false);
01044 
01045   bool IsOk(const bool& ThrowExcept=true) const;
01047   void Dump(FILE *OutF=stdout) const;
01049 
01050   static PBPGraph GetSmallGraph();
01051 
01052   friend class TPt<TBPGraph>;
01053 };
01054 
01055 // set flags
01056 namespace TSnap {
01057 template <> struct IsBipart<TBPGraph> { enum { Val = 1 }; };
01058 }