Snap算法学习01-03Snap中的类及其定义

//graph.h定义的基本类型

无向图  

/// Undirected graph. ##TUNGraph::Class
class TUNGraph

有向图

/// Directed graph. ##TNGraph::Class
class TNGraph

二部图

/// Bipartite graph. ##Bipartite_graph
class TBPGraph

多重图

/// Directed multigraph. ##TNEGraph::Class
class TNEGraph

 下面以多重图为例查看类型  

  1 class TNEGraph   
  2 public:  
  3 typedef TNEGraph TNet; 
  4   typedef TPt<TNEGraph> PNet;
  5 public:
  6   class TNode  {//节点类型定义；并friend class TNEGraph}；
  7   class TEdge  {//边的类型定义；并friend class TNEGraph}；
  8   class TNodeI {//节点迭代器类型定义；并友元TNEGraph }；
  9   class TEdgeI {//边迭代器类型定义；并友元TNEGraph }；
 10 private:
 11   TNode& GetNode(const int& NId) { return NodeH.GetDat(NId); }
 12   const TNode& GetNode(const int& NId) const { return NodeH.GetDat(NId); }
 13   TEdge& GetEdge(const int& EId) { return EdgeH.GetDat(EId); }
 14   const TEdge& GetEdge(const int& EId) const { return EdgeH.GetDat(EId); }
 15 private:
 16   TCRef CRef;
 17   TInt MxNId, MxEId;
 18   THash<TInt, TNode> NodeH;
 19   THash<TInt, TEdge> EdgeH;
 20 public:
 21   TNEGraph() : CRef(), MxNId(0), MxEId(0) { }
 22   /// Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.
 23   explicit TNEGraph(const int& Nodes, const int& Edges) : CRef(), MxNId(0), MxEId(0) 
        { Reserve(Nodes, Edges); }
 24   TNEGraph(const TNEGraph& Graph) : 
        MxNId(Graph.MxNId), MxEId(Graph.MxEId), NodeH(Graph.NodeH), EdgeH(Graph.EdgeH) { }
 25   /// Constructor for loading the graph from a (binary) stream SIn.
 26   TNEGraph(TSIn& SIn) : MxNId(SIn), MxEId(SIn), NodeH(SIn), EdgeH(SIn) { }
 27   /// Saves the graph to a (binary) stream SOut.
 28   void Save(TSOut& SOut) const
      { MxNId.Save(SOut); MxEId.Save(SOut); NodeH.Save(SOut); EdgeH.Save(SOut);}
 29   /// Static constructor that returns a pointer to the graph. 
      ///Call: PNEGraph Graph = TNEGraph::New().
 30   static PNEGraph New() { return PNEGraph(new TNEGraph()); }
 31   /// Static constructor that returns a pointer to the graph and reserves enough memory for
      ///memory for Nodes nodes and Edges edges. ##TNEGraph::New 
 32 static PNEGraph New(const int& Nodes, const int& Edges)
     { return PNEGraph(new TNEGraph(Nodes, Edges));}
 33 // Static constructor that loads the graph from a stream SIn and returns a pointer to it.

 34   static PNEGraph Load(TSIn& SIn) { return PNEGraph(new TNEGraph(SIn)); }
 35   /// Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
 36   bool HasFlag(const TGraphFlag& Flag) const;
 37   TNEGraph& operator = (const TNEGraph& Graph) { if (this!=&Graph) {
 38     MxNId=Graph.MxNId; MxEId=Graph.MxEId; NodeH=Graph.NodeH; EdgeH=Graph.EdgeH; }
        return *this; }
 39 
 40   /// Returns the number of nodes in the graph.
 41   int GetNodes() const { return NodeH.Len(); }
 42   /// Adds a node of ID NId to the graph. ##TNEGraph::AddNode
 43   int AddNode(int NId = -1);
 44   /// Adds a node of ID NodeI.GetId() to the graph.
 45   int AddNode(const TNodeI& NodeId) { return AddNode(NodeId.GetId()); }
 46   /// Deletes node of ID NId from the graph. ##TNEGraph::DelNode
 47   void DelNode(const int& NId);
 48   /// Deletes node of ID NodeI.GetId() from the graph.
 49   void DelNode(const TNode& NodeI) { DelNode(NodeI.GetId()); }
 50   /// Tests whether ID NId is a node.
 51   bool IsNode(const int& NId) const { return NodeH.IsKey(NId); }
 52   /// Returns an iterator referring to the first node in the graph.
 53   TNodeI BegNI() const { return TNodeI(NodeH.BegI(), this); }
 54   /// Returns an iterator referring to the past-the-end node in the graph.
 55   TNodeI EndNI() const { return TNodeI(NodeH.EndI(), this); }
 56   /// Returns an iterator referring to the node of ID NId in the graph.
 57   TNodeI GetNI(const int& NId) const { return TNodeI(NodeH.GetI(NId), this); }
 58   /// Returns an ID that is larger than any node ID in the graph.
 59   int GetMxNId() const { return MxNId; }
 60 
 61   /// Returns the number of edges in the graph.
 62   int GetEdges() const { return EdgeH.Len(); }
 63   /// Adds an edge with ID EId between node IDs SrcNId and DstNId to the graph.
      /// ##TNEGraph::AddEdge
 64   int AddEdge(const int& SrcNId, const int& DstNId, int EId  = -1);
 65   /// Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
 66   int AddEdge(const TEdgeI& EdgeI) 
       { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), EdgeI.GetId()); }
 67   /// Deletes an edge with edge ID EId from the graph.
 68   void DelEdge(const int& EId);
 69   /// Deletes all edges between node IDs SrcNId and DstNId from the graph. 
      ///##TNEGraph::DelEdge
 70   void DelEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true);
 71   /// Tests whether an edge with edge ID EId exists in the graph.
 72   bool IsEdge(const int& EId) const { return EdgeH.IsKey(EId); }
 73   /// Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
 74   bool IsEdge(const int& SrcNId, const int& DstNId, const bool& IsDir = true) const 
        { int EId; return IsEdge(SrcNId, DstNId, EId, IsDir); }
 75   /// Tests whether an edge between node IDs SrcNId and DstNId exists in the graph. 
      /// if an edge exists, return its edge ID in EId
 76   bool IsEdge(const int& SrcNId, const int& DstNId, int& EId, const bool& IsDir = true)
         const;
 77   /// Returns an edge ID between node IDs SrcNId and DstNId, 
      /// if such an edge exists. Otherwise, return -1.
 78   int GetEId(const int& SrcNId, const int& DstNId) const 
        { int EId; return IsEdge(SrcNId, DstNId, EId)?EId:-1; }
 79   /// Returns an iterator referring to the first edge in the graph.
 80   TEdgeI BegEI() const { return TEdgeI(EdgeH.BegI(), this); }
 81   /// Returns an iterator referring to the past-the-end edge in the graph.
 82   TEdgeI EndEI() const { return TEdgeI(EdgeH.EndI(), this); }
 83   /// Returns an iterator referring to edge with edge ID EId. 
 84   TEdgeI GetEI(const int& EId) const { return TEdgeI(EdgeH.GetI(EId), this); }
 85   /// Returns an iterator referring to edge (SrcNId, DstNId) in the graph. 
 86   TEdgeI GetEI(const int& SrcNId, const int& DstNId) const 
       { return GetEI(GetEId(SrcNId, DstNId)); }
 87 
 88   /// Returns an ID of a random node in the graph.
 89   int GetRndNId(TRnd& Rnd=TInt::Rnd) { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
 90   /// Returns an interator referring to a random node in the graph.
 91   TNodeI GetRndNI(TRnd& Rnd=TInt::Rnd) { return GetNI(GetRndNId(Rnd)); }
 92   /// Returns an ID of a random edge in the graph.
 93   int GetRndEId(TRnd& Rnd=TInt::Rnd) { return EdgeH.GetKey(EdgeH.GetRndKeyId(Rnd, 0.8)); }
 94   /// Returns an interator referring to a random edge in the graph.
 95   TEdgeI GetRndEI(TRnd& Rnd=TInt::Rnd) { return GetEI(GetRndEId(Rnd)); }
 96   /// Gets a vector IDs of all nodes in the graph.
 97   void GetNIdV(TIntV& NIdV) const;
 98   /// Gets a vector IDs of all edges in the graph.
 99   void GetEIdV(TIntV& EIdV) const;
100 
101   /// Tests whether the graph is empty (has zero nodes).
102   bool Empty() const { return GetNodes()==0; }
103   /// Deletes all nodes and edges from the graph.
104   void Clr() { MxNId=0; MxEId=0; NodeH.Clr(); EdgeH.Clr(); }
105   /// Reserves memory for a graph of Nodes nodes and Edges edges.
106   void Reserve(const int& Nodes, const int& Edges) {
107     if (Nodes>0) { NodeH.Gen(Nodes/2); } if (Edges>0) { EdgeH.Gen(Edges/2); } }
108   /// Defragments the graph. ##TNEGraph::Defrag
109   void Defrag(const bool& OnlyNodeLinks=false);
110   /// Checks the graph data structure for internal consistency. ##TNEGraph::IsOk
111   bool IsOk(const bool& ThrowExcept=true) const;
112   /// Print the graph in a human readable form to an output stream OutF.
113   void Dump(FILE *OutF=stdout) const;
114   /// Returns a small multigraph on 5 nodes and 6 edges. ##TNEGraph::GetSmallGraph
115   static PNEGraph GetSmallGraph();
116   friend class TPt<TNEGraph>;
117 };
118 
119 // set flags
120 namespace TSnap {
121 template <> struct IsMultiGraph<TNEGraph> { enum { Val = 1 }; };
122 template <> struct IsDirected<TNEGraph> { enum { Val = 1 }; };
123 }