Laboration 3: Reseplanering

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.

Uppgiften

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.

Detaljer:

• Programmet ska ta fyra argument:

  1. En fil med hållplatser (filformatet beskrivs nedan).

  2. En fil med linjer (filformatet beskrivs nedan).

  3. Starthållplatsen.

  4. Ä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).

• 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 programmet i Java eller Haskell.

  • Om ni väljer att använda Java ska ni 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).

  • Om ni väljer att använda Haskell ska ni implementera en funktion med följande typ:

        _ => Graph v e -> v -> v -> Maybe ([v], e)

    (Klassvillkoren, "_", kan t ex vara (Ord v, Ord e, Num e), vilket gör att man kan jämföra nodetiketter och kantvikter med funktioner som (==) och (<=), och dessutom ger tillgång till numeriska funktioner som (+) för kantvikter. Om man använder HashMaps kanske Ord v kan bytas ut mot Eq v och Hashable v.)

    Givet en graf utan negativa kantvikter och två noder ska funktionen avgöra om det finns en väg från den första noden till den andra, och i så fall ge ett par som svar, innehållandes

    • alla noder (inklusive start- och slutnoderna) längs en av de kortaste vägarna från den första noden till den andra, och
    • längden på de kortaste vägarna från den första noden till den andra.

• Ni måste definiera en egen grafklass/-typ, 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  +  l) log v), där e är antalet kanter, v antalet noder, och l är den största nodetikettens storlek. 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 binomialköer eller Hinzes prioritetssökköer.

    För att installera de här paketen, kör följande kommandon i terminalen: först cabal update och sedan cabal install pqueue PSQueue.

  Notera att tidskomplexitetskravet gör att det kan vara olämpligt att representera grafer som hashtabeller som mappar nodetiketter till grannlistor. Det kan dock fungera att ha en hashtabell som mappar nodetiketter till unika heltal, och använda heltal istället för nodetiketter i den underliggande grafrepresentationen.

• 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 e d 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.

Linjenätsfiler

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.

Filformatet

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.

Hjälppaket

För att underlätta arbetet får ni ett paket/en modul, Lab3Help, med funktioner för att läsa in linjeinformation. Javapaketet innehåller också gränssnittet Path:

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

• Haskell: Lab3Help.hs, dokumentation.

Hållplatsfiler kan läsas in med metoden readStops (om ni använder Java hittar ni readStops i klassen Lab3File). Metoden/funktionen readStops ger en lista som innehåller element av typen BStop/Stop. De här elementen representerar hållplatser och innehåller namn samt koordinater.

Linjefiler kan läsas in med readLines, vars resultat är en lista med element av typen BLineTable/LineTable (om ni använder Java hittar ni readLines i klassen Lab3File). Varje BLineTable/LineTable 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/LineStop, som innehåller hållplatsens namn samt den tid det tar att ta sig till hållplatsen från föregående hållplats.

Exempel

Följande filer med hållplatsinformation och linjeinformation 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 (kanske inte helt aktuella) 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.
• stops-nopath.txt och lines-nopath.txt är en osammanhängande graf. Implementationen ska hantera sådana grafer.

Grafiskt gränssnitt

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):

• Java: Gränssnittet ingår i paketet Lab3Help som nämndes ovan, se GUI.

• Haskell: Lab3GUI.hs, dokumentation.

  Haskellgränssnittet använder Threepenny-gui, version 0.6.0.3, som kan installeras genom att köra följande kommandon i terminalen: först cabal update och sedan cabal install 'threepenny-gui == 0.6.0.3'.

  Om det inte går att installera paketet så kan det hända att det fungerar bättre med en nyare version av GHC. På (några av?) skolans datorer kan man aktivera unsup och köra vcs-select -p ghc-7.10.2 för att få tillgång till GHC 7.10.2.

  Det går också att använda Javagränssnittet ovan med Haskellprogram (eller andra program) på följande sätt:

      java -jar Lab3Help.jar <Haskellprogram> <hållplatsfil> <linjefil>

  Gränssnittet kör då programmet <Haskellprogram>. Det är troligt att det inte räcker att ge programmets namn, utan att man också behöver ange sökvägen (t ex ./Lab3).

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.

Testning

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. Lösningar som inte accepteras av testprogrammet kan underkännas utan närmare granskning av koden.

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, Lab3GUI.hs, eller någon av graferna ovan.

Era inlämningar måste följa de vanliga instruktionerna.

Tips

Ni får använda standardpaket (dock måste ni definiera en egen grafklass/-typ). T ex kan HashMap (för Java) och Data.Map.Strict 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.)