ts.c

it is very important

/* $Id: ts.c,v 1.1 1996/10/04 13:37:05 calvert Exp $
 * 
 * ts.c -- routines to construct transit-stub graphs
 *         using the Stanford GraphBase tools.
 *
 * This code calls the routines in geog.c
 *
 */

#include <stdio.h>
#include <sys/types.h>		/* for NBBY */
#include <alloca.h>
#include "gb_graph.h"
#include <math.h>
#include "geog.h"
#include <limits.h>
#include <string.h>
#include <assert.h>

static char tsId[]="$Id: ts.c,v 1.1 1996/10/04 13:37:05 calvert Exp $";

/* convention for trouble codes: TS adds 7-9 */
#define TS_TRBL		7


#define vtoi(g,v)	((v) - (g)->vertices)

#define link	vv.G		/* Graph utility field */

/* Graph aux fields */

/* The following three are stored with the FINAL graph */
#define MaxTdiam	xx.I    /* Maximum Transit diameter (hops) */
#define MaxSdiam	yy.I    /* Maximum Stub diameter (hops) */
#define Topdiam		zz.I    /* Top-level Diameter (hops) */

/* The following two are used ONLY in Stub graphs */
#define Gxoff   xx.I            /* global x offset of stub domain graph */
#define Gyoff   yy.I            /* global y offset of stub domain graph */

#define TS_UTIL 	"ZZZIIZIZIZZIII"
                      /* VVVVVVAAGGGGGG */
                      /* uvwxyzabuvwxyz
			         uvwxyz */


#define sub     u.G             /* subordinate graph of a node */
#define flat	z.V		/* corresponding node in "flat" graph */

#define vindex(V,G)	((V) - (G)->vertices) 
#define	halfup(x)	(((x)>>1)+1)

#define OVERALL_DENSITY_FACTOR	80.0
#define STUB_DENSITY_FACTOR	16.0
#define TRANSIT_SPREAD		0.5

#define STACKMAX	0x800	/* max memory allocated in stack	*/

#define RANDMULT	3	/* multiplier for random iterations	*/
				/* determines max deviation from mean	*/

/*
#define BADRETURN(x)	{ free(nnodes); free(nstubs); free(nstubnodes);\
			  return (x); }
*/

/* fast diameter computation using Floyd-Warshall
 * Returns the HOP diameter of the graph, i.e. each edge given UNIT wt.
 * Leaves the LENGTH diameter of the graph in g->Gldiam.
 * It also works for DIRECTED graphs. */
long
fdiam(Graph *g)
{
register i,j,k;
long **dist, **ldist;
int changed,mallocd;
long diam, ldiam, newdist = 0, otherend;
Vertex *v;
Arc *a;

    i = g->n*g->n*sizeof(long*);
    if (i<STACKMAX) {
	dist = (long **)alloca(i);
	ldist = (long**)alloca(i);
	mallocd = 0;
    } else {
	dist = (long **)malloc(i);
        ldist = (long**)malloc(i);
	mallocd = 1;
    }

    for (i=0; i < g->n; i++) {
	if (mallocd) {
	    dist[i] = (long *)malloc(g->n*sizeof(long));
	    ldist[i] = (long *)malloc(g->n*sizeof(long));
	} else {
	    dist[i] = (long *)alloca(g->n*sizeof(long));
	    ldist[i] = (long *)alloca(g->n*sizeof(long));
	}
	for (j=0; j < g->n; j++)
	  dist[i][j] = ldist[i][j] =  BIGINT;

	dist[i][i] = ldist[i][i] = 0;
    }

    for (i=0,v=g->vertices; i < g->n; i++,v++)
	for (a=v->arcs; a; a=a->next) {
	    otherend = vtoi(g,a->tip);
	    ldist[i][otherend] = a->len;       /* edge weight */
	    dist[i][otherend] = 1;
	}

    /* iterate until nothing changes */
    changed = 1;
    while (changed) {
      /* INVARIANT: dist[i][k] == BIGINT  === ldist[i][k] == BIGINT */
	changed = 0;
	for (i=0; i<g->n; i++)
	    for (j=0; j<g->n; j++) {
		for (k=0; k<g->n; k++) { /* i < k < j */
		    if (i==j || j==k || i==k)
			continue;
		    /* i != j && j != k && i != k */
		    if (dist[i][k] == BIGINT ||
			dist[k][j] == BIGINT)
			continue;	/* nothing to gain */
		    newdist = dist[i][k] + dist[k][j];
		    if (newdist < dist[i][j]) {
			dist[i][j] = newdist;
			changed++;
		    } /* if shorter */
		    newdist = ldist[i][k] + ldist[k][j];
		    if (newdist < ldist[i][j]) {
			ldist[i][j] = newdist;
			changed++;
		    } /* if shorter */
	        } /* for k */

            } /* for j */

    } /* while (changed) */

    diam = ldiam = 0;
    /* now find max shortest path */
    for (i=0; i<g->n; i++)
	for (j=0; j<g->n; j++) {
	  if (dist[i][j] > diam)
	    diam = dist[i][j];
	  if (ldist[i][j] > diam)
	    ldiam = ldist[i][j];
        }

    if (mallocd) {
      for (i=0; i<g->n; i++) {
	free(dist[i]);
	free(ldist[i]);
      }
      free(dist);
      free(ldist);
    }

/* Store the Euclidean diameter; for now we don't do anything with it.
    g->Gldiam = ldiam;
*/ 


    return diam;

} /* fdiam */

void
die(s)
{
fprintf(stderr,"Fatal error %s\n",s);
exit(1);
}

/* Create a copy of each edge in fromG in toG.			*/
/* Also places a pointer in each node in fromG pointing to the  */
/* corresponding node in toG.					*/
/* Requires: fromG != NULL, toG != NULL, toG->n >= fromG->n	*/
void
copyedges(Graph *fromG, Graph *toG, long base)
{
register i, indx;
Vertex *np, *vp, *basep;
Arc *ap;

basep = toG->vertices + base;

for (i=0,vp=fromG->vertices,np=basep; i<fromG->n;
     i++,vp++,np++) {
  
  vp->flat = np;	/* keep a pointer from old v to new */

  for (ap=vp->arcs; ap; ap=ap->next) {
    indx = vindex(ap->tip,fromG);
    if (i<indx) /* do each edge only once */ {
      gb_new_edge(np,basep+indx,ap->len); /* euclidean doesn't change! */
      np->arcs->policywt = 1;           /* unit weight for policy  */
      (np->arcs+1)->policywt = 1;       /* both directions!  */
    }
  }
}

} /* copyedges() */
		

/* Generate Transit-Stub graphs.					*/
/* Returns NULL without cleaning up when any subroutine call [e.g. geo(),  */
/* gb_new_graph()] fails.						   */
Graph *
transtub(long seed,
	 int spx,		/* mean # stubs/transit node	*/
	 int nrants,		/* # random transit-stub edges	*/
	 int nranss,		/* # random stub-stub edges	*/
	 geo_parms* toppp,	/* params for transit connectivity */
	 geo_parms* transpp,	/*   "     "  transit domains	*/
	 geo_parms* stubpp)	/*   "     "  stub domains	*/
{

int topdiam,	/* diameter of top-level graph */
    transdiam=0,  /* max diameter of a transit domain graph*/
    stubdiam=0;	/* max diameter of a stub domain graph */
long ts,	/* length of transit-stub edges */
     ss,	/* length of stub-stub edges */
     tt;	/* length of transit-transit edges */

Graph *topG=NULL, *newG=NULL, *stubG=NULL, *finalG, *dgp, *ddgp, *sgp, *tempg;
/* XXX this should be ifdef'd to be "int" on 32-bit machines and "short"  */
/* on 64-bit machines.  Who needs a graph with more than 2 billion nodes? */

long *nnodes=NULL, *nstubs=NULL, *nstubnodes=NULL;
long maxtnodes, maxstubs, maxstubnodes, maxtotal;

/* for positioning in plane. */
long globscale, xoffset, yoffset, maxstuboff, maxx, minx, maxy, miny, xrange,
yrange;
long i,j,k;
long indx, diam, totalnodes, base, dom;
char dnodename[ID_FIELD_SIZE], snodename[ID_FIELD_SIZE];
int dnamelen, numtries=0;
register Vertex *v,*dnp, *snp,	/* domain node and stub node pointers	*/
       *ddnp, *fp, *tp, *tmp;

Arc *a;
long dnn,snn,		/* domain node number, stub node number	*/
     snum,		/* stub number */
     attachnode;	/* index of edge endpoint */

/* XXXXXX We need to copy ALL parameters because we modify them, and they
 * need to be saved with the output graph. */

geo_parms workparms;

   if (seed)
	gb_init_rand(seed);

/* allocate dynamic arrays.  We can calc upper bounds on sizes		*/
/* because increase above mean due to randomize() is at most number	*/
/* of iterations.  Note: These look weird, but they are correct.	*/

   maxtnodes = transpp->n + (RANDMULT *toppp->n);
   maxstubs = spx + (RANDMULT * maxtnodes);
   maxstubnodes = stubpp->n + (RANDMULT*maxstubs);

   /*   We can already calculate the total number of nodes  */
   totalnodes = toppp->n * transpp->n * (spx * stubpp->n + 1);

   nstubs = (long *)malloc(maxtnodes*sizeof(long)); /* stubs per T node */
   nstubnodes = (long *)malloc(maxstubs*sizeof(long)); /* stub nodes per stub*/
   nnodes = (long *)malloc(toppp->n*sizeof(long));  /* nodes per T dom */

/* Compute the scales.  The global scale determines the actual unit sizes.
 * The others determine how big (i.e. how much of the whole square) a transit
 * domain and a stub domain are.  That is, the fraction of the square
 * covered by a transit domain is TRANSIT_SPREAD^2. XXX should be a parameter
 * Fraction of a square covered by a stub domain = (stubpp->scale/globscale)^2.
 */

   globscale = (long) rint(sqrt(totalnodes*OVERALL_DENSITY_FACTOR));
   toppp->scale = globscale;
   transpp->scale = (long) rint(globscale*TRANSIT_SPREAD);
   if (transpp->scale&1)
     transpp->scale += 1;
   stubpp->scale = (long) rint(sqrt(maxstubnodes*STUB_DENSITY_FACTOR));

   assert(stubpp->scale < globscale);

   do {
	gb_recycle(topG);
	topG = geo(0,toppp);
	if (topG==NULL) {
	    free(nnodes);
	    free(nstubs);
	    free(nstubnodes);
	    return NULL;       /* don't mess with geo's trouble code */
	}
   } while (!isconnected(topG) && ++numtries < 100);

   if (numtries >= 100) 
	die("Failed to get a connected graph after 100 tries\n");
         /* XXX return NULL + set code */

   topdiam = fdiam(topG);

   /* randomize the number of nodes per transit domain */

   randomize(nnodes,topG->n,transpp->n,RANDMULT*topG->n);

   workparms = *transpp;

   for (i=0,v=topG->vertices;  i<topG->n; i++,v++) {
     
     xoffset = v->xpos - (transpp->scale/2);
     yoffset = v->ypos - (transpp->scale/2);
     if (xoffset < 0)
       xoffset = 0;
     if (yoffset < 0)
       yoffset = 0;
     if ((xoffset + transpp->scale) > globscale)
       xoffset = globscale - transpp->scale;
     if ((yoffset + transpp->scale) > globscale)
       yoffset = globscale - transpp->scale;


     /* v == &topG->vertices[i], represents one whole transit domain	*/
     /* create a connected domain graph */

     workparms.n = nnodes[i];
     newG = geo(0,&workparms);   /* create graph with nnodes[i] nodes */
     if (newG==NULL) return NULL;

     numtries = 0;
     while (!isconnected(newG) && ++numtries<=100) {
       gb_recycle(newG);
       newG = geo(0,&workparms);   /* create graph with nnodes[i] nodes */
       if (newG == NULL) return NULL;
     }
     if (numtries > 100)
       die("Failed to get connected domain graph.");
     if (gb_trouble_code)
       return NULL;
     
     diam = fdiam(newG);

     if (diam > transdiam) transdiam = diam;
     
     v->sub = newG;

     /* randomize the number of stubs per transit node for this t domain */

     randomize(nstubs,newG->n,spx,RANDMULT*newG->n);
        
     /* now for each node k in this T domain, create some S		*/
     /* domains to attach to it.  These (nstubs[k] of 'em) domains 	*/
     /* average stubpp->n nodes per domain.				*/

     workparms = *stubpp;

     for (k=0,dnp=newG->vertices; k<newG->n; k++,dnp++) {