visita.c

Floyd-wharshall algoritm for the shortest path problem. I wrote this in C. It s easy to compile and

/*----------------------------------------------------------------------
 * visita.c
 * l-grafi version 0.1
 * Sorgente in cui scrivo le procedure per la visita del grafo sul
 * lavoranti su liste di adiaceza
 *--------------------------------------------------------------------*/

#include "in.h"
#include "func.h"

#define UNDEFINED -1

typedef struct bfs_queue_item {
    int vertex_no;
    struct bfs_queue_item *next;
} bfs_queue_item_t;

dfs_bfs_result_t *dfs_result;
dgraph_t *current_graph;

void dfs_recursive(int v);

/*----------------------------------------------------------------------
 * dfs_bfs_result_t *dfs(dgraph_t *g, int v)
 * Fa una visita in profondita' del grafo puntato da g
 * Input : grafo g da visitare , e il punto di starting della ricerca
 * Output : struttura di rappresentazione per il risultato (vedi in.h)
 *--------------------------------------------------------------------*/

dfs_bfs_result_t *dfs(dgraph_t *g, int v)
{
    int i, n;
    int *vertices, *parents, *visit_nos;
    n = g->n;

    /* Alloco lo spazio per i risultati*/
    dfs_result = malloc(sizeof(dfs_bfs_result_t));
    dfs_result->vertices = malloc(n * sizeof(int));
    dfs_result->parents = malloc(n *sizeof(int));
    dfs_result->visit_nos = malloc(n * sizeof(int));
    /* Inizializzo tutti gli elementi dell'array a non visitati */
    vertices = dfs_result->vertices;
    parents = dfs_result->parents;
    visit_nos = dfs_result->visit_nos;
    for(i = 0; i < n; i++) {
        vertices[i] = parents[i] = visit_nos[i] = UNDEFINED;}
    dfs_result->size = n;
    dfs_result->n = 0;
    /* Procediamo con una visita in profondita' ricorsiva. 
     * Da notare che la chiamata ricorsiva accede al grafo tramite 
     * la variabile globale current_graph.
     */
    current_graph = g;
    dfs_recursive(v);
    return dfs_result;
}

/*----------------------------------------------------------------------
 * void dfs_recursive(int v)
 * Ricorsivamente fa una visita in profondita' del vertice v nel grafo
 * Input : vertice v 
 *--------------------------------------------------------------------*/

void dfs_recursive(int v)
{
    dgraph_edge_t *edge_ptr;
    int w;

    /* Aggiungo il vertice v ai risultati e incremento il contatore per
     * il numero dei vertici nei risultati
     */

    dfs_result->vertices[dfs_result->n] = v; 
    dfs_result->visit_nos[v] = dfs_result->n++;
    edge_ptr = current_graph->vertices[v].first_edge;
    while(edge_ptr) {
        w = edge_ptr->vertex_no;
        if(dfs_result->visit_nos[w] == UNDEFINED) {
            dfs_result->parents[dfs_result->n] = v;
            dfs_recursive(w);
        }
        edge_ptr = edge_ptr->next;
    }
}

/*----------------------------------------------------------------------
 * dfs_bfs_result_t *bfs(dgraph_t *g, int v)
 * Esegue una ricerca del tipo breath first search sul grafo g dal 
 * vertice v
 *--------------------------------------------------------------------*/

dfs_bfs_result_t *bfs(dgraph_t *g, int v) {
    dfs_bfs_result_t *result;
    bfs_queue_item_t *q_head, *q_tail, *q_item;
    dgraph_edge_t *edge_ptr;
    int *vertices, *parents, *visit_nos;
    int i, c, w, n;
    n = g->n;

    result = malloc(sizeof(dfs_bfs_result_t));
    result->vertices = malloc(n * sizeof(int));
    result->parents = malloc(n *sizeof(int));
    result->visit_nos = malloc(n * sizeof(int));
    vertices = result->vertices;
    parents = result->parents;
    visit_nos = result->visit_nos;
    for(i = 0; i < n; i++) {
        vertices[i] = parents[i] = visit_nos[i] = UNDEFINED;
    }
    result->size = n;
    q_item = malloc(sizeof(bfs_queue_item_t));
    q_item->vertex_no = v;
    q_item->next = NULL;
    q_head = q_tail = q_item;
    vertices[0] = v;
    visit_nos[v] = 0;
    c = 1; 
    do {
        v = q_head->vertex_no;
        edge_ptr = g->vertices[v].first_edge;
        while(edge_ptr) {
            w = edge_ptr->vertex_no;
            if(visit_nos[w] == UNDEFINED) {
                q_item = malloc(sizeof(bfs_queue_item_t));
                q_item->vertex_no = w;
                q_item->next = NULL;
                q_tail = q_tail->next = q_item;
                parents[c] = v;
                vertices[c] = w;
             visit_nos[w] = c++;
            }
            edge_ptr = edge_ptr->next;
        }
        q_item = q_head;
        q_head = q_head->next;
        free(q_item);
    } while(q_head);
    result->n = c;
    return result;
}



/*----------------------------------------------------------------------
 * void dfs_bfs_result_free(dfs_bfs_result_t *r)
 * Libera lo spazio usato dalla struttura per la memorizzazione dei 
 * risultati della dfs/bfs (vedi in.h)
 *----------------------------------------------------------------------*/

void dfs_bfs_result_free(dfs_bfs_result_t *r)
{
    free(r->vertices);
    free(r->parents);
    free(r->visit_nos);
    free(r);
}

/*----------------------------------------------------------------------
 * dfs_bfs_result_print()
 * Stampa i risultati della dfs o bfs
 *----------------------------------------------------------------------*/

void dfs_bfs_result_print(dfs_bfs_result_t *r)
{
    int i, n;
    n = r->size;
    
    printf("parents   =");
    for(i = 0; i < n; i++) {
        if(r->parents[i] == UNDEFINED) 
           { printf("   -");}
        else {
            printf(" %3d", r->parents[i]);
        }
    }
    putchar('\n');

    printf("vertices  =");
    for(i = 0; i < n; i++) {
        if(r->vertices[i] == UNDEFINED) {
            printf("   -");
        }
        else {
            printf(" %3d", r->vertices[i]);
        }
    }
    putchar('\n');

    printf("visit_nos =");
    for(i = 0; i < n; i++) {
        if(r->visit_nos[i] == UNDEFINED) {
            printf("   -");
        }
        else {
            printf(" %3d", r->visit_nos[i]);
        }
    }
    putchar('\n');
}