SNAP Library 2.1, User Reference  2013-09-25 10:47:25
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
TSubGraphsEnum Class Reference

Connected Sub-graph Enumeration. More...

#include <ghash.h>

List of all members.

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

Definition at line 566 of file ghash.h.

: NGraph(Graph) { }

Member Function Documentation

void TSubGraphsEnum::EnumSubGraphs ( const int &  MaxEdges)

Definition at line 312 of file ghash.cpp.

                                                      {
  TExeTm ExeTm;
  Gen2Graphs();
  printf("  %2d edge graphs:  %d\t[%s]\n", 2, SgV.Len(), ExeTm.GetTmStr());  ExeTm.Tick();
  //for (int i = 0; i < SgV.Len(); i++) { SgV[i].Dump(TStr::Fmt("  %d", i+1)); }
  //printf("**************************************************************\n");
  TSimpleGraph SimpleG;
  TIntPrV& EdgeV = SimpleG.GetEdgeV();
  // multiple edge sub-graphs
  for (int edges = 3; edges <= MaxEdges; edges++) {
    EdgeV.Clr();
    printf("  %2d edge graphs:", edges);
    for (int g1 = 0; g1 < SgV.Len()-1; g1++) {
      for (int g2 = g1+1; g2 < SgV.Len(); g2++) {
        if (SimpleG.Join(SgV[g1], SgV[g2])) { NextSgV.Add(SimpleG); }
      }
    }
    printf("  candidates: %8d [%s]", NextSgV.Len(), ExeTm.GetTmStr());  ExeTm.Tick();
    NextSgV.Sort();
    SgV.Gen(NextSgV.Len(), 0);
    SgV.Add(NextSgV[0]);
    for (int i = 1; i < NextSgV.Len(); i++) {
      if (SgV.Last() != NextSgV[i]) {
        SgV.Add(NextSgV[i]);
      }
    }
    NextSgV.Clr(false);
    printf("  total: %8d [%s]\n", SgV.Len(), ExeTm.GetTmStr());  ExeTm.Tick();
    //for (int i = 0; i < SgV.Len(); i++) { SgV[i].Dump(TStr::Fmt("  %d", i+1)); }
    //printf("**************************************************************\n");
  }
}

Definition at line 282 of file ghash.cpp.

                                {
  // singe edge sub-graphs
  SgV.Gen(NGraph->GetEdges(), 0);
  TSimpleGraph SimpleG;
  TIntPrV& EdgeV = SimpleG.GetEdgeV();
  EdgeV.Gen(1);
  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
    for (int e = 0; e < NI.GetOutDeg(); e++) {
      EdgeV[0] = TIntPr(NI.GetId(), NI.GetOutNId(e));
      SgV.Add(SimpleG);
    }
  }
  SgV.Sort();
  // two edge sub-graphs
  EdgeV.Gen(2);
  for (int g1 = 0; g1 < SgV.Len()-1; g1++) {
    const TIntPr& E1 = SgV[g1].GetEdgeV()[0];
    for (int g2 = g1+1; g2 < SgV.Len(); g2++) {
      const TIntPr& E2 = SgV[g2].GetEdgeV()[0];
      if (E1.Val2 == E2.Val1 || E1.Val1 == E2.Val2 || E1.Val1 == E2.Val1 || E1.Val2 == E2.Val2) {
        EdgeV[0] = TMath::Mn(E1, E2);
        EdgeV[1] = TMath::Mx(E1, E2);
        SimpleG.Dump();
        NextSgV.Add(SimpleG);
      }
    }
  }
  SgV.MoveFrom(NextSgV);
}
void TSubGraphsEnum::RecurBfs ( const int &  MxDepth)

Definition at line 345 of file ghash.cpp.

                                                {
  TExeTm ExeTm;
  SgV.Clr(true);
  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
    TSimpleGraph SimpleG;
    RecurBfs(NI.GetId(), MxDepth, SimpleG);
    //NGraph->DelNode(NI.GetId());
    printf(".");
  }
  printf("\ncandidates: %d\n", SgV.Len());
  SgV.Sort();
  int Cnt = 1;
  for (int i = 1; i < SgV.Len(); i++) {
    if (SgV[i-1] != SgV[i]) Cnt++;
  }
  printf("distinct:   %d\t[%s]\n", Cnt, ExeTm.GetTmStr());
}
void TSubGraphsEnum::RecurBfs ( const int &  NId,
const int &  Depth,
TSimpleGraph PrevG 
)

Definition at line 363 of file ghash.cpp.

                                                                                   {
  if (Depth == 0) {
    TIntPrV& EdgeV = PrevG();
    EdgeV.Sort();
    for (int i = 1; i < EdgeV.Len(); i++) {
      if (EdgeV[i-1] == EdgeV[i]) { return; }
    }
    SgV.Add(PrevG);
    return;
  }
  const TNGraph::TNodeI NI = NGraph ->GetNI(NId);
  for (int e = 0; e < NI.GetOutDeg(); e++) {
    TSimpleGraph CurG = PrevG;
    CurG.AddEdge(NI.GetId(), NI.GetOutNId(e));
    RecurBfs(NI.GetOutNId(e), Depth-1, CurG);
  }
  for (int e = 0; e < NI.GetInDeg(); e++) {
    TSimpleGraph CurG = PrevG;
    CurG.AddEdge(NI.GetInNId(e), NI.GetId());
    RecurBfs(NI.GetInNId(e), Depth-1, CurG);
  }
}
void TSubGraphsEnum::RecurBfs1 ( const int &  MxDepth)

Definition at line 386 of file ghash.cpp.

                                                 {
  TExeTm ExeTm;
  SgV.Clr(true);
  for (TNGraph::TNodeI NI = NGraph->BegNI(); NI < NGraph->EndNI(); NI++) {
    TSimpleGraph SimpleG;
    RecurBfs1(NI.GetId(), MxDepth);
    //NGraph->DelNode(NI.GetId());
    printf(".");
  }
  printf("candidates: %d\n", SgV.Len());
  SgV.Sort();
  int Cnt = 1;
  for (int i = 1; i < SgV.Len(); i++) {
    if (SgV[i-1]!=SgV[i]) {
      //SgV[i].Dump();
      Cnt++;
    }
  }
  printf("distinct:   %d\t[%s]\n", Cnt, ExeTm.GetTmStr());
}
void TSubGraphsEnum::RecurBfs1 ( const int &  NId,
const int &  Depth 
)

Definition at line 407 of file ghash.cpp.

                                                               {
  if (Depth == 0) {
    TIntPrV EdgeV;
    EdgeH.GetKeyV(EdgeV);
    EdgeV.Sort();
    SgV.Add(EdgeV);
    return;
  }
  const TNGraph::TNodeI NI = NGraph ->GetNI(NId);
  for (int e = 0; e < NI.GetOutDeg(); e++) {
    const TIntPr Edge(NId, NI.GetOutNId(e));
    if (! EdgeH.IsKey(Edge)) {
      EdgeH.AddKey(Edge);
      RecurBfs1(NI.GetOutNId(e), Depth-1);
      EdgeH.DelKey(Edge);
    }
  }
  for (int e = 0; e < NI.GetInDeg(); e++) {
    const TIntPr Edge(NI.GetInNId(e), NId);
    if (! EdgeH.IsKey(Edge)) {
      EdgeH.AddKey(Edge);
      RecurBfs1(NI.GetInNId(e), Depth-1);
      EdgeH.DelKey(Edge);
    }
  }
}

Member Data Documentation

Definition at line 563 of file ghash.h.

Definition at line 562 of file ghash.h.

Definition at line 564 of file ghash.h.

Definition at line 562 of file ghash.h.


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