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 gränssnittet Path med hjälp av Dijkstras algoritm för kortaste vägen. Gränssnittet innehåller metoderna computePath som beräknar snabbaste vägen mellan två noder i en graf, getPath som returnerar en iterator med namn på noderna på vägen och getPathLength som returnerar restiden längs vägen.

Hjälpfiler

För att underlätta arbetet får ni ett paket med funktioner för att läsa in busslinjeinformation, ett enkelt användargränssnitt (GUI) och en klass ni kan använda för att rita busslinjenätet och snabbaste vägar. Paketet heter Lab3Help och finns nedan som jar-fil. Packa inte upp den utan lägg den i er CLASSPATH.

Hjälppaketet Lab3Help (jar, java-doc) (senast uppdaterad 2011-11-29 17:51)
Gränssnittet Path (javadoc, Path.java, Path.class) som ni ska implementera (se ovan och javadoc).

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 grafen från sidan 332 i kursboken för 2011.
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 skall slippa skriva inläsningkod för dessa filer finns det två publika metoder i hjälppaketet Lab3Help. Dessa returnerar innehållet i de två filer som nämns nedan.

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 skall användas för att rita en karta över busslinjenätet och den snabbaste vägen. Denna fil läses in med metoden readStops i klassen Lab3File som finns i hjälppaketet Lab3Help). Metoden returnerar en lista innehållande element av typen BStop. Ett BStop-objekt representerar en hållplats och innehåller dess namn samt dess koordinater. Dessa klasser finns beskrivna i Lab3File-dokumentationen.

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.

Denna fil läses in med metoden readLines i Lab3File, som returnerar en lista med BLineTable. 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 av typen BLineStop, som innehåller hållplatsens namn samt den tid det tar att ta sig till hållplatsen från hållplatsen före. Dessa klasser finns beskrivna i Lab3File-dokumentationen.

Grafrepresentation, programstruktur mm

Ni skall att använda grannlistor ("adjacency lists") för att representera er graf. Er implementation ska ha 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 effektiv prioritetskö.

Ni får använda Javas standardpaket om ni vill, t ex är HashMap lämplig att använda för att slå upp strängar.

Tänk på att separara huvudprogrammet från implementeringen av gränssnittet Path. Utskrift och eventuell grafik ska göras i huvudprogrammet! Det räcker om huvudprogrammet skriver ut listan av hållplatser på den funna vägen.

Separera implementeringen av grafen med dess grundläggande metoder från implementeringen av Dijkstras algoritm!

Användargränssnitt (GUI)

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 till 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 för att se om ni får rätt resultat. Ni kan göra detta genom att själva beräkna bästa vägen i en graf, och sedan låta ert program göra samma sak. Ni kan använda de 3 graferna givna ovan, eller skriva egna.

Testprogram

Det finns ett testprogram som ni kan använda för att se om ert program ger rätt resultat för en graf. I båda fallen testas er implementation av interfacet Path. Tänk på att computePath kommer att anropas flera gånger efter att konstruktorn 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, eller någon av graferna ovan. De är separata resurser.
Skicka med Path.java.

Era inlämningar måste följa de vanliga instruktionerna och måste dessutom innehålla följande:

Ett huvudprogram som beräknar snabbaste vägen mellan två hållplatser, talar om vilka hållplatser som ligger längs denna väg, samt längden på den snabbaste vägen.
Ni får själva bestämma om ni vill använda det givna användargränssnittet och kartritaren. Om ni inte använder det givna användargränssnittet (eller motsvarande) skall det gå att ge programmet en graf och två hållplatser som argument till main. Det räcker om huvudprogrammet skriver ut listan av hållplatser på den funna vägen.
Använder ni det givna användargränssnittet och kartritaren behöver det naturligtvis inte beskrivas eller dokumenteras när ni ger en översikt över er kod.
En klass som implementerar gränssnittet Path. Er algoritm ska ha den ovan angivna tidskomplexiteten för Dijkstras algoritm, och får gärna vara testad med testprogrammet ovan.