graphcounter.cpp

Go to the documentation of this file.

#include "stdafx.h"
#include "graphcounter.h"

//Number of directed connected 5-node subgraphs = 9364

// Directed 3 graph implementation
int TD3Graph::m_numOfGraphs = 13;
int TD3Graph::m_graphIds[] = {6,12,14,36,38,46,78,102,140,164,166,174,238};

int TD3Graph::getId(const PNGraph &G, const TIntV &sg) {
        int id=0;
        //Node 0
        if(TGraphEnumUtils::IsEdge(G, sg[0], sg[1])) id+=2;
        if(TGraphEnumUtils::IsEdge(G, sg[0], sg[2])) id+=4;
        //Node 1
        if(TGraphEnumUtils::IsEdge(G, sg[1], sg[0])) id+=8;
        if(TGraphEnumUtils::IsEdge(G, sg[1], sg[2])) id+=32;
        //Node 2
        if(TGraphEnumUtils::IsEdge(G, sg[2], sg[0])) id+=64;
        if(TGraphEnumUtils::IsEdge(G, sg[2], sg[1])) id+=128;
        //
        return id;
}
// Directed 4 graph implementation
int TD4Graph::m_numOfGraphs = 199;
int TD4Graph::m_graphIds[] = {14, 28, 30, 74, 76, 78, 90, 92, 94, 204, 206, 222, 280, 282, 286, 
                                                                328, 330, 332, 334, 344, 346, 348, 350, 390, 392, 394, 396, 398, 
                                                                404, 406, 408, 410, 412, 414, 454, 456, 458, 460, 462, 468, 470, 
                                                                472, 474, 476, 478, 856, 858, 862, 904, 906, 908, 910, 922, 924, 
                                                                926, 972, 974, 990, 2184, 2186, 2190, 2202, 2204, 2206, 2252, 2254, 
                                                                2270, 2458, 2462, 2506, 2510, 2524, 2526, 3038, 4370, 4374, 4382, 
                                                                4418, 4420, 4422, 4424, 4426, 4428, 4430, 4434, 4436, 4438, 4440, 
                                                                4442, 4444, 4446, 4546, 4548, 4550, 4556, 4558, 4562, 4564, 4566, 
                                                                4572, 4574, 4678, 4682, 4686, 4692, 4694, 4698, 4700, 4702, 4740, 
                                                                4742, 4748, 4750, 4758, 4764, 4766, 4812, 4814, 4830, 4946, 4950, 
                                                                4952, 4954, 4958, 4994, 4998, 5002, 5004, 5006, 5010, 5012, 5014, 
                                                                5016, 5018, 5020, 5022, 5058, 5062, 5064, 5066, 5068, 5070, 5074, 
                                                                5076, 5078, 5080, 5082, 5084, 5086, 6342, 6348, 6350, 6356, 6358, 
                                                                6364, 6366, 6550, 6552, 6554, 6558, 6598, 6602, 6604, 6606, 6614, 
                                                                6616, 6618, 6620, 6622, 6854, 6858, 6862, 6870, 6874, 6876, 6878, 
                                                                7126, 7128, 7130, 7134, 13142, 13146, 13148, 13150, 13260, 13262, 
                                                                13278, 14678, 14686, 14790, 14798, 14810, 14812, 14814, 15258, 
                                                                15262, 15310, 15326, 31710 };

int TD4Graph::getId(const PNGraph &G, const TIntV &sg) {
        int id=0;
        //Node 0
        if(TGraphEnumUtils::IsEdge(G, sg[0], sg[1])) id+=2;
        if(TGraphEnumUtils::IsEdge(G, sg[0], sg[2])) id+=4;
        if(TGraphEnumUtils::IsEdge(G, sg[0], sg[3])) id+=8;
        //Node 1
        if(TGraphEnumUtils::IsEdge(G, sg[1], sg[0])) id+=16;
        if(TGraphEnumUtils::IsEdge(G, sg[1], sg[2])) id+=64;
        if(TGraphEnumUtils::IsEdge(G, sg[1], sg[3])) id+=128;
        //Node 2
        if(TGraphEnumUtils::IsEdge(G, sg[2], sg[0])) id+=256;
        if(TGraphEnumUtils::IsEdge(G, sg[2], sg[1])) id+=512;
        if(TGraphEnumUtils::IsEdge(G, sg[2], sg[3])) id+=2048;
        //Node 3
        if(TGraphEnumUtils::IsEdge(G, sg[3], sg[0])) id+=4096;
        if(TGraphEnumUtils::IsEdge(G, sg[3], sg[1])) id+=8192;
        if(TGraphEnumUtils::IsEdge(G, sg[3], sg[2])) id+=16384;
        //
        return id;
}

// Directed 3 or 4 graph counter implementation
TD34GraphCounter::TD34GraphCounter(int GraphSz) {
        IAssert(GraphSz==3 || GraphSz==4);
        //
        m_subGraphSize = GraphSz;
        //
        int numOfGraphs = 0;
        if(GraphSz==3) numOfGraphs = TD3Graph::m_numOfGraphs;
        else if(GraphSz==4) numOfGraphs = TD4Graph::m_numOfGraphs;
        //
        for(int i=0; i<numOfGraphs; i++) {
                int graphId = 0;
                if(GraphSz==3) graphId = TD3Graph::m_graphIds[i];
                else if(GraphSz==4) graphId = TD4Graph::m_graphIds[i];
                //
                TVec<PNGraph> isoG;
                TGraphEnumUtils::GetIsoGraphs(graphId, GraphSz, isoG);
                //
                TVec<uint64> graphIds(isoG.Len());
                uint64 minGraphId = TGraphEnumUtils::GetMinAndGraphIds(isoG, graphIds);
                for(int j=0; j<graphIds.Len(); j++)
                        m_graphMaps.AddDat((int)graphIds[j], (int)minGraphId);
                //
                m_graphCounters.AddDat((int)minGraphId, 0);
        }
}
void TD34GraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
        int graphId = 0;
        if(m_subGraphSize==3) graphId = TD3Graph::getId(G, sg);
        else if(m_subGraphSize==4) graphId = TD4Graph::getId(G, sg);
        //
        if(!m_graphMaps.IsKey(graphId)) { printf("This graph does not exist: %d\n", graphId); getchar(); return; }
        int minGraphId = m_graphMaps.GetDat(graphId);
        //
        m_graphCounters.GetDat(minGraphId)++;
}

PNGraph TD34GraphCounter::GetGraph(const int& GraphId) const {
  PNGraph G = TNGraph::New();
  TGraphEnumUtils::GetGraph(GraphId, m_subGraphSize, G);
  return G;
}

// Directed graph counter implementation
void TDGraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
        uint64 graphId = TGraphEnumUtils::GraphId(G, sg);
        //
        if(m_graphMaps.IsKey(graphId)) {
                TUInt64 minGraphId = m_graphMaps.GetDat(graphId);
                m_graphCounters.GetDat(minGraphId)++;
        }else{
                TVec<PNGraph> isoG;
                TGraphEnumUtils::GetIsoGraphs(graphId, sg.Len(), isoG);
                //
                TVec<uint64> graphIds(isoG.Len());
                uint64 minGraphId = TGraphEnumUtils::GetMinAndGraphIds(isoG, graphIds);
                for(int j=0; j<graphIds.Len(); j++)
                        m_graphMaps.AddDat(graphIds[j], minGraphId);
                //
                m_graphCounters.AddDat(minGraphId, 1);
        }
}

// Directed ghash graph counter implementation
void TDGHashGraphCounter::operator()(const PNGraph &G, const TIntV &sg) {
        PNGraph indG = TNGraph::New();
        TGraphEnumUtils::GetIndGraph(G, sg, indG);
        //
        if(m_graphs.IsKey(indG))
                m_graphs.GetDat(indG)++;
        else m_graphs.AddDat(indG, 1);
}

// TGraphEnumUtils implementation
void TGraphEnumUtils::GetNormalizedMap(const PNGraph &G, THash<TInt,TInt> &map) {
        int nId=0;
        for(TNGraph::TNodeI it=G->BegNI(); it<G->EndNI(); it++) {
                //printf("%d -> %d\n", it.GetId(), nId);
                map.AddDat(it.GetId(), nId);
                nId++;
        }
}

void TGraphEnumUtils::GetPermutations(TIntV &v, int start, TVec<TIntV> &perms) {
        int n = v.Len();
        if (start == n-1) perms.Add(v);
        else {
                for (int i = start; i < n; i++) {
                        int tmp = v[i];
                        v[i] = v[start];
                        v[start] = tmp;
                        GetPermutations(v, start+1, perms);
                        //
                        v[start] = v[i];
                        v[i] = tmp;
                }
        }
}

void TGraphEnumUtils::GetNormalizedGraph(const PNGraph &G, PNGraph &nG) {
        //Get bijective map from original node ids to normalized node ids(0,1,2,...)
        THash<TInt,TInt> map;
        GetNormalizedMap(G, map);
        //Add nodes
        for(int i=0; i<G->GetNodes(); i++) nG->AddNode(i);
        //Add edges
        for(TNGraph::TEdgeI eIt=G->BegEI(); eIt<G->EndEI(); eIt++) {
                int srcId = eIt.GetSrcNId();
                int dstId = eIt.GetDstNId();
                //
                int mSrcId = map.GetDat(srcId);
                int mDstId = map.GetDat(dstId);
                //
                nG->AddEdge(mSrcId, mDstId);
        }
}

void TGraphEnumUtils::GetEdges(uint64 graphId, int nodes, TVec<TPair<int,int> > &edges) {
        for(int row=0; row<nodes; row++) {
                for(int col=0; col<nodes; col++) {
                        int n = row*nodes+col;
                        //
                        uint64 bits = graphId >> n;
                        uint64 mask = 1;
                        if((bits & mask)==1) edges.Add(TPair<int,int>(row, col));
                }
        }
}

void TGraphEnumUtils::GetIsoGraphs(uint64 graphId, int nodes, TVec<PNGraph> &isoG) {
        TIntV v(nodes); for(int i=0; i<nodes; i++) v[i]=i;
        TVec<TIntV> perms; GetPermutations(v, 0, perms);
        isoG.Gen(perms.Len());
        //
        TVec<TPair<int,int> > edges;
        GetEdges(graphId, nodes, edges);
        //
        for(int i=0; i<perms.Len(); i++) {
                isoG[i] = TNGraph::New();
                //Add nodes
                for(int j=0; j<nodes; j++) isoG[i]->AddNode(j);
                //Add edges
                for(int j=0; j<edges.Len(); j++) {
                        int srcId = edges[j].Val1;
                        int dstId = edges[j].Val2;
                        //
                        int pSrcId = perms[i][srcId];
                        int pDstId = perms[i][dstId];
                        //
                        isoG[i]->AddEdge(pSrcId, pDstId);
                }
        }
}

void TGraphEnumUtils::GetIsoGraphs(const PNGraph &G, TVec<PNGraph> &isoG) {
        int nodes = G->GetNodes();
        //
        TIntV v(nodes); for(int i=0; i<nodes; i++) v[i]=i;
        TVec<TIntV> perms; GetPermutations(v, 0, perms);
        isoG.Gen(perms.Len());
        //
        for(int i=0; i<perms.Len(); i++) {
                isoG[i] = TNGraph::New();
                //Add nodes
                for(int j=0; j<nodes; j++) isoG[i]->AddNode(j);
                //Add edges
                for(TNGraph::TEdgeI eIt=G->BegEI(); eIt<G->EndEI(); eIt++) {
                        int srcId = eIt.GetSrcNId();
                        int dstId = eIt.GetDstNId();
                        //
                        int pSrcId = perms[i][srcId];
                        int pDstId = perms[i][dstId];
                        //
                        isoG[i]->AddEdge(pSrcId, pDstId);
                }
        }
}

void TGraphEnumUtils::GetIndGraph(const PNGraph &G, const TIntV &sg, PNGraph &indG) {
        //Add nodes
        for(int i=0; i<sg.Len(); i++) indG->AddNode(sg[i]);
        //Add edges
        for(int i=0; i<sg.Len(); i++) {
                int nId = sg[i];
                TNGraph::TNodeI nIt = G->GetNI(nId);
                //
                int deg = nIt.GetOutDeg();
                for(int j=0; j<deg; j++) {
                        int dstId = nIt.GetNbrNId(j);
                        if(nId == dstId) continue;
                        //
                        if(indG->IsNode(dstId)) indG->AddEdge(nId, dstId);
                }
        }
}

void TGraphEnumUtils::GetGraph(uint64 graphId, int nodes, PNGraph &G) {
  G->Clr();
        //Add nodes;
        for(int i=0; i<nodes; i++) G->AddNode(i);
        //Add edges
        for(int row=0; row<nodes; row++) {
                for(int col=0; col<nodes; col++) {
                        int n = row*nodes+col;
                        //
                        uint64 bits = graphId >> n;
                        uint64 mask = 1;
                        if((bits & mask)==1) G->AddEdge(row, col);
                }
        }
}

uint64 TGraphEnumUtils::GraphId(const PNGraph &G) {
        int nodes = G->GetNodes();
        uint64 id=0;
        for(TNGraph::TEdgeI it=G->BegEI(); it<G->EndEI(); it++) {
                int srcId = it.GetSrcNId();
                int dstId = it.GetDstNId();
                //
                id += TMath::Pow2(srcId*nodes + dstId);
        }
        //
        return id;
}

uint64 TGraphEnumUtils::GraphId(const PNGraph &G, const TIntV &sg) {
        int nodes = sg.Len();
        uint64 graphId = 0;
        for(int i=0; i<nodes; i++) {
                for(int j=0; j<nodes; j++) {
                        if(i==j) continue;
                        //
                        if(TGraphEnumUtils::IsEdge(G, sg[i], sg[j])) graphId+=TMath::Pow2(i*nodes + j);
                }
        }
        return graphId;
}

uint64 TGraphEnumUtils::GetMinAndGraphIds(const TVec<PNGraph> &isoG, TVec<uint64> &graphIds) {
        IAssert(isoG.Len() > 0);
        //
        uint64 minGraphId = GraphId(isoG[0]);
        graphIds.Add(minGraphId);
        //
        for(int i=1; i<isoG.Len(); i++) {
                uint64 curGraphId = GraphId(isoG[i]);
                if(minGraphId > curGraphId) minGraphId=curGraphId;
                //
                graphIds.Add(curGraphId);
        }
        //
        return minGraphId;
}