Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
7.4 kB
1
Indexable
Never
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#include "File_OP.h"
#include "Graph_OP.h"

#define _TEST_ 2000
#define INFINITIVE_VALUE 10e6

Graph LoadtoGraph(char *filename, int mode)
{
    int maxrow = 0;
    int line = 0;
    rowdata *fileline = UnStructureFileRead(filename, &maxrow, &line);
    if (mode == _TEST_)
        PrintRowData(fileline, line);

    Graph gph = createGraph();

    for (int i = 0; i < line; i++)
    {
        char str[10] = "\0";
        strcpy(str, fileline[i].rowdata[0]);
        str[strlen(str) - 1] = '\0';
        char *newstr = (char *)malloc(10 * sizeof(char));
        strcpy(newstr, str);
        addVertex(gph, i, newstr);
        if (mode == _TEST_)
            printf("Here insert vertex = %s\n", newstr);
        strcpy(str, "\0");
    }

    if (mode == _TEST_)
        printf("Here line = %d\n", line);
    for (int i = 0; i < line; i++)
    {
        char str[10] = "\0";
        strcpy(str, fileline[i].rowdata[0]);
        str[strlen(str) - 1] = '\0';
        int u = getID(gph, str);
        if (mode == _TEST_)
            printf("Here rownum = %d\n", fileline[i].rownum);
        for (int j = 1; j < fileline[i].rownum; j++)
        {
            char *out1 = NULL, *out2 = NULL;
            SeperateWord(fileline[i].rowdata[j], &out1, &out2, '-');
            int v = getID(gph, out1);
            int w = atoi(out2);
            if (mode == _TEST_)
                printf("Insert Edge (%s,%s) = (%d,%d) = %d\n", out1, str, v, u, w);
            addEdge(gph, v, u, w);
        }
    }

    //**************************************************************
    for (int i = 0; i < line; i++)
    {
        freePointer(fileline[i].rowdata, fileline[i].rownum);
    }
    return gph;
}

Graph readURL(char *filename1, char *filename2)
{
    int maxrow = 0;
    int maxline = 0;
    rowdata *row = UnStructureFileRead(filename1, &maxrow, &maxline);

    Graph gph = createGraph();
    for (int i = 1; i < maxline; i++)
    {
        char *url = row[i].rowdata[0];
        //printf("%s\n", url);
        char *id = row[i].rowdata[1];
        int t = atoi(id);
        addVertex(gph, t, url);
    }

    int maxrow1 = 0;
    int maxline1 = 0;
    rowdata *row1 = UnStructureFileRead(filename2, &maxrow1, &maxline1);

    for (int i = 1; i < maxline1; i++)
    {
        int u = atoi(row1[i].rowdata[0]);
        for (int j = 1; j < row1[i].rownum; j++)
        {
            int v = atoi(row1[i].rowdata[j]);
            //printf("Add edge (u,v) = (%d,%d) = 1\n", u, v);
            addEdge(gph, u, v, 1);
        }
    }
    return gph;
}

double RankPoint[5000];

void PageRank(Graph g, int m)
{
    JRB tmp;
    double LastRank[5000];
    jrb_traverse(tmp, g.vertices){
        int k = jval_i(tmp->key);
        LastRank[k] = RankPoint[k];
    }
    int output[100];
    for (int i = 0; i < m; i++)
    {
        jrb_traverse(tmp, g.vertices)
        {
            double S = 0;
            int t = jval_i(tmp->key);
            int n = indegree(g, t, output);
            for (int j = 0; j < n; j++)
            {
                int outsub[100];
                int d = outdegree(g, output[j], outsub);
                if (d > 0)
                {
                    S += LastRank[output[j]] / (double)d;
                }
            }
            RankPoint[t] = S;
        }
    }
}

int IsVertex(Graph g, int v)
{
    if (jrb_find_int(g.vertices, v) != NULL)
        return 1;
    return 0;
}

void SearchforTop(int* Rank, int* output){
    int max = 0;
    for (int i = 0; i < 5000; i++)
    {
        
    }
    
}

int main(int argc, char const *argv[])
{
    Graph gph;

    for (int i = 0; i < 5000; i++)
    {
        RankPoint[i] = 1;
    }

    int sel = 0;
    int cont = 1;

    int count_out = 0;
    int count_in = 0;

    int output2[100] = {0};
    JRB tmp2, sub2;

    int id1, id2;

    while (cont)
    {
        printf("================== Here's program menu ===================\n");
        printf("1. Print Webpage, URL\n2. PageRank(1)\n3. PageRank(m)\n4. Pages only out/in-connected\n5. SPT URL\n6. Exit\n");
        printf("Select: ");
        scanf("%d", &sel);
        switch (sel)
        {
        case 1:
            gph = readURL("webpages.txt", "pageConnections.txt");
            JRB tmp1;
            jrb_traverse(tmp1, gph.vertices)
            {
                printf("%s %d\n", jval_s(tmp1->val), jval_i(tmp1->key));
            }
            //=========================================================================================
            int max = 0;
            int min = 1000;
            JRB tmp;
            JRB maxnode, minnode;
            int output[100] = {0};
            jrb_traverse(tmp, gph.vertices)
            {
                int t = indegree(gph, jval_i(tmp->key), output);
                //printf("Here %d: %d\n", jval_i(tmp->key), t);
                if (t > max)
                {
                    max = t;
                    maxnode = tmp;
                }
                if (t < min)
                {
                    min = t;
                    minnode = tmp;
                }
            }
            printf("Page with highest in-connection: %s %d\n", jval_s(maxnode->val), jval_i(maxnode->key));
            printf("Page with lowest in-connection: %s %d\n", jval_s(minnode->val), jval_i(minnode->key));
            break;
        case 2:
            PageRank(gph, 1);
            printf("After 1 Loop, Ranks are: \n");
            JRB tr;
            jrb_traverse(tr, gph.vertices)
            {
                int u = jval_i(tr->key);
                char *web = jval_s(tr->val);
                printf("%s %d %.2f\n", web, u, RankPoint[u]);
            }
            break;
        case 3:
            printf("Insert m = ");
            int loop = 0;
            scanf("%d", &loop);
            PageRank(gph, loop);
            jrb_traverse(tr, gph.vertices)
            {
                int u = jval_i(tr->key);
                char *web = jval_s(tr->val);
                printf("%s %d %.2f\n", web, u, RankPoint[u]);
            }
            printf("Top 3 page rank: \n");
            
            break;
        case 4:
            jrb_traverse(tmp2, gph.vertices)
            {
                if (outdegree(gph, jval_i(tmp2->key), output2) == 0)
                {
                    count_out++;
                }
                if (indegree(gph, jval_i(tmp2->key), output2) == 0)
                {
                    count_in++;
                }
            }
            printf("Number of out-only pages: %d\nNumber of in-only pages: %d\n", count_out, count_in);
            break;
        case 5:
            do
            {
                printf("Insert id1 id2: ");
                scanf("%d %d", &id1, &id2);
            } while (IsVertex(gph, id1) && IsVertex(gph, id2));
            int path[100];
            int length[100];
            double f = shortestPath(gph, id1, id2, path, length);
            if (f != INFINITIVE_VALUE)
                printf("Shortest Path: %.2f\n", f);
            else
                printf("No connection found\n");
            break;
        case 6:
            printf("End of service\nExitting....\n");
            cont = 0;
            break;
        default:
            printf("Please select again from 1 to 6 only\n");
            break;
        }
    }
    dropGraph(gph);
    return 0;
}