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ć.

 

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