SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
cncom.h
Go to the documentation of this file.
1 // Connected Components
3 class TCnCom;
4 typedef TVec<TCnCom> TCnComV;
5 
6 namespace TSnap {
7 
9 template <class PGraph> void GetNodeWcc(const PGraph& Graph, const int& NId, TIntV& CnCom);
11 template <class PGraph> bool IsConnected(const PGraph& Graph);
13 template <class PGraph> bool IsWeaklyConn(const PGraph& Graph);
15 
17 template <class PGraph> void GetWccSzCnt(const PGraph& Graph, TIntPrV& WccSzCnt);
19 
21 template <class PGraph> void GetWccs(const PGraph& Graph, TCnComV& CnComV);
23 
25 template <class PGraph> void GetSccSzCnt(const PGraph& Graph, TIntPrV& SccSzCnt);
27 
29 template <class PGraph> void GetSccs(const PGraph& Graph, TCnComV& CnComV);
31 template <class PGraph> double GetMxWccSz(const PGraph& Graph);
33 template <class PGraph> double GetMxSccSz(const PGraph& Graph);
34 
36 
39 template <class PGraph> PGraph GetMxWcc(const PGraph& Graph);
41 
44 template <class PGraph> PGraph GetMxScc(const PGraph& Graph);
46 
49 template <class PGraph> PGraph GetMxBiCon(const PGraph& Graph);
50 
52 
54 void GetBiConSzCnt(const PUNGraph& Graph, TIntPrV& SzCntV);
56 
58 void GetBiCon(const PUNGraph& Graph, TCnComV& BiCnComV);
60 
62 void GetArtPoints(const PUNGraph& Graph, TIntV& ArtNIdV);
64 
67 void GetEdgeBridges(const PUNGraph& Graph, TIntPrV& EdgeV);
69 
71 void Get1CnComSzCnt(const PUNGraph& Graph, TIntPrV& SzCntV);
73 
76 void Get1CnCom(const PUNGraph& Graph, TCnComV& Cn1ComV);
78 
81 PUNGraph GetMxBiCon(const PUNGraph& Graph, const bool& RenumberNodes=false);
82 
83 }; // namespace TSnap
84 
85 //#//////////////////////////////////////////////
88 class TCnCom {
89 public:
91 public:
92  TCnCom() : NIdV() { }
93  TCnCom(const TIntV& NodeIdV) : NIdV(NodeIdV) { }
94  TCnCom(const TCnCom& CC) : NIdV(CC.NIdV) { }
95  TCnCom(TSIn& SIn) : NIdV(SIn) { }
96  void Save(TSOut& SOut) const { NIdV.Save(SOut); }
97  TCnCom& operator = (const TCnCom& CC) { if (this != &CC) NIdV = CC.NIdV; return *this; }
98  bool operator == (const TCnCom& CC) const { return NIdV == CC.NIdV; }
99  bool operator < (const TCnCom& CC) const { return NIdV < CC.NIdV; }
100 
101  int Len() const { return NIdV.Len(); }
102  bool Empty() const { return NIdV.Empty(); }
103  void Clr() { NIdV.Clr(); }
104  void Add(const int& NodeId) { NIdV.Add(NodeId); }
105  const TInt& operator [] (const int& NIdN) const { return NIdV[NIdN]; }
106  const TIntV& operator () () const { return NIdV; }
107  TIntV& operator () () { return NIdV; }
108  const TInt& GetVal(const int& NIdN) const { return operator[](NIdN); }
109  void Sort(const bool& Asc = true) { NIdV.Sort(Asc); }
110  bool IsNIdIn(const int& NId) const { return NIdV.SearchBin(NId) != -1; }
111  const TInt& GetRndNId() const { return NIdV[TInt::Rnd.GetUniDevInt(Len())]; }
112  static void Dump(const TCnComV& CnComV, const TStr& Desc=TStr());
113  static void SaveTxt(const TCnComV& CnComV, const TStr& FNm, const TStr& Desc=TStr());
117  template <class PGraph, class TVisitor>
118  static void GetDfsVisitor(const PGraph& Graph, TVisitor& Visitor);
119  int GetPrimHashCd() const { return NIdV.GetPrimHashCd(); }
120  int GetSecHashCd() const { return NIdV.GetSecHashCd(); }
121 };
122 
123 template <class PGraph, class TVisitor>
124 void TCnCom::GetDfsVisitor(const PGraph& Graph, TVisitor& Visitor) {
125  const int Nodes = Graph->GetNodes();
126  TSStack<TIntTr> Stack(Nodes);
127  int edge=0, Deg=0, U=0;
128  TIntH ColorH(Nodes);
129  typename PGraph::TObj::TNodeI NI, UI;
130  for (NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
131  U = NI.GetId();
132  if (! ColorH.IsKey(U)) { // is unvisited node
133  ColorH.AddDat(U, 1);
134  Visitor.DiscoverNode(U); // discover
135  Stack.Push(TIntTr(U, 0, Graph->GetNI(U).GetOutDeg()));
136  while (! Stack.Empty()) {
137  const TIntTr& Top = Stack.Top();
138  U=Top.Val1; edge=Top.Val2; Deg=Top.Val3;
139  typename PGraph::TObj::TNodeI UI = Graph->GetNI(U);
140  Stack.Pop();
141  while (edge != Deg) {
142  const int V = UI.GetOutNId(edge);
143  Visitor.ExamineEdge(U, V); // examine edge
144  if (! ColorH.IsKey(V)) {
145  Visitor.TreeEdge(U, V); // tree edge
146  Stack.Push(TIntTr(U, ++edge, Deg));
147  U = V;
148  ColorH.AddDat(U, 1);
149  Visitor.DiscoverNode(U); // discover
150  UI = Graph->GetNI(U);
151  edge = 0; Deg = UI.GetOutDeg();
152  }
153  else if (ColorH.GetDat(V) == 1) {
154  Visitor.BackEdge(U, V); // edge upward
155  ++edge; }
156  else {
157  Visitor.FwdEdge(U, V); // edge downward
158  ++edge; }
159  }
160  ColorH.AddDat(U, 2);
161  Visitor.FinishNode(U); // finish
162  }
163  }
164  }
165 }
166 
167 //#//////////////////////////////////////////////
170 public:
175 public:
177  TArtPointVisitor(const int& Nodes) : VnLowH(Nodes), ParentH(Nodes) { }
178  void DiscoverNode(int NId) { Time++; VnLowH.AddDat(NId, TIntPr(Time, Time)); }
179  void FinishNode(const int& NId) {
180  if (! ParentH.IsKey(NId)) { return; } const int Prn = ParentH.GetDat(NId);
181  VnLowH.GetDat(Prn).Val2 = TMath::Mn(VnLowH.GetDat(Prn).Val2, VnLowH.GetDat(NId).Val2);
182  if (VnLowH.GetDat(Prn).Val1==1 && VnLowH.GetDat(NId).Val1!=2) { ArtSet.AddKey(Prn); }
183  if (VnLowH.GetDat(Prn).Val1!=1 && VnLowH.GetDat(NId).Val2>=VnLowH.GetDat(Prn).Val1) { ArtSet.AddKey(Prn); } }
184  void ExamineEdge(const int& NId1, const int& NId2) { }
185  void TreeEdge(const int& NId1, const int& NId2) { ParentH.AddDat(NId2, NId1); }
186  void BackEdge(const int& NId1, const int& NId2) {
187  if (ParentH.IsKey(NId1) && ParentH.GetDat(NId1)!=NId2) {
188  VnLowH.GetDat(NId1).Val2 = TMath::Mn(VnLowH.GetDat(NId1).Val2, VnLowH.GetDat(NId2).Val1); } }
189  void FwdEdge(const int& NId1, const int& NId2) {
190  VnLowH.GetDat(NId1).Val2 = TMath::Mn(VnLowH.GetDat(NId1).Val2, VnLowH.GetDat(NId2).Val1); }
191 };
192 
193 //#//////////////////////////////////////////////
196 public:
203 public:
205  TBiConVisitor(const int& Nodes) : VnLowH(Nodes), ParentH(Nodes), Stack(Nodes) { }
206  void DiscoverNode(int NId) { Time++; VnLowH.AddDat(NId, TIntPr(Time, Time)); }
207  void FinishNode(const int& NId) {
208  if (! ParentH.IsKey(NId)) { return; } const int Prn = ParentH.GetDat(NId);
209  VnLowH.GetDat(Prn).Val2 = TMath::Mn(VnLowH.GetDat(Prn).Val2, VnLowH.GetDat(NId).Val2);
210  if (VnLowH.GetDat(NId).Val2 >= VnLowH.GetDat(Prn).Val1) {
211  NSet.Clr(false);
212  while (! Stack.Empty() && Stack.Top() != TIntPr(Prn, NId)) {
213  const TIntPr& Top = Stack.Top();
214  NSet.AddKey(Top.Val1); NSet.AddKey(Top.Val2); Stack.Pop(); }
215  if (! Stack.Empty()) {
216  const TIntPr& Top = Stack.Top();
217  NSet.AddKey(Top.Val1); NSet.AddKey(Top.Val2); Stack.Pop(); }
218  TIntV NIdV; NSet.GetKeyV(NIdV); NIdV.Sort();
219  CnComV.Add(NIdV); } }
220  void ExamineEdge(const int& NId1, const int& NId2) { }
221  void TreeEdge(const int& NId1, const int& NId2) {
222  ParentH.AddDat(NId2, NId1);
223  Stack.Push(TIntPr(NId1, NId2)); }
224  void BackEdge(const int& NId1, const int& NId2) {
225  if (ParentH.IsKey(NId1) && ParentH.GetDat(NId1)!=NId2) {
226  Stack.Push(TIntPr(NId1, NId2));
227  VnLowH.GetDat(NId1).Val2 = TMath::Mn(VnLowH.GetDat(NId1).Val2, VnLowH.GetDat(NId2).Val1); } }
228  void FwdEdge(const int& NId1, const int& NId2) { }
229 };
230 
231 //#//////////////////////////////////////////////
233 template <class PGraph, bool OnlyCount = false>
234 class TSccVisitor {
235 public:
236  PGraph Graph;
242 public:
243  TSccVisitor(const PGraph& _Graph) :
244  Graph(_Graph), TmRtH(Graph->GetNodes()), Stack(Graph->GetNodes()) { }
245  void DiscoverNode(int NId) {
246  Time++; TmRtH.AddDat(NId, TIntPr(-Time, NId)); // negative time -- node not yet in any SCC
247  Stack.Push(NId); }
248  void FinishNode(const int& NId) {
249  typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
250  TIntPr& TmRtN = TmRtH.GetDat(NId);
251  int W = -1, Cnt = 0;
252  for (int i = 0; i < NI.GetOutDeg(); i++) {
253  W = NI.GetOutNId(i);
254  const TIntPr& TmRtW = TmRtH.GetDat(W);
255  if (TmRtW.Val1 < 0) { // node not yet in any SCC
256  TmRtN.Val2 = GetMinDiscTm(TmRtN.Val2, TmRtW.Val2); } }
257  if (TmRtN.Val2 == NId) {
258  if (! OnlyCount) { CnComV.Add(); }
259  do { W = Stack.Top(); Stack.Pop();
260  if (OnlyCount) { Cnt++; } else { CnComV.Last().Add(W); }
261  TmRtH.GetDat(W).Val1 = abs(TmRtH.GetDat(W).Val1); // node is in SCC
262  } while (W != NId);
263  if (OnlyCount) { SccCntH.AddDat(Cnt) += 1; } } }
264  void ExamineEdge(const int& NId1, const int& NId2) { }
265  void TreeEdge(const int& NId1, const int& NId2) { }
266  void BackEdge(const int& NId1, const int& NId2) { }
267  void FwdEdge(const int& NId1, const int& NId2) { }
268  int GetMinDiscTm(const int& NId1, const int& NId2) const {
269  return abs(TmRtH.GetDat(NId1).Val1) < abs(TmRtH.GetDat(NId2).Val1) ? NId1 : NId2; }
270 };
271 
272 //#//////////////////////////////////////////////
273 // Implementation
274 namespace TSnap {
275 
276 template <class PGraph>
277 void GetNodeWcc(const PGraph& Graph, const int& NId, TIntV& CnCom) {
278  typename PGraph::TObj::TNodeI NI;
279  THashSet<TInt> VisitedNId(Graph->GetNodes()+1);
280  TSnapQueue<int> NIdQ(Graph->GetNodes()+1);
281  VisitedNId.AddKey(NId);
282  NIdQ.Push(NId);
283  while (! NIdQ.Empty()) {
284  const typename PGraph::TObj::TNodeI Node = Graph->GetNI(NIdQ.Top()); NIdQ.Pop();
285  if (HasGraphFlag(typename PGraph::TObj, gfDirected)) {
286  for (int e = 0; e < Node.GetInDeg(); e++) {
287  const int InNId = Node.GetInNId(e);
288  if (! VisitedNId.IsKey(InNId)) {
289  NIdQ.Push(InNId); VisitedNId.AddKey(InNId); }
290  }
291  }
292  for (int e = 0; e < Node.GetOutDeg(); e++) {
293  const int OutNId = Node.GetOutNId(e);
294  if (! VisitedNId.IsKey(OutNId)) {
295  NIdQ.Push(OutNId); VisitedNId.AddKey(OutNId); }
296  }
297  }
298  CnCom.Gen(VisitedNId.Len(), 0);
299  for (int i = 0; i < VisitedNId.Len(); i++) {
300  CnCom.Add(VisitedNId.GetKey(i));
301  }
302 }
303 
304 template <class PGraph>
305 bool IsConnected(const PGraph& Graph) {
306  return IsWeaklyConn(Graph);
307 }
308 
309 template <class PGraph>
310 bool IsWeaklyConn(const PGraph& Graph) {
311  if (Graph->Empty()) {
312  return true;
313  }
314  THashSet<TInt> VisitedNId(Graph->GetNodes());
315  TSnapQueue<int> NIdQ(Graph->GetNodes()+1);
316  typename PGraph::TObj::TNodeI NI;
317  // the rest of the nodes
318  NIdQ.Push(Graph->BegNI().GetId());
319  while (! NIdQ.Empty()) {
320  const typename PGraph::TObj::TNodeI Node = Graph->GetNI(NIdQ.Top()); NIdQ.Pop();
321  if (HasGraphFlag(typename PGraph::TObj, gfDirected)) {
322  for (int e = 0; e < Node.GetInDeg(); e++) {
323  const int InNId = Node.GetInNId(e);
324  if (! VisitedNId.IsKey(InNId)) { NIdQ.Push(InNId); VisitedNId.AddKey(InNId); }
325  }
326  }
327  for (int e = 0; e < Node.GetOutDeg(); e++) {
328  const int OutNId = Node.GetOutNId(e);
329  if (! VisitedNId.IsKey(OutNId)) { NIdQ.Push(OutNId); VisitedNId.AddKey(OutNId); }
330  }
331  }
332  if (VisitedNId.Len() < Graph->GetNodes()) { return false; }
333  return true;
334 }
335 
336 template <class PGraph>
337 void GetWccSzCnt(const PGraph& Graph, TIntPrV& WccSzCnt) {
338  THashSet<TInt> VisitedNId(Graph->GetNodes());
339  TIntH SzToCntH;
340  TSnapQueue<int> NIdQ(Graph->GetNodes()+1);
341  typename PGraph::TObj::TNodeI NI;
342  int Cnt = 0;
343  // zero degree nodes
344  for (NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
345  if (NI.GetDeg() == 0) { Cnt++; VisitedNId.AddKey(NI.GetId()); }
346  }
347  if (Cnt > 0) SzToCntH.AddDat(1, Cnt);
348  // the rest of the nodes
349  for (NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
350  if (! VisitedNId.IsKey(NI.GetId())) {
351  VisitedNId.AddKey(NI.GetId());
352  NIdQ.Clr(false); NIdQ.Push(NI.GetId());
353  Cnt = 0;
354  while (! NIdQ.Empty()) {
355  const typename PGraph::TObj::TNodeI Node = Graph->GetNI(NIdQ.Top()); NIdQ.Pop();
356  if (HasGraphFlag(typename PGraph::TObj, gfDirected)) {
357  for (int e = 0; e < Node.GetInDeg(); e++) {
358  const int InNId = Node.GetInNId(e);
359  if (! VisitedNId.IsKey(InNId)) { NIdQ.Push(InNId); VisitedNId.AddKey(InNId); }
360  }
361  }
362  for (int e = 0; e < Node.GetOutDeg(); e++) {
363  const int OutNId = Node.GetOutNId(e);
364  if (! VisitedNId.IsKey(OutNId)) { NIdQ.Push(OutNId); VisitedNId.AddKey(OutNId); }
365  }
366  Cnt++;
367  }
368  SzToCntH.AddDat(Cnt) += 1;
369  }
370  }
371  SzToCntH.GetKeyDatPrV(WccSzCnt);
372  WccSzCnt.Sort(true);
373 }
374 
375 template <class PGraph>
376 void GetWccs(const PGraph& Graph, TCnComV& CnComV) {
377  typename PGraph::TObj::TNodeI NI;
378  THashSet<TInt> VisitedNId(Graph->GetNodes()+1);
379  TSnapQueue<int> NIdQ(Graph->GetNodes()+1);
380  TIntV CcNIdV;
381  CnComV.Clr(); CcNIdV.Gen(1);
382  // zero degree nodes
383  for (NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
384  if (NI.GetDeg() == 0) {
385  const int NId = NI.GetId();
386  VisitedNId.AddKey(NId);
387  CcNIdV[0] = NId; CnComV.Add(CcNIdV);
388  }
389  }
390  // the rest of the nodes
391  for (NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
392  const int NId = NI.GetId();
393  if (! VisitedNId.IsKey(NId)) {
394  VisitedNId.AddKey(NId);
395  NIdQ.Clr(false); NIdQ.Push(NId);
396  CcNIdV.Clr(); CcNIdV.Add(NId);
397  while (! NIdQ.Empty()) {
398  const typename PGraph::TObj::TNodeI Node = Graph->GetNI(NIdQ.Top()); NIdQ.Pop();
399  if (HasGraphFlag(typename PGraph::TObj, gfDirected)) {
400  for (int e = 0; e < Node.GetInDeg(); e++) {
401  const int InNId = Node.GetInNId(e);
402  if (! VisitedNId.IsKey(InNId)) {
403  NIdQ.Push(InNId); VisitedNId.AddKey(InNId); CcNIdV.Add(InNId); }
404  }
405  }
406  for (int e = 0; e < Node.GetOutDeg(); e++) {
407  const int OutNId = Node.GetOutNId(e);
408  if (! VisitedNId.IsKey(OutNId)) {
409  NIdQ.Push(OutNId); VisitedNId.AddKey(OutNId); CcNIdV.Add(OutNId); }
410  }
411  }
412  CcNIdV.Sort(true);
413  CnComV.Add(TCnCom(CcNIdV)); // add wcc comoponent
414  }
415  }
416  CnComV.Sort(false);
417 }
418 
419 template <class PGraph>
420 void GetSccSzCnt(const PGraph& Graph, TIntPrV& SccSzCnt) {
421  TSccVisitor<PGraph, true> Visitor(Graph);
422  TCnCom::GetDfsVisitor(Graph, Visitor);
423  Visitor.SccCntH.GetKeyDatPrV(SccSzCnt);
424  SccSzCnt.Sort(true);
425 }
426 
427 template <class PGraph>
428 void GetSccs(const PGraph& Graph, TCnComV& CnComV) {
429  TSccVisitor<PGraph, false> Visitor(Graph);
430  TCnCom::GetDfsVisitor(Graph, Visitor);
431  CnComV = Visitor.CnComV;
432  CnComV.Sort(false);
433 }
434 
435 template <class PGraph>
436 double GetMxWccSz(const PGraph& Graph) {
437  TCnComV CnComV;
438  GetWccs(Graph, CnComV);
439  if (Graph->GetNodes() == 0) { return 0; }
440  else { return CnComV[0].Len() / double(Graph->GetNodes()); }
441 }
442 
443 template <class PGraph>
444 double GetMxSccSz(const PGraph& Graph) {
445  TCnComV CnComV;
446  GetSccs(Graph, CnComV);
447  if (Graph->GetNodes() == 0) { return 0; }
448  else { return CnComV[0].Len() / double(Graph->GetNodes()); }
449 }
450 
451 template <class PGraph>
452 PGraph GetMxWcc(const PGraph& Graph) {
453  TCnComV CnComV;
454  GetWccs(Graph, CnComV);
455  if (CnComV.Empty()) { return PGraph::TObj::New(); }
456  int CcId = 0, MxSz = 0;
457  for (int i = 0; i < CnComV.Len(); i++) {
458  if (MxSz < CnComV[i].Len()) {
459  MxSz=CnComV[i].Len(); CcId=i; }
460  }
461  if (CnComV[CcId].Len()==Graph->GetNodes()) {
462  return Graph; }
463  else {
464  return TSnap::GetSubGraph(Graph, CnComV[CcId]());
465  }
466 }
467 
468 template <class PGraph>
469 PGraph GetMxScc(const PGraph& Graph) {
470  TCnComV CnComV;
471  GetSccs(Graph, CnComV);
472  if (CnComV.Empty()) { return PGraph::TObj::New(); }
473  int CcId = 0, MxSz = 0;
474  for (int i = 0; i < CnComV.Len(); i++) {
475  if (MxSz < CnComV[i].Len()) {
476  MxSz=CnComV[i].Len(); CcId=i; }
477  }
478  if (CnComV[CcId].Len()==Graph->GetNodes()) {
479  return Graph; }
480  else {
481  return TSnap::GetSubGraph(Graph, CnComV[CcId]());
482  }
483 }
484 
485 template <class PGraph>
486 PGraph GetMxBiCon(const PGraph& Graph) {
487  TCnComV CnComV;
488  GetBiCon(TSnap::ConvertGraph<PUNGraph, PGraph>(Graph), CnComV);
489  if (CnComV.Empty()) { return PGraph::TObj::New(); }
490  int CcId = 0, MxSz = 0;
491  for (int i = 0; i < CnComV.Len(); i++) {
492  if (MxSz < CnComV[i].Len()) {
493  MxSz=CnComV[i].Len(); CcId=i; }
494  }
495  if (CnComV[CcId].Len()==Graph->GetNodes()) {
496  return Graph; }
497  else {
498  return TSnap::GetSubGraph(Graph, CnComV[CcId]());
499  }
500 }
501 
502 } // namespace TSnap
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
static void Dump(const TCnComV &CnComV, const TStr &Desc=TStr())
Definition: cncom.cpp:3
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
TArtPointVisitor()
Definition: cncom.h:176
TInt Time
Definition: cncom.h:202
bool Empty()
Definition: ds.h:2591
void BackEdge(const int &NId1, const int &NId2)
Definition: cncom.h:186
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:999
void Add(const int &NodeId)
Definition: cncom.h:104
void Clr()
Definition: cncom.h:103
void FwdEdge(const int &NId1, const int &NId2)
Definition: cncom.h:267
TVec< TCnCom > TCnComV
Definition: cncom.h:3
void FinishNode(const int &NId)
Definition: cncom.h:248
TBiConVisitor(const int &Nodes)
Definition: cncom.h:205
Definition: ds.h:130
PGraph GetMxWcc(const PGraph &Graph)
Returns a graph representing the largest weakly connected component on an input Graph.
Definition: cncom.h:452
void GetArtPoints(const PUNGraph &Graph, TIntV &ArtNIdV)
Returns articulation points of a Graph.
Definition: cncom.cpp:48
double GetMxWccSz(const PGraph &Graph)
Returns the fraction of nodes in the largest weakly connected component of a Graph.
Definition: cncom.h:436
void GetNodeWcc(const PGraph &Graph, const int &NId, TIntV &CnCom)
Returns (via output parameter CnCom) all nodes that are in the same connected component as node NId...
Definition: cncom.h:277
TVal & Top()
Definition: ds.h:2595
TArtPointVisitor(const int &Nodes)
Definition: cncom.h:177
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TCnComV CnComV
Definition: cncom.h:241
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:1011
const TInt & GetRndNId() const
Definition: cncom.h:111
void GetKeyV(TVec< TKey > &KeyV) const
Definition: shash.h:1347
void Gen(const int &ExpectVals)
Definition: shash.h:1115
void GetBiConSzCnt(const PUNGraph &Graph, TIntPrV &SzCntV)
Returns a distribution of bi-connected component sizes.
Definition: cncom.cpp:31
int GetMinDiscTm(const int &NId1, const int &NId2) const
Definition: cncom.h:268
void GetSccs(const PGraph &Graph, TCnComV &CnComV)
Returns all strongly connected components in a Graph.
Definition: cncom.h:428
THash< TInt, TInt > ParentH
Definition: cncom.h:198
TVal1 Val1
Definition: ds.h:132
void ExamineEdge(const int &NId1, const int &NId2)
Definition: cncom.h:184
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
void ExamineEdge(const int &NId1, const int &NId2)
Definition: cncom.h:264
static TRnd Rnd
Definition: dt.h:1146
void GetSccSzCnt(const PGraph &Graph, TIntPrV &SccSzCnt)
Returns a distribution of strongly connected component sizes.
Definition: cncom.h:420
TCnComV CnComV
Definition: cncom.h:200
void FwdEdge(const int &NId1, const int &NId2)
Definition: cncom.h:228
TCnCom(TSIn &SIn)
Definition: cncom.h:95
void DiscoverNode(int NId)
Definition: cncom.h:206
void FinishNode(const int &NId)
Definition: cncom.h:207
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:954
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TSStack< TInt > Stack
Definition: cncom.h:238
TCnCom & operator=(const TCnCom &CC)
Definition: cncom.h:97
TBiConVisitor()
Definition: cncom.h:204
void Sort(const bool &Asc=true)
Definition: cncom.h:109
void TreeEdge(const int &NId1, const int &NId2)
Definition: cncom.h:265
TVal2 Val2
Definition: ds.h:133
static void GetDfsVisitor(const PGraph &Graph, TVisitor &Visitor)
Definition: cncom.h:124
int GetSecHashCd() const
Definition: cncom.h:120
TIntH SccCntH
Definition: cncom.h:240
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 DiscoverNode(int NId)
Definition: cncom.h:245
TIntSet NSet
Definition: cncom.h:201
Definition: cncom.h:88
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
TIntV NIdV
Definition: cncom.h:90
bool operator<(const TCnCom &CC) const
Definition: cncom.h:99
double GetMxSccSz(const PGraph &Graph)
Returns the fraction of nodes in the largest strongly connected component of a Graph.
Definition: cncom.h:444
void BackEdge(const int &NId1, const int &NId2)
Definition: cncom.h:266
TIntSet ArtSet
Definition: cncom.h:173
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
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:171
bool IsNIdIn(const int &NId) const
Definition: cncom.h:110
void FinishNode(const int &NId)
Definition: cncom.h:179
int AddKey(const TKey &Key)
Definition: shash.h:1254
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
const TIntV & operator()() const
Definition: cncom.h:106
int GetPrimHashCd() const
Definition: cncom.h:119
Definition: ds.h:2575
Definition: fl.h:128
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
TSStack< TIntPr > Stack
Definition: cncom.h:199
void TreeEdge(const int &NId1, const int &NId2)
Definition: cncom.h:221
Definition: dt.h:1137
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
const TInt & GetVal(const int &NIdN) const
Definition: cncom.h:108
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
TCnCom(const TCnCom &CC)
Definition: cncom.h:94
void Push()
Definition: ds.h:2597
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
Definition: ds.h:32
PGraph Graph
Definition: cncom.h:236
THash< TInt, TIntPr > VnLowH
Definition: cncom.h:197
void GetEdgeBridges(const PUNGraph &Graph, TIntPrV &EdgeV)
Returns bridge edges of a Graph.
Definition: cncom.cpp:55
bool IsWeaklyConn(const PGraph &Graph)
Tests whether the Graph is weakly connected.
Definition: cncom.h:310
void Pop()
Definition: ds.h:2599
void ExamineEdge(const int &NId1, const int &NId2)
Definition: cncom.h:220
void BackEdge(const int &NId1, const int &NId2)
Definition: cncom.h:224
Definition: dt.h:412
Strongly connected componetns Depht-First-Search visitor class.
Definition: cncom.h:234
bool IsConnected(const PGraph &Graph)
Tests whether the Graph is (weakly) connected.
Definition: cncom.h:305
TSccVisitor(const PGraph &_Graph)
Definition: cncom.h:243
bool operator==(const TCnCom &CC) const
Definition: cncom.h:98
void TreeEdge(const int &NId1, const int &NId2)
Definition: cncom.h:185
const TInt & operator[](const int &NIdN) const
Definition: cncom.h:105
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:214
Articulation point Depth-First-Search visitor class.
Definition: cncom.h:169
TCnCom()
Definition: cncom.h:92
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
TVal1 Val1
Definition: ds.h:34
int Len() const
Definition: cncom.h:101
TVal2 Val2
Definition: ds.h:35
void Save(TSOut &SOut) const
Definition: cncom.h:96
Definition: bd.h:196
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:171
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
bool IsKey(const TKey &Key) const
Definition: hash.h:258
bool Empty() const
Definition: cncom.h:102
TCnCom(const TIntV &NodeIdV)
Definition: cncom.h:93
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void FwdEdge(const int &NId1, const int &NId2)
Definition: cncom.h:189
TInt Time
Definition: cncom.h:239
void DiscoverNode(int NId)
Definition: cncom.h:178
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
TVal3 Val3
Definition: ds.h:134
THash< TInt, TInt > ParentH
Definition: cncom.h:172
PGraph GetMxScc(const PGraph &Graph)
Returns a graph representing the largest strongly connected component on an input Graph...
Definition: cncom.h:469
THash< TInt, TIntPr > TmRtH
Definition: cncom.h:237