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 22:
11 todo o caminho de ''w'' até ''v'' representa um ciclo
 
A seguir é apresentado um exemplo da execução do algoritmo de busca em profundidade. A aresta (4,2), na cor verde, representa uma aresta de retorno, e o caminho do vértice (2,3,4) representa um ciclo do grafo.
 
[[Ficheiro:GraphDFS.png|commoldura|centro|Detecção de Ciclos por Busca em Profundidade]]
Linha 33:
 
== Descrição ==
 
O modelo do Pregel consiste basicamente em uma sequência de iterações
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.
 
O método inicia com cada vértice enviando para seus vizinhos uma mensagem com uma lista contendo apenas o próprio vértice. Os passos seguintes consistem de pequenas computações realizadas sobre as listas recebidas por mensagens de outros vértices. Se o vértice não recebeu mensagem alguma, então o vértice se desativa. O algoritmo termina quando todos os vértices estão inativos.
 
Para cada lista recebida, se o vértice receber uma lista contendo a si próprio em qualquer posição exceto a primeira, o vértice rejeita a mensagem. Se a lista recebida começar com o próprio vértice, então um ciclo foi detectado. Para as demais listas recebidas, o vértice se adiciona ao final da lista e a encaminha para todos os seus vizinhos.
 
[[Ficheiro:GraphDCMP.png|commoldura|centro|Detecção de Ciclos por Passagem de Mensagem]]