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
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
TSubGraphEnum< TGraphCounter > Class Template Reference

#include <subgraphenum.h>

Collaboration diagram for TSubGraphEnum< TGraphCounter >:
Collaboration graph
[legend]

Classes

class  TSSet
 
class  TSVec
 

Public Member Functions

 TSubGraphEnum ()
 
void GetSubGraphs (PNGraph &Graph, int SubGraphSz, TGraphCounter &Counter)
 
void GetSubGraphs (PNGraph &Graph, int NId, int SubGraphSz, TGraphCounter &Counter)
 

Private Member Functions

void GetSubGraphs_recursive (TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId)
 
void GetSubGraphs_recursive (TSVec &sg, const TSSet &sgNbrs, TSSet &ext)
 

Private Attributes

PNGraph m_graph
 
int m_nodes
 
int m_subGraphSz
 
TGraphCounter * m_functor
 

Detailed Description

template<class TGraphCounter>
class TSubGraphEnum< TGraphCounter >

Definition at line 15 of file subgraphenum.h.

Constructor & Destructor Documentation

template<class TGraphCounter >
TSubGraphEnum< TGraphCounter >::TSubGraphEnum ( )
inline

Definition at line 69 of file subgraphenum.h.

69 { }

Member Function Documentation

template<class TGraphCounter >
void TSubGraphEnum< TGraphCounter >::GetSubGraphs ( PNGraph &  Graph,
int  SubGraphSz,
TGraphCounter &  Counter 
)

Definition at line 112 of file subgraphenum.h.

References TSubGraphEnum< TGraphCounter >::TSSet::Add(), TNGraph::GetNodes(), and TSubGraphEnum< TGraphCounter >::TSVec::Push().

112  {
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 }
TNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
TExeTm
Definition: tm.h:355
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
TSubGraphEnum::m_functor
TGraphCounter * m_functor
Definition: subgraphenum.h:64
TSubGraphEnum::GetSubGraphs_recursive
void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId)
Definition: subgraphenum.h:81
TNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TSubGraphEnum::m_graph
PNGraph m_graph
Definition: subgraphenum.h:61

Here is the call graph for this function:

template<class TGraphCounter >
void TSubGraphEnum< TGraphCounter >::GetSubGraphs ( PNGraph &  Graph,
int  NId,
int  SubGraphSz,
TGraphCounter &  Counter 
)

Definition at line 171 of file subgraphenum.h.

References TSubGraphEnum< TGraphCounter >::TSSet::Add(), TNGraph::TNodeI::GetDeg(), TNGraph::TNodeI::GetNbrNId(), TNGraph::GetNodes(), TExeTm::GetSecs(), and TSubGraphEnum< TGraphCounter >::TSVec::Push().

171  {
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 }
TNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:416
TExeTm
Definition: tm.h:355
TNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:548
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:499
TSubGraphEnum::m_functor
TGraphCounter * m_functor
Definition: subgraphenum.h:64
TNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:398
TSubGraphEnum::GetSubGraphs_recursive
void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId)
Definition: subgraphenum.h:81
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TExeTm::GetSecs
double GetSecs() const
Definition: tm.h:366
TSubGraphEnum::m_graph
PNGraph m_graph
Definition: subgraphenum.h:61

Here is the call graph for this function:

template<class TGraphCounter >
void TSubGraphEnum< TGraphCounter >::GetSubGraphs_recursive ( TSVec &  sg,
const TSSet &  sgNbrs,
TSSet &  ext,
int  vId 
)
private

Definition at line 81 of file subgraphenum.h.

References TSubGraphEnum< TGraphCounter >::TSSet::Add(), TSubGraphEnum< TGraphCounter >::TSSet::Capacity(), TSubGraphEnum< TGraphCounter >::TSVec::Contains(), TNGraph::TNodeI::GetDeg(), TNGraph::TNodeI::GetNbrNId(), TSubGraphEnum< TGraphCounter >::TSVec::getVec(), TSubGraphEnum< TGraphCounter >::TSSet::IsKey(), TSubGraphEnum< TGraphCounter >::TSVec::Pop(), TSubGraphEnum< TGraphCounter >::TSVec::Push(), TSubGraphEnum< TGraphCounter >::TSSet::Remove(), and TSubGraphEnum< TGraphCounter >::TSVec::Size().

81  {
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 }
TNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:416
TNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:398
TSubGraphEnum::GetSubGraphs_recursive
void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId)
Definition: subgraphenum.h:81
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TSubGraphEnum::m_graph
PNGraph m_graph
Definition: subgraphenum.h:61

Here is the call graph for this function:

template<class TGraphCounter >
void TSubGraphEnum< TGraphCounter >::GetSubGraphs_recursive ( TSVec &  sg,
const TSSet &  sgNbrs,
TSSet &  ext 
)
private

Definition at line 140 of file subgraphenum.h.

References TSubGraphEnum< TGraphCounter >::TSSet::Add(), TSubGraphEnum< TGraphCounter >::TSSet::Capacity(), TSubGraphEnum< TGraphCounter >::TSVec::Contains(), TNGraph::TNodeI::GetDeg(), TNGraph::TNodeI::GetNbrNId(), TSubGraphEnum< TGraphCounter >::TSVec::getVec(), TSubGraphEnum< TGraphCounter >::TSSet::IsKey(), TSubGraphEnum< TGraphCounter >::TSVec::Pop(), TSubGraphEnum< TGraphCounter >::TSVec::Push(), TSubGraphEnum< TGraphCounter >::TSSet::Remove(), and TSubGraphEnum< TGraphCounter >::TSVec::Size().

140  {
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 }
TNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:416
TNGraph::TNodeI::GetDeg
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:398
TSubGraphEnum::GetSubGraphs_recursive
void GetSubGraphs_recursive(TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId)
Definition: subgraphenum.h:81
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TSubGraphEnum::m_graph
PNGraph m_graph
Definition: subgraphenum.h:61

Here is the call graph for this function:

Member Data Documentation

template<class TGraphCounter >
TGraphCounter* TSubGraphEnum< TGraphCounter >::m_functor
private

Definition at line 64 of file subgraphenum.h.

template<class TGraphCounter >
PNGraph TSubGraphEnum< TGraphCounter >::m_graph
private

Definition at line 61 of file subgraphenum.h.

template<class TGraphCounter >
int TSubGraphEnum< TGraphCounter >::m_nodes
private

Definition at line 62 of file subgraphenum.h.

template<class TGraphCounter >
int TSubGraphEnum< TGraphCounter >::m_subGraphSz
private

Definition at line 63 of file subgraphenum.h.

The documentation for this class was generated from the following file: