LabASD - Implementazione del tipo "Grafo"

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-15

Questo file contiene alcune funzioni per gestire la rappresentazione di grafi mediante liste di adiacenza. È possibile rappresentare sia grafi orientati che non orientati, usando le strutture dati seguenti:

typedef struct Edge {
    int src;
    int dst;
    double weight;
    struct Edge *next;
} Edge;

typedef enum { GRAPH_UNDIRECTED, GRAPH_DIRECTED } Graph_type;

typedef struct {
    int n;
    int m;
    Graph_type t;
    Edge **edges;
    int *in_deg;
    int *out_deg;
} Graph;

Edge rappresenta un arco del grafo. Per grafi non orientati, ogni arco \((u,v)\) deve essere presente due volte: una come \((u,v)\) nella lista di adiacenza di \(u\), e una come \((v,u)\) nella lista di adiacenza di \(v\). Le liste sono concatenate semplici; il campo next indica l'arco successivo della lista di adiacenza, oppure NULL se è l'ultimo nodo.

La struttura Graph rappresenta l'intero grafo; la spiegazione dei vari campi è nel file graph.h. Il campo edges è un array di lunghezza \(n\) di puntatori: edges[v] punta all'inizio della lista di adiacenza del nodo \(v\), oppure NULL se \(v\) non ha archi uscenti. in_deg e out_deg sono array di lunghezza \(n\); in_deg[v] e out_deg[v] sono, rispettivamente, il grado entrante e il grado uscente di \(v\). Nel caso di grafi non orientati, si deve avere out_deg[v] == in_deg[v] per ogni \(v\), dato che ogni arco viene considerato sia entrante che uscente su entrambi gli estremi. È necessario mantenere l'informazione sui gradi entranti/uscenti durante la costruzione del grafo.

La Figura 1 mostra un esempio di rappresentazione di un grafo orientato, mentre la Figura 2 mostra un esempio di grafo non orientato; si noti che l'ordine con cui gli archi compaiono nelle liste di adiacenza non è rilevante, e dipende dall'ordine con cui sono stati inseriti nel grafo.

Figura 1: Rappresentazione di un grafo orientato
Figura 1: Rappresentazione di un grafo orientato
Figura 2: Rappresentazione di un grafo non orientato
Figura 2: Rappresentazione di un grafo non orientato

L'elenco delle funzioni con la descrizione dei parametri e del comportamento atteso è presente nel file graph.h.

Il file graph-main.c contiene una funzione main() che legge un grafo da file (o da standard input) e ne stampa il contenuto a video. È possibile usare questo programma per stampare il grado entrante/uscente dei nodi (come richiesto nei quiz di autovalutazione), invocando le funzioni graph_in_degree() oppure graph_out_degree().

Per compilare:

    gcc -std=c99 -Wall -Wpedantic graph.c graph-main.c -o graph-main

Per eseguire:

    ./graph-main < graph10.in

oppure

    ./graph-main graph10.in

Formato di input/output

Le funzioni graph_read_from_file() e graph_write_to_file() utilizzano un semplice formato testuale per rappresentare un grafo:

n m type
s[0]    d[0]    w[0]
s[1]    d[1]    w[1]
...
s[m-1]  d[m-1]  w[m-1]

dove:

File