Witam. Mam tabelkę Tickets (https://github.com/coolphon/BusCompanySupport/blob/master/app/models/ticket.rb) która zawiera informacje o podróży - skąd, dokąd, o której i do której. Chciałbym zastosować algorytm Dijkstry. Problem w tym że nie do końca wiem jak mogę go zaaplikować. Czy ktoś już może implementował ten algorytm? Bardziej mi chodzi o wskazówki w jaki sposób podejść do tego, jakiś pseudo kod…
Z góry dzięki za pomoc
Pozdrawiam
Z tego na ile rozumiem przeznaczenie tej klasy to ona Ci kompletnie nie pomaga bo algorytm miałby zastosowanie gdybyś miał połączone ze sobą klasy City(tutaj zależy jaką implementację algorytmu wybierzesz) które miałyby informacje nt. miast połączeń z innymi oraz odległości między nimi. I na tych danych mógłbyś zastosować ten algorytm aby znaleźć najkrótszą trasę którą proponujesz użytkownikowi a potem przepisujesz do klasy Ticket.
Co do implementacji samego algorytmu to jest to już “przewałkowane” na internetsach (wikipedia itd.).
Ale ja to mam zgromadzone na zasadzie - wszystkie bilety jakie istnieją są w tabelce Tickets. I taki ticket zawiera informacje skąd dokąd a koszt dostania się z punktu A do B to różnica pomiędzy czasem przyjazdu a czasem wyjazdu. Czytałem art na wikipedii dotyczący tego algorytmu ale mam problem z przemieleniem tego na kod. Mniej więcej wyobrażam sobie że będę wyszukiwał najpierw ticket bezpośredni(to już zaimplementowałem w kontrolerze) to alternatywnie muszę właśnie przeszukać bazę danych pod kątem tego połączenia. Tylko jak sobie wyobrażam implementację to mam problem z tym że muszę mieć dostęp do obiektów Ticket w Rubym, a w momencie gdy próbuję się odwołać do nich np tak =>
ticket = Ticket.find(1)
ticket.cityFrom
To dostaję error że to obiekt Active Record i nie mogę się odwołać w taki sposób.
:cityFrom, :cityTo, nie masz tych pol w baze wiec skad chcesz te dane brac? to musza byc jakies metody, nie widze tego u ciebie nigdzie
Ok widze w schema ze jednak masz ta w modelu jakas nieaktualna jest, no to jak takie pole jest to mozesz odwolac sie spokojnie i dostaniech dane, nie powinno byc problemu
W modelu zapomnialem annotate zrobić stad schema w modelu jest stare. Dzięki za zwrócenie na to uwagi, poprawie przy najbliższym commicie. Wcześniej były From i To ale to się gryzło ze składnią SQLa i musiałem zmienić.
Hej,
Trochę pokradłem, dokonałem brzydkich rzeczy aby zaprzęgnąć algorytm do działania i już prawie działa. Utknąłem na przekazywaniu zmiennej z kontrolera do widoku. Tutaj: https://github.com/coolphon/BusCompanySupport/blob/master/app/controllers/tickets_controller.rb
w linijkach 49-52 popełniam jakiś banalny błąd który powoduje że w widoku zamiast @tickets mam nil i nie mogę nic zrobić. Logger w kontrolerze pokazuje że zmienna @tickets istnieje. Robię to w ten sposób bo używam gemu paginate który działa tylko na obiektach ActiveRecord a @tickets w tamtym konkretnym wypadku jest zwykłą tablicą.
Generalnie na pewno w kodzie jest mnóstwo błędów pt “not the ruby way” i jeśli ktoś ma ochotę mi je wytknąć to ja z chęcią z pokorą je przyjmę.
respond_to do |format|
format.html { render(shortest_path_ticket_path)} //było redirect_to
format.xml { render :xml => @tickets }
end
Poprzenoś to do modelu
Jeśli masz czas i chęć do zabawy to zrób przerzucanie tych danych do Neo4j i tam zrób Dijkstrę.
Polecam literaturę: http://www.albertus.pl/ksiazka-projektowanie-algorytmow-i-struktur-danych-krystyna-balinska-301240/
Na studiach była wstępem do programowania - miałem także przyjemność (teraz to już przyjemność 
) mieć prowadzone zajęcia z autorką powyższej książki 
Myślę, że możesz tam znaleźć całkiem niezłe wytłumaczenie i rozwiązanie Twojego problemu
do wizualizacji możesz spojrzeć na to: http://weierstrass.is.tokushima-u.ac.jp/ikeda/suuri/dijkstra/DijkstraApp.shtml?demo1
algorytm jest raczej prosty i intuicyjny;)
ale z użyciem go w DB może być problem, skłaniałbym się do odpowiedzi Sławosza (neo4j), ewentualnie poszukaj jakiejś funkcji składowanej w necie
[quote=Tubis]respond_to do |format|
format.html { render(shortest_path_ticket_path)} //było redirect_to
format.xml { render :xml => @tickets }
end
Poprzenoś to do modelu[/quote]
pomogło takie coś:
respond_to do |format|
format.html { render:shortest_path } //było redirect_to
format.xml { render :xml => @tickets }
end
Dzięki za wskazówkę, wczoraj w nocy już ślepia mi się kleiły. Póki co rozwiązanie od strony algorytmicznej jest zrobione(użyłem bezpośrednio algorytmu z http://rosettacode.org przerzucając dane z activerecord do tablicy i tym feeduje algorytm. W wyniku dostaję tablice zawierającą najkrótszą drogę i tą drogę ponownie wyszukuje w activerecordzie i prezentuje userowi. Bardzo toporne rozwiązanie ale najszybsze z dostępnych dla mnie i zrozumiałe.
Możesz użyć też tablic lub hashy aby składować dane bezpośrednio w bazie Postgresql: http://www.postgresql.org/docs/9.1/static/hstore.html http://www.postgresql.org/docs/9.1/static/arrays.html - będzie mniej przerażająco.
Mam ponownie pytanie odnośnie sposobu w jaki powinienem coś zaimplementować. Mam zmienną @tickets która jest obiektem typu Array (nie activerecord) i zawiera bilety które można zarezerwować. Dla pojedynczego biletu mam akcję “reserve” która pozwala zarezerwować taki bilet. Natomiast dla tablicy już takiej akcji nie posiadam. Teraz moje pytanie czy da się to zrobić w widoku w taki sposób że mam jeden guzik reserve który wywoła wielokrotnie metodę reserve na każdym obiekcie w tablicy czy też muszę stworzyć nową metodę w kontrolerze reserve_many_tickets i jako parametr przesyłać tablicę ID ticketów do rezerwowania?
[code=ruby]arr = [‘foo’, ‘bar’]
arr.map {|s| s.upcase } #=> [‘FOO’, ‘BAR’]
arr.map(&:to_s) #=> [‘FOO’, ‘BAR’][/code]