SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
subgraphenum.h
Go to the documentation of this file.
00001 #ifndef Snap_SubGraphEnum_h
00002 #define Snap_SubGraphEnum_h
00003 
00004 #include "Snap.h"
00005 
00007 // Subgraph enumeration 
00008 //
00009 // Enumerates all connected induced subgraph on SubGraphSz nodes
00010 // The algorithm is described in Efficient Detection of Network 
00011 // Motifs by Sebastian Wernicke, IEEE/ACM Transactions on 
00012 // Computational Biology and Bioinformatics, 2006.
00013 
00014 template<class TGraphCounter>
00015 class TSubGraphEnum {
00016 private:
00017         class TSSet {
00018         protected:
00019                 int m_capacity;
00020                 int m_size;
00021                 bool *m_nodes;
00022         public:
00023                 TSSet(int capacity) {
00024                         m_nodes = (bool *)malloc(capacity); memset(m_nodes, 0, capacity);
00025                         m_capacity = capacity; m_size = 0; }
00026                 TSSet(const TSSet &set) {
00027                         m_nodes = (bool *)malloc(set.m_capacity); memcpy(m_nodes, set.m_nodes, set.m_capacity);
00028                         m_capacity = set.m_capacity; m_size = set.m_size; }
00029                 ~TSSet() { free(m_nodes); }
00030         public:
00031                 inline void Add(int i) { if(!m_nodes[i]) m_size++; m_nodes[i]=true; }
00032                 inline void Remove(int i) { m_nodes[i]=false; m_size--; }
00033                 inline bool IsKey(int i) const { return m_nodes[i]; }
00034                 inline int Capacity() const { return m_capacity; }
00035                 inline int Size() const { return m_size; }
00036                 inline bool operator[](int i) const { return m_nodes[i]; }
00037         };
00038         class TSVec {
00039         protected:
00040                 int m_capacity;
00041                 int m_size;
00042                 int *m_arr;
00043                 TIntV m_v;
00044         public:
00045                 TSVec(int capacity) {
00046                         m_v.Gen(capacity); m_arr = (int *) m_v.BegI();
00047       for(int i=0; i<capacity; i++) { m_arr[i]=-1; }
00048                         m_capacity = capacity; m_size = 0; }
00049         public:
00050                 inline bool Contains(int nodeId) const {
00051                         for(int i=0; i<m_size; i++) { if(m_arr[i]==nodeId) return true; } return false; }
00052         public:
00053                 inline void Push(int nodeId) { m_arr[m_size]=nodeId; m_size++; }
00054                 inline void Pop() { m_size--; m_arr[m_size]=-1; }
00055                 inline int Capacity() const { return m_capacity; }
00056                 inline int Size() const { return m_size; }
00057                 inline const TIntV &getVec() const { return m_v; }
00058                 inline int operator[](int i) const { return m_arr[i]; }
00059         };
00060 private:
00061         PNGraph m_graph;
00062         int m_nodes;
00063         int m_subGraphSz;
00064         TGraphCounter *m_functor;
00065 private:
00066         void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId);
00067         void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext);
00068 public: 
00069   TSubGraphEnum() { }
00070         //Graph must be normalized (vertex ids are 0,1,2,...)
00071         void GetSubGraphs(PNGraph &Graph, int SubGraphSz, TGraphCounter& Counter);
00072         void GetSubGraphs(PNGraph &Graph, int NId, int SubGraphSz, TGraphCounter& Counter);
00073 };
00074 // TGraphCounter must implement 
00075 // void operator()(const PNGraph &G, const TIntV &SubGraphNIdV);
00076 // which gets called whenever a new subgraph on nodes in SubGraphNIdV is identified
00077 
00079 // TSubGraphEnum implementation
00080 template <class TGraphCounter>
00081 void TSubGraphEnum<TGraphCounter>::GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId) {
00082         if(sg.Size() == m_subGraphSz) { (*m_functor)(m_graph, sg.getVec()); return; }
00083         //
00084         for(int i=0; i<ext.Capacity(); i++) {
00085                 while(ext[i] == false) {
00086                         i++;
00087                         if(i == ext.Capacity()) return;
00088                 }
00089                 //
00090                 int wId = i;
00091                 TNGraph::TNodeI wIt = m_graph->GetNI(wId);
00092                 int wDeg = wIt.GetDeg();
00093                 //
00094                 ext.Remove(wId);
00095                 //
00096                 TSSet newExt = ext;
00097                 TSSet newSgNbrs = sgNbrs;
00098                 for(int j=0; j<wDeg; j++) {
00099                         int nbrId = wIt.GetNbrNId(j);
00100                         if(nbrId > vId && !sgNbrs.IsKey(nbrId) && !sg.Contains(nbrId)) {
00101                                 newExt.Add(nbrId);
00102                                 newSgNbrs.Add(nbrId);
00103                         }
00104                 }
00105                 sg.Push(wId);
00106                 GetSubGraphs_recursive(sg, newSgNbrs, newExt, vId);
00107                 sg.Pop();
00108         }
00109 }
00110 
00111 template <class TGraphCounter>
00112 void TSubGraphEnum<TGraphCounter>::GetSubGraphs(PNGraph &Graph, int SubGraphSz, TGraphCounter &Functor) {
00113         m_graph = Graph;
00114         m_nodes = m_graph->GetNodes();
00115         m_subGraphSz = SubGraphSz;
00116         m_functor = &Functor;
00117         //
00118         TExeTm extime;
00119         for(TNGraph::TNodeI it=m_graph->BegNI(); it<m_graph->EndNI(); it++) {
00120                 int vId = it.GetId();
00121                 int vDeg = it.GetDeg();
00122                 //Subgraph
00123                 TSVec sg(SubGraphSz);
00124                 sg.Push(vId);
00125                 //Subgraph extension
00126                 TSSet ext(m_nodes);
00127                 for(int i=0; i<vDeg; i++) {
00128                         int nbrId = it.GetNbrNId(i);
00129                         if(nbrId > vId) 
00130                                 ext.Add(nbrId);
00131                 }
00132                 //Subgraph neighbours
00133                 TSSet sgNbrs = ext;
00134                 GetSubGraphs_recursive(sg, sgNbrs, ext, vId);
00135         }
00136         //printf("secs: %llf\n", extime.GetSecs());
00137 }
00138 
00139 template <class TGraphCounter>
00140 void TSubGraphEnum<TGraphCounter>::GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext) {
00141         if(sg.Size() == m_subGraphSz) { (*m_functor)(m_graph, sg.getVec()); return; }
00142         //
00143         for(int i=0; i<ext.Capacity(); i++) {
00144                 while(ext[i] == false) {
00145                         i++;
00146                         if(i == ext.Capacity()) return;
00147                 }
00148                 //
00149                 int wId = i;
00150                 TNGraph::TNodeI wIt = m_graph->GetNI(wId);
00151                 int wDeg = wIt.GetDeg();
00152                 //
00153                 ext.Remove(wId);
00154                 //
00155                 TSSet newExt = ext;
00156                 TSSet newSgNbrs = sgNbrs;
00157                 for(int j=0; j<wDeg; j++) {
00158                         int nbrId = wIt.GetNbrNId(j);
00159                         if(!sgNbrs.IsKey(nbrId) && !sg.Contains(nbrId)) {
00160                                 newExt.Add(nbrId);
00161                                 newSgNbrs.Add(nbrId);
00162                         }
00163                 }
00164                 sg.Push(wId);
00165                 GetSubGraphs_recursive(sg, newSgNbrs, newExt);
00166                 sg.Pop();
00167         }
00168 }
00169 
00170 template <class TGraphCounter>
00171 void TSubGraphEnum<TGraphCounter>::GetSubGraphs(PNGraph &Graph, int NId, int SubGraphSz, TGraphCounter &Functor) {
00172         m_graph = Graph;
00173         m_nodes = m_graph->GetNodes();
00174         m_subGraphSz = SubGraphSz;
00175         m_functor = &Functor;
00176         //
00177         TNGraph::TNodeI it=m_graph->GetNI(NId);
00178         int vId = NId;
00179         int vDeg = it.GetDeg();
00180         //Subgraph
00181         TSVec sg(SubGraphSz);
00182         sg.Push(vId);
00183         //Subgraph extension
00184         TSSet ext(m_nodes);
00185         for(int i=0; i<vDeg; i++) {
00186                 int nbrId = it.GetNbrNId(i);
00187                 ext.Add(nbrId);
00188         }
00189         //Subgraph neighbours
00190         TSSet sgNbrs = ext;
00191         //
00192         TExeTm extime;
00193         GetSubGraphs_recursive(sg, sgNbrs, ext);
00194         printf("secs: %llf\n", extime.GetSecs());
00195 }
00196 
00197 
00198 #endif