Rosetta Code

Floyd-Warshall algorithm: Difference between revisions

Page Discussion

Floyd-Warshall algorithm (view source)

Revision as of 17:27, 7 January 2023

683 bytes removed ,  1 year ago
m
→‎{{header|C}}
m (syntax highlighting fixup automation)
Line 1,370:
</pre>
 
==={{libheader|Gadget}}===
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.
VERSION 2. Using Gadget, an a "C" library.
 
<syntaxhighlight lang="c">
 
#include<limits.h>▼
#include "gadget<limits.h">
▲#include <limitsgadget/gadget.h>
 
LIB_GADGET_START
 
/* algunos datos globales */
Line 1,379 ⟶ 1,384:
 
/* algunos prototipos */
F_STAT DatosdeArchivo( const char *cFile);
int * CargaGrafoCargaMatriz(int * graphmat, DS_ARRAY * graph_datamat_data, const char * cFile, F_STAT stat );▼
void SeteaRangosLectura(F_STAT dataFile);
int * CargaMatrizCargaGrafo(int * matgraph, DS_ARRAY * mat_datagraph_data, const 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
if ( Arg_count != 2 ){
GetArgStr(cFile,1);▼
Msg_yellow("Modo de uso:\n ./floyd <archivo_de_vertices>\n");
SetTokSep(' ');▼
Stop(1);▼
}▼
▲ GetArgStrGet_arg_str (cFile,1);
▲ SetTokSepSet_token_sep(' ');
Cls;
if(ExistFileExist_file(cFile)){
New Arrayarray graph as int;
graph = CargaGrafo(graph, &graph_datapSDS(graph), cFile);
if(graph){
/* calcula Floyd-Warshall */
printf(Print "Vertices=%d, edges=%d\n",vertices,edges);
 
Floyd_Warshall( SDS(graph,) graph_data); Prnl;
 
Free Arrayarray graph;
}
 
}else{
MsgRedfMsg_redf("No existe el archivo %s",cFile);
}
Free Securesecure cFile;
End
 
void Floyd_Warshall( RDS(int * ,graph, DS_ARRAY) graph_data){
 
Array processWeights, processedVertices as int(vertices,vertices);
Fill array processWeights as int(vertices,vertices) with SHRT_MAX;
▲
 
ROWS 0:1:vertices-1; COLS 0:1:vertices-1;
int i,j,k;
COMPUTE_MATRange ( MAT(for processWeights )[0:1:vertices, =0:1:vertices SHRT_MAX];
 
MAT( processedVertices ) = (i!=j)?j+1:0; ); ▼
Compute_for( processWeights, i,j,
▲ MAT( $processedVertices )[i,j] = (i!=j)?j+1:0; );
{)▼
 
#define VERT_ORIG 0
Line 1,421 ⟶ 1,432:
#define WEIGHT 2
 
VECTIterator up i [0:1:edges-1;] {
$2processWeights[ $graph[i,VERT_ORIG]-1, $graph[i,VERT_DEST]-1 ] = $graph[i,WEIGHT];
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) );
 
Compute_for (processWeights,i,j,
PAGS Iterator up k [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(Print "pair dist path");
 
// ya existen rangos definios para "processWeights":
COMPUTE_MAT ( if(i!=j)
Compute_for(processWeights, i, j,
▲ {
printfif("\n%d -> %d %3d %5d",i+1,!=j+1, Cell(processWeights,i,j),i+1);
int k = i+1;{
Print do{"\n%d -> %d %3d %5d", i+1, j+1, $processWeights[i,j], i+1;
int k = Cell(processedVertices,k-i+1,j);
printf("->%d",k);do{
}while( k! =j+ $processedVertices[k-1),j];
} Print " -> %d", k;
}while(k!=j+1);
}
);
 
Free Arrayarray processWeights, processedVertices;
}
 
F_STAT DatosdeArchivo( const char *cFile){
return StatFileStat_file(cFile);
}
 
int * CargaMatriz( pRDS(int, mat), const char * cFile, F_STAT stat ){
void SeteaRangosLectura(F_STAT df){
return LoadMatrix_intLoad_matrix( SDS(mat, mat_data), cFile, stat);▼
ROWS 0:1:df.total_lines-1 ;
COLS 0:1:df.max_tokens_per_line-1;
PAGS NONE;
}
 
int * CargaMatrizCargaGrafo( pRDS(int, * matgraph), DS_ARRAY * mat_data,const 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);
 
graphRange = CargaMatriz(ptr graph, graph_data, cFile[0:1:dataFile.total_lines-1, 0:1:dataFile).max_tokens_per_line-1];
 
graph = CargaMatriz( SDS(graph), cFile, dataFile);
 
if( graph ){
/* obtengo vertices = 4 y edges = 5 */
edges = dataFile.total_lines;
/*Block( buscovertices, entreRange los vertices,ptr elgraph último[ nodo0:1:pRows(graph), el0:1:1 mayor.];
Uso un "Block", para no llamar una función */ DS_MAXMIN maxNode = Max_array( SDS(graph) );
Block( vertices, COLS 0:1:1; Out_int( $graph[maxNode.local] ) // 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{
MsgRedfMsg_redf("Archivo \"%s\" no ha podido ser cargado",cFile);
}
 
}else{
MsgRedfMsg_redf("Archivo \"%s\" no es cuadrado",cFile);
}
return graph;
Mr Dalien
545

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/335208"