Map Reduce алгоритм удаления циклов из графика - PullRequest
Новая
       28

Map Reduce алгоритм удаления циклов из графика

4 голосов
/ 21 мая 2011

Этот вопрос имеет отличный ответ для обнаружения циклов в ориентированном графе.К сожалению, сделать ее версию Map Reduce нелегко.

В частности, меня интересует алгоритм Map Reduce для удаления циклов из ориентированного графа.

Я оценил, используя алгоритм поиска в ширину (BFS), но проблема, которую я вижу, состоит в том, что дваразличные края могут быть удалены одновременно, чтобы отрезать цикл.Результатом этого сценария является то, что слишком много ребер может быть удалено.Важно, чтобы циклы были удалены при минимизации количества удаленных ребер.

Предпочтительны решения с доступными доказательствами!

Спасибо.

Ответы [ 2 ]

1 голос
/ 22 мая 2011

Ну, если вы хотите удалить все циклы, то у вас получится дерево.Поэтому независимо от того, какой алгоритм вы используете, вы удалите | E |- (n -1) ребер.(если это было правильно, конечно)

Однако вопрос заключается в том, приведет ли удаление ребер к отключенному графу.Для этого вам нужно будет упорядочить края (скажем, лексикографический порядок).Затем вы должны всегда удалять самое большое ребро в цикле.[Полагаю, доказательство правильности очень прямое: просто используйте алгоритм Крускала и найдите, что они будут одинаковыми!]

Любой алгоритм связующего дерева решит проблему за вас.В зависимости от того, что вы хотите оптимизировать (сложность времени или сообщений или любой другой показатель производительности), вы найдете разные алгоритмы.BFS - лучшее времяНи один алгоритм не может решить эту проблему для сообщения c (logn + m) при c> 0.

Существует алгоритм, который мне нравится использовать для DAG, называется YO-YO.Описание алгоритма можно найти в: http://www.site.uottawa.ca/~flocchin/CSI4509/8-yoyo11_fr.pdf

1 голос
/ 21 мая 2011

Вам нужно итеративное уменьшение карты для реализации этого алгоритма.См. http://www.iterativemapreduce.org/ для структуры сокращения карт, которая сосредотачивается вокруг итеративного сокращения карт.Или http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm для проработанного примера того, как выполнить поиск в ширину по графу с помощью Hadoop, используя итеративное уменьшение карты.

...