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 40:
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.
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.
[[Ficheiro:GraphDCMP.png|commoldura|centro|Detecção de Ciclos por Passagem de Mensagem]]▼
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 existe nenhuma mensagem sendo enviada pelo grafo, terminando a execução do algoritmo.
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.
| |||