Map Zredukuj algorytm usuwania cykli z wykresu - algorytm, wykres, hadoop, mapreduce, graph-algorithm

To pytanie ma świetną odpowiedź na wykrywanie cykli na wyrenderowanym wykresie. Niestety, nie wydaje się łatwo zrobić Mapę zmniejszyć jego wersję.

W szczególności interesuję się algorytmem Map Reduce do usuwania cykli z ukierunkowanego wykresu.

Oceniłem, korzystając z pierwszego zakresu wyszukiwania(BFS), ale widzę problem, że dwie różne krawędzie mogą zostać usunięte jednocześnie, aby odciąć cykl. Wpływ tego scenariusza polega na tym, że można usunąć zbyt wiele krawędzi. Ważne jest, aby cykle były usuwane przy zminimalizowaniu liczby usuniętych krawędzi.

Rozwiązania z dostępnymi dowodami są preferowane!

Dzięki.

Odpowiedzi:

Aby wdrożyć ten algorytm, potrzebujesz iteracyjnej mapy. Widzieć http://www.iterativemapreduce.org/ w przypadku mapy zmniejszają się ramy, które koncentrują się wokół iteracyjnej mapy. Lub http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm dla sprawdzonego przykładu tego, jak wykonać szerokie pierwsze wyszukiwanie za pomocą wykresu z Hadoop przy użyciu iteracyjnej redukcji mapy.

Cóż, jeśli chcesz usunąć wszystkie cykle, skończysz z drzewem. Więc bez względu na to, jakiego algorytmu używasz, usuniesz | E | - (n -1) krawędzi. (jeśli to prawda, oczywiście)

Pozostaje jednak pytanie, czy skreśleniekrawędzie doprowadzą do odłączenia wykresu. W tym celu musisz uporządkować krawędzie (powiedzmy, leksykograficzny), powinieneś zawsze usunąć największą krawędź w cyklu. (Domyślam się, że poprawność jest bardzo bezpośrednia: po prostu użyj algorytmu Kruskala i stwierdzą, że będą takie same!]

Każdy algorytm drzewa opinającego rozwiąże problemproblem dla Ciebie. W zależności od tego, co chcesz zoptymalizować (złożoność czasu lub bałaganu lub jakąkolwiek inną metrykę wyników), znajdziesz różne algorytmy. BFS jest najlepszy na czas. Żaden algorytm nie może rozwiązać problemu za mniej niż c (logn + m) wiadomość dla c> 0.

Istnieje algorytm, który lubię używać dla DAG nazywa się YO-YO. Opis algorytmu można znaleźć w: http://www.site.uottawa.ca/~flocchin/CSI4509/8-yoyo11_fr.pdf