TGraphEnumUtils Class Reference

#include <graphcounter.h>

Static Public Member Functions
static bool	IsEdge (const PNGraph &G, int SrcNId, int DstNId)
static void	GetEdges (uint64 graphId, int nodes, TVec< TPair< int, int > > &edges)
static void	GetNormalizedGraph (const PNGraph &G, PNGraph &nG)
static void	GetIndGraph (const PNGraph &G, const TIntV &sg, PNGraph &indG)
static void	GetGraph (uint64 graphId, int nodes, PNGraph &G)
static void	GetIsoGraphs (uint64 graphId, int nodes, TVec< PNGraph > &isoG)
static void	GetIsoGraphs (const PNGraph &G, TVec< PNGraph > &isoG)
static uint64	GraphId (const PNGraph &G)
static uint64	GraphId (const PNGraph &G, const TIntV &sg)
static uint64	GetMinAndGraphIds (const TVec< PNGraph > &isoG, TVec< uint64 > &graphIds)

Static Private Member Functions
static void	GetNormalizedMap (const PNGraph &G, THash< TInt, TInt > &map)
static void	GetPermutations (TIntV &v, int start, TVec< TIntV > &perms)

Detailed Description

Definition at line 79 of file graphcounter.h.

Member Function Documentation

void TGraphEnumUtils::GetEdges ( uint64  graphId, int  nodes, TVec< TPair< int, int > > &  edges  )

static

Definition at line 190 of file graphcounter.cpp.

Referenced by GetIsoGraphs().

                                                                                      {
        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));
                }
        }
}

Here is the caller graph for this function:

void TGraphEnumUtils::GetGraph ( uint64  graphId, int  nodes, PNGraph &  G  )

static

Definition at line 269 of file graphcounter.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), and TNGraph::Clr().

Referenced by TD34GraphCounter::GetGraph().

                                                                    {
  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);
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetIndGraph ( const PNGraph &  G, const TIntV &  sg, PNGraph &  indG  )

static

Definition at line 251 of file graphcounter.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::TNodeI::GetNbrNId(), TNGraph::GetNI(), TNGraph::TNodeI::GetOutDeg(), TNGraph::IsNode(), and TVec< TVal, TSizeTy >::Len().

Referenced by TDGHashGraphCounter::operator()().

                                                                                  {
        //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);
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetIsoGraphs ( uint64  graphId, int  nodes, TVec< PNGraph > &  isoG  )

static

Definition at line 202 of file graphcounter.cpp.

References TVec< TVal, TSizeTy >::Gen(), GetEdges(), GetPermutations(), TVec< TVal, TSizeTy >::Len(), and TNGraph::New().

Referenced by TDGraphCounter::operator()(), and TD34GraphCounter::TD34GraphCounter().

                                                                                 {
        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);
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetIsoGraphs ( const PNGraph &  G, TVec< PNGraph > &  isoG  )

static

Definition at line 227 of file graphcounter.cpp.

References TNGraph::BegEI(), TNGraph::EndEI(), TVec< TVal, TSizeTy >::Gen(), TNGraph::GetNodes(), GetPermutations(), TVec< TVal, TSizeTy >::Len(), and TNGraph::New().

                                                                        {
        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);
                }
        }
}

Here is the call graph for this function:

uint64 TGraphEnumUtils::GetMinAndGraphIds ( const TVec< PNGraph > &  isoG, TVec< uint64 > &  graphIds  )

static

Definition at line 311 of file graphcounter.cpp.

References TVec< TVal, TSizeTy >::Add(), GraphId(), IAssert, and TVec< TVal, TSizeTy >::Len().

Referenced by TDGraphCounter::operator()(), and TD34GraphCounter::TD34GraphCounter().

                                                                                           {
        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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetNormalizedGraph ( const PNGraph &  G, PNGraph &  nG  )

static

Definition at line 172 of file graphcounter.cpp.

References TNGraph::AddEdge(), TNGraph::AddNode(), TNGraph::BegEI(), TNGraph::EndEI(), THash< TKey, TDat, THashFunc >::GetDat(), TNGraph::GetNodes(), and GetNormalizedMap().

                                                                      {
        //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);
        }
}

Here is the call graph for this function:

void TGraphEnumUtils::GetNormalizedMap ( const PNGraph &  G, THash< TInt, TInt > &  map  )

staticprivate

Definition at line 147 of file graphcounter.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TNGraph::BegNI(), and TNGraph::EndNI().

Referenced by GetNormalizedGraph().

                                                                              {
        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++;
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TGraphEnumUtils::GetPermutations ( TIntV &  v, int  start, TVec< TIntV > &  perms  )

staticprivate

Definition at line 156 of file graphcounter.cpp.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Len().

Referenced by GetIsoGraphs().

                                                                             {
        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;
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

uint64 TGraphEnumUtils::GraphId ( const PNGraph &  G )

static

Definition at line 285 of file graphcounter.cpp.

References TNGraph::BegEI(), TNGraph::EndEI(), TNGraph::GetNodes(), and TMath::Pow2().

Referenced by GetMinAndGraphIds(), and TDGraphCounter::operator()().

                                                {
        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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

uint64 TGraphEnumUtils::GraphId ( const PNGraph &  G, const TIntV &  sg  )

static

Definition at line 298 of file graphcounter.cpp.

References IsEdge(), TVec< TVal, TSizeTy >::Len(), and TMath::Pow2().

                                                                 {
        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;
}

Here is the call graph for this function:

static bool TGraphEnumUtils::IsEdge ( const PNGraph &  G, int  SrcNId, int  DstNId  )

inlinestatic

Definition at line 84 of file graphcounter.h.

References TNGraph::IsEdge().

Referenced by TD3Graph::getId(), TD4Graph::getId(), and GraphId().

                                                                      {
    // JURE return G->GetNodeC(SrcNId).IsOutNId(DstNId);
    return G->IsEdge(SrcNId, DstNId, true);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

---

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

• snap-adv/graphcounter.h
• snap-adv/graphcounter.cpp