Trzy błędy w Union Find

Ostatnio zajęłam się przerobieniem mojego algorytmu MST tak żeby znajdywał spójne składowe w grafie (Connected Components o których mówiłam wcześniej). Długo szło mi coś nie tak, wreszcie znalazłam trzy błędy przez które mój program nie dawał takich samych wyników jak w Sparku.

  1. Porównywałam napisy zamiast liczb. W ten sposób, „12” było mniejsze od „8” bo jeśli potraktujemy te dwie liczby jako napisy to przecież „12” jest alfabetycznie wcześniej od „8”. Na szczęście dało się to szybko poprawić.
  2. Przy wypisywaniu wyników, nie używałam funkcji find do znajdowania przynależności wierzchołka do komponentu lecz wypisywałam do jakiego wierzchołka jest on bezpośrednio połączony. Jak już znalazłam ten błąd to też łatwo się go dało naprawić, zamiast parent[p], gdzie trzymałam identyfikator komponentu do jakiego wierzchołek należał, trzeba było użyć funkcji find(p) która wywoływała się rekurencyjnie aż doszło się do korzenia w spójnej składowej który był właściwym identyfikatorem komponentu.
  3. Dane które miałam były uszkodzone. Było to 5,5 GB danych zamiast 6,3. Już się zmartwiłam, że będę musiała znowu lecieć na uczelnię i walczyć z pendrivem żeby wgrać ten duży plik do systemu plików hdfs, ale na szczęście odkryłam dzięki stronie [1] taką komendę:
    tar jfx wiki.tar.bz2 -O | hdfs dfs -put – In/wikiNew
    Dzięki fladze -O, pliki nie są wypakowywane lokalnie lesz od razu do strumienia wyjściowego. Następnie wynik jest przekazywany do komendy hdfs dfs -put która pozwala na wgranie plików do hdfs. Zwycięstwo 🙂

Teraz ostatnie poprawki kodu. Właśnie liczę UF dla danych z Wikipedii na czterech maszynach. Jeśli będzie poprawnie, to zaimplementuję jeszcze wzorzec In-Maper Combiner, który wzięłam z artykułu [2], a który jest bardzo ładnie rozpisany na stronie 3.

Jak już to zadziała to będę mogła powrócić do zadania z BFS-em. Cieszę się, że wykryłam błąd z danymi zanim utworzyłam z tych danych listę sąsiedztwa potrzebną na działanie algorytmu BFS. Przeczytałam również wspomniany artykuł o technikach optymalizacji algorytmów grafowych w MapReduce i wykorzystam tam przynajmniej dwie techniki In Mapper Combiner wspomniany powyżej oraz Shimmy. Obydwie techniki będą pasowały do rozwiązań BFS oraz PageRank. Nie wiem jeszcze czy coś sprytnego da się zastosować do APSP i Triangle Count którego chyba się podejmę. Czas pokaże, a jest go mało, więc przekonam się chyba dość szybko.

Do dzieła!

_____

[1] – http://hakunamapdata.com/why-put-is-better-than-copyfromlocal-when-coping-files-to-hdfs/
[2] – Design Patterns for Efficient Graph Algorithms in MapReduce, Jimmy Lin and Michael Schatz
[3] – https://vangjee.wordpress.com/2012/03/07/the-in-mapper-combining-design-pattern-for-mapreduce-programming/

Reklamy

Błąd znaleziony

Problem jest z moją klasą edgesToList. Jako dane wejściowe przyjmuje ona listę krawędzi w grafie:
a c
d b

I tworzy następującą listę sąsiedztwa:
a;c
d;b

Jak widać, nie ma w wynikowej liście wiersza który zaczynałby się od wierzchołka c ani b, a to dlatego, że z tych wierzchołków nie wychodzi żadna krawędź.

Jeśli wierzchołek a jest źródłem, to mój BFS da następujący wynik:
a 0
c 1
d MAX

Nie ma drogi z a do b, więc powinien w wyniku być również wiersz b MAX. Czemu jednak go brakuje? Już tłumaczę.

Istnieje krawędź z a do c, więc w jednej z iteracji algorytmu rozważani są wszyscy sąsiedzi a i odległość do c jest bez problemu obliczona. Nie ma jednak drogi z a do d, więc sąsiedzi d nigdy nie są rozważani, czyli algorytm nie zdaje sobie sprawy o istnieniu wierzchołka b. Żeby był on wzięty pod uwagę, to w pliku wejściowym powinien być wiersz w którym znajduje się jedynie znak b bez żadnych średników i sąsiadów – oznaczałoby to, że b istnieje, ale nie wychodzi z niego żadna krawędź, czyli tak jak jest w rzeczywistości.

Tak więc wystarczy przerobić klasę edgesToList by wypisywała również wierzchołki z których nie wychodzi żadna krawędź w taki sposób:
a;c
b
c
d;c
I chyba nawet wiem już jak to zrobić.

EDIT:
No i super, jedna linijka wystarczyła żeby wszystko policzyło się dobrze 🙂

Kolejne zadania to:

  1. Użyć edgesToList żeby utworzyć listę sąsiedztwa dla grafu z Wikipedii
  2. Użyć invertEdges (również napisanej przeze mnie) żeby odwrócić krawędzie na potrzeby obliczenia SSSP przez Sparka
  3. Poprawić wypisywanie wyników SSSP w Sparku żeby było możliwe łatwe porównanie wyników z wersji Hadoop i Spark. Jeśli będą się zgadzały to ten etap będzie można wreszcie uznać za skończony!
  4. Poczytać poprzednio wspomniany artykuł (Design Patterns for Efficient Graph Algorithms in MapReduce) w którym są opisane techniki optymalizacji algorytmów iteracyjnych w MapReduce. Prawdopodobnie używam tych technik nie zdając sobie z tego sprawy, bo używałam tutoriali do napisania tego algorytmu iteracyjnego, ale przydałoby się nazywać rzeczy po imieniu kiedy będę prezentowała swój algorytm promotorowi, a w tym artykule są zebrane wszystkie definicje.

To teraz będę spać spokojnie. Hurra!

Braki w wynikach

Po zalogowaniu się do VPNa na moim komputerze okazało się, że obliczenia z środy oraz dzisiejsze wciąż trwają. Zdecydowanie coś jest nie tak z algorytmem SSSP w Sparku. Postanowiłam go na razie porzucić i użyć klasy ShortestPaths o którym wspomniałam w poprzednim poście.

Obliczam właśnie ShortestPaths dla średnich danych. Liczy się szybko i poprawnie. Krawędzie są skierowane, więc jest dużo wierzchołków które nie są dostępne ze źródła.

Zrobiłam też obliczenia SSSP dla tego średniego grafu w Hadoop. Niestety brakuje paru wierzchołków w wyniku, to dziwne. Będzie trzeba jutro to dokładnie sprawdzić czemu są braki.

Jak zostanie już naprawione to będzie należało:

  1. Utworzyć listę sąsiedztwa dla wierzchołków z grafu Wikipedii. Ten graf jest przedstawiony jako lista krawędzi gdzie w każdym wierszu jest powiedziane z jakiego wierzchołka rozpoczyna się krawędź i do jakiego ona prowadzi. Algorytm BFS w Hadoop korzysta z listy sąsiedztwa, dodatkowo potrzebuje jeszcze parametrów distance i visited. Do takiego przetworzenia danych z listy krawędzi na listę sąsiedztwa napisałam klasę edgesToList. Użyję ją od razu jak naprawię błąd z brakującymi wierzchołkami dla grafu średniego.
  2. Zapuścić ShortestPaths ze Sparka dla danych z wikipedii i porównać. Jak wyniki będą się zgadzały, opisać i pokazać promotorowi.
  3. Ponieważ szkoda mi teraz czasu na szukanie info o tym jak wczytać graf w Sparku z wagami (postaram się poszukać o tym info jutro w pracy), zajmę się następnie przerabianiem MST na Connected Compnents, żebym miała do pokazania kolejny program.
  4. W pracy warto będzie też poczytać [1]. Są tam opisane efektywne wzorce w paradygmacie MapReduce dla algorytmów grafowych – na pewno będzie to warto wrzucić do źródeł a i może znajdzie się tam coś ciekawego w temacie.

_____
[1] – Design Patterns for Efficient Graph Algorithms in MapReduce, Jimmy Lin and Michael Schatz

Obliczenia trwają wieczność

Jak w temacie, wczoraj około północy zapuściłam obliczenia najkrótszej ścieżki dla danych z Wikipedii dla programu w Sparku i program wciąż jeszcze liczy! Nie korzystam teraz z mojego komputera więc nie mogę połączyć się z VPNem uczelnianej sieci żeby podejrzec co jest nie tak.

Dobra wiadomość jest taka, że istotnie będzie trzeba wprowadzić niewielkie zmiany do mojego programu MST żeby policzyć Connected Components w grafie – a więc udało mi się uratować jakiś miesiąc lub dwa mojej pracy którą wykonałam w grudniu i styczniu.

Oprócz problemu z najkrótszą ścieżką w Sparku dla grafu bez wag, mam również problem z obliczeniem najkrótszej ścieżki z pojedynczego źródła dla grafu z wagami. Wydaje się, że Spark nie może wczytać wag w jakiś prosty sposób (poprzednio używałam do tego celu GraphLoader.edgeListFile). Trzeba by było wprowadzić dodatkowe kroki gdzie krawędzie byłyby mapowane na jakieś wagi.

Jak dostanę się do swojego komputera to dobrze by było podejrzeć co się dzieje z aktualnym programem w Sparku, czemu liczy tak długo i ile procent zadania już wykonał.

Póki nie mam dostępu do swojego kompa, zacznę rozważać algorytm ShortestPaths z biblioteki Sparka – być może będzie mógł posłużyć do obliczenia SSSP i APSP jednocześnie? W definicji tego algorytmu jest napisane:
Computes shortest paths to the given set of landmark vertices, returning a graph where each vertex attribute is a map containing the shortest-path distance to each reachable landmark.
Czyli oblicza najkrótsze ścieżki z każdego wierzchołka do  wybranej grupy wierzchołków, landmarks. Wykorzystałabym to następująco:

  • Jeśli w tej grupie landmarks byłyby wszystkie wierzchołki, to algorytm obliczyłby APSP.
  • Jeśli krawędzie są obustronne i w wybranej grupie landmarks będzie tylko źródło to wtedy algorytm obliczy SSSP.
  • Jeśli graf jest jednak skierowany, to wystarczy odwrócić kierunek krawędzi i znowu w grupie wierzchołków docelowych wybrać tylko źródło  – efekt będzie taki sam co liczenie odległości ze źródła do wszystkich wierzchołków gdy krawędzie wskazują we właściwym kierunku.

Niestety znowu nie jest nigdzie napisane, że ten algorytm będzie działał dla grafów z wagami. Trzeba będzie to sprawdzić.

 

Idzie do przodu!

Powoli, powoli, idzie do przodu!

Co mam zrobione:

  • Algorytm BFS z iteracjami napisany w Hadoop dla grafu bez wag

Co się robi:

  • Algorytm Single Source Shortest Path w Spark z biblioteki GraphX dla grafu bez wag

Co potem:

  • Jak Spark skończy liczyć, będzie trzeba porównać wyniki i mam nadzieję, że będą identyczne! 🙂
  • Znaleźć info czy Spark potrafi policzyć SSSP dla grafu z wagami
  • Jeśli tak to policzyć powyższe a następnie przerobić algorytm Bfs na BfsWeighted żeby liczył BFS-a dla grafu z wagami

Inne algorytmy:

  1. Za pomocą algorytmu MST można zbadać połączone komponenty w grafie. Tak się składa, że GraphX zawiera w swojej bibliotece algorytm do zliczania połączonych komponentów. Należałoby zatem go uruchomić i sprawdzić jaki jest wynik oraz odpowiednio zaadaptować do tego MST – dzięki temu moje wypociny z tym algorytmem (któremu poświeciłam z dwa miesiące, kwiecień i maj) nie pójdą do kosza!
  2. W wolnym czasie można poczytać [1], jest tam trochę info o algorytmach które działają na systemach rozproszonych, a więc procesy nie dzielą wspólnej pamięci lecz przesyłają sobie wiadomości – czyli tak jak to działa w MapReduce. Warto by się wczytać na temat algorytmu APSP, może da się coś wykorzystać w oparciu o model MapReduce?
  3. Na końcu, jak już powyższe będzie policzone i ładnie zaprezentowane promotorowi, można się zająć algorytmami Triangle Count (opisanym w [2]), K-Means (szczegóły tu: [3]) oraz klasycznym dla MapReduce, algorytmem Page Rank. O szczegółach napiszę kiedy przyjdzie na to czas, teraz zajmę się poprzednimi punktami z listy.

______

[1] – M. Raynal, Distributed Algorithms for Message-Passing Systems, Chapter 2
[2] – Meysam Taassori , Counting Triangles in MapReduce
[3] – Weizhong Zhao, Huifang Ma and Qing He, Parallel K-Means Clustering Based on MapReduce, CloudCom 2009, LNCS 5931, pp. 674–679, 2009

Szukam motywacji

OK, nie udało się z moim pomysłem… No i nie mogę tego przeboleć. Myśl, że muszę zaczynać od początku, a przynajmniej cofnąć się o parę miesięcy strasznie mnie przygnębia.

Jutro muszę koniecznie napisać wersję klasyczną BFS-a na Hadoop i przetestować ją dla małych danych, średnich i wreszcie dla danych z Wikipedii.

Następnie należy zmienić jeden warunek w algorytmie, żeby działał dla grafów z wagami. Algorytm nie powinien przestać analizować wierzchołków jak już je odwiedzi lecz w każdym momencie kiedy jakaś ścieżka jest polepszana, jest niezbędna dodatkowa iteracja algorytmu.

W doborze algorytmów ogranicza mnie przede wszystkim dostępna biblioteka Sparka z którą muszę porównywać moje rozwiązania.

Muszę się też zastanowić, czy nie da się jakoś wykorzystać algorytmu do znalezienia połączonych komponentów (ang. connected components) w grafie – taki algorytm istnieje w Sparku i chyba można go prosto napisać w środowisku równoległym. Ale zanim to zrobię, warto skończyć wreszcie tego BFS-a!

Plan na jutro:

  1. BFS dla grafu bez wag. Klasyczne rozwiązanie Hadoop. Dla danych małych, średnich i wreszcie dużych, niemieszczących się w pamięci maszyny.
  2. BFS dla grafu z wagami. Powinno być łatwo przerobić algorytm poprzedni. Opisać. Pokazać promotorowi. Mieć jeden algorytm (w dwóch przypadkach) z głowy.
  3. Rozważyć algorytmy APSP, Connected components, Triangle Count i Page Rank. Powinno wystarczyć. Nie powinno być trudno.

Motywacjo, przybywaj!

Utrata sposobu rozwiązania

Udało mi się wykonać niezbędne testy, żeby móc stwierdzić co jest nie tak. Niestety, dane se się zgadzały i już po pierwszym punkcie mojego testu stwierdziłam, że coś jest nie tak z algorytmem BFS w wersji rozproszonej. Wykonałam BFS w Hadoop ale bez rozdzielania wierzchołków na maszyny i wyniki były identyczne ze Sparkiem, więc najwidoczniej coś mi nie działało z moim programem rozproszonym.

Dopiero po rozpisaniu grafu (a nie było to proste przy tak dużej liczbie danych) udało mi się znaleźć mniejszy scenariusz dla którego rozproszony algorytm nie zadziałał.

Graf dla mniejszych danych w którym algorytm się wywala wygląda następująco (liczby przed średnikiem to wierzchołki, a po średniku to ich sąsiedzi):
0;1,5
1;0,2
2;1,3
3;2,4
4;3,8
5;0,6
6;5,7
7;6,8
8;7,4

Teraz załóżmy, że w maszynie A lądują wiersze 1 i 2, a wiersze 3,4,5,6,7,8 lądują w maszynie B. Wiersz zerowy ląduje w obu maszynach bo jest to wierzchołek startowy.

Najkrótszą trasą z 0 do 4 jest 0-1-2-3-4, czyli ma długość 4. Rozproszony algorytm powie niestety że 5. A to dlatego, że jeśli analizujemy wierzchołek x i jego sąsiad y był już odwiedzony, to krawędź między nimi uznaje się za zbędną – skoro y był odwiedzony to znaczy, że już w jakiś sposób się go wcześniej odwiedziło, więc znana jest krótsza droga do niego niż przez x. Tak więc maszyna B obliczy trasę do 4 o długości 5 następująco: 0-5-6-7-8-4. Przy odwiedzaniu 3 uzna, że krawędź między 3 i 4 jest zbędna, bo 4 już zostało wcześniej odwiedzone.

Przy połączeniu wszystkich informacji, 3 nie będzie miało odległości 6, jak obliczyła maszyna B (0-5-6-7-8-4-3) tylko 3 (0-1-2-3), ale krawędź między 3 i 4 została wcześniej usunięta. W ten sposób 0-1-2-3-4 nigdy nie zostanie obliczona i zostanie trasa do 4 o długości 5… Więc jest błąd.

Algorytm może zakładać, że krawędź między wierzchołkiem x i y jest zbędna wtedy i tylko wtedy jeśli y został wcześniej odwiedzony i wszystkie wierzchołki na poziomie y zostały odwiedzone. Rozpraszając wierzchołki po maszynach w losowy sposób, nie zwracając uwagę na poziomy w grafie, nie jesteśmy w stanie zagwarantować podkreślonego warunku – stąd mój błąd.

Wygląda na to, że zostaje mi do zaimplementowania klasyczna wersja algorytmu BFS która ma tyle iteracji co głębokość grafu, a jest to dość proste rozwiązanie.Szkoda, bo nie chciałam iść na łatwiznę tylko wymyślić jakąś optymalizację i przez to straciłam dużo czasu. Teraz wracam do początku żeby zaimplementować podstawową wersję. Szkoda!