TSubGraphEnum< TGraphCounter > Class Template Reference

#include <subgraphenum.h>

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.

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

template<class TGraphCounter >

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

Definition at line 171 of file subgraphenum.h.

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

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.

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

template<class TGraphCounter >

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

Definition at line 140 of file subgraphenum.h.

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

---

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:

• snap-adv/subgraphenum.h