SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
graphcounter.cpp
Go to the documentation of this file.
1 #include "stdafx.h"
2 #include "graphcounter.h"
3 
4 //Number of directed connected 5-node subgraphs = 9364
5 
7 // Directed 3 graph implementation
9 int TD3Graph::m_graphIds[] = {6,12,14,36,38,46,78,102,140,164,166,174,238};
10 
11 int TD3Graph::getId(const PNGraph &G, const TIntV &sg) {
12  int id=0;
13  //Node 0
14  if(TGraphEnumUtils::IsEdge(G, sg[0], sg[1])) id+=2;
15  if(TGraphEnumUtils::IsEdge(G, sg[0], sg[2])) id+=4;
16  //Node 1
17  if(TGraphEnumUtils::IsEdge(G, sg[1], sg[0])) id+=8;
18  if(TGraphEnumUtils::IsEdge(G, sg[1], sg[2])) id+=32;
19  //Node 2
20  if(TGraphEnumUtils::IsEdge(G, sg[2], sg[0])) id+=64;
21  if(TGraphEnumUtils::IsEdge(G, sg[2], sg[1])) id+=128;
22  //
23  return id;
24 }
26 // Directed 4 graph implementation
27 int TD4Graph::m_numOfGraphs = 199;
28 int TD4Graph::m_graphIds[] = {14, 28, 30, 74, 76, 78, 90, 92, 94, 204, 206, 222, 280, 282, 286,
29  328, 330, 332, 334, 344, 346, 348, 350, 390, 392, 394, 396, 398,
30  404, 406, 408, 410, 412, 414, 454, 456, 458, 460, 462, 468, 470,
31  472, 474, 476, 478, 856, 858, 862, 904, 906, 908, 910, 922, 924,
32  926, 972, 974, 990, 2184, 2186, 2190, 2202, 2204, 2206, 2252, 2254,
33  2270, 2458, 2462, 2506, 2510, 2524, 2526, 3038, 4370, 4374, 4382,
34  4418, 4420, 4422, 4424, 4426, 4428, 4430, 4434, 4436, 4438, 4440,
35  4442, 4444, 4446, 4546, 4548, 4550, 4556, 4558, 4562, 4564, 4566,
36  4572, 4574, 4678, 4682, 4686, 4692, 4694, 4698, 4700, 4702, 4740,
37  4742, 4748, 4750, 4758, 4764, 4766, 4812, 4814, 4830, 4946, 4950,
38  4952, 4954, 4958, 4994, 4998, 5002, 5004, 5006, 5010, 5012, 5014,
39  5016, 5018, 5020, 5022, 5058, 5062, 5064, 5066, 5068, 5070, 5074,
40  5076, 5078, 5080, 5082, 5084, 5086, 6342, 6348, 6350, 6356, 6358,
41  6364, 6366, 6550, 6552, 6554, 6558, 6598, 6602, 6604, 6606, 6614,
42  6616, 6618, 6620, 6622, 6854, 6858, 6862, 6870, 6874, 6876, 6878,
43  7126, 7128, 7130, 7134, 13142, 13146, 13148, 13150, 13260, 13262,
44  13278, 14678, 14686, 14790, 14798, 14810, 14812, 14814, 15258,
45  15262, 15310, 15326, 31710 };
46 
47 int TD4Graph::getId(const PNGraph &G, const TIntV &sg) {
48  int id=0;
49  //Node 0
50  if(TGraphEnumUtils::IsEdge(G, sg[0], sg[1])) id+=2;
51  if(TGraphEnumUtils::IsEdge(G, sg[0], sg[2])) id+=4;
52  if(TGraphEnumUtils::IsEdge(G, sg[0], sg[3])) id+=8;
53  //Node 1
54  if(TGraphEnumUtils::IsEdge(G, sg[1], sg[0])) id+=16;
55  if(TGraphEnumUtils::IsEdge(G, sg[1], sg[2])) id+=64;
56  if(TGraphEnumUtils::IsEdge(G, sg[1], sg[3])) id+=128;
57  //Node 2
58  if(TGraphEnumUtils::IsEdge(G, sg[2], sg[0])) id+=256;
59  if(TGraphEnumUtils::IsEdge(G, sg[2], sg[1])) id+=512;
60  if(TGraphEnumUtils::IsEdge(G, sg[2], sg[3])) id+=2048;
61  //Node 3
62  if(TGraphEnumUtils::IsEdge(G, sg[3], sg[0])) id+=4096;
63  if(TGraphEnumUtils::IsEdge(G, sg[3], sg[1])) id+=8192;
64  if(TGraphEnumUtils::IsEdge(G, sg[3], sg[2])) id+=16384;
65  //
66  return id;
67 }
68 
70 // Directed 3 or 4 graph counter implementation
72  IAssert(GraphSz==3 || GraphSz==4);
73  //
74  m_subGraphSize = GraphSz;
75  //
76  int numOfGraphs = 0;
77  if(GraphSz==3) numOfGraphs = TD3Graph::m_numOfGraphs;
78  else if(GraphSz==4) numOfGraphs = TD4Graph::m_numOfGraphs;
79  //
80  for(int i=0; i<numOfGraphs; i++) {
81  int graphId = 0;
82  if(GraphSz==3) graphId = TD3Graph::m_graphIds[i];
83  else if(GraphSz==4) graphId = TD4Graph::m_graphIds[i];
84  //
85  TVec<PNGraph> isoG;
86  TGraphEnumUtils::GetIsoGraphs(graphId, GraphSz, isoG);
87  //
88  TVec<uint64> graphIds(isoG.Len());
89  uint64 minGraphId = TGraphEnumUtils::GetMinAndGraphIds(isoG, graphIds);
90  for(int j=0; j<graphIds.Len(); j++)
91  m_graphMaps.AddDat((int)graphIds[j], (int)minGraphId);
92  //
93  m_graphCounters.AddDat((int)minGraphId, 0);
94  }
95 }
96 void TD34GraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
97  int graphId = 0;
98  if(m_subGraphSize==3) graphId = TD3Graph::getId(G, sg);
99  else if(m_subGraphSize==4) graphId = TD4Graph::getId(G, sg);
100  //
101  if(!m_graphMaps.IsKey(graphId)) { printf("This graph does not exist: %d\n", graphId); getchar(); return; }
102  int minGraphId = m_graphMaps.GetDat(graphId);
103  //
104  m_graphCounters.GetDat(minGraphId)++;
105 }
106 
107 PNGraph TD34GraphCounter::GetGraph(const int& GraphId) const {
108  PNGraph G = TNGraph::New();
110  return G;
111 }
112 
114 // Directed graph counter implementation
115 void TDGraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
116  uint64 graphId = TGraphEnumUtils::GraphId(G, sg);
117  //
118  if(m_graphMaps.IsKey(graphId)) {
119  TUInt64 minGraphId = m_graphMaps.GetDat(graphId);
120  m_graphCounters.GetDat(minGraphId)++;
121  }else{
122  TVec<PNGraph> isoG;
123  TGraphEnumUtils::GetIsoGraphs(graphId, sg.Len(), isoG);
124  //
125  TVec<uint64> graphIds(isoG.Len());
126  uint64 minGraphId = TGraphEnumUtils::GetMinAndGraphIds(isoG, graphIds);
127  for(int j=0; j<graphIds.Len(); j++)
128  m_graphMaps.AddDat(graphIds[j], minGraphId);
129  //
130  m_graphCounters.AddDat(minGraphId, 1);
131  }
132 }
133 
135 // Directed ghash graph counter implementation
136 void TDGHashGraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
137  PNGraph indG = TNGraph::New();
138  TGraphEnumUtils::GetIndGraph(G, sg, indG);
139  //
140  if(m_graphs.IsKey(indG))
141  m_graphs.GetDat(indG)++;
142  else m_graphs.AddDat(indG, 1);
143 }
144 
146 // TGraphEnumUtils implementation
148  int nId=0;
149  for(TNGraph::TNodeI it=G->BegNI(); it<G->EndNI(); it++) {
150  //printf("%d -> %d\n", it.GetId(), nId);
151  map.AddDat(it.GetId(), nId);
152  nId++;
153  }
154 }
155 
157  int n = v.Len();
158  if (start == n-1) perms.Add(v);
159  else {
160  for (int i = start; i < n; i++) {
161  int tmp = v[i];
162  v[i] = v[start];
163  v[start] = tmp;
164  GetPermutations(v, start+1, perms);
165  //
166  v[start] = v[i];
167  v[i] = tmp;
168  }
169  }
170 }
171 
173  //Get bijective map from original node ids to normalized node ids(0,1,2,...)
174  THash<TInt,TInt> map;
175  GetNormalizedMap(G, map);
176  //Add nodes
177  for(int i=0; i<G->GetNodes(); i++) nG->AddNode(i);
178  //Add edges
179  for(TNGraph::TEdgeI eIt=G->BegEI(); eIt<G->EndEI(); eIt++) {
180  int srcId = eIt.GetSrcNId();
181  int dstId = eIt.GetDstNId();
182  //
183  int mSrcId = map.GetDat(srcId);
184  int mDstId = map.GetDat(dstId);
185  //
186  nG->AddEdge(mSrcId, mDstId);
187  }
188 }
189 
190 void TGraphEnumUtils::GetEdges(uint64 graphId, int nodes, TVec<TPair<int,int> > &edges) {
191  for(int row=0; row<nodes; row++) {
192  for(int col=0; col<nodes; col++) {
193  int n = row*nodes+col;
194  //
195  uint64 bits = graphId >> n;
196  uint64 mask = 1;
197  if((bits & mask)==1) edges.Add(TPair<int,int>(row, col));
198  }
199  }
200 }
201 
202 void TGraphEnumUtils::GetIsoGraphs(uint64 graphId, int nodes, TVec<PNGraph> &isoG) {
203  TIntV v(nodes); for(int i=0; i<nodes; i++) v[i]=i;
204  TVec<TIntV> perms; GetPermutations(v, 0, perms);
205  isoG.Gen(perms.Len());
206  //
207  TVec<TPair<int,int> > edges;
208  GetEdges(graphId, nodes, edges);
209  //
210  for(int i=0; i<perms.Len(); i++) {
211  isoG[i] = TNGraph::New();
212  //Add nodes
213  for(int j=0; j<nodes; j++) isoG[i]->AddNode(j);
214  //Add edges
215  for(int j=0; j<edges.Len(); j++) {
216  int srcId = edges[j].Val1;
217  int dstId = edges[j].Val2;
218  //
219  int pSrcId = perms[i][srcId];
220  int pDstId = perms[i][dstId];
221  //
222  isoG[i]->AddEdge(pSrcId, pDstId);
223  }
224  }
225 }
226 
228  int nodes = G->GetNodes();
229  //
230  TIntV v(nodes); for(int i=0; i<nodes; i++) v[i]=i;
231  TVec<TIntV> perms; GetPermutations(v, 0, perms);
232  isoG.Gen(perms.Len());
233  //
234  for(int i=0; i<perms.Len(); i++) {
235  isoG[i] = TNGraph::New();
236  //Add nodes
237  for(int j=0; j<nodes; j++) isoG[i]->AddNode(j);
238  //Add edges
239  for(TNGraph::TEdgeI eIt=G->BegEI(); eIt<G->EndEI(); eIt++) {
240  int srcId = eIt.GetSrcNId();
241  int dstId = eIt.GetDstNId();
242  //
243  int pSrcId = perms[i][srcId];
244  int pDstId = perms[i][dstId];
245  //
246  isoG[i]->AddEdge(pSrcId, pDstId);
247  }
248  }
249 }
250 
251 void TGraphEnumUtils::GetIndGraph(const PNGraph &G, const TIntV &sg, PNGraph &indG) {
252  //Add nodes
253  for(int i=0; i<sg.Len(); i++) indG->AddNode(sg[i]);
254  //Add edges
255  for(int i=0; i<sg.Len(); i++) {
256  int nId = sg[i];
257  TNGraph::TNodeI nIt = G->GetNI(nId);
258  //
259  int deg = nIt.GetOutDeg();
260  for(int j=0; j<deg; j++) {
261  int dstId = nIt.GetNbrNId(j);
262  if(nId == dstId) continue;
263  //
264  if(indG->IsNode(dstId)) indG->AddEdge(nId, dstId);
265  }
266  }
267 }
268 
269 void TGraphEnumUtils::GetGraph(uint64 graphId, int nodes, PNGraph &G) {
270  G->Clr();
271  //Add nodes;
272  for(int i=0; i<nodes; i++) G->AddNode(i);
273  //Add edges
274  for(int row=0; row<nodes; row++) {
275  for(int col=0; col<nodes; col++) {
276  int n = row*nodes+col;
277  //
278  uint64 bits = graphId >> n;
279  uint64 mask = 1;
280  if((bits & mask)==1) G->AddEdge(row, col);
281  }
282  }
283 }
284 
286  int nodes = G->GetNodes();
287  uint64 id=0;
288  for(TNGraph::TEdgeI it=G->BegEI(); it<G->EndEI(); it++) {
289  int srcId = it.GetSrcNId();
290  int dstId = it.GetDstNId();
291  //
292  id += TMath::Pow2(srcId*nodes + dstId);
293  }
294  //
295  return id;
296 }
297 
299  int nodes = sg.Len();
300  uint64 graphId = 0;
301  for(int i=0; i<nodes; i++) {
302  for(int j=0; j<nodes; j++) {
303  if(i==j) continue;
304  //
305  if(TGraphEnumUtils::IsEdge(G, sg[i], sg[j])) graphId+=TMath::Pow2(i*nodes + j);
306  }
307  }
308  return graphId;
309 }
310 
312  IAssert(isoG.Len() > 0);
313  //
314  uint64 minGraphId = GraphId(isoG[0]);
315  graphIds.Add(minGraphId);
316  //
317  for(int i=1; i<isoG.Len(); i++) {
318  uint64 curGraphId = GraphId(isoG[i]);
319  if(minGraphId > curGraphId) minGraphId=curGraphId;
320  //
321  graphIds.Add(curGraphId);
322  }
323  //
324  return minGraphId;
325 }
#define IAssert(Cond)
Definition: bd.h:262
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:420
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
THash< TUInt64, TUInt64 > m_graphMaps
Definition: graphcounter.h:31
THash< TUInt64, TUInt64 > m_graphCounters
Definition: graphcounter.h:32
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:596
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
static int m_graphIds[]
Definition: graphcounter.h:54
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:594
const TDat & GetDat(const PNGraph &Graph) const
Returns the data associated with key Graph.
Definition: ghash.h:192
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
void operator()(const PNGraph &G, const TIntV &sg)
static void GetPermutations(TIntV &v, int start, TVec< TIntV > &perms)
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
static int getId(const PNGraph &G, const TIntV &sg)
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
void operator()(const PNGraph &G, const TIntV &sg)
PNGraph GetGraph(const int &GraphId) const
static int m_numOfGraphs
Definition: graphcounter.h:53
static uint Pow2(const int &pow)
Definition: xmath.h:24
static void GetIsoGraphs(uint64 graphId, int nodes, TVec< PNGraph > &isoG)
static bool IsEdge(const PNGraph &G, int SrcNId, int DstNId)
Definition: graphcounter.h:84
static void GetNormalizedMap(const PNGraph &G, THash< TInt, TInt > &map)
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
bool IsKey(const PNGraph &Graph) const
Test whether Graph is an existing key in the hash table.
Definition: ghash.h:184
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
unsigned long long uint64
Definition: bd.h:38
static uint64 GraphId(const PNGraph &G)
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:546
static void GetEdges(uint64 graphId, int nodes, TVec< TPair< int, int > > &edges)
static int getId(const PNGraph &G, const TIntV &sg)
TDat & AddDat(const PNGraph &Graph)
Adds a key Graph to the table and returns its data value.
Definition: ghash.h:177
static void GetNormalizedGraph(const PNGraph &G, PNGraph &nG)
static int m_numOfGraphs
Definition: graphcounter.h:63
TGHash< TUInt64 > m_graphs
Definition: graphcounter.h:44
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:612
Definition: ds.h:32
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
static uint64 GetMinAndGraphIds(const TVec< PNGraph > &isoG, TVec< uint64 > &graphIds)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
THash< TInt, TInt > m_graphMaps
Definition: graphcounter.h:19
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
THash< TInt, TUInt64 > m_graphCounters
Definition: graphcounter.h:20
static void GetIndGraph(const PNGraph &G, const TIntV &sg, PNGraph &indG)
void operator()(const PNGraph &G, const TIntV &sg)
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
static void GetGraph(uint64 graphId, int nodes, PNGraph &G)
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
static int m_graphIds[]
Definition: graphcounter.h:64
TD34GraphCounter(int GraphSz)
Definition: dt.h:1318