SNAP Library 4.0, User 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.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);
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);
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
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:2590
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:2594
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:1143
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:2574
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:1134
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:2596
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:2598
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:201
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