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 }

 1 // 图中无向边计数
 2 // Counts unique undirected edges in the graph  //不考虑多重边
 3 template <class PGraph>
 4 int CntUniqUndirEdges(const PGraph& Graph) {
 5   TIntSet NbrSet;
 6   TIntSet SelfNbrSet;
 7   int Cnt = 0;
 8   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
 9     NbrSet.Clr(false);
10     for (int e = 0; e < NI.GetDeg(); e++) { // unique neighbors of a node
11       const int NbrId = NI.GetNbrNId(e);
12       if (NbrId == NI.GetId()) { // remember self-edges
13         SelfNbrSet.AddKey(NbrId);
14       } else {
15         NbrSet.AddKey(NbrId);
16       }
17     }
18     Cnt += NbrSet.Len();
19   }
20   // OP RS 2014/06/11 self-edges are currently not used 
21   //return Cnt / 2 + SelfNbrSet.Len();
22   return Cnt / 2;
23 }

 1 //图中有向边计数
 2 template <class PGraph>
 3 int CntUniqDirEdges(const PGraph& Graph) {
 4   TIntSet NbrSet;
 5   int Cnt = 0;
 6   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
 7     NbrSet.Clr(false);
 8     for (int e = 0; e < NI.GetOutDeg(); e++) { // unique out-neighbors of a node
 9       if (NI.GetOutNId(e) != NI.GetId()) { // skip self-edges
10         NbrSet.AddKey(NI.GetOutNId(e)); }
11     }
12     Cnt += NbrSet.Len();
13   }
14   return Cnt;
15 }

 1 template <class PGraph>
 2 int CntUniqBiDirEdges(const PGraph& Graph) {
 3   if (! Graph->HasFlag(gfDirected)) { // graph is undirected
 4     return CntUniqUndirEdges(Graph);  // then every edge is bi-directional
 5   }
 6   TIntSet NbrSet;
 7   int Cnt = 0;
 8   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
 9     const int SrcId = NI.GetId();
10     for (int e = 0; e < NI.GetOutDeg(); e++) {
11       const int DstId = NI.GetOutNId(e);
12       if (DstId <= SrcId) { continue; } // count each un-dir edge only once
13       if (Graph->IsEdge(DstId, SrcId)) { Cnt++; }
14     }
15   }
16   return Cnt;
17 }