Snap算法学习01-01关于节点及边的操作

 1 // 对图中节点进行遍历,找出入度数与指定值相等的节点个数
 2 // Returns the number of nodes with in-degree NodeInDeg
 3 template <class PGraph>
 4 int CntInDegNodes(const PGraph& Graph, const int& NodeInDeg) {
 5   int Cnt = 0;
 6   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
 7     if (NI.GetInDeg() == NodeInDeg) Cnt++;
 8   }
 9   return Cnt;
10 }

 1 // 指定节点NId与节点集合NodeSet中各点之间的存在边的数量
 2 // Returns the number of nodes in NodeSet that have an edge to the node NId.
 3 template <class PGraph>
 4 int CntEdgesToSet(const PGraph& Graph, const int& NId, const TIntSet& NodeSet) {
 5   if (! Graph->IsNode(NId)) { return 0; }
 6   const bool IsDir = Graph->HasFlag(gfDirected);
 7   const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
 8   if (! IsDir) {
 9     int EdgesToSet = 0;
10     for (int e = 0; e < NI.GetOutDeg(); e++) {
11       if (NodeSet.IsKey(NI.GetOutNId(e))) { EdgesToSet++; } }
12     return EdgesToSet;
13   } else {
14     TIntSet Set(NI.GetDeg());
15     for (int e = 0; e < NI.GetOutDeg(); e++) {
16       if (NodeSet.IsKey(NI.GetOutNId(e))) { Set.AddKey(NI.GetOutNId(e)); } }
17     for (int e = 0; e < NI.GetInDeg(); e++) {
18       if (NodeSet.IsKey(NI.GetInNId(e))) { Set.AddKey(NI.GetInNId(e)); } }
19     return Set.Len();
20   }
21 }

 1 // 找出拥有最大度数的若干节点，并从中随机选取一个节点作为返回值。
 2 // Returns a randomly chosen node from all the nodes with the maximum degree.
 3 template <class PGraph>
 4 int GetMxDegNId(const PGraph& Graph) {
 5   TIntV MxDegV;
 6   int MxDeg=-1;
 7   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
 8     if (MxDeg < NI.GetDeg()) { MxDegV.Clr(); MxDeg = NI.GetDeg(); }
 9     if (MxDeg == NI.GetDeg()) { MxDegV.Add(NI.GetId()); }
10   }
11   EAssertR(! MxDegV.Empty(), "Input graph is empty!");
12   return MxDegV[TInt::Rnd.GetUniDevInt(MxDegV.Len())];
13 }

1 // 获取每个节点及其度数
2 // Returns a vector of pairs ：(node id, node in-degree)
3 template <class PGraph>
4 void GetNodeInDegV(const PGraph& Graph, TIntPrV& NIdInDegV) {
5   NIdInDegV.Reserve(Graph->GetNodes(), 0);
6   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
7     NIdInDegV.Add(TIntPr(NI.GetId(), NI.GetInDeg()));
8   }
9 }

1 template <class PGraph>
2 void GetNodeOutDegV(const PGraph& Graph, TIntPrV& NIdOutDegV) {
3   NIdOutDegV.Reserve(Graph->GetNodes(), 0);
4   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
5     NIdOutDegV.Add(TIntPr(NI.GetId(), NI.GetOutDeg()));
6   }
7 }