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
Public Member Functions | Private Member Functions | Private Attributes | List of all members
ProcessedGraph Class Reference

#include <localmotifcluster.h>

Public Member Functions

 ProcessedGraph ()
 
 ProcessedGraph (PUNGraph graph, MotifType mt)
 
 ProcessedGraph (PNGraph graph, MotifType mt)
 
void assignWeights_undir (MotifType mt)
 
void assignWeights_dir (MotifType mt)
 
PUNGraph getOriginalGraph () const
 
PUNGraph getTransformedGraph () const
 
CountVH getCounts () const
 
const WeightVH & getWeights () const
 
float getTotalVolume () const
 
void printCounts ()
 
void printWeights ()
 

Private Member Functions

void countClique (PUNGraph &G, int KSize, TIntV &PrevNodes, int level)
 
void countDirTriadMotif (PNGraph graph)
 

Private Attributes

PUNGraph Graph_org
 
PUNGraph Graph_trans
 
CountVH Counts
 
WeightVH Weights
 
float TotalVol
 

Detailed Description

Definition at line 56 of file localmotifcluster.h.

Constructor & Destructor Documentation

ProcessedGraph::ProcessedGraph ( )
inline

Definition at line 96 of file localmotifcluster.h.

96 {}
ProcessedGraph::ProcessedGraph ( PUNGraph  graph,
MotifType  mt 
)

Definition at line 117 of file localmotifcluster.cpp.

117  {
118  Graph_org = graph;
119  assignWeights_undir(mt);
120 }
ProcessedGraph::assignWeights_undir
void assignWeights_undir(MotifType mt)
Definition: localmotifcluster.cpp:195
ProcessedGraph::ProcessedGraph ( PNGraph  graph,
MotifType  mt 
)

Definition at line 247 of file localmotifcluster.cpp.

247  {
248  Graph_org = TSnap::ConvertGraph<PUNGraph>(graph);
249  countDirTriadMotif(graph);
250  assignWeights_dir(mt);
251 }
ProcessedGraph::assignWeights_dir
void assignWeights_dir(MotifType mt)
Definition: localmotifcluster.cpp:457
ProcessedGraph::countDirTriadMotif
void countDirTriadMotif(PNGraph graph)
Definition: localmotifcluster.cpp:398

Member Function Documentation

void ProcessedGraph::assignWeights_dir ( MotifType  mt)

Definition at line 457 of file localmotifcluster.cpp.

457  {
458  TIntV MtfInclude;
459  switch (mt) {
460  case UniDE : {MtfInclude.Add(0); break;}
461  case BiDE : MtfInclude.Add(1); break;
462  case DE : MtfInclude.Add(0); MtfInclude.Add(1); MtfInclude.Add(1); break;
463  case DE_any : MtfInclude.Add(0); MtfInclude.Add(1); break;
464 
465  case M1 : MtfInclude.Add(2); break;
466  case M2 : MtfInclude.Add(3); break;
467  case M3 : MtfInclude.Add(4); break;
468  case M4 : MtfInclude.Add(5); break;
469  case M5 : MtfInclude.Add(6); break;
470  case M6 : MtfInclude.Add(7); break;
471  case M7 : MtfInclude.Add(8); break;
472  case triad : {
473  MtfInclude.Add(2);
474  MtfInclude.Add(3);
475  MtfInclude.Add(4);
476  MtfInclude.Add(5);
477  MtfInclude.Add(6);
478  MtfInclude.Add(7);
479  MtfInclude.Add(8);
480  break;
481  }
482  case cycle : {
483  MtfInclude.Add(2);
484  MtfInclude.Add(3);
485  MtfInclude.Add(4);
486  MtfInclude.Add(5);
487  MtfInclude.Add(5);
488  break;
489  }
490  case FFLoop : {
491  MtfInclude.Add(6);
492  MtfInclude.Add(7);
493  MtfInclude.Add(7);
494  MtfInclude.Add(8);
495  MtfInclude.Add(8);
496  break;
497  default:
498  TExcept::Throw("Unknown motif type!");
499  }
500  }
501 
502  Graph_trans = TSnap::ConvertGraph<PUNGraph>(Graph_org);
503  Weights = WeightVH(Graph_org->GetMxNId());
504 
505  TotalVol = 0;
506  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
507  int NodeId = NI.GetId();
508  float deg_w = 0;
509  for (int e = 0; e < NI.GetOutDeg(); e++) {
510  int NbrId = NI.GetOutNId(e);
511  TIntV& CountHere = Counts[NodeId](NbrId);
512  int WeightHere = 0;
513  for (int i = 0; i < MtfInclude.Len(); i ++) {
514  WeightHere += CountHere[MtfInclude[i]];
515  }
516  if (WeightHere) {
517  Weights[NodeId](NbrId) = WeightHere;
518  deg_w += WeightHere;
519  } else {
520  Graph_trans->DelEdge(NodeId, NbrId);
521  }
522  }
523  Weights[NodeId](NodeId) = deg_w;
524  TotalVol += deg_w;
525  }
526 
527  return;
528 }
TUNGraph::GetMxNId
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:243
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TExcept::Throw
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
TUNGraph::DelEdge
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
WeightVH
TVec< THash< TInt, TFlt > > WeightVH
Definition: localmotifcluster.h:6
TUNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TUNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
void ProcessedGraph::assignWeights_undir ( MotifType  mt)

Definition at line 195 of file localmotifcluster.cpp.

195  {
196  Weights = WeightVH(Graph_org->GetMxNId());
197  Graph_trans = TSnap::ConvertGraph<PUNGraph>(Graph_org);
198  int KSize = getCliqueSize(mt);
199  if (KSize == 2) {
200  // Don't need to count, assign weights directly!
201  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
202  int NodeId = NI.GetId();
203  for (int e = 0; e < NI.GetOutDeg(); e++) {
204  Weights[NodeId](NI.GetOutNId(e)) = 1;
205  }
206  Weights[NodeId](NodeId) = NI.GetOutDeg();
207  }
208  TotalVol = 2 * Graph_org->GetEdges();
209  } else {
210  if (Counts.Len() == 0 || Counts.BegI()->Len() == 0 || Counts.BegI()->BegI()->Dat.Len() < KSize - 2) {
211  // If the KSize-clique has not been counted yet, then we count.
212  Counts = CountVH(Graph_org->GetMxNId());
213  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
214  int NodeId = NI.GetId();
215  for (int e = 0; e < NI.GetOutDeg(); e++) {
216  Counts[NodeId](NI.GetOutNId(e)) = TIntV(KSize - 2);
217  }
218  }
219  TIntV PrevNodes(KSize - 2);
220  countClique(Graph_org, KSize, PrevNodes, 0);
221  }
222 
223  // Now we assign weights!
224  TotalVol = 0;
225  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
226  int NodeId = NI.GetId();
227  float deg_w = 0;
228  for (int e = 0; e < NI.GetOutDeg(); e++) {
229  int NbrId = NI.GetOutNId(e);
230  int MtfCntHere = Counts[NodeId](NbrId)[KSize-3];
231  if (MtfCntHere) {
232  Weights[NodeId](NbrId) = MtfCntHere;
233  deg_w += MtfCntHere;
234  } else {
235  Graph_trans->DelEdge(NodeId, NbrId);
236  }
237  }
238  Weights[NodeId](NodeId) = deg_w;
239  TotalVol += deg_w;
240  }
241  }
242 }
ProcessedGraph::countClique
void countClique(PUNGraph &G, int KSize, TIntV &PrevNodes, int level)
Definition: localmotifcluster.cpp:146
THashKeyDat::Dat
TDat Dat
Definition: hash.h:13
CountVH
TVec< THash< TInt, TIntV > > CountVH
Definition: localmotifcluster.h:7
TUNGraph::GetMxNId
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:243
THash::BegI
TIter BegI() const
Definition: hash.h:213
TUNGraph::GetEdges
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
WeightVH
TVec< THash< TInt, TFlt > > WeightVH
Definition: localmotifcluster.h:6
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
getCliqueSize
int getCliqueSize(const MotifType &type)
Definition: localmotifcluster.cpp:88
TUNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TIntV
TVec< TInt > TIntV
Definition: ds.h:1594
TUNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
THash::Len
int Len() const
Definition: hash.h:228
void ProcessedGraph::countClique ( PUNGraph &  G,
int  KSize,
TIntV &  PrevNodes,
int  level 
)
private

Definition at line 146 of file localmotifcluster.cpp.

146  {
147  // Each edge means a (level+2)-clique in the original graph!
148  if (level >= KSize - 1) {
149  throw "exception!!";
150  }
151  if (level >= 1) {
152  for (TUNGraph::TEdgeI EI = G->BegEI(); EI < G->EndEI(); EI ++ ) {
153  int SrcNId = EI.GetSrcNId();
154  int DstNId = EI.GetDstNId();
155  Counts[SrcNId](DstNId)[level-1] ++;
156  Counts[DstNId](SrcNId)[level-1] ++;
157  }
158  }
159  for (TUNGraph::TNodeI NI = G->BegNI(); NI < G->EndNI(); NI ++ ) {
160  int NodeId = NI.GetId();
161  int degHere = NI.GetOutDeg();
162  for (int i = 0; i < level; i ++) {
163  Counts[PrevNodes[i]](NodeId)[level-1] += degHere;
164  Counts[NodeId](PrevNodes[i])[level-1] += degHere;
165  }
166 
167  if (level == KSize - 2) {
168  continue;
169  }
170  // Go to the next level
171  PrevNodes[level] = NodeId;
172  TIntV neighborsID;
173  for (int e = 0; e < NI.GetOutDeg(); e++) {
174  int nbrID = NI.GetOutNId(e);
175  if (higherDeg(G, NodeId, nbrID)) {
176  neighborsID.Add(nbrID);
177  }
178  }
179  PUNGraph subGraph = TSnap::GetSubGraph(G, neighborsID);
180  int numEdges = subGraph->GetEdges();
181  for (int i = 0; i <= level; i ++) {
182  for (int j = i + 1; j <= level; j ++) {
183  Counts[PrevNodes[i]](PrevNodes[j])[level] += numEdges;
184  Counts[PrevNodes[j]](PrevNodes[i])[level] += numEdges;
185  }
186  }
187  countClique(subGraph, KSize, PrevNodes, level + 1);
188  }
189 }
TUNGraph::TEdgeI
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
ProcessedGraph::countClique
void countClique(PUNGraph &G, int KSize, TIntV &PrevNodes, int level)
Definition: localmotifcluster.cpp:146
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
higherDeg
bool higherDeg(PUNGraph &G, TUNGraph::TNodeI &NI1, int nodeID2)
Definition: localmotifcluster.cpp:125
TSnap::GetSubGraph
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
TPt
Definition: bd.h:196
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void ProcessedGraph::countDirTriadMotif ( PNGraph  graph)
private

Definition at line 398 of file localmotifcluster.cpp.

398  {
399  int numBasicDirMtf = 9;
400  Counts = CountVH(Graph_org->GetMxNId());
401  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
402  int NodeId = NI.GetId();
403  for (int e = 0; e < NI.GetOutDeg(); e++) {
404  Counts[NodeId](NI.GetOutNId(e)) = TIntV(numBasicDirMtf);
405  }
406  }
407  for (TNGraph::TNodeI NI = graph->BegNI(); NI < graph->EndNI(); NI ++ ) {
408  long nodeID = NI.GetId();
409  TIntV neighborsID;
410  for (long e = 0; e < NI.GetOutDeg(); e++) {
411  long nbrID = NI.GetOutNId(e);
412  if (higherDeg(graph, nodeID, nbrID)) {
413  neighborsID.Add(nbrID);
414  Counts[nodeID](nbrID)[0] ++;
415  Counts[nbrID](nodeID)[0] ++;
416  }
417  }
418  for (long e = 0; e < NI.GetInDeg(); e++) {
419  long nbrID = NI.GetInNId(e);
420  if (higherDeg(graph, nodeID, nbrID)) {
421  if (graph->IsEdge(nodeID, nbrID)) {
422  Counts[nodeID](nbrID)[0] --;
423  Counts[nbrID](nodeID)[0] --;
424  Counts[nodeID](nbrID)[1] ++;
425  Counts[nbrID](nodeID)[1] ++;
426  } else {
427  neighborsID.Add(nbrID);
428  Counts[nodeID](nbrID)[0] ++;
429  Counts[nbrID](nodeID)[0] ++;
430  }
431  }
432  }
433  PNGraph subGraph = TSnap::GetSubGraph(graph, neighborsID);
434  for (TNGraph::TEdgeI EI = subGraph->BegEI(); EI < subGraph->EndEI(); EI ++ ) {
435  long srcNId = EI.GetSrcNId();
436  long dstNId = EI.GetDstNId();
437  int MotifNumber = 0;
438  if (srcNId > dstNId || !subGraph->IsEdge(dstNId, srcNId)) {
439  MotifNumber = checkTriadMotif(graph, nodeID, srcNId, dstNId);
440  MotifNumber ++;
441  Counts[nodeID](srcNId)[MotifNumber] ++;
442  Counts[srcNId](nodeID)[MotifNumber] ++;
443  Counts[nodeID](dstNId)[MotifNumber] ++;
444  Counts[dstNId](nodeID)[MotifNumber] ++;
445  Counts[srcNId](dstNId)[MotifNumber] ++;
446  Counts[dstNId](srcNId)[MotifNumber] ++;
447  }
448  }
449  }
450  return;
451 }
TNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
CountVH
TVec< THash< TInt, TIntV > > CountVH
Definition: localmotifcluster.h:7
checkTriadMotif
int checkTriadMotif(PNGraph &G, long nodeID, long srcNId, long dstNId)
Definition: localmotifcluster.cpp:273
TNGraph::EndEI
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:588
TUNGraph::GetMxNId
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:243
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TNGraph::BegEI
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:586
higherDeg
bool higherDeg(PUNGraph &G, TUNGraph::TNodeI &NI1, int nodeID2)
Definition: localmotifcluster.cpp:125
TNGraph::TEdgeI
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:426
TNGraph::IsEdge
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
TSnap::GetSubGraph
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
TNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
TNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TUNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TIntV
TVec< TInt > TIntV
Definition: ds.h:1594
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TUNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
CountVH ProcessedGraph::getCounts ( ) const
inline

Definition at line 112 of file localmotifcluster.h.

112 { return Counts; };
PUNGraph ProcessedGraph::getOriginalGraph ( ) const
inline

Definition at line 110 of file localmotifcluster.h.

110 {return Graph_org; };
float ProcessedGraph::getTotalVolume ( ) const
inline

Definition at line 114 of file localmotifcluster.h.

114 { return TotalVol; };
PUNGraph ProcessedGraph::getTransformedGraph ( ) const
inline

Definition at line 111 of file localmotifcluster.h.

111 {return Graph_trans; };
const WeightVH& ProcessedGraph::getWeights ( ) const
inline

Definition at line 113 of file localmotifcluster.h.

113 { return Weights; };
void ProcessedGraph::printCounts ( )

Definition at line 531 of file localmotifcluster.cpp.

531  {
532  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
533  int NodeId = NI.GetId();
534  for (int e = 0; e < NI.GetOutDeg(); e++) {
535  int NbrId = NI.GetOutNId(e);
536  TIntV& CountThisEdge = Counts[NodeId](NbrId);
537  printf("(%d, %d): ", NodeId, NbrId);
538  for (int i = 0; i < CountThisEdge.Len(); i ++) {
539  int output = CountThisEdge[i];
540  printf("%d ", output);
541  }
542  printf("\n");
543  }
544  }
545 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TUNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TUNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
void ProcessedGraph::printWeights ( )

Definition at line 547 of file localmotifcluster.cpp.

547  {
548  for (TUNGraph::TNodeI NI = Graph_org->BegNI(); NI < Graph_org->EndNI(); NI ++ ) {
549  int NodeId = NI.GetId();
550  for (int e = 0; e < NI.GetOutDeg(); e++) {
551  int NbrId = NI.GetOutNId(e);
552  printf("(%d, %d): ", NodeId, NbrId);
553  if (Weights[NodeId].IsKey(NbrId)) {
554  float weight = Weights[NodeId](NbrId);
555  printf("%.2f ", weight);
556  } else {
557  printf("Not a key in Weights");
558  }
559  printf("\n");
560  }
561  float d_w = Weights[NodeId](NodeId);
562  printf("\td_w(%d) = %.2f.\n", NodeId, d_w);
563  }
564  printf("Total volume = %.2f. \n", TotalVol);
565  Graph_trans->Dump();
566 }
TUNGraph::TNodeI
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TUNGraph::Dump
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:207
TUNGraph::EndNI
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TUNGraph::BegNI
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237

Member Data Documentation

CountVH ProcessedGraph::Counts
private

Definition at line 66 of file localmotifcluster.h.

PUNGraph ProcessedGraph::Graph_org
private

Definition at line 58 of file localmotifcluster.h.

PUNGraph ProcessedGraph::Graph_trans
private

Definition at line 62 of file localmotifcluster.h.

float ProcessedGraph::TotalVol
private

Definition at line 78 of file localmotifcluster.h.

WeightVH ProcessedGraph::Weights
private

Definition at line 74 of file localmotifcluster.h.

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