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
TSubGraphsEnum Class Reference

Connected Sub-graph Enumeration. More...

#include <ghash.h>

Collaboration diagram for TSubGraphsEnum:

Public Member Functions

 TSubGraphsEnum (PNGraph Graph)
 
void Gen2Graphs ()
 
void EnumSubGraphs (const int &MaxEdges)
 
void RecurBfs (const int &MxDepth)
 
void RecurBfs (const int &NId, const int &Depth, TSimpleGraph &PrevG)
 
void RecurBfs1 (const int &MxDepth)
 
void RecurBfs1 (const int &NId, const int &Depth)
 

Private Attributes

TSimpleGraphV SgV
 
TSimpleGraphV NextSgV
 
THash< TIntPr, TIntHEdgeH
 
PNGraph NGraph
 

Detailed Description

Connected Sub-graph Enumeration.

Definition at line 560 of file ghash.h.

Constructor & Destructor Documentation

TSubGraphsEnum::TSubGraphsEnum ( PNGraph  Graph)
inline

Definition at line 566 of file ghash.h.

566 : NGraph(Graph) { }
PNGraph NGraph
Definition: ghash.h:564

Member Function Documentation

void TSubGraphsEnum::EnumSubGraphs ( const int &  MaxEdges)

Definition at line 312 of file ghash.cpp.

References TVec< TVal, TSizeTy >::Add(), TVec< TVal, TSizeTy >::Clr(), TVec< TVal, TSizeTy >::Gen(), Gen2Graphs(), TSimpleGraph::GetEdgeV(), TExeTm::GetTmStr(), TSimpleGraph::Join(), TVec< TVal, TSizeTy >::Last(), TVec< TVal, TSizeTy >::Len(), NextSgV, SgV, TVec< TVal, TSizeTy >::Sort(), and TExeTm::Tick().

312  {
313  TExeTm ExeTm;
314  Gen2Graphs();
315  printf(" %2d edge graphs: %d\t[%s]\n", 2, SgV.Len(), ExeTm.GetTmStr()); ExeTm.Tick();
316  //for (int i = 0; i < SgV.Len(); i++) { SgV[i].Dump(TStr::Fmt(" %d", i+1)); }
317  //printf("**************************************************************\n");
318  TSimpleGraph SimpleG;
319  TIntPrV& EdgeV = SimpleG.GetEdgeV();
320  // multiple edge sub-graphs
321  for (int edges = 3; edges <= MaxEdges; edges++) {
322  EdgeV.Clr();
323  printf(" %2d edge graphs:", edges);
324  for (int g1 = 0; g1 < SgV.Len()-1; g1++) {
325  for (int g2 = g1+1; g2 < SgV.Len(); g2++) {
326  if (SimpleG.Join(SgV[g1], SgV[g2])) { NextSgV.Add(SimpleG); }
327  }
328  }
329  printf(" candidates: %8d [%s]", NextSgV.Len(), ExeTm.GetTmStr()); ExeTm.Tick();
330  NextSgV.Sort();
331  SgV.Gen(NextSgV.Len(), 0);
332  SgV.Add(NextSgV[0]);
333  for (int i = 1; i < NextSgV.Len(); i++) {
334  if (SgV.Last() != NextSgV[i]) {
335  SgV.Add(NextSgV[i]);
336  }
337  }
338  NextSgV.Clr(false);
339  printf(" total: %8d [%s]\n", SgV.Len(), ExeTm.GetTmStr()); ExeTm.Tick();
340  //for (int i = 0; i < SgV.Len(); i++) { SgV[i].Dump(TStr::Fmt(" %d", i+1)); }
341  //printf("**************************************************************\n");
342  }
343 }
Definition: tm.h:355
TSimpleGraphV NextSgV
Definition: ghash.h:562
Simple directed/undirected graph defined by its edges.
Definition: ghash.h:539
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntPrV & GetEdgeV()
Definition: ghash.h:551
TSimpleGraphV SgV
Definition: ghash.h:562
bool Join(const TSimpleGraph &G1, const TSimpleGraph &G2)
Definition: ghash.cpp:233
const char * GetTmStr() const
Definition: tm.h:370
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void Tick()
Definition: tm.h:364
void Gen2Graphs()
Definition: ghash.cpp:282
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
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:

void TSubGraphsEnum::Gen2Graphs ( )

Definition at line 282 of file ghash.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegNI(), TSimpleGraph::Dump(), TNGraph::EndNI(), TVec< TVal, TSizeTy >::Gen(), TNGraph::GetEdges(), TSimpleGraph::GetEdgeV(), TVec< TVal, TSizeTy >::Len(), TMath::Mn(), TVec< TVal, TSizeTy >::MoveFrom(), TMath::Mx(), NextSgV, NGraph, SgV, TVec< TVal, TSizeTy >::Sort(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

Referenced by EnumSubGraphs().

282  {
283  // singe edge sub-graphs
284  SgV.Gen(NGraph->GetEdges(), 0);
285  TSimpleGraph SimpleG;
286  TIntPrV& EdgeV = SimpleG.GetEdgeV();
287  EdgeV.Gen(1);
288  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
289  for (int e = 0; e < NI.GetOutDeg(); e++) {
290  EdgeV[0] = TIntPr(NI.GetId(), NI.GetOutNId(e));
291  SgV.Add(SimpleG);
292  }
293  }
294  SgV.Sort();
295  // two edge sub-graphs
296  EdgeV.Gen(2);
297  for (int g1 = 0; g1 < SgV.Len()-1; g1++) {
298  const TIntPr& E1 = SgV[g1].GetEdgeV()[0];
299  for (int g2 = g1+1; g2 < SgV.Len(); g2++) {
300  const TIntPr& E2 = SgV[g2].GetEdgeV()[0];
301  if (E1.Val2 == E2.Val1 || E1.Val1 == E2.Val2 || E1.Val1 == E2.Val1 || E1.Val2 == E2.Val2) {
302  EdgeV[0] = TMath::Mn(E1, E2);
303  EdgeV[1] = TMath::Mx(E1, E2);
304  SimpleG.Dump();
305  NextSgV.Add(SimpleG);
306  }
307  }
308  }
310 }
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
TSimpleGraphV NextSgV
Definition: ghash.h:562
Simple directed/undirected graph defined by its edges.
Definition: ghash.h:539
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:313
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntPrV & GetEdgeV()
Definition: ghash.h:551
TSimpleGraphV SgV
Definition: ghash.h:562
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void Dump(const TStr &Desc=TStr()) const
Definition: ghash.cpp:274
Definition: ds.h:32
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1073
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
PNGraph NGraph
Definition: ghash.h:564

Here is the call graph for this function:

Here is the caller graph for this function:

void TSubGraphsEnum::RecurBfs ( const int &  MxDepth)

Definition at line 345 of file ghash.cpp.

References TNGraph::BegNI(), TVec< TVal, TSizeTy >::Clr(), TNGraph::EndNI(), TExeTm::GetTmStr(), TVec< TVal, TSizeTy >::Len(), NGraph, SgV, and TVec< TVal, TSizeTy >::Sort().

Referenced by RecurBfs().

345  {
346  TExeTm ExeTm;
347  SgV.Clr(true);
348  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
349  TSimpleGraph SimpleG;
350  RecurBfs(NI.GetId(), MxDepth, SimpleG);
351  //NGraph->DelNode(NI.GetId());
352  printf(".");
353  }
354  printf("\ncandidates: %d\n", SgV.Len());
355  SgV.Sort();
356  int Cnt = 1;
357  for (int i = 1; i < SgV.Len(); i++) {
358  if (SgV[i-1] != SgV[i]) Cnt++;
359  }
360  printf("distinct: %d\t[%s]\n", Cnt, ExeTm.GetTmStr());
361 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
Definition: tm.h:355
Simple directed/undirected graph defined by its edges.
Definition: ghash.h:539
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSimpleGraphV SgV
Definition: ghash.h:562
const char * GetTmStr() const
Definition: tm.h:370
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void RecurBfs(const int &MxDepth)
Definition: ghash.cpp:345
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
PNGraph NGraph
Definition: ghash.h:564

Here is the call graph for this function:

Here is the caller graph for this function:

void TSubGraphsEnum::RecurBfs ( const int &  NId,
const int &  Depth,
TSimpleGraph PrevG 
)

Definition at line 363 of file ghash.cpp.

References TVec< TVal, TSizeTy >::Add(), TSimpleGraph::AddEdge(), TNGraph::TNodeI::GetId(), TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TVec< TVal, TSizeTy >::Len(), NGraph, RecurBfs(), SgV, and TVec< TVal, TSizeTy >::Sort().

363  {
364  if (Depth == 0) {
365  TIntPrV& EdgeV = PrevG();
366  EdgeV.Sort();
367  for (int i = 1; i < EdgeV.Len(); i++) {
368  if (EdgeV[i-1] == EdgeV[i]) { return; }
369  }
370  SgV.Add(PrevG);
371  return;
372  }
373  const TNGraph::TNodeI NI = NGraph ->GetNI(NId);
374  for (int e = 0; e < NI.GetOutDeg(); e++) {
375  TSimpleGraph CurG = PrevG;
376  CurG.AddEdge(NI.GetId(), NI.GetOutNId(e));
377  RecurBfs(NI.GetOutNId(e), Depth-1, CurG);
378  }
379  for (int e = 0; e < NI.GetInDeg(); e++) {
380  TSimpleGraph CurG = PrevG;
381  CurG.AddEdge(NI.GetInNId(e), NI.GetId());
382  RecurBfs(NI.GetInNId(e), Depth-1, CurG);
383  }
384 }
Simple directed/undirected graph defined by its edges.
Definition: ghash.h:539
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSimpleGraphV SgV
Definition: ghash.h:562
void AddEdge(const int &SrcNId, const int &DstNId)
Definition: ghash.h:549
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
void RecurBfs(const int &MxDepth)
Definition: ghash.cpp:345
int GetId() const
Returns ID of the current node.
Definition: graph.h:400
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:404
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:412
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
PNGraph NGraph
Definition: ghash.h:564

Here is the call graph for this function:

void TSubGraphsEnum::RecurBfs1 ( const int &  MxDepth)

Definition at line 386 of file ghash.cpp.

References TNGraph::BegNI(), TVec< TVal, TSizeTy >::Clr(), TNGraph::EndNI(), TExeTm::GetTmStr(), TVec< TVal, TSizeTy >::Len(), NGraph, SgV, and TVec< TVal, TSizeTy >::Sort().

Referenced by RecurBfs1().

386  {
387  TExeTm ExeTm;
388  SgV.Clr(true);
389  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
390  TSimpleGraph SimpleG;
391  RecurBfs1(NI.GetId(), MxDepth);
392  //NGraph->DelNode(NI.GetId());
393  printf(".");
394  }
395  printf("candidates: %d\n", SgV.Len());
396  SgV.Sort();
397  int Cnt = 1;
398  for (int i = 1; i < SgV.Len(); i++) {
399  if (SgV[i-1]!=SgV[i]) {
400  //SgV[i].Dump();
401  Cnt++;
402  }
403  }
404  printf("distinct: %d\t[%s]\n", Cnt, ExeTm.GetTmStr());
405 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
Definition: tm.h:355
Simple directed/undirected graph defined by its edges.
Definition: ghash.h:539
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSimpleGraphV SgV
Definition: ghash.h:562
const char * GetTmStr() const
Definition: tm.h:370
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
void RecurBfs1(const int &MxDepth)
Definition: ghash.cpp:386
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
PNGraph NGraph
Definition: ghash.h:564

Here is the call graph for this function:

Here is the caller graph for this function:

void TSubGraphsEnum::RecurBfs1 ( const int &  NId,
const int &  Depth 
)

Definition at line 407 of file ghash.cpp.

References TVec< TVal, TSizeTy >::Add(), EdgeH, TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), NGraph, RecurBfs1(), SgV, and TVec< TVal, TSizeTy >::Sort().

407  {
408  if (Depth == 0) {
409  TIntPrV EdgeV;
410  EdgeH.GetKeyV(EdgeV);
411  EdgeV.Sort();
412  SgV.Add(EdgeV);
413  return;
414  }
415  const TNGraph::TNodeI NI = NGraph ->GetNI(NId);
416  for (int e = 0; e < NI.GetOutDeg(); e++) {
417  const TIntPr Edge(NId, NI.GetOutNId(e));
418  if (! EdgeH.IsKey(Edge)) {
419  EdgeH.AddKey(Edge);
420  RecurBfs1(NI.GetOutNId(e), Depth-1);
421  EdgeH.DelKey(Edge);
422  }
423  }
424  for (int e = 0; e < NI.GetInDeg(); e++) {
425  const TIntPr Edge(NI.GetInNId(e), NId);
426  if (! EdgeH.IsKey(Edge)) {
427  EdgeH.AddKey(Edge);
428  RecurBfs1(NI.GetInNId(e), Depth-1);
429  EdgeH.DelKey(Edge);
430  }
431  }
432 }
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
TSimpleGraphV SgV
Definition: ghash.h:562
THash< TIntPr, TIntH > EdgeH
Definition: ghash.h:563
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
Definition: ds.h:32
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
void RecurBfs1(const int &MxDepth)
Definition: ghash.cpp:386
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
int GetInDeg() const
Returns in-degree of the current node.
Definition: graph.h:404
int GetInNId(const int &NodeN) const
Returns ID of NodeN-th in-node (the node pointing to the current node).
Definition: graph.h:412
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
PNGraph NGraph
Definition: ghash.h:564

Here is the call graph for this function:

Member Data Documentation

THash<TIntPr, TIntH> TSubGraphsEnum::EdgeH
private

Definition at line 563 of file ghash.h.

Referenced by RecurBfs1().

TSimpleGraphV TSubGraphsEnum::NextSgV
private

Definition at line 562 of file ghash.h.

Referenced by EnumSubGraphs(), and Gen2Graphs().

PNGraph TSubGraphsEnum::NGraph
private

Definition at line 564 of file ghash.h.

Referenced by Gen2Graphs(), RecurBfs(), and RecurBfs1().

TSimpleGraphV TSubGraphsEnum::SgV
private

Definition at line 562 of file ghash.h.

Referenced by EnumSubGraphs(), Gen2Graphs(), RecurBfs(), and RecurBfs1().


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