graph.c

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

/*----------------------------------------------------------------------
 * graph.c
 * l-grafi version 0.1
 * Sorgente in cui realizzo le procedure per lavorare con i grafi
 *--------------------------------------------------------------------*/

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

#define UNDEFINED -1

const int MaxEdgeCost = 100000000;
const int MinEdgeCost = 1;

/* Partiremo sempre dal vertice StartVertex per memorizzare qualcosa in un grafo */
const int StartVertex = 0;

/*--------------------------------------------------------------------
 * dgraph_t *dgraph_blank(int n)
 * Crea un grafo senza archi di dimensione n
 * Input : il numero di nodi
 * Output : il grafo
 *--------------------------------------------------------------------*/

dgraph_t *dgraph_blank(int n)
{
    dgraph_t *g;
    dgraph_vertex_t *vertices;
    int i;
    g = malloc(sizeof(dgraph_t));
    vertices = g->vertices = malloc(n*sizeof(dgraph_vertex_t));
    g->n = n;
    for(i = 0; i < n; i++) {
        vertices[i].first_edge = vertices[i].last_edge = NULL;
    }
    return g;
}

/* dgraph_rnd_dense() - creates a directed random graph with all vertices
 * reachable from the starting vertex.  Parameter n is the size of the graph,
 * and parameter prob is the probability of edge existence.
 * Returns a pointer to the random graph created.
 */
dgraph_t *dgraph_rnd_dense(int n, double prob)
{
    int i, j, k, m;
    int *c, *size;
    int *sources;
    double x;
    int costDiff;
    dgraph_t *g;
    dgraph_vertex_t *vertex, *vertices;

    /* Allocate space for the graph. */
    g = malloc(sizeof(dgraph_t));
    g->vertices = malloc(n*sizeof(dgraph_vertex_t));
    g->n = n;

    /* Allocate space for temporary arrays. */
    c = malloc(n * sizeof(int));
    size = malloc(n * sizeof(int));
    sources = malloc(n * sizeof(int));

    /* Initialise variables and arrays. */
    costDiff = (MaxEdgeCost - MinEdgeCost);
    vertices = g->vertices;
    for(i = 0; i < n; i++) {
        vertices[i].first_edge = NULL;
        vertices[i].last_edge = NULL;
        
        c[i] = i;
        size[i] = 1;
        sources[i] = UNDEFINED;
    }

    /* For each vertex, except the starting vertex, set up one random edge
     * pointing to it.  We do not set up a random edge pointing to the starting
     * vertex, that is, vertex number 0.
     */
    for(j = 1; j < n; j++) {

        /* Choose one of the available 'from' verticies at random. */
        k = rand() % (n - size[j]);

        /* Find the unused vertex, i, that corresponds to k, and record the
         * connection in the array sources[].
         */
        i = -1; m = -1;
        while(m < k) {
            i++;
            if(c[i] != c[j]) m++;
        }
        sources[j] = i;

        /* In order to avoid creating cycles in the sub-graph, we update the
         * array c[] to keep track of the connected parts in the sub-graph.
         * Do this by updating all verticies with connection number c[i] to
         * have connection number c[j].
         */
        m = c[i];
        for(k = 0; k < n; k++) {
            if(c[k] == m) {
                c[k] = c[j];
                size[k] += size[j];
            }
        }
    }

    /* We are done with using c[] and size[]. */
    free(c);
    free(size);

    /* We note that we must change the probability of edge existence slightly
     * since n-1 edges have already been determined.
     */
    prob = (prob*n - 1) / (n - 1);

    /* Create the random graph.  Edges from vertex i to vertex j.
     * Variable k keeps track of the number of vertices in the out set
     * of the current vertex.
     */
    for(i = 0; i < n; i++) {
        
        vertex = &vertices[i];

        for(j = 0; j < n; j++) {

            /* Only create edges that are not from a vertex to itself.
             */
            if (i != j) {
                
                /* Create and edge from vertex i to vertex j with probability
                 * prob.  All edges in the connecting sub-graph are created.
                 */
                x = (double) rand() / RAND_MAX;
                if (x <= prob || sources[j] == i) {
                    add_new_edge(vertex, j, MinEdgeCost + (rand() % costDiff));
                   add_new_edge(vertex, j, MinEdgeCost + (rand() % costDiff));
                }
            }
        }
    }

    /* We are done with using sources[]. */
    free(sources);

    return g;
}

/*-------------------------------------------------------------------
 * void dgraph_free(dgraph_t *g)
 * Libero lo spazio dalla memoria occupato dalla struttura dgraph_t
 *-------------------------------------------------------------------*/

void dgraph_free(dgraph_t *g)
{
    int i, n;
    dgraph_vertex_t *vertices;
    dgraph_edge_t *edge_ptr, *next_edge_ptr;
    n = g->n;
    vertices = g->vertices;
    
    for(i = 0; i < g->n; i++) {
        edge_ptr = vertices[i].first_edge;
        while(edge_ptr) {
            next_edge_ptr = edge_ptr->next;
            free(edge_ptr);
            edge_ptr = next_edge_ptr;
        }
    }
    free(vertices);
    free(g);
}

/*-------------------------------------------------------------------
 * void add_new_edge(dgraph_vertex_t *vertex, int dest_vertex_no, long dist)
 * Aggiunge un nuovo nodo alla lista dei nodi del vertice puntato da
 * 'vertex'. 
 * Input : il vertice puntato, il numero del nodo da connettere, la distanza
 *-------------------------------------------------------------------*/

void add_new_edge(dgraph_vertex_t *vertex, int dest_vertex_no, long dist)
{
    dgraph_edge_t *new_edge, *last_edge;
    
    new_edge = malloc(sizeof(dgraph_edge_t));
    new_edge->vertex_no = dest_vertex_no;
    new_edge->dist = dist;
    new_edge->next = NULL;
    if((last_edge = vertex->last_edge)) {
        last_edge->next = new_edge;
    }
    else {
        vertex->first_edge = new_edge;
    }
    vertex->last_edge = new_edge;       
}

/*-------------------------------------------------------------------
 * dgraph_t * add_al_from_vertex_to_vertex (dgraph_t *g,int s, int d)
 * Aggiunge ad un nodo la lista di adiacenza di un altro nodo 
 * con tutti i suoi figli.
 * input : grafo, indice del nodo di sorgente,indice del nodo da aggiungere
 * output : grafo
 *-------------------------------------------------------------------*/

dgraph_t * add_al_from_vertex_to_vertex (dgraph_t *g,int s, int d)
{
int b;
dgraph_edge_t *edge_ptr,*edge_ptr2;
edge_ptr= g->vertices[d].first_edge;
while (edge_ptr)
{
b=0;
b=edge_ptr->vertex_no;
if ((al_edge_present_test(g->vertices[s].first_edge,b))==0)
add_new_edge(&g->vertices[s],b,1 + (rand() % 999));
edge_ptr=edge_ptr->next;
}
return g;
}

/*-------------------------------------------------------------------
 * int al_edge_present_test(dgraph_edge_t *edge_ptr,int vertex_no)
 * Fa un test se a un nodo e' connesso o meno un dato  figlio
 *-------------------------------------------------------------------*/
int al_edge_present_test(dgraph_edge_t *edge_ptr,int vertex_no)
{
while (edge_ptr)
{
if (edge_ptr->vertex_no==vertex_no) return -1;
edge_ptr=edge_ptr->next;
}
return 0;
}


/*-------------------------------------------------------------------
 * void al_show (dgraph_t *g)
 * Stampa il grafo rappresentato tramite liste di adiacenza
 *-------------------------------------------------------------------*/

void al_show (dgraph_t *g)
{
dgraph_edge_t *edge_ptr,*nex_edge_ptr;
int i,n,k;

 for (i=0;i<g->n;i++){
 edge_ptr=g->vertices[i].first_edge;
 printf ("[%d]",i);
 while(edge_ptr){
 printf ("->%d",edge_ptr->vertex_no);
 edge_ptr=edge_ptr->next; 
 } //while
 printf ("\n");
 } // For
}