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
Static Public Member Functions | Static Private Member Functions | List of all members
TGraphEnumUtils Class Reference

#include <graphcounter.h>

Static Public Member Functions

static bool IsEdge (const PNGraph &G, int SrcNId, int DstNId)
 
static void GetEdges (uint64 graphId, int nodes, TVec< TPair< int, int > > &edges)
 
static void GetNormalizedGraph (const PNGraph &G, PNGraph &nG)
 
static void GetIndGraph (const PNGraph &G, const TIntV &sg, PNGraph &indG)
 
static void GetGraph (uint64 graphId, int nodes, PNGraph &G)
 
static void GetIsoGraphs (uint64 graphId, int nodes, TVec< PNGraph > &isoG)
 
static void GetIsoGraphs (const PNGraph &G, TVec< PNGraph > &isoG)
 
static uint64 GraphId (const PNGraph &G)
 
static uint64 GraphId (const PNGraph &G, const TIntV &sg)
 
static uint64 GetMinAndGraphIds (const TVec< PNGraph > &isoG, TVec< uint64 > &graphIds)
 

Static Private Member Functions

static void GetNormalizedMap (const PNGraph &G, THash< TInt, TInt > &map)
 
static void GetPermutations (TIntV &v, int start, TVec< TIntV > &perms)
 

Detailed Description

Definition at line 79 of file graphcounter.h.

Member Function Documentation

void TGraphEnumUtils::GetEdges ( uint64  graphId,
int  nodes,
TVec< TPair< int, int > > &  edges 
)
static

Definition at line 190 of file graphcounter.cpp.

Referenced by GetIsoGraphs().

190  {
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 }
uint64
unsigned long long uint64
Definition: bd.h:38
TPair
Definition: ds.h:32
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the caller graph for this function:

void TGraphEnumUtils::GetGraph ( uint64  graphId,
int  nodes,
PNGraph &  G 
)
static

Definition at line 269 of file graphcounter.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), and TNGraph::Clr().

Referenced by TD34GraphCounter::GetGraph().

269  {
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 }
TPt::Clr
void Clr()
Definition: bd.h:502
uint64
unsigned long long uint64
Definition: bd.h:38

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetIndGraph ( const PNGraph &  G,
const TIntV &  sg,
PNGraph &  indG 
)
static

Definition at line 251 of file graphcounter.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::TNodeI::GetNbrNId(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::IsNode(), and TVec< TVal, TSizeTy >::Len().

Referenced by TDGHashGraphCounter::operator()().

251  {
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 }
TNGraph::TNodeI::GetNbrNId
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:420
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetIsoGraphs ( uint64  graphId,
int  nodes,
TVec< PNGraph > &  isoG 
)
static

Definition at line 202 of file graphcounter.cpp.

References TVec< TVal, TSizeTy >::Gen(), GetEdges(), GetPermutations(), TVec< TVal, TSizeTy >::Len(), and TNGraph::New().

Referenced by TDGraphCounter::operator()(), and TD34GraphCounter::TD34GraphCounter().

202  {
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 }
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TGraphEnumUtils::GetPermutations
static void GetPermutations(TIntV &v, int start, TVec< TIntV > &perms)
Definition: graphcounter.cpp:156
TGraphEnumUtils::GetEdges
static void GetEdges(uint64 graphId, int nodes, TVec< TPair< int, int > > &edges)
Definition: graphcounter.cpp:190
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetIsoGraphs ( const PNGraph &  G,
TVec< PNGraph > &  isoG 
)
static

Definition at line 227 of file graphcounter.cpp.

References TNGraph::BegEI(), TNGraph::EndEI(), TVec< TVal, TSizeTy >::Gen(), TNGraph::GetNodes(), GetPermutations(), TVec< TVal, TSizeTy >::Len(), and TNGraph::New().

227  {
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 }
TNGraph::New
static PNGraph New()
Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New().
Definition: graph.h:481
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TGraphEnumUtils::GetPermutations
static void GetPermutations(TIntV &v, int start, TVec< TIntV > &perms)
Definition: graphcounter.cpp:156
TNGraph::TEdgeI
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523

Here is the call graph for this function:

uint64 TGraphEnumUtils::GetMinAndGraphIds ( const TVec< PNGraph > &  isoG,
TVec< uint64 > &  graphIds 
)
static

Definition at line 311 of file graphcounter.cpp.

References TVec< TVal, TSizeTy >::Add(), GraphId(), IAssert, and TVec< TVal, TSizeTy >::Len().

Referenced by TDGraphCounter::operator()(), and TD34GraphCounter::TD34GraphCounter().

311  {
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
uint64
unsigned long long uint64
Definition: bd.h:38
TGraphEnumUtils::GraphId
static uint64 GraphId(const PNGraph &G)
Definition: graphcounter.cpp:285
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetNormalizedGraph ( const PNGraph &  G,
PNGraph &  nG 
)
static

Definition at line 172 of file graphcounter.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::BegEI(), TNGraph::EndEI(), THash< TKey, TDat, THashFunc >::GetDat(), TNGraph::GetNodes(), and GetNormalizedMap().

172  {
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 }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TGraphEnumUtils::GetNormalizedMap
static void GetNormalizedMap(const PNGraph &G, THash< TInt, TInt > &map)
Definition: graphcounter.cpp:147
TNGraph::TEdgeI
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430

Here is the call graph for this function:

void TGraphEnumUtils::GetNormalizedMap ( const PNGraph &  G,
THash< TInt, TInt > &  map 
)
staticprivate

Definition at line 147 of file graphcounter.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TNGraph::BegNI(), and TNGraph::EndNI().

Referenced by GetNormalizedGraph().

147  {
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 }
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetPermutations ( TIntV &  v,
int  start,
TVec< TIntV > &  perms 
)
staticprivate

Definition at line 156 of file graphcounter.cpp.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().

Referenced by GetIsoGraphs().

156  {
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 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TGraphEnumUtils::GetPermutations
static void GetPermutations(TIntV &v, int start, TVec< TIntV > &perms)
Definition: graphcounter.cpp:156
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

uint64 TGraphEnumUtils::GraphId ( const PNGraph &  G)
static

Definition at line 285 of file graphcounter.cpp.

References TNGraph::BegEI(), TNGraph::EndEI(), TNGraph::GetNodes(), and TMath::Pow2().

Referenced by GetMinAndGraphIds(), and TDGraphCounter::operator()().

285  {
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 }
TMath::Pow2
static uint Pow2(const int &pow)
Definition: xmath.h:24
TNGraph::TEdgeI
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
uint64
unsigned long long uint64
Definition: bd.h:38

Here is the call graph for this function:

Here is the caller graph for this function:

uint64 TGraphEnumUtils::GraphId ( const PNGraph &  G,
const TIntV &  sg 
)
static

Definition at line 298 of file graphcounter.cpp.

References IsEdge(), TVec< TVal, TSizeTy >::Len(), and TMath::Pow2().

298  {
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 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TMath::Pow2
static uint Pow2(const int &pow)
Definition: xmath.h:24
TGraphEnumUtils::IsEdge
static bool IsEdge(const PNGraph &G, int SrcNId, int DstNId)
Definition: graphcounter.h:84
uint64
unsigned long long uint64
Definition: bd.h:38

Here is the call graph for this function:

static bool TGraphEnumUtils::IsEdge ( const PNGraph &  G,
int  SrcNId,
int  DstNId 
)
inlinestatic

Definition at line 84 of file graphcounter.h.

References TNGraph::IsEdge().

Referenced by TD3Graph::getId(), TD4Graph::getId(), and GraphId().

84  {
85  // JURE return G->GetNodeC(SrcNId).IsOutNId(DstNId);
86  return G->IsEdge(SrcNId, DstNId, true);
87  }

Here is the call graph for this function:

Here is the caller graph for this function:

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