Esercizi e sorgenti dei programmi

Libreria di funzioni C per programmi su grafi

La libreria C "grafi.c" presenta un insieme di strutture dati e di funzioni per l'implementazione di algoritmi per la risoluzione di problemi su grafi, alberi e reti. In particolare nel seguito sono implementati i seguenti elementi:

Strutture che definiscono nuovi tipi di dati

elementoLista: È una struttura composta da un numero intero (campo info) ed un puntatore ad una struttura elementoLista. È utile per la definizione di strutture che costituiscono gli elementi di una lista puntata per memorizzare sequenze di numeri interi (es.: le etichette dei vertici di un grafo presenti in una lista di adiacenza).
coda: È una struttura composta da due puntatori a strutture elementoLista. I due puntatori primo e ultimo servono rispettivamente per puntare al primo e all'ultimo elemento di una lista che rappresenta una coda (struttura FIFO - first in first out).
grafo: È una struttura composta da un numero intero n ed un puntatore al primo elemento di un vettore di puntatori a strutture di tipo elementoLista. È utile per la definizione di una struttura unica per la rappresentazione di un grafo mediante liste di adiacenza; n è il numero di vertici del grafo.

Funzioni di libreria per la manipolazione di liste

impila: Funzione che aggiunge come primo elemento di una lista un nuovo elemento passato come argomento. In questo modo gli elementi sono aggiunti alla lista come in una pila (struttura di tipo LIFO - last in first out).
push: È una funzione che consente di aggiungere come ultimo elemento di una coda un nuovo elemento.
pop: È una funzione che consente di estrarre (ed eliminare dalla lista) il primo elemento di una coda.
leggiLista: È una funzione che consente di acquisire in input una sequenza di numeri interi e di memorizzarli come elementi di una lista gestita come una pila (LIFO); questa funzione è utile per acquisire in input gli elementi della lista di adiacenza di un vertice di un grafo.
stampaLista: È una funzione che consente di stampare su standard output i valori interi degli elementi di una lista.

Funzioni di libreria per la gestione di grafi

leggiGrafo: È una funzione che consente di acquisire in input (tramite la funzione leggiLista) le n liste di adiacenza di un grafo.
leggiGrafoPesato: È una funzione che consente di acquisire in input (tramite la funzione leggiLista) le n liste di adiacenza di un grafo di tipo “grafoPesato” e la matrice dei pesi W(i,j) associati agli spigoli del grafo (W(i,j)=0 se i=j, W(i,j)=∞ se (i,j) ∉ E(G)).
stampaGrafo: È una funzione che consente di stampare su standard output (tramite la funzione stampaLista) le liste di adiacenza di un grafo.
salvaGrafo: Funzione che scrive su file le liste di adiacenza degli n vertici del grafo. Ogni lista è indirizzata da un elemento dell'array puntato da G.V.
salvaListeGrafo: Funzione che scrive su file le liste di adiacenza degli n vertici del grafo in un formato compatibile con la funzione “FromAdjacencyLists” del software Mathematica. Ogni lista è indirizzata da un elemento dell'array puntato da G.V.
addEdge: Aggiunge lo spigolo (u,v) inserendo l'elemento v nella lista di adiacenza di u. Restituisce 1 se u non esiste, restituisce 2 se v non esiste restituisce 3 se (u,v) già esiste; restituisce 0 se lo spigolo viene aggiunto con successo.
removeEdge: Elimina lo spigolo (u,v) dal grafo rimuovendo l'elemento v dalla lista di adiacenza di u. Restituisce 1 se lo spigolo (u,v) non esiste; restituisce 0 altrimenti, in caso di successo.
completeGraph: Costruisce il grafo completo K_n con n vertici.
emptyGraph: Costruisce il grafo nullo n vertici.
cycleGraph: Costruisce il grafo C_n, costituito da un ciclo semplice con n vertici.
randomGraph: Costruisce un grafo non orientato random con n vertici; ogni spigolo (u,v) esiste con probabilità 0 ≤ p ≤ 1.
grafoTrasposto: Costruisce le liste di adiacenza del grafo G^T trasposto del grafo orientato G, ossia il grafo con il verso degli spigoli invertito.
sortTopologico: Restituisce il puntatore al primo elemento di una lista contenente i vertici del grafo disposti in ordine topologico (se (u,v) ∈ E(G) allora u<v).
linkGrafoToGrafoPesato: Crea un grafo di tipo “grafo” con la lista di adiacenza che punta a quella di un altro grafo di tipo “grafoPesato”.

Header file: grafi.h

/*
**  grafi.h
**
**  Header file della libreria di funzioni utili per la gestione di grafi, 
**  alberi e liste.
**
**  #(@)20081108(liverani@mat.uniroma3.it)
**  #(@)20120429(liverani@mat.uniroma3.it)
*/

#define INFINITO INT_MAX/2


/*
 *  elementoLista
 *
 *  tipo di dato per gli elementi di una lista concatenata
 */

typedef struct nodo {
  int info;
  struct nodo *next;
} elementoLista;


/*
 *  coda
 *
 *  tipo di dato per indirizzare gli elementi di una coda: contiene
 *  un puntatore al primo elemento ed uno all'ultimo elemento della coda.
 */

typedef struct scoda {
  elementoLista *primo;
  elementoLista *ultimo;
} coda;


/*
 *  grafo
 *  
 *  tipo di dato per indirizzare l'array delle liste di adiacenza con
 *  cui viene definito un grafo.
 */

typedef struct sgrafo {
  int n;
  elementoLista **V;
} grafo;


/*
 *  grafoPesato
 *
 *  tipo di dato per la rappresentazione di grafi con pesi associati
 *  agli spigoli.
 */
typedef struct sgrafoPesato {
  int n;
  elementoLista **V;
  int **W;
} grafoPesato;

/*
 *  Prototipi delle funzioni definite in "grafi.c".
 */
 
void debug(char s[100]);

elementoLista *impila(elementoLista *p, int x);

void push(coda *pQ, int x);

int pop(coda *pQ);

elementoLista *invertiLista(elementoLista *p);

elementoLista *leggiLista(void);

void stampaLista(elementoLista *p);

int leggiGrafo(grafo *pG);

int leggiGrafoPesato(grafoPesato *pG);

void stampaGrafo(grafo G);

void salvaGrafo(grafo G);

void salvaListeGrafo(grafo G);

int addEdge(grafo *pG, int u, int v);

int removeEdge(grafo *pG, int u, int v);

int completeGraph(grafo *pG, int n);

int emptyGraph(grafo *pG, int n);

int cycleGraph(grafo *pG, int n);

int randomGraph(grafo *pG, int n, float p);

void grafoTrasposto(grafo G, grafo *pGT);

elementoLista * sortTopologico(grafo G);

void linkGrafoToGrafoPesato(grafo *pG1, grafoPesato *pG2);

Libreria di funzioni: grafi.c

/*
**  grafi.c
**
**  Libreria di funzioni utili per la gestione di grafi, alberi e liste.
**
**  #(@)20081228(liverani@mat.uniroma3.it)
**  #(@)20120429(liverani@mat.uniroma3.it)
*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>
#include "grafi.h"

/*
 * debug
 *
 *  Visualizza una stringa su "standard error" se la libreria e'
 *  stata compilata in modalita' di debug (con l'opzione "-DDEBUG")
 */

void debug(char s[100]) {
#ifdef DEBUG
  fprintf(stderr, "***\n*** %s\n***\n", s);
  fflush(stderr);
#endif
  return;
}


/*
 *  impila
 *
 *  Inserisce all'inizio della lista p un nuovo elementoLista.
 *  Restituisce l'indirizzo del nuovo primo elemento della lista.
 */
elementoLista *impila(elementoLista *p, int x) {
  elementoLista *q;
  q = malloc(sizeof(elementoLista));
  q->info = x;
  q->next = p;
  p = q;
  return(p);
}


/*
 *  leggiLista
 *
 *  Legge in input da stdin una sequenza di n elementi interi e li
 *  memorizza, come una pila, in una lista concatenata di elementi
 *  di tipo elementoLista.
 *  Restituisce l'indirizzo del primo elemento della lista.
 */
elementoLista *leggiLista(void) {
  int i, n, x;
  elementoLista *primo = NULL;
  printf("Numero di elementi: ");
  scanf("%d", &n);
  printf("Inserisci %d elementi: ", n);
  for (i=0; i<n; i++) {
    scanf("%d", &x);
    primo = impila(primo, x);
  }
  return(primo);
}


/*
 *  push(&Q, x) 
 *
 *  Accoda l'elemento x nella coda Q
 */
void push(coda *pQ, int x) {
  elementoLista *p;
  p = malloc(sizeof(elementoLista));
  p->info = x;
  p->next = NULL;
  if (pQ->ultimo == NULL){
    pQ->ultimo = p;
    pQ->primo = p;
  }  else {
    pQ->ultimo->next = p;
    pQ->ultimo = p;
  }
  return;
}


/*
 *  pop(&Q)
 *
 *  Estrae dalla coda Q il primo elemento. Q non deve essere vuota.
 *
 */
int pop(coda *pQ) {
  int x;
  elementoLista *p;
  x = pQ->primo->info;
  if (pQ->primo->next == NULL) {
    free(pQ->primo);
    pQ->primo = NULL;
    pQ->ultimo = NULL;
  } else {
    p = pQ->primo;
    pQ->primo = pQ->primo->next;
    free(p);
  }
  return(x);
}


/*
 *  stampaLista(p)
 *
 *  Stampa su stdout la lista di elementi di tipo elementoLista a partire
 *  dall'elemento puntato da p.
 */
void stampaLista(elementoLista *p) {
  while (p != NULL) {
    printf("%d --> ", p->info);
    p = p->next;
  }
  printf("NULL\n");
  return;
}


/*
 *  invertiLista(p)
 *
 *  Inverte l'ordine degli elementi presenti in una lista in cui il primo
 *  elemento e' puntato da p (funzione ricorsiva).
 */
elementoLista *invertiLista(elementoLista *p) {
  elementoLista *q = NULL;
  if (p != NULL && p->next != NULL) {
    q = invertiLista(p->next);
    p->next->next = p;
    p->next = NULL;
  } else {
    q = p;
  }
  return(q);
}


/*
 *  leggiGrafo(G)
 *
 *  Legge in input da stdin il numero di vertici di cui e' composto il grafo,
 *  definisce un vettore di n puntatori a elementi di tipo elementoLista per 
 *  indirizzare le liste di adiacenza di ciascun nodo del grafo; legge in input
 *  da stdin n liste di adiacenza e le fa puntare dagli elementi del vettore.
 *  Restituisce il numero di elementi del grafo. Accetta come argomento l'indirizzo
 *  di memoria di un puntatore a cui assegna l'indirizzo del vettore allocato
 *  nella funzione.
 */
int leggiGrafo(grafo *pG) {
  int i, n;
  printf("Numero di vertici: ");
  scanf("%d", &n);
  pG->n = n;
  pG->V = malloc((n+1)*sizeof(elementoLista *));
  for (i=1; i<=n; i++) {
    printf("Lista di adiacenza del vertice %d.\n", i);
    pG->V[i] = leggiLista();
  }
  return(n);
}


/*
 *  leggiGrafoPesato(G)
 *
 *  Legge in input le liste di adiacenza del grafo pesato e i pesi associati
 *  ad ogni spigolo.
 */
int leggiGrafoPesato(grafoPesato *pG) {
  int i, j, n;
  elementoLista *p;
  printf("Numero di vertici: ");
  scanf("%d", &n);
  pG->n = n;
  pG->V = malloc((n+1)*sizeof(elementoLista *));
  pG->W = malloc((n+1)*(n+1)*sizeof(int *));
  for (i=1; i<=n; i++)
    pG->W[i] = malloc((n+1)*sizeof(int));
  for (i=1; i<=n; i++) {
    for (j=1; j<=n; j++) 
      if (i==j)
        pG->W[i][j] = 0;
      else
        pG->W[i][j] = INFINITO;
    printf("Lista di adiacenza del vertice %d.\n", i);
    pG->V[i] = leggiLista();
    p = pG->V[i];
    while (p != NULL) {
      printf("Peso dello spigolo (%d,%d): ", i, p->info);
      scanf("%d", &pG->W[i][p->info]);
      p = p->next;
    }
  }
  return(n);
}


/*
 *  stampaGrafo(G, n)
 *
 *  Stampa su stdout le liste di adiacenza degli n vertici del grafo. Ogni
 *  lista e' indirizzata da un elemento dell'array puntato da G.
 */
void stampaGrafo(grafo G) {
  int i;
  for (i=1; i<=G.n; i++) {
    printf("%3d: ", i);
    stampaLista(G.V[i]);
  }
  return;
}


/*
 *  salvaGrafo(G)
 *
 *  Scrive su file le liste di adiacenza degli n vertici del grafo. Ogni
 *  lista e' indirizzata da un elemento dell'array puntato da G.
 */
void salvaGrafo(grafo G) {
  int i;
  FILE *out;
  elementoLista *p;
  char nome[100];
  printf("Nome del file: ");
  scanf("%s", nome);
  out = fopen(nome, "w+t");
  if (out != NULL) {
    for (i=1; i<=G.n; i++) {
      p = G.V[i];
      while (p != NULL) {
        fprintf(out, "%d ", p->info);
        p = p->next;
      }
      fprintf(out, "\n");
    }
    fclose(out);
  } else {
    fprintf(stderr, "ERRORE: impossibile scrivere sul file '%s'.\n\n", nome);
  }
  return;
}


/*
 *      salvaListeGrafo(G)
 *
 *      Scrive su file le liste di adiacenza degli n vertici del grafo nel
 *      formato compabile con Mathematica. Ogni lista e' indirizzata da un
 *      elemento dell'array puntato da G.
 */
void salvaListeGrafo(grafo G) {
  int i;
  FILE *out;
  elementoLista *p;
  char nome[100];
  printf("Nome del file: ");
  scanf("%s", nome);
  out = fopen(nome, "w+t");
  if (out != NULL) {
    fprintf(out, "{");
    for (i=1; i<=G.n; i++) {
      p = G.V[i];
      fprintf(out, "{");
      while (p != NULL) {
        fprintf(out, "%d", p->info);
        p = p->next;
        if (p != NULL) 
          fprintf(out, ",");
      }
      fprintf(out, "}");
      if (i<G.n)
        fprintf(out, ", ");
    }
    fprintf(out, "}\n");
    fclose(out);
  } else {
    fprintf(stderr, "ERRORE: impossibile scrivere sul file '%s'.\n\n", nome);
  }
  return;
}



/*
 *  addEdge(pG, u, v)
 *
 *  Aggiunge lo spigolo (u,v) inserendo l'elemento v nella lista di adiacenza
 *  di u. Restituisce 1 se u non esiste, restituisce 2 se v non esiste, 
 *  restituisce 3 se (u,v) gia' esiste; restituisce 0 se lo spigolo viene
 *  aggiunto con successo.
 */
int addEdge(grafo *pG, int u, int v) {
  int rc = 0;
  elementoLista *p;
  
  if (u > pG->n)
    rc = 1;
  if (v > pG->n)
    rc = 2;
  if (rc == 0) {
    p = pG->V[u];
    while (p != NULL && rc == 0) {
      if (p->info == v)
        rc = 3;
      p = p->next;
    }
    if (rc == 0) {
      p = malloc(sizeof(elementoLista));
      p->info = v;
      p->next = pG->V[u];
      pG->V[u] = p;
    }
  }
  return(rc);
}


/*
 *  removeEdge(pG, u, v)
 *
 *  Elimina lo spigolo (u,v) dal grafo rimuovendo l'elemento v dalla
 *  lista di adiacenza di u. Restituisce 1 se lo spigolo (u,v) non esiste;
 *  restituisce 0 altrimenti, in caso di successo.
 */
int removeEdge(grafo *pG, int u, int v) {
  int rc = 0;
  elementoLista *p, *q;
  
  if (u > pG->n || v > pG->n || pG->V[u] == NULL) {
    rc = 1;
  } else {
    p = pG->V[u];
    if (p->info == v) {
      pG->V[u] = p->next;
    } else {
      q = p;
      p = p->next;
      while (p != NULL) {
        if (p->info == v) {
          q->next = p->next;
          p = NULL;
        } else {
          q = p;
          p = p->next;
        }
      }
    }
  }
  return(rc);
}


/*
 *  completeGraph(pG, n)
 *
 *  Costruisce il grafo completo K_n con n vertici.
 */
int completeGraph(grafo *pG, int n) {
  int i, j;

  pG->n = n;
  pG->V = malloc((n+1)*sizeof(elementoLista *));
  for (i=1; i<=n; i++) {
    pG->V[i] = NULL;
    for (j=1; j<=n; j++) {
      if (i != j)
        addEdge(pG, i, j);
    }
  }
  return(n);
}


/*
 *  emptyGraph(pG, n)
 *
 *  Costruisce il grafo nullo n vertici.
 */
int emptyGraph(grafo *pG, int n) {
  int i;

  pG->n = n;
  pG->V = malloc((n+1)*sizeof(elementoLista *));
  for (i=1; i<=n; i++)
    pG->V[i] = NULL;
  return(n);
}


/*
 *  cycleGraph(pG, n)
 *
 *  Costruisce il grafo Cn costituito da un ciclo con n vertici.
 */
int cycleGraph(grafo *pG, int n) {
  int i;

  pG->n = n;
  pG->V = malloc((n+1)*sizeof(elementoLista *));
  for (i=1; i<=n; i++)
    pG->V[i] = NULL;
  for (i=1; i<n; i++) {
    addEdge(pG, i, i+1);
    addEdge(pG, i+1, i);
  }
  addEdge(pG, n, 1);
  addEdge(pG, 1, n);
  return(n);
}


/*
 *  randomGraph(pG, n, p)
 *
 *  Costruisce un grafo non orientato random con n vertici; ogni spigolo (u,v)
 *  esiste con probabilita' 0 <= p <= 1.
 */
int randomGraph(grafo *pG, int n, float p) {
  int i, j;

  srand((unsigned) time(NULL));
  pG->n = n;
  pG->V = malloc((n+1)*sizeof(elementoLista *));
  for (i=1; i<=n; i++)
    pG->V[i] = NULL;
  for (i=1; i<n; i++) {
    for (j=i+1; j<=n; j++) {
      if ((float)(rand() % 100)/100.0 < p) {
        addEdge(pG, i, j);
        addEdge(pG, j, i);
      }
    }
  }
  return(n);
}


/*
 *  grafoTrasposto(G, pGT)
 *  
 *  Crea il grafo puntato da pGT con gli stessi vertici di G, ma gli spigoli
 *  orientati al contrario.
 */
void grafoTrasposto(grafo G, grafo *pGT) {
  int i;
  elementoLista *p, *q;
  pGT->n = G.n;
  pGT->V = malloc((G.n+1)*sizeof(elementoLista *));
  for (i=1; i<=G.n; i++) {
    pGT->V[i] = NULL;
  }
  for (i=1; i<=G.n; i++) {
    p = G.V[i];
    while (p != NULL) {
      q = malloc(sizeof(elementoLista));
      q->info = i;
      q->next = pGT->V[p->info];
      pGT->V[p->info] = q;
      p = p->next;
    }
  }
  return;
}


/*
 *  sortTopologico(G)
 *
 *  Esegue l'ordinamento topologico del grafo orientato aciclico G
 *  e restituisce il puntatore al primo elemento di una lista con 
 *  i vertici di G in ordine topologico.
 */
elementoLista * sortTopologico(grafo G) {
  int *eliminato, flag, i, j;
  grafo GT;
  coda Q;
  Q.primo = NULL;
  Q.ultimo = NULL;
  eliminato = malloc(sizeof(int)*(G.n + 1));
  for (i=1; i<=G.n; i++) 
    eliminato[i] = 0;
  grafoTrasposto(G, &GT);
  flag = 1;
  while (flag != 0) {
    flag=0;
    for (i=1; i <= GT.n; i++) {
      if (!eliminato[i] && GT.V[i] == NULL) {
        flag=1;
        push(&Q, i);
        eliminato[i] = 1;
        for (j=1; j<=GT.n; j++) {
          removeEdge(&GT, j, i);
        }
      }
    }
  }
  return(Q.primo);
}


/*
 *  linkGrafoToGrafoPesato
 *
 *  Crea un grafo di tipo "grafo" con la lista di adiacenza che punta a
 *  quella di un altro grafo di tipo "grafoPesato".
 */

void linkGrafoToGrafoPesato(grafo *pG1, grafoPesato *pG2){
  pG1->n = pG2->n;
  pG1->V = pG2->V;
  return;
}

Un programma di esempio: esempio.c

#include <stdlib.h>
#include <stdio.h>
#include "grafi.h"

int main(void) {
  grafo G;
  int n;
        
  n = leggiGrafo(&G);
  salvaGrafo(G);
  stampaGrafo(G);
  return(0);
}

Compilazione ed esecuzione

Compilazione della libreria grafi.c. Viene generata la libreria in formato oggetto grafi.o; la libreria dovrà essere collegata (link) al programma in fase di compilazione e linking.

$ gcc -c grafi.c -Wall

Per visualizzare i messaggi prodotti dalla funzione debug definita nella libreria grafi.c è necessario aggiungere l'opzione "-DDEBUG" sulla linea di comando, per definire (opzione "-D") il simbolo DEBUG utile al precompilatore per includere o escludere il corpo della funzione debug dal sorgente da compilare per produrre il file eseguibile.

$ gcc -c grafi.c -DDEBUG -Wall

Compilazione del programma esempio.c e collegamento della libreria grafi.o. Viene prodotto il file esempio in formato binario eseguibile.

$ gcc esempio.c grafi.o -o esempio -Wall

Esecuzione del programma esempio dislocato nella directory corrente.

$ ./esempio

Corso di Ottimizzazione Combinatoria (IN440)