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!

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 z Twittera

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

Zdjęcie na Facebooku

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

Zdjęcie na Google+

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

Connecting to %s