Floyd-Warshall algorithm: Difference between revisions
→{{header|C}}
Line 1,355:
<pre>
C:\rosettaCode>fwGraph.exe fwGraph.txt
pair dist path
1 -> 2 -1 1->3->4->2
1 -> 3 -2 1->3
1 -> 4 0 1->3->4
2 -> 1 4 2->1
2 -> 3 2 2->1->3
2 -> 4 4 2->1->3->4
3 -> 1 5 3->4->2->1
3 -> 2 1 3->4->2
3 -> 4 2 3->4
4 -> 1 3 4->2->1
4 -> 2 -1 4->2
4 -> 3 1 4->2->1->3
</pre>
VERSION 2. Usando una librería experimental, que pronto será liberada en GitHub, desarrollé la versión anterior del programa. La librería trabaja con memoria dinámica, tanto para strings, como para arrays de un tipo y multitipo. En el ejemplo, se usan funciones para arrays de un tipo. Lo que busco con esta librería experimental, es simplificar la programación, elevar el nivel de abstracción del lenguaje C (un poco), y lograr código elegante.
<lang C>
#include<limits.h>
#include "gadget.h"
/* algunos datos globales */
int vertices,edges;
/* algunos prototipos */
F_STAT DatosdeArchivo( char *cFile);
void SeteaRangosLectura(F_STAT dataFile);
int * CargaMatriz(int * mat, DS_ARRAY * mat_data, char * cFile, F_STAT stat );
int * CargaGrafo(int * graph, DS_ARRAY * graph_data, char *cFile);
void Floyd_Warshall(int * graph, DS_ARRAY graph_data);
/* bloque principal */
Main
GetArgStr(cFile,1);
SetTokSep(' ');
Cls;
if(ExistFile(cFile)){
New Array graph as int;
graph = CargaGrafo(graph, &graph_data, cFile);
if(graph){
/* calcula Floyd-Warshall */
printf("Vertices=%d, edges=%d\n",vertices,edges);
Floyd_Warshall(graph, graph_data);
Free Array graph;
}
}else{
MsgRedf("No existe el archivo %s",cFile);
}
Free Secure cFile;
End
void Floyd_Warshall(int * graph, DS_ARRAY graph_data){
Array processWeights, processedVertices as int(vertices,vertices);
ROWS 0:1:vertices-1; COLS 0:1:vertices-1;
COMPUTE_MAT ( MAT( processWeights ) = SHRT_MAX;
MAT( processedVertices ) = (i!=j)?j+1:0; );
#define VERT_ORIG 0
#define VERT_DEST 1
#define WEIGHT 2
VECT 0:1:edges-1;
IterVec( i,
int vert_origen = Cell(graph,i,VERT_ORIG)-1;
int vert_destino = Cell(graph,i,VERT_DEST)-1;
Cell( processWeights, vert_origen, vert_destino ) = Cell( graph,i,WEIGHT) );
PAGS 0:1:vertices-1;
COMPUTE_BLK ( if( Cell(processWeights,j,i) + Cell(processWeights,i,k) < Cell(processWeights,j,k) )
{
Cell(processWeights,j,k) = Cell(processWeights,j,i) + Cell(processWeights,i,k);
Cell(processedVertices,j,k) = Cell(processedVertices,j,i);
}
);
printf("pair dist path");
COMPUTE_MAT ( if(i!=j)
{
printf("\n%d -> %d %3d %5d",i+1,j+1, Cell(processWeights,i,j),i+1);
int k = i+1;
do{
k = Cell(processedVertices,k-1,j);
printf("->%d",k);
}while(k!=j+1);
}
);
Free Array processWeights, processedVertices;
}
F_STAT DatosdeArchivo( char *cFile){
return StatFile(cFile);
}
void SeteaRangosLectura(F_STAT df){
ROWS 0:1:df.total_lines-1 ;
COLS 0:1:df.max_tokens_per_line-1;
PAGS NONE;
}
int * CargaMatriz(int * mat, DS_ARRAY * mat_data, char * cFile, F_STAT stat ){
return LoadMatrix_int( mat, mat_data, cFile, stat);
}
int * CargaGrafo(int * graph, DS_ARRAY * graph_data, char *cFile){
F_STAT dataFile = DatosdeArchivo(cFile);
if(dataFile.is_matrix){
SeteaRangosLectura(dataFile);
graph = CargaMatriz( graph, graph_data, cFile, dataFile);
if( graph ){
/* obtengo vertices y edges */
edges = dataFile.total_lines;
/* busco entre los vertices, el último nodo, el mayor.
Uso un "Block", para no llamar una función */
Block( vertices, COLS 0:1:1; // busque en las 2 primeras columnas del array vertices
ROWS 0:1:graph_data->rows-1; // busque en todas las filas
PAGS NONE; // no hay páginas
DS_MAXMIN maxNode = MaxArray_int( graph,graph_data );
OutInt( Cell(graph, maxNode.local) ) );
}else{
MsgRedf("Archivo \"%s\" no ha podido ser cargado",cFile);
}
}else{
MsgRedf("Archivo \"%s\" no es cuadrado",cFile);
}
return graph;
}
</lang>
{{out}}
Archivo fuente: floyd_data.txt
<pre>
1 3 -2
3 4 2
4 2 -1
2 1 4
2 3 3
</pre>
Salida:
<pre>
$ ./floydWarshall floy_data.txt
Vertices=4, edges=5
pair dist path
1 -> 2 -1 1->3->4->2
| |||