Laboration 3 - Reseplanering

Er uppgift är att implementera en tjänst liknande Västtrafiks reseplanerare. Ert program har tillgång till ett busslinjenät och har till uppgift att beräkna kortaste restiden mellan två givna hållplatser i detta nät. Man räknar ut restiden genom att addera färdtiderna mellan hållplatserna på den snabbaste resvägen.

Busslinjenätet beskrivs i två filer vars format ges nedan. Ert program ska läsa in dessa filer och skapa en riktad graf för detta linjenät. Vidare ska ni implementera Dijkstras algoritm och använda den för att beräkna kortaste restiden mellan två givna hållplatser:

Om ni väljer att använda Java ska ni implementera gränssnittet Path (Path.java, Path.class). Gränssnittet innehåller metoderna computePath som beräknar kortaste vägen mellan två noder i en graf, getPath som ger en iterator med namn på noderna på vägen, och getPathLength som ger restiden längs vägen.
Om ni väljer att använda Haskell ska ni implementera en funktion med följande typ: Graph -> String -> String -> [String]. Givet en graf och två noder (representerade som strängar) ska funktionen beräkna den kortaste vägen från den första noden till den andra. (Ni får själva definiera typen Graph.)

Hjälpfiler

För att underlätta arbetet får ni ett paket, Lab3Help, med funktioner för att läsa in busslinjeinformation. För Java finns även ett enkelt användargränssnitt (GUI) och en klass ni kan använda för att rita upp busslinjenätet och snabbaste vägar:

Java: Lab3Help.jar, dokumentation. Packa inte upp jar-filen utan lägg den i er CLASSPATH.
Haskell: Lab3Help.hs, dokumentation.

Följande grafer med hållplatsinformation (noder) och linjeinformation (kanter) kan användas för att testa er implementation:

stops-air.txt och lines-air.txt är en liten graf från en tidigare kursbok.
stops-g332.txt och lines-g332.txt är graf 9.8 från Weiss (både andra och tredje upplagan).
stops-gbg.txt och lines-gbg.txt är en graf med hållplatser och linjer i Göteborg.
stops-bvs.txt och lines-bvs.txt är en stor graf med hållplatser och linjer som ni kan använda för testning av effektiviteten av er lösning.

Filformat för busslinjenätet

Nedan följer en beskrivning av filformatet för busslinjenätet. För att ni ska slippa skriva inläsningskod för dessa filer finns det två publika metoder/funktioner i hjälppaketet Lab3Help som ni kan använda.

Filerna för busslinjenätet har följande struktur. Den första filen innehåller information om hållplatserna i nätet:

Brunnsparken                    500     500
Redbergsplatsen                 700     350
Frölunda-Torg                   200     900

För varje hållplats finns förutom namnet också hållplatsens koordinater (heltal mellan 0 och 1000); koordinaterna kan användas för att rita en karta över busslinjenätet och den snabbaste vägen. Hållplatsfiler kan läsas in med metoden readStops (om ni använder Java hittar ni readStops i klassen Lab3File). Metoden/funktionen readStops returnerar en lista som innehåller element av typen BStop. De här elementen representerar hållplatser och innehåller namn samt koordinater.

Nästa fil innehåller en beskrivning av de olika busslinjerna:

60 5
Redbergsplatsen
Drottningtorget         5
Chalmers                2
Drottningtorget         2
Redbergsplatsen         5
34 7
Östra-sjukhuset
Olskroken               6
Centralstationen        3
Tuve                    7
Centralstationen        7
Olskroken               3
Östra-sjukhuset         6

Först kommer linjenumret, sedan följer antalet hållplatser och slutligen listan över vilka hållplatser som ingår i linjen och den tid som det tar mellan hållplatserna.

Den här sortens fil kan läsas in med readLines, som returnerar en lista med element av typen BLineTable (om ni använder Java hittar ni readLines i klassen Lab3File). Varje BLineTable representerar information om en linje och innehåller linjens nummer samt de hållplatser som ingår i linjen. Dessa hållplatser representeras av objekt/värden av typen BLineStop, som innehåller hållplatsens namn samt den tid det tar att ta sig till hållplatsen från hållplatsen innan.

Programstruktur, grafrepresentation m m

Huvudprogrammet ska beräkna en snabbaste väg mellan två hållplatser, tala om vilka hållplatser som ligger längs denna väg, och vägens längd.

Ni får själva bestämma om ni vill använda det givna användargränssnittet och kartritaren (se nedan). Om ni inte använder det givna användargränssnittet (eller motsvarande) ska det gå att ge programmet en graf (två filer: hållplatser + linjer) och två hållplatser som kommandoradsargument.

Huvudprogrammet ska separeras från implementationen av grafer och Dijkstras algoritm. Utskrift och eventuell grafik ska hanteras i huvudprogrammet.

Ni måste använda grannlistor ("adjacency lists") för att representera grafer, och grafimplementationen, samt implementationen av Dijkstras algoritm, måste vara återanvändbara och (någorlunda) generella. Grafimplementationen med dess grundläggande metoder/funktioner måste dessutom separeras från implementationen av Dijkstras algoritm.

Dijkstras algoritm måste vara implementerad så att den har tidskomplexiteten O((m+n)log n), där m är antalet kanter och n antalet noder. Därför är det viktigt att ni använder en (tillräckligt) effektiv prioritetskö:

En möjlighet är att använda den prioritetskö ni implementerade i labb 2. (Givet att den är tillräckligt effektiv.)
Om ni använder Java kan ni t ex använda PriorityQueue.
Om ni använder Haskell så kan ni t ex använda Data.PSQueue. Idén bakom Data.PSQueue finns beskriven i Hinzes "A Simple Implementation Technique for Priority Search Queues" (se kurslitteraturen), som även innehåller en implementation av Dijkstras algoritm. Notera dock att Hinzes kod bara ger kortaste avståndet från startnoden till andra noder, den ger inte en komplett kortaste väg. Koden är också beskriven med hjälp av "vyer", som Haskell saknar stöd för. Följande variant av Hinzes kod är kanske enklare att förstå: HinzeDijkstra.hs.
För att få tillgång till Data.PSQueue, kör följande kommandon i terminalen: först cabal update och sedan cabal install PSQueue.

Ni får använda standardpaket om ni vill, t ex kan HashMap (för Java) och Data.Map eller Data.HashMap.Strict (för Haskell) vara lämpliga att använda för att slå upp strängar. (Om ni vill använda Data.HashMap.Strict, kör då följande kommandon i terminalen: först cabal update och sedan cabal install unordered-containers.)

Användargränssnitt (GUI)

Det finns för närvarande inget GUI för Haskell.

I Lab3Help-paketet finns det också ett enkelt GUI Lab3Frame som ni kan använda till er lab. Detta gränssnitt ger användaren möjlighet att välja avrese- och sluthållplats. Vidare innehåller det också en JTextArea, i vilken programmet kan skriva ut information om snabbaste vägen. Metoderna i Lab3Frame finns beskrivna i dokumentationen.

bild på huvudprogram

Grafisk representation av kartan

För att rita en karta över alla busslinjerna och den snabbaste vägen kan ni använda BusMapFrame. För er egen skull bör er lösning kunna rita ut hela kartan och den snabbaste vägen mellan de två givna hållplatserna. Hur ni använder BusMapFrame finns beskrivet i dokumentationen av Lab3Help-paketet.

bild över linjenät

Testning

Det är lämpligt att ni först testar ert program på några små grafer (som ni själva definierar) innan ni försöker med de stora graferna.

Ni måste testa er lösning och se till att ni får rätt resultat. Ni kan göra detta genom att själva beräkna bästa vägen i en graf (t ex någon av de fyra ovan), och sedan låta programmet göra samma sak.

Det finns också ett testprogram. Lösningar som inte accepteras av testprogrammet kan underkännas utan närmare granskning av koden.

Testprogrammet kan användas både för Javalösningar och för Haskellösningar. Om ni använder Java så testar programmet er implementation av gränssnittet Path. Tänk på att computePath kan komma att anropas flera gånger efter att konstrueraren har anropats.

Inlämning

Skicka in dokumentation, de klasser som ni har skrivit, och andra relevanta filer (t ex egna grafer). Skicka inte med testing.jar, Lab3Help.jar, Lab3Help.hs, eller någon av graferna ovan. Skicka med Path.java.

Era inlämningar måste följa de vanliga instruktionerna. Använder ni det givna användargränssnittet och kartritaren behöver de naturligtvis inte beskrivas eller dokumenteras när ni ger en översikt över er kod.