/****************************************************************************
*
* prim.c -- Algoritmo di Jarník-Prim
*
* Copyright (C) 2021, 2022, 2024 Moreno Marzolla
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see .
*
****************************************************************************/
/***
% LabASD - Algoritmo di Jarník-Prim
% Moreno Marzolla
% Ultimo aggiornamento: 2024-01-29
![Vojtěch Jarník (1897--1970, a sinistra) e Robert Clay Prim (a destra)](Vojtech_Jarnik_Robert_Prim.jpg)
Implementare l'algoritmo di Prim per il calcolo del _Minimum Spanning
Tree_ (MST) di un grafo non orientato pesato. L'algoritmo di Prim è
stato scoperto dal matematico ceco [Vojtěch
Jarník](https://en.wikipedia.org/wiki/Vojt%C4%9Bch_Jarn%C3%ADk) nel
1930, e successivamente riscoperto da [Robert
C. Prim](https://en.wikipedia.org/wiki/Robert_C._Prim) nel 1957; per
questo è anche detto _algoritmo di Jarník-Prim_.
L'algoritmo richiede un nodo di partenza $s$, che può essere scelto
arbitrariamente se il grafo è connesso, e sfrutta una coda di priorità
che abbiamo già implementato nei file
[minheap.c](../solutions/minheap.c) e
[minheap.h](../solutions/minheap.h). Questo programma usa $s=0$ come
nodo di partenza.
Per inizializzare le distanze a $+\infty$ si usi il simbolo `HUGE_VAL`
definito in `` che rappresenta l'infinito positivo[^1].
[^1]: In realtà la documentazione afferma che
> The macros `HUGE_VAL`, `HUGE_VALF`, `HUGE_VALL` expand to
> constants of types `double`, `float` and `long double`,
> respectively, that represent a large positive value, possibly
> positive infinity.
Il simbolo `INFINITY` rappresenta il valore "infinito" su
processori che supportano lo standard
[IEEE754](https://en.wikipedia.org/wiki/IEEE_754), ma purtroppo
è definito solo da C99 in poi. `INFINITY` non è semplicemente
"un valore grande": ad esempio, lo standard IEEE754 impone che
se $x$ è un qualunque valore positivo finito, allora `INFINITY +
x == INFINITY`, mentre `HUGE_VAL + x` potrebbe causare
overflow. I compilatori che ho a disposizione _sembrano_
definire `HUGE_VAL` come `INFINITY`, ma non è garantito che sia
sempre così.
Il programma legge il grafo da un file il cui nome viene passato sulla
riga di comando, e stampa a video l'elenco degli archi che fanno parte
del MST. Il formato dell'input è lo stesso utilizzato dal tipo di
dato [grafo](graph.html):
```
n m 0
s[0] d[0] w[0]
s[1] d[1] w[1]
...
s[m-1] d[m-1] w[m-1]
```
dove:
- `n` è il numero di nodi del grafo; i nodi sono rappresentati dagli
interi $0, \ldots, (n-1)$;
- `m` è il numero di archi del grafo
- `0` indica che il grafo è non orientato
- `s, d, w` sono rispettivamente il nodo sorgente, il nodo destinazione,
e il peso di ciascun arco. I pesi sono valori reali.
Il programma stampa l'elenco degli archi che fanno parte del MST,
nello stesso formato dell'input. È quindi possibile usare l'output
come input al programma stesso.
Per compilare:
gcc -std=c90 -Wall -Wpedantic graph.c minheap.c prim.c -o prim
Per eseguire:
./prim graph10.in
## Domande
- Dato un grafo non orientato pesato e connesso con $n$ nodi e $m$
archi, qual è il numero massimo di archi che può far parte di un
MST?
- Cosa succede se applichiamo l'algoritmo di Prim ad un grafo
non connesso?
## File
- [prim.c](prim.c)
- [minheap.c](../solutions/minheap.c)
- [minheap.h](../solutions/minheap.h)
- [graph.c](../solutions/graph.c)
- [graph.h](../solutions/graph.h)
- [mst10.in](mst10.in) ([output atteso](mst10-prim.out))
- [mst100.in](mst100.in) ([output atteso](mst100-prim.out))
- [mst1000.in](mst1000.in)
- [mst1500.in](mst1500.in)
- [mst2000.in](mst2000.in)
***/
#include
#include
#include
#include
#include
#include "minheap.h"
#include "graph.h"
/* Calcola il MST usando l'algoritmo di Prim.
Parametri:
- `g`: grafo di cui calcolare il MST. Se il grafo non è connesso,
questa funzione calcola il MST della componente connessa di cui
fa parte il nodo `s`.
- `s`: nodo da cui fare iniziare l'algoritmo di Prim; se il grafo è
connesso, `s` può essere scelto in modo arbitrario.
- `mst[v]` è un puntatore all'arco in ingresso a `v` lungo il
cammino dalla sorgente a `v`; si noti che il grafo `g` è non
orientato, quindi la "direzione" deriva solo dalla scelta del
nodo sorgente. `mst[]` è un array di `n` puntatori ad arco che
deve essere allocato dal chiamante
Risultato:
- peso complessivo dell'albero.
*/
double prim( const Graph *g, int s, const Edge **mst )
{
const int n = graph_n_nodes(g);
/* d[v] è il minimo tra i pesi degli archi incidenti che collegano
v con un nodo già raggiunto dal MST */
double *d = (double*)malloc(n * sizeof(*d));
/* added[v] == 1 se e solo se il nodo v è già stato aggiunto al
MST, quindi non va più considerato in futuro */
char *added = (char*)malloc(n * sizeof(*added));
/* p[v] è il "predecessore" di v nello spanning tree che stiamo
costruendo. Il predecessore è definito come il nodo che viene
prima di v nel cammino dalla sorgente s. Si noti che non
facciamo alcun uso di questo array, nel senso che lo calcoliamo
per mostrare come si fa, ma non viene utilizzato nel resto del
programma. */
int *p = (int*)malloc(n * sizeof(*p));
MinHeap *q = minheap_create(n);
double wtot = 0.0;
int i;
assert(d != NULL);
assert(added != NULL);
assert(p != NULL);
assert( (s>=0) && (snext) {
const double w = edge->weight;
const int v = edge->dst;
if (!added[v] && (w < d[v])) {
d[v] = w;
p[v] = u;
mst[v] = edge;
minheap_change_prio(q, v, d[v]);
}
}
}
minheap_destroy(q);
free(added);
free(d);
free(p);
return wtot;
}
/* Stampa a video l'elenco degli archi del MST nello stesso formato
usato per il grafo di input. */
void print_mst( const Graph *g, const Edge **mst )
{
const int n = graph_n_nodes(g);
int nmst = 0; /* numero di archi che fanno parte del MST */
int v;
assert(mst != NULL);
/* Contiamo gli archi che fanno parte del MST */
for (v=0; vsrc, e->dst, e->weight);
}
}
}
int main( int argc, char *argv[] )
{
Graph *G;
const Edge **mst = NULL; /* mst[v] è il puntatore all'arco che collega v con il suo predecessore nel MST */
double wtot = 0.0; /* peso totale del MST */
FILE *filein = stdin;
int n;
if (argc != 2) {
fprintf(stderr, "Usage: %s filename\n", argv[0]);
return EXIT_FAILURE;
}
if (strcmp(argv[1], "-") != 0) {
filein = fopen(argv[1], "r");
if (filein == NULL) {
fprintf(stderr, "Can not open %s\n", argv[1]);
return EXIT_FAILURE;
}
}
G = graph_read_from_file(filein);
if (graph_type(G) != GRAPH_UNDIRECTED) {
fprintf(stderr, "ERRORE: Questo programma richiede grafi non orientati\n");
return EXIT_FAILURE;
}
n = graph_n_nodes(G);
mst = (const Edge**)malloc(n * sizeof(*mst)); assert(mst != NULL);
wtot = prim(G, 0, mst);
print_mst(G, mst);
printf("# MST weight = %f\n", wtot);
graph_destroy(G);
free(mst);
if (filein != stdin) fclose(filein);
return EXIT_SUCCESS;
}