[comp.hypercube] T or routing question

grunwald@M.CS.UIUC.EDU (07/16/87)

The following program contains functions to compute one of many grey codes
and the inverse function for that grey code.

The loop would be defined as grey(0), grey(1), ...., grey(N-1) for N nodes.
If each node was 'nodeNumber', then you can define: 

#define wrap(x,y,z) ( (x) < y ? y : ( ( (x) > z ) ? z : x ))

	gNode = grey(nodeNumber)
	leftNode = greyinv( wrap(gNode-1, 0, N-1) );
	rightNode = greyinv( wrap(gNode+1, 0, N-1) );

'wrap' simply servers to keep the node numbers in the range 0..N-1. More
complicated structures.

main()
{
    int i;
    for (i = 0; i < 8; i++) {
	printf("%3d: [%3d, %3d] [%3d,%3d]  [%3d, %3d]\n",
	       i,
	       grey(i-1), invgrey(grey(i-1)),
	       grey(i), invgrey(grey(i)),
	       grey(i+1), invgrey(grey(i+1)));
    }
}

grey(i)
int i;
{
    return (i >> 1) ^ i;
}

invgrey(i)
int i;
{
    int j = i;
    do {
	j = ( j >> 1 );
	i ^= j;
    } while (j != 0);
    return(i);
}

dinucci@ogcvax.UUCP (David C. DiNucci) (07/16/87)

In article <ogcvax.1351> I write:
>In article <hubcap.282> gdburns@TCGOULD.TN.CORNELL.EDU (Greg Burns) writes:
>>000 001 011 010 110 111 101 100
>>
>>Given only a bit code difference (src exclusive or dest) we all know how
>>to route on a hypercube.  But how do you determine the route on the above
>>loop?
>
>  . . .
>
>Any solution that doesn't require message passing will beat this
>for setup speed, but I don't know about simplicity.

Message passing can be eliminated easily by just "simulating" the
cube on each node.  This can be done by using something like the
following:  (Unlike the previous alg, this one is untested though
nearly identical)
   dest = 0;
   count = 0;
   do {
     ++count;
     me = dest;
     dest = me ^ (count & -count);
   } while (me != mynode)
   if (count == cubesize) dest = 0;
   /* dest now contains ptr to next guy in the ring */

The previous algorithm is missing the special-case "if" at the end.

Sorry for wasting so much bandwidth on a personal solution to a
problem which has likely been solved by uncountable others (and
probably better).
-- 
Dave DiNucci                    UUCP:  ..ucbvax!tektronix!ogcvax!dinucci
Oregon Graduate Center          CSNET: dinucci@Oregon-Grad.csnet
Beaverton, Oregon