Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Identificação de ciclos em grafos: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição |
Sem resumo de edição |
||
Linha 32:
Portanto, é necessário um algoritmo que divida o problema de detecção de ciclos em subproblemas entre nós de computação, de modo que os nós busquem por cíclos de maneira paralela, garantindo que todos os ciclos serão encontrados. Propõe-se então, um algoritmo para detecção de ciclos de grafo por passagem de mensagens entre os vértices, baseado no modelo Pregel de processamento de grafos da Google. Esse modelo apresenta uma abordagem centrada nos vértices em que os vértices do grafo trabalham juntos para detectar ciclos.
== Algoritmo de Detecção de Ciclos por Passagem de Mensagens ==
O modelo do Pregel consiste basicamente em uma sequência de iterações, em cada uma das quais um vértice recebe mensagens enviadas por outros vértices na iteração anterior e enviar mensagens para outros vértices.
Linha 42:
Por definição, temos que a lista de vértices, que pode ser vista como uma sequência ordenada de vértices, representa um caminho no grafo. Portanto, quando um vértice recebe uma lista em que o primeiro elemento da lista é o próprio vértice, temos que o caminho representado por aquela lista teve início no próprio vértice, isto é, a lista representa um ciclo no grafo.
A seguir é apresentado um exemplo da execução do algoritmo de detecção de ciclos por passagem de mensagens. Pode-se observar que no passo (d), o vértice 2 recebe uma mensagem em que a lista de vértices é iniciada pelo próprio vértice 2, detectando assim um ciclo no grafo (2,3,4). No passo (e), o vértice 2 rejeita uma mensagem contendo a si próprio na segunda posição da lista. Pode-se notar que a lista rejeitada contém o ciclo detectado anteriormente, e é por esse motivo que o vértice 2 aparece no meio da lista rejeitada, pois o ciclo é um sub-caminho do caminho representado pela lista rejeitada no passo (e). Por fim, no passo (f) todos os vértices são desativados e não
[[Ficheiro:GraphDCMP.png|commoldura|centro|Detecção de Ciclos por Passagem de Mensagens]]
No passo (d) do exemplo, todos os três vértices detectam o ciclo (2,3,4). Para assegurar que apenas um dos vértices reportem a detecção, pode-se detectar o ciclo apenas do vértice cujo identificador seja o menor (por algum critério de ordenação) dentre os demais vértices do ciclo, onde no exemplo seria o vértice 2.
==== Pseudo-Código no Modelo Pregel de Programação Paralela ====
Como mencionado anteriormente, o algoritmo proposto é baseado no modelo Pregel da Google. Nesse modelo de programação paralela, os programas de usuário são expressos como sequências de iterações, chamadas de ''supersteps'', nas quais cada vértice recebe mensagens enviadas por outros vértices na iteração anterior, envia mensagens para outros vértices, e modifica seu próprio estado e o estado das arestas de saída. O modelo Pregel é projetado para implementações em clusters de computadores que sejam eficientes, escaláveis e tolerante a falhas, de maneira que detalhes referentes à distribuição são escondidos pela abstração da API.
O usuário desse modelo implementa um método chamado COMPUTE, que será executado por todos os vértices ativos em cada ''superstep''. O vértice se desativa votando para parar (''halt'') e o algoritmo como um todo termina quando todos os vértices estão simultaneamente desativados e não existem mais mensagens sendo enviadas.
| |||