SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
cncom.cpp
Go to the documentation of this file.
1 // Connected Components
3 void TCnCom::Dump(const TCnComV& CnComV, const TStr& Desc) {
4  if (! Desc.Empty()) { printf("%s:\n", Desc.CStr()); }
5  for (int cc = 0; cc < CnComV.Len(); cc++) {
6  const TIntV& NIdV = CnComV[cc].NIdV;
7  printf("%d : ", NIdV.Len());
8  for (int i = 0; i < NIdV.Len(); i++) { printf(" %d", NIdV[i].Val); }
9  printf("\n");
10  }
11 }
12 
13 void TCnCom::SaveTxt(const TCnComV& CnComV, const TStr& FNm, const TStr& Desc) {
14  FILE *F = fopen(FNm.CStr(), "wt");
15  if (! Desc.Empty()) { fprintf(F, "# %s\n", Desc.CStr()); }
16  fprintf(F, "# Connected Components:\t%d\n", CnComV.Len());
17  fprintf(F, "# Connected components (format: <Size>\\t<NodeId1>\\t<NodeId2>...)\n");
18  for (int cc = 0; cc < CnComV.Len(); cc++) {
19  const TIntV& NIdV = CnComV[cc].NIdV;
20  fprintf(F, "%d", NIdV.Len());
21  for (int i = 0; i < NIdV.Len(); i++) { fprintf(F, "\t%d", NIdV[i].Val); }
22  fprintf(F, "\n");
23  }
24  fclose(F);
25 }
26 
28 // Connected Components
29 namespace TSnap {
30 
31 void GetBiConSzCnt(const PUNGraph& Graph, TIntPrV& SzCntV) {
32  TCnComV BiCnComV;
33  GetBiCon(Graph, BiCnComV);
34  TIntH SzCntH;
35  for (int c =0; c < BiCnComV.Len(); c++) {
36  SzCntH.AddDat(BiCnComV[c].Len()) += 1;
37  }
38  SzCntH.GetKeyDatPrV(SzCntV);
39  SzCntV.Sort();
40 }
41 
42 void GetBiCon(const PUNGraph& Graph, TCnComV& BiCnComV) {
43  TBiConVisitor Visitor(Graph->GetNodes());
44  TCnCom::GetDfsVisitor(Graph, Visitor);
45  BiCnComV = Visitor.CnComV;
46 }
47 
48 void GetArtPoints(const PUNGraph& Graph, TIntV& ArtNIdV) {
49  TArtPointVisitor Visitor(Graph->GetNodes());
50  TCnCom::GetDfsVisitor(Graph, Visitor);
51  Visitor.ArtSet.GetKeyV(ArtNIdV);
52 }
53 
54 // bridges are edges in the size 2 biconnected components
55 void GetEdgeBridges(const PUNGraph& Graph, TIntPrV& EdgeV) {
56  TCnComV BiCnComV;
57  GetBiCon(Graph, BiCnComV);
58  TIntPrSet EdgeSet;
59  for (int c = 0; c < BiCnComV.Len(); c++) {
60  const TIntV& NIdV = BiCnComV[c].NIdV;
61  if (NIdV.Len() == 2) {
62  EdgeSet.AddKey(TIntPr(TMath::Mn(NIdV[0], NIdV[1]), TMath::Mx(NIdV[0], NIdV[1])));
63  }
64  }
65  EdgeSet.GetKeyV(EdgeV);
66 }
67 
68 // Algorithm: Find all bridges, remove them from the graph, find largest component K
69 // now add all bridges that do not touch K, find connected components
70 void Get1CnComSzCnt(const PUNGraph& Graph, TIntPrV& SzCntV) {
71  //TCnCom::GetWccCnt(Graph, SzCntV); IAssertR(SzCntV.Len() == 1, "Graph is not connected.");
72  TIntPrV EdgeV;
73  GetEdgeBridges(Graph, EdgeV);
74  if (EdgeV.Empty()) { SzCntV.Clr(false); return; }
75  PUNGraph TmpG = TUNGraph::New();
76  *TmpG = *Graph;
77  for (int e = 0; e < EdgeV.Len(); e++) {
78  TmpG->DelEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
79  TCnComV CnComV; GetWccs(TmpG, CnComV);
80  IAssert(CnComV.Len() >= 2);
81  const TIntV& MxWcc = CnComV[0].NIdV;
82  TIntSet MxCcSet(MxWcc.Len());
83  for (int i = 0; i < MxWcc.Len(); i++) {
84  MxCcSet.AddKey(MxWcc[i]); }
85  // create new graph: bridges not touching MxCc of G with no bridges
86  for (int e = 0; e < EdgeV.Len(); e++) {
87  if (! MxCcSet.IsKey(EdgeV[e].Val1) && ! MxCcSet.IsKey(EdgeV[e].Val2)) {
88  TmpG->AddEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
89  }
90  GetWccSzCnt(TmpG, SzCntV);
91  for (int c = 0; c < SzCntV.Len(); c++) {
92  if (SzCntV[c].Val1 == MxCcSet.Len()) {
93  SzCntV.Del(c); break; }
94  }
95 }
96 
97 // get the node ids in 1-connected components
98 void Get1CnCom(const PUNGraph& Graph, TCnComV& Cn1ComV) {
99  //TCnCom::GetWccCnt(Graph, SzCntV); IAssertR(SzCntV.Len() == 1, "Graph is not connected.");
100  TIntPrV EdgeV;
101  GetEdgeBridges(Graph, EdgeV);
102  if (EdgeV.Empty()) { Cn1ComV.Clr(false); return; }
103  PUNGraph TmpG = TUNGraph::New();
104  *TmpG = *Graph;
105  for (int e = 0; e < EdgeV.Len(); e++) {
106  TmpG->DelEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
107  TCnComV CnComV; GetWccs(TmpG, CnComV);
108  IAssert(CnComV.Len() >= 2);
109  const TIntV& MxWcc = CnComV[0].NIdV;
110  TIntSet MxCcSet(MxWcc.Len());
111  for (int i = 0; i < MxWcc.Len(); i++) {
112  MxCcSet.AddKey(MxWcc[i]); }
113  // create new graph: bridges not touching MxCc of G with no bridges
114  for (int e = 0; e < EdgeV.Len(); e++) {
115  if (! MxCcSet.IsKey(EdgeV[e].Val1) && ! MxCcSet.IsKey(EdgeV[e].Val2)) {
116  TmpG->AddEdge(EdgeV[e].Val1, EdgeV[e].Val2); }
117  }
118  GetWccs(TmpG, Cn1ComV);
119  // remove the largest component of G
120  for (int c = 0; c < Cn1ComV.Len(); c++) {
121  if (MxCcSet.IsKey(Cn1ComV[c].NIdV[0])) {
122  Cn1ComV.Del(c); break; }
123  }
124 }
125 
126 PUNGraph GetMxBiCon(const PUNGraph& Graph, const bool& RenumberNodes) {
127  TCnComV CnComV;
128  GetBiCon(Graph, CnComV);
129  if (CnComV.Empty()) {
130  return PUNGraph();
131  }
132  int CcId = 0, MxSz = 0;
133  for (int i = 0; i < CnComV.Len(); i++) {
134  if (MxSz < CnComV[i].Len()) {
135  MxSz = CnComV[i].Len();
136  CcId=i;
137  }
138  }
139  return TSnap::GetSubGraph(Graph, CnComV[CcId](), RenumberNodes);
140 }
141 
142 } // namespace TSnap
static void Dump(const TCnComV &CnComV, const TStr &Desc=TStr())
Definition: cncom.cpp:3
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
PUNGraph GetMxBiCon(const PUNGraph &Graph, const bool &RenumberNodes)
Returns a graph representing the largest bi-connected component on an undirected Graph.
Definition: cncom.cpp:126
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
void GetArtPoints(const PUNGraph &Graph, TIntV &ArtNIdV)
Returns articulation points of a Graph.
Definition: cncom.cpp:48
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void GetKeyV(TVec< TKey > &KeyV) const
Definition: shash.h:1347
void GetBiConSzCnt(const PUNGraph &Graph, TIntPrV &SzCntV)
Returns a distribution of bi-connected component sizes.
Definition: cncom.cpp:31
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
static void GetDfsVisitor(const PGraph &Graph, TVisitor &Visitor)
Definition: cncom.h:124
Biconnected componetns Depth-First-Search visitor class.
Definition: cncom.h:195
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TIntV NIdV
Definition: cncom.h:90
PUNGraph GetSubGraph(const PUNGraph &Graph, const TIntV &NIdV, const bool &RenumberNodes)
Returns an induced subgraph of an undirected graph Graph with NIdV nodes with an optional node renumb...
Definition: subgraph.cpp:7
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
int AddKey(const TKey &Key)
Definition: shash.h:1254
void Get1CnCom(const PUNGraph &Graph, TCnComV &Cn1ComV)
Returns 1-components: maximal connected components of that can be disconnected from the Graph by remo...
Definition: cncom.cpp:98
void Get1CnComSzCnt(const PUNGraph &Graph, TIntPrV &SzCntV)
Distribution of sizes of 1-components, maximal number of components that can be disconnected from the...
Definition: cncom.cpp:70
void GetBiCon(const PUNGraph &Graph, TCnComV &BiCnComV)
Returns all bi-connected components of a Graph.
Definition: cncom.cpp:42
void GetEdgeBridges(const PUNGraph &Graph, TIntPrV &EdgeV)
Returns bridge edges of a Graph.
Definition: cncom.cpp:55
Definition: dt.h:412
bool Empty() const
Definition: dt.h:488
Definition: hash.h:97
Articulation point Depth-First-Search visitor class.
Definition: cncom.h:169
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
Definition: bd.h:196
char * CStr()
Definition: dt.h:476
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void GetWccSzCnt(const PGraph &Graph, TIntPrV &WccSzCnt)
Returns a distribution of weakly connected component sizes.
Definition: cncom.h:337
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376
static void SaveTxt(const TCnComV &CnComV, const TStr &FNm, const TStr &Desc=TStr())
Definition: cncom.cpp:13
TPt< TUNGraph > PUNGraph
Pointer to an undirected graph (TUNGraph)
Definition: graph.h:5