misc.c

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

/*----------------------------------------------------------------------
 * Misc.c
 * l-grafi version 0.1
 * Varie procedure di utilita'
 *---------------------------------------------------------------------*/

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

/*---------------------------------------------------------------------
 *---------------------------------------------------------------------*/

static unsigned int SEED = 93186752;


double random_lup ()
{
/* The following parameters are recommended settings based on research
   uncomment the one you want. */


   static unsigned int a = 1588635695, m = 4294967291U, q = 2, r = 1117695901;
/* static unsigned int a = 1223106847, m = 4294967291U, q = 3, r = 625646750;*/
/* static unsigned int a = 279470273, m = 4294967291U, q = 15, r = 102913196;*/
/* static unsigned int a = 1583458089, m = 2147483647, q = 1, r = 564025558; */
/* static unsigned int a = 784588716, m = 2147483647, q = 2, r = 578306215;  */
/* static unsigned int a = 16807, m = 2147483647, q = 127773, r = 2836;      */
/* static unsigned int a = 950706376, m = 2147483647, q = 2, r = 246070895;  */

   SEED = a*(SEED % q) - r*(SEED / q);
   return ((double)SEED / (double)m);
 }


void rand_seed (unsigned int init)   {if (init != 0) SEED = init;}

dgraph_t * dgraph_rand(int nodi,float perc_archi)
{
int i, archi=PERCENT(nodi,perc_archi);
dgraph_t *rst;
rst=dgraph_blank(nodi);
for(i=1;i<archi*nodi;i++){
add_new_edge(&rst->vertices[RAND_INT(0,nodi-1)],RAND_INT(0,nodi-1),1 + (rand() % 999));
}
return rst;
}
/*---------------------------------------------------------------------
 * ADJMAT  * LoadGraph_am(char* filename,int nodi,int rami)
 * Fa il load da un file in cui è rppresentato un grafo sottoforma di
 * matrice cosi' formattato  : %d %d %d.
 * In output rida' la matrice ottenuta
 *---------------------------------------------------------------------*/

ADJMAT  * LoadGraph_am(char* filename,int nodi,int rami)
{
ADJMAT * re;
FILE *f;
 int i,j,w;
 re=am_create(nodi);
 re->vtcnt=nodi;
 re->edcnt=rami;
 if((f=fopen(filename,"r"))==NULL) exit(0);
 printf("[*] Leggo dal file %s un grafo con %d nodi e %d archi  \n",filename,re->vtcnt , re->edcnt);
 while (fscanf(f,"%d %d %d",&i,&j,&w) != EOF){
 re->mat[i][j]=w;
 }
 fflush(f);
 fclose(f);
return re;
}

/* Funzioni di conversione */

/*---------------------------------------------------------------------
 * dgraph_t * al_to_am(ADJMAT *am)
 * In input vuole la matrice di convertire, in output rida'
 * il grafo rappresentato tramite liste di adiacenza 
 *---------------------------------------------------------------------*/

dgraph_t * al_to_am(ADJMAT *am)
{
int i,j;
dgraph_t * rst;
dgraph_vertex_t *vertex;
dgraph_edge_t *edge_ptr;
/*costruisco il grafo vuoto con i soli nodi*/
rst=dgraph_blank(am->vtcnt);
/*visito la matrice*/
for (i=0;i<am->vtcnt;i++)
 for (j=0;j<am->vtcnt;j++){
  if (am->mat[i][j]==1) add_new_edge(&rst->vertices[i],j,1 + (rand() % 999));
   }
return rst;
}

/*---------------------------------------------------------------------
 * ADJMAT * am_to_al(dgraph_t *g)
 * In input vuole il grafo rappresentato tramite liste di adiaceza
 * rida' in output il grafo rappresentato tramite matrici diadiacenza
 *---------------------------------------------------------------------*/

ADJMAT * am_to_al(dgraph_t *g){
ADJMAT *rst;
dgraph_edge_t *edge_ptr;
int i;

rst=am_create(g->n);
rst->vtcnt=g->n;
for (i=0;i<g->n;i++) {
edge_ptr=g->vertices[i].first_edge;
while(edge_ptr){
rst->mat[i][edge_ptr->vertex_no]=1;
edge_ptr=edge_ptr->next;
}
}
return rst;
}

/*---------------------------------------------------------------------
 * int connect(dgraph_t *g,int s,int d)
 * Usato per fare un test nella creazione del grafo delle cfc
 * serve per vedere se un nodo è conesso o meno ad un altro 
 * tramite una ricerca in profondita'.
 * in input vuole s che èl'id del nodo sorgente e d che èl'id del nodo
 * al quale si vuole vedere se è o meno connesso.
 *---------------------------------------------------------------------*/

int connect(dgraph_t *g,int s,int d)
{
int i;
/*typedef struct dfs_bfs_result {
    int n, size;
    int *vertices;
    int *parents;
    int *visit_nos;
} dfs_bfs_result_t;*/
dfs_bfs_result_t *re;
re=dfs(g,s);
for (i=1;i<re->size;i++)
{
if(re->vertices[i]==d) return 0;
}
return -1;
}