cfc.c

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

/*----------------------------------------------------------------------
 * sc.c
 * l-grafi version 0.1
 * Sorgente per la determinazione delle c.f.c tramite l'algoritmo
 * ricorsivo di tarjan
 *----------------------------------------------------------------------*/

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

#define UNDEFINED -1

/*Come nella dfs search settiamo questo prototimo visibile solo da questo sorgente */
void sc_recursive(int v);

dgraph_vertex_t *vertices;
int *sc_vertices, *sets_s, *sets_f;

/* Lo stack usato per generare le cfc. sp[v] da' la posizione del vertice v
 * in sc_stack[]. La cima dello stack è specificaa da tos.
 */
int *sc_stack, *sp, tos;

/* Qui vengono memorizzati i "visit numbers" usati per la determinazione
 * delle cfc 
 */
int *visit_nos, *low_link_nos;

/* unvisited[] contiene tutti i vertici che devono ancora essere visitati.
 * p[v] da la posizione del vertice v in unvisited[].
 */
int *unvisited, *p, n_unvisited;

/* Utilizziamo contatori per :
 * - il numero di vertici visitati
 * - il numero di vertici scritti nell'array vertices[]
 * - il numero delle cfc
 */

int n_visited, n_written, n_sets;



/*----------------------------------------------------------------------
 * sc_result_t *sc(dgraph_t *g, int v)
 * sc genera le cfc del grafo g e le memorizza in una struct del tipo
 * sc_result_t (vedi in.h per info)
 *----------------------------------------------------------------------*/

sc_result_t *sc(dgraph_t *g, int v)
{
    int i, n;
    sc_result_t *result;

    n = g->n;
    vertices = g->vertices;  /* i vertici a cui si accede tramite sc_recursive()*/
    /*Allochiamo lo spazio per i risultati*/
    result = malloc(sizeof(sc_result_t));
    sc_vertices = result->vertices = malloc(n * sizeof(int));
    sets_s = result->sets_s = malloc(n *sizeof(int));
    sets_f = result->sets_f = malloc(n *sizeof(int));

    /* Allochiamo lo spazio prima di generare i risultati*/
    sc_stack = malloc(n * sizeof(int));
    sp = malloc(n * sizeof(int));
    visit_nos = malloc(n * sizeof(int));
    low_link_nos = malloc(n * sizeof(int));
    unvisited = malloc(n *sizeof(int));
    p = malloc(n * sizeof(int));
    
    /* Inizializziamo i componenti dell'array a -1;
     *  - le componenti di sets_s[] e sets_f[] sono a -1
     *    fino a quando vengono scritti sopra dei dati
     *  - visit_nos[] e' a -1 fino a quando il vertice non e' stato visitato 
     *  _ sp[v] è anch'esso a -1 fino a quando v non è sullo stack
     * In piu' teniamo traccia dei vertici non visitati tramite l'array
     * unvisited[]e p[];
     */  
    for(i = 0; i < n; i++) {
	sets_s[i] = sets_f[i] = visit_nos[i] = sp[i] = UNDEFINED;
	p[i] = unvisited[i] = i;
    }

    result->size = n;
     
    /* L'algoritmo di tarjan procede compe un dfs. 
     * Si noti che la sc_recursive() è u prototipo che accede al grafo tramite
     * la variabile globale 'vertices'. Se una parte del grafo non è raggiunta
     * sc_recursive() è chiamata ancora finche tutti i vertici non sono
     * stati raggiunti
     */
    tos = 0;
    n_written = n_visited = 0;
    n_unvisited = n;
    n_sets = 0;
    do {
	v = unvisited[0];
        sc_recursive(v);
    } while(n_unvisited);
    result->n_sets = n_sets;

    free(sc_stack);
    free(sp);
    free(visit_nos);
    free(low_link_nos);
    free(unvisited);
    free(p);
    return result;
}


/*----------------------------------------------------------------------
 * void sc_recursive(int v)
 * Questa procedura è 'esplicitazione in C dell'algoritmo di tarjan.
 * il quale procede come una dfs dal vertice v nel grafo.
 * Aggiorno la truttura dei risultati tramite le variabili globali
 * sc_vertices, sets_s, sets_f
 *----------------------------------------------------------------------*/
void sc_recursive(int v)
{
    dgraph_edge_t *edge_ptr;
    int w, replace_v;

    /* Aggiungo il vertice v ai risultati e incremento il contatore dei vertici
     */
    low_link_nos[v] = visit_nos[v] = n_visited;
    n_visited++;

    /* Rimuovo il vertice visitato dall'array contenente i vertici non visitati
     */
    n_unvisited--;
    replace_v = unvisited[p[v]] = unvisited[n_unvisited];
    p[replace_v] = p[v];

    /* Metto v sullo stack */
    sc_stack[tos] = v;
    sp[v] = tos;
    tos++;
    
    /* Faccio lo stesso procedimento che con la dfs*/
    edge_ptr = vertices[v].first_edge;
    while(edge_ptr) {
        w = edge_ptr->vertex_no;
        if(visit_nos[w] == UNDEFINED) {
	    sc_recursive(w);
	    if(low_link_nos[w] < low_link_nos[v])
		low_link_nos[v] = low_link_nos[w];
	}
	else if(visit_nos[w] < visit_nos[v] && sp[w] != UNDEFINED) {
            if(visit_nos[w] < low_link_nos[v]) low_link_nos[v] = visit_nos[w];
	}
        edge_ptr = edge_ptr->next;
    }

    /* Se tutti i vertici in v , viene trovata un cfc */
    if(low_link_nos[v] == visit_nos[v]) {
	sets_s[n_sets] = n_written;
        /* I vertici della cfc sono memorizzati dalla cima dello stack 
 	 * in v. Rimuovendo questi vertici sono scritti sulla struttura
         * che rappresenta il risultato della computazione
         */
        do {
	    tos--;
            replace_v = sc_vertices[n_written] = sc_stack[tos];
	    sp[replace_v] = UNDEFINED;
	    n_written++;
	} while(replace_v != v);

	sets_f[n_sets] = n_written - 1;
	n_sets++;
    }
}

/*----------------------------------------------------------------------
 * void sc_result_free(sc_result_t *r)
 * Libera lo spazio usato dalla struttura che rappresenta una cfc
 *----------------------------------------------------------------------*/
void sc_result_free(sc_result_t *r)
{
    free(r->vertices);
    free(r->sets_s);
    free(r->sets_f);
    free(r);
}


/*----------------------------------------------------------------------
 * void sc_result_print(sc_result_t *r)
 * Stampa le cfc e gli id dei vertici contenuti
 *----------------------------------------------------------------------*/
void sc_result_print(sc_result_t *r)
{
    int i,x, j, n_sets;

    n_sets = r->n_sets;
    printf ("%d SC components\n",n_sets);
x=n_sets-1;
for(i = 0; i <n_sets; i++) {
        printf("SC%d =",i);
	for(j = r->sets_f[x-i]; j >=r->sets_s[x-i]; j--) {
        printf(" %3d", r->vertices[j]);
	}
 putchar('\n');
}
}


/*----------------------------------------------------------------------
 * int sc_connect(int s,int d,sc_result_t *r,dgraph_t *g)
 * Vede se due cfc sono realmente connesse fra di loro
 * in input vuole la cfc sorgente, quella su cui effettuare il test
 * la struttura dei risultati nella ricerca delle cfc e il grafo di
 * partenza g.In output avro' 0 se sono connesse altrimenti -1
 *----------------------------------------------------------------------*/

int sc_connect(int s,int d,sc_result_t *r,dgraph_t *g)
{
int i,x,z=0,j, n_sets,*cmp;
        n_sets = r->n_sets;
        x=n_sets-1;
        cmp=malloc( (sizeof(int)) *r->sets_f[x-s]);
        for(j = r->sets_f[x-s]; j >=r->sets_s[x-s]; j--) {
        cmp[z]=r->vertices[j];
        z++;
        }
/* HO riempito l'array con i nodi che compongono la cfc s
 * ora vedo se s è connessa a  effettuo il test suggerito dalla piazza :
Il grafo delle cfc ha:
un nodo per ogni cfc;
un arco A -> B se esistono a appartenente ad A e b appartenente a B tali
che a -> b nel grafo di partenza.

*/
for(j = r->sets_f[x-d]; j >=r->sets_s[x-d]; j--)
{
for (i=0;i<z;i++){ if (connect(g,cmp[i], r->vertices[j])==0) return 0;}
}
free(cmp);
return -1;
}

/*----------------------------------------------------------------------
 * dgraph_t * cfc_graph(int s,dgraph_t *g,sc_result_t *r)
 * Una volta che so ce una cfc è connessa ad un altra o meno posso
 * crearmi il grafo delle cfc.
 * Questo è quello che fa questa procedura richiedendo in input
 * s che è il numero delle cfc in un grafo, il grafo di partenza g
 * per effettuare i test,e la struttura dei risultati nella ricerca
 * delle cfc.
 * In output avermo il grafo delle cfc senza la chiusura transitiva-
 * riflessiva 
*----------------------------------------------------------------------*/

dgraph_t * cfc_graph(int s,dgraph_t *g,sc_result_t *r)
{
int i=0,j=0;
dgraph_t *rst;
rst=dgraph_blank(s);
for (i=0;i<s;i++)
 for (j=0;j<s;j++) if  (sc_connect(i,j,r,g)==0){add_new_edge(&rst->vertices[i],j,1 + (999));
}
return rst;
}

/*----------------------------------------------------------------------
 * dgraph_t *cfc_finish(sc_result_t *r,dgraph_t *cfc,int size)
 * Avendo la chiusura transitiva -riflessiva del  grafo delle cfc 
 * posso ritornare a quello originale
 * In input vuole la struct dei risultati nella ricerca delle cfc, il 
 * grafo della chisura transitiva-riflessiva delle cfc e la grandezza
 * del grafo originale
 * In output avremo il grafo originale con la chiusura transitiva
 * riflessiva
 *----------------------------------------------------------------------*/
 
dgraph_t *cfc_finish(sc_result_t *r,dgraph_t *cfc,int size)
{
int i,x,w,j,z;
dgraph_t *rst;
dgraph_edge_t *edge_ptr;
x=r->n_sets-1;
rst=dgraph_blank(size);
for (i=0;i<r->n_sets;i++)
{
edge_ptr=cfc->vertices[i].first_edge;
while(edge_ptr)
{
w=edge_ptr->vertex_no;
for(j = r->sets_f[x-i]; j >=r->sets_s[x-i]; j--)
{
for(z = r->sets_f[x-w]; z >=r->sets_s[x-w]; z--)
add_new_edge(&rst->vertices[r->vertices[j] ],r->vertices[z],1 + (rand() % 999));
}
edge_ptr=edge_ptr->next;
}
}
return rst;
} 

/*----------------------------------------------------------------------
 * Avendo tutto a nostra disposizione creiamo la procedura madre
 * per la chiusura transitiva riflessiva del nostro grafo passando 
 * per le cfc. Questa vuole in input solo il grafo originale e rida'
 * in output il tempo impiegato a fare il tutto.
 *----------------------------------------------------------------------*/
double cfc(dgraph_t *g)
{
double t1,t2,ret;
dgraph_t *cfc_graph_t;
sc_result_t *r;

t1=clock();
r=sc(g,0); /* ricerco le cfc del grafo g */
cfc_graph_t=cfc_graph(r->n_sets,g,r);  /* costruisco il grafo delle cfc */
/* Dal grafo delle cfc con chiusura riflessiva -transitiva mi riporto a quello
 * originale ,costruendo il grafo della chiusura transitiva -riflessiva
 * del grafo di partenza
 */
cfc_finish(r,FloydWarshall_al(cfc_graph_t),g->n);
t2=clock();
ret=TO_MSEC(t2-t1);
dgraph_free(cfc_graph_t); /*libero il grafo*/
return ret;
}