[Commit] nickle/examples apsp.5c,NONE,1.1 shortpaths.5c,NONE,1.1

[Bart Massey]

Committed by: bart

Update of /local/src/CVS/nickle/examples
In directory home.keithp.com:/tmp/cvs-serv7423/examples

Added Files:
	apsp.5c shortpaths.5c 
Log Message:
Added rudimentary SVG output namespace.
Added example: Floyd-Warshall all-pairs shortest-path algorithm.
Added example: program illustrating both of above.



--- NEW FILE: apsp.5c ---
/*
 * All-Pairs Shortest Path Computation
 * using Floyd-Warshall O(n**3) method
 *  CLR 2nd ed p. 632
 * Bart Massey 2004/06
 */
namespace APSP {
    public typedef real distance;

    public typedef struct {
	distance dist;
	int first_hop;
    } shortest_path;

    public shortest_path[*,*]
    compute_paths(distance[*,*] adjacencies) {
	int[*] ns = dims(adjacencies);
	assert(dim(ns) == 2 && ns[0] == ns[1],
	       "ill-conditioned adjacencies");
	int n = ns[0];
	/* set things up */
	shortest_path[n,n] path =
	  {{{dist = -1, first_hop = -1}, ...},...};
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		path[i,j].dist = adjacencies[i,j];
		if (i != j && adjacencies[i,j] >= 0)
		    path[i,j].first_hop = j;
	    }
	}
	/* do the computation */
	for (int k = 0; k < n; k++) {
	    for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
		    if (i == j)
			continue;
		    real dik = path[i,k].dist;
		    real dkj = path[k,j].dist;
		    if (dik <= 0 || dkj <= 0)
			continue;
		    real dij = path[i,j].dist;
		    if (dij <= 0 || dik + dkj < dij) {
			path[i,j].dist = dik + dkj;
			path[i,j].first_hop = path[i,k].first_hop;
		    }
		}
	    }
	}
	return path;
    }
}

--- NEW FILE: shortpaths.5c ---
autoimport APSP;
autoimport PRNG;
autoload SVG;

dev_srandom(32);

typedef struct {
    int x, y;
} point;

int side = 500;
int blot = 10;

SVG::start(stdout, side, side);

point[10] locns = { [i] = (point){x = randint(side), y = randint(side)} };
for (int i = 0; i < dim(locns); i++)
     SVG::spot(stdout, "red", locns[i].x, locns[i].y, blot);

real dist(point p1, point p2) {
    return sqrt((p2.x - p1.x) ** 2 +
		(p2.y - p1.y) ** 2);
}

distance[dim(locns), dim(locns)] adj = {
    [i, j] {
	if (randint(2) == 1)
	    return dist(locns[i], locns[j]);
	return -1;
    }
};
for (int i = 0; i < dim(locns); i++) {
     for (int j = 0; j < i; j++) {
	 adj[j,i] = adj[i,j];
	 if (adj[i,j] > 0)
	     SVG::segment(stdout, "red",
			  locns[i].x, locns[i].y,
			  locns[j].x, locns[j].y);
     }
}

shortest_path[*,*] path = compute_paths(adj);
int i = randint(dim(locns));
SVG::spot(stdout, "green", locns[i].x, locns[i].y, blot);
for (int j = 0; j < dim(locns); j++) {
    if (path[i,j].first_hop == -1)
	continue;
    SVG::spot(stdout, "blue", locns[j].x, locns[j].y, blot);
    for (int k = i; k != j; k = path[k,j].first_hop) {
	int m = path[k,j].first_hop;
	SVG::segment(stdout, "blue",
		 locns[k].x, locns[k].y,
		 locns[m].x, locns[m].y);
    }
}
		 
SVG::stop(stdout);