122 lines
3.4 KiB
C
122 lines
3.4 KiB
C
#include <limits.h>
|
|
#include <gadget/gadget.h>
|
|
|
|
LIB_GADGET_START
|
|
|
|
/* algunos datos globales */
|
|
int vertices,edges;
|
|
|
|
/* algunos prototipos */
|
|
F_STAT DatosdeArchivo( const char *cFile);
|
|
int * CargaMatriz(int * mat, DS_ARRAY * mat_data, const char * cFile, F_STAT stat );
|
|
int * CargaGrafo(int * graph, DS_ARRAY * graph_data, const char *cFile);
|
|
void Floyd_Warshall(int * graph, DS_ARRAY graph_data);
|
|
|
|
/* bloque principal */
|
|
Main
|
|
if ( Arg_count != 2 ){
|
|
Msg_yellow("Modo de uso:\n ./floyd <archivo_de_vertices>\n");
|
|
Stop(1);
|
|
}
|
|
Get_arg_str (cFile,1);
|
|
Set_token_sep(' ');
|
|
Cls;
|
|
if(Exist_file(cFile)){
|
|
New array graph as int;
|
|
graph = CargaGrafo( pSDS(graph), cFile);
|
|
if(graph){
|
|
/* calcula Floyd-Warshall */
|
|
Print "Vertices=%d, edges=%d\n",vertices,edges;
|
|
|
|
Floyd_Warshall( SDS(graph) ); Prnl;
|
|
|
|
Free array graph;
|
|
}
|
|
|
|
}else{
|
|
Msg_redf("No existe el archivo %s",cFile);
|
|
}
|
|
Free secure cFile;
|
|
End
|
|
|
|
void Floyd_Warshall( RDS(int,graph) ){
|
|
|
|
Array processedVertices as int(vertices,vertices);
|
|
Fill array processWeights as int(vertices,vertices) with SHRT_MAX;
|
|
|
|
int i,j,k;
|
|
Range for processWeights [0:1:vertices, 0:1:vertices ];
|
|
|
|
Compute_for( processWeights, i,j,
|
|
$processedVertices[i,j] = (i!=j)?j+1:0;
|
|
)
|
|
|
|
#define VERT_ORIG 0
|
|
#define VERT_DEST 1
|
|
#define WEIGHT 2
|
|
|
|
Iterator up i [0:1:edges] {
|
|
$2processWeights[ $graph[i,VERT_ORIG]-1, $graph[i,VERT_DEST]-1 ] = $graph[i,WEIGHT];
|
|
}
|
|
|
|
Compute_for (processWeights,i,j,
|
|
Iterator up k [0:1:vertices] {
|
|
if( $processWeights[j,i] + $processWeights[i,k] < $processWeights[j,k] )
|
|
{
|
|
$processWeights[j,k] = $processWeights[j,i] + $processWeights[i,k];
|
|
$processedVertices[j,k] = $processedVertices[j,i];
|
|
}
|
|
} );
|
|
|
|
Print "pair dist path";
|
|
|
|
// ya existen rangos definios para "processWeights":
|
|
Compute_for(processWeights, i, j,
|
|
if(i!=j)
|
|
{
|
|
Print "\n%d -> %d %3d %5d", i+1, j+1, $processWeights[i,j], i+1;
|
|
int k = i+1;
|
|
do{
|
|
k = $processedVertices[k-1,j];
|
|
Print " -> %d", k;
|
|
}while(k!=j+1);
|
|
}
|
|
);
|
|
|
|
Free array processWeights, processedVertices;
|
|
}
|
|
|
|
F_STAT DatosdeArchivo( const char *cFile){
|
|
return Stat_file(cFile);
|
|
}
|
|
|
|
int * CargaMatriz( pRDS(int, mat), const char * cFile, F_STAT stat ){
|
|
return Load_matrix( SDS(mat), cFile, stat);
|
|
}
|
|
|
|
int * CargaGrafo( pRDS(int, graph), const char *cFile){
|
|
|
|
F_STAT dataFile = DatosdeArchivo(cFile);
|
|
if(dataFile.is_matrix){
|
|
|
|
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 ){
|
|
/* obtengo vertices = 4 y edges = 5 */
|
|
edges = dataFile.total_lines;
|
|
|
|
Block( vertices, Range ptr graph [ 0:1:pRows(graph), 0:1:1 ];
|
|
DS_MAXMIN maxNode = Max_array( SDS(graph) );
|
|
Out_int( $graph[maxNode.local] ) );
|
|
}else{
|
|
Msg_redf("Archivo \"%s\" no ha podido ser cargado",cFile);
|
|
}
|
|
|
|
}else{
|
|
Msg_redf("Archivo \"%s\" no es cuadrado",cFile);
|
|
}
|
|
return graph;
|
|
}
|