ts.c

it is very important

       /* dnp == &newG->vertices[k] */
       /* k is the index of the current transit node */

       dnp->sub = NULL;

       dnp->xpos += xoffset;     /* position this node in the global plane */
       dnp->ypos += yoffset;

       /* Compute the range of possible offsets for stubs from this node. */
       /* The furthest point of a stub may be up to stubscale from node */
       /* (in each direction).  That is, the origin of the node is in the */
       /* range [max(0,dnp->pos-stubpp->scale),dnp->pos] */

       minx = dnp->xpos - stubpp->scale;
       if (minx < 0) minx = 0;
       miny = dnp->ypos - stubpp->scale;
       if (miny < 0) miny = 0;

       maxx = dnp->xpos;
       if (maxx + stubpp->scale > globscale)
	 maxx = globscale - stubpp->scale;
       maxy = dnp->ypos;
       if (maxy + stubpp->scale > globscale)
	 maxy = globscale - stubpp->scale;

       xrange = maxx - minx;
       yrange = maxy - miny;

       randomize(nstubnodes,nstubs[k],stubpp->n,RANDMULT*nstubs[k]);

       for (j=0; j< nstubs[k]; j++) {	/* create this many stubs */ 
	 workparms.n = nstubnodes[j];	/* with this many nodes */

	 stubG = geo(0,&workparms);
	 if (stubG == NULL) return NULL;

	 while (!isconnected(stubG)) {
	   gb_recycle(stubG);
	   stubG = geo(0,&workparms);
	   if (stubG == NULL) return NULL;
	 }

	 /* compute the offset of this stub from dnp's position */
	 /* These won't be used until the graph is "flattened" in the */
	 /* final stage. */
	 if (xrange)
	   stubG->Gxoff = minx + (random() % xrange);
	 else
	   stubG->Gxoff = minx;
	 if (yrange)
	   stubG->Gyoff = miny + (random() % yrange);
	 else
	   stubG->Gyoff = miny;

	 /* keep track of max of all stub diameters */
	 diam = fdiam(stubG);
	 if (diam > stubdiam) stubdiam = diam;

	 /* add the graph to the node's list */
	 stubG->link = dnp->sub;
	 dnp->sub = stubG;

       } /* create stubs attached to node u */

     } /* for each vertex of this transit domain */

   }  /* for each top-level domain */

   /*
    * Edge length calculations. Main constraints are:
    *  (0) 2ts > topdiam
    *  (1) 2ss > stubdiam
    *  (2) 2tt > transdiam
    *  (3) 2ts > topdiam*tt + (tipdiam+1)*transdiam  [implies (0)]
    *  (4) 2ss > 2stubdiam+2ts+(topdiam)tt+(topdiam+1)transdiam
    *      =
    *       ss > stubdiam + ts + (topdiam)tt/2 + (topdiam+1)transdiam/2
    *      => 
    *       ss > stubdiam
    *      => {2ss > ss, transitivity >}
    *       2ss > stubdiam [i.e. (1)]
    *  (5) ss ~ 2ts + e [desirable but may or may not always be true]
    *  where 
    *  tt = length of edges connecting transit domains
    *  ts = length of edges connecting transits to stubs
    *  ss = length of (random) edges connecting stubs to stubs.
    *
    *  Noting that 2*((X>>1)+1) > X for nonnegative X, we define
    *
    *	halfup(x) to be (((x)>>1)+1)
    */

    tt = halfup(transdiam);
    ts = halfup(topdiam*tt) + halfup((topdiam+1)*transdiam);
    ss = stubdiam  + 2*ts;

   /*
    *  Note that all intra-domain edges can keep original length!
    */

   /* Now we can flatten the hierarchy of graphs into the final Graph */

   finalG = gb_new_graph(totalnodes);
   base = 0;
   for (dom=0,v=topG->vertices; dom<topG->n; dom++,v++) { /* for each domain */
	/* v = &topG->vertices[dom] */

	dgp = v->sub;	/* dgp points to the "current" domain graph */

	copyedges(dgp,finalG,base);	/* copy in edges of the domain */
	/* NB lengths of edges do not change      */
	/* Policy weights are set to unity by copyedges() */

	base += dgp->n;			/* account for the domain's nodes */

	/* now go through the nodes of this domain */
	for (dnn=0,dnp=dgp->vertices; dnn<dgp->n; dnn++,dnp++) {

	    /* name of this (transit) node */

	    sprintf(dnodename,"T:%d.%d",dom,dnn);
	    dnp->flat->name = gb_save_string(dnodename);
	    
	    /* position of this node */
	    dnp->flat->xpos = dnp->xpos;
	    dnp->flat->ypos = dnp->ypos;

	    /* get ready for stubs */

	    strcpy(snodename,dnodename);
	    snodename[0] = 'S';	/* change transit to stub */
	    dnamelen = strlen(dnodename);

	    /* now deal with stubs */
	    snum = 0;
	    sgp = dnp->sub;
	    while (sgp) {
	      Vertex *anp;

		copyedges(sgp,finalG,base);

		for (snn=0,snp=sgp->vertices; snn<sgp->n; snn++,snp++) {

		    /* name each node */
		    sprintf(snodename+dnamelen,"/%d.%d",snum,snn);
		    snp->flat->name = gb_save_string(snodename);

                    /* and position it correctly */
		    snp->flat->xpos = snp->xpos + sgp->Gxoff;
		    snp->flat->ypos = snp->ypos + sgp->Gyoff;
		    assert(snp->flat->xpos < globscale);
		    assert(snp->flat->ypos < globscale);


	        } /* for each node of this stub */

		attachnode = gb_next_rand()%sgp->n;
                anp = finalG->vertices+(base+attachnode);
	        assert((dnp->flat-finalG->vertices) < (anp-finalG->vertices));
		gb_new_edge(dnp->flat,anp, idist(dnp->flat,anp));
                dnp->flat->arcs->policywt = ts;
	        (dnp->flat->arcs+1)->policywt = ts;

		base += sgp->n;	/* account for this stub's nodes */

		sgp = sgp->link;

		snum++;

	    }	/* for each stub graph of this node */

	}  /* for each node of this domain */

   }	/* for each domain */

   if (base != totalnodes) {
	fprintf(stderr,"incorrect node total: base=%d, totalnodes=%d\n",
		base,totalnodes);
	exit(3);
   }

   /* Now we have to place the top-level (interdomain) edges	*/
   /* Can do this now because each "old" node has a pointer to	*/
   /* corresponding node in the "flat" graph, also each node has*/
   /* a hierarchical name. */

   for (dom=0,v=topG->vertices; dom<topG->n; dom++,v++) { /* for each domain */
	dgp = v->sub;
	for (a=v->arcs;a;a=a->next) {	 /* add edges to other domains */
	    /* choose an endpoint in each graph */
	    dnp = dgp->vertices + (gb_next_rand()%dgp->n);
	    ddgp = a->tip->sub;
	    ddnp = ddgp->vertices + (gb_next_rand()%ddgp->n);
	    fp = dnp->flat;
	    tp = ddnp->flat;
	    if (tp < fp) {
	      tmp = fp;
	      fp = tp;
	      tp = tmp;
	    }
	    gb_new_edge(fp,tp,idist(fp,tp));
	    /* fp < tp */
	    fp->arcs->policywt = tt;
	    (fp->arcs+1)->policywt = tt;
        }
   }


   /* Next add some RANDOM transit-stub edges.			*/
   for (i=0; i<nrants; i++) {
	dnp = topG->vertices + (gb_next_rand()%topG->n); /*choose dom*/
	dgp = dnp->sub;
	dnp = dgp->vertices[gb_next_rand()%dgp->n].flat; /* and a node */
	assert(dnp->name[0]=='T');	/* sanity check */

	do {	/* choose S node NOT already connected to this T dom node */
	   snp = finalG->vertices + (gb_next_rand()%finalG->n);
	} while (!td_OK(snp,dnp));
	if (snp < dnp) {     /* we require dnp < snp */
	  tmp = dnp;
	  dnp = snp;
	  snp = tmp;
	}
	gb_new_edge(dnp,snp,idist(dnp,snp));
	dnp->arcs->policywt = ts;
	(dnp->arcs+1)->policywt = ts;
   }


   /* Next, add some RANDOM stub-stub edges.			*/
   /* Don't add edges between nodes in the same stub domain;	*/
   /* anything else is OK. */

   for (i=0; i<nranss; i++) {
	do {
	    /* pick two nodes at random that aren't in the same stub */
	    dnp = finalG->vertices + (gb_next_rand()%finalG->n);
	    ddnp = finalG->vertices + (gb_next_rand()%finalG->n);
	} while (!stubs_OK(dnp,ddnp));
	if (ddnp < dnp) {  /* required is dnp < ddnp */
	  tmp = dnp;
	  dnp = ddnp;
	  ddnp = dnp;
	}
	gb_new_edge(dnp,ddnp,idist(dnp,ddnp));
	/* fp < tp */
	dnp->arcs->policywt = ss;
	(dnp->arcs+1)->policywt = ss;
   }


   /* Finally, put the parameter info in the "id" string of the new graph */
   sprintf(finalG->id,"transtub(%ld,%d,%d,%d,",
	seed,spx,nrants,nranss);
   i = strlen(finalG->id);
   i += printparms(dnodename,toppp);
   if (i<ID_FIELD_SIZE) {
	strcat(finalG->id,dnodename);
	finalG->id[i++] = ',';
	finalG->id[i] = (char) 0;
        i += printparms(dnodename,transpp);
        if (i<ID_FIELD_SIZE) {
	    strcat(finalG->id,dnodename);
	    finalG->id[i++] = ',';
	    finalG->id[i] = (char) 0;
	    i += printparms(dnodename,stubpp);
            if (i<ID_FIELD_SIZE) {
		strcat(finalG->id,dnodename);
		finalG->id[i++] = ')';
                if (i<ID_FIELD_SIZE)
		    finalG->id[i] = (char) 0;
	    } else {
		strncat(finalG->id,dnodename,
			(ID_FIELD_SIZE-strlen(finalG->id)));
	    }
        } else
	    finalG->id[strlen(finalG->id)] = (char) 0;
   } else
	finalG->id[strlen(finalG->id)] = (char) 0;

   strcpy(finalG->util_types,TS_UTIL);
   finalG->Gscale = globscale;		/* uu */
   finalG->MaxTdiam = transdiam;	/* xx */
   finalG->MaxSdiam = stubdiam;		/* yy */
   finalG->Topdiam = topdiam;		/* zz */

   /* CLEAN UP: free up all the memory we grabbed. */

   for (v=topG->vertices; v<topG->vertices+topG->n; v++) {
	dgp = v->sub;
	for (dnp = dgp->vertices; dnp<dgp->vertices+dgp->n; dnp++) {
	    sgp = NULL;	
	    tempg = dnp->sub;
	    while (tempg) {
		sgp = tempg;
		tempg = tempg->link;
		gb_recycle(sgp);
	    }
	}
	gb_recycle(dgp);
   }
   gb_recycle(topG);

   free((char *)nstubnodes);
   free((char *)nstubs);
   free((char *)nnodes);	/* free the last little bit */

   /* return the new graph! */
   return finalG;

}  /* ts() */

/* return true if it's OK to put an edge between stub node snp and	*/
/* transit node dnp.   The criteria are:				*/
/*    - snp is a stub node						*/
/*    - dnp is a transit node 						*/
/*    - the stub domain is not administratively "under" this transit    */
/*      node.								*/
int
td_OK(Vertex *snp,Vertex *dnp)
{
int dlen, slen;

    if (*snp->name != 'S') return 0;
    dlen = strlen(dnp->name+2);
    slen = strcspn(snp->name+2,"/");

    /* if the domain prefix is the same, it's NOT OK */
    return ((dlen != slen) || strncmp(dnp->name+2,snp->name+2,dlen));
}

/* OK to put an extra edge between two stub nodes, as long as they are	*/
/* not already in the same stub domain.  This is checked by the initial	*/
/* prefix of their names, i.e. the part before the final '.'		*/
/* if these two strings differ, it's OK.				*/
int
stubs_OK(Vertex *snp0,Vertex *snp1)
{
int slen0, slen1;
char *cp;

    if (*snp0->name != 'S' ||
        *snp1->name != 'S')
	return 0;

    /* find the last occurrence of "." in each string */
    /* I don't trust strrchr(), gdb doesn't seem to either */
    slen0 = strlen(snp0->name);
    cp = snp0->name + slen0;	/* initially points to null */
    while (*cp != '.' && --cp > snp0->name) slen0--;

    slen1 = strlen(snp0->name);
    cp = snp1->name + slen1;	/* initially points to null */
    while (*cp != '.' && --cp > snp1->name) slen1--;


    /* strncmp returns nonzero if strings differ, which means "OK" */
    return strncmp(snp0->name,snp1->name,(slen0>slen1?slen1:slen0));
}