Uppgift 10 våren 2013

Uppgiften ska lämnas till din övningsledare på övningen den 19/4.

För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter.

Hemuppgift

Läs den här texten om grafer.

Läs om filer och felhantering i kapitel 12 i programmeringsboken. Studera programmet Grep.java. Det är en förenklad version (som inte hanterar reguljära uttryck) av Unixkommandot grep. Jämför med grep.go, motsvarande program skrivet i Go.

Skriftlig uppgift

Grafer

Lämna in svar på följande uppgifter.

• Rita en oriktad graf med 6 hörn, 10 kanter och 2 sammanhängande komponenter. Går det att rita en graf med 5 hörn, 4 kanter och 3 komponenter?
• Låt G vara en oriktad graf som består av 8 hörn numrerade från 0 till 7 och kantmängden {(0,1), (0,3), (1,4), (2,2), (3,4), (3,5), (6,7)}.
  • Rita G.
  • Ange ordningen som hörnen besöks vid en djupetförstsökning (DFS) med start i hörn 0.
  • Ange ordningen som hörnen besöks vid en breddenförstsökning (BFS) med start i hörn 0.
  Du kan anta att grannarna till ett hörn besöks i nummerordning.
• Förklara varför DFS tar Θ(n²) tid för en sammanhängande graf med n hörn om grafen representeras med en närhetsmatris.

HashGraph

Bekanta dig med koden i Eclipse-projektet Graph.zip och gör sedan ytterligare en implementation av gränssnittet Graph. Din implementation ska avända närhetslistor implementerade med hjälp av hashtabeller. Datastrukturer och metodsignaturer är redan deklarerade i klassen HashGraph och testkod finns i klassen HashGraphTest. Du får inte ändra koden i gränssnitten Graph, VertexIterator eller VertexAction.

• Lämna in den nyskrivna klassen HashGraph.

Eclipse-tips: Jag har bara hittat ett väl fungerande sätt att importera ett existerande projekt från en zip-fil. Välj alternativet "Import..." från fil-menyn, välj sedan "Existing Projects into Workspace", tryck på "Next >", välj "Select archive file" och tryck till slut på "Finish".

Komponenter i slumpgraf

Prova din nya grafklass genom att skriva ett program som bygger en graf med n noder och n slumpmässigt utplacerade kanter. Programmet ska med hjälp av djupetförstsökning beräkna antalet komponenter i grafen och storleken på den största komponentet.

• Lämna in koden för detta program. (Du behöver naturligtvis inte lämna in de klasser och gränssnitt som finns färdiga.)

Prova hur snabbt ditt program blir för olika värden på n, n <= 5000, när man använder närhetsmatris respektive närhetslistor.

• Ange antalet komponenter och den största komponentents storlek när n = 1000.
• Vilken datastruktur är bäst i det här fallet? Varför? Förklara genom att beräkna tidskomplexiteten för DFS med närhetsmatris samt för DFS med närhetslistor.

Hitta vägen

Skriv ett program som anropas på följande sätt i Unix.

java Path FROM TO

FROM och TO är två heltal som anger en startnod och en slutnod i en graf. Programmet ska skriva ut noderna på någon väg från FROM till TO om det finns en sådan väg i grafen, annars skriver programmet ut en tom rad. Använd DFS.

Eclipse-tips: Du kan ange kommandoradsparametrar via "Run Configurations..." i run-menyn under fliken "Arguments".

Grafen ska lagras i en fil med namnet Distances.txt. Noderna är numrerade 0, 1, 2, ..., n-1. Filens första rad innehåller talet n. De andra raderna innehåller tre tal i, j och d separerade med blanktecken. Det positiva talet d anger avståndet mellan noderna i och j. Filen kan också innehålla "//"-kommentarer och tomma rader. Kommentarerna fungerar på samma sätt som i Java. Här är ett exempel på en fil som beskriver en liten graf.

// This is a database with distances between a number of cities.
// The cities are numbered 0, 1, 2, ..., n-1.
// The first lines contains the integer n.
// Each following line contains three integers i, j, and d separated by spaces.
// The positive number d is the distance between i and j.

6        // Size

0 1 100  // First edge
0 3 80
0 5 25
1 2 120
1 5 60
2 3 50
3 4 100
4 5 200  // Last edge

Vid eventuella fel så ska programmet skriva ut ett relevant felmeddelande till stderr och inte skriva något på stdout.

Alternativ uppgift

Om du vill så kan du istället göra hela uppgiften i Go. Använd då kodskelettet graph_skeleton.zip. How to Write Go Code innehåller de instruktioner du behöver för att komma igång med att bygga och testa egna paket i Go.

Valfri extrauppgift

Kraven är desamma som i den obligatoriska uppgiften men du skall i stället skriva ut den kortaste vägen mellan start- och slutnod. Använd Dijkstras algoritm.