Floyd-Warshall algorithm: Difference between revisions

Content added Content deleted
m (syntax highlighting fixup automation)
Line 1,370: Line 1,370:
</pre>
</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">
<syntaxhighlight lang="c">

⚫
#include<limits.h>
#include "gadget.h"
#include <limits.h>
⚫
#include <gadget/gadget.h>

LIB_GADGET_START


/* algunos datos globales */
/* algunos datos globales */
Line 1,379: Line 1,384:


/* algunos prototipos */
/* algunos prototipos */
F_STAT DatosdeArchivo( char *cFile);
F_STAT DatosdeArchivo( const char *cFile);
⚫
int * CargaMatriz(int * mat, DS_ARRAY * mat_data, const char * cFile, F_STAT stat );
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, const char *cFile);
⚫
int * CargaGrafo(int * graph, DS_ARRAY * graph_data, char *cFile);
void Floyd_Warshall(int * graph, DS_ARRAY graph_data);
void Floyd_Warshall(int * graph, DS_ARRAY graph_data);


/* bloque principal */
/* bloque principal */
Main
Main
if ( Arg_count != 2 ){
⚫
GetArgStr(cFile,1);
Msg_yellow("Modo de uso:\n ./floyd <archivo_de_vertices>\n");
⚫
SetTokSep(' ');
⚫
Stop(1);
⚫
}
⚫
Get_arg_str (cFile,1);
⚫
Set_token_sep(' ');
Cls;
Cls;
if(ExistFile(cFile)){
if(Exist_file(cFile)){
New Array graph as int;
New array graph as int;
graph = CargaGrafo(graph, &graph_data, cFile);
graph = CargaGrafo( pSDS(graph), cFile);
if(graph){
if(graph){
/* calcula Floyd-Warshall */
/* calcula Floyd-Warshall */
printf("Vertices=%d, edges=%d\n",vertices,edges);
Print "Vertices=%d, edges=%d\n",vertices,edges;


Floyd_Warshall(graph, graph_data);
Floyd_Warshall( SDS(graph) ); Prnl;


Free Array graph;
Free array graph;
}
}


}else{
}else{
MsgRedf("No existe el archivo %s",cFile);
Msg_redf("No existe el archivo %s",cFile);
}
}
Free Secure cFile;
Free secure cFile;
End
End


void Floyd_Warshall(int * graph, DS_ARRAY graph_data){
void Floyd_Warshall( RDS(int,graph) ){


Array processWeights, processedVertices as int(vertices,vertices);
Array 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_MAT ( MAT( processWeights ) = SHRT_MAX;
Range for processWeights [0:1:vertices, 0:1:vertices ];

⚫
MAT( processedVertices ) = (i!=j)?j+1:0; );
Compute_for( processWeights, i,j,
⚫
$processedVertices[i,j] = (i!=j)?j+1:0;
⚫
)


#define VERT_ORIG 0
#define VERT_ORIG 0
Line 1,421: Line 1,432:
#define WEIGHT 2
#define WEIGHT 2


VECT 0:1:edges-1;
Iterator up i [0:1:edges] {
$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 0:1:vertices-1;
Iterator up k [0:1:vertices] {
⚫
COMPUTE_BLK ( if( Cell(processWeights,j,i) + Cell(processWeights,i,k) < Cell(processWeights,j,k) )
if( $processWeights[j,i] + $processWeights[i,k] < $processWeights[j,k] )
{
{
Cell(processWeights,j,k) = Cell(processWeights,j,i) + Cell(processWeights,i,k);
$processWeights[j,k] = $processWeights[j,i] + $processWeights[i,k];
Cell(processedVertices,j,k) = Cell(processedVertices,j,i);
$processedVertices[j,k] = $processedVertices[j,i];
}
}
);
} );


printf("pair dist path");
Print "pair dist path";


// ya existen rangos definios para "processWeights":
COMPUTE_MAT ( if(i!=j)
Compute_for(processWeights, i, j,
⚫
{
printf("\n%d -> %d %3d %5d",i+1,j+1, Cell(processWeights,i,j),i+1);
if(i!=j)
int k = i+1;
{
do{
Print "\n%d -> %d %3d %5d", i+1, j+1, $processWeights[i,j], i+1;
k = Cell(processedVertices,k-1,j);
int k = i+1;
printf("->%d",k);
do{
}while(k!=j+1);
k = $processedVertices[k-1,j];
}
Print " -> %d", k;
);
}while(k!=j+1);
}
);


Free Array processWeights, processedVertices;
Free array processWeights, processedVertices;
}
}


F_STAT DatosdeArchivo( char *cFile){
F_STAT DatosdeArchivo( const char *cFile){
return StatFile(cFile);
return Stat_file(cFile);
}
}


int * CargaMatriz( pRDS(int, mat), const char * cFile, F_STAT stat ){
void SeteaRangosLectura(F_STAT df){
⚫
return Load_matrix( SDS(mat), cFile, stat);
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 ){
int * CargaGrafo( pRDS(int, graph), const char *cFile){
⚫
return LoadMatrix_int( mat, mat_data, cFile, stat);
}

int * CargaGrafo(int * graph, DS_ARRAY * graph_data, char *cFile){


F_STAT dataFile = DatosdeArchivo(cFile);
F_STAT dataFile = DatosdeArchivo(cFile);
if(dataFile.is_matrix){
if(dataFile.is_matrix){
⚫
SeteaRangosLectura(dataFile);


graph = CargaMatriz( graph, graph_data, cFile, dataFile);
Range ptr graph [0:1:dataFile.total_lines-1, 0:1:dataFile.max_tokens_per_line-1];

graph = CargaMatriz( SDS(graph), cFile, dataFile);


if( graph ){
if( graph ){
/* obtengo vertices y edges */
/* obtengo vertices = 4 y edges = 5 */
edges = dataFile.total_lines;
edges = dataFile.total_lines;
/* busco entre los vertices, el último nodo, el mayor.
Block( vertices, Range ptr graph [ 0:1:pRows(graph), 0:1:1 ];
Uso un "Block", para no llamar una función */
DS_MAXMIN maxNode = Max_array( SDS(graph) );
Block( vertices, COLS 0:1:1; // busque en las 2 primeras columnas del array vertices
Out_int( $graph[maxNode.local] ) );
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{
}else{
MsgRedf("Archivo \"%s\" no ha podido ser cargado",cFile);
Msg_redf("Archivo \"%s\" no ha podido ser cargado",cFile);
}
}


}else{
}else{
MsgRedf("Archivo \"%s\" no es cuadrado",cFile);
Msg_redf("Archivo \"%s\" no es cuadrado",cFile);
}
}
return graph;
return graph;
Retrieved from "https://rosettacode.org/wiki/Floyd-Warshall_algorithm"