#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, TIntH >	EdgeH
PNGraph	NGraph

Detailed Description

Connected Sub-graph Enumeration.

Definition at line 408 of file ghash.h.

Constructor & Destructor Documentation

TSubGraphsEnum::TSubGraphsEnum ( PNGraph Graph ) [inline]

Definition at line 414 of file ghash.h.

: NGraph(Graph) { }

Member Function Documentation

void TSubGraphsEnum::EnumSubGraphs ( const int & MaxEdges )

Definition at line 311 of file ghash.cpp.

References TVec< TVal >::Add(), TVec< TVal >::Clr(), TVec< TVal >::Gen(), Gen2Graphs(), TSimpleGraph::GetEdgeV(), TExeTm::GetTmStr(), TSimpleGraph::Join(), TVec< TVal >::Last(), TVec< TVal >::Len(), NextSgV, SgV, TVec< TVal >::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:

void TSubGraphsEnum::Gen2Graphs ( )

Definition at line 281 of file ghash.cpp.

References TVec< TVal >::Add(), TNGraph::BegNI(), TSimpleGraph::Dump(), TNGraph::EndNI(), TVec< TVal >::Gen(), TNGraph::GetEdges(), TSimpleGraph::GetEdgeV(), TVec< TVal >::Len(), Mn, TVec< TVal >::MoveFrom(), Mx, NextSgV, NGraph, SgV, TVec< TVal >::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 344 of file ghash.cpp.

References TNGraph::BegNI(), TVec< TVal >::Clr(), TNGraph::EndNI(), TExeTm::GetTmStr(), TVec< TVal >::Len(), NGraph, SgV, and TVec< TVal >::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 362 of file ghash.cpp.

References TVec< TVal >::Add(), TSimpleGraph::AddEdge(), TNGraph::TNodeI::GetId(), TNGraph::TNodeI::GetInDeg(), TNGraph::TNodeI::GetInNId(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::TNodeI::GetOutNId(), TVec< TVal >::Len(), NGraph, RecurBfs(), SgV, and TVec< TVal >::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 385 of file ghash.cpp.

References TNGraph::BegNI(), TVec< TVal >::Clr(), TNGraph::EndNI(), TExeTm::GetTmStr(), TVec< TVal >::Len(), NGraph, SgV, and TVec< TVal >::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 406 of file ghash.cpp.

References TVec< TVal >::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 >::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);
    }
  }
}