Warning! This is the 2012 course's website! You probably want the current course website.
Laboration 4. Vägen är målet
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 Lab4Help
och finns nedan som jar-fil.
Packa inte upp den utan lägg den i er
CLASSPATH.
- Gränssnittet
Path
(javadoc, Path.java) ska ni implementera. - Hjälppaketet
Lab4Help
(javadoc, Lab4Help.jar). - Testpaketet (testing.jar) lärde ni känna redan i lab 2.
Följande grafer med hållplatsinformation (noder) och linjeinformation (bågar) kan användas för att testa er implementation:
- stops-air.txt och lines-air.txt är en liten graf med flyglinjer från en tidigare kursbok.
- 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.
Alla filer ovan finns samlade i ett zip-arkiv.
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 Lab4Help
. 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.
Angered 750 1000 AxelDahlströmsTorg 200 70 Biskopsgården 50 950 ... WavrinskisPlats 450 150 ÖstraSjukhuset 1000 800
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 Lab4File
som finns i
hjälppaketet Lab4Help
). 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
Lab4File
-dokumentationen.
Nästa fil innehåller en beskrivning av de olika busslinjerna:
60 17 Redbergsplatsen Kärralundsgatan 6 Ullevi 5 Centralstationen 3 ... Redbergsplatsen 6 34 13 ÖstraSjukhuset Härlanda 12 Redbergsplatsen 2 Olskrokstorget 1 ... ÖstraSjukhuset 12Fö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
Lab4File
, 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 Lab4File
-dokumentationen.
Grafrepresentation, programstruktur m.m.
Grafen
Ni skall att använda grannlistor ("adjacency lists") för att representera er graf. Er implementation ska ha tidskomplexiteten O(N log N) eller bättre, där N = |E|+|V| är antalet bågar plus antalet noder. Därför är det viktigt att ni använder en effektiv prioritetskö för att implementera Dijkstra-algoritmens mängd V–S.
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.
Programstruktur
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!
Tips: börja med ett skelett!
Ett tips i all välmening är att börja med ett enkelt skelett för er implementation av
Path
. Detta skelett gör absolut ingenting, men får inte heller misslyckas:
- konstruerarna gör ingenting alls,
getPathLength()
kan returnera ett valfritt värde,computePath()
behöver bara spara de två hållplatserna, så attgetPath()
kan returnera just de två hållplatserna.
Med denna uppenbart felaktiga implementation, kan ni göra ett huvudprogram som går att kompilera och köra. Se längst ner på denna sida för tips på hur huvudprogrammet ska kunna bete sig.
Användargränssnitt (GUI)
I Lab4Help
-paketet finns det också ett enkelt GUI
Lab4Frame
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
Lab4Frame
finns beskrivna i dokumentationen.
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 Lab4Help
-paketet.
Testning
Det är lämpligt att ni först testar ert program på några små grafer (t.ex. lines/stops-air.txt) 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 tre graferna givna ovan, eller skriva egna.
Testprogram
Precis som i lab 2 finns det ett testprogram
(testing.jar)
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 gränssnittet Path
.
Tänk på att computePath
kommer att anropas flera gånger
efter att konstruktorn har anropats.
För denna lab finns det två testgeneratorer:
Lab4FileTest
tar filer med stop och linjer och testar från alla noder till alla noder i grafen.Lab4GenTest
testar med genererade grafer.
Spara testprogrammet i samma katalog som ni har er kompilerade java-kod (dvs .class-filerna). Starta sedan en terminal och i samma katalog kör:
java -ea -jar testing.jar lab4test.Lab4FileTest "MyPath stops-gbg.txt lines-gbg.txt" java -ea -jar testing.jar lab4test.Lab4GenTest "MyPath"Ni bör testa alla exempelgrafer från labbeskrivningen, och några miljoner av de genererade graferna.
Om testprogrammet verkar hänga sig (ger inga utskrifter) så har ni antagligen en oändlig loop i ert program. Kör då istället:
java -ea -jar testing.jar -v 5 lab4test...Det sista testfallet är då det fall som programmet hänger sig för.
Andra sätt att använda programmet
Det finns ett flertal flaggor som kan användas. För att se dem, kör:
java -ea -jar testing.jar --help java -ea -jar testing.jar lab4test.Lab4FileTest "MyPath --help" java -ea -jar testing.jar lab4test.Lab4GenTest "MyPath --help"
Inlämning
Skicka in dokumentation, de klasser som ni har skrivit, och andra relevanta filer (t ex egna grafer), inklusive Path.java.
Skicka inte med testing.jar, Lab4Help.jar, eller någon
av graferna ovan. De är separata resurser.
Era inlämningar måste följa de vanliga lab-instruktionerna och måste dessutom innehålla följande:
En klass som implementerar gränssnittet
Path
. Er implementation avcomputePath
ska ha den ovan angivna tidskomplexiteten för Dijkstras algoritm, och bör vara testad med testprogrammet ovan.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. Nedan kallar vi huvudprogrammet för
FindBusRoute.java
.Ni får själva bestämma om ni vill använda det givna användargränssnittet och kartritaren. Om ni använder det grafiska gränssnittet ska användaren ge två argument till programmet – hållplatsfilen och linjefilen:
java -ea FindBusRoute stops-gbg.txt lines-gbg.txt
Om ni inte använder det givna användargränssnittet (eller motsvarande) skall användaren kunna ge fyra argument till programmet: de två filerna, och start- och sluthållplats:
java -ea FindBusRoute stops-gbg.txt lines-gbg.txt Hagakyrkan Mariaplan
Programmet ska då åtminstone skriva ut listan av hållplatser längs den funna vägen:Hagakyrkan Järntorget Stigbergstorget Mariaplan