spgrid.c

来自「17个最短路径源代码。代码效率高」· C语言 代码 · 共 675 行 · 第 1/2 页

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <values.h>

#include "random.c"

#define DASH '-'
#define VERY_FAR 100000000

#define DOUBLE_CYCLE   0
#define CYCLE          1
#define PATH           2

#define NO             0
#define YES            1

#define NODE( x, y ) (x*Y + y + 1)

#define PRINT_ARC( i, j, length )\
{\
l = length;\
if ( p_f ) l += ( p[i] - p[j] );\
printf ("a %8ld %8ld %12ld\n", i, j, l );\
}

char   *graph_type[] =
  {
    "double cycle",
    "cycle",
    "path"
  };

/* generator of layered networks for the shortest paths problem;
   extended DIMACS format for output */

main ( argc, argv )

int argc;
char* argv[];

{

char   args[30];

long   X,   /* horizontal size of grid */
       Y;   /* vertical size of grid */

long   x,
       y,
       y1, y2, yp,
       dl, dx, xn, yn, count,
       *mess;

double n;
long   n0,
       source,
       i,
       i0,
       j,
       dij;

double m;
long   m0,
       mc,
       k;

long   *p,
       p_t,
       l,
       lx;

long   seed,
       seed1,
       seed2;

int    ext=0;

FILE   *fout;

/* initialized by default values */

/* variables for generating one layer */

/* variables for generating spanning graph */
int    c_f = 0, cw_f = 0, cm_f = 0, cl_f = 0;

int    cw = DOUBLE_CYCLE;  /* type of spanning graph */
long   cm = 0,             /* lower bound of the interval */
       cl = 100;           /* upper bound of the interval */

/* variables for generating additional arcs */
int    a_f = 0, ax_f = 0, am_f = 0, al_f = 0;

long   ax = 0,             /* number of additional arcs */
       am = 0,             /* lower bound of the interval */
       al = 100;           /* upper bound of the interval */
       
/* variables for inter-layer arcs */
int    i_f = 0, ip_f = 0, ix_f = 0, ih_f = 0,
       im_f = 0, il_f = 0, in_f = 0, is_f = 0;

int    ip = NO;       /* to mess or not to mess */
long   ix = 1,        /* number of interlayered arcs in a NODE */
       ih = 1,        /* step between two layeres */
       il = 10000,    /* upper bound of the interval */
       im = 1000;     /* lower bound of the interval */
double in = 1,        /* l *=  in * |x1-x2| */ 
       is = 0;        /* l *=  is * |x1-x2|^2 */

/* variables for artifical source */
int    s_f = 0, sl_f = 0, sm_f = 0;
long   sl   = VERY_FAR, /* upper bound of artifical arc */
       sm,              /* lower bound of artifical arc */
       s;  

/* variables for potentials */
int    p_f = 0, pl_f = 0, pm_f = 0, pn_f = 0, ps_f = 0;

long   pl,            /* upper bound of the interval */
       pm;            /* lower bound of the interval */
double pn = 0,        /* p +=  ln * (x+1) */ 
       ps = 0;        /* p +=  ls * (x+1)^2 */

int np;               /* number of parameter parsing now */


  /* parsing  parameters */

if ( argc < 2 ) goto usage;

np = 0;

strcpy ( args, argv[1] );

  if ( ( args[0] == DASH ) && ( args[1] == 'h')
     )
      goto help;

if ( argc < 4 ) goto usage;

/* first parameter - horizontal size */
np = 1;
if ( ( X = atoi ( argv[1] ) )  <  1  )  goto usage;

/* second parameter - vertical size */
np = 2;
if ( ( Y = atoi ( argv[2] ) )  <  1  )  goto usage;

/* third parameter - seed */
np=3;
if ( ( seed = atoi ( argv[3] ) )  <=  0  )  goto usage;

/* other parameters */

for ( np = 4; np < argc; np ++ )
  {
    strcpy ( args, argv[np] );
    if ( args[0] != DASH ) goto usage;

    switch ( args[1] )
      {

      case 'c' : /* spanning graph in one layer */
	  c_f = 1;
	switch ( args[2] )
	  { 
	  case 'l': /* upper bound of the interval */
	    cl_f = 1;
	    cl  =  (long) atof ( &args[3] );
	    break;
	  case 'm': /* lower bound */
	    cm_f = 1;
	    cm  = (long ) atof ( &args[3] );
	    break;
	  case 'c': /* type - cycle */
	    cw_f = 1;
	    cw   = CYCLE;
	    break;
	  case 'd': /* type - double cycle */
	    cw_f = 1;
	    cw   = DOUBLE_CYCLE;
	    break;
	  case 'p': /* type - path */
	    cw_f = 1;
	    cw   = PATH;
	    break;

	  default:  /* unknown switch  value */
	    goto usage;
	  }
	break;

      case 'a' : /* additional arcs in one layer */
	 a_f = 1;
	switch ( args[2] )
	  { 
	  case 'l': /* upper bound of the interval */
	    al_f = 1;
	    al  =  (long) atof ( &args[3] );
	    break;
	  case 'm': /* lower bound */
	    am_f = 1;
	    am  = (long ) atof ( &args[3] );
	    break;
	  case 'x': /* number of additional arcs */
	    ax_f = 1;
	    ax   = (long ) atof ( &args[3] );
	    if ( ax < 0 ) goto usage;
	    break;

	  default:  /* unknown switch  value */
	    goto usage;
	  }
	break;


      case 'i' : /* interlayered arcs */
	i_f = 1;

	switch ( args[2] )
	  { 
	  case 'l': /* upper bound */
	    il_f = 1;
	    il  =  (long) atof ( &args[3] );
	    break;
	  case 'm': /* lower bound */
	    im_f = 1;
	    im  = (long ) atof ( &args[3] );
	    break;
	  case 'n': /* additional length: l *= in*|i1-i2| */
	    in_f = 1;
	    in  = atof ( &args[3] );
	    break;
	  case 's': /* additional length: l *= is*|i1-i2|^2 */
	    is_f = 1;
	    is  = atof ( &args[3] );
	    break;
	  case 'p': /* mess interlayered arcs */
	    ip_f = 1;
	    ip = YES;
	    break;
	  case 'x': /* number of interlayered arcs */
	    ix_f = 1;
	    ix  = atof ( &args[3] );
	    if ( ix < 1 ) goto usage;
	    break;
	  case 'h': /* step between two layeres */
	    ih_f = 1;
	    ih  = atof ( &args[3] );
	    if ( ih < 1 ) goto usage;
	    break;
	  default:  /* unknown switch  value */
	    goto usage;
	  }
	break;

      case 's' : /* additional source */
        s_f = 1;
	if ( strlen ( args ) > 2 )
	{  
	switch ( args[2] )
	  { 
	  case 'l': /* upper bound of art. arc */
	    sl_f = 1;
	    sl  =  (long) atof ( &args[3] );
            break;
	  case 'm': /* lower bound of art. arc */
	    sm_f = 1;
	    sm  =  (long) atof ( &args[3] );
            break;
	  default:  /* unknown switch  value */
	    goto usage;
          }
         }
	break;

      case 'p' : /* potentials */
	p_f = 1;
	if ( strlen ( args ) > 2 )
	{  
	switch ( args[2] )
	  { 
	  case 'l': /* upper bound */
	    pl_f = 1;
	    pl  =  (long) atof ( &args[3] );
	    break;
	  case 'm': /* lower bound */
	    pm_f = 1;
	    pm  = (long ) atof ( &args[3] );
	    break;
	  case 'n': /* additional: p *= pn*(x+1) */
	    pn_f = 1;
	    pn  = atof ( &args[3] );
	    break;
	  case 's': /* additional: p = ps* (x+1)^2 */
	    ps_f = 1;
	    ps  = atof ( &args[3] );
	    break;
	  default:  /* unknown switch  value */
	    goto usage;
	  }
        }
	break;

      default: /* unknoun case */
	goto usage;
      }
  }
   

/* ----- ajusting parameters ----- */

/* spanning */
if ( cl < cm ) { lx = cl; cl = cm; cm = lx; }

/* additional arcs */
if ( al < am ) { lx = al; al = am; am = lx; }

/* interlayered arcs */
if ( il < im ) { lx = il; il = im; im = lx; }

/* potential parameters */
if ( p_f )
  {
   if ( ! pl_f ) pl = il;
   if ( ! pm_f ) pm = im;
   if ( pl < pm ) { lx = pl; pl = pm; pm = lx; }
  }

/* number of nodes and arcs */

n = (double)X *(double)Y + 1;

m  = (double)Y; /* arcs from source */

switch ( cw )
{