Göm menyn

Abstraktion och abstrakta datatyper

Labbens syfte

  • Öva på att använda dictionaries
  • Introduktion till abstrakta datatyper
  • Prova på att använda text-editor + IPython istället för IDLE.

Att skicka in

  • Filen med er kod skickas in till er labbhandledare enligt samma procedur som tidigare labbar.

Grafer i Python

Python har ingen inbyggd datatyp för att hantera grafer, så för att kunna skriva program som hanterar grafer, måste vi hitta på ett eget sätt.

För att minska risken att vi som programmerare slarvar och för att göra koden mer läsbar och strukturerad behöver vi lägga upp en plan för att hantera grafer. Den metod man använder sig av kallas för abstraktion och vi skapar då abstrakta datatyper. Detta sätt att tänka använder man även i objektorienterad programmering.

Övergripande uppgift

Vi vill kunna representera en graf i python och ta reda på om två hörn är grannar, graden hos hörn och lite egenskaper hos en graf. Ni ska också inte heller jobba i IDLE utan i en texteditor och använda er av IPython.

En abstrakt datatyp för grafer

Grafer har hörn och kanter. I Strandh består en graf av en mängd hörn, en mängd kanter och funktionen phi eller psi beroende på om vi har en kant eller hörncenterad graf-representation.

Vi ska i denna labb använda oss av en hörncentrerad representation. I Python kan vi använda ett dictionary för att mappa mellan en nyckel och ett värde, så i denna labb använder vi oss av ett dictionary för att koppla ihop.

Vissa algoritmer vi ska implementera behöver markera hörn och kanter. Vi måste i vår representation av hörn och kanter också kunna lagra om de är markerade eller inte. Alltså:

  • Låt ett hörn representeras som en lista med två element: namnet på hörnet, samt ett heltal. Är heltalet 0 är hörnet inte markerat, är heltalet inte 0 är hörnet markerat. Det omarkerade hörnet "a1" ser alltså ut så här: ["a1", 0]. Det markerade hörnet "a2" skulle kunna se ut så här: ["a2", 3].
  • Låt en kant representeras som en lista med två element: namnet på kanten samt ett heltal. Är heltalet 0, är kanten inte markerad, är heltalet inte 0 är kanten markerad. Den markerade kanten "e1" kan alltså se ut så här: ["e1", 1]
  • Låt ett dictionary mappa mellan hörn och kanter: låt namn på hörn vara nycklar och en lista av namn på kanter vara värdet. Om vi har de två hörnen "a1" och "a2" och kanten "e1" som berör dessa hörn, har vi alltså följande innehåll i vårt dictionary: Uppdatering 2014-11-25: {"a1": "e1", "a2": "e1"} {"a1": ["e1"], "a2": ["e1"]}. Hörn kan ju röra fler än en kant, så det ska så kanterna måste ligga i en lista.
  • Låt en graf vara en lista som innehåller
    1. en lista med hörn
    2. en lista med kanter
    3. ett dictionary som kopplar ihop hörn med kanter

Vår representation av grafen som innehåller hörnen "a1" och "a2" enligt ovan, kanten "e1" enligt ovan, samt mappningen mellan hörn och kanter ser alltså ut så här: [ [["a1, 0], ["a2", 3]], [["e1", 1]], {"a1": "e1", "a2": "e1"}].

Det är relativt bökigt att skriva in graferna för hand med denna representation, så därför skriver vi hjälpfunktioner som hjälper oss abstrahera bort det bökiga.

Pseudokod som kommentarer

I denna labb gäller det att hålla tungan rätt i mun. För varje uppgift ni kommer till ska ni därför först skriva pseudokod för hur ni tänkt lösa uppgiften. Använd pseudokoden sedan som kommentarer till er implementation. Nedan följer ett exempel på hur detta kan se ut.

Pseudokod

def find_largest_number(number_list):
    # 1. sätt variabeln max_num till den första siffran i number_list
    # 2. loopa igenom resten av number_list. Om vi stöter på ett tal som är
    #    större än max_num, sätt max_num till det
    # 3. returnera max_num

Implementation

def find_largest_number(number_list):
    # 1. sätt variabeln max_num till den första siffran i number_list
    max_num = number_list[0]
    # 2. loopa igenom resten av number_list. Om vi stöter på ett tal som är
    #    större än max_num, sätt max_num till det
    for num in number_list[1:]:
        if num > max_num:
            max_num = num
    # 3. returnera max_num
    return max_num

Labbskelett

Labbskelett till denna labb hittar ni här: http://www.ida.liu.se/~729G04/labbar/labbmaterial/labb6-labbskelett.py

Uppgift 1

Representera graferna i nedanstående bilder i pythonkod.

För att ni inte ska behöva knappa in alla listor och dictionaries för hand behöver vi några funktioner som hjälper oss att handskas med graferna. Dessa följer nedan. Ni måste först skapa hjälpfunktioerna

Uppgift 1a: create_vertex(label)

Skriv funktionen create_vertex(label) som tar in en sträng som representerar namnet på ett hörn. Funktionen returnerar sedan en datastruktur enligt ovan som används för att representera ett hörn, dvs en lista med en sträng (namn), och ett heltal (markerad eller ej). Låt hörnet vara omarkerat när du skapar det.

Uppgift 1b: get_vertex_label(vertex)

Skriv funktionen get_vertex_label(vertex) som returnerar namnet på hörnet vertex.

Uppgift 1c: create_edge(label)

Skriv funktionen create_vertex(label) som tar in en sträng som representerar namnet på ett hörn. Funktionen returnerar sedan en datastruktur enligt ovan som används för att representera ett hörn, dvs en lista med en sträng (namn), och ett heltal (markerad eller ej). Låt hörnet vara omarkerat när du skapar det.

Uppgift 1d: get_edge_label(edge)

Skriv funktionen get_edge_label(edge) som returnerar namnet på kanten edge.

Uppgift 1e: create_graph()

Skriv funktionen create_graph() som ska returnera en tom datastruktur enligt specifikationen ovan, dvs en lista som innehåller två tomma listor och ett dictionary.

Uppgift 1f: add_vertext(graph, vertex_label)

Skriv funktionen add_vertex(graph, vertex_label) som tar in grafen graph, dvs en lista med två listor och ett dictionary, samt namnet på ett hörn vertex_label, dvs en sträng. Funktionen ska skapa och lägga till hörnet med namnet vertex_label till grafen graph. Två hörn får inte heta samma sak, så om det redan finns ett hörn i grafen graph med samma namn som hörnet vertex, får hörnet vertex inte läggas till. Skriv istället ut ett felmeddelande, t.ex. "ERROR: duplicate vertex". Ännu bättre om ni också skriver ut namnet på det hörn som inte kunde läggas till.

Uppgift 1g: add_edge(graph, edge_label, vertex_label1, vertex_label2)

Skriv funktionen add_edge(graph, edge_label, vertex_label1, vertex_label2) som tar in grafen graph, kanten med namnet edge_label, dvs en sträng, samt namnen på två hörn, vertex_label1 och vertex_label2 (som kanten berör).

Funktionen ska skapa en kant och lägga till den till grafen graph. Man ska bara få lägga till en kant om de hörn som den berör redan finns i grafen. Två kanter i grafen får inte heller ha samma namn.

Om någon av hörnen inte finns i grafen, ska kanten inte läggas till och ett felmeddelande skrivas ut, t.ex. "ERROR: could not find vertex in graph.", ännnu bättre är det om ni också skriver ut namnet på det hörn som inte fanns med.

Tips: det kan vara smidigt att ha funktionen från uppg 2b här. Ni får göra den i förväg om ni vill.

Uppgift 2

Ytterligare hjälpfunktioner.

Uppgift 2a: get_vertex_count(graph)

Skriv funktionen get_vertex_count(graph) som returnerar antalet hörn i grafen graph.

Uppgift 2b: get_edge_count(graph)

Skriv funktionen get_edge_count(graph) som returnerar antalet kanter i grafen graph.

Uppgift 2c: get_vertex(graph, index)

Skriv funktionen get_vertex(graph, index) som ska returnera det hörn (dvs en lista med två element, en sträng och ett heltal) som har har indexet index i grafen.

Uppgift 2d: get_vertex_index(graph, label)

Skriv funktionen get_vertex_index(graph, label) som ska returnera det index som hörnet med namnet label har i grafen graph. Om hörnet inte finns, ska -1 returneras.

Uppgift 2e: get_edge(graph, index)

Skriv funktionen get_edge(graph, index) som ska returnera den kant (dvs en lista med två element, en sträng och ett heltal) som har har indexet index i grafen.

Uppgift 2f: get_edge_index(graph, label)

Skriv funktionen get_edge_index(graph, label) som ska returnera det index som kanten med namnet label har i grafen graph. Om kanten inte finns, ska -1 returneras.

Uppgift 2g: get_vertex_edge_labels(graph, vertex_label)

Skriv funktionen get_vertex_edges(graph, vertex_label) som returnerar en lista med de namnen på de kanter som berör hörnet med namnet vertex_label.

Uppgift 2h: get_vertex_labels(graph):

Skriv funktionen get_vertex_labels(graph) som ska returnera en lista med namnen på de hörn som finns i grafen graph.

Uppgift 2i: get_edge_labels(graph):

Skriv funktionen get_edge_labels(graph) som ska returnera en lista med namnen på de kanter som finns i grafen graph.

Uppgift 3: storleken på en graf

Storleken på en graf definieras som antalet kanter. Skriv funktionen size(graph) som tar in en graf, dvs en datastrukturen vi använder för vår abstrakta datatyp graph och returnerar dess storlek.

Uppgift 4: graden hos ett hörn

Skriv funktionen degree(graph, vertex_label) som returnerar graden hos hörnet med namnet vertex_label i grafen graph.

Uppgift 5: Berörs hörnet av kanten?

Skriv funktionen touches(graph, vertex_label, edge_label) som returnerar True om hörnet med namnet vertex_label och kanten med namnet edge_label berör varandra i grafen graph. Om de inte berör varandra, returneras False.

Uppgift 6: Är hörnen grannar?

Skriv funktionen are_neighbors(graph, vertex_label1, vertex_label2) som returnerar True om hörnen med namnen vertex_label1 och vertex_label2 är grannar, annars returneras False.

Uppgift 7: Vilka är hörnets grannar?

Skriv funktionen get_neighbors(graph, vertex_label) som returnerar en lista med namnen på grannarna till hörnet med namnet vertex_label.


Sidansvarig: Jody Foo
Senast uppdaterad: 2014-11-19