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
[[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, 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]]
|