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
Classes | Public Member Functions | Private Member Functions | Private Attributes
TSubGraphEnum< TGraphCounter > Class Template Reference

#include <subgraphenum.h>

Collaboration diagram for TSubGraphEnum< TGraphCounter >:
Collaboration graph
[legend]

List of all members.

Classes

class  TSSet
class  TSVec

Public Member Functions

 TSubGraphEnum ()
void GetSubGraphs (PNGraph &Graph, int SubGraphSz, TGraphCounter &Counter)
void GetSubGraphs (PNGraph &Graph, int NId, int SubGraphSz, TGraphCounter &Counter)

Private Member Functions

void GetSubGraphs_recursive (TSVec &sg, const TSSet &sgNbrs, TSSet &ext, int vId)
void GetSubGraphs_recursive (TSVec &sg, const TSSet &sgNbrs, TSSet &ext)

Private Attributes

PNGraph m_graph
int m_nodes
int m_subGraphSz
TGraphCounter * m_functor

Detailed Description

template<class TGraphCounter>
class TSubGraphEnum< TGraphCounter >

Definition at line 15 of file subgraphenum.h.

Constructor & Destructor Documentation

template<class TGraphCounter >
TSubGraphEnum< TGraphCounter >::TSubGraphEnum ( ) [inline]

Definition at line 69 of file subgraphenum.h.

{ }

Member Function Documentation

template<class TGraphCounter >
void TSubGraphEnum< TGraphCounter >::GetSubGraphs ( PNGraph &  Graph,
int  SubGraphSz,
TGraphCounter &  Counter 
)

Definition at line 112 of file subgraphenum.h.

References TSubGraphEnum< TGraphCounter >::TSSet::Add(), TNGraph::GetNodes(), and TSubGraphEnum< TGraphCounter >::TSVec::Push().

                                                                                                      {
        m_graph = Graph;
        m_nodes = m_graph->GetNodes();
        m_subGraphSz = SubGraphSz;
        m_functor = &Functor;
        //
        TExeTm extime;
        for(TNGraph::TNodeI it=m_graph->BegNI(); it<m_graph->EndNI(); it++) {
                int vId = it.GetId();
                int vDeg = it.GetDeg();
                //Subgraph
                TSVec sg(SubGraphSz);
                sg.Push(vId);
                //Subgraph extension
                TSSet ext(m_nodes);
                for(int i=0; i<vDeg; i++) {
                        int nbrId = it.GetNbrNId(i);
                        if(nbrId > vId) 
                                ext.Add(nbrId);
                }
                //Subgraph neighbours
                TSSet sgNbrs = ext;
                GetSubGraphs_recursive(sg, sgNbrs, ext, vId);
        }
        //printf("secs: %llf\n", extime.GetSecs());
}

Here is the call graph for this function:

template<class TGraphCounter >
void TSubGraphEnum< TGraphCounter >::GetSubGraphs ( PNGraph &  Graph,
int  NId,
int  SubGraphSz,
TGraphCounter &  Counter 
)

Definition at line 171 of file subgraphenum.h.

References TSubGraphEnum< TGraphCounter >::TSSet::Add(), TNGraph::TNodeI::GetDeg(), TNGraph::TNodeI::GetNbrNId(), TNGraph::GetNodes(), TExeTm::GetSecs(), and TSubGraphEnum< TGraphCounter >::TSVec::Push().

                                                                                                               {
        m_graph = Graph;
        m_nodes = m_graph->GetNodes();
        m_subGraphSz = SubGraphSz;
        m_functor = &Functor;
        //
        TNGraph::TNodeI it=m_graph->GetNI(NId);
        int vId = NId;
        int vDeg = it.GetDeg();
        //Subgraph
        TSVec sg(SubGraphSz);
        sg.Push(vId);
        //Subgraph extension
        TSSet ext(m_nodes);
        for(int i=0; i<vDeg; i++) {
                int nbrId = it.GetNbrNId(i);
                ext.Add(nbrId);
        }
        //Subgraph neighbours
        TSSet sgNbrs = ext;
        //
        TExeTm extime;
        GetSubGraphs_recursive(sg, sgNbrs, ext);
        printf("secs: %llf\n", extime.GetSecs());
}

Here is the call graph for this function:

template<class TGraphCounter >
void TSubGraphEnum< TGraphCounter >::GetSubGraphs_recursive ( TSVec &  sg,
const TSSet &  sgNbrs,
TSSet &  ext,
int  vId 
) [private]

Definition at line 81 of file subgraphenum.h.

References TSubGraphEnum< TGraphCounter >::TSSet::Add(), TSubGraphEnum< TGraphCounter >::TSSet::Capacity(), TSubGraphEnum< TGraphCounter >::TSVec::Contains(), TNGraph::TNodeI::GetDeg(), TNGraph::TNodeI::GetNbrNId(), TSubGraphEnum< TGraphCounter >::TSVec::getVec(), TSubGraphEnum< TGraphCounter >::TSSet::IsKey(), TSubGraphEnum< TGraphCounter >::TSVec::Pop(), TSubGraphEnum< TGraphCounter >::TSVec::Push(), TSubGraphEnum< TGraphCounter >::TSSet::Remove(), and TSubGraphEnum< TGraphCounter >::TSVec::Size().

                                                                                                             {
        if(sg.Size() == m_subGraphSz) { (*m_functor)(m_graph, sg.getVec()); return; }
        //
        for(int i=0; i<ext.Capacity(); i++) {
                while(ext[i] == false) {
                        i++;
                        if(i == ext.Capacity()) return;
                }
                //
                int wId = i;
                TNGraph::TNodeI wIt = m_graph->GetNI(wId);
                int wDeg = wIt.GetDeg();
                //
                ext.Remove(wId);
                //
                TSSet newExt = ext;
                TSSet newSgNbrs = sgNbrs;
                for(int j=0; j<wDeg; j++) {
                        int nbrId = wIt.GetNbrNId(j);
                        if(nbrId > vId && !sgNbrs.IsKey(nbrId) && !sg.Contains(nbrId)) {
                                newExt.Add(nbrId);
                                newSgNbrs.Add(nbrId);
                        }
                }
                sg.Push(wId);
                GetSubGraphs_recursive(sg, newSgNbrs, newExt, vId);
                sg.Pop();
        }
}

Here is the call graph for this function:

template<class TGraphCounter >
void TSubGraphEnum< TGraphCounter >::GetSubGraphs_recursive ( TSVec &  sg,
const TSSet &  sgNbrs,
TSSet &  ext 
) [private]

Definition at line 140 of file subgraphenum.h.

References TSubGraphEnum< TGraphCounter >::TSSet::Add(), TSubGraphEnum< TGraphCounter >::TSSet::Capacity(), TSubGraphEnum< TGraphCounter >::TSVec::Contains(), TNGraph::TNodeI::GetDeg(), TNGraph::TNodeI::GetNbrNId(), TSubGraphEnum< TGraphCounter >::TSVec::getVec(), TSubGraphEnum< TGraphCounter >::TSSet::IsKey(), TSubGraphEnum< TGraphCounter >::TSVec::Pop(), TSubGraphEnum< TGraphCounter >::TSVec::Push(), TSubGraphEnum< TGraphCounter >::TSSet::Remove(), and TSubGraphEnum< TGraphCounter >::TSVec::Size().

                                                                                                    {
        if(sg.Size() == m_subGraphSz) { (*m_functor)(m_graph, sg.getVec()); return; }
        //
        for(int i=0; i<ext.Capacity(); i++) {
                while(ext[i] == false) {
                        i++;
                        if(i == ext.Capacity()) return;
                }
                //
                int wId = i;
                TNGraph::TNodeI wIt = m_graph->GetNI(wId);
                int wDeg = wIt.GetDeg();
                //
                ext.Remove(wId);
                //
                TSSet newExt = ext;
                TSSet newSgNbrs = sgNbrs;
                for(int j=0; j<wDeg; j++) {
                        int nbrId = wIt.GetNbrNId(j);
                        if(!sgNbrs.IsKey(nbrId) && !sg.Contains(nbrId)) {
                                newExt.Add(nbrId);
                                newSgNbrs.Add(nbrId);
                        }
                }
                sg.Push(wId);
                GetSubGraphs_recursive(sg, newSgNbrs, newExt);
                sg.Pop();
        }
}

Here is the call graph for this function:

Member Data Documentation

template<class TGraphCounter >
TGraphCounter* TSubGraphEnum< TGraphCounter >::m_functor [private]

Definition at line 64 of file subgraphenum.h.

template<class TGraphCounter >
PNGraph TSubGraphEnum< TGraphCounter >::m_graph [private]

Definition at line 61 of file subgraphenum.h.

template<class TGraphCounter >
int TSubGraphEnum< TGraphCounter >::m_nodes [private]

Definition at line 62 of file subgraphenum.h.

template<class TGraphCounter >
int TSubGraphEnum< TGraphCounter >::m_subGraphSz [private]

Definition at line 63 of file subgraphenum.h.

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