Er uppgift är att implementera en tjänst liknande Västtrafiks reseplanerare. Ert program har tillgång till ett linjenät och har till uppgift att beräkna kortaste restiden mellan två givna hållplatser i detta nät, givet information om restiden mellan efterföljande hållplatser på varje linje. För enkelhets skull så behöver ni inte hantera avgångstider, utan det antas att varje resa kan ske omedelbart. Ni kan tänka er att det finns ett obegränsat antal taxibilar på varje hållplats.
Programmet 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. Huvudprogrammet ska heta Lab3
.
Detaljer:
Programmet ska ta fyra argument:
En fil med hållplatser (filformatet beskrivs nedan).
En fil med linjer (filformatet beskrivs nedan).
Starthållplatsen.
Ändhållplatsen.
Programmet ska läsa in filerna, skapa en riktad graf som representerar linjenätverket, och sedan beräkna en kortaste väg från starthållplatsen till ändhållplatsen (om möjligt).
Exempel på anrop av programmet:
java Lab3 stops.txt lines.txt HållplatsA HållplatsB
Programmet ska producera utdata på följande format: En rad med restiden (ett tal), och därefter en rad för varje hållplats (inklusive start- och ändhållplatserna). Om det inte finns någon kortaste väg så ska programmet skriva ut ett lämpligt meddelande (som inte får kunna förväxlas med en restid).
Om de fyra argumenten ovan exempelvis är stops-gbg.txt
lines-gbg.txt
Angered
Botaniska
så ska resultatet vara följande utskrift:
28
Angered
Gamlestadstorget
Centralstationen
Brunnsparken
Grönsakstorget
Vasaplatsen
VasaViktoriagatan
Olivedalsgatan
Botaniska
Om argumenten istället är stops-gbg.txt
lines-gbg.txt
Angered
Angered
så ska resultatet vara följande utskrift:
0
Angered
Om argumenten är stops-nopath.txt
lines-nopath.txt
Göteborg
Götene
så kan resultatet vara följande utskrift:
Det finns ingen väg från Göteborg till Götene.
Ni ska implementera implementera gränssnittet Path. Gränssnittet innehåller följande metoder:
* `computePath`: Beräknar en kortaste väg (om det finns
någon) mellan två noder i en graf utan negativa
kantvikter.
* `getPath`: Ger en iterator med noderna längs vägen (om
det finns någon), inklusive start- och målnoderna. Om det
inte finns någon väg ska iteratorn vara tom.
* `getPathLength`: Ger vägens längd (om det finns någon).
Ni måste definiera en egen grafklass, och ni måste representera grafer med grannlistor ("adjacency lists").
Ni måste använda Dijkstras algoritm för att beräkna en kortaste väg, och ni måste implementera algoritmen själva. Algoritmen måste vara implementerad så att den har tidskomplexiteten O(v + e log v), där e är antalet kanter, v antalet noder, under förutsättning att grafen inte är en multi-graf och att avgöra likhet mellan nodernas etiketter tar O(1). (Detta gäller inte för alla exempelgrafer och kanske inte för era nodetiketter, men det kan ni bortse från.) 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.)
Annars kan ni använda java collection frameworks implementering: PriorityQueue.
Grafimplementationen, samt implementationen av Dijkstras algoritm, måste vara återanvändbara och (någorlunda) generella:
Det ska gå att implementera andra grafalgoritmer utan att ändra på grafrepresentationen.
Grafdatastrukturen får inte innehålla några fält som bara används för Dijkstras algoritm.
Det ska gå att använda Dijkstras algoritm i andra program.
Huvudprogrammet ska separeras från implementationen av grafer och Dijkstras algoritm. Utskrift och eventuell grafik ska hanteras i huvudprogrammet.
Nedan följer en beskrivning av filformatet för linjenätet. För att ni ska slippa lägga för mycket tid på att skriva inläsningskod finns det metoder/funktioner i hjälppaketet Lab3Help
som ni kan använda.
Filerna för linjenä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 från 0 till 1000). Koordinaterna kan användas för att rita en karta över linjenätet och den snabbaste vägen.
Nästa fil innehåller en beskrivning av de olika linjerna:
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ör varje linje kommer först linjenumret, sedan antalet hållplatser, och slutligen listan över vilka hållplatser som ingår i linjen och tiden (i minuter) mellan de olika hållplatserna.
För att underlätta arbetet får ni ett paket, Lab3Help.jar(dokumentation), med funktioner för att läsa in linjeinformation och gränssnittet Path
. Packa inte upp jar-filen utan lägg den i er CLASSPATH.
Hållplatsfiler kan läsas in med metoden readStops
i klassen Lab3File
. Metoden readStops
ger en lista som innehåller element av typen BStop
. De här elementen representerar hållplatser och innehåller namn samt koordinater.
Linjefiler kan läsas in med readLines
, också i klassen Lab3File
, vars resultat är en lista med element av typen 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/värden av typen BLineStop
, som innehåller hållplatsens namn samt den tid det tar att ta sig till hållplatsen från föregående hållplats.
Följande filer med hållplatsinformation och linjeinformation kan användas för att testa er implementation:
För att underlätta utvecklingen, och kanske göra uppgiften lite intressantare, får ni tillgång till ett grafiskt användargränssnitt (GUI). Gränssnittet ingår i paketet Lab3Help
som nämndes ovan, se GUI
.
För att anropa GUI:t kan ni använda följande mall:
Lab3File fileParser = new Lab3File();
List<BStop> stops = fileParser.readStops(...);
List<BLineTable> lines = fileParser.readLines(...);
new GUI(stops, lines, new DijkstraStringPath(stops, lines));
Ni ska alltså använda konstruktorn i klassen GUI
, inte main-metoden.
Gränssnitten ger användaren möjlighet att välja avrese- och ändhållplatser, och visar information om de beräknade snabbaste vägarna.
Javagränssnitt: textruta.
Javagränssnitt: linjenätskarta.
Haskellgränssnitt.
Det är kanske lämpligt att först testa programmet med några små grafer.
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 exempelgraferna ovan), och sedan låta programmet göra samma sak.
Det finns också ett testprogram. Detta testprogram körs automatiskt när ni skickar in labben så se till att ert program klarar det. Se nedan för mer information om detta. För att kunna testa programmet själva och det ska kunna passera den automatiska testningen behöver ni implementera en icke-generisk wrapper-klass till er Path
-klass. Denna ska ha namnet DijkstraStringPath
. Denna wrapper måste ha en konstruktor som tar en lista med BStop
och lista med BLineTable
och den ska implementera interfacet 'PathPath
för den konkreta type String
). Signaturen för klassen ska alltså vara följande
public class DijkstraStringPath implements Path<String> {
public DijkstraStringPath(List<BStop>, List<BLineTable>) ...
public void computePath(String from, String to) ...
public Iterator<String> getPath() ...
public int getPathLength() ...
}
Implementering av denna ska förstås helt enkelt göra motsvarande anrop till er generiska Dijkstra-implementering. Wrappern är bara till för att få test-programmet att fungera.
Ni ska, som lösa filer, lämna in era källkodsfiler (huvudprogrammet (Lab3.java
), wrapper-klassen (DijkstraStringPath.java
) och er implementering av graf och Dijkstra's)). Era klasser ska inte deklarareras i något paket. Koden ska vara välstrukturerad och välkommenterad. Dessutom ska ni skicka in en textfil kallad dok.txt
, eller doc.txt
om ni skriver på engelska. I denna fil ska ni förklara varför er implementering av Dijkstra's algoritm uppfyller kravet på tidskomplexitet som anges ovan.
Skicka inte med testing.jar
, Lab3Help.jar
eller någon av graferna ovan.
Fire har en ny funktion för att automatiskt testa inskickade labbar. Detta använder vi i labb 3. Det den automatiska testningen gör är att kompilera er källkod och köra samma program som ni har tillgång till (testprogram). Kör alltså testprogrammet själva innan ni skickar in för att försäkra er om att det kommer att klara testet. Om kompilering eller testprogrammet misslyckas får ni meddelande om detta och möjlighet att dra tillbaka er inlämning. Händer detta så gör det, fixa felet och skicka in igen. Labbrättaren kommer inte hantera en inlämning med misslyckad testning. Om ni behöver hjälp så gå till labbhandledning. Observera att ni behöver göra den wrapper-klass som beskrivs under avsnittet Testning ovan.
Notera att den automatiska testningen sker asynkront. Man behöver oftast ladda om sidan för att se testresultatet i fire.
Ni får använda standardpaket (dock måste ni definiera en egen grafklass/-typ). T ex kan HashMap vara lämplig att använda för att slå upp strängar.