adjacencywdigraph.h

google搜索的核心技术

// AdjacencyWDigraph.h: interface for the AdjacencyWDigraph class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_ADJACENCYWDIGRAPH_H__EABCC361_5F82_4860_89BC_61F057214A8C__INCLUDED_)
#define AFX_ADJACENCYWDIGRAPH_H__EABCC361_5F82_4860_89BC_61F057214A8C__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template<class T>
class AdjacencyWDigraph{
	public:
		AdjacencyWDigraph(int Vertices=10,T noEdge=0);
		AdjacencyWDigraph(int Vertices,T noEdge, T ** array,int prNum=10, float prInit=1.0,float xs=0.5);
		~AdjacencyWDigraph();
        AdjacencyWDigraph<T>& Add(int i,int j, T noEdge);
		int OutDegree(int i) const;
		int InDegree(int i) const;
		void Output() const;
		float * calculate() const;
	private:
		T NoEdge;
		int n;
		int prNum;
		float prInit;
		float xs;
		T * * a;
};
template<class T>
AdjacencyWDigraph<T>::AdjacencyWDigraph(int Vertices,T noEdge)
{
	n=Vertices;
	NoEdge=noEdge;
	a = Make2DArray<int>(n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			a[i][j]=NoEdge;
}
template<class T>
AdjacencyWDigraph<T>::AdjacencyWDigraph(int Vertices,T noEdge, T ** array,int prNum, float prInit, float xs)
{
	n=Vertices;
	NoEdge=noEdge;
	a = array;
	this->prNum = prNum;
	this->prInit = prInit;
	this->xs = xs;
}
template<class T>
AdjacencyWDigraph<T>::~AdjacencyWDigraph()
{
	Delete2DArray(a,n);
}
template<class T>
AdjacencyWDigraph<T>&AdjacencyWDigraph<T>::Add(int i,int j, T value)
{

	a[i][j]=value;
	return *this;
}
template<class T>
int AdjacencyWDigraph<T>::OutDegree(int i) const
{
	if(i<0||i>=n) throw 0;
	int sum=0;
	for(int j=0;j<n;j++)
		if(a[i][j]!=NoEdge) sum++;
	return sum;
}
template<class T>
int AdjacencyWDigraph<T>::InDegree(int i) const
{
    if(i<0||i>=n) return 0;
    int sum=0;
	for(int j=0;j<n;j++)
		if(a[j][i]!=NoEdge) sum++;
    return sum;
}
template<class T>
void AdjacencyWDigraph<T>::Output() const
{    
}
template<class T>
float * AdjacencyWDigraph<T>::calculate() const
{
	 int * x = new int[n];//节点出度
	 
     for(int i=0;i<n;i++)
	 {
		x[i] = OutDegree(i);
	 }
	float *b = new float [n];
	float l= xs;
	//float l=0.5;
	for(i=0; i<n; i++) b[i] = prInit;//迭代初值
    for(int s=1;s<=prNum;s++)//迭代10次
	{
	   
		
		for(i=0;i<n;i++)
		{
			float temp = 0.0;
			for(int j = 0; j < n;j++){
				if(a[j][i] != NoEdge){
					temp = temp + b[j]/(float)x[j];
				}
			}
			b[i] = 1 - l + l * temp;
		}
	}
	
	delete []x;
	return b;
}
template<class T>
void Delete2DArray(T ** &b,int n)
{
	for(int i = 0; i < n; i++)
		delete []b[i];
	delete []b;
	b=0;      
}
template<class T>
T ** Make2DArray(int n)
{
	 T ** a;
	 a = new T * [n];
	 for(int i = 0;i < n; i++){
		 a[i] = new T [n];
	 }
	 return a;
}
template<class T>
void BubbleSort(T a[],int n)
{
	for(int i=n;i>1;i--)
		for(int j=0;j<i-1;j++)
			if(a[j]<a[j+1]) Swap(a[j],a[j+1]);				
		
}
template<class T>
inline void Swap(T& a,T& b)
{
	T temp=a;a=b;b=temp;
}

#endif // !defined(AFX_ADJACENCYWDIGRAPH_H__EABCC361_5F82_4860_89BC_61F057214A8C__INCLUDED_)