Chapter 6


Transportation Routes and Network Algorithms


Technical Terms:

adjacent, breadth-first, depth-first, Hasse's algorithm, matrix, spanning tree, walk.

Link to Chapter 6 Complement


Alternate Routing Analysis: Hasse's Algorithm

The measurement of spatial proximity often rests on measures of shortest total distance. In real-world applications, it can happen that a disaster, or some other disruption, forces a need for alternate routing that only the instant before was not needed. Planning for once-in-a-lifetime (or longer) events naturally tends not to be a high priority for municipal authorities. One strategy for linking the temporal and spatial component of transportation routing problems is illustrated below using an algorithm of Hasse (Hasse, 1961). Geographer John Nystuen has been teaching urban planning students the merits of considering Hasse's algorithm and related graph theoretical material for a couple of decades. Nystuen suggested considering the Los Angeles freeways, using Hasse's algorithm, in their post-earthquake state of disarray following a disastrous earthquake on January 17, 1994 (Arlinghaus, Arlinghaus, Harary, and Nystuen, 1994). We offer this unusual application as a complement to traditional traffic modeling. In computer science, there are two better-known algorithms for computing shortest distance between nodes, Dijkstra's algorithm and Floyd's algorithm. For a discussion of reasons for preferring one of these algorithms to another, see the complementary Chapter 6.

An algebraic device introduced by Maria Hasse (Hasse, 1961; Harary, Norman, and Cartwright, 1965) offers a method for finding the shortest distance between any two nodes in a network of n nodes when given only distances between adjacent nodes. The algorithm is one that focuses on structure alone, and it is therefore spatial; when distances are measured in time, a temporal element is introduced.  The manipulation is similar in form to that used to multiply matrices, given two n x n matrices A and B. To find the entries in their Hasse-sum, matrix C, take the minimum of the row-by-column sums; thus, the entry

c2,2 = min {a2,1+b1,2, a2,2+b2,2, a2,3+b3,2, ... , a2,n+bn,2}

is the entry in the second row, second column of the Hasse-sum matrix formed from the matrices A and B.

It is often tedious to calculate Hasse-sums of matrices. To facilitate the calculation of these sums, a Pascal program was written to produce integral results (written by W. C. Arlinghaus; originally presented on a poster by Arlinghaus, Arlinghaus, and Nystuen, "Elements of Geometric Routing Theory—II" Association of American Geographers, National Meetings, Toronto, Ontario, April 1990).



program hasse(input,output);

const max=999999;

n=24;

type hed=array[1..n,1..n] of integer;

var a:array[1..n] of hed;

done:boolean;

i,j,k,num:integer;

procedure print(matrix:hed);

begin

for i:=i to n do

begin

for j:=1 to n do

if matrix[i,j]=max then write (' *')

else write(matrix[i,j]:4);

writeln

end

end;

procedure hedsum(power, init:hed;var next:hed;var flag:boolean);

var row,col,min,middle,temp:integer;

begin

flag:=true;

for row:=1 to n do

for col:=1 to n do

begin

min:=power[row,col];

for middle:=1 to n do

begin

temp:=power[row,middle]+init[middle,col];

if temp<min the min:=temp

end;

next[row,col]:=min;

if next[row,col]<>power[row,col] then flag:=false;

end

end;

{main program}

begin

for i:=1 to n do for j:=1 to n do a[1][i,j]:=max;

for i:=1 to n do a[1][i,i]:=0;

repeat

readln(i,j,num);

a[1][i,j]:=num;

a[1][j,i]:=num;

until eof;

page; writeln('this is the initial matrix');writeln;

print(a[1]);

k:=0;

repeat

k:=k+1;

hedsum(a[k],a[1],a[k+1],done);

page; writeln('this is power',k+1:5); writeln;

print(a[k+1]);

until (done) or (k=n-1);

writeln;

writeln('the number of steps was', k:5)

end.


The results below show the outcome of applying this tool to one change in the Los Angeles freeway pattern following a devastating earthquake (January 17, 1994) (Arlinghaus, Arlinghaus, Harary, and Nystuen, 1994).

Los Angeles, 1994

When an earthquake caused a disastrous collapse of a span of the Santa Monica freeway, according to television reports of the time the world's busiest freeway (carrying an estimated 300,000 vehicles per weekday), municipal authorities managed to keep the city moving. Their focused approach employed a well-balanced combination of alternate routing strategies as outside forecasters of doom predicted massive gridlock that did not occur. In the analysis below, we test Hasse's algorithm against the freeway exit adjacency configuration changed by the earthquake and interpret the results. Indeed, what would a forecaster who used the Hasse algorithm have predicted in this situation?

Pre-earthquake configuration

The graph in Figure 6.1 shows a portion of the Los Angeles freeway system, and nearby major surface arterials, linking Los Angeles International Airport (LAX) to the Central City (CC). It is natural to introduce alternate routes to freeways along surface roads that are already present. Earlier mathematical literature is replete with rerouting problems following edge deletion (Menger, 1927; Ford and Fulkerson, 1962). One set of major surface routes is added to the map in Figure 6.1 to offer a number of different routes.  We limited our interests to consider what sort of impact the partial closing of the Santa Monica freeway might have on travel times to and from the airport and the downtown region. Nodes represent all locations for access to other roads.  There is no access from one road to another except at nodes in Figure 6.1.  First, we consider the freeway and surface road graph in its pre-earthquake configuration.

Image

Figure 6.1.  Los Angeles freeway and major surface road graph:  pre-earthquake configuration.  LAX denotes Los Angeles International Airport. CC denotes the Central City. North is at the top.

The matrix, A, in Figure 6.2 displays time-distances in quarter minutes, in tabular form across the network shown in Figure 6.1. The entry of 12 in the first row, second column indicates that it takes 12 quarter-minutes to travel from the node labeled 1 to the node labeled 2. Thus this matrix has a value x in row i, column j if there is a direct route of x quarter minutes from i to j. This is an extension of the idea of adjacency matrix for weighted graphs. Travel times were calculated from distances in the 1993 Rand McNally Road Atlas, assuming (from reports from Nystuen) an average speed of 40 mph. A zero in this matrix indicates that there are zero quarter-minutes required as travel time--thus, zeroes appear in this matrix only along the main diagonal. Nodes are treated as points within which no travel is possible. An asterisk indicates that there is no direct linkage, via a single edge, between corresponding entries:  an asterisk in the (1,3) position indicates that there is no single edge of the graph linking node 1 to node 3 although of course a sequence of two edges does join them.

0

12

*

*

18

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

12

0

18

*

*

*

*

*

*

*

*

*

*

*

*

*

6

*

*

*

*

*

*

*

*

18

0

24

*

*

*

*

*

*

*

*

*

*

*

*

*

18

*

*

*

*

*

*

*

*

24

0

*

30

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

18

*

*

*

0

*

12

*

*

*

*

*

*

*

*

*

12

*

*

*

*

*

*

*

*

*

*

30

*

0

*

12

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

*

12

*

0

*

6

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

*

12

*

0

*

9

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

*

6

*

0

*

6

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

*

9

*

0

*

6

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

*

6

*

0

*

6

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

*

6

*

0

*

*

*

6

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

*

6

*

0

12

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

12

0

12

*

*

*

*

*

*

*

3

*

*

*

*

*

*

*

*

*

*

*

*

*

*

12

0

21

*

*

*

*

*

*

*

3

*

*

*

*

*

*

*

*

*

*

*

6

*

*

21

0

*

*

*

*

*

*

*

*

*

6

*

*

12

*

*

*

*

*

*

*

*

*

*

*

0

12

9

*

*

*

*

*

*

*

18

*

*

21

*

*

*

*

*

*

*

*

*

*

12

0

*

9

*

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

9

*

0

12

9

*

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

9

12

0

*

9

*

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

9

*

0

12

6

*

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

9

12

0

*

12

*

*

*

*

*

*

*

*

*

*

15

*

*

3

*

*

*

*

*

*

6

*

0

12

*

*

*

*

*

*

*

*

*

*

*

21

*

*

3

*

*

*

*

*

*

12

12

0

Figure 6.2. This figure displays a matrix showing travel times in one-quarter minutes for the Los Angeles freeway and major surface road network, pre-earthquake configuration. A numerical entry in position (i, j) indicates that there is a single edge in Figure 6.1 joining node i to node j. The size of the number represents travel time. An asterisk in the (i, j) position indicates that there is no single edge joining nodes i and j but that there may be multiple-edge walks linking i and j. Cells with background color are cells with entries that are different in pre- and post-earthquake calculations.

Higher Hasse-powers of the matrix A in Figure 6.2 count numbers of walks of longer length. The matrix A2 (formed by using the Hasse operator on A and A) counts walks of two edges as well as those of one edge. Thus, in A2 one would expect to find an entry indicating the total time to travel from node 1 to node 3:  indeed, the travel time of 30 quarter-minutes from nodes 1 to 3 is, in A2, the sum of the travel times from 1 to 2 (12 quarter-minutes) and from 2 to 3 (18 quarter-minutes). The entries from A also remain in this matrix. Once an integral entry enters a Hasse matrix in the (i, j) position, it remains there and no further calculation takes place in that cell. Thus, A2 contains all the integral entries of A as well as integral entries representing all the two-edge walks in the network. Similarly, A3 contains all the entries of A2 and of A as well as integral entries representing all three-edge walks in the network. The number of asterisks in the matrix decreases as more integral entries are recorded. Higher Hasse powers continue to be calculated until all cells have an integral entry. Then the procedure is run one more time. If the result is a duplicate of the previous stage, the process is complete. In the case of the Los Angeles Freeway network, all cells have integral entries in A8.

In the animated matrix of Figure 6.3, all eight Hasse-sum matrices have been entered.  Integral values enter the animation at different times depending on when they enter the sequence of matrices A to A8.  Entries in red are the initial values from matrix A. Reload this page when ready to look at this figure. Each cell contains an animated .gif of 30 seconds length. Earlier integral entries remain fixed until all cells have an integral entry.

Animated Hasse-sum matrix.

Figure 6.3.  Animated Hasse-sum matrix contains eight different matrices. Integral values enter the animation at different times depending on when they enter the sequence of matrices A to A8. Entries in red are the initial values from matrix A. Reload this page when ready to look at this figure. Each cell contains an animated .gif of 30 seconds length. Earlier integral entries remain fixed until all cells have an integral entry. Cells with background color are cells with entries that are different in pre- and post-earthquake calculations.

The Hasse operator always selects the shortest path if more than one is available. Other algorithms execute similar calculations; however, Floyd's algorithm provides easy display of lengths only (and not the components that compose them), while Dijkstra's algorithm is not designed for easy display of results but does permit the determination of the actual position of the shortest path. Both of these algorithms require the same number of steps independent of the actual data; Hasse's does not, and the animation shows that clearly—it stops shorter than would Floyd's or Dijkstra's in many situations. A static version of the final matrix is presented in Figure 6.4. Further detail has been published elsewhere (Harary, Norman, and Cartwright, 1960; Arlinghaus, Arlinghaus, and Nystuen, 1990).

0

12

30

54

18

51

30

60

36

69

42

75

48

45

57

78

18

30

27

39

36

48

42

54

12

0

18

42

18

39

30

48

36

57

42

63

45

33

45

66

6

18

15

27

24

36

30

42

30

18

0

24

36

39

48

48

54

57

60

63

63

51

51

69

24

18

33

27

42

36

48

48

54

42

24

0

60

30

72

42

78

51

84

57

87

75

75

63

48

42

57

51

66

60

72

72

18

18

36

60

0

45

12

54

18

63

24

69

30

39

51

72

12

24

21

33

30

42

36

48

51

39

39

30

45

0

57

12

63

21

69

27

72

60

51

33

33

21

42

30

51

39

57

48

30

30

48

72

12

57

0

48

6

54

12

60

18

30

42

63

24

36

15

27

21

33

27

39

60

48

48

42

54

12

48

0

54

9

60

15

63

51

39

21

42

30

33

21

42

30

48

36

36

36

54

78

18

63

6

54

0

48

6

54

12

24

36

57

30

42

21

33

15

27

21

33

69

57

57

51

63

21

54

9

48

0

54

6

54

42

30

12

51

39

42

30

33

21

39

27

42

42

60

84

24

69

12

60

6

54

0

48

6

18

30

51

36

48

27

39

21

33

15

27

75

63

63

57

69

27

60

15

54

6

48

0

48

36

24

6

57

45

48

36

39

27

33

21

48

45

63

87

30

72

18

63

12

54

6

48

0

12

24

45

39

51

30

42

21

33

15

27

45

33

51

75

39

60

30

51

24

42

18

36

12

0

12

33

27

39

18

30

9

21

3

15

57

45

51

75

51

51

42

39

36

30

30

24

24

12

0

21

39

33

30

24

21

15

15

3

78

66

69

63

72

33

63

21

57

12

51

6

45

33

21

0

60

51

51

42

42

33

36

24

18

6

24

48

12

33

24

42

30

51

36

57

39

27

39

60

0

12

9

21

18

30

24

36

30

18

18

42

24

21

36

30

42

39

48

45

51

39

33

51

12

0

21

9

30

18

36

30

27

15

33

57

21

42

15

33

21

42

27

48

30

18

30

51

9

21

0

12

9

21

15

27

39

27

27

51

33

30

27

21

33

30

39

36

42

30

24

42

21

9

12

0

21

9

27

21

36

24

42

66

30

51

21

42

15

33

21

39

21

9

21

42

18

30

9

21

0

12

6

18

48

36

36

60

42

39

33

30

27

21

33

27

33

21

15

33

30

18

21

9

12

0

18

12

42

30

48

72

36

57

27

48

21

39

15

33

15

3

15

36

24

36

15

27

6

18

0

12

54

42

48

72

48

48

39

36

33

27

27

21

27

15

3

24

36

30

27

21

18

12

12

0

Figure 6.4. This figure shows the eighth iterate Hasse-sum matrix, A8, for the Los Angeles freeway and major surface road network, pre-earthquake configuration. Cells with background color are cells with entries that are different in pre- and post-earthquake calculations.

Post-earthquake configuration

When the Santa Monica freeway collapsed (red swath in Figure 6.5; Figure 6.6 suggests the extent of the damage), all freeway-only traffic was forced along the green route in Figure 6.5. No traffic could move beyond the freeway exits represented as nodes 4 and 6 in Figure 6.5. Previously, traffic might have followed either the green or red freeway routes; the earthquake destroyed the red-only route. In either pre- or post-earthquake scenarios, a number of major surface route traverses are available, as well.

Image

Image

Figure 6.5.  Los Angeles freeway and major surface road graph:  post-earthquake (January 17, 1994) configuration. Red swath denotes the collapse of the Santa Monica freeway. LAX denotes Los Angeles International Airport. CC denotes the Central City. North is at the top.

Figure 6.6. Drawing, suggesting damage to the Los Angeles freeways, based on a photo from the New York Times, Tuesday, January 18, 1994.

An initial matrix, B (different from A), is required to capture the linkage pattern between LAX and CC following the 1994 earthquake (Figure 6.7). The matrix B, representing the graph in Figure 6.5, indicates a new adjacency pattern; in A, the 4th row, 6th column contained a value of 30 to represent the direct linkage between nodes 4 and 6. The corresponding entry (yellow cells in all matrices) in matrix B is an asterisk; there is no longer a walk, of a single graphical edge, available between nodes 4 and 6. When Hasse's algorithm is run using B (Figure 6.7), instead of A (Figure 6.2), as the initial matrix, the iteration requires the same number of stages; however, some of the entries (cells with blue backgrounds) are larger in B than in A, reflecting the need for longer paths to provide alternate routes around the earthquake-altered freeway.

0

12

*

*

18

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

12

0

18

*

*

*

*

*

*

*

*

*

*

*

*

*

6

*

*

*

*

*

*

*

*

18

0

24

*

*

*

*

*

*

*

*

*

*

*

*

*

18

*

*

*

*

*

*

*

*

24

0

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

18

*

*

*

0

*

12

*

*

*

*

*

*

*

*

*

12

*

*

*

*

*

*

*

*

*

*

*

*

0

*

12

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

*

12

*

0

*

6

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

*

12

*

0

*

9

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

*

6

*

0

*

6

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

*

9

*

0

*

6

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

*

6

*

0

*

6

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

*

6

*

0

*

*

*

6

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

*

6

*

0

12

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

12

0

12

*

*

*

*

*

*

*

3

*

*

*

*

*

*

*

*

*

*

*

*

*

*

12

0

21

*

*

*

*

*

*

*

3

*

*

*

*

*

*

*

*

*

*

*

6

*

*

21

0

*

*

*

*

*

*

*

*

*

6

*

*

12

*

*

*

*

*

*

*

*

*

*

*

0

12

9

*

*

*

*

*

*

*

18

*

*

21

*

*

*

*

*

*

*

*

*

*

12

0

*

9

*

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

9

*

0

12

9

*

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

9

12

0

*

9

*

*

*

*

*

*

*

*

*

*

15

*

*

*

*

*

*

*

*

*

9

*

0

12

6

*

*

*

*

*

*

*

*

*

*

21

*

*

*

*

*

*

*

*

*

9

12

0

*

12

*

*

*

*

*

*

*

*

*

*

15

*

*

3

*

*

*

*

*

*

6

*

0

12

*

*

*

*

*

*

*

*

*

*

*

21

*

*

3

*

*

*

*

*

*

12

12

0

Figure 6.7.  This figure displays a matrix showing travel times in one-quarter minutes for the Los Angeles freeway and major surface road network, post-earthquake configuration. A numerical entry in position (i, j) indicates that there is a single edge in Figure 6.5 joining node i to node j. The size of the number represents travel time. An asterisk in the (i, j) position indicates that there is no single edge joining nodes i and j; there may, however, be multiple-edge walks linking i and j. Cells with background color are cells with entries that are different in pre- and post-earthquake calculations.

The animated matrix in Figure 6.8 shows the only differences, pre-earthquake (top row in Figure 6.8) and post-earthquake (bottom row in Figure 6.8) of time required to traverse the graph to or from LAX to CC. Redundancy in connection across interior surface routes kept most entries in the matrix the same. One would expect delays directly related to earthquake damage associated with the cells with background color (yellow or blue).

Animated Hasse-sum matrices.

Figure 6.8.  Animated Hasse-sum matrices.  The first row in this animation shows the animated fourth row of A, A2, ... , A8; the second row shows the animated fourth row of B, B2, ... , B8.

In the eighth iteration (Figure 6.9), the B-iterate contains entries in the (4,6), (4,8), (4,10), (4,12), and (4,16) positions that are about 30 quarter-minutes larger than are the entries in the corresponding eighth A-iterate (Figure 6.4). This numerical increase comes purely from spatial pattern--it does not address the natural increase in congestion that one might also expect.

0

12

30

54

18

51

30

60

36

69

42

75

48

45

57

78

18

30

27

39

36

48

42

54

12

0

18

42

18

39

30

48

36

57

42

63

45

33

45

66

6

18

15

27

24

36

30

42

30

18

0

24

36

39

48

48

54

57

60

63

63

51

51

69

24

18

33

27

42

36

48

48

54

42

24

0

60

63

72

72

78

81

84

87

87

75

75

93

48

42

57

51

66

60

72

72

18

18

36

60

0

45

12

54

18

63

24

69

30

39

51

72

12

24

21

33

30

42

36

48

51

39

39

63

45

0

57

12

63

21

69

27

72

60

51

33

33

21

42

30

51

39

57

48

30

30

48

72

12

57

0

48

6

54

12

60

18

30

42

63

24

36

15

27

21

33

27

39

60

48

48

72

54

12

48

0

54

9

60

15

63

51

39

21

42

30

33

21

42

30

48

36

36

36

54

78

18

63

6

54

0

48

6

54

12

24

36

57

30

42

21

33

15

27

21

33

69

57

57

81

63

21

54

9

48

0

54

6

54

42

30

12

51

39

42

30

33

21

39

27

42

42

60

84

24

69

12

60

6

54

0

48

6

18

30

51

36

48

27

39

21

33

15

27

75

63

63

87

69

27

60

15

54

6

48

0

48

36

24

6

57

45

48

36

39

27

33

21

48

45

63

87

30

72

18

63

12

54

6

48

0

12

24

45

39

51

30

42

21

33

15

27

45

33

51

75

39

60

30

51

24

42

18

36

12

0

12

33

27

39

18

30

9

21

3

15

57

45

51

75

51

51

42

39

36

30

30

24

24

12

0

21

39

33

30

24

21

15

15

3

78

66

69

93

72

33

63

21

57

12

51

6

45

33

21

0

60

51

51

42

42

33

36

24

18

6

24

48

12

33

24

42

30

51

36

57

39

27

39

60

0

12

9

21

18

30

24

36

30

18

18

42

24

21

36

30

42

39

48

45

51

39

33

51

12

0

21

9

30

18

36

30

27

15

33

57

21

42

15

33

21

42

27

48

30

18

30

51

9

21

0

12

9

21

15

27

39

27

27

51

33

30

27

21

33

30

39

36

42

30

24

42

21

9

12

0

21

9

27

21

36

24

42

66

30

51

21

42

15

33

21

39

21

9

21

42

18

30

9

21

0

12

6

18

48

36

36

60

42

39

33

30

27

21

33

27

33

21

15

33

30

18

21

9

12

0

18

12

42

30

48

72

36

57

27

48

21

39

15

33

15

3

15

36

24

36

15

27

6

18

0

12

54

42

48

72

48

48

39

36

33

27

27

21

27

15

3

24

36

30

27

21

18

12

12

0

Figure 6.9. This figure shows the eighth iterate Hasse-sum matrix, B8, for the Los Angeles freeway and major surface road network, post-earthquake configuration. Cells with background color are cells with entries that are different in pre- and post-earthquake calculations.

What the diligent forecaster of earthquake disaster on traffic patterns might learn from this example is to not underestimate the role of redundant connection, in this case through surface routes. The surface route pattern that was introduced here permitted all turns at each of the surface route intersections. Had that assumption been modified in any of a number of ways, the size of the numerical entries would have increased (Arlinghaus, Arlinghaus, Harary, and Nystuen, 1994). For example, turns (especially U.S. left-hand turns onto two way streets) generally force additional slowing of the traffic. If one allowed right-hand turns only, for example, the algorithm would proceed as above but would be applied to an asymmetric matrix instead of to a symmetric one, as above. One-way streets, instead of two-way, would also lead to an asymmetric matrix as a base for the Hasse procedure. Traffic lights, with timing pattern based on estimates of traffic, alter flows in one way; those with timing pattern that respond to actual traffic alter flows in yet another way. Each of the situations that is minor from a conceptual standpoint (although perhaps not from a real-world standpoint), as well as myriad others, can be captured numerically in a structurally equivalent Hasse-model.

Concern for the one-way street issue appears in Robbins (1939) classic paper that answered the question, "when is it possible to find an assignment of one-way directions for all the streets in a town while preserving the property that it is possible to reach any point in town from any other point?" for a town with no one way streets. Boesch and Tindell (1980) pursue this earlier analysis and analyze reachability criteria in systems that do permit one-way streets. Some current thinking in Ann Arbor Michigan, apparently the locale of Robbins's original model, would have one-way streets removed in an effort to make streetscapes more pedestrian-oriented. The "New Urbanist" mode of planning, that recalls many of the urban village concepts of pre-World War II planning (City of Ann Arbor Planning Commission, 1999), might find a theoretical root in Robbins's theorem from those times!

Spanning Trees:  Ann Arbor, Michigan, 2000

Another problem that occurs frequently is that of selecting a subtree of a connected graph that contains every node. Such a tree is called a spanning tree. For instance, a transportation planner might want to select a subset of the road network to carry the bulk of the traffic, to connect all major intersections, and to minimize the number of roads that must carry high-density traffic. A spanning tree might do this.

The tree might also be selected to have few or many branches at a single node. For example, ring roads avoid branches, while grid systems have many branches. Algorithms exist to try to create either kind of branching. One creates a small amount of local branching with depth-first algorithms and bushier trees with breadth-first algorithms. All such algorithms rely on an initial ordering of the nodes of the original graph.

Consider the following example, drawn from a street pattern similar to that in Ann Arbor, Michigan.

Case 1.  Depth-first. Consider the graph below (Figure 6.10) with nodes labeled A, ..., R.

Click on image to see animated tree structure.

Figure 6.10.  This figure illustrates a depth-first labeling of a graph.

A rooted tree is constructed with root A. A path is constructed starting at A and adding the smallest (in order) edge that continues this path, until it is impossible to add more. In this case the path is A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P.

Then one "backtracks" until an edge can be added, in this case {L,Q}. Further backtracking allows the edge {I,R} to be added, completing the illustrated spanning tree. (One might have been tempted to add the edge {M,O} or the edge {J,Q}; however, those additions would have destroyed the "tree" structure.)

Case 2.  Breadth-first. Now consider the same graph, but with a different labeling (Figure 6.11).

Click on image to see animated tree structure.

Figure 6.11. This figure illustrates a breadth-first labeling of a graph.

Construct a tree with root A. This time add all edges at A that do not complete a cycle. Thus, all of AB, AC, AD, AE are added. At the next level, add edges at B, C, D, and E that do not complete a cycle. At the third level, add edges from any of F, G, H, I, L, M, and N that do not complete a cycle (so here, only from G and I ). In the fourth level, edges only from O and J are added and no more can be added following their addition. The rooted tree produced using this strategy may be seen by clicking on the map in Figure 6.11.

Of course, the original graphs may be weighted. In this case, one can search for a minimal spanning tree. That algorithm appears in the complementary chapter