SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
graphcounter.cpp
Go to the documentation of this file.
00001 #include "stdafx.h"
00002 #include "graphcounter.h"
00003 
00004 //Number of directed connected 5-node subgraphs = 9364
00005 
00007 // Directed 3 graph implementation
00008 int TD3Graph::m_numOfGraphs = 13;
00009 int TD3Graph::m_graphIds[] = {6,12,14,36,38,46,78,102,140,164,166,174,238};
00010 
00011 int TD3Graph::getId(const PNGraph &G, const TIntV &sg) {
00012         int id=0;
00013         //Node 0
00014         if(TGraphEnumUtils::IsEdge(G, sg[0], sg[1])) id+=2;
00015         if(TGraphEnumUtils::IsEdge(G, sg[0], sg[2])) id+=4;
00016         //Node 1
00017         if(TGraphEnumUtils::IsEdge(G, sg[1], sg[0])) id+=8;
00018         if(TGraphEnumUtils::IsEdge(G, sg[1], sg[2])) id+=32;
00019         //Node 2
00020         if(TGraphEnumUtils::IsEdge(G, sg[2], sg[0])) id+=64;
00021         if(TGraphEnumUtils::IsEdge(G, sg[2], sg[1])) id+=128;
00022         //
00023         return id;
00024 }
00026 // Directed 4 graph implementation
00027 int TD4Graph::m_numOfGraphs = 199;
00028 int TD4Graph::m_graphIds[] = {14, 28, 30, 74, 76, 78, 90, 92, 94, 204, 206, 222, 280, 282, 286, 
00029                                                                 328, 330, 332, 334, 344, 346, 348, 350, 390, 392, 394, 396, 398, 
00030                                                                 404, 406, 408, 410, 412, 414, 454, 456, 458, 460, 462, 468, 470, 
00031                                                                 472, 474, 476, 478, 856, 858, 862, 904, 906, 908, 910, 922, 924, 
00032                                                                 926, 972, 974, 990, 2184, 2186, 2190, 2202, 2204, 2206, 2252, 2254, 
00033                                                                 2270, 2458, 2462, 2506, 2510, 2524, 2526, 3038, 4370, 4374, 4382, 
00034                                                                 4418, 4420, 4422, 4424, 4426, 4428, 4430, 4434, 4436, 4438, 4440, 
00035                                                                 4442, 4444, 4446, 4546, 4548, 4550, 4556, 4558, 4562, 4564, 4566, 
00036                                                                 4572, 4574, 4678, 4682, 4686, 4692, 4694, 4698, 4700, 4702, 4740, 
00037                                                                 4742, 4748, 4750, 4758, 4764, 4766, 4812, 4814, 4830, 4946, 4950, 
00038                                                                 4952, 4954, 4958, 4994, 4998, 5002, 5004, 5006, 5010, 5012, 5014, 
00039                                                                 5016, 5018, 5020, 5022, 5058, 5062, 5064, 5066, 5068, 5070, 5074, 
00040                                                                 5076, 5078, 5080, 5082, 5084, 5086, 6342, 6348, 6350, 6356, 6358, 
00041                                                                 6364, 6366, 6550, 6552, 6554, 6558, 6598, 6602, 6604, 6606, 6614, 
00042                                                                 6616, 6618, 6620, 6622, 6854, 6858, 6862, 6870, 6874, 6876, 6878, 
00043                                                                 7126, 7128, 7130, 7134, 13142, 13146, 13148, 13150, 13260, 13262, 
00044                                                                 13278, 14678, 14686, 14790, 14798, 14810, 14812, 14814, 15258, 
00045                                                                 15262, 15310, 15326, 31710 };
00046 
00047 int TD4Graph::getId(const PNGraph &G, const TIntV &sg) {
00048         int id=0;
00049         //Node 0
00050         if(TGraphEnumUtils::IsEdge(G, sg[0], sg[1])) id+=2;
00051         if(TGraphEnumUtils::IsEdge(G, sg[0], sg[2])) id+=4;
00052         if(TGraphEnumUtils::IsEdge(G, sg[0], sg[3])) id+=8;
00053         //Node 1
00054         if(TGraphEnumUtils::IsEdge(G, sg[1], sg[0])) id+=16;
00055         if(TGraphEnumUtils::IsEdge(G, sg[1], sg[2])) id+=64;
00056         if(TGraphEnumUtils::IsEdge(G, sg[1], sg[3])) id+=128;
00057         //Node 2
00058         if(TGraphEnumUtils::IsEdge(G, sg[2], sg[0])) id+=256;
00059         if(TGraphEnumUtils::IsEdge(G, sg[2], sg[1])) id+=512;
00060         if(TGraphEnumUtils::IsEdge(G, sg[2], sg[3])) id+=2048;
00061         //Node 3
00062         if(TGraphEnumUtils::IsEdge(G, sg[3], sg[0])) id+=4096;
00063         if(TGraphEnumUtils::IsEdge(G, sg[3], sg[1])) id+=8192;
00064         if(TGraphEnumUtils::IsEdge(G, sg[3], sg[2])) id+=16384;
00065         //
00066         return id;
00067 }
00068 
00070 // Directed 3 or 4 graph counter implementation
00071 TD34GraphCounter::TD34GraphCounter(int GraphSz) {
00072         IAssert(GraphSz==3 || GraphSz==4);
00073         //
00074         m_subGraphSize = GraphSz;
00075         //
00076         int numOfGraphs = 0;
00077         if(GraphSz==3) numOfGraphs = TD3Graph::m_numOfGraphs;
00078         else if(GraphSz==4) numOfGraphs = TD4Graph::m_numOfGraphs;
00079         //
00080         for(int i=0; i<numOfGraphs; i++) {
00081                 int graphId = 0;
00082                 if(GraphSz==3) graphId = TD3Graph::m_graphIds[i];
00083                 else if(GraphSz==4) graphId = TD4Graph::m_graphIds[i];
00084                 //
00085                 TVec<PNGraph> isoG;
00086                 TGraphEnumUtils::GetIsoGraphs(graphId, GraphSz, isoG);
00087                 //
00088                 TVec<uint64> graphIds(isoG.Len());
00089                 uint64 minGraphId = TGraphEnumUtils::GetMinAndGraphIds(isoG, graphIds);
00090                 for(int j=0; j<graphIds.Len(); j++)
00091                         m_graphMaps.AddDat((int)graphIds[j], (int)minGraphId);
00092                 //
00093                 m_graphCounters.AddDat((int)minGraphId, 0);
00094         }
00095 }
00096 void TD34GraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
00097         int graphId = 0;
00098         if(m_subGraphSize==3) graphId = TD3Graph::getId(G, sg);
00099         else if(m_subGraphSize==4) graphId = TD4Graph::getId(G, sg);
00100         //
00101         if(!m_graphMaps.IsKey(graphId)) { printf("This graph does not exist: %d\n", graphId); getchar(); return; }
00102         int minGraphId = m_graphMaps.GetDat(graphId);
00103         //
00104         m_graphCounters.GetDat(minGraphId)++;
00105 }
00106 
00107 PNGraph TD34GraphCounter::GetGraph(const int& GraphId) const {
00108   PNGraph G = TNGraph::New();
00109   TGraphEnumUtils::GetGraph(GraphId, m_subGraphSize, G);
00110   return G;
00111 }
00112 
00114 // Directed graph counter implementation
00115 void TDGraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
00116         uint64 graphId = TGraphEnumUtils::GraphId(G, sg);
00117         //
00118         if(m_graphMaps.IsKey(graphId)) {
00119                 TUInt64 minGraphId = m_graphMaps.GetDat(graphId);
00120                 m_graphCounters.GetDat(minGraphId)++;
00121         }else{
00122                 TVec<PNGraph> isoG;
00123                 TGraphEnumUtils::GetIsoGraphs(graphId, sg.Len(), isoG);
00124                 //
00125                 TVec<uint64> graphIds(isoG.Len());
00126                 uint64 minGraphId = TGraphEnumUtils::GetMinAndGraphIds(isoG, graphIds);
00127                 for(int j=0; j<graphIds.Len(); j++)
00128                         m_graphMaps.AddDat(graphIds[j], minGraphId);
00129                 //
00130                 m_graphCounters.AddDat(minGraphId, 1);
00131         }
00132 }
00133 
00135 // Directed ghash graph counter implementation
00136 void TDGHashGraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
00137         PNGraph indG = TNGraph::New();
00138         TGraphEnumUtils::GetIndGraph(G, sg, indG);
00139         //
00140         if(m_graphs.IsKey(indG))
00141                 m_graphs.GetDat(indG)++;
00142         else m_graphs.AddDat(indG, 1);
00143 }
00144 
00146 // TGraphEnumUtils implementation
00147 void TGraphEnumUtils::GetNormalizedMap(const PNGraph &G, THash<TInt,TInt> &map) {
00148         int nId=0;
00149         for(TNGraph::TNodeI it=G->BegNI(); it<G->EndNI(); it++) {
00150                 //printf("%d -> %d\n", it.GetId(), nId);
00151                 map.AddDat(it.GetId(), nId);
00152                 nId++;
00153         }
00154 }
00155 
00156 void TGraphEnumUtils::GetPermutations(TIntV &v, int start, TVec<TIntV> &perms) {
00157         int n = v.Len();
00158         if (start == n-1) perms.Add(v);
00159         else {
00160                 for (int i = start; i < n; i++) {
00161                         int tmp = v[i];
00162                         v[i] = v[start];
00163                         v[start] = tmp;
00164                         GetPermutations(v, start+1, perms);
00165                         //
00166                         v[start] = v[i];
00167                         v[i] = tmp;
00168                 }
00169         }
00170 }
00171 
00172 void TGraphEnumUtils::GetNormalizedGraph(const PNGraph &G, PNGraph &nG) {
00173         //Get bijective map from original node ids to normalized node ids(0,1,2,...)
00174         THash<TInt,TInt> map;
00175         GetNormalizedMap(G, map);
00176         //Add nodes
00177         for(int i=0; i<G->GetNodes(); i++) nG->AddNode(i);
00178         //Add edges
00179         for(TNGraph::TEdgeI eIt=G->BegEI(); eIt<G->EndEI(); eIt++) {
00180                 int srcId = eIt.GetSrcNId();
00181                 int dstId = eIt.GetDstNId();
00182                 //
00183                 int mSrcId = map.GetDat(srcId);
00184                 int mDstId = map.GetDat(dstId);
00185                 //
00186                 nG->AddEdge(mSrcId, mDstId);
00187         }
00188 }
00189 
00190 void TGraphEnumUtils::GetEdges(uint64 graphId, int nodes, TVec<TPair<int,int> > &edges) {
00191         for(int row=0; row<nodes; row++) {
00192                 for(int col=0; col<nodes; col++) {
00193                         int n = row*nodes+col;
00194                         //
00195                         uint64 bits = graphId >> n;
00196                         uint64 mask = 1;
00197                         if((bits & mask)==1) edges.Add(TPair<int,int>(row, col));
00198                 }
00199         }
00200 }
00201 
00202 void TGraphEnumUtils::GetIsoGraphs(uint64 graphId, int nodes, TVec<PNGraph> &isoG) {
00203         TIntV v(nodes); for(int i=0; i<nodes; i++) v[i]=i;
00204         TVec<TIntV> perms; GetPermutations(v, 0, perms);
00205         isoG.Gen(perms.Len());
00206         //
00207         TVec<TPair<int,int> > edges;
00208         GetEdges(graphId, nodes, edges);
00209         //
00210         for(int i=0; i<perms.Len(); i++) {
00211                 isoG[i] = TNGraph::New();
00212                 //Add nodes
00213                 for(int j=0; j<nodes; j++) isoG[i]->AddNode(j);
00214                 //Add edges
00215                 for(int j=0; j<edges.Len(); j++) {
00216                         int srcId = edges[j].Val1;
00217                         int dstId = edges[j].Val2;
00218                         //
00219                         int pSrcId = perms[i][srcId];
00220                         int pDstId = perms[i][dstId];
00221                         //
00222                         isoG[i]->AddEdge(pSrcId, pDstId);
00223                 }
00224         }
00225 }
00226 
00227 void TGraphEnumUtils::GetIsoGraphs(const PNGraph &G, TVec<PNGraph> &isoG) {
00228         int nodes = G->GetNodes();
00229         //
00230         TIntV v(nodes); for(int i=0; i<nodes; i++) v[i]=i;
00231         TVec<TIntV> perms; GetPermutations(v, 0, perms);
00232         isoG.Gen(perms.Len());
00233         //
00234         for(int i=0; i<perms.Len(); i++) {
00235                 isoG[i] = TNGraph::New();
00236                 //Add nodes
00237                 for(int j=0; j<nodes; j++) isoG[i]->AddNode(j);
00238                 //Add edges
00239                 for(TNGraph::TEdgeI eIt=G->BegEI(); eIt<G->EndEI(); eIt++) {
00240                         int srcId = eIt.GetSrcNId();
00241                         int dstId = eIt.GetDstNId();
00242                         //
00243                         int pSrcId = perms[i][srcId];
00244                         int pDstId = perms[i][dstId];
00245                         //
00246                         isoG[i]->AddEdge(pSrcId, pDstId);
00247                 }
00248         }
00249 }
00250 
00251 void TGraphEnumUtils::GetIndGraph(const PNGraph &G, const TIntV &sg, PNGraph &indG) {
00252         //Add nodes
00253         for(int i=0; i<sg.Len(); i++) indG->AddNode(sg[i]);
00254         //Add edges
00255         for(int i=0; i<sg.Len(); i++) {
00256                 int nId = sg[i];
00257                 TNGraph::TNodeI nIt = G->GetNI(nId);
00258                 //
00259                 int deg = nIt.GetOutDeg();
00260                 for(int j=0; j<deg; j++) {
00261                         int dstId = nIt.GetNbrNId(j);
00262                         if(nId == dstId) continue;
00263                         //
00264                         if(indG->IsNode(dstId)) indG->AddEdge(nId, dstId);
00265                 }
00266         }
00267 }
00268 
00269 void TGraphEnumUtils::GetGraph(uint64 graphId, int nodes, PNGraph &G) {
00270   G->Clr();
00271         //Add nodes;
00272         for(int i=0; i<nodes; i++) G->AddNode(i);
00273         //Add edges
00274         for(int row=0; row<nodes; row++) {
00275                 for(int col=0; col<nodes; col++) {
00276                         int n = row*nodes+col;
00277                         //
00278                         uint64 bits = graphId >> n;
00279                         uint64 mask = 1;
00280                         if((bits & mask)==1) G->AddEdge(row, col);
00281                 }
00282         }
00283 }
00284 
00285 uint64 TGraphEnumUtils::GraphId(const PNGraph &G) {
00286         int nodes = G->GetNodes();
00287         uint64 id=0;
00288         for(TNGraph::TEdgeI it=G->BegEI(); it<G->EndEI(); it++) {
00289                 int srcId = it.GetSrcNId();
00290                 int dstId = it.GetDstNId();
00291                 //
00292                 id += TMath::Pow2(srcId*nodes + dstId);
00293         }
00294         //
00295         return id;
00296 }
00297 
00298 uint64 TGraphEnumUtils::GraphId(const PNGraph &G, const TIntV &sg) {
00299         int nodes = sg.Len();
00300         uint64 graphId = 0;
00301         for(int i=0; i<nodes; i++) {
00302                 for(int j=0; j<nodes; j++) {
00303                         if(i==j) continue;
00304                         //
00305                         if(TGraphEnumUtils::IsEdge(G, sg[i], sg[j])) graphId+=TMath::Pow2(i*nodes + j);
00306                 }
00307         }
00308         return graphId;
00309 }
00310 
00311 uint64 TGraphEnumUtils::GetMinAndGraphIds(const TVec<PNGraph> &isoG, TVec<uint64> &graphIds) {
00312         IAssert(isoG.Len() > 0);
00313         //
00314         uint64 minGraphId = GraphId(isoG[0]);
00315         graphIds.Add(minGraphId);
00316         //
00317         for(int i=1; i<isoG.Len(); i++) {
00318                 uint64 curGraphId = GraphId(isoG[i]);
00319                 if(minGraphId > curGraphId) minGraphId=curGraphId;
00320                 //
00321                 graphIds.Add(curGraphId);
00322         }
00323         //
00324         return minGraphId;
00325 }