PageRank之基于C和C#的基本实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define OK 1
#define ERROR -1
#define FALSE 0
#define TRUE 1
#define MAXVER 20  //定义最大顶点数
#define MAXQSIZE 100
//#define OVERFLOW -2

typedef char verType;    //顶点类型
typedef int Status;
typedef int Boolean;

typedef struct
{
    verType verx[MAXVER];
    int arcs[MAXVER][MAXVER];    //邻接矩阵
    int vernum, arcnum;    //定义最大顶点数 和 弧
}MGraph;

Boolean visited[MAXVER];    //顶点开始都没有被访问过
int locate(MGraph G, verType ch);    //查找顶点在数组中的下标
Status CreateDG(MGraph *G,int v);    //创建有向图
void Create_Transfer_matrix(MGraph G, double ***F);    //创建转移矩阵
double** Mat_mul(double **M1, int num);    //矩阵相乘
int GetNum(MGraph G, int h, int l);    //得到每一行非0项的个数
double *Iteration(double *M1, double **M2, double *M, int num);    //迭代法
int main(void)
{
    double **F = NULL;
    MGraph G;
    CreateDG(&G, 0);
    Create_Transfer_matrix(G, &F);
    Mat_mul(F, G.vernum);
    return 0;
}


double *Iteration(double *M1, double **M2, double *M, int num)
{//迭代法
    double *M3, temp = 0;
    int i, j;
    M3 = malloc(num * sizeof(double));
    printf("\n");
    for(i = 0; i < num; i++)
    {
        printf("@ = %0.10lf\n", M[i]);
    }
    for (i = 0; i < num; i++)
    {
        for (j = 0; j < num; j++)
        {
            temp = M1[j] * M2[i][j] + temp;
        }
        M3[i] = temp + M[i];
        temp = 0;
    }
    putchar(10);
    for (i = 0; i < num; i++)
    {
        printf("%.10lf\n", M3[i]);
    }
    putchar(10);

    return M3;
}

double** Mat_mul(double **M1, int num)
{
    int i,j;
    double *M2, *M3, temp = 0, *M;
    M3 = malloc(num *sizeof(double));
    M2 = malloc(num * sizeof(double));
    for (i = 0; i < num; i++)        //初始化概率分布矩阵
    {
        M2[i] = (1.0 / num * 1.0);
    }
    for (i = 0; i < num; i++)
    {
        for (j = 0; j < num; j++) 
        {
            temp = M1[i][j] * M2[j] + temp;
        }
        M3[i] = temp + M2[i] * 0.2;
        temp = 0;
    }
    for (i = 0; i < num; i++)
    {
        printf("%.10lf\n", M3[i]);
    }
    for (j = 0; j < num; j++) 
    {
        M2[j] = M2[j] * 0.2;
    }
    M = Iteration(M3, M1, M2, num);    //调用函数实现转移矩阵和概率向量的相乘
    while (fabs(M[0] - M3[0]) > 0.0000000001)    //设置迭代结束条件
    {
        M3 = M;
        M = Iteration(M3, M1, M2, num);
        
    }    
    for (i = 0; i < num; i++)
    {
        M[i] = M[i] * 0.8 + 0.2 / num;
    }
    for (i = 0; i < num; i++)
        printf(" - %.10lf\n", M3[i] - 0.0000000001);
    return M1;
    
}

void Create_Transfer_matrix(MGraph G, double ***F)
{//创建转移矩阵
    int i, j;
    (*F) = malloc(G.vernum * sizeof(double *));
    for (i = 0; i < G.vernum; i++)
    {
        (*F)[i] = malloc(G.vernum * sizeof(double));
    }
    for (i = 0; i < G.vernum; i++)
    {
        for (j = 0; j < G.vernum; j++)
        {
            if (GetNum(G, G.vernum, i) == 0)
                (*F)[j][i] = 0;
            else
                (*F)[j][i] = 0.8 * (G.arcs[j][i] / (GetNum(G, G.vernum, i) * 1.0));
        }
    }
    putchar(10);
    printf("\n转移矩阵为:\n");
    for (i = 0; i < G.vernum; i++)
    {
        for (j = 0; j < G.vernum; j++)
        {
            printf("%.10lf ", (*F)[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int locate(MGraph G, verType ch)
{
    int i;
    for (i = 0; i < G.vernum && ch != G.verx[i]; i++);
    return i;

}

Status CreateDG(MGraph *G,int v)
{
    int i, j, k;
    verType ch1, ch2;
    printf("请输入有向图的顶点数和弧数,格式如(0 0): ");
    scanf("%d %d", &G->vernum, &G->arcnum);
    fflush(stdin);    //除缓存
    printf("请输入顶点符号:\n");
    for (i = 0; i < G->vernum; i++)
    {
        scanf("%c", &G->verx[i]);
        fflush(stdin);
    }
    for (i = 0; i < G->vernum; i++)
    {
        for (j = 0; j < G->vernum; j++)
        {
            G->arcs[i][j] = 0;    //赋初值
        }
    }
    printf("请输入有连接的点: 格式(A B)\n");
    for (i = 0; i < G->arcnum; i++)
    {
        printf("请输入第%d对值\n", i + 1);
        scanf("%c %c", &ch1, &ch2);    //输入顶点符号
        fflush(stdin);
        k = locate(*G, ch1);   //获得顶点下标
        j = locate(*G, ch2);
        G->arcs[j][k] = 1;  //为邻接矩阵赋值
    }
    return OK;
}

int GetNum(MGraph G, int h, int l)    //得到每一列非0的个数
{
    int i, Num = 0;
    for (i = 0; i < h; i++)
    {
        if (G.arcs[i][l] > 0)
        {
            Num++;
        }
    }
    return Num;
}