SNAP Library 3.0, Developer 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
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:376
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
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:425
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:516
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
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:514
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:438
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:220
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:386
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 IDs 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:477
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:532
Definition: ds.h:32
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:362
static uint64 GetMinAndGraphIds(const TVec< PNGraph > &isoG, TVec< uint64 > &graphIds)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
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:495
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:216
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
static void GetGraph(uint64 graphId, int nodes, PNGraph &G)
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
static int m_graphIds[]
Definition: graphcounter.h:64
TD34GraphCounter(int GraphSz)
Definition: dt.h:1225