SNAP Library 4.1, Developer Reference  2018-07-26 16:30:42
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
ProcessedGraph Class Reference

#include <localmotifcluster.h>

Collaboration diagram for ProcessedGraph:

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 WeightVHgetWeights () 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.

References assignWeights_undir(), and Graph_org.

117  {
118  Graph_org = graph;
120 }
void assignWeights_undir(MotifType mt)

Here is the call graph for this function:

ProcessedGraph::ProcessedGraph ( PNGraph  graph,
MotifType  mt 
)

Definition at line 247 of file localmotifcluster.cpp.

References assignWeights_dir(), countDirTriadMotif(), and Graph_org.

247  {
248  Graph_org = TSnap::ConvertGraph<PUNGraph>(graph);
249  countDirTriadMotif(graph);
250  assignWeights_dir(mt);
251 }
void assignWeights_dir(MotifType mt)
void countDirTriadMotif(PNGraph graph)

Here is the call graph for this function:

Member Function Documentation

void ProcessedGraph::assignWeights_dir ( MotifType  mt)

Definition at line 457 of file localmotifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), TUNGraph::BegNI(), BiDE, Counts, cycle, DE, DE_any, TUNGraph::DelEdge(), TUNGraph::EndNI(), FFLoop, TUNGraph::GetMxNId(), Graph_org, Graph_trans, TVec< TVal, TSizeTy >::Len(), M1, M2, M3, M4, M5, M6, M7, TExcept::Throw(), TotalVol, triad, UniDE, and Weights.

Referenced by ProcessedGraph().

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);
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 }
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:243
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
static void Throw(const TStr &MsgStr)
Definition: ut.h:187
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
TVec< THash< TInt, TFlt > > WeightVH
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
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

Here is the call graph for this function:

Here is the caller graph for this function:

void ProcessedGraph::assignWeights_undir ( MotifType  mt)

Definition at line 195 of file localmotifcluster.cpp.

References THash< TKey, TDat, THashFunc >::BegI(), TVec< TVal, TSizeTy >::BegI(), TUNGraph::BegNI(), countClique(), Counts, THashKeyDat< TKey, TDat >::Dat, TUNGraph::EndNI(), getCliqueSize(), TUNGraph::GetEdges(), TUNGraph::GetMxNId(), Graph_org, Graph_trans, THash< TKey, TDat, THashFunc >::Len(), TVec< TVal, TSizeTy >::Len(), TotalVol, and Weights.

Referenced by ProcessedGraph().

195  {
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.
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 }
void countClique(PUNGraph &G, int KSize, TIntV &PrevNodes, int level)
TDat Dat
Definition: hash.h:13
TVec< THash< TInt, TIntV > > CountVH
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 GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TVec< THash< TInt, TFlt > > WeightVH
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
int getCliqueSize(const MotifType &type)
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TVec< TInt > TIntV
Definition: ds.h:1594
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
int Len() const
Definition: hash.h:228

Here is the call graph for this function:

Here is the caller graph for this function:

void ProcessedGraph::countClique ( PUNGraph G,
int  KSize,
TIntV PrevNodes,
int  level 
)
private

Definition at line 146 of file localmotifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), TUNGraph::BegEI(), TUNGraph::BegNI(), Counts, TUNGraph::EndEI(), TUNGraph::EndNI(), TUNGraph::GetEdges(), TSnap::GetSubGraph(), and higherDeg().

Referenced by assignWeights_undir().

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 }
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:121
void countClique(PUNGraph &G, int KSize, TIntV &PrevNodes, int level)
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
bool higherDeg(PUNGraph &G, TUNGraph::TNodeI &NI1, int nodeID2)
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
Definition: bd.h:196
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

Here is the caller graph for this function:

void ProcessedGraph::countDirTriadMotif ( PNGraph  graph)
private

Definition at line 398 of file localmotifcluster.cpp.

References TVec< TVal, TSizeTy >::Add(), TNGraph::BegEI(), TUNGraph::BegNI(), TNGraph::BegNI(), checkTriadMotif(), Counts, TNGraph::EndEI(), TUNGraph::EndNI(), TNGraph::EndNI(), TUNGraph::GetMxNId(), TSnap::GetSubGraph(), Graph_org, higherDeg(), and TNGraph::IsEdge().

Referenced by ProcessedGraph().

398  {
399  int numBasicDirMtf = 9;
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 }
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:544
TVec< THash< TInt, TIntV > > CountVH
int checkTriadMotif(PNGraph &G, long nodeID, long srcNId, long dstNId)
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:588
int GetMxNId() const
Returns an ID that is larger than any node ID in the graph.
Definition: graph.h:243
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:586
bool higherDeg(PUNGraph &G, TUNGraph::TNodeI &NI1, int nodeID2)
Edge iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:426
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
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
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:546
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:379
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TVec< TInt > TIntV
Definition: ds.h:1594
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

Here is the call graph for this function:

Here is the caller graph for this function:

CountVH ProcessedGraph::getCounts ( ) const
inline

Definition at line 112 of file localmotifcluster.h.

References Counts.

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

Definition at line 110 of file localmotifcluster.h.

References Graph_org.

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

Definition at line 114 of file localmotifcluster.h.

References TotalVol.

Referenced by MAPPR::computeProfile().

114 { return TotalVol; };

Here is the caller graph for this function:

PUNGraph ProcessedGraph::getTransformedGraph ( ) const
inline

Definition at line 111 of file localmotifcluster.h.

References Graph_trans.

Referenced by MAPPR::computeAPPR(), and MAPPR::computeProfile().

111 {return Graph_trans; };

Here is the caller graph for this function:

const WeightVH& ProcessedGraph::getWeights ( ) const
inline

Definition at line 113 of file localmotifcluster.h.

References Weights.

Referenced by MAPPR::computeAPPR(), and MAPPR::computeProfile().

113 { return Weights; };

Here is the caller graph for this function:

void ProcessedGraph::printCounts ( )

Definition at line 531 of file localmotifcluster.cpp.

References TUNGraph::BegNI(), Counts, TUNGraph::EndNI(), Graph_org, and TVec< TVal, TSizeTy >::Len().

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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237

Here is the call graph for this function:

void ProcessedGraph::printWeights ( )

Definition at line 547 of file localmotifcluster.cpp.

References TUNGraph::BegNI(), TUNGraph::Dump(), TUNGraph::EndNI(), Graph_org, Graph_trans, TotalVol, and Weights.

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 }
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:68
void Dump(FILE *OutF=stdout) const
Print the graph in a human readable form to an output stream OutF.
Definition: graph.cpp:207
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237

Here is the call graph for this function:

Member Data Documentation

CountVH ProcessedGraph::Counts
private
PUNGraph ProcessedGraph::Graph_trans
private
float ProcessedGraph::TotalVol
private
WeightVH ProcessedGraph::Weights
private

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