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
motifcluster.cpp
Go to the documentation of this file.
1 #include "stdafx.h"
2 #include "motifcluster.h"
3 
4 #if defined(F77_POST)
5 # define F77_NAME(name) name ## _
6 #else
7 # define F77_NAME(name) name
8 #endif
9 
11 // ARPACK routines for symmetric eigenvalue problem
12 extern "C" {
13  void F77_NAME(dsaupd)(int *ido, char *bmat, int *n, char *which, int *nev,
14  double *tol, double *resid, int *ncv, double *V,
15  int *ldv, int *iparam, int *ipntr, double *workd,
16  double *workl, int *lworkl, int *info);
17 
18  void F77_NAME(dseupd)(int *rvec, char *HowMny, int *select, double *d,
19  double *Z, int *ldz, double *sigma, char *bmat, int *n,
20  char *which, int *nev, double *tol, double *resid,
21  int *ncv, double *V, int *ldv, int *iparam, int *ipntr,
22  double *workd, double *workl, int *lworkl, int *info);
23 }
24 
26 // Utility functions
27 
28 // Increments weight on (i, j) by one
29 static void IncrementWeight(int i, int j, WeightVH& weights) {
30  int minval = MIN(i, j);
31  int maxval = MAX(i, j);
32  THash<TInt, TInt>& edge_weights = weights[minval];
33  edge_weights(maxval) += 1;
34 }
35 
37  TStr motif_lc = motif.GetLc();
38  if (motif_lc == "m1") { return M1; }
39  else if (motif_lc == "m2") { return M2; }
40  else if (motif_lc == "m3") { return M3; }
41  else if (motif_lc == "m4") { return M4; }
42  else if (motif_lc == "m5") { return M5; }
43  else if (motif_lc == "m6") { return M6; }
44  else if (motif_lc == "m7") { return M7; }
45  else if (motif_lc == "m8") { return M8; }
46  else if (motif_lc == "m9") { return M9; }
47  else if (motif_lc == "m10") { return M10; }
48  else if (motif_lc == "m11") { return M11; }
49  else if (motif_lc == "m12") { return M12; }
50  else if (motif_lc == "m13") { return M13; }
51  else if (motif_lc == "bifan") { return bifan; }
52  else if (motif_lc == "bi-fan") { return bifan; }
53  else if (motif_lc == "triangle") { return triangle; }
54  else if (motif_lc == "clique3") { return clique3; }
55  else if (motif_lc == "clique4") { return clique4; }
56  else if (motif_lc == "clique5") { return clique5; }
57  else if (motif_lc == "clique6") { return clique6; }
58  else if (motif_lc == "clique7") { return clique7; }
59  else if (motif_lc == "clique8") { return clique8; }
60  else if (motif_lc == "clique9") { return clique9; }
61  else if (motif_lc == "semiclique") { return semiclique; }
62  else if (motif_lc == "semi-clique") { return semiclique; }
63  else if (motif_lc == "edge") { return edge; }
64  else if (motif_lc == "undir") { return edge; }
65  else if (motif_lc == "undirected") { return edge; }
66  else { TExcept::Throw("Unknown motif"); }
67  return edge;
68 }
69 
71 // Subgraph type checking
72 bool MotifCluster::IsNoEdge(PNGraph graph, int u, int v) {
73  return !graph->IsEdge(u, v) && !graph->IsEdge(v, u);
74 }
75 
76 bool MotifCluster::IsUnidirEdge(PNGraph graph, int u, int v) {
77  return graph->IsEdge(u, v) && !graph->IsEdge(v, u);
78 }
79 
80 bool MotifCluster::IsBidirEdge(PNGraph graph, int u, int v) {
81  return graph->IsEdge(u, v) && graph->IsEdge(v, u);
82 }
83 
84 bool MotifCluster::IsMotifM1(PNGraph graph, int u, int v, int w) {
85  return ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, v, w) &&
86  IsUnidirEdge(graph, w, u)) ||
87  (IsUnidirEdge(graph, u, w) && IsUnidirEdge(graph, w, v) &&
88  IsUnidirEdge(graph, v, u)));
89 }
90 
91 bool MotifCluster::IsMotifM2(PNGraph graph, int u, int v, int w) {
92  return ((IsBidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w) &&
93  IsUnidirEdge(graph, w, v)) ||
94  (IsBidirEdge(graph, u, v) && IsUnidirEdge(graph, w, u) &&
95  IsUnidirEdge(graph, v, w)) ||
96  (IsBidirEdge(graph, u, w) && IsUnidirEdge(graph, u, v) &&
97  IsUnidirEdge(graph, v, w)) ||
98  (IsBidirEdge(graph, u, w) && IsUnidirEdge(graph, v, u) &&
99  IsUnidirEdge(graph, w, v)) ||
100  (IsBidirEdge(graph, v, w) && IsUnidirEdge(graph, v, u) &&
101  IsUnidirEdge(graph, u, w)) ||
102  (IsBidirEdge(graph, v, w) && IsUnidirEdge(graph, u, v) &&
103  IsUnidirEdge(graph, w, u)));
104 }
105 
106 bool MotifCluster::IsMotifM3(PNGraph graph, int u, int v, int w) {
107  if ((IsBidirEdge( graph, u, v) && IsBidirEdge( graph, v, w)) &&
108  (IsUnidirEdge(graph, u, w) || IsUnidirEdge(graph, w, u))) { return true; }
109  if ((IsBidirEdge( graph, u, w) && IsBidirEdge( graph, w, v)) &&
110  (IsUnidirEdge(graph, u, v) || IsUnidirEdge(graph, v, u))) { return true; }
111  if ((IsBidirEdge( graph, w, u) && IsBidirEdge( graph, u, v)) &&
112  (IsUnidirEdge(graph, w, v) || IsUnidirEdge(graph, v, w))) { return true; }
113  return false;
114 }
115 
116 bool MotifCluster::IsMotifM4(PNGraph graph, int u, int v, int w) {
117  return IsBidirEdge(graph, u, v) && IsBidirEdge(graph, u, w) &&
118  IsBidirEdge(graph, v, w);
119 }
120 
121 bool MotifCluster::IsMotifM5(PNGraph graph, int u, int v, int w) {
122  if ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w)) &&
123  (IsUnidirEdge(graph, v, w) || IsUnidirEdge(graph, w, v))) { return true; }
124  if ((IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, v, w)) &&
125  (IsUnidirEdge(graph, u, w) || IsUnidirEdge(graph, w, u))) { return true; }
126  if ((IsUnidirEdge(graph, w, v) && IsUnidirEdge(graph, w, u)) &&
127  (IsUnidirEdge(graph, v, u) || IsUnidirEdge(graph, u, v))) { return true; }
128  return false;
129 }
130 
131 bool MotifCluster::IsMotifM6(PNGraph graph, int u, int v, int w) {
132  return ((IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, u, w) &&
133  IsBidirEdge(graph, v, w)) ||
134  (IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, v, w) &&
135  IsBidirEdge(graph, u, w)) ||
136  (IsUnidirEdge(graph, w, u) && IsUnidirEdge(graph, w, v) &&
137  IsBidirEdge(graph, u, v)));
138 }
139 
140 bool MotifCluster::IsMotifM7(PNGraph graph, int u, int v, int w) {
141  return ((IsUnidirEdge(graph, v, u) && IsUnidirEdge(graph, w, u) &&
142  IsBidirEdge(graph, v, w)) ||
143  (IsUnidirEdge(graph, u, v) && IsUnidirEdge(graph, w, v) &&
144  IsBidirEdge(graph, u, w)) ||
145  (IsUnidirEdge(graph, u, w) && IsUnidirEdge(graph, v, w) &&
146  IsBidirEdge(graph, u, v)));
147 }
148 
149 bool MotifCluster::IsMotifM8(PNGraph graph, int center, int v, int w) {
150  return IsNoEdge(graph, v, w) && IsUnidirEdge(graph, center, v) &&
151  IsUnidirEdge(graph, center, w);
152 }
153 
154 bool MotifCluster::IsMotifM9(PNGraph graph, int center, int v, int w) {
155  return IsNoEdge(graph, v, w) &&
156  ((IsUnidirEdge(graph, center, v) && IsUnidirEdge(graph, w, center)) ||
157  (IsUnidirEdge(graph, center, w) && IsUnidirEdge(graph, v, center)));
158 }
159 
160 bool MotifCluster::IsMotifM10(PNGraph graph, int center, int v, int w) {
161  return IsNoEdge(graph, v, w) && IsUnidirEdge(graph, v, center) &&
162  IsUnidirEdge(graph, w, center);
163 }
164 
165 bool MotifCluster::IsMotifM11(PNGraph graph, int center, int v, int w) {
166  return IsNoEdge(graph, v, w) &&
167  ((IsBidirEdge(graph, center, v) && IsUnidirEdge(graph, center, w)) ||
168  (IsBidirEdge(graph, center, w) && IsUnidirEdge(graph, center, v)));
169 }
170 
171 bool MotifCluster::IsMotifM12(PNGraph graph, int center, int v, int w) {
172  return IsNoEdge(graph, v, w) &&
173  ((IsBidirEdge(graph, center, v) && IsUnidirEdge(graph, w, center)) ||
174  (IsBidirEdge(graph, center, w) && IsUnidirEdge(graph, v, center)));
175 }
176 
177 bool MotifCluster::IsMotifM13(PNGraph graph, int center, int v, int w) {
178  return IsNoEdge(graph, v, w) && IsBidirEdge(graph, center, v)
179  && IsBidirEdge(graph, center, w);
180 }
181 
182 
184 // Triangle weighting
186  // Note: This is the most efficient when the nodes are numbered
187  // 0, 1, ..., num_nodes - 1.
188  int max_nodes = graph->GetMxNId() + 1;
189  TVec< TKeyDat<TInt, TInt> > degrees(max_nodes);
190  degrees.PutAll(TKeyDat<TInt, TInt>(0, 0));
191  // Set the degree of a node to be the number of nodes adjacent to the node in
192  // the undirected graph.
193  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
194  int src = NI.GetId();
195  int num_nbrs = NI.GetOutDeg();
196  // For each incoming edge that is not an outgoing edge, include it.
197  for (int i = 0; i < NI.GetInDeg(); ++i) {
198  int dst = NI.GetInNId(i);
199  if (!NI.IsOutNId(dst)) {
200  ++num_nbrs;
201  }
202  }
203  degrees[src] = TKeyDat<TInt, TInt>(num_nbrs, src);
204  }
205 
206  degrees.Sort();
207  order = TIntV(max_nodes);
208  for (int i = 0; i < order.Len(); ++i) {
209  order[degrees[i].Dat] = i;
210  }
211 }
212 
214  WeightVH& weights) {
215  TIntV order;
216  DegreeOrdering(graph, order);
217  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
218  int src = NI.GetId();
219  int src_pos = order[src];
220 
221  // Get all neighbors who come later in the ordering
222  TIntV neighbors_higher;
223  for (int i = 0; i < NI.GetOutDeg(); i++) {
224  int nbr = NI.GetOutNId(i);
225  if (order[nbr] > src_pos) {
226  neighbors_higher.Add(nbr);
227  }
228  }
229  for (int i = 0; i < NI.GetInDeg(); i++) {
230  int nbr = NI.GetInNId(i);
231  if (!NI.IsOutNId(nbr) && order[nbr] > src_pos) {
232  neighbors_higher.Add(nbr);
233  }
234  }
235 
236  for (int ind1 = 0; ind1 < neighbors_higher.Len(); ind1++) {
237  for (int ind2 = ind1 + 1; ind2 < neighbors_higher.Len(); ind2++) {
238  int dst1 = neighbors_higher[ind1];
239  int dst2 = neighbors_higher[ind2];
240  // Check for triangle formation
241  if (graph->IsEdge(dst1, dst2) || graph->IsEdge(dst2, dst1)) {
242  bool motif_occurs = false;
243  switch (motif) {
244  case M1:
245  motif_occurs = IsMotifM1(graph, src, dst1, dst2);
246  break;
247  case M2:
248  motif_occurs = IsMotifM2(graph, src, dst1, dst2);
249  break;
250  case M3:
251  motif_occurs = IsMotifM3(graph, src, dst1, dst2);
252  break;
253  case M4:
254  motif_occurs = IsMotifM4(graph, src, dst1, dst2);
255  break;
256  case M5:
257  motif_occurs = IsMotifM5(graph, src, dst1, dst2);
258  break;
259  case M6:
260  motif_occurs = IsMotifM6(graph, src, dst1, dst2);
261  break;
262  case M7:
263  motif_occurs = IsMotifM7(graph, src, dst1, dst2);
264  break;
265  default:
266  TExcept::Throw("Unknown directed triangle motif");
267  }
268  // Increment weights of the triad (src, dst1, dst2) if it occurs.
269  if (motif_occurs) {
270  IncrementWeight(src, dst1, weights);
271  IncrementWeight(src, dst2, weights);
272  IncrementWeight(dst1, dst2, weights);
273  }
274  }
275  }
276  }
277  }
278 }
279 
281 // Wedge weighting
283  WeightVH& weights) {
284  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
285  int center = NI.GetId();
286 
287  // Get all neighbors
288  TIntV neighbors;
289  for (int i = 0; i < NI.GetOutDeg(); i++) {
290  int nbr = NI.GetOutNId(i);
291  neighbors.Add(nbr);
292  }
293  for (int i = 0; i < NI.GetInDeg(); i++) {
294  int nbr = NI.GetInNId(i);
295  if (!NI.IsOutNId(nbr)) {
296  neighbors.Add(nbr);
297  }
298  }
299 
300  for (int ind1 = 0; ind1 < neighbors.Len(); ind1++) {
301  for (int ind2 = ind1 + 1; ind2 < neighbors.Len(); ind2++) {
302  int dst1 = neighbors[ind1];
303  int dst2 = neighbors[ind2];
304  bool motif_occurs = false;
305  switch (motif) {
306  case M8:
307  motif_occurs = IsMotifM8(graph, center, dst1, dst2);
308  break;
309  case M9:
310  motif_occurs = IsMotifM9(graph, center, dst1, dst2);
311  break;
312  case M10:
313  motif_occurs = IsMotifM10(graph, center, dst1, dst2);
314  break;
315  case M11:
316  motif_occurs = IsMotifM11(graph, center, dst1, dst2);
317  break;
318  case M12:
319  motif_occurs = IsMotifM12(graph, center, dst1, dst2);
320  break;
321  case M13:
322  motif_occurs = IsMotifM13(graph, center, dst1, dst2);
323  break;
324  default:
325  TExcept::Throw("Unknown directed wedge motif");
326  }
327  // Increment weights of (center, dst1, dst2) if it occurs.
328  if (motif_occurs) {
329  IncrementWeight(center, dst1, weights);
330  IncrementWeight(center, dst2, weights);
331  IncrementWeight(dst1, dst2, weights);
332  }
333  }
334  }
335  }
336 }
337 
338 
340 // Bifan weighting
342  // Find all pairs of nodes that are not adjacent
343  // Note: does not scale to large sparse networks but will work for smaller
344  // networks such as common neuronal connectivity datasets.
345  TIntV node_ids;
346  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
347  node_ids.Add(NI.GetId());
348  }
349  for (int i = 0; i < node_ids.Len(); i++) {
350  for (int j = i + 1; j < node_ids.Len(); j++) {
351  int src1 = node_ids[i];
352  int src2 = node_ids[j];
353  if (IsNoEdge(graph, src1, src2)) {
354  // All unidirectional out-neighbors of src1
355  THash<TInt, TInt> nbr_counts;
356  TNGraph::TNodeI NI1 = graph->GetNI(src1);
357  for (int k = 0; k < NI1.GetOutDeg(); k++) {
358  int nbr = NI1.GetOutNId(k);
359  if (IsUnidirEdge(graph, src1, nbr)) {
360  nbr_counts(nbr) += 1;
361  }
362  }
363 
364  // All unidirectional out-neighbors of src2
365  TNGraph::TNodeI NI2 = graph->GetNI(src2);
366  for (int k = 0; k < NI2.GetOutDeg(); k++) {
367  int nbr = NI2.GetOutNId(k);
368  if (IsUnidirEdge(graph, src2, nbr)) {
369  nbr_counts(nbr) += 1;
370  }
371  }
372 
373  // Get all common outgoing neighbors
374  TIntV common;
375  for (THash<TInt, TInt>::TIter it = nbr_counts.BegI();
376  it < nbr_counts.EndI(); it++) {
377  if (it->Dat == 2) {
378  common.Add(it->Key);
379  }
380  }
381 
382  // Update weights with all common neighbors
383  for (int ind1 = 0; ind1 < common.Len(); ind1++) {
384  for (int ind2 = (ind1 + 1); ind2 < common.Len(); ind2++) {
385  int dst1 = common[ind1];
386  int dst2 = common[ind2];
387  if (IsNoEdge(graph, dst1, dst2)) {
388  IncrementWeight(src1, src2, weights);
389  IncrementWeight(src1, dst1, weights);
390  IncrementWeight(src1, dst2, weights);
391  IncrementWeight(src2, dst1, weights);
392  IncrementWeight(src2, dst2, weights);
393  IncrementWeight(dst1, dst2, weights);
394  }
395  }
396  }
397  }
398  }
399  }
400 }
401 
402 
404 // Semiclique weighting
406  for (TUNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI++) {
407  int src = NI.GetId();
408  for (int j = 0; j < NI.GetDeg(); j++) {
409  int dst = NI.GetNbrNId(j);
410  if (dst <= src) { continue; }
411 
412  // Common neighbors of dst that are neighbors of src
413  TIntV common;
414  TUNGraph::TNodeI dst_NI = graph->GetNI(dst);
415  for (int k = 0; k < dst_NI.GetOutDeg(); k++) {
416  int nbr = dst_NI.GetNbrNId(k);
417  if (nbr != src && nbr != dst && NI.IsNbrNId(nbr)) {
418  common.Add(nbr);
419  }
420  }
421 
422  for (int k = 0; k < common.Len(); k++) {
423  for (int l = k + 1; l < common.Len(); l++) {
424  int nbr1 = common[k];
425  int nbr2 = common[l];
426  if (!graph->IsEdge(nbr1, nbr2)) {
427  IncrementWeight(src, dst, weights);
428  IncrementWeight(src, nbr1, weights);
429  IncrementWeight(src, nbr2, weights);
430  IncrementWeight(dst, nbr1, weights);
431  IncrementWeight(dst, nbr2, weights);
432  IncrementWeight(nbr1, nbr2, weights);
433  }
434  }
435  }
436  }
437  }
438 }
439 
440 
442 // Simple edge weighting
444  for (TNGraph::TEdgeI it = graph->BegEI(); it < graph->EndEI(); it++) {
445  int src = it.GetSrcNId();
446  int dst = it.GetDstNId();
447  if (src == dst) {
448  continue;
449  }
450  // Only count reciprocated edges if src < dst
451  if (!graph->IsEdge(dst, src) || src < dst) {
452  IncrementWeight(src, dst, weights);
453  }
454  }
455 }
456 
458  for (TUNGraph::TEdgeI it = graph->BegEI(); it < graph->EndEI(); it++) {
459  int src = it.GetSrcNId();
460  int dst = it.GetDstNId();
461  if (src == dst) {
462  continue;
463  }
464  IncrementWeight(src, dst, weights);
465  }
466 }
467 
468 
470 // Motif adjacency formation
472  WeightVH& weights) {
473  weights = WeightVH(graph->GetMxNId() + 1);
474  switch (motif) {
475  case M1:
476  case M2:
477  case M3:
478  case M4:
479  case M5:
480  case M6:
481  case M7:
482  TriangleMotifAdjacency(graph, motif, weights);
483  break;
484  case M8:
485  case M9:
486  case M10:
487  case M11:
488  case M12:
489  case M13:
490  WedgeMotifAdjacency(graph, motif, weights);
491  break;
492  case bifan:
493  BifanMotifAdjacency(graph, weights);
494  break;
495  case edge:
496  EdgeMotifAdjacency(graph, weights);
497  break;
498  default:
499  TExcept::Throw("Unknown directed motif type");
500  }
501 }
502 
503 void MotifCluster::CliqueMotifAdjacency(PUNGraph graph, int clique_size,
504  WeightVH& weights) {
505  ChibaNishizekiWeighter cnw(graph);
506  cnw.Run(clique_size);
507  weights = cnw.weights();
508 }
509 
511  WeightVH& weights) {
512  weights = WeightVH(graph->GetMxNId() + 1);
513  switch (motif) {
514  case triangle:
515  case clique3:
516  CliqueMotifAdjacency(graph, 3, weights);
517  break;
518  case clique4:
519  CliqueMotifAdjacency(graph, 4, weights);
520  break;
521  case clique5:
522  CliqueMotifAdjacency(graph, 5, weights);
523  break;
524  case clique6:
525  CliqueMotifAdjacency(graph, 6, weights);
526  break;
527  case clique7:
528  CliqueMotifAdjacency(graph, 7, weights);
529  break;
530  case clique8:
531  CliqueMotifAdjacency(graph, 8, weights);
532  break;
533  case clique9:
534  CliqueMotifAdjacency(graph, 9, weights);
535  break;
536  case semiclique:
537  SemicliqueMotifAdjacency(graph, weights);
538  break;
539  case edge:
540  EdgeMotifAdjacency(graph, weights);
541  default:
542  TExcept::Throw("Unknown undirected motif type");
543  }
544 }
545 
546 
548 // Clique weighting
550  k_ = k;
551  C_.Clr();
552 
553  // Process the k - 1 core
554  PUNGraph kcore = TSnap::GetKCore(orig_graph_, k - 1);
555  TSnap::DelSelfEdges(kcore);
556  int max_nodes = kcore->GetMxNId();
557  for (int i = 0; i <= max_nodes; i++) {
558  if (!kcore->IsNode(i)) {
559  kcore->AddNode(i);
560  }
561  }
562 
563  int N = kcore->GetNodes();
564  weights_ = WeightVH(N);
565  graph_ = TVec < TVec<TIntV> >(k + 2);
566  for (int i = 0; i < k + 2; ++i) {
567  graph_[i] = TVec<TIntV>(N);
568  }
569  labels_ = TIntV(N);
570  labels_.PutAll(k);
571 
572  TVec<TIntV>& graph_k = graph_[k];
573  for (int src = 0; src < N; src++) {
574  TUNGraph::TNodeI src_it = kcore->GetNI(src);
575  int deg = src_it.GetDeg();
576  graph_k[src] = TIntV(deg);
577  for (int edge = 0; edge < deg; edge++) {
578  int dst = src_it.GetNbrNId(edge);
579  graph_k[src][edge] = dst;
580  }
581  }
582 }
583 
585  Initialize(k);
586  TIntV U(graph_[k].Len());
587  for (int i = 0; i < U.Len(); i++) {
588  U[i] = i;
589  }
590  CliqueEnum(k, U);
591 }
592 
594  TIntV& order) {
595  TVec< TKeyDat<TInt, TInt> > degs(U.Len());
596  int end_size = 0;
597  for (int i = 0; i < U.Len(); i++) {
598  int node = U[i];
599  int size = graph_[k][node].Len();
600  if (size > 0) {
601  degs[end_size] = TKeyDat<TInt, TInt>(-size, node);
602  ++end_size;
603  }
604  }
605  // Only keep nodes with degree > 0
606  degs.Trunc(end_size);
607  // Sort by increasing degree
608  degs.Sort();
609 
610  order = TIntV(degs.Len());
611  for (int i = 0; i < degs.Len(); i++) {
612  order[i] = degs[i].Dat;
613  }
614 }
615 
617  for (int i = 0; i < clique.Len(); ++i) {
618  for (int j = i + 1; j < clique.Len(); ++j) {
619  IncrementWeight(clique[i], clique[j], weights_);
620  }
621  }
622 }
623 
625  for (int i = 0; i < U.Len(); i++) {
626  int node = U[i];
627  TIntV& nbrs = graph_[2][node];
628  for (int j = 0; j < nbrs.Len(); j++) {
629  int nbr = nbrs[j];
630  // Only count each edge once
631  if (node < nbr) {
632  TIntV clique(C_.Len() + 2);
633  clique[0] = node;
634  clique[1] = nbr;
635  for (int k = 0; k < C_.Len(); k++) {
636  clique[k + 2] = C_[k];
637  }
638  UpdateWeights(clique);
639  }
640  }
641  }
642 }
643 
644 void ChibaNishizekiWeighter::AdjustLabels(int kcurr, int klast, const TIntV& Up) {
645  for (int i = 0; i < Up.Len(); i++) {
646  int node = Up[i];
647  TIntV& nbrs_kcurr = graph_[kcurr][node];
648  TIntV& nbrs_klast = graph_[klast][node];
649  TIntV nbrs_klast_new;
650  for (int j = 0; j < nbrs_klast.Len(); j++) {
651  int nbr = nbrs_klast[j];
652  if (labels_[nbr] == kcurr) {
653  nbrs_kcurr.Add(nbr);
654  } else {
655  nbrs_klast_new.Add(nbr);
656  }
657  }
658  graph_[klast][node] = nbrs_klast_new;
659  }
660 }
661 
663  // Handle base case
664  if (k == 2) {
665  FlushCliques(U);
666  return;
667  }
668 
669  // Get the degrees of nodes in U
670  TIntV order;
671  SubgraphDegreeOrder(k, U, order);
672  for (int i = 0; i < order.Len(); i++) {
673  int vi = order[i];
674  // Get neighbors of current node in the subgraph
675  TIntV& U_prime = graph_[k][vi];
676 
677  // Re-label
678  for (int j = 0; j < U_prime.Len(); j++) {
679  labels_[U_prime[j]] = k - 1;
680  }
681  AdjustLabels(k - 1, k, U_prime);
682 
683  // Recurse
684  C_.Add(vi);
685  CliqueEnum(k - 1, U_prime);
686  C_.DelLast();
687 
688  // Re-label
689  for (int j = 0; j < U_prime.Len(); j++) {
690  labels_[U_prime[j]] = k;
691  }
692  AdjustLabels(k, k - 1, U_prime);
693  labels_[vi] = k + 1;
694  AdjustLabels(k + 1, k, U_prime);
695  }
696 }
697 
698 
700 // Spectral stuff
702  TSweepCut& sweepcut, double tol,
703  int maxiter) {
704  WeightVH weights;
705  MotifAdjacency(graph, motif, weights);
706  SpectralCut(weights, sweepcut, tol, maxiter);
707 }
708 
710  TSweepCut& sweepcut, double tol,
711  int maxiter) {
712  WeightVH weights;
713  MotifAdjacency(graph, motif, weights);
714  SpectralCut(weights, sweepcut, tol, maxiter);
715 }
716 
718  double tol, int maxiter) {
719  if (W.GetRows() != W.GetCols()) {
720  TExcept::Throw("Matrix must be square.");
721  }
722 
723  int N = W.GetCols();
724 
725  // all ones vector
726  TFltV e(N);
727  e.PutAll(1.0);
728  // degree vector
729  TFltV d(N);
730  d.PutAll(0.0);
731  W.Multiply(e, d);
732 
733  // Unit first eigenvector and d^{-1/2}
734  TFltV v0(N);
735  TFltV dnorm(N);
736  for (int i = 0; i < d.Len(); i++) {
737  if (d[i] <= 0.0) {
738  TExcept::Throw("Node with zero degree.");
739  }
740  v0[i] = TMath::Sqrt(d[i]);
741  dnorm[i] = 1.0 / TMath::Sqrt(d[i]);
742  }
743  TLinAlg::Normalize(v0);
744 
745  // Form I + Ln, where Ln is normalized Laplacian
746  TVec< TIntFltKdV > L_weights(N);
747  for (int j = 0; j < N; j++) {
748  const TIntFltKdV& W_col = W.ColSpVV[j];
749  TIntFltKdV& L_col = L_weights[j];
750  for (int ind = 0; ind < W_col.Len(); ind++) {
751  int i = W_col[ind].Key;
752  double val = W_col[ind].Dat;
753  L_col.Add(TIntFltKd(i, -val * dnorm[i] * dnorm[j]));
754  }
755  L_col.Add(TIntFltKd(j, 2.0));
756  }
757 
758  TSparseColMatrix L(L_weights, N, N);
759  TFltV evals;
760  TFullColMatrix evecs;
761  SymeigsSmallest(L, 2, evals, evecs, tol, maxiter);
762  fvec = evecs.ColV[1];
763  for (int i = 0; i < fvec.Len(); i++) {
764  fvec[i] *= dnorm[i];
765  }
766  // Adjust by 1 on the eigenvalue since we added the identity
767  return evals[1] - 1;
768 }
769 
770 // Given a vector of hashmaps representing weights in a graph, construct the
771 // undirected, unweighted. graph with the same network structure.
773  int num_edges = 0;
774  for (int i = 0; i < weights.Len(); i++) {
775  num_edges += weights[i].Len();
776  }
777  PUNGraph graph = TUNGraph::New(weights.Len(), num_edges);
778  for (int i = 0; i < weights.Len(); i++) {
779  graph->AddNode(i);
780  }
781  for (int i = 0; i < weights.Len(); i++) {
782  const THash<TInt, TInt>& edge_list = weights[i];
783  for (THash<TInt, TInt>::TIter it = edge_list.BegI(); it < edge_list.EndI();
784  it++) {
785  graph->AddEdge(i, it->Key);
786  }
787  }
788 
789  return graph;
790 }
791 
792 // Maps a vector of unique ids to 0, 1, ..., num_ids - 1. Sets up data
793 // structures id_map and rev_id_map so that
794 // id_map[original_id] = new_id
795 // rev_id_map[new_id] = original_id
796 static void MapIdsToFirstN(const TIntV& ids, THash<TInt, TInt>& id_map,
797  TIntV& rev_id_map) {
798  id_map = THash<TInt, TInt>();
799  rev_id_map = TIntV(ids.Len());
800  for (int i = 0; i < ids.Len(); i++) {
801  int id = ids[i];
802  if (id_map.IsKey(id)) {
803  TExcept::Throw("List of ids is not unique.");
804  }
805  id_map(id) = i;
806  rev_id_map[i] = id;
807  }
808 }
809 
810 // Run a sweep cut on the network represented by W and Fiedler vector fvec,
811 // storing the conductances from the sweep in conds and the order of the nodes
812 // in order.
813 static void Sweep(const TSparseColMatrix& W, const TFltV& fvec, TFltV& conds,
814  TIntV& order) {
815  // Get ordering of nodes
816 
817  TVec< TKeyDat<TFlt, TInt> > fvec_inds(fvec.Len());
818  for (int i = 0; i < fvec.Len(); i++) {
819  fvec_inds[i] = TKeyDat<TFlt, TInt>(fvec[i], i);
820  }
821  fvec_inds.Sort();
822  order = TIntV(fvec.Len());
823  TIntV rank(fvec.Len());
824  for (int i = 0; i < fvec.Len(); i++) {
825  order[i] = fvec_inds[i].Dat;
826  rank[order[i]] = i;
827  }
828 
829  // Sweep by adjusting cut and volume
830  conds = TFltV(order.Len() - 1);
831  double cut = 0;
832  double vol = 0;
833  double total_vol = 0;
834  for (int ind = 0; ind < order.Len(); ind++) {
835  const TIntFltKdV& nbr_weights = W.ColSpVV[ind];
836  for (TIntFltKdV::TIter it = nbr_weights.BegI(); it < nbr_weights.EndI();
837  it++) {
838  total_vol += it->Dat;
839  }
840  }
841  double vol_comp = total_vol;
842 
843  for (int ind = 0; ind < order.Len() - 1; ind++) {
844  int node = order[ind];
845  const TIntFltKdV& nbr_weights = W.ColSpVV[node];
846  for (TIntFltKdV::TIter it = nbr_weights.BegI(); it < nbr_weights.EndI();
847  it++) {
848  int nbr = it->Key;
849  if (node == nbr) { continue; }
850  double val = it->Dat;
851  // Adjust the cut amount
852  if (rank[nbr] > ind) {
853  // nbr is on the other side: add to the cut
854  cut += val;
855  } else {
856  // now on the same side as nbr: subtract from the cut
857  cut -= val;
858  }
859  vol += val;
860  vol_comp -= val;
861  }
862 
863  double mvol = MIN(vol, vol_comp);
864  if (mvol <= 0.0) {
865  TExcept::Throw("Nonpositive set volume.");
866  }
867  conds[ind] = cut / mvol;
868  }
869 }
870 
871 void MotifCluster::SpectralCut(const WeightVH& weights, TSweepCut& sweepcut,
872  double tol, int maxiter) {
873  // Form graph and get maximum component
874  PUNGraph graph = UnweightedGraphRepresentation(weights);
875  TCnComV components;
876  TSnap::GetWccs(graph, components);
877  int max_wcc_size = 0;
878  int max_wcc_ind = -1;
879  for (int i = 0; i < components.Len(); i++) {
880  int size = components[i].Len();
881  if (size > max_wcc_size) {
882  max_wcc_size = size;
883  max_wcc_ind = i;
884  }
885  }
886  TCnCom comp = components[max_wcc_ind];
887  sweepcut.component = comp;
888  if (comp.Len() == 1) {
889  printf("WARNING: No non-trivial connected components "
890  "(likely due to no instances of the motif)\n");
891  sweepcut.cond = 0;
892  sweepcut.eig = 0;
893  return;
894  }
895 
896 
897  // Map largest connected component to a matrix, keeping track of ids.
898  THash<TInt, TInt> id_map;
899  TIntV rev_id_map;
900  MapIdsToFirstN(comp.NIdV, id_map, rev_id_map);
901 
902  TVec<TIntFltKdV> matrix_entries(comp.Len());
903  for (int ind1 = 0; ind1 < comp.Len(); ++ind1) {
904  int c_ind = comp[ind1];
905  const THash<TInt, TInt>& edge_list = weights[c_ind];
906  int i_ind = id_map(c_ind);
907  TIntFltKdV& col = matrix_entries[i_ind];
908  for (THash<TInt, TInt>::TIter it = edge_list.BegI(); it < edge_list.EndI();
909  it++) {
910  int ind2 = it->Key;
911  int val = it->Dat;
912  if (comp.IsNIdIn(ind2)) {
913  int j_ind = id_map(ind2);
914  col.Add(TIntFltKd(j_ind, val));
915  // Add symmetric part
916  matrix_entries[j_ind].Add(TIntFltKd(i_ind, val));
917  }
918  }
919  }
920 
921  // Get Fiedler vector and run the sweep
922  TSparseColMatrix W(matrix_entries, comp.Len(), comp.Len());
923  TFltV fvec;
924  sweepcut.eig = NFiedlerVector(W, fvec, tol, maxiter);
925 
926  TFltV conds;
927  TIntV order;
928  Sweep(W, fvec, conds, order);
929  sweepcut.sweep_profile = conds;
930 
931  // Extract the cluster
932  double min_cond = 2.0;
933  int min_ind = -1;
934  for (int i = 0; i < conds.Len(); i++) {
935  double cond = conds[i];
936  if (cond < min_cond) {
937  min_cond = cond;
938  min_ind = i;
939  }
940  }
941  sweepcut.cond = min_cond;
942  TIntV cluster;
943  int start = 0;
944  int end = min_ind + 1;
945  if (end >= conds.Len() / 2) {
946  start = min_ind + 1;
947  end = conds.Len() + 1;
948  }
949  for (int i = start; i < end; i++) {
950  cluster.Add(rev_id_map[order[i]]);
951  }
952  sweepcut.cluster = cluster;
953 }
954 
955 void SymeigsSmallest(const TSparseColMatrix& A, int nev, TFltV& evals,
956  TFullColMatrix& evecs, double tol, int maxiter) {
957  // type of problem
958  int mode = 1;
959  // communication variable
960  int ido = 0;
961  // standard eigenvalue problem
962  char bmat = 'I';
963  // dimension of problem
964  int n = A.GetCols();
965  // type of eigenvector (smallest algebraic)
966  char which[] = "SA";
967  // Space for residual
968  double *resid = new double[n];
969  // Number of lanczos vectors
970  int ncv = MIN(MAX(2 * nev, 20), n - 1);
971  // Space for Lanczos basis vectors
972  double *V = new double[ncv * n];
973 
974  // dimension of basis vectors
975  int ldv = n;
976  // Various input / output data
977  int *iparam = new int[11];
978  // exact shifts
979  iparam[0] = 1;
980  // maximum number of iterations
981  iparam[2] = maxiter;
982  // mode
983  iparam[6] = mode;
984  // Output data
985  int *ipntr = new int[11];
986  // work array
987  double *workd = new double[3 * n];
988  // output workspace
989  int lworkl = ncv * (ncv + 8);
990  double *workl = new double[lworkl];
991  // Communication information
992  int info = 0;
993 
994  TFltV Ax(n);
995  // Communication loop. We keep applying A * x until ARPACK tells us to stop.
996  while (true) {
997  F77_NAME(dsaupd)(&ido, &bmat, &n, &which[0], &nev, &tol, &resid[0], &ncv,
998  &V[0], &ldv, &iparam[0], &ipntr[0], &workd[0], &workl[0],
999  &lworkl, &info);
1000  TFltV result(n);
1001  result.PutAll(0.0);
1002  double *load = &workd[ipntr[0] - 1];
1003  for (int i = 0; i < n; i++) {
1004  result[i] = load[i];
1005  }
1006 
1007  if (ido == 1) {
1008  // Need another matrix-vector product.
1009  A.Multiply(result, Ax);
1010  double *store = &workd[ipntr[1] - 1];
1011  for (int i = 0; i < n; i++) {
1012  store[i] = Ax[i];
1013  }
1014  } else if (ido == 99) {
1015  // We have finished.
1016  break;
1017  } else {
1018  // There was an error.
1019  TExcept::Throw("ARPACK error");
1020  }
1021  }
1022 
1023  // Extract the eigenvectors and eigenvalues
1024 
1025  // compute Ritz vectors
1026  int rvec(true);
1027  // Form of Ritz vectors
1028  char howmny = 'A';
1029  // select doesn't matter with howmny set to A
1030  int *select = new int[ncv];
1031  // Store Ritz values
1032  double *d = new double[nev];
1033  // Shift
1034  double sigmar = 0;
1035 
1036  F77_NAME(dseupd)(&rvec, &howmny, select, &d[0], &V[0], &ldv, &sigmar, &bmat,
1037  &n, &which[0], &nev, &tol, &resid[0], &ncv, &V[0], &ldv,
1038  &iparam[0], &ipntr[0], &workd[0], &workl[0], &lworkl, &info);
1039  if (info != 0) {
1040  TExcept::Throw("ARPACK error");
1041  }
1042 
1043  // Get eigenvalues and eigenvalues in sorted order
1044  TVec< TKeyDat<TFlt, TInt> > d_inds(nev);
1045  for (int i = 0; i < nev; i++) {
1046  d_inds[i] = TKeyDat<TFlt, TInt>(d[i], i);
1047  }
1048  d_inds.Sort();
1049 
1050  evals = TFltV(nev);
1051  evecs.ColV = TVec<TFltV>(nev);
1052  for (int i = 0; i < nev; i++) {
1053  double eval = d_inds[i].Key;
1054  int ind = d_inds[i].Dat;
1055  evals[ind] = eval;
1056  TFltV& col = evecs.ColV[ind];
1057  for (int j = ind * n; j < ind * n + n; j++) {
1058  col.Add(V[j]);
1059  }
1060  }
1061  evecs.RowN = n;
1062  evecs.ColN = nev;
1063 
1064  // Clean up
1065  delete[] resid;
1066  delete[] V;
1067  delete[] iparam;
1068  delete[] ipntr;
1069  delete[] workd;
1070  delete[] workl;
1071  delete[] select;
1072  delete[] d;
1073 }
Definition: ds.h:346
void F77_NAME() dsaupd(int *ido, char *bmat, int *n, char *which, int *nev, double *tol, double *resid, int *ncv, double *V, int *ldv, int *iparam, int *ipntr, double *workd, double *workl, int *lworkl, int *info)
void AdjustLabels(int kcurr, int klast, const TIntV &U)
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
static bool IsMotifM12(PNGraph graph, int center, int v, int w)
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
void FlushCliques(const TIntV &U)
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:548
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:280
static MotifType ParseMotifType(const TStr &motif)
static bool IsMotifM10(PNGraph graph, int center, int v, int w)
static bool IsMotifM2(PNGraph graph, int u, int v, int w)
static bool IsMotifM7(PNGraph graph, int u, int v, int w)
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:552
static bool IsMotifM4(PNGraph graph, int u, int v, int w)
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:596
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:243
TIter BegI() const
Definition: hash.h:213
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:381
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:594
TIntV cluster
Definition: motifcluster.h:40
static double Sqrt(const double &x)
Definition: xmath.h:13
MotifType
TIter EndI() const
Definition: hash.h:218
static bool IsMotifM11(PNGraph graph, int center, int v, int w)
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
double eig
Definition: motifcluster.h:42
static void Normalize(TFltV &x)
Definition: linalg.cpp:328
static bool IsMotifM1(PNGraph graph, int u, int v, int w)
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:90
TCnCom component
Definition: motifcluster.h:44
void SubgraphDegreeOrder(int k, const TIntV &U, TIntV &order)
static bool IsBidirEdge(PNGraph graph, int u, int v)
static bool IsMotifM13(PNGraph graph, int center, int v, int w)
static bool IsMotifM3(PNGraph graph, int u, int v, int w)
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:94
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
Definition: cncom.h:88
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:430
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
TIntV NIdV
Definition: cncom.h:90
void UpdateWeights(const TIntV &clique)
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
int GetRows() const
Definition: linalg.h:45
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
#define MIN(a, b)
Definition: bd.h:346
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
static PUNGraph UnweightedGraphRepresentation(const WeightVH &weights)
bool IsNIdIn(const int &NId) const
Definition: cncom.h:110
int GetCols() const
Definition: linalg.h:47
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:278
static void SpectralCut(const WeightVH &weights, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
void SymeigsSmallest(const TSparseColMatrix &A, int nev, TFltV &evals, TFullColMatrix &evecs, double tol, int maxiter)
TStr GetLc() const
Definition: dt.h:502
TVec< THash< TInt, TFlt > > WeightVH
TVec< TIntFltKdV > ColSpVV
Definition: linalg.h:60
static void IncrementWeight(int i, int j, WeightVH &weights)
static void MotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
static void WedgeMotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
void CliqueEnum(int k, const TIntV &U)
static void BifanMotifAdjacency(PNGraph graph, WeightVH &weights)
static bool IsMotifM9(PNGraph graph, int center, int v, int w)
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:556
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:432
static bool IsMotifM6(PNGraph graph, int u, int v, int w)
static void TriangleMotifAdjacency(PNGraph graph, MotifType motif, WeightVH &weights)
void Multiply(const TFltVV &B, int ColId, TFltV &Result) const
Definition: linalg.h:24
TVec< TFltV > ColV
Definition: linalg.h:131
double cond
Definition: motifcluster.h:41
static bool IsUnidirEdge(PNGraph graph, int u, int v)
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:550
static void DegreeOrdering(PNGraph graph, TIntV &order)
TVec< TFlt > TFltV
Definition: ds.h:1596
PGraph GetKCore(const PGraph &Graph, const int &K)
Definition: kcore.h:106
int GetOutDeg() const
Returns out-degree of the current node.
Definition: graph.h:406
Definition: dt.h:412
TFltV sweep_profile
Definition: motifcluster.h:43
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TVec< TVec< TIntV > > graph_
Definition: motifcluster.h:183
static double NFiedlerVector(const TSparseColMatrix &W, TFltV &fvec, double tol=kDefaultTol, int maxiter=kMaxIter)
void F77_NAME() dseupd(int *rvec, char *HowMny, int *select, double *d, double *Z, int *ldz, double *sigma, char *bmat, int *n, char *which, int *nev, double *tol, double *resid, int *ncv, double *V, int *ldv, int *iparam, int *ipntr, double *workd, double *workl, int *lworkl, int *info)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:383
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
static void MapIdsToFirstN(const TIntV &ids, THash< TInt, TInt > &id_map, TIntV &rev_id_map)
int Len() const
Definition: cncom.h:101
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:111
TVec< TInt > TIntV
Definition: ds.h:1594
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
static void Sweep(const TSparseColMatrix &W, const TFltV &fvec, TFltV &conds, TIntV &order)
static bool IsMotifM5(PNGraph graph, int u, int v, int w)
static bool IsMotifM8(PNGraph graph, int center, int v, int w)
#define F77_NAME(name)
Definition: motifcluster.cpp:7
static void SemicliqueMotifAdjacency(PUNGraph graph, WeightVH &weights)
bool IsEdge(const int &SrcNId, const int &DstNId) const
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition: graph.cpp:137
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
void DelSelfEdges(const PGraph &Graph)
Removes all the self-edges from the graph.
Definition: alg.h:419
#define MAX(a, b)
Definition: bd.h:350
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
void Trunc(const TSizeTy &_Vals=-1)
Truncates the vector's length and capacity to _Vals elements.
Definition: ds.h:1033
static void CliqueMotifAdjacency(PUNGraph graph, int clique_size, WeightVH &weights)
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376
int GetOutNId(const int &NodeN) const
Returns ID of NodeN-th out-node (the node the current node points to).
Definition: graph.h:416
static bool IsNoEdge(PNGraph graph, int u, int v)
static void GetMotifCluster(PNGraph graph, MotifType motif, TSweepCut &sweepcut, double tol=kDefaultTol, int maxiter=kMaxIter)
static void EdgeMotifAdjacency(PNGraph graph, WeightVH &weights)