SNAP Library 3.0, User Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | List of all members
TCliqueOverlap Class Reference

#include <cliques.h>

Public Member Functions

 TCliqueOverlap ()
 
void GetMaximalCliques (const PUNGraph &G, int MinMaxCliqueSize, TVec< TIntV > &MaxCliques)
 

Static Public Member Functions

static void GetRelativeComplement (const THashSet< TInt > &A, const THashSet< TInt > &B, THashSet< TInt > &Complement)
 
static void GetIntersection (const THashSet< TInt > &A, const THashSet< TInt > &B, THashSet< TInt > &C)
 
static int Intersection (const THashSet< TInt > &A, const THashSet< TInt > &B)
 
static void CalculateOverlapMtx (const TVec< TIntV > &MaxCliques, int MinNodeOverlap, TVec< TIntV > &OverlapMtx)
 
static PUNGraph CalculateOverlapMtx (const TVec< TIntV > &MaxCliques, int MinNodeOverlap)
 
static void GetOverlapCliques (const TVec< TIntV > &OverlapMtx, int MinNodeOverlap, TVec< TIntV > &CliqueIdVV)
 
static void GetOverlapCliques (const TVec< TIntV > &OverlapMtx, const TVec< TIntV > &MaxCliques, double MinOverlapFrac, TVec< TIntV > &CliqueIdVV)
 
static void GetMaxCliques (const PUNGraph &G, int MinMaxCliqueSize, TVec< TIntV > &MaxCliques)
 Enumerate maximal cliques of the network on more than MinMaxCliqueSize nodes. More...
 
static void GetCPMCommunities (const PUNGraph &G, int MinMaxCliqueSize, TVec< TIntV > &Communities)
 Clique Percolation method communities. More...
 

Private Member Functions

void GetNbrs (int NId, THashSet< TInt > &Nbrs) const
 
int GetNodeIdWithMaxDeg (const THashSet< TInt > &Set) const
 
int MaxNbrsInCANDNodeId (const THashSet< TInt > &SUBG, const THashSet< TInt > &CAND) const
 
void Expand (const THashSet< TInt > &SUBG, THashSet< TInt > &CAND)
 

Private Attributes

PUNGraph m_G
 
TIntV m_Q
 
TVec< TIntV > * m_maxCliques
 
int m_minMaxCliqueSize
 

Detailed Description

Definition at line 8 of file cliques.h.

Constructor & Destructor Documentation

TCliqueOverlap::TCliqueOverlap ( )
inline

Definition at line 29 of file cliques.h.

29 : m_G(), m_Q(), m_maxCliques(NULL), m_minMaxCliqueSize(3) { }
TCliqueOverlap::m_minMaxCliqueSize
int m_minMaxCliqueSize
Definition: cliques.h:13
TCliqueOverlap::m_maxCliques
TVec< TIntV > * m_maxCliques
Definition: cliques.h:12
TCliqueOverlap::m_G
PUNGraph m_G
Definition: cliques.h:10
TCliqueOverlap::m_Q
TIntV m_Q
Definition: cliques.h:11

Member Function Documentation

void TCliqueOverlap::CalculateOverlapMtx ( const TVec< TIntV > &  MaxCliques,
int  MinNodeOverlap,
TVec< TIntV > &  OverlapMtx 
)
static

Definition at line 127 of file cliques.cpp.

127  {
128  OverlapMtx.Clr();
129  //
130  int n = MaxCliques.Len();
131  //Convert max cliques to HashSets
132  TVec<THashSet<TInt> > cliques;
133  for (int i=0; i<n; i++) {
134  const int len = MaxCliques[i].Len();
135  cliques.Add();
136  if (len < MinNodeOverlap) { continue; }
137  THashSet<TInt>& set = cliques.Last(); set.Gen(len);
138  for (int j=0; j<len; j++) { set.AddKey(MaxCliques[i][j]); }
139  }
140  //Init clique clique overlap matrix
141  n = cliques.Len();
142  OverlapMtx.Gen(n);
143  for (int i=0; i<n; i++) OverlapMtx[i].Gen(n);
144  //Calculate clique clique overlap matrix
145  for (int i=0; i<n; i++) {
146  OverlapMtx[i][i] = cliques[i].Len();
147  for (int j=i+1; j<n; j++) {
148  OverlapMtx[i][j] = Intersection(cliques[i], cliques[j]); }
149  }
150 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THashSet::Gen
void Gen(const int &ExpectVals)
Definition: shash.h:1115
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TCliqueOverlap::Intersection
static int Intersection(const THashSet< TInt > &A, const THashSet< TInt > &B)
Definition: cliques.cpp:23
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
PUNGraph TCliqueOverlap::CalculateOverlapMtx ( const TVec< TIntV > &  MaxCliques,
int  MinNodeOverlap 
)
static

Definition at line 152 of file cliques.cpp.

152  {
153  const int n = MaxCliques.Len();
154  //Convert max cliques to HashSets
155  TVec<THashSet<TInt> > cliques;
156  for (int i=0; i<n; i++) {
157  const int len = MaxCliques[i].Len();
158  cliques.Add();
159  if (len < MinNodeOverlap) { continue; }
160  THashSet<TInt>& set = cliques.Last(); set.Gen(len);
161  for (int j=0; j<len; j++) { set.AddKey(MaxCliques[i][j]); }
162  }
163  //Init clique clique overlap matrix
164  PUNGraph OverlapMtx = TUNGraph::New();
165  for (int i=0; i < n; i++) {
166  OverlapMtx->AddNode(i); }
167  //Calculate clique clique overlap matrix
168  for (int i=0; i<n; i++) {
169  for (int j=i+1; j<n; j++) {
170  if (Intersection(cliques[i], cliques[j]) >= MinNodeOverlap) {
171  OverlapMtx->AddEdge(i,j); }
172  }
173  }
174  return OverlapMtx;
175 }
TUNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THashSet::Gen
void Gen(const int &ExpectVals)
Definition: shash.h:1115
TUNGraph::New
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:155
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
TUNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TCliqueOverlap::Intersection
static int Intersection(const THashSet< TInt > &A, const THashSet< TInt > &B)
Definition: cliques.cpp:23
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
void TCliqueOverlap::Expand ( const THashSet< TInt > &  SUBG,
THashSet< TInt > &  CAND 
)
private

Definition at line 73 of file cliques.cpp.

73  {
74  if (SUBG.Len()==0) { if (m_Q.Len() >= m_minMaxCliqueSize) { m_Q.Pack(); m_maxCliques->Add(m_Q); } return; }
75  if (CAND.Len()==0) return;
76  //Get u that maximaze CAND intersection with neighbours of vertex u
77  int u = MaxNbrsInCANDNodeId(SUBG, CAND);
78  //Get neighbours of node u
79  THashSet<TInt> nbrsU;
80  GetNbrs(u, nbrsU);
81  //Get relative complement of nbrsU in CAND
82  THashSet<TInt> EXT;
83  GetRelativeComplement(CAND, nbrsU, EXT);
84  while(EXT.Len() != 0) {
85  int q = GetNodeIdWithMaxDeg(EXT);
86  //
87  m_Q.Add(q);
88  //
89  THashSet<TInt> nbrsQ;
90  GetNbrs(q, nbrsQ);
91  //
92  THashSet<TInt> SUBGq;
93  GetIntersection(SUBG, nbrsQ, SUBGq);
94  //
95  THashSet<TInt> CANDq;
96  GetIntersection(CAND, nbrsQ, CANDq);
97  //
98  Expand(SUBGq, CANDq);
99  //
100  CAND.DelKey(q);
101  m_Q.DelLast();
102  //
103  EXT.Clr();
104  GetRelativeComplement(CAND, nbrsU, EXT);
105  }
106 }
THashSet::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
TCliqueOverlap::GetRelativeComplement
static void GetRelativeComplement(const THashSet< TInt > &A, const THashSet< TInt > &B, THashSet< TInt > &Complement)
Definition: cliques.cpp:6
TCliqueOverlap::GetNbrs
void GetNbrs(int NId, THashSet< TInt > &Nbrs) const
Definition: cliques.cpp:35
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THashSet::DelKey
void DelKey(const TKey &Key)
Definition: shash.h:1289
TCliqueOverlap::MaxNbrsInCANDNodeId
int MaxNbrsInCANDNodeId(const THashSet< TInt > &SUBG, const THashSet< TInt > &CAND) const
Definition: cliques.cpp:53
TCliqueOverlap::GetIntersection
static void GetIntersection(const THashSet< TInt > &A, const THashSet< TInt > &B, THashSet< TInt > &C)
Definition: cliques.cpp:13
TCliqueOverlap::Expand
void Expand(const THashSet< TInt > &SUBG, THashSet< TInt > &CAND)
Definition: cliques.cpp:73
TCliqueOverlap::m_minMaxCliqueSize
int m_minMaxCliqueSize
Definition: cliques.h:13
THashSet::Len
int Len() const
Definition: shash.h:1121
TCliqueOverlap::m_maxCliques
TVec< TIntV > * m_maxCliques
Definition: cliques.h:12
TVec::Pack
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1005
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TVec::DelLast
void DelLast()
Removes the last element of the vector.
Definition: ds.h:635
TCliqueOverlap::m_Q
TIntV m_Q
Definition: cliques.h:11
TCliqueOverlap::GetNodeIdWithMaxDeg
int GetNodeIdWithMaxDeg(const THashSet< TInt > &Set) const
Definition: cliques.cpp:41
void TCliqueOverlap::GetCPMCommunities ( const PUNGraph &  G,
int  MinMaxCliqueSize,
TVec< TIntV > &  Communities 
)
static

Clique Percolation method communities.

Definition at line 224 of file cliques.cpp.

224  {
225  printf("Clique Percolation Method\n");
226  TExeTm ExeTm;
227  TVec<TIntV> MaxCliques;
228  TCliqueOverlap::GetMaxCliques(G, MinMaxCliqueSize, MaxCliques);
229  // op RS 2012/05/15, commented out next line, a parameter is missing,
230  // creating a warning on OS X
231  // printf("...%d cliques found\n");
232  // get clique overlap matrix (graph)
233  PUNGraph OverlapGraph = TCliqueOverlap::CalculateOverlapMtx(MaxCliques, MinMaxCliqueSize-1);
234  printf("...overlap matrix (%d, %d)\n", G->GetNodes(), G->GetEdges());
235  // connected components are communities
236  TCnComV CnComV;
237  TSnap::GetWccs(OverlapGraph, CnComV);
238  NIdCmtyVV.Clr(false);
239  TIntSet CmtySet;
240  for (int c = 0; c < CnComV.Len(); c++) {
241  CmtySet.Clr(false);
242  for (int i = 0; i <CnComV[c].Len(); i++) {
243  const TIntV& CliqueNIdV = MaxCliques[CnComV[c][i]];
244  CmtySet.AddKeyV(CliqueNIdV);
245  }
246  NIdCmtyVV.Add();
247  CmtySet.GetKeyV(NIdCmtyVV.Last());
248  NIdCmtyVV.Last().Sort();
249  }
250  printf("done [%s].\n", ExeTm.GetStr());
251 }
THashSet::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
TExeTm
Definition: tm.h:355
THashSet::AddKeyV
void AddKeyV(const TVec< TKey > &KeyV)
Definition: shash.h:1284
TUNGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
THashSet::GetKeyV
void GetKeyV(TVec< TKey > &KeyV) const
Definition: shash.h:1347
TCliqueOverlap::GetMaxCliques
static void GetMaxCliques(const PUNGraph &G, int MinMaxCliqueSize, TVec< TIntV > &MaxCliques)
Enumerate maximal cliques of the network on more than MinMaxCliqueSize nodes.
Definition: cliques.cpp:217
TUNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:168
TExeTm::GetStr
const char * GetStr() const
Definition: tm.h:368
TCliqueOverlap::CalculateOverlapMtx
static void CalculateOverlapMtx(const TVec< TIntV > &MaxCliques, int MinNodeOverlap, TVec< TIntV > &OverlapMtx)
Definition: cliques.cpp:127
TSnap::GetWccs
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376
void TCliqueOverlap::GetIntersection ( const THashSet< TInt > &  A,
const THashSet< TInt > &  B,
THashSet< TInt > &  C 
)
static

Definition at line 13 of file cliques.cpp.

13  {
14  if (A.Len() < B.Len()) {
15  for (THashSetKeyI<TInt> it=A.BegI(); it<A.EndI(); it++)
16  if (B.IsKey(it.GetKey())) C.AddKey(it.GetKey());
17  } else {
18  for (THashSetKeyI<TInt> it=B.BegI(); it<B.EndI(); it++)
19  if (A.IsKey(it.GetKey())) C.AddKey(it.GetKey());
20  }
21 }
THashSet::BegI
TIter BegI() const
Definition: shash.h:1105
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
THashSet::EndI
TIter EndI() const
Definition: shash.h:1112
THashSet::Len
int Len() const
Definition: shash.h:1121
void TCliqueOverlap::GetMaxCliques ( const PUNGraph &  G,
int  MinMaxCliqueSize,
TVec< TIntV > &  MaxCliques 
)
static

Enumerate maximal cliques of the network on more than MinMaxCliqueSize nodes.

Definition at line 217 of file cliques.cpp.

217  {
218  TCliqueOverlap CO;
219  MaxCliques.Clr(false);
220  CO.GetMaximalCliques(G, MinMaxCliqueSize, MaxCliques);
221 }
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TCliqueOverlap::GetMaximalCliques
void GetMaximalCliques(const PUNGraph &G, int MinMaxCliqueSize, TVec< TIntV > &MaxCliques)
Definition: cliques.cpp:108
void TCliqueOverlap::GetMaximalCliques ( const PUNGraph &  G,
int  MinMaxCliqueSize,
TVec< TIntV > &  MaxCliques 
)

Definition at line 108 of file cliques.cpp.

108  {
109  if (G->GetNodes() == 0) return;
110  //
111  m_G = G;
112  m_minMaxCliqueSize = MinMaxCliqueSize;
113  m_maxCliques =& MaxCliques;
114  m_Q.Clr();
115  //
116  THashSet<TInt> SUBG;
117  THashSet<TInt> CAND;
118  for (TUNGraph::TNodeI NI=m_G->BegNI(); NI<m_G->EndNI(); NI++) {
119  TInt nId = NI.GetId();
120  SUBG.AddKey(nId);
121  CAND.AddKey(nId);
122  }
123  //
124  Expand(SUBG, CAND);
125 }
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
TUNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:168
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TCliqueOverlap::Expand
void Expand(const THashSet< TInt > &SUBG, THashSet< TInt > &CAND)
Definition: cliques.cpp:73
TInt
Definition: dt.h:1044
TCliqueOverlap::m_minMaxCliqueSize
int m_minMaxCliqueSize
Definition: cliques.h:13
TCliqueOverlap::m_maxCliques
TVec< TIntV > * m_maxCliques
Definition: cliques.h:12
TCliqueOverlap::m_G
PUNGraph m_G
Definition: cliques.h:10
TUNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:211
TUNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:209
TCliqueOverlap::m_Q
TIntV m_Q
Definition: cliques.h:11
void TCliqueOverlap::GetNbrs ( int  NId,
THashSet< TInt > &  Nbrs 
) const
private

Definition at line 35 of file cliques.cpp.

35  {
36  TUNGraph::TNodeI node = m_G->GetNI(NId);
37  int deg = node.GetDeg();
38  for (int i=0; i<deg; i++) Nbrs.AddKey(node.GetNbrNId(i));
39 }
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
TUNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:86
TUNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TCliqueOverlap::m_G
PUNGraph m_G
Definition: cliques.h:10
TUNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:107
int TCliqueOverlap::GetNodeIdWithMaxDeg ( const THashSet< TInt > &  Set) const
private

Definition at line 41 of file cliques.cpp.

41  {
42  int id = -1;
43  int maxDeg = -1;
44  //
45  for (THashSetKeyI<TInt> it=Set.BegI(); it<Set.EndI(); it++) {
46  int nId = it.GetKey();
47  int deg = m_G->GetNI(nId).GetDeg();
48  if (maxDeg < deg) { maxDeg=deg; id=nId; }
49  }
50  return id;
51 }
THashSet::BegI
TIter BegI() const
Definition: shash.h:1105
TUNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:86
TUNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
THashSet::EndI
TIter EndI() const
Definition: shash.h:1112
TCliqueOverlap::m_G
PUNGraph m_G
Definition: cliques.h:10
void TCliqueOverlap::GetOverlapCliques ( const TVec< TIntV > &  OverlapMtx,
int  MinNodeOverlap,
TVec< TIntV > &  CliqueIdVV 
)
static

Definition at line 177 of file cliques.cpp.

177  {
178  int n = OverlapMtx.Len();
179  for (int i=0; i<n; i++) {
180  bool isCommunity = false;
181  for (int j=i+1; j<n; j++) {
182  if (OverlapMtx[i][j] >= MinNodeOverlap) {
183  if (! isCommunity) {
184  TIntV v; v.Add(i);
185  CliqueIdVV.Add(v);
186  isCommunity=true;
187  }
188  CliqueIdVV.Last().Add(j);
189  }
190  }
191  }
192 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void TCliqueOverlap::GetOverlapCliques ( const TVec< TIntV > &  OverlapMtx,
const TVec< TIntV > &  MaxCliques,
double  MinOverlapFrac,
TVec< TIntV > &  CliqueIdVV 
)
static

Definition at line 194 of file cliques.cpp.

194  {
195  int n = OverlapMtx.Len();
196  for(int i=0; i<n; i++){
197  bool isCommunity = false;
198  int size1 = MaxCliques[i].Len();
199  for(int j=i+1; j<n; j++){
200  int size2 = MaxCliques[j].Len();
201  double ratio = OverlapMtx[i][j];
202  if(size1 < size2) ratio /= size1;
203  else ratio /= size2;
204  if(ratio >= MinOverlapFrac){
205  if(!isCommunity){
206  TIntV v; v.Add(i);
207  CliqueIdVV.Add(v);
208  isCommunity=true;
209  }
210  CliqueIdVV.Last().Add(j);
211  }
212  }
213  }
214 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void TCliqueOverlap::GetRelativeComplement ( const THashSet< TInt > &  A,
const THashSet< TInt > &  B,
THashSet< TInt > &  Complement 
)
static

Definition at line 6 of file cliques.cpp.

6  {
7  for (THashSet<TInt>::TIter it=A.BegI(); it<A.EndI(); it++) {
8  const int nId = it.GetKey();
9  if (!B.IsKey(nId)) Complement.AddKey(nId);
10  }
11 }
THashSet::BegI
TIter BegI() const
Definition: shash.h:1105
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
THashSet::EndI
TIter EndI() const
Definition: shash.h:1112
int TCliqueOverlap::Intersection ( const THashSet< TInt > &  A,
const THashSet< TInt > &  B 
)
static

Definition at line 23 of file cliques.cpp.

23  {
24  int n = 0;
25  if (A.Len() < B.Len()) {
26  for (THashSetKeyI<TInt> it=A.BegI(); it<A.EndI(); it++)
27  if (B.IsKey(it.GetKey())) n++;
28  } else {
29  for (THashSetKeyI<TInt> it=B.BegI(); it<B.EndI(); it++)
30  if (A.IsKey(it.GetKey())) n++;
31  }
32  return n;
33 }
THashSet::BegI
TIter BegI() const
Definition: shash.h:1105
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
THashSet::EndI
TIter EndI() const
Definition: shash.h:1112
THashSet::Len
int Len() const
Definition: shash.h:1121
int TCliqueOverlap::MaxNbrsInCANDNodeId ( const THashSet< TInt > &  SUBG,
const THashSet< TInt > &  CAND 
) const
private

Definition at line 53 of file cliques.cpp.

53  {
54  int id = -1;
55  int maxIntersection = -1;
56  //
57  for (THashSetKeyI<TInt> it=SUBG.BegI(); it<SUBG.EndI(); it++) {
58  int nId = it.GetKey();
59  TUNGraph::TNodeI nIt = m_G->GetNI(nId);
60  int deg = nIt.GetDeg();
61  //
62  int curIntersection = 0;
63  for (int i=0; i<deg; i++) {
64  int nbrId = nIt.GetNbrNId(i);
65  if (CAND.IsKey(nbrId)) curIntersection++;
66  }
67  //
68  if (maxIntersection < curIntersection) { maxIntersection=curIntersection; id=nId; }
69  }
70  return id;
71 }
THashSet::BegI
TIter BegI() const
Definition: shash.h:1105
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
TUNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:86
TUNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
THashSet::EndI
TIter EndI() const
Definition: shash.h:1112
TCliqueOverlap::m_G
PUNGraph m_G
Definition: cliques.h:10
TUNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:107

Member Data Documentation

PUNGraph TCliqueOverlap::m_G
private

Definition at line 10 of file cliques.h.

TVec<TIntV>* TCliqueOverlap::m_maxCliques
private

Definition at line 12 of file cliques.h.

int TCliqueOverlap::m_minMaxCliqueSize
private

Definition at line 13 of file cliques.h.

TIntV TCliqueOverlap::m_Q
private

Definition at line 11 of file cliques.h.

The documentation for this class was generated from the following files: