Tips: labb grafer

Detta är den minsta av de tre labbarna i labbserien. I labben ska du lösa vissa uppgifter med hjälp av indatat du erhållit och algoritmerna som presenterats under föreläsning.

Programmeringsmomenten i denna labb är

• Förstå datat i indatafilen, testa din implementations förståelse av indatat genom att skriva ut de olika delarna separat. Kontrollräkna så att du får med alla noderna.
• Implementera den datastruktur som ska representera grafen. Både lista och matris är möjliga att använda. En matris kan i vissa delar möjliggöra en mer direkt översättning algoritm -> implementation.
• Implementera algoritmerna. Börja med DFS, testa implementationen. Din funktion ska kunna svara på frågan om grafen är sammanhängande utifrån en angiven startnod.
• Implementera funktioner som besvarar frågeställningarna.

Parsning av indata

Parsning av indatat är en nödvändig del av labben. Eftersom den här delen av uppgiften inte berör varken en adjacency-matris eller någon av algoritmerna ger jag här ett exempel på hur det kan gå till. Kontrollera med din handledare om du får använda koden som den är, eller om du ska skriva egen kod.

Att förstå indata består av två steg. Lexning och parsning.

Lexning

Lexning består i att tillskriva speciella symboler eller uttryck i indatat en betydelse. Symbolerna själva kallas lexemer, dess betydelse beskrivs av en token. I vårt indata måste vi tilldela en betydelse till åtminstone 3 olika typer av symboler.

Lexeme: #      Token: Comment
Lexeme: M      Token: Meta
Lexeme: 0-9    Token: Edge

En lexer måste också kunna berätta om indatat är slut så ytterligare en token behövs:

Lexeme: [EOF]  Token: EndOfFile

Parsning

Parsningsdelen består i att

1. bestämma en datastruktur som kan beskriva indatat på ett lättanvänt sätt.
2. fråga lexern om hur indatat ser ut.
3. Läsa/förstå indatat som din token indikerar, därefter sätta in indatat i datastrukturen i (1). Detta är parse-steget.

Eftersom indatat är radbaserat är den enkelt att skriva en lexer och parser för detta dataformat.

Det exempel jag ger nedan använder följande gränssnitt för inläsning av indatafilen.

reader.h

//
// Created by martin on 2022-03-30.
//

#ifndef DOA_LABB1_READER_H
#define DOA_LABB1_READER_H

#include<istream>
#include<map>
#include<vector>

using node_id_t = int;
using weight_t = double;
using meta_t = std::map<node_id_t, std::string>;

struct edge{
    node_id_t n1;
    node_id_t n2;
    weight_t weight;
    std::string description;
};

using edge_list_t = std::vector<edge>;

using adjacency_list_t = std::pair<meta_t, edge_list_t>;

adjacency_list_t parse_file(std::string filename);

#endif //DOA_LABB1_READER_H

Funktionen parse_file returnerar en adjacency list tillsammans med beskrivningen av varje nod. Du bör därefter göra om listan till en adjacency matris.

Implementationen för reader.h kan vara

reader.cpp

//
// Created by martin on 2022-03-30.
//

#include "reader.h"

#include<fstream>
#include<string>
#include<map>


enum token{
    COMMENT, META, EDGE, END_OF_FILE
};

token get_line_type(std::istream& is){
    switch(is.peek()){
        case std::istream::traits_type::eof():      return END_OF_FILE;
        case '#':                                   return COMMENT;
        case 'M':                                   return META;
    };
    return EDGE;
}

meta_t meta;

edge read_edge(std::istream& is){
    edge e;
    is >> e.n1 >> e.n2 >> e.weight;
    std::getline(is, e.description);
    return e;
}

void read_meta(std::istream& is){
    char discard;
    node_id_t vertex_id;
    std::string name;
    is >> discard >> vertex_id;
    std::getline(is, name);
    meta[vertex_id] = name;
}

adjacency_list_t parse_file(std::string filename){
    std::ifstream in(filename);
    token l;
    edge_list_t edge_list;
    while((l = get_line_type(in)) != END_OF_FILE){
        edge e;
        switch(l){
            case token::EDGE:
                e = read_edge(in);
                edge_list.push_back(e);
                break;
            case token::META:
                read_meta(in);
                break;
            default:
                std::string comment;
                std::getline(in, comment);
        }
    }
    return adjacency_list_t{meta, edge_list};
}