SNAP Library 2.0, User 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
ghash.h
Go to the documentation of this file.
00001 //#//////////////////////////////////////////////
00003 
00007 class TGraphKey {
00008 public:
00009   static const int RoundTo;
00010 private:
00011 public:
00012   TInt Nodes;
00013   TIntPrV EdgeV;  // renumbers the graph (node Ids 0..nodes-1)
00014   TFltV SigV;     // signature (for hashing)
00015   TInt VariantId; // graphs can have the same signature but are not-isomorphic. VariantId starts with 1.
00016 public:
00017   TGraphKey() : Nodes(-1), EdgeV(), SigV(), VariantId(0) { }
00018   TGraphKey(const TSFltV& GraphSigV);
00019   TGraphKey(const TIntV& GraphSigV);
00020   TGraphKey(const TFltV& GraphSigV);
00021   TGraphKey(const TGraphKey& GraphKey);
00022   TGraphKey(TSIn& SIn);
00023   void Save(TSOut& SOut) const;
00024   TGraphKey& operator = (const TGraphKey& GraphKey);
00025   bool operator == (const TGraphKey& GraphKey) const { return SigV==GraphKey.SigV && VariantId==GraphKey.VariantId; }
00026 
00027   int GetPrimHashCd() const { return abs(SigV.GetPrimHashCd() ^ VariantId); }
00028   int GetSecHashCd() const { return abs(SigV.GetSecHashCd() ^ VariantId<<8); }
00029 
00031   int GetNodes() const { return Nodes; }
00033   int GetEdges() const { return EdgeV.Len(); }
00035 
00040   int GetSigLen() const { return SigV.Len(); }
00042 
00045   int GetVariant() const { return VariantId; }
00047   void SetVariant(const int& Variant) { VariantId = Variant; }
00049   void SetEdgeV(const TIntPrV& EdgeIdV) { EdgeV = EdgeIdV; }
00050 
00052   PNGraph GetNGraph() const;
00054 
00056   void TakeGraph(const PNGraph& Graph);
00058 
00061   void TakeGraph(const PNGraph& Graph, TIntPrV& NodeMap);
00063 
00065   void TakeSig(const PNGraph& Graph, const int& MnSvdGraph, const int& MxSvdGraph);
00066   
00068   void SaveTxt(FILE *F) const;
00070 
00072   void SaveGViz(const TStr& OutFNm, const TStr& Desc = TStr(), const TStr& NodeAttrs="", const int& Size=-1) const;
00074 
00076   void DrawGViz(const TStr& OutFNm, const TStr& Desc = TStr(), const TStr& NodeAttrs="", const int& Size=-1) const;
00077 
00079 
00082   static bool IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TIntV& NodeIdMap);
00084   static bool IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TVec<TIntV>& NodeIdMapV);
00086   static bool IsIsomorph(const TGraphKey& Key1, const TGraphKey& Key2, const TVec<TIntV>& NodeIdMapV, int& IsoPermId);
00087 };
00088 
00089 //#//////////////////////////////////////////////
00091 
00102 template <class TDat>
00103 class TGHash {
00104 public:
00105   typedef typename THash<TGraphKey, TDat>::TIter TIter;
00106 private:
00107   TInt MxIsoCheck;     // maximum graph size for which we perform brute force graph isomorphism check
00108   TInt MxSvdGraph;     // maximum graph size for which we perform SVD-based approximate isomorphism check
00109   THash<TInt, TVec<TIntV> > GSzToPermH; // Graph size to a vector of all node permutations (for graphs of up to MxIsoCkeck nodes)
00110   TBool HashOnlyTrees; // hashing only trees (exact isomorphism test)
00111   THash<TGraphKey, TDat> GraphH;
00112 private:
00113   void InitPermutations();
00114   int IsGetKeyId(const PNGraph& Graph) const;
00115   int IsGetKeyId(const PNGraph& Graph, TGraphKey& GKey) const;
00116   int IsGetKeyId(const PNGraph& Graph, TGraphKey& GKey, TIntPrV& NodeMap) const;
00117 public:
00119 
00126   TGHash(const bool& HashTrees, const int& MaxIsoCheck=8, const int& MaxSvdGraph=500);
00127   TGHash(TSIn& SIn);
00128   void Save(TSOut& SOut) const;
00129 
00131   const TDat& operator [] (const int& KeyId) const { return GraphH[KeyId]; }
00133   TDat& operator [] (const int& KeyId) { return GraphH[KeyId]; }
00135   const TDat& operator () (const TGraphKey& Key) const { return GraphH.GetDat(Key); }
00137   TDat& operator () (const TGraphKey& Key) { return GraphH.GetDat(Key); }
00139   TIter BegI() const { return GraphH.BegI(); }
00141   TIter EndI() const { return GraphH.EndI(); }
00143   TIter GetI(const int& KeyId) const  { return GraphH.GetI(KeyId); }
00144 
00146   bool HashTrees() const { return HashOnlyTrees; }
00147 
00149   void Gen(const int& ExpectVals) { GraphH.Gen(ExpectVals); }
00151 
00154   void Clr(const bool& DoDel=true, const int& NoDelLim=-1) { GraphH.Clr(DoDel, NoDelLim); }
00156   bool Empty() const { return GraphH.Empty(); }
00158   int Len() const {  return GraphH.Len(); }
00160   int GetPorts() const { return GraphH.GetPorts(); }
00162   bool IsAutoSize() const { return GraphH.IsAutoSize(); }
00164   int GetMxKeyIds() const { return GraphH.GetMxKeyIds(); }
00166 
00168   bool IsKeyIdEqKeyN() const { return GraphH.IsKeyIdEqKeyN(); }
00169 
00171 
00173   int AddKey(const PNGraph& Graph);
00175 
00177   TDat& AddDat(const PNGraph& Graph) { return GraphH[AddKey(Graph)]; }
00179 
00181   TDat& AddDat(const PNGraph& Graph, const TDat& Dat) { return GraphH[AddKey(Graph)] = Dat; }
00182 
00184   bool IsKey(const PNGraph& Graph) const { int k=IsGetKeyId(Graph); return k!=-1; }
00186 
00188   int GetKeyId(const PNGraph& Graph) const { return IsGetKeyId(Graph); }
00190 
00192   const TDat& GetDat(const PNGraph& Graph) const { return GraphH[GetKeyId(Graph)]; }
00194 
00196   TDat& GetDat(const PNGraph& Graph) { return GraphH[GetKeyId(Graph)]; }
00197 
00199   const TGraphKey& GetKey(const int& KeyId) const { return GraphH.GetKey(KeyId); }
00201 
00203   int GetKeyId(const TGraphKey& Key) const { return GraphH.GetKeyId(Key); }
00205   bool IsKey(const TGraphKey& Key) const { return GraphH.IsKey(Key); }
00207   bool IsKey(const TGraphKey& Key, int& KeyId) const { return GraphH.IsKey(Key, KeyId); }
00209   bool IsKeyId(const int& KeyId) const { return GraphH.IsKeyId(KeyId); }
00211 
00213   const TDat& GetDat(const TGraphKey& Key) const { return GraphH.GetDat(Key); }
00215 
00217   TDat& GetDat(const TGraphKey& Key) { return GraphH.GetDat(Key); }
00219 
00221   const TDat& GetDatId(const int& KeyId) const { return GraphH[KeyId]; }
00223 
00225   TDat& GetDatId(const int& KeyId) { return GraphH[KeyId]; }
00226 
00228   void GetKeyDat(const int& KeyId, TGraphKey& Key, TDat& Dat) const { GraphH.GetKeyDat(KeyId, Key, Dat); }
00230   bool IsKeyGetDat(const TGraphKey& Key, TDat& Dat) const { return GraphH.IsKeyGetDat(Key, Dat); }
00231 
00233 
00235   bool GetNodeMap(const PNGraph& Graph, TIntPrV& NodeMapV) const;
00237 
00239   bool GetNodeMap(const PNGraph& Graph, TIntPrV& NodeMapV, int& KeyId) const;
00240 
00242 
00245   int FFirstKeyId() const { return 0-1; }
00247 
00250   bool FNextKeyId(int& KeyId) const { return GraphH.FNextKeyId(KeyId); }
00252   void GetKeyV(TVec<TGraphKey>& KeyV) const { GraphH.GetKeyV(KeyV); }
00254   void GetDatV(TVec<TDat>& DatV) const { GraphH.GetDatV(DatV); }
00256 
00258   void GetKeyIdByDat(TIntV& KeyIdV, const bool& Asc = true) const;
00260 
00263   void GetKeyIdByGSz(TIntV& KeyIdV, const bool& Asc = true) const;
00265   void GetKeyDatPrV(TVec<TPair<TGraphKey, TDat> >& KeyDatPrV) const { GraphH.GetKeyDatPrV(KeyDatPrV); }
00267   void GetDatKeyPrV(TVec<TPair<TDat, TGraphKey> >& DatKeyPrV) const { GraphH.GetDatKeyPrV(DatKeyPrV); }
00268 
00270 
00272   void Defrag() { GraphH.Defrag(); }
00274   void Pack() { GraphH.Pack(); }
00275 
00277   void DrawGViz(const int& KeyId, const TStr& OutFNmPref, const TStr& OutputType = "gif", TStr Desc="") const;
00279   void DrawGViz(const TIntV& KeyIdV, const TStr& OutFNmPref, const TStr& OutputType = "gif") const;
00281   void SaveTxt(const TStr& OutFNm, const TStr& Desc, const TStr& DatColNm, const bool& SortByKeyVal=true) const;
00283   void SaveDetailTxt(const TStr& OutFNm, const TStr& Desc, const TStr& DatColNm) const;
00284 };
00285 
00286 template <class TDat>
00287 void TGHash<TDat>::InitPermutations() {
00288   GSzToPermH.Clr();
00289   for (int nodes = 2; nodes <= MxIsoCheck; nodes++) {
00290     TVec<TIntV> NodePermutationV;
00291     TIntV NodeIdV(nodes, 0);
00292     for (int i = 0; i < nodes; i++)  NodeIdV.Add(i);
00293     NodeIdV.Pack();
00294     NodePermutationV.Add(NodeIdV);
00295     while (NodeIdV.NextPerm()) {
00296       NodePermutationV.Add(NodeIdV);
00297     }
00298     NodePermutationV.Pack();
00299     GSzToPermH.AddDat(nodes, NodePermutationV);
00300   }
00301 }
00302 
00303 template <class TDat>
00304 TGHash<TDat>::TGHash(const bool& HashTrees, const int& MaxIsoCheck, const int& MaxSvdGraph) :
00305  MxIsoCheck(MaxIsoCheck), MxSvdGraph(MaxSvdGraph), GSzToPermH(), HashOnlyTrees(HashTrees), GraphH() {
00306   if (! HashTrees) {
00307     InitPermutations();
00308   }
00309 }
00310 
00311 template <class TDat>
00312 TGHash<TDat>::TGHash(TSIn& SIn) : MxIsoCheck(SIn), MxSvdGraph(SIn), GSzToPermH(), HashOnlyTrees(SIn), GraphH(SIn) {
00313   if (! HashOnlyTrees) {
00314     InitPermutations();
00315   }
00316 }
00317 
00318 template <class TDat>
00319 void TGHash<TDat>::Save(TSOut& SOut) const {
00320   MxIsoCheck.Save(SOut);
00321   MxSvdGraph.Save(SOut);
00322   HashOnlyTrees.Save(SOut);
00323   GraphH.Save(SOut);
00324 }
00325 
00326 template <class TDat>
00327 int TGHash<TDat>::AddKey(const PNGraph& Graph) {
00328   if (HashOnlyTrees) {
00329     int RootNId;  IAssert(TSnap::IsTree(Graph, RootNId));
00330     TIntV TreeSig;  TSnap::GetTreeSig(Graph, RootNId, TreeSig);
00331     TGraphKey GKey(TreeSig);
00332     const int KeyId = GraphH.GetKeyId(GKey);
00333     if (KeyId == -1) {
00334       GKey.TakeGraph(Graph);
00335       return GraphH.AddKey(GKey);
00336     }
00337     return KeyId;
00338   } else {
00339     TGraphKey GKey;
00340     GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph); // get signature
00341     const int Nodes = GKey.GetNodes();
00342     if (Nodes > 2 && Nodes <= MxIsoCheck) {
00343       GKey.TakeGraph(Graph);
00344       // Check all variants with same signature
00345       for (int variant = 1; ; variant++) {
00346         GKey.SetVariant(variant);
00347         int KeyId = GraphH.GetKeyId(GKey);
00348         if (KeyId == -1) { // Key of such signature and variant does not exist yet.
00349           KeyId = GraphH.AddKey(GKey);
00350           return KeyId;
00351         }
00352         if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes))) { // Graph isomorphism test
00353           return KeyId;  // Found isomorphic graph.
00354         }
00355       }
00356     } else {
00357       const int KeyId = GraphH.GetKeyId(GKey);
00358       if (KeyId == -1) {
00359         GKey.TakeGraph(Graph);
00360         return GraphH.AddKey(GKey);
00361       }
00362       return KeyId;
00363     }
00364   }
00365   Fail;
00366   return -1;
00367 }
00368 
00369 template <class TDat>
00370 int TGHash<TDat>::IsGetKeyId(const PNGraph& Graph) const {
00371   TGraphKey GKey;
00372   return IsGetKeyId(Graph, GKey);
00373 }
00374 
00375 template <class TDat>
00376 int TGHash<TDat>::IsGetKeyId(const PNGraph& Graph, TGraphKey& GKey) const {
00377   if (HashOnlyTrees) {
00378     // For trees we perform exact isomorshism test based on graph signatures
00379     int RootNId;  IAssert(TSnap::IsTree(Graph, RootNId));
00380     TIntV TreeSig;  TSnap::GetTreeSig(Graph, RootNId, TreeSig);
00381     GKey = TGraphKey(TreeSig);
00382     const int KeyId = GraphH.GetKeyId(GKey);
00383     return KeyId;
00384   } else {
00385     // For small graphs  of less than MxIsoCheck nodes we perform brute force isomorphism checking
00386     GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph);
00387     const int Nodes = GKey.GetNodes();
00388     if (Nodes > 2 && Nodes <= MxIsoCheck) {
00389       GKey.TakeGraph(Graph);
00390       for (int variant = 1; ; variant++) {
00391         GKey.SetVariant(variant);
00392         int KeyId = GraphH.GetKeyId(GKey); // Is there a graph of the same signature and same VariantId
00393         if (KeyId == -1) { return -1; }
00394         if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes))) { return KeyId; } // perform brute force isomorphism check
00395       }
00396     } else {
00397       // For all other graphs we perform approximate graph isomorphism checking
00398       const int KeyId = GraphH.GetKeyId(GKey);
00399       return KeyId;
00400     }
00401   }
00402   Fail;
00403   return -1;
00404 }
00405 
00406 template <class TDat>
00407 bool TGHash<TDat>::GetNodeMap(const PNGraph& Graph, TIntPrV& NodeMapV) const {
00408   int KeyId;
00409   return GetNodeMap(Graph, NodeMapV, KeyId);
00410 }
00411 
00412 template <class TDat>
00413 bool TGHash<TDat>::GetNodeMap(const PNGraph& Graph, TIntPrV& NodeMapV, int& KeyId) const {
00414   NodeMapV.Clr(false);
00415   if (HashOnlyTrees) {
00416     int RootNId;  IAssert(TSnap::IsTree(Graph, RootNId));
00417     TIntV TreeSig;  TSnap::GetTreeSig(Graph, RootNId, TreeSig, NodeMapV);
00418     TGraphKey GKey(TreeSig);
00419     KeyId = GraphH.GetKeyId(GKey);
00420     return KeyId != -1;
00421   } else {
00422     const int Nodes = Graph->GetNodes();
00423     int IsoPermId = -1;
00424     NodeMapV.Clr(false);
00425     if (Nodes == 0) { return true; }
00426     else if (Nodes == 1) {
00427       NodeMapV.Add(TIntPr(Graph->BegNI().GetId(), 0));  return true; }
00428     else if (Nodes <= MxIsoCheck) {
00429       TGraphKey GKey;
00430       GKey.TakeSig(Graph, MxIsoCheck+1, MxSvdGraph);
00431       GKey.TakeGraph(Graph, NodeMapV);
00432       for (int variant = 1; ; variant++) {
00433         GKey.SetVariant(variant);
00434         KeyId = GraphH.GetKeyId(GKey);
00435         if (KeyId == -1) { return false; }
00436         if (TGraphKey::IsIsomorph(GKey, GraphH.GetKey(KeyId), GSzToPermH.GetDat(Nodes), IsoPermId)) {
00437           const TIntV& K1K2Perm = GSzToPermH.GetDat(Nodes)[IsoPermId];
00438           // map from graph to key1 to key2
00439           for  (int i = 0; i < NodeMapV.Len(); i++) {
00440             NodeMapV[i].Val2 = K1K2Perm[NodeMapV[i].Val2]; }
00441           return true;
00442         }
00443       }
00444       return false;
00445     } else {
00446       return false; // graph too big to find the mapping
00447     }
00448   }
00449   Fail;
00450   return false;
00451 }
00452 
00453 template <class TDat>
00454 void TGHash<TDat>::GetKeyIdByDat(TIntV& KeyIdV, const bool& Asc) const {
00455   TVec<TQuad<TDat, TInt,TInt, TInt> > DatKeyIdV(Len(), 0); // <TDat,Nodes,Edges,KeyId>
00456   for (int i = FFirstKeyId(); FNextKeyId(i); ) {
00457     DatKeyIdV.Add(TQuad<TDat, TInt,TInt, TInt>(GetDatId(i), GetKey(i).GetNodes(), GetKey(i).GetEdges(), i));
00458   }
00459   DatKeyIdV.Sort(Asc);
00460   KeyIdV.Gen(Len(), 0);
00461   for (int i = 0; i < Len(); i++) {
00462     KeyIdV.Add(DatKeyIdV[i].Val4);
00463   }
00464 }
00465 
00466 template <class TDat>
00467 void TGHash<TDat>::GetKeyIdByGSz(TIntV& KeyIdV, const bool& Asc) const {
00468   TVec<TQuad<TInt,TInt, TDat, TInt> > DatKeyIdV(Len(), 0); // <Nodes,Edges,TDat,KeyId>
00469   for (int i = FFirstKeyId(); FNextKeyId(i); ) {
00470     DatKeyIdV.Add(TQuad< TInt,TInt, TDat, TInt>(GetKey(i).GetNodes(), GetKey(i).GetEdges(), GetDatId(i), i));
00471   }
00472   DatKeyIdV.Sort(Asc);
00473   KeyIdV.Gen(Len(), 0);
00474   for (int i = 0; i < Len(); i++) {
00475     KeyIdV.Add(DatKeyIdV[i].Val4);
00476   }
00477 }
00478 
00479 template <class TDat>
00480 void TGHash<TDat>::DrawGViz(const int& KeyId, const TStr& OutFNmPref, const TStr& OutputType, TStr Desc) const {
00481   IAssert(OutputType == "ps" || OutputType == "gif" || OutputType == "png");
00482   const TGraphKey& GKey = GetKey(KeyId);
00483   const TStr Desc1 = TStr::Fmt("%s (%d, %d)", Desc.CStr(), GKey.GetNodes(), GKey.GetEdges());
00484   GKey.SaveGViz(OutFNmPref+".dot", Desc1);
00485   TSnap::TSnapDetail::GVizDoLayout(OutFNmPref+".dot", OutFNmPref+"."+OutputType, gvlDot);
00486 }
00487 
00488 template <class TDat>
00489 void TGHash<TDat>::DrawGViz(const TIntV& KeyIdV, const TStr& OutFNmPref, const TStr& OutputType) const {
00490   IAssert(OutputType == "ps" || OutputType == "gif" || OutputType == "png");
00491   TExeTm ExeTm;
00492   printf("Plotting %d graphs\n", KeyIdV.Len());
00493   for (int i = 0; i < KeyIdV.Len(); i++) {
00494     const TStr FNm = TStr::Fmt("%s.%03d.key%d.", OutFNmPref.CStr(), i+1, KeyIdV[i]());
00495     const TStr Desc = TStr::Fmt("KeyId:%d", KeyIdV[i]());
00496     const TGraphKey& GKey = GetKey(KeyIdV[i]);
00497     printf("\r  %d  g(%d, %d)    ", i, GKey.GetNodes(), GKey.GetEdges());
00498     GKey.SaveGViz(FNm+"dot", Desc);
00499     TSnap::TSnapDetail::GVizDoLayout(FNm+"dot", FNm+OutputType, gvlDot);
00500   }
00501   printf("done [%s].\n", ExeTm.GetTmStr());
00502 }
00503 
00504 template <class TDat>
00505 void TGHash<TDat>::SaveTxt(const TStr& OutFNm, const TStr& Desc, const TStr& DatColNm, const bool& SortByKeyVal) const {
00506   TIntV KeyIdV;
00507   if (SortByKeyVal) GetKeyIdByDat(KeyIdV, false);
00508   else GetKeyIdByGSz(KeyIdV, true);
00509   FILE *F = fopen(OutFNm.CStr(), "wt");
00510   fprintf(F, "Graph-Hash-Table");
00511   fprintf(F, "%s\n", Desc.CStr());
00512   fprintf(F, "%d graphs\n", KeyIdV.Len());
00513   fprintf(F, "Rank\tKeyId\tNodes\tEdges\t%s\n", DatColNm.CStr());
00514   for (int i = 0; i < KeyIdV.Len(); i++) {
00515     const TGraphKey& Key = GetKey(KeyIdV[i]);
00516     fprintf(F, "%d\t%d\t%d\t%d\t%s\n", i+1, KeyIdV[i](), Key.GetNodes(), Key.GetEdges(),
00517       GetDatId(KeyIdV[i]).GetStr().CStr());
00518   }
00519   fclose(F);
00520 }
00521 
00522 template <class TDat>
00523 void TGHash<TDat>::SaveDetailTxt(const TStr& OutFNm, const TStr& Desc, const TStr& DatColNm) const {
00524   TIntV KeyIdV;  GetKeyIdByDat(KeyIdV, false);
00525   FILE *F = fopen(OutFNm.CStr(), "wt");
00526   fprintf(F, "Graph-Hash-Table\n");
00527   fprintf(F, "%s\n", Desc.CStr());
00528   fprintf(F, "%d graphs", KeyIdV.Len());
00529   for (int i = 0; i < KeyIdV.Len(); i++) {
00530     fprintf(F, "\n\n[%5d]\tRank: %d\n", KeyIdV[i](), i+1);
00531     fprintf(F, "Dat:  %s\n", GetDat(KeyIdV[i]).GetStr().CStr());
00532     GetDatId(KeyIdV[i]).SaveTxt(F);
00533   }
00534   fclose(F);
00535 }
00536 
00537 //#//////////////////////////////////////////////
00539 class TSimpleGraph {
00540 private:
00541   TIntPrV EdgeV;
00542 public:
00543   TSimpleGraph() { }
00544   TSimpleGraph(const TIntPrV& GEdgeV) : EdgeV(GEdgeV) { }
00545   bool operator == (const TSimpleGraph& Graph) const { return EdgeV == Graph.EdgeV; }
00546   bool operator < (const TSimpleGraph& Graph) const { return EdgeV < Graph.EdgeV; }
00547 
00548   int GetEdges() const { return EdgeV.Len(); }
00549   void AddEdge(const int& SrcNId, const int& DstNId) { EdgeV.Add(TIntPr(SrcNId, DstNId)); }
00550   bool Join(const TSimpleGraph& G1, const TSimpleGraph& G2);
00551   TIntPrV& GetEdgeV() { return EdgeV; }
00552   TIntPrV& operator () () { return EdgeV; }
00553 
00554   void Dump(const TStr& Desc = TStr()) const;
00555 };
00556 typedef TVec<TSimpleGraph> TSimpleGraphV;
00557 
00558 //#//////////////////////////////////////////////
00560 class TSubGraphsEnum {
00561 private:
00562   TSimpleGraphV SgV, NextSgV;
00563   THash<TIntPr, TIntH> EdgeH;
00564   PNGraph NGraph;
00565 public:
00566   TSubGraphsEnum(PNGraph Graph) : NGraph(Graph) { }
00567 
00568   void Gen2Graphs();
00569   void EnumSubGraphs(const int& MaxEdges);
00570   void RecurBfs(const int& MxDepth);
00571   void RecurBfs(const int& NId, const int& Depth, TSimpleGraph& PrevG);
00572   void RecurBfs1(const int& MxDepth);
00573   void RecurBfs1(const int& NId, const int& Depth);
00574   //void RecurBfs(const int& NId, const int& Depth, const THash<TIntPr, TInt>& EdgeH);
00575 };
00576 
00577