[I2 logo] [RWTH logo] MOVES: Software Modeling and Verification
(Informatik 2)
Computer Science / RWTH / I2 / Research / Skil / Examples / Shpaths
Printer-friendly
Skil Sample Applications

Shortest Paths in Graphs



#include "Par/par.c"
#include "Array/array.h"
#include "Include/sys/limits.h"
#include "Include/math.h"


static void pck_f ($t v, Buff buff)
{
   return ;
}


static void upck_f (Buff buff, $t *vptr)
{
   return ;
}


static int *def_lowerbd (Index totalsize, int procNr)
{
   int *res, hSize, vSize, hBlockSize, vBlockSize ;

   vSize = totalsize[0] ;
   hSize = totalsize[1] ;

   vBlockSize = vSize / yNetDim ;
   if (vBlockSize * yNetDim < vSize)
      vBlockSize++ ;
   
   hBlockSize = hSize / xNetDim ;
   if (hBlockSize * xNetDim < hSize)
      hBlockSize++ ;

   res = (int *) VMalloc (2 * sizeof (int), "def_lowerbd") ;

   res[0] = (procNr / xNetDim) * vBlockSize ;
   res[1] = (procNr % xNetDim) * hBlockSize ;

   return (res) ;
}


static $t init_f (Index ix)
{
   return (abs (ix[0] - ix[1]) <= 1 ? abs (ix[0] - ix[1]) : INT_MAX) ;
}


static $t zero (Index ix)
{
   return (0) ;
}


static $t int_max (Index ix)
{
   return (INT_MAX) ;
}


static void destroy_f ($t v)
{
   return ;
}


static $t min ($t x, $t y)
{
   return (x < y ? x : y) ;
}


int main (int argc, char **argv)
{
   array <unsigned> a, b, c               ;
   int              i, log2n              ;
   float            flog2n                ;
   int              size                  ;
   Index            totalsize, def_blsize ;

   size = atoi (argv[1]) ;

   par_init   () ;
   array_init () ;

   totalsize[0] = size ;
   totalsize[1] = size ;

   def_blsize[0] = 0 ;
   def_blsize[1] = 0 ;

   a = array_create (2, totalsize, def_blsize, def_lowerbd (totalsize), init_f ) ;
   b = array_create (2, totalsize, def_blsize, def_lowerbd (totalsize), zero   ) ;
   c = array_create (2, totalsize, def_blsize, def_lowerbd (totalsize), int_max) ;

   flog2n = log (size) / log (2) ;
   log2n  = flog2n == floor (flog2n) ? flog2n : floor (flog2n) + 1 ;

   for (i = 0 ; i < log2n ; i++)
   {
      array_copy (a, b) ;

      array_gen_mult (a, b, min, (+), c, pck_f, upck_f) ;

      if (i < log2n - 1)
         array_copy (c, a) ;
   }

   array_destroy (a, destroy_f) ;
   array_destroy (b, destroy_f) ;
   array_destroy (c, destroy_f) ;

   array_close () ;
   par_close   () ;

   return (0) ;
}


Back to the Skil home page

Valid HTML 4.01 Strict! Valid CSS!