SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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
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:416
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:499
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:398
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:379
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