4

Utilizando como base as notas iniciais 0.15 para todos e depois deve adicionar nota de acordo com o explicado no artigo http://cmup.fc.up.pt/cmup/mecs/googlePR.pdf

Se considerarmos as páginas 1, 2 e 3 como sendo:

1: link1
2: link2
3: link3

O arquivo paginas.txt desse exemplo seria:

1 link1 
2 link2
3 link3

Enquanto que o arquivo links.txt seria:

1 2 
2 1
2 3

O seu programa deve então calcular o PageRank de cada uma das páginas contidas no arquivo paginas.txt (tomando como base o arquivo links.txt), e gerar como saída, uma arquivo chamado paginasOrdenadas.txt, onde as páginas estão ordenadas do maior para o menor PageRank. Caso duas páginas possuam o mesmo PageRank, deve vir primeiro no arquivo aquela que tiver o menor id.

Alguem saberia me informar porque esse meu loop está dando os resultados errados? O meu link.txt está assim :

1 3
2 1
3 1
3 2
3 4

O meu paginas.txt está assim:

1 link1
2 link2
3 link3
4 link4

o meu Loop:

void calculoPageRank(struct page *pageRank, int numLinhas){
    int h=1,g=1;
    int j=1,i=1;
    float soma = 0.0, difer= 0.2;

    while (difer>=0.05) {
        while (h<=numLinhas) {
            soma= 0.0;
            i=pageRank[h].numeroDeLinksRecebe;
            while (i!=0) {
                g = pageRank[h].quaisLinks[i];
                soma += 0.85 * (pageRank[g].rank/pageRank[g].numeroDeLinksEnviados);
                i--;
                difer = (soma+0.15) - pageRank[h].rank;
            }

            pageRank[h].rank=soma+0.15;
            printf("%f ",difer);
            h++;
        }
        j++;
    }
}

E o algoritmo completo:

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

typedef struct page{
    char pagina[20];
    int numeroDeLinksRecebe;
    int numeroDeLinksEnviados;
    int quaisLinks[30];
    float rank;
}page;

int numeroLinhas(){
    char caracter = '\0';
    int numLinhas = 0;
    FILE *arq;
    arq = fopen("paginas.txt", "r");
    while (!feof(arq)) {
        fread(&caracter, 1, 1, arq);
        if (caracter=='\n') {
            numLinhas++;
        }
    }
    fclose(arq);
    return numLinhas;
}

void calculoPageRank(struct page *pageRank, int numLinhas){
    int h=1,g=1;
    int j=1,i=1;
    float soma = 0.0, difer= 0.2;

    while (difer>=0.05) {
        while (h<=numLinhas) {
            soma= 0.0;
            i=pageRank[h].numeroDeLinksRecebe;
            while (i!=0) {
                g = pageRank[h].quaisLinks[i];
                soma += 0.85 * (pageRank[g].rank/pageRank[g].numeroDeLinksEnviados);
                i--;
                difer = (soma+0.15) - pageRank[h].rank;
            }

            pageRank[h].rank=soma+0.15;
            printf("%f ",difer);
            h++;
        }
        j++;
    }
}

void leitura(struct page *pageRank, int numLinhas){
    int i=1,j=1;
    FILE *arq;
    arq = fopen("paginas.txt", "r");
    while (fscanf(arq, "%d %s", &j, pageRank[i].pagina)!=EOF) {
        i++;
    }
    fclose(arq);

    int g = 1;
    for (i=1; i<=numLinhas; i++) {
        pageRank[i].numeroDeLinksRecebe = 0;
        pageRank[i].numeroDeLinksEnviados=0;
        pageRank[i].rank = 0.15;
    }

    int aux;

    FILE *arq1;
    arq1=fopen("links.txt", "r");
    while (fscanf(arq1, "%d %d", &i, &aux)!=EOF) {
        if (i==j) {
            g++;
            pageRank[i].numeroDeLinksRecebe++;
            pageRank[aux].numeroDeLinksEnviados++;
        }
        else{
            j=i;
            g=1;
            pageRank[i].numeroDeLinksRecebe++;
            pageRank[aux].numeroDeLinksEnviados++;
        }
        pageRank[i].quaisLinks[g] = aux;
    }
    fclose(arq1);
}

int main(){
    int numLinhas = numeroLinhas()+1;

    page pageRank[80];
    int i=1;
    leitura(pageRank, numLinhas);
    for (i=1; i<=numLinhas; i++) {
        printf("i=%d recebe=%d envia=%d rank=%f\n", i, pageRank[i].numeroDeLinksRecebe, pageRank[i].numeroDeLinksEnviados,pageRank[i].rank);
    }

    calculoPageRank(pageRank, numLinhas);

    for (i=1; i<=numLinhas; i++) {
        printf("\n %d rank: %f\n", i, pageRank[i].rank);
    }
}

Dentro desse contexto o loop está retornando uma saída que eu não esperava. O retorno correto seria: PR1 = 1.4901 PR2 = 0.7833 PR3 = 1.5766 PR4 = 0.1500 e está entregando R1 = 0.277500 PR2 = 0.267938 PR3 = 0.623184 PR4 = 0.150000.

Alguém sabe porque meu loop está entregando resultados incoerentes?

3
  • Que resultado o seu programa está gerando?
    – Gabe
    4/02/2014 às 17:49
  • PR1 = 0.277500 PR2 = 0.267938 PR3 = 0.623184 PR4 = 0.150000 4/02/2014 às 18:22
  • 1
    Pena que o pessoal que votou negativamente, não voltou para ver como está agora.
    – Maniero
    7/02/2014 às 19:51

2 Respostas 2

2

Eu confesso que não consigo, numa primeira leitura, entender como o PageRank funciona e expressá-lo por meio de código. Mas observando sua tentativa de solução, identifiquei três problemas em potencial que podem estar contribuindo para um resultado incorreto:

  1. Loop infinito em potencial no while externo

    Quando você sai do while interno - o que indica que sua condição não é mais satisfeita - e simplesmente faz j++ e continua o loop externo, a condição do while interno não mudou. Isso significa que, se após a primeira iteração o difer continuar maior que 0.05, ele vai entrar num loop infinito. Para sua sorte, isso não aconteceu, senão em vez de uma saída incorreta você teria um programa travado...

    Sugiro resolver isso antes de passar pro item 2. Se o que você quer é passar por todas as linhas de novo, o que está faltando é voltar o h para zero. A propósito...

  2. Por que h começa com 1, e i para no zero?

    Isso é intencional? Ou você não está sabendo que, em C, os índices começam no zero (i.e. o 1º elemento é array[0], o 2º array[1], o 3º array[2] e assim por diante)? Desculpe se falei uma coisa básica, mas não vi razão olhando o código para assumir que você de fato queria "pular" o primeiro elemento. (e se isso estiver mesmo errado, estou surpreso de você não encontrar um segfault...)

  3. O while externo só leva em consideração o último link visitado.

    Cada vez que você analisa um link você atribui o difer diversas vezes (isso está correto, mas não é realmente necessário - você poderia fazê-lo uma única vez, logo após sair do while mais interno; mas isso é detalhe). Entretanto, quando você vai analisar o próximo link você está descartando os valores dos links anteriores, de modo que ao final somente o último link visitado contribui para o difer - e portanto define se o loop externo vai continuar ou não.

    Imagino que não seja isso que você pretende, ou estou enganado? Talvez o que você queira é continuar o loop caso o difer máximo seja maior que 0.05.

Juntando tudo, sugiro mudar seu código para:

int h=1,g=1; // (Estou mantendo essas linhas iguais,
int j=1,i=1; //  pois elas não importam agora...)
float soma = 0.0, difer= 0.2, max_difer = 0.2; // Variável extra para a diferença máxima

while (max_difer>=0.05) { // Agora compara a diferença máxima
    max_difer = 0.2; // ... resetando ela no início de cada loop
    h = 0; // h também tem de ser resetado, para zero, não para 1

    while (h<numLinhas) { // h vai de 0 a numLinhas-1, então é < e não <=
        soma= 0.0;
        i=pageRank[h].numeroDeLinksRecebe-1; // idem para o i
        while (i>=0) { // i pode ir até zero, então é >= em vez de !=
            g = pageRank[h].quaisLinks[i];
            soma += 0.85 * (pageRank[g].rank/pageRank[g].numeroDeLinksEnviados);
            i--;
        }
        difer = (soma+0.15) - pageRank[h].rank; // Movi pra fora do loop interno

        if ( difer < max_difer ) // Atualiza a diferença máxima
            max_difer = difer;

        pageRank[h].rank=soma+0.15;
        printf("%f ",difer);
        h++;
    }
    j++;
}

Não sei se vai te levar ao resultado esperado, mas espero que seja de alguma ajuda!

6
  • Dei uma atualizada no código font para você conseguir entender um pouco dos loops, vê ai se tiver um tempo :D 1/02/2014 às 3:49
  • 2
    @user2984406 Além de copiar minha resposta pra sua pergunta, você fez mais alguma coisa? Ok, você postou a struct, o código que lê do arquivo, etc, mas isso não vai me ajudar a entender melhor o page rank... (a propósito, por que você lê o arquivo paginas.txt duas vezes?)
    – mgibsonbr
    1/02/2014 às 6:17
  • hmm, então cara, eu não copiei apenas eu fiz umas correções para ver se mudava algo e continuou com a mesma resposta, por isso eu deixei a sua que eu achei melhor estruturada. O PAGERANK é assim, todos as paginas iniciam com 0.15 de nota, assim que alguém tem um link apontando para o site ele ganha a nota do site multiplicado pelo 0.85, o único problema é que quando os sites mudam a nota constantemente essa diferença reflete em todos os sites que ele aponta e assim por diante, quando a diferença começa a ficar muito pequena o loop tem que parar, tem algo errado nesse algoritmo e não enxergo. 1/02/2014 às 13:57
  • @user2984406 blz, o problema não é copiar (esse site é meio que um wiki, então copie à vontade, basta citar a fonte). O caso é que eu identifiquei uns probleminhas no seu código, mas eu não dei uma solução completa - eu não sei como! E quando você repetiu meu código e perguntou "e agora?", eu simplesmente não tinha mais nada a contribuir; minha resposta já está no limite da minha capacidade. A edição foi só para não descaracterizar a pergunta (como pus no comentário da edição), mas se você tiver algum avanço e quiser perguntar aqui por um novo problema [específico], não tem nenhum problema!
    – mgibsonbr
    1/02/2014 às 21:54
  • @user2984406 A propósito, eu e mais 2 usuários já votamos para reabrir sua pergunta (agora que ela está mais objetiva), se mais 2 fizerem isso você voltará a poder receber respostas (aí quem sabe alguém mais experiente que eu possa te ajudar...)
    – mgibsonbr
    1/02/2014 às 21:55
2

Algumas notas sobre estilo:

  • Utilize for quando o número de iterações for conhecido de antemão, e deixe while para quando você deve alcançar uma condição em um número de passos desconhecido.

  • Declare as variáveis no ponto mais próximo do ponto de utilização, e no escopo mais restrito necessário. Alguns professores acreditam que se deve declarar as variáveis em um bloco no começo da função, um hábito que deve ser abandonado. Por exemplo, i não é usada fora do laço de h, então vale a pena declará-lo apenas dentro do laço.

  • Se possível, use C99 ou C11, que te permite por exemplo usar a declaração de variáveis dentro do for.

  • Constantes em código perdem o significado rápido. O que significa 0.85? Claro, você rabiscou num papel para chegar a esse valor, mas essa informação não ficou no código. Considere declarar p = 0.15 dentro da função, e substituir os lugares onde se utiliza esse valor.

  • Falando mais um pouco sobre isso: existe uma piada que é imoral escrever uma função destruir_bagdah(): o correto é fazer uma função destruir(cidade) e então passar Bagdá como parâmetro. No seu caso, considere que o PageRank pode funcionar com outros valores de p desejados, então que ele deveria vir de fora.


Muito possivelmente, o problema do seu código é que você está alterando o vetor de ranks enquanto atravessa ele. Você precisa fazer uma cópia da estrutura para poder alterar a nova.

Isto fica evidente se você vir o cálculo de PageRank como uma iteração de multiplicação de matriz. Se A é a matriz que dá os links, onde A[i][j] = 1 se a página i tem um link pra página j, e v é o vetor de ranks, então o PageRank é obtido iterando

v_novo = A * v_prev + v_aleatório

até que v_prev ~ v_novo. Eu não testei o programa a seguir, mas espero que esteja correto. Da próxima vez, considere facilitar mais o trabalho de quem responde, inúmeras vezes só no esforço de criar um exemplo mínimo você já resolve o problema.

// Nao precisa colocar o tipo de pageRank como struct page, vc ja
// fez um typedef
void calculoPageRank(page *pageRank, int numLinhas){    
    // Se nao tem motivo pra usar float, use double, que eh mais preciso
    double p = 0.15;
    double soma = 0.0, difer= 0.2; 

    int contador = 0; // j nao parecia um bom nome pra essa variavel
    while (difer >= 0.05) {
        page copia[numLinhas]; //C99 - se nao funcionar, use copia[80]

        // memcpy copia pedacos de memoria. Necessita do header <string.h>
        memcpy(copia, pageRank, numLinhas * sizeof(page));

        for (int h = 1; h <= numLinhas; h++) {
            soma= 0.0;
            int i = copia[h].numeroDeLinksRecebe;
            for (; i > 0; i--) {
                int g = copia[h].quaisLinks[i];
                soma += (1 - p) * (copia[g].rank / copia[g].numeroDeLinksEnviados);
                difer = (soma + p) - copia[h].rank;
            }

            pageRank[h].rank = soma + p;
            printf("%f ",difer);
        }
        contador++; // Pra que voce esta usando isso?
    }
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .