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 }