Estruturas de Dados - PageRank (implementação)

E aí [Música] Olá caros alunos sejam bem-vindos a mais uma aula da disciplina de estrutura de dados na hora de hoje esta que a última aula nós vamos falar sobre a implementação em ser mais mais do pagerank na hora de hoje nós vamos falar primeiramente sobre algumas noções preliminares mudanças que a Gente terá que fazer nos códigos das aulas anteriores e depois eu vou falar sobre alguns detalhes de implementação Na verdade eu vou mostrar a implementação do pagerank em ser mais começando com noções preliminares nós vamos utilizar o nosso código implementado como a representação por Matriz de adjacências o código foi feito para ser usado com grafos não direcionados Entretanto a mudança para grafos direcionados é bastante simples Eu até já mencionei sobre essa mudança em aulas anteriores sobre o que você precisa fazer para transformar aquela implementação de graça não direcionado para grafo direcionado é basicamente a gente tem que mudar o algoritmo AD que é o método AD AD que é este método que eu já estou colocando aqui esse método recebia por parâmetro o vértice de origem e o vértice de destino e um peso para ser colocado naquela esta daí o quê que eu Fazia era pegaram inicial do vértice de origem e o índice do verso de destino colocando nas variáveis bro e colo porque eu preciso desse Row e col para acessar a matriz de adjacência anteriormente essas duas linhas de código aqui elas estavam desde comentadas significando que o adicionava esse peso aqui que veio por parâmetro tanto na célula louco Call ou seja dizendo que havia um Maré Está indo de from ver tem que separar Silver phinx assim como eu colocava esse mesmo peso e na matriz de adjacência na posição Call ou dizendo que havia uma aresta indo The Two weeks para from verdi's isso porque era um gráfico não direcionado agora que nós temos um grafo direcionado eu não preciso mais dessa linha aqui e é por isso que ela deve ser comentada e vamos olhar agora o tipo abstrato de dados a única mudança que a gente fez nesse tipo abstrato de dados pode incluir o método get page rank então aqui embaixo temos esse void get page rank slot* o void indica que nós não vamos retornar nada dessa função pelo menos não no retorno da função e daqui o flores* indica que nós estamos em recebendo um parâmetro que é ponteiro para frente o que que é esse parâmetro Na verdade é um vetor de números em ponto flutuante o que que esse método vai fazer ele vai computar o pagerank de todos os vértices dentro do grupo e vai adicionar o pagerank nesse nesse vetor que veio por parâmetro então A ideia é essa quem alok então vetor é quem invoca o método get page rank do método get page rank está única função dele é atualizar os números no vetor E então quem invoca o método get page rank é responsável por tabela o tamanho do vetor esse tamanho do vetor ele tem que ser igual ao número de vértices que tem no meu gráfico tem que se tomar um cuidado com isso então vou ensinar como a gente utiliza esse grupo esse gráfico aqui é o gráfico da aula passada nós utilizamos ele para usar os nossos exemplos como eu implemento esse gráfico usando o nosso Nossa classe primeiro mês eu crie um objeto da classe feito isso eu faço o quê que mas eu queria os vértices por exemplo os vértices A B C e D que são os vértices A B C e D desse meu grupo daí eu adiciona esses vértices no grafo propriamente dito então é Divertics A B C e D e data que eu já tenho os vértices o que que eu preciso fazer agora adicionar as arestas então por exemplo tem uma aresta de até ser e uma aresta de bom então eu coloco aqui um código grafite. At e grave ponto and at AB e assim sucessivamente para todas as arestas nota que eu estou colocando um como peso de todo mundo tanto faz o peso que eu colocaria aqui para esse nosso exemplo porque porque o algoritmo que vai computar o pagerank ele não vai utilizar esses pesos Aqui nós só vamos utilizar o fato de existir uma aresta de um canto a outro então para usar esse método get baby ranks o que que uma pessoa precisa fazer ela precisa primeiramente declarar o vetor com this page rank serão alocadas serão colocados então é isso que eu faço nessa linha que eu acabei de colocar em evidência Flow transferidos para o page rank C = New flicks eu estou dizendo aqui que une o fluxo é um vetor de tamanho quatro porque porque só tem 4 vértices e ganhou Ibope esse Craft. Guedes pagerank passando USB torpor parâmetro quando eu posso receber torpor parâmetro basta esperar esse método aqui acabar e o Speed hack de todos os vértices alocados no gráfico na ordem que eu coloquei aqui no ERP Então vai ser o ar antes do bebê antes do ser e antes do vamos continuar aqui nós já sabemos como fazer para invocar o método get page rank agora que nós precisamos fazer é implementar o método get vamos ver a Primeira ideia aqui nessa nesses lotes esses lá ele tem a seguinte ideia eu sei que em algum momento eu vou precisar redistribuir os pagerank então um vértice A ele vai dar pagerank por assim dizer para todo mundo para quem ele linka para quem ele tem aresta Isso quer dizer o quê que se atém por exemplo é de pagerank ele vai dar x nesse nosso caso sobre três para o primeiro x sobre 3 por segundo e x sobre 3 por terceiro porque três aqui porque por esta minha figura é o grau de saída de ar Então eu preciso do grau de saída de ar em algum momento para para colocar no pé direito Lembrando que o grau de saída não é o grau então não vou usar nessa não pedir em que a gente não usa na meta quebrar o grau propriamente dita só o saindo Então a primeira coisa que eu vou fazer a computar o grau de saída eu vou computar o grau de saída para todos os vértices e colocar os valores dentro desse vetor chamado Auto Posto tigre que é um vetor de inteiros um tamanho suficiente para todos os vértices Então a primeira coisa que eu vou fazer aqui criar um for para poder barrer todos os ventos e daí para cada um desses vértices eu inicializo out pode degree daquele verse.

com 0 Olá primeiramente eu vou inicializar com 10 e depois eu vou na matriz de adjacência então um espaço aqui para o desenhar uma matriz de adjacência ótimo aqui vamos supor que aqui eu tenho o tadinha correspondente ao vértice A e na matriz de adjacência eu contabilizo todos os valores aqui Quantas vezes aparece um valor diferente de nulo AD porque diferentes no at porque não é de significa que não a aresta então eu quero verificar quantas vezes existem arestas e isso é a definição do grau de saída então começa Auto Posto Tigre e com zero e depois para todos os Jotas Oi tá possível Jotas ter um índices de vértices e tambor varrer todos os elementos aqui nesse vetor por exemplo para o ar eu verifico se existe alguém com no é diferente de zero se existe alguém como é diferente de zero então eu sou miau cipante degree ao final desse laço aqui eu vou ter o auto posto degree do i-ésimo vértice e ao final desse outro laço aqui eu vou ter na variável ou se pode dizer que o esmalte pode de Grid todos cobertos bom então dado que nós temos o auto posto de Grace todos os vértices nós já temos informação suficiente para computar o pagerank de todos os raps para computar o pagerank como ele vai ser computado de forma interativa eu preciso saber o pagerank da iteração anterior para saber o pagerank para poder computar o pagerank da iteração atual então o que que eu estou fazendo aqui eu estou criando duas variados uma chamada PR frios que seria o pagerank de todos os versos na iteração anterior por isso que eu coloquei prévios aqui E esse p e vai ser o pagerank de todos os vértices na interação atual que eu vou computador utilizando o PR prios Então são dois vetores que eu vou utilizar e esses dois vetores ele tem tamanho suficiente para computar o Pedro mente de todos os vértices Então como o page rank é o número um ponto flutuante então eu coloquei milfont no bux. to é de pontos flutuantes do tamanho do número de IPs a e agora para inicializar o pedirem muito bem nós vimos na aula passada que ainda que a inicialização é feita da seguinte forma se nós temos n vértices sejam n páginas web nós temos n vértices de cada um deles vai ser inicializado com o valor um sobre ele então todo mundo vai receber um sobre ele eu sei qual é o número de vértices que é o número que está na variável num vértices então a única coisa que eu preciso fazer é colocar em PR prios que a minha variável PR privadas aqui o valor de 1 / um ver se esse quer dizer o que que eu estou inicializando todos os pets com pagerank = 1 sobre n não é esse é o pasto de inicialização é feito isso o que que eu faço o espaços interativos só para sabermos o damping factor que seria o fator de amortecimento foi inicializado com o valor 0. 85 que o valor mais recomendado pela literatura e o que que eu fiz aqui eu criei um primeiro for que que significa esse for é um forte vai esperar pela pela quantidade de vezes que eu quero que intere Então nesse nosso caso aqui eu vou dizer olha eu vou fazer sem interações no máximo 100 interações é um valor que dá E sobra para os gráficos que a gente vai colocar aqui na verdade gráficos muito grandes pela literatura a gente já percebe que 50 interações por isso não ser suficiente para gráficos bem grandes então sem na verdade parece pouco mas acredita em mim o valor até exagerado Então vou colocar sem interações Então vou repetir sem interações e pés é bom não precisa nem se preocupar em memorizar esse num e ter aqui é porque você quer uso esse no Inter dentro do aço então é que eu só coloquei para saber que a gente vai repetir 100 vezes e em cada uma dessas interações o que que eu preciso fazer muito bem no início dessas interações vamos assumir que o que importa é o valor que está em PR vídeos por quê Porque eu vou obter o valor que está em PR príons para gerar o valor na variável no vetor PR são dois vetores então no início do laço aqui o que importa é o valor que está em PR privadas para me ajudar a colocar valores em PR seu pagerank na inteira pagerank na interação atual então para todos os vértices o que é que eu faço para cada um deles eu começo dizendo olha PR e é igual a zero porque eu estou colocando o PR e igual a zero porque eu vou começar ainda a somar todos os pen drives a todos os valores recebidos de quem dica para essa página que tá eu vou inicializar o valor dele com 10 e depois eu somo com o valor que vem daqui com o valor que vem daqui com o valor que vem daqui essa ideia de se for aqui fazer essa soma Então vou verificar larga para todos os vértices que tem no grafo vértices tem o gráfico que podem porventura mandarem valor para essa página aqui eu vou olhar para todos eles e vou verificar se eles possuem arestas para esse gráfico aqui como eu faço essa verificação hora a minha estrutura interna é uma matriz de adjacência o que eu quero na verdade aqui são os predecessores umdeterminado nó então na matriz de adjacência ela tem quando eu olho para as linhas da Matriz de adjacência eu estou olhando para quem Esse verso por exemplo aqui esse JS movies tu está mandando as suas arestas pedir a origem de quais arestas então se eu coloco aqui um valor diferente de nulo é que significa que existe uma aresta DJ para a só que eu quero os predecessores isso aqui não tá me dando os predecessores para ter os predecessores eu olho a coluna por exemplo eu quero os predecessores de bebê então é para essa coluna aqui que eu devo olhar Então os predecessores de bebê vão ser todos que tem um valor na matriz de adjacência diferentes de no AD nessa coluna quinta eu sei por exemplo que o ar uma tem um link para ver aqui não é o j digamos o J mais um aqui seria sardinha também tem um link para ver então eu olho para as colunas e é por isso que nesse Edis eu coloquei eh diz j i porque eu estou olhando para as colunas Eu Estou verificando eu quero computar o page rank do E então tenho que olhar todos os J aí dessa como dessa da Matriz de adjacência ou seja isso o J significa que eu estou olhando essa coluna aqui E então todos os que têm luedy toda vez que tem um valor diferente de noedi eu faço a seguinte soma eu compro eu pego o valor que está no PR prio ou seja o valor do JS mesmo vértice na iteração anterior dividido pelo grau de saída do JS vértice ou seja isso é basicamente aquela fórmula que eu ensinei ela na aula passada efeito todos esses somatórios eu tenho a primeira parte que o algoritmo simplificada dependente rank a parte final seria colocar um menos de / 11 vértices e seria a chance de alguém chegar naquela página ao acaso sem clicar em nenhum link mas de vezes o pagerank de e isso vai atualizar o pagerank de perceba que eu estou atualizando o pagerank de a mesma variável aqui e aqui primeiramente eu fiz a primeira pergunta que ser o algoritmo simplificado e depois eu a contabilização levando em conta que o usuário ele pode se cansar parar de clicar nos links escolher uma página completamente ao acaso o efeito isso eu já tenho o valor do esse pagerank nessa interação então eu uso esse pagerank dessa interação para atualizar o PR prios porque o atualiza o PR prios porque eu já estou me preparando para próxima interação onde esse valor será utilizado para criar na próxima interação o valor do Pr da iteração seguinte então é essa ideia do do algoritmo eu basicamente estou implementando aquela fórmula que eu apresentei para vocês na aula passada pura e simplesmente de uma maneira direta a maneira que eu expliquei é a maneira que eu estou apresentando por fim nós temos que fazer o seguinte retornar os valores para quem chamou a função e desalocar a memória que nós colocamos dinamicamente o que que nós vamos fazer primeiramente hora page rank c a variável que veio por parâmetro é um ponteiro para um ver o demônio então eu vou lá na memória Ah tá eu vou lá na memória e pega os valores que estão no PR que a minha variável local então para cada um desses valores eu vou e coloca na região da memória na região de memória alocada por quem chamou essa função e após essa função a pessoa que invocou a função vai ter os valores na região de memória que ela mesma criou tá então isso daqui serve para a gente ter um retorno dessa função para quem invocou a função e ao final eu desloco a região de memória que eu alô que então eu coloquei um vetor PR previous Então me desloco ele bem aqui utilizando deles eu algo que em vetor PR então disallow aqui e eu a locatio vetor out the Green e o diz a Locke e se vê por aqui só para não ter vazamento de memória após a chamada dessa função é é basicamente isso que eu precisava falar para vocês sobre a implementação desse pagerank desse algoritmo que computa a métrica pagerank para todos os vértices lembrando é claro que todos os métodos que eu apresento aqui eles estão implementados no material de apoio tão no material de apoio está aqui o gráfico gráfico do CPP por dentro desse gráfico do CPP o último método aqui embaixo é esse método que eu acabei de apresentar para vocês é o método que é que tem doente e eu também Criei um arquivo chamado graph pagerank que é o a classe Man que vai fazer a chamada do pagerank justamente para você poder compilar por exemplo demais mais* pontos CPP e após dar o ser mais mais asteriscos.