SNAP Library , Developer Reference  2013-01-07 14:03:36
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
TGraphEnumUtils Class Reference

#include <graphcounter.h>

List of all members.

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

                                                                    {
  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:

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 >::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 >::Gen(), GetEdges(), GetPermutations(), TVec< TVal >::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 >::Gen(), TNGraph::GetNodes(), GetPermutations(), TVec< TVal >::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 >::Add(), GraphId(), IAssert, and TVec< TVal >::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 
) [static, private]

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 
) [static, private]

Definition at line 156 of file graphcounter.cpp.

References TVec< TVal >::Add(), and TVec< TVal >::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 >::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 
) [inline, static]

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: