Parallel Computing
 CSE Home Other Quarters ZPL About Us Search Contact Info

 Syllabus Programming with ZPL Assignments Assignment 1 (and soln) Assignment 2 (html) (pdf) (ppt) Assignment 3

# Assignment 3 Solution

The strategy for this solution is to use a boolean propogation map that identifies all the points water can flow down to. In each iteration, the propogation map is extended until no change is made. To extend the propogation map, consider some cell, (X, Y). To determine whether (X, Y) should be set to true in the next iteration, look at all the neighbors of (X, Y). If it has a neighbor which is already set to true, and whose elevation is higher (or equal), then that means water can get to (X, Y). If the elevation matrix is A and the propogation matrix is Dn, then this is computed using the expression:
```Dn := Dn | (A<=A@no & Dn@no) | (A<=A@ne & Dn@ne)
| (A<=A@ea & Dn@ea) | (A<=A@se & Dn@se)
| (A<=A@so & Dn@so) | (A<=A@sw & Dn@sw)
| (A<=A@we & Dn@we) | (A<=A@nw & Dn@nw);
```
Note that this computation is written from the perspective of the cell being propogated to, not the cell we are propogating from. It essentially asks, "is my neighbor in the propogation map and can water flow from my neighbor to me."

This allows us to compute all the cells water can get to from the high point. However, it may pass off the grid or pool up at a local minima. In order to account for this, we compute basically the same function, but starting at the low point(s) and working up. We then AND these two maps together to get only those cells on a path from high to low. This requires setting a border around the matrix to avoid incorrect propogation. Making reasonable assumptions about the minimum and maximum values we'll encounter, we handle this with two matrices Aup and Adn. Adn has a border of 0s (since we can never propogate down from a zero cell) and Aup has a border of 100,000( ensuring that we'll never propogate up from a border cell.) It might be slightly more efficient to completely compute the down propogation map with one loop and then the up propogation map in a separate loop, as one map may require more iterations to complete. This would also remove the need for both the Aup and Adn matrices, since a single bordered matrix could be used and the border just set appropriately for the down computation and then reset for the up computation.

## Code

Adding code to read an input file, display the map at the end, etc. we get:
```program drainage;

prototype GetDim(infile:file):integer;

config var
filename: string = "A.mat";

default_size:integer = 5;
m:integer = GetDim(infile);
n:integer = GetDim(infile);

region	  R = [1..m, 1..n];
Rbig = [0..m+1, 0..n+1];
direction  no = [-1, 0];
ne = [-1, 1];
ea = [ 0, 1];
se = [ 1, 1];
so = [ 1, 0];
sw = [ 1,-1];
we = [ 0,-1];
nw = [-1,-1];
var	  A : [R] double;
Tu,Td,Up,Dn : [R] boolean;

procedure drainage();
var
[R] begin

Up := 0; Dn := 0;
Up := A=(min<<A); -- Set low point(s) to true
Dn := A=(max<<A); -- Set high point(s) to true
[Rbig] Aup := 100000; -- Set up borders
Aup := A;
repeat
Tu := Up; Td := Dn; -- Remember previous iteration
Up := Up | (Aup>=Aup@no & Up@no) | (Aup>=Aup@ne & Up@ne)
| (Aup>=Aup@ea & Up@ea) | (Aup>=Aup@se & Up@se)
| (Aup>=Aup@so & Up@so) | (Aup>=Aup@sw & Up@sw)
| (Aup>=Aup@we & Up@we) | (Aup>=Aup@nw & Up@nw);
until ! |<<((Tu != Up) | (Td != Dn));  -- Any change from before?

writeln("Drainage is:\n", Up & Dn);
end;

var step:double;
begin
if (infile != znull) then
end;
end;

procedure GetDim(infile:file):integer;
var dim:integer;
begin
dim := 0;
if (infile != znull) then
end;
return dim;
end;
```

## Test Cases

The test cases we used are:
• mat01.in - Basic path from high to low with a moat around the high point and a berm restricting the path to the low point.
```Input:
10 10
51 51 51 51 51 50 50 50 50 50
51 50 50 50 51 50 50 50 50 50
51 50 52 50 51 50 50 50 50 50
51 50 50 50 51 51 50 50 50 50
51 51 51 51 50 51 51 50 50 50
50 50 50 51 51 50 51 51 50 50
50 50 50 50 51 51 50 51 51 50
50 50 50 50 50 51 51 50 51 51
50 50 50 50 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51

Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
```
• mat02.in - From 2 separate high points to the same low point
```Input:
10 10
51 51 51 51 51 51 51 51 51 51
51 50 50 50 51 51 50 50 50 51
51 50 52 50 51 51 50 52 50 51
51 50 50 50 51 51 50 50 50 51
51 51 51 51 50 50 51 51 51 51
50 50 50 51 51 50 51 51 50 50
50 50 50 50 51 51 50 51 51 50
50 50 50 50 50 51 51 50 51 51
50 50 50 50 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51

Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0

mat03.in - From 2 separate high points to two separate low points
Input:
10 10
51 51 51 51 51 51 51 51 51 51
51 50 50 50 51 51 50 50 50 51
51 50 52 50 51 51 50 52 50 51
51 50 50 50 51 51 50 50 50 51
51 51 50 51 51 51 51 50 51 51
50 51 50 51 51 51 51 50 51 51
50 51 50 51 51 51 51 50 51 51
50 51 50 51 51 51 51 50 51 51
50 49 51 51 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51

Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0

mat04.in - A separate path to a local minimum (should not be taken).
Input:
10 10
53 53 53 53 53 53 53 53 53 53
53 50 50 50 53 50 53 53 53 53
53 50 55 50 53 53 53 53 53 53
53 52 50 50 53 53 53 53 53 53
53 51 53 53 50 53 53 53 53 53
53 50 53 53 53 50 53 53 53 53
50 50 53 53 53 53 50 53 53 50
53 53 53 53 53 53 53 50 53 53
53 53 53 53 53 53 53 53 49 53
53 53 53 53 53 53 53 53 53 53

Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0

mat05.in - A path from the low point to a local maximum (should not be taken)
Input:
10 10
53 53 53 53 53 53 53 53 53 53
53 50 50 50 53 50 53 53 53 53
53 50 55 50 53 53 53 53 53 53
53 50 50 50 53 53 53 53 53 53
53 53 53 53 50 53 53 53 53 53
53 53 53 53 53 50 53 53 53 53
53 53 53 53 53 53 50 53 53 53
53 53 53 53 53 53 53 49 53 53
53 53 53 53 53 53 53 53 50 53
53 53 53 53 53 53 53 53 53 53

Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

mat06.in - wrap-around alternate path to min (path goes down from moat
and then coes across from column 0 to column 9.  Would work if matrix
was a torus, but we shouldn't take it, since we're not wrapping around.)
Input:
10 10
53 53 53 53 53 53 53 53 53 53
53 50 50 50 53 50 53 53 53 53
53 50 55 50 53 53 53 53 53 53
53 52 50 50 53 53 53 53 53 53
53 51 53 53 50 53 53 53 53 53
53 50 53 53 53 50 53 53 53 53
50 50 53 53 53 53 50 53 50 50
53 53 53 53 53 53 53 49 53 53
53 53 53 53 53 53 53 53 50 53
53 53 53 53 53 53 53 53 53 53

Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

mat07.in - another wrap-around alternate path to min
Input:
10 10
53 53 53 53 53 53 53 53 53 53
53 50 50 50 53 50 53 53 53 53
53 50 55 50 53 53 53 53 53 53
53 52 50 50 53 53 53 53 53 53
53 51 53 53 50 53 53 53 53 53
53 50 53 53 53 50 53 53 53 53
50 50 53 53 53 53 50 53 53 50
53 53 53 53 53 53 53 49 53 50
53 53 53 53 53 53 53 53 50 53
53 53 53 53 53 53 53 53 53 53

Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

mat08.in - Low point in the upper right hand corner is unreachable.
Input:
10 10
51 51 51 51 51 50 50 50 50 50
51 50 50 50 51 50 50 50 49 50
51 50 52 50 51 50 50 50 50 50
51 50 50 50 51 51 50 50 50 50
51 51 51 51 50 51 51 50 50 50
50 50 50 51 51 50 51 51 50 50
50 50 50 50 51 51 50 51 51 50
50 50 50 50 50 51 51 50 51 51
50 50 50 50 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51

Result:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0

mat09.in - Low and high points are disconnected, no path exists.
Input:
10 10
51 51 51 51 51 50 50 50 50 50
51 50 50 50 51 50 50 50 50 50
51 50 53 50 51 50 50 50 50 50
51 50 50 50 51 51 50 50 50 50
51 51 51 51 50 51 51 50 50 50
50 50 50 51 51 52 51 51 50 50
50 50 50 50 51 51 50 51 51 50
50 50 50 50 50 51 51 50 51 51
50 50 50 50 50 50 51 51 49 51
50 50 50 50 50 50 50 51 51 51

Result:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

```

 Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to carlson]