SNAP Library 3.0, User Reference  2016-07-20 17:56:49
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
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.

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:574
void TGraphEnumUtils::GetGraph ( uint64  graphId,
int  nodes,
PNGraph &  G 
)
static

Definition at line 269 of file graphcounter.cpp.

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 }
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
uint64
unsigned long long uint64
Definition: bd.h:38
TNGraph::Clr
void Clr()
Deletes all nodes and edges from the graph.
Definition: graph.h:532
void TGraphEnumUtils::GetIndGraph ( const PNGraph &  G,
const TIntV &  sg,
PNGraph &  indG 
)
static

Definition at line 251 of file graphcounter.cpp.

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:376
TNGraph::GetNI
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
TNGraph::IsNode
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:477
TNGraph::TNodeI::GetOutDeg
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:362
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
void TGraphEnumUtils::GetIsoGraphs ( uint64  graphId,
int  nodes,
TVec< PNGraph > &  isoG 
)
static

Definition at line 202 of file graphcounter.cpp.

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:425
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
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:495
void TGraphEnumUtils::GetIsoGraphs ( const PNGraph &  G,
TVec< PNGraph > &  isoG 
)
static

Definition at line 227 of file graphcounter.cpp.

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:425
TNGraph::EndEI
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:516
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TNGraph::BegEI
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:514
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
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:386
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
uint64 TGraphEnumUtils::GetMinAndGraphIds ( const TVec< PNGraph > &  isoG,
TVec< uint64 > &  graphIds 
)
static

Definition at line 311 of file graphcounter.cpp.

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:547
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:574
void TGraphEnumUtils::GetNormalizedGraph ( const PNGraph &  G,
PNGraph &  nG 
)
static

Definition at line 172 of file graphcounter.cpp.

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 }
TNGraph::EndEI
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:516
TNGraph::BegEI
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:514
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
TNGraph::AddNode
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:236
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
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:386
TNGraph::AddEdge
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge from node IDs SrcNId to node DstNId to the graph.
Definition: graph.cpp:321
void TGraphEnumUtils::GetNormalizedMap ( const PNGraph &  G,
THash< TInt, TInt > &  map 
)
staticprivate

Definition at line 147 of file graphcounter.cpp.

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::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:479
TNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:481
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:339
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
void TGraphEnumUtils::GetPermutations ( TIntV &  v,
int  start,
TVec< TIntV > &  perms 
)
staticprivate

Definition at line 156 of file graphcounter.cpp.

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:547
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:574
uint64 TGraphEnumUtils::GraphId ( const PNGraph &  G)
static

Definition at line 285 of file graphcounter.cpp.

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 }
TNGraph::EndEI
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:516
TNGraph::BegEI
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:514
TNGraph::GetNodes
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:438
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:386
uint64
unsigned long long uint64
Definition: bd.h:38
uint64 TGraphEnumUtils::GraphId ( const PNGraph &  G,
const TIntV &  sg 
)
static

Definition at line 298 of file graphcounter.cpp.

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:547
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
static bool TGraphEnumUtils::IsEdge ( const PNGraph &  G,
int  SrcNId,
int  DstNId 
)
inlinestatic

Definition at line 84 of file graphcounter.h.

84  {
85  // JURE return G->GetNodeC(SrcNId).IsOutNId(DstNId);
86  return G->IsEdge(SrcNId, DstNId, true);
87  }
TNGraph::IsEdge
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
The documentation for this class was generated from the following files: