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

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

w

Connecting to %s