SNAP Library 3.0, User Reference  2016-07-20 17:56:49
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
ChibaNishizekiWeighter Class Reference

#include <motifcluster.h>

Public Member Functions

 ChibaNishizekiWeighter (PUNGraph graph)
 
void Run (int k)
 
WeightVHweights ()
 

Private Member Functions

void SubgraphDegreeOrder (int k, const TIntV &U, TIntV &order)
 
void UpdateWeights (const TIntV &clique)
 
void FlushCliques (const TIntV &U)
 
void CliqueEnum (int k, const TIntV &U)
 
void AdjustLabels (int kcurr, int klast, const TIntV &U)
 
void Initialize (int k)
 

Private Attributes

TVec< TVec< TIntV > > graph_
 
TIntV labels_
 
TIntV C_
 
int k_
 
PUNGraph orig_graph_
 
WeightVH weights_
 

Detailed Description

Definition at line 155 of file motifcluster.h.

Constructor & Destructor Documentation

ChibaNishizekiWeighter::ChibaNishizekiWeighter ( PUNGraph  graph)
inline

Definition at line 157 of file motifcluster.h.

157 : orig_graph_(graph) {}

Member Function Documentation

void ChibaNishizekiWeighter::AdjustLabels ( int  kcurr,
int  klast,
const TIntV U 
)
private

Definition at line 644 of file motifcluster.cpp.

644  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec< TVec< TIntV > > graph_
Definition: motifcluster.h:183
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void ChibaNishizekiWeighter::CliqueEnum ( int  k,
const TIntV U 
)
private

Definition at line 662 of file motifcluster.cpp.

662  {
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 }
void AdjustLabels(int kcurr, int klast, const TIntV &U)
void FlushCliques(const TIntV &U)
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
void SubgraphDegreeOrder(int k, const TIntV &U, TIntV &order)
void CliqueEnum(int k, const TIntV &U)
TVec< TVec< TIntV > > graph_
Definition: motifcluster.h:183
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
void DelLast()
Removes the last element of the vector.
Definition: ds.h:635
void ChibaNishizekiWeighter::FlushCliques ( const TIntV U)
private

Definition at line 624 of file motifcluster.cpp.

624  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
void UpdateWeights(const TIntV &clique)
TVec< TVec< TIntV > > graph_
Definition: motifcluster.h:183
void ChibaNishizekiWeighter::Initialize ( int  k)
private

Definition at line 549 of file motifcluster.cpp.

549  {
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 }
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:215
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:168
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:86
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
TVec< THash< TInt, TInt > > WeightVH
Definition: motifcluster.h:8
PGraph GetKCore(const PGraph &Graph, const int &K)
Definition: kcore.h:106
TVec< TVec< TIntV > > graph_
Definition: motifcluster.h:183
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:107
TVec< TInt > TIntV
Definition: ds.h:1529
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:207
void DelSelfEdges(const PGraph &Graph)
Removes all the self-edges from the graph.
Definition: alg.h:419
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
void ChibaNishizekiWeighter::Run ( int  k)

Definition at line 584 of file motifcluster.cpp.

584  {
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 }
void CliqueEnum(int k, const TIntV &U)
TVec< TVec< TIntV > > graph_
Definition: motifcluster.h:183
void ChibaNishizekiWeighter::SubgraphDegreeOrder ( int  k,
const TIntV U,
TIntV order 
)
private

Definition at line 593 of file motifcluster.cpp.

594  {
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 }
Definition: ds.h:345
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec< TVec< TIntV > > graph_
Definition: motifcluster.h:183
TVec< TInt > TIntV
Definition: ds.h:1529
void Trunc(const TSizeTy &_Vals=-1)
Truncates the vector's length and capacity to _Vals elements.
Definition: ds.h:982
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
void ChibaNishizekiWeighter::UpdateWeights ( const TIntV clique)
private

Definition at line 616 of file motifcluster.cpp.

616  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
static void IncrementWeight(int i, int j, WeightVH &weights)
WeightVH& ChibaNishizekiWeighter::weights ( )
inline

Definition at line 163 of file motifcluster.h.

163 { return weights_; }

Member Data Documentation

TIntV ChibaNishizekiWeighter::C_
private

Definition at line 185 of file motifcluster.h.

TVec< TVec<TIntV> > ChibaNishizekiWeighter::graph_
private

Definition at line 183 of file motifcluster.h.

int ChibaNishizekiWeighter::k_
private

Definition at line 186 of file motifcluster.h.

TIntV ChibaNishizekiWeighter::labels_
private

Definition at line 184 of file motifcluster.h.

PUNGraph ChibaNishizekiWeighter::orig_graph_
private

Definition at line 187 of file motifcluster.h.

WeightVH ChibaNishizekiWeighter::weights_
private

Definition at line 188 of file motifcluster.h.


The documentation for this class was generated from the following files: