Connected Sub-graph Enumeration. More...

#include <ghash.h>

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, TIntH >	EdgeH
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.

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

void TSubGraphsEnum::Gen2Graphs ( )

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

THash<TIntPr, TIntH> TSubGraphsEnum::EdgeH [private]

Definition at line 563 of file ghash.h.

TSimpleGraphV TSubGraphsEnum::NextSgV [private]

Definition at line 562 of file ghash.h.

PNGraph TSubGraphsEnum::NGraph [private]

Definition at line 564 of file ghash.h.

TSimpleGraphV TSubGraphsEnum::SgV [private]

Definition at line 562 of file ghash.h.

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

snap-core/ghash.h
snap-core/ghash.cpp

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation