SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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
Main namespace for all the Snap global entities.
Definition: alg.h:1
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
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
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 DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
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:491
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
char * CStr()
Definition: dt.h:479
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