Datastrukturer (DAT037), lp2 2017

Tjänster där användaren anger startplats och destination och sedan får en vägbeskrivning för kortaste/snabbaste vägen kan baseras på Dijkstras algoritm. Kartan representeras av en viktad graf där noderna är platser/adresser och en vikt anger avståndet mellan två platser (eller tiden det tar att förflytta sig mellan dem med ett visst transportmedel). Dijkstras algoritm beräknar en kortaste väg mellan två platser, d.v.s. en väg för vilken summan av vikterna i alla ingående kanter är så liten som möjligt.

Laborationen består av två delar. I del A ska ni implementera en datatyp som är en kombination av en avbildning och en prioritetskö. Denna kan ni ha nytta av när ni sedan, i del B, ska implementera Dijkstras algoritm.

A. "PrioMap"

Låt oss kalla en datatyp som kombinerar en avbildning och en prioritetskö på följande sätt för en "PrioMap". Datatypen har operationerna put och get från avbildnings-ADTn. Man kan alltså sätta in nyckel-värdepar och slå upp en nyckel och få det associerade värdet. Men man kan också plocka ut det minsta nyckel-värdeparet liknande en prioritetskö och det är värdena i nyckel-värdeparen som avgör vilket par som har högst prioritet.

Gränssnittet ni ska implementera är följande (filen PrioMap.java):

public interface PrioMap<K, V extends Comparable<? super V>> {
    void put(K k, V v);
    V get(K k);
    Pair<K, V> peek();
    Pair<K, V> poll();
}

Gränssnittet är generiskt; K är typparametern för nycklar och V parameter för värdetypen. Notera att värdetypen måste implementera Comparable. Alltså kan man jämföra värden i implementering för att avgöra vilket som är minst (och har högst prioritet). Gränssnittet refererar till en klass Pair (filen Pair.java). Denna är en generisk representation för par av objekt, i detta sammanhang ett par av en nyckel och ett värde.

Er implementering ska heta APrioMap och den ska ha en konstruktor utan argument som skapar en tom PrioMap. Metoderna ska göra följande:

Ett exempel på hur metoderna ska fungera:

PrioMap<String, Integer> pm = new APrioMap<>();
pm.put("A", 5);
pm.put("B", 8);
System.out.println(pm.peek());  // <A,5>
pm.put("A", 12);
System.out.println(pm.poll());  // <B,8>
System.out.println(pm.get("A"));  // 12
System.out.println(pm.get("B"));  // null

Metoderna ska ha följande tidskomplexitet (n är antal nyckelvärde-par):

Ni får använda vad som helst från javas standardbibliotek.

Tips: Utgå från er kod för binära heapen i labb 2. Utöka den genom att lägga till en avbildning, t.ex. en HashMap. Om ni använder en HashMap kan ni anta att hashningen fungerar bra, d.v.s. att komplexiteten för dess operationer är O(1) amorterat.

Testning

Det finns ett testprogram som testar er APrioMap (filen TestAPrioMap.java). Programmet behöver en textfil med testfall (filen apriomaptestcases.txt). Programmet körs så här:

java TestAPrioMap apriomaptestcases.txt

Om den hittar fel så är det som vanligt en bra idé att använda exemplet som visas för avlusning.

Komplexitetsanalys

Ni ska analysera tidskomplexiteten för era implementationer av put, get, peek och poll och lägga dessa analyser i en textfil kallad komplexitet.txt.

B. Dijkstras algoritm

Skriv färdigt följande klass (filen Graph.java):

import java.util.List;

public class Graph {
    public Graph() { ... }
    
    public void addVertice(String label) { ... }
    
    public void addEdge(String node1, String node2, int dist) { ... }
    
    public static class Path {
        public int totalDist;
        public List<String> vertices;
        public Path(int totalDist, List<String> vertices) {
            this.totalDist = totalDist;
            this.vertices = vertices;
        }

        @Override
        public String toString() {
            return "totalDist: " + totalDist + ", vertices: " + vertices.toString();
        }
    }
    
    public Path shortestPath(String start, String dest) { ... }
}

Klassen ska representera oriktade, viktade grafer med strängar som nod-etiketter och heltal som vikter. Representationen måste ske med grannlista.

Den lokala klassen Path representerar en väg från en start- till en slutnod i grafen. totalDist är summan av vikterna på alla kanter som ingår i vägen och vertices innehåller etiketterna för de noder som ingår i vägen, inklusive start- och slutnod.

Konstruktorn och metoderna ska göra följande:

Ett exempel på hur metoderna ska fungera:

Graph g = new Graph();
g.addVertice("A");
g.addVertice("B");
g.addVertice("C");
g.addVertice("D");
g.addVertice("E");
g.addVertice("F");
g.addEdge("A", "B", 2);
g.addEdge("B", "E", 3);
g.addEdge("A", "D", 7);
g.addEdge("D", "E", 1);
g.addEdge("B", "C", 1);
System.out.println(g.shortestPath("A", "C"));  // totalDist: 3, vertices: [A, B, C]
System.out.println(g.shortestPath("D", "A"));  // totalDist: 6, vertices: [D, E, B, A]
System.out.println(g.shortestPath("E", "F"));  // null

Ni ska implementera shortestPath med Dijkstras algoritm. Tidskomplexiteten för denna metod ska vara

O((v + e)logv)

där v är antalet noder i grafen och e är antalet kanter.

Ni får använda vad som helst från javas standardbibliotek. Om ni använder hashtabeller kan ni anta att hashning fungerar bra (d.v.s. operationerna tar O(1) amorterat).

Tips: Använd er PrioMap från del A.

Testning

Det finns ett testprogram som testar er implementation av Dijkstra (filen TestDijkstra.java). Detta behöver en textfil med testfall (filen dijkstratestcases.txt). Programmet körs så här:

java TestDijkstra dijkstratestcases.txt

Komplexitetsanalys

Ni ska analysera tidskomplexiteten för er implementation av shortestPath och inkludera denna analys i textfilen komplexitet.txt.

Givet material

Rapportering

Se till att ni noga följer de allmänna reglerna och riktlinjerna för laborationerna.

Innan ni skickar in ska ni se till att er kod klarar de automatiska tester som beskrivs ovan.

Skicka in följande filer: