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
subgraphenum.h
Go to the documentation of this file.
1 #ifndef Snap_SubGraphEnum_h
2 #define Snap_SubGraphEnum_h
3 
4 #include "Snap.h"
5 
7 // Subgraph enumeration
8 //
9 // Enumerates all connected induced subgraph on SubGraphSz nodes
10 // The algorithm is described in Efficient Detection of Network
11 // Motifs by Sebastian Wernicke, IEEE/ACM Transactions on
12 // Computational Biology and Bioinformatics, 2006.
13 
14 template<class TGraphCounter>
16 private:
17  class TSSet {
18  protected:
20  int m_size;
21  bool *m_nodes;
22  public:
23  TSSet(int capacity) {
24  m_nodes = (bool *)malloc(capacity); memset(m_nodes, 0, capacity);
25  m_capacity = capacity; m_size = 0; }
26  TSSet(const TSSet &set) {
27  m_nodes = (bool *)malloc(set.m_capacity); memcpy(m_nodes, set.m_nodes, set.m_capacity);
28  m_capacity = set.m_capacity; m_size = set.m_size; }
29  ~TSSet() { free(m_nodes); }
30  public:
31  inline void Add(int i) { if(!m_nodes[i]) m_size++; m_nodes[i]=true; }
32  inline void Remove(int i) { m_nodes[i]=false; m_size--; }
33  inline bool IsKey(int i) const { return m_nodes[i]; }
34  inline int Capacity() const { return m_capacity; }
35  inline int Size() const { return m_size; }
36  inline bool operator[](int i) const { return m_nodes[i]; }
37  };
38  class TSVec {
39  protected:
41  int m_size;
42  int *m_arr;
44  public:
45  TSVec(int capacity) {
46  m_v.Gen(capacity); m_arr = (int *) m_v.BegI();
47  for(int i=0; i<capacity; i++) { m_arr[i]=-1; }
48  m_capacity = capacity; m_size = 0; }
49  public:
50  inline bool Contains(int nodeId) const {
51  for(int i=0; i<m_size; i++) { if(m_arr[i]==nodeId) return true; } return false; }
52  public:
53  inline void Push(int nodeId) { m_arr[m_size]=nodeId; m_size++; }
54  inline void Pop() { m_size--; m_arr[m_size]=-1; }
55  inline int Capacity() const { return m_capacity; }
56  inline int Size() const { return m_size; }
57  inline const TIntV &getVec() const { return m_v; }
58  inline int operator[](int i) const { return m_arr[i]; }
59  };
60 private:
62  int m_nodes;
64  TGraphCounter *m_functor;
65 private:
66  void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId);
67  void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext);
68 public:
70  //Graph must be normalized (vertex ids are 0,1,2,...)
71  void GetSubGraphs(PNGraph &Graph, int SubGraphSz, TGraphCounter& Counter);
72  void GetSubGraphs(PNGraph &Graph, int NId, int SubGraphSz, TGraphCounter& Counter);
73 };
74 // TGraphCounter must implement
75 // void operator()(const PNGraph &G, const TIntV &SubGraphNIdV);
76 // which gets called whenever a new subgraph on nodes in SubGraphNIdV is identified
77 
79 // TSubGraphEnum implementation
80 template <class TGraphCounter>
81 void TSubGraphEnum<TGraphCounter>::GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId) {
82  if(sg.Size() == m_subGraphSz) { (*m_functor)(m_graph, sg.getVec()); return; }
83  //
84  for(int i=0; i<ext.Capacity(); i++) {
85  while(ext[i] == false) {
86  i++;
87  if(i == ext.Capacity()) return;
88  }
89  //
90  int wId = i;
91  TNGraph::TNodeI wIt = m_graph->GetNI(wId);
92  int wDeg = wIt.GetDeg();
93  //
94  ext.Remove(wId);
95  //
96  TSSet newExt = ext;
97  TSSet newSgNbrs = sgNbrs;
98  for(int j=0; j<wDeg; j++) {
99  int nbrId = wIt.GetNbrNId(j);
100  if(nbrId > vId && !sgNbrs.IsKey(nbrId) && !sg.Contains(nbrId)) {
101  newExt.Add(nbrId);
102  newSgNbrs.Add(nbrId);
103  }
104  }
105  sg.Push(wId);
106  GetSubGraphs_recursive(sg, newSgNbrs, newExt, vId);
107  sg.Pop();
108  }
109 }
110 
111 template <class TGraphCounter>
112 void TSubGraphEnum<TGraphCounter>::GetSubGraphs(PNGraph &Graph, int SubGraphSz, TGraphCounter &Functor) {
113  m_graph = Graph;
114  m_nodes = m_graph->GetNodes();
115  m_subGraphSz = SubGraphSz;
116  m_functor = &Functor;
117  //
118  TExeTm extime;
119  for(TNGraph::TNodeI it=m_graph->BegNI(); it<m_graph->EndNI(); it++) {
120  int vId = it.GetId();
121  int vDeg = it.GetDeg();
122  //Subgraph
123  TSVec sg(SubGraphSz);
124  sg.Push(vId);
125  //Subgraph extension
126  TSSet ext(m_nodes);
127  for(int i=0; i<vDeg; i++) {
128  int nbrId = it.GetNbrNId(i);
129  if(nbrId > vId)
130  ext.Add(nbrId);
131  }
132  //Subgraph neighbours
133  TSSet sgNbrs = ext;
134  GetSubGraphs_recursive(sg, sgNbrs, ext, vId);
135  }
136  //printf("secs: %llf\n", extime.GetSecs());
137 }
138 
139 template <class TGraphCounter>
141  if(sg.Size() == m_subGraphSz) { (*m_functor)(m_graph, sg.getVec()); return; }
142  //
143  for(int i=0; i<ext.Capacity(); i++) {
144  while(ext[i] == false) {
145  i++;
146  if(i == ext.Capacity()) return;
147  }
148  //
149  int wId = i;
150  TNGraph::TNodeI wIt = m_graph->GetNI(wId);
151  int wDeg = wIt.GetDeg();
152  //
153  ext.Remove(wId);
154  //
155  TSSet newExt = ext;
156  TSSet newSgNbrs = sgNbrs;
157  for(int j=0; j<wDeg; j++) {
158  int nbrId = wIt.GetNbrNId(j);
159  if(!sgNbrs.IsKey(nbrId) && !sg.Contains(nbrId)) {
160  newExt.Add(nbrId);
161  newSgNbrs.Add(nbrId);
162  }
163  }
164  sg.Push(wId);
165  GetSubGraphs_recursive(sg, newSgNbrs, newExt);
166  sg.Pop();
167  }
168 }
169 
170 template <class TGraphCounter>
171 void TSubGraphEnum<TGraphCounter>::GetSubGraphs(PNGraph &Graph, int NId, int SubGraphSz, TGraphCounter &Functor) {
172  m_graph = Graph;
173  m_nodes = m_graph->GetNodes();
174  m_subGraphSz = SubGraphSz;
175  m_functor = &Functor;
176  //
177  TNGraph::TNodeI it=m_graph->GetNI(NId);
178  int vId = NId;
179  int vDeg = it.GetDeg();
180  //Subgraph
181  TSVec sg(SubGraphSz);
182  sg.Push(vId);
183  //Subgraph extension
184  TSSet ext(m_nodes);
185  for(int i=0; i<vDeg; i++) {
186  int nbrId = it.GetNbrNId(i);
187  ext.Add(nbrId);
188  }
189  //Subgraph neighbours
190  TSSet sgNbrs = ext;
191  //
192  TExeTm extime;
193  GetSubGraphs_recursive(sg, sgNbrs, ext);
194  printf("secs: %llf\n", extime.GetSecs());
195 }
196 
197 
198 #endif
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:420
bool IsKey(int i) const
Definition: subgraphenum.h:33
TSSet(const TSSet &set)
Definition: subgraphenum.h:26
int operator[](int i) const
Definition: subgraphenum.h:58
Definition: tm.h:355
TSSet(int capacity)
Definition: subgraphenum.h:23
void Push(int nodeId)
Definition: subgraphenum.h:53
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:503
TGraphCounter * m_functor
Definition: subgraphenum.h:64
const TIntV & getVec() const
Definition: subgraphenum.h:57
void GetSubGraphs(PNGraph &Graph, int SubGraphSz, TGraphCounter &Counter)
Definition: subgraphenum.h:112
bool operator[](int i) const
Definition: subgraphenum.h:36
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:402
void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId)
Definition: subgraphenum.h:81
int Capacity() const
Definition: subgraphenum.h:34
void Remove(int i)
Definition: subgraphenum.h:32
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
int Size() const
Definition: subgraphenum.h:35
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
double GetSecs() const
Definition: tm.h:366
bool Contains(int nodeId) const
Definition: subgraphenum.h:50
TSVec(int capacity)
Definition: subgraphenum.h:45
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
PNGraph m_graph
Definition: subgraphenum.h:61
int Capacity() const
Definition: subgraphenum.h:55
int Size() const
Definition: subgraphenum.h:56