Алгоритм связанных компонентов в свинье

Question

Мы рассмотрели простой алгоритм для поиска связанных компонентов в графе, где иногда иногда бывает большой диаметр (наибольшие компоненты могут достигать 1 м).

Мы нашли много очень сложных алгоритмов MR:

• http://codingwiththomas.blogspot.de/2011/04/graph-exploration-with-hadoop-mapreduce.html
• http://blog.piccolboni.info/2010/07/map-reduce-algorithm-for-connected.html
• http://chasebradford.wordpress.com/2010/10/23/mapreduce-implementation-for-union-find/

Что случилось с очень простой алгоритм:

• компонент foreach, сгенерируйте flatten (nodes_bag) как node, node_with_the_smallest_id как comp_id;
• группы узла
• фильтр узлы с более чем одним comp_id и построить «обновление большого comp_id малого comp_id» стол
• обновление всех узлы с большим comp_id к соответствующему новому малому comp_id, и пометить их как грязные

и перейти к следующей итерации с этими грязными узлами ... что нам здесь не хватает?

Answer 1

Разве ваш предложенный алгоритм не квадратичен? Алгоритм связанных компонентов Тарьяна является линейным.

Answer 2

Хорошо. Причина, по которой мы не можем использовать этот очень простой алгоритм, состоит в том, что у него есть ошибка: сборка «update large comp_id to small comp_id» может быть рекурсивной. Например, если есть 3 компоненты от предыдущей итерации:

A->{1,2} 
B->{2,3} 
C->{3,4} 

Группа по и фильтр будет строить нам этот перевод стол:

A->B 
B->C 

И это вызвало бы число итераций, чтобы быть линейным (самый большой диаметр) в некоторых случаях = длинные цепочки, как в этом мини-примере, занимают много времени, чтобы сходиться.