alg.c

来自「Floyd-wharshall algoritm for the shortes」· C语言 代码 · 共 69 行

 /*----------------------------------------------------------------------
 * alg.c
 * l-grafi version 0.1
 * Sorgente rappresentate i vari algoritmi per la chiusura transitiva-
 * riflessiva
 *--------------------------------------------------------------------*/

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

/*--------------------------------------------------------------------
 * double  FloydWarshall(dgraph_t *g )
 * Fa la chiusura transitiva-riflessiva lavorando su matrici
 * Input  : Il grafo da processare
 * Output : Il tempo di computazione
 *--------------------------------------------------------------------*/

double  FloydWarshall(dgraph_t *g )
{
 int k,i,j;
 clock_t t1,t2,rst;
 ADJMAT *matrice;
 dgraph_t *ret;
 
  t1=clock();
  
  matrice=am_to_al (g);                         /*Trasformazione della lista di adiacenza in matrice*/
  for ( i = 0; i < matrice->vtcnt; i++ )
  matrice->mat[i][i]=1;                         /*Chiusura riflessiva*/
  for ( k = 0; k < matrice->vtcnt; k++ )
  for ( i = 0; i < matrice->vtcnt; i++ )
  for ( j = 0; j < matrice->vtcnt; j++ )
  matrice->mat[i][j]=matrice->mat[i][j] || (matrice->mat[i][k] && matrice->mat[k][j]); /*Chiusura transitiva*/
  ret=al_to_am(matrice); /*Conversione matrice a lista*/
  
  t2=clock();
  rst=TO_MSEC(t2-t1);
  
  return rst;
}
 
/*----------------------------------------------------------------------
 * dgraph_t *FloydWarshall_al(dgraph_t *g )
 * Floyd-Warshall che lavora direttamente su liste
 * Input  : Grafo da processare
 * Output : Grafo nuovo con chiusura transitiva-riflessiva
----------------------------------------------------------------------*/

dgraph_t *FloydWarshall_al(dgraph_t *g )
{
int i,b,e;
dgraph_edge_t *edge_ptr,*edge_ptr2;
dgraph_t *ret;
clock_t t1,t2,rst;
ret=dgraph_blank(g->n);

for(i=0;i<g->n;i++) add_new_edge(&g->vertices[i],i,1 + (rand() % 999));
for (i=0;i<g->n;i++)
{
edge_ptr=g->vertices[i].first_edge;
while (edge_ptr){
add_al_from_vertex_to_vertex(g,i,edge_ptr->vertex_no);
edge_ptr=edge_ptr->next;
}}

return g;

}