SNAP Library 2.1, Developer 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
cncom.cpp
Go to the documentation of this file.
00001 
00002 // Connected Components
00003 void TCnCom::Dump(const TCnComV& CnComV, const TStr& Desc) {
00004   if (! Desc.Empty()) { printf("%s:\n", Desc.CStr()); }
00005   for (int cc = 0; cc < CnComV.Len(); cc++) {
00006     const TIntV& NIdV = CnComV[cc].NIdV;
00007     printf("%d : ", NIdV.Len());
00008     for (int i = 0; i < NIdV.Len(); i++) { printf(" %d", NIdV[i].Val); }
00009     printf("\n");
00010   }
00011 }
00012 
00013 void TCnCom::SaveTxt(const TCnComV& CnComV, const TStr& FNm, const TStr& Desc) {
00014   FILE *F = fopen(FNm.CStr(), "wt");
00015   if (! Desc.Empty()) { fprintf(F, "# %s\n", Desc.CStr()); }
00016   fprintf(F, "# Connected Components:\t%d\n", CnComV.Len());
00017   fprintf(F, "# Connected components (format: <Size>\\t<NodeId1>\\t<NodeId2>...)\n");
00018   for (int cc = 0; cc < CnComV.Len(); cc++) {
00019     const TIntV& NIdV = CnComV[cc].NIdV;
00020     fprintf(F, "%d", NIdV.Len());
00021     for (int i = 0; i < NIdV.Len(); i++) { fprintf(F, "\t%d", NIdV[i].Val); }
00022     fprintf(F, "\n");
00023   }
00024   fclose(F);
00025 }
00026 
00028 // Connected Components
00029 namespace TSnap {
00030 
00031 void GetBiConSzCnt(const PUNGraph& Graph, TIntPrV& SzCntV) {
00032   TCnComV BiCnComV;
00033   GetBiCon(Graph, BiCnComV);
00034   TIntH SzCntH;
00035   for (int c =0; c < BiCnComV.Len(); c++) {
00036     SzCntH.AddDat(BiCnComV[c].Len()) += 1;
00037   }
00038   SzCntH.GetKeyDatPrV(SzCntV);
00039   SzCntV.Sort();
00040 }
00041 
00042 void GetBiCon(const PUNGraph& Graph, TCnComV& BiCnComV) {
00043   TBiConVisitor Visitor(Graph->GetNodes());
00044   TCnCom::GetDfsVisitor(Graph, Visitor);
00045   BiCnComV = Visitor.CnComV;
00046 }
00047 
00048 void GetArtPoints(const PUNGraph& Graph, TIntV& ArtNIdV) {
00049   TArtPointVisitor Visitor(Graph->GetNodes());
00050   TCnCom::GetDfsVisitor(Graph, Visitor);
00051   Visitor.ArtSet.GetKeyV(ArtNIdV);
00052 }
00053 
00054 // bridges are edges in the size 2 biconnected components
00055 void GetEdgeBridges(const PUNGraph& Graph, TIntPrV& EdgeV) {
00056   TCnComV BiCnComV;
00057   GetBiCon(Graph, BiCnComV);
00058   TIntPrSet EdgeSet;
00059   for (int c = 0; c < BiCnComV.Len(); c++) {
00060     const TIntV& NIdV = BiCnComV[c].NIdV; 
00061     if (NIdV.Len() == 2) {
00062       EdgeSet.AddKey(TIntPr(TMath::Mn(NIdV[0], NIdV[1]), TMath::Mx(NIdV[0], NIdV[1]))); 
00063     }
00064   }
00065   EdgeSet.GetKeyV(EdgeV);
00066 }
00067 
00068 // Algorithm: Find all bridges, remove them from the graph, find largest component K
00069 // now add all bridges that do not touch K, find connected components
00070 void Get1CnComSzCnt(const PUNGraph& Graph, TIntPrV& SzCntV) {
00071   //TCnCom::GetWccCnt(Graph, SzCntV);  IAssertR(SzCntV.Len() == 1, "Graph is not connected.");
00072   TIntPrV EdgeV;
00073   GetEdgeBridges(Graph, EdgeV);
00074   if (EdgeV.Empty()) { SzCntV.Clr(false); return; }
00075   PUNGraph TmpG = TUNGraph::New();
00076   *TmpG = *Graph;
00077   for (int e = 0; e < EdgeV.Len(); e++) {
00078     TmpG->DelEdge(EdgeV[e].Val1, EdgeV[e].Val2);  }
00079   TCnComV CnComV;  GetWccs(TmpG, CnComV);
00080   IAssert(CnComV.Len() >= 2);
00081   const TIntV& MxWcc = CnComV[0].NIdV;
00082   TIntSet MxCcSet(MxWcc.Len());
00083   for (int i = 0; i < MxWcc.Len(); i++) { 
00084     MxCcSet.AddKey(MxWcc[i]); }
00085   // create new graph: bridges not touching MxCc of G with no bridges
00086   for (int e = 0; e < EdgeV.Len(); e++) {
00087     if (! MxCcSet.IsKey(EdgeV[e].Val1) &&  ! MxCcSet.IsKey(EdgeV[e].Val2)) {
00088       TmpG->AddEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
00089   }
00090   GetWccSzCnt(TmpG, SzCntV);
00091   for (int c = 0; c < SzCntV.Len(); c++) {
00092     if (SzCntV[c].Val1 == MxCcSet.Len()) { 
00093       SzCntV.Del(c);  break; }
00094   }
00095 }
00096 
00097 // get the node ids in 1-connected components 
00098 void Get1CnCom(const PUNGraph& Graph, TCnComV& Cn1ComV) {
00099   //TCnCom::GetWccCnt(Graph, SzCntV);  IAssertR(SzCntV.Len() == 1, "Graph is not connected.");
00100   TIntPrV EdgeV;
00101   GetEdgeBridges(Graph, EdgeV);
00102   if (EdgeV.Empty()) { Cn1ComV.Clr(false); return; }
00103   PUNGraph TmpG = TUNGraph::New();
00104   *TmpG = *Graph;
00105   for (int e = 0; e < EdgeV.Len(); e++) {
00106     TmpG->DelEdge(EdgeV[e].Val1, EdgeV[e].Val2);  }
00107   TCnComV CnComV;  GetWccs(TmpG, CnComV);
00108   IAssert(CnComV.Len() >= 2);
00109   const TIntV& MxWcc = CnComV[0].NIdV;
00110   TIntSet MxCcSet(MxWcc.Len());
00111   for (int i = 0; i < MxWcc.Len(); i++) { 
00112     MxCcSet.AddKey(MxWcc[i]); }
00113   // create new graph: bridges not touching MxCc of G with no bridges
00114   for (int e = 0; e < EdgeV.Len(); e++) {
00115     if (! MxCcSet.IsKey(EdgeV[e].Val1) &&  ! MxCcSet.IsKey(EdgeV[e].Val2)) {
00116       TmpG->AddEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
00117   }
00118   GetWccs(TmpG, Cn1ComV);
00119   // remove the largest component of G
00120   for (int c = 0; c < Cn1ComV.Len(); c++) {
00121     if (MxCcSet.IsKey(Cn1ComV[c].NIdV[0])) {
00122       Cn1ComV.Del(c);  break; }
00123   }
00124 }
00125 
00126 PUNGraph GetMxBiCon(const PUNGraph& Graph, const bool& RenumberNodes) {
00127   TCnComV CnComV;
00128   GetBiCon(Graph, CnComV);
00129   if (CnComV.Empty()) { 
00130     return PUNGraph(); 
00131   }
00132   int CcId = 0, MxSz = 0;
00133   for (int i = 0; i < CnComV.Len(); i++) {
00134     if (MxSz < CnComV[i].Len()) {
00135       MxSz = CnComV[i].Len();  
00136       CcId=i; 
00137     }
00138   }
00139   return TSnap::GetSubGraph(Graph, CnComV[CcId](), RenumberNodes);
00140 }
00141 
00142 } // namespace TSnap