SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
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>

Collaboration diagram for TSubGraphsEnum:

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.

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().

                                                      {
  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");
  }
}

Here is the call graph for this function:

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().

                                {
  // 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);
}

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().

                                                {
  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());
}

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().

                                                                                   {
  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);
  }
}

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().

                                                 {
  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());
}

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(), THash< TKey, TDat, THashFunc >::AddKey(), THash< TKey, TDat, THashFunc >::DelKey(), EdgeH, TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), THash< TKey, TDat, THashFunc >::GetKeyV(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), THash< TKey, TDat, THashFunc >::IsKey(), NGraph, RecurBfs1(), SgV, and TVec< TVal, TSizeTy >::Sort().

                                                               {
  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);
    }
  }
}

Here is the call graph for this function:


Member Data Documentation

Definition at line 563 of file ghash.h.

Referenced by RecurBfs1().

Definition at line 562 of file ghash.h.

Referenced by EnumSubGraphs(), and Gen2Graphs().

Definition at line 564 of file ghash.h.

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

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: