ML20053D237

SPTH3:Subroutine for Finding Shortest Sabotage Paths.

ML20053D237
Person / Time
Site:	Clinch River
Issue date:	05/28/1982
From:	Holdridge D, Hulme B SANDIA NATIONAL LABORATORIES
To:
Shared Package
ML20053D221	List: ML20053D220 ML20053D224 ML20053D237
References
SAND77-1060, NUDOCS 8206040218
Download: ML20053D237 (36)

Text

, - - _ _ _ ___ ___ ___ - .__ _ ._ ___ ___ _ . _ _ - . . _ . _ - _ . - - . .. . - - _ _ -

l ATTAClEENT E

! l SAND 771060 Unlimited Release 4

I e

l l

i i

l SPTH3: A Subroutine for Finding Shortest l Sabotage Paths  !

l

\

j l

i l

Bernie L. Hulme, Diane B. Holdridge

.r. : .. _, e ,

~

W. s' ~ * ?.s.g:'"-

d, t'$ s 3, s. ,,..

37188 .** * ',

t ' 1~" '

't ' ? ,,,e<had try jendistdoestaries' Ibde' '

- ,M '- -  :

i*g 5%j,ft.t'tsn$ thermore.ChillernW948D th the 8dieseur.:

S j {p, 4.cjpg, 2 : . .o ,.,,..

.r., w, " ' snoa ..t 9 $! ';_; g y

• j y .

x.s y .

@ . .T$' . .

w

. . - % + , t.

W4-

'" tv...::q4:...

.qq ; -..

• /.* UM. . My 9is .'h.kdje,95' ' * .

4 * * * .

k s.,o a o -o.. . ., .

-: v- ~  ;- :y;

,s -

JD 's Q,, Li,a. ' ,-

.g *.'*.,* -

VMcG

.?' . . \ '. _~,, s.

n 4:k * .:.

{.

• g.

~ . Yet '

I

__ . . . .s , l l

2900 O(7 7J) i l

l 8206040218 820528 l PDR ADOCK 05000537 C PDR

nsored by This report was prepared as an account of work spoNeit the United States Government. i ion, nor any of the United States Energy subcontractors, Research and De their employees, nor any of their contractors, sed or implied, or their employees, makes any warranty, expreslity for the or assumes any legal liability or responsibi that its use would not information, app accuracy, completeness or usefulness of a infringe privately owned rights.

l

- . - - . - - - _ - - - - , - - - _ , . ,_r-- -- .~. _,, _ .__ . , . - _ . - , - - - - - - - - - . - ,

- SAND 77- 1060 Unlimited Release Printed July 1977 SPTH3: A SUBROUTINE FOR FINDING SHORTEST SABOTAGE PATHS Bernie L. Halme Numerical Mathematics Division Diane B. Holriridge t Applied Mathematics Division Sandia Laboratories Albuquerque, New Mexico 87115 ABSTRACT This document explains how to construct a sabotage graph which models any fixed-site facility and how to use the subroutine SPTH3 to find shortest paths in the graph. The shortest sabotage paths represent physical routes through the site which would allow an adversary to take advantage of the greatest weaknesses in the system of barriers and alares.

The subroutine SPIH3 is a tool with which safeguards designers and analysts can study the relative effects of design changes on the adversary routing problem. In addition to showing how to use SPTH3, this report discusses the methods used to find shortest paths and several implementatica details which cause SPTH3 to be extremely efficient.

l l

• Presently in Nuclear Waste Technology Division.

Printed in the United States of America Available from National Technical Information Service U.S. Department of Commerce 5285 Port Royal Road Springfield, Virginia 22161 Price: $4.00 Microfiche $3 00 1

1

TABLE OF CONTENTS Page .

. . 3

1. Introduction . . . . . . . . . . . . .

4

2. Description of SPTH3 . . . . . . . . . . . .

The Sabotage Graph . . . . . . . . . . . . . 5 3

. . . . . 6 3.1. The Regions . . . . . . . .

. 6

32. The Graph G . . . . . . . . . . . .

The Weights . . . . . . . . 9 3.3 . . . . .

. . . . . . 11

4. How to Use SPTH3 . . . . . .

11 4.1. The Call List . . . . . . .

12 4.2. Input . . . . . .

Work Arrays . . . . . . . . . 13 4.3 . . . .

. 13 4.4. Output . . . . . . . . . . . . .

. . . . . . 14 5 Examples . . . . . . . . .

. 14 5 1. A Sample Problem . . . . . . . .

16

52. Run Time and Array Storage Results . . . .

. . . 18

6. Some Details of Implementation . . . . . .

. . . . . . . 18 6.1. A Flow Chart . . . . . .

. 19 6.2. The Triangle Inequality Tests . . . . . .

. . . . . 20 6.3 Computing Direct Distances l . . 20 6.4. Storing and Accessing Direct Distances

. . . . 22 6.5 The Dijkstra-Yen Search

. . 24 6.6. Retracing the Shortest Paths

. . 25 6.7 Counting the Shortest Paths .

. . 26 7 Listing of SPTH3 . . . . . . . . . .

i

(

i l

l

(

l

[

l 2 _

1. Introduction This report documents the latest code for finding shortest paths in thesabotagegraphsdescribedin(h]. A sabotage graph is a network which models a fixed-site facility. Shortests paths in the graph represent physical routes along which a saboteur could minimize time, or detection probability, or some other quantity reflected in the graph weights.

Currently path length in SPTH3 is the ordinary sum of the node and are weights in the path, so that either delay times (for barrier penetration at nodes and travel along arcs) or else distances could be used as weights.

So far shortest-time paths have been of principal interest. A trivial modification to SPTH3 would allow it to accept detection probability weights and produce sabotage paths which minimize cumulative detection probability. In the remainder of the report we shall think of the graph weights as times.

SPTH3 addresses the problem of a simultaneous attack by several teams each having a single target. This provides a lower bound for the path length of a single team with several targets to attack sequentially, and it also addresses a very real possibility which would place great stress upon the safeguards system. For further details motivating this model and considering the length-independence of different shortest-time paths, see[4].

It must be understood that the graph model and the pathfinding techniques do not take into account battles between adversaries and defenders. Such encounters require stochastic models. The sabotage graphs used for pathfinding have constant weights which give representative Since the delay times (perhaps minimum or average) values of delay times.

are in reality random variables, the graph-theoretic method of this j

3

report should be viewed as a deterministic approach to finding sabotage "

routes which exploit any weaknesses in the barrier and alarm systems. ~

Such paths require further evaluation either by simulation methods such as FESEM [2] to assess the paths' effects upon guard encounters or else by probabilistic methods such as EASI [1] to predict the likelihood of Both of these path evaluators require a path to sabotage interruption.

be given.

Thus, SPTH3 may be used to derive input for FESDI or EASI or else simply to indicate relative vulnerabilities in the barrier and alarm systems.

Those This document explains both what SPTH3 does and how to use it.

The readers interested only in how to use it may ignore Section 6.

shortest path algorithm embedded in SPTH3 is that of Dijkstra [3] as However, modified by Yen [6,5]. This algorithm is the best available.

its use in SPTH3 differs somewhat from the description given in [4].

Rather than searching outward to the boundary from each target as describe A substantial in[k],SPTH3see,rches$nwardfromtheboundarytoallnodes.

reduction in storage requirements and tenfold reductions in run time have l

l resulted from this and other improvements to the pathfinding code.

l

2. Description of SPTH3 .

SPTH3 finds shortest paths in a special graph called a sabotage graph. This graph models a fixed-site facility to some level of detail The details for i

thought to be appropriate for the user's purpose.

In brief, the nodes constructing the graph are given in the next section.

doors, are important locations in the plant (say, perimeter gates, building

locations),

windows, vents, stairwells, storage vaults, and vital equipment and the arcs are physical paths from one location to another.

l

There are three types of nodes: (i) boundary nodes located at possible perimeter penetration points, (ii) barrier nodes located on internal barriers at possible penetration points, and (iii) target nodes

• at vital equipment or material locations. The simultaneous sabota6e f

problem is to find all the shortest paths from the set of boundary nodes to each target. Given the graph (as a list of arcs) and the are and node weights, SPTH3 uses the Dijkstra-Yen algorithm described in Section 6.5 to search from the boundary nodes of the graph until the lengths of the shortest paths to all the other nodes are known. During the search SPTH3 keeps a list of the immediate predecessor (s) of each node along a shortest path from the boundary. This allows all shortest paths to each target to be retraced and stored without further arithmetic following the Dijkstra-Yen search.

The output from SPTH3 is simply a list of the directed arcs which belong to the shortest paths directed from the boundary to all the targets, together with a list of the number and length of the shortest paths to each target. It is possible to have more than one shortest path to any node, and this number can be obtained easily by a simple procedure explained in Section 6.7 3 The Sabotage Graph The first and most important part of the use of SPTH3 is the constntetion and weighting of the sabotage graph. This invol*tes three steps:

(1) partitioning the drawings of the plant into regions,

• Fomerly called hardware nodes.

5

(2) specifying the nodes and arcs of the graph model, (3) weighting the nodes and arcs with times (or detection probabilities) derived from test data or analyst judgement.

31 The Regions The boundary and the important internal barriers (fences, walls, floors, stairvells, etc.) naturally partition a map of the site into regions R , r = 1,2,... . A region is a very general area within which r

saboteurs may travel unimpeded by barriers. Some regions may appear on the drawing as disjoint domains, e.g., a stairvell or elevator region may appear as the union of the areas in which it intersects each floor of a building. However, if there are no significant delays to entering the stairvell, then the floors and the connecting stairwell may be treated as one region. The region structure is simply an aid to constructing the nodes and arcs which constitute the sabotage graph.

3.2. The Graph G Next, the analyst must carefully place nodes at all the important locations. Since the model is discrete there is some arbitrariness in the node selection process, and an analyst may want to try various graphs l differing in the number and location of the nodes. The node set should include representative penetration points along the boundary and along I the barriers between regions as well as all targets of interest inside l

the regions.

Once the regions and the nodes are specified, the arcs are determined by a fixed rule which gives sabotage graphs their special structure.

Every pair of nodes in region Rr is connected by an arc, forming a complete subgraph G ,, r = 1,2,... .

6

An interface between two regions may contain more than one barrier node, and this requires special attention from the analyst. Two reasons for using such multiple barrier nodes are to model barriers that (a) have varying hardness, or (b) have such physical extent that the are lengths are significantly affected by the node locations. An are joining node i to node j is denoted by the unordered integer pair (i,j) or (j,1). Multiple barrier nodes on a single barrier cause an arc in one region to have the 1

same name, or node pair, as some are in the adjacent re6 on (Figure la).

In order that each are have a unique node pair as its endpoints, the analyst must split each of the multiple barrier nodes into two barrier nodes connected by an arc (Figure Ib). Our decision to list the arcs of G region by region for purposes of computer input requires that each are belong to a single region. Consequently each are introduced by splitting multiple barrier nodes must belong to its own specially created region.

E l

I b I I ,_.t.__,,,,

R2 i k I

( --_(___

I I I l l g I ___L___

% 1 J J .

_q-.

I _a- _ _.- _ L _ _

Figure la. Figure Ib.

Multiple barrier nodes. Splitting of multiple barrier nodes.

The regions created by splitting multiple barrier nodes are numbered also, givin 6 a total of N3 ngions R r, each having a complete subgraph Gr*

7

The union of all these subgraphs is the sabotare graph _*

R G= U G r' r=1 whcse nodes are then numbered as follows:

target nodes, 1 to ny, barrier nodes, ny+1 to n +n' 2

= N.

boundary nodes, ny+n2+1 to n y +n 2 * "3 An example is shown in Figure 2, where squares are used for boundary nodes, Three nodes c.rcles for barrier nodes, and shaded circles for targets.

have been split.

on the barrier g n R2

_.__________._____.__________________q l

i

_L.

l 14 J 1 l 9 10' I

r- i- , T h 5

/8 I l 6 3  : Rs l l

3 u _7_ _s u_q_a ,

I l l 1

I - i I I L _ _ _ _ _ _ _ _ _ _ __ _ _ _ _J I I I I I I

l J

Figure 2.

A Sabotage Graph

• 'Ihis graph differs slightly from the graph of [14] in which boundary-boundary and target-target arcs were omitted.

8

7 Notice that every barrier and boundary node belongs to exactly two regions (counting the infinite off-site region), and every target node belongs to only one region. Also, due to the completeness of the subgraphe, the paths of G represent all the physically meaningful ways for saboteurs to proceed using only the given penetration points and targets.

3.3 The Weights Both the nodes and the arcs of G are assigned constant, nonnegative weights. The node weights w g2 0, 1 s i s N, are penetration and target destruction times, while the are weights a =a 2 0, (i,j) c G, are transit times. Realizing that these constants are simply representative values of random variables that depend on the physical characteristics of the barriers and the amount and type of equipment postulated for the attacking force, the analyst must decide whether to be conservative and use minimum values reflecting best possible adversary performance or else use intermediate or average values.

When the are weights are minimum values, they will autoratically satisfy a regional triangle inequality. That is, if arcs (1,j), (j,k) and (k,1) belong to Gr and their weights represent minimal transit times, then it must be true that

( "i,k ' "i,j + "j,k

• Since saboteurs may travel at different rates in different regions, this t

inequality need not hold for triangles whose arcs lie in different regions.

SPIT 3 tests all the trier.gle inequalities (1) for each region simply as a check on date consistency for the user's benefit. The pathfinding algorithm will perform perfectly well, of course, whether or not the i

triangle inequalities hold, so that this data check can be deleted from l 9

SPnI3 The weighting of the nodes and arcs which result from the splitting ,

of multiple barrier nodes may be done in many ways as long as the weights of the two new nodes and their connectin6 are sum to the barrier penetration time.

A weighting of the graph from Figure 2 is given in Figure 3 3 - _-_- _-_ _..- -_ _ _.-- - - _ _ _ _ _._ _ _ _ _ -. _ _

10 l 6 l l

_____4 o F_____q l l

s l5 J l g 1 16 20._L l L 4 7 3 NO 0 3,4 30 3( 5 0 8 5 l 0

~l 56 3 3

4 2 l u _ l _ _., I l

u_I__s 2 3h l

I l I 4 l 3 l l L ._ _ _ _4 '_2 ___________i I I 6 45 l I

45 l l

6 __ _ _ _ j L_ __ __ _ _ _ _.

l l

Figure 3 l A Weighted Sabotage Graph -

SPUI3 does not accept dire.:ted nodes and arcs, i.e. , nodes and arcs whose weights depend on the direction of travel. Of course, directed nodes and arcs could have been allowed, because Dijkstra's algorithm works equally well for directed graphs (digraphs) as for undirected graphs.

However, we have deliberately omitted directedness from the sabotage 10

~ -.

graphs because, in the applications for which SPTH3 is intended, are lengths are essentially the same in both directions and the doors locked on only one side are normally locked on the side first encountered by the saboteur.

~

h. How to Use SPTH3 h.1. The Call List The call list for subroutine SPTH3 is SPTH3 (N1, N2, N3 , NA ,W , MR , II , JJ , AWT , MAXE , IEDG E ,NE , N SP , XMINL ) .

The dummy arguments have the following meanings:

N1 - the number of target nodes, N2 - the number of barrier nodes, N3 - the number of boundary nodes, l

NA - the number of arcs, l

W(-) - the node weight vector, dimensioned N=N1+N2+N3, (the next four vectors, dimensioned NA, give the arcs as quadruples

( consisting of a region, two nodes, and an are reight) l MR(-) - the region index vector, II(+) - a node index vector, JJ(-) - a node index vector, ART (+) - the arc weight vector, MAXE - the maximum number of edges (ares) in the digraph S of shortest paths directed from the boundary to all target nodes, IEDGE( ,*) - the edges in the digraph S, each edge being given by three indices -- the region and two ordered nodes, dimensioned l

(3,MAXE),

NE - the number of edges in digraph S, NSP(*) - the number of shortest paths to each target, dimensioned N1, 11

XMINL(-) - the length of the shortest paths to each target, dimensioned N1.

h .2. Input To use SPTH3, first construct a weighted sabotage graph as indicated Next, in the program which calls SPTH3, dimension W by N, in Section 3 the vectors MR, II, JJ and AWT by NA, and the vectors NSP and XMINL by N1.

Set MAXE to some guess at the maximum nu=ber of edges S will have, and Then store the node weights in W and the dimension IEDGE by (3,MAXE).

The node weights are given in the obvious are data in MR, II, JJ and AWT.

Although there is no obvious order order: W(I) for node I,1 s I s N.

in which to give the arc data, a very special crdering of the arcs is required.

The arcs are given by the quadruples MR(K), II(K), JJ(K), AWT(K),1 s K s NA .

All the arcs of one region are listed consecutively, and the regions may For example, in a three region problem, the arcs be givet. in any order.

of region two could be listed first, followed by the arcs of regions The arcs of each region, however, must be listed as if three and ona. f they were taken row by row from the strictly upper triangular part o For example, if the nodes of one region are some node adjacency matrix.

{l6,9,21,h,7}, then an acceptable are ordering based on the given n (21,4), .

)

ordering is (16,9), (16,21), (16,4), (16,7), (9,21), (9,4), (9,7 ,

(21,7),(4,7). Notice that the arc ordering for a region may be based But once a node ordering is on any ordering of the region's nodes.

d chosen for the region, the arcs must be given by pairing the first no e h each with each other node in order, then pairing the second node wit 12

following node in order, and similarly for the third node, etc.

The reason for this requirement is that it produces tremendous savings in storage. The special are ordering allows SPTH3 to quickly compute the address of any arc weight and, thereby, completely eliminates the need for the usual N x N direct distance matrix. For graphs with several hundred nodes this is very important.

b.3 Work Arrays SPTH3 has several work arrays whose dimensions must be set by the user before running the job. The meanings of these arrays are explained in the program comments and in Section 6. In order to use SPTH3 it is sufficient for the user to set the following dimensions:

XLABEL,NPATH,IPERM,ITDiP,NEXT - N, NODE - (N,4),

IREG - (NR,2), where NR = the number of regions, NPOOL - bO, an arbitrary setting for an unpredictable total number of extra predecessors for nodes which have more than one predecessor along shortest paths. SPTH3 prints a messa6e when this dimension needs to be increased. In this case, tne results should be considered incomp.lete, and the problem should be rerun with a larger dimension for NP00L.

b '. h . Output I The output consists of MAXE,IEDGE,NE,NSP and XMINL ,

whose meanings are given above.

MAXE and NE serve as flags and must be tested upon return from SPTH3 l

to see if a normal execution took place. If MAXE = 0 upon return, there was a failure of the triangle inequality on the are weights of some i

region, a message was printed, and the pathfinding algorithm was not 13 1

L

executed. The user should correct the arc data indicated by the message and try again. Also, it is possible to return with NE = 0. This means that pathfinding was aborted because some node could not be reached from .

the boundary. The user must check the are list to be sure that all the arcs are present in each region.

It should be noted that the weight vectors W and AWT are changed by SPIH3 in the following way:

W(I) - W(I)/2. , N1 + 1 s I s N1 + N2 ,

AWT(K) - AWT(K) + W(II(K)) + W(JJ(K)) , 1 s K s NA .

If necessary, the user may restore W and AWT to their input values by firstsubtractingW(II(K))+W(JJ(K))fromAWT(K),for1sKsNA,and then doubling each barrier node weight. This change of W and AWT is also related to the above mentioned storage economy because it allows the input vector AWT to be used for the direct distance storage in lieu of the standard N x N matrix noz'nally used in Dijkstra's algorithm.

I 5 Examples 5 1. A Sample Problem Let us take the weighted graph of Figure 3 as an example. In Figure b this graph is shown with the digraph S of shortest sabotage paths superimposed in dark lines.

l The input consists of N1 = 2, N2 = 6, N3 = 2, NA = 23 ,

W = (4.,4.,5.,5.,5.,5.,5.,5.,16.,20.} ,

l 14

MR II JJ AWT 1 6 7 40.

1 6 8 6.

1 6 9 45 1 6 lo 40.

1 7 8 40.

1 7 9 lo.

1 7 lo 6.

- 1 8 9 40.

1 8 10 45 1 9 10 6.

2 1 2 3 2 1 3 4.

2 1 4 36.

2 1 5 34.

2 2 3 2.

2 2 4 34.

2 2 5 32.

2 3 4 33 2 3 5 30.

2 4 5 3 3 3 6 o.

4 4 7 o.

5 5 8 o.

7 o ho lo l

F_--q i g_a _ _ _ _ _ -1I5 i i d. '

L 4 J l 20,_L  !

r- - --7 33 0 o 4 3 5 2 l

l 7__ 2 4

34 b_l_ I i l i I 4 I l I L 4

6

____'_____i 3

I l

45 I l

45 l i

l u_____.__________________----_16 Figure 4.

The Digraph S of Shortest Sabotage Paths Superimposed on a Weighted Sabotage Graph 15

The output is Target NSF XMINL ,

1 2 73 2 2 71.

IEDGE (NE = 9)

Region Node Node 2 3 1 2 3 2 3 6 3 1 8 6 5 5 8 2 h 5 4 7 4 1 lo 7 1 9 7 .

Since the digraph S is given completely by IEDGE, S is easily drawn by simply darkening the edges indicated by the ordered node pairs in IEDGE.

NSP and XMINL show that there are two shortest paths to each target, those to node 1 having length 73. and those to node 2 having length 71.

5.2. Run Time and Array Storage Results SPTH3 is extremely fast. The li.jkstra-Yen algorithm used for pathfinding has a worst-case run time on the order of O(N ) for an N-node graph. Although SPIH3 also checks all the triangle inequalities in each region, does the bookkeeping for multiple predecessors, and retraces and counts the number of shortest paths to each target, it uses almost a '

negligible amount of run time. As shown in Table I a realistic sized problem of 310 nodes and 1191 arcs requires only about a second and a half of CDC 6600 run time.

Consequently, we feel that execution time for shortest path problems should be of very Little concern to most users.

As mentioned in Section 4.4, SPTH3 is also very storage efficient.

the N x N matrix of direct distances nomally used in Dijkstra's algorithm 16

has been eliminated in favor of a storage scheme which overwrites the input vector AWT with direct distances between node centers. Thus, the array storage, which dominates SPTH3' storage requirements for larger problems, is linear in the number of nodes, arcs, regions, etc. In particular SPTH3's arrays need loN + 4NA + 2NR + 2N1 + 3NE + ho storege locations, where 40 is an unpredictable diuension that proved adequate for our set of test problems. Table I also gives the array storage requirements for the larger probleias in the test set.

The sample problem in Figure 4 is Problem 3 below.

Table I CDC 6600 Run Time and Array Storage Results N des &s Regions Edges in S hray Run Time Problem N1-N2-N3 N NA NR NE Storage (seconds) 1 1 1 7 13 4 3 - 0.004 2 5-1-2 8 16 2 6 - o.004 3 2 2 lo 23 5 9 - 0.005 4 4 2 14 34 6 12 -

0.007 5 1-8-8 17 32 8 1 -

o.009

. 6 1-10 -8 19 40 8 1 411 0.009 7 1-31-14 46 112 20 2 996 0.041 8 20-58-4 82 514 35 43 3155 o.167 30-120-5 155 656 82 81 4681 o.446 9

10 10-296-4 310 1191 192 38 8422 1.563 17

6. Some Details of Implementation 6.1. A Flow Chart .

SPnD u

Arty triangle Yes a ~

inequality Return MAXE=O f failurss T

u Store direct II(K).JJ(K) between node centers in KdI(K) 1 s K s NA.

Set arrays NODE, IRE so that Dg ,y W be addressed in AWT.

+

Perform a Dijkstra-Yen Figure 5 search from the boundary to all

" d'*-

A Flow Chart of SPTH3 4

Retrace S, all shortest paths to

( targets, storing l arcs in IEDGE.

(

1 Court number of shortest paths to each node I in S.

t

' Store in NPATH(I).

l h

Set NSP(I)=NPATH(I)

• IMINL(I)=

ILABEL(I) 1sIsE U

Peturn l

18 t

6.2. The Triangle Inequality Tests Finding the triangles of each region is very easy given the conpleteness of the subgrapn and the special ordering of the arcs. For exa:::ple, consider the arcs of region R2 in the graph of Figure 4, II JJ AWT 1 2 3 1 3 4.

1 4 36.

1 5 34.

2 3 2.

2 4 34.

2 5 32.

3 4 33 3 5 30.

4 5 3 All the triangles containing arc (1,2) are found by taking each arc (1,t) listed below (1,2) together with each arc (2,4). In this case, the triangles are (1,2,3), (1,2,4) and (1,2,5). Next, all the triangles containing arc (1,3) are obtained by taking each are (1,t) listed below (1,3) together with each arc (3,4). This yields triangles (1,3,4) and (1,3,5). Finally, triangle (1,4,5) is obtained in a similar way.

Of course, each triangle (1,j,k) has three corresponding inequalities which are tested separately "i,j ' "i,k "k,j '

"i,k # "i,j + "j,k *

"j,k # "j,i + "i,k

• i As mentioned earlier, this portion of SPTH3 could be delete 2 without I

affecting the pathfinding procedure.

{

19

(

6.3 Cornputing Direct Distances Dijkstra's algorithm is defined in tems of a direct distance matrix D, whose elements (direct distance from i to j , (1,j ) c G ,

d = 0, i=j, (2)

<= , otherwise.

The algorithm applies to any digraph having weights only on the ares, since the nodes are thought of as points. A sabotage graph has node weights wg in forming the distances which SPTH3 combines with the are weights a d between node centers. The procedure is to halve the barrier node weights (since these are the intermediate nodes on paths from the boundary to the targets) and then to add each are weight to its endpoint weights, i.e.

(3) w = v1 /2. , n 1+1sisn1+n2*

t

+v (i,j) c G .

(b) d =a 1 + v) ,

6.h. Storing and Accessing Direct Distances SPTH3 avoids creating the N x N matrix D by storing the positive, finite, D values in the input are weight vector AWT when (4) is computed, i.e I = II(K) , J = JJ(K) l (5)

I AWT(K) = AWT(K) + W(I) + W(J) , 1 s K s NA .

This saves a great deal of storage for large N because the number of arcs f

in G is always small with respect to N2 (see Table I).

The penalty we pay for this storage efficiency is in the cost of in AWT. That is, when Dijkstra's algorithm finding any particular dy,y needs d y,y, SPTH3 must find a value K such that 20 l

(6) AWT(K) = d7,y ,

instead of just referencing D(I,J). Fortunately, the c mpleteness of the subgraphs and the special ordering of arcs in each subgraph allows K to be computed very quickly given I and J (see the run times in Table I).

To facilitste this index c mputation, two integer arrays are constructed prior to the Dijkstra-Yen search. NODE (I, ) contains the two regions and two local node numbers for node I. The local nede number in each region is detemined by the node ordering used to order the arcs of the region.

For the sample problem in Section 5 1, NODE (7,*) = (1,2,4,2} ,

meaning that node '/ is the second node of region 1 and the second node of region b. Since only the finite, internal regions are numbered, boundary nodes have only one region number and one local node number. Similarly for target nodes which belong to only one region.

IREG(R,*) contains the first word address minus one in AWT of the arcs of region R followed by the number of nodes in R. Thus, when SPTH3 needs dy,y(IM ), h does the fo h ng:

(a) compares region numbers for I and J to see if arc (I,J) belongs I to G, l (b) if(I,J)/G,noaddresscomputationisneededsinced ==,

[ (c) if (I,J) c G , en e st word adhess dus me of We arcs l R of region R, the number of nodes in region R, the local number of node'I in R, t ,y and the local number of node J in R, ty, are c abined to yield .

4 st y,+ t 7 y, l

K = <qIRm(R,1) +y (t -1)IREG(R,2) 7 -74 (4 +1)/2 IRE (R,1) + (4 y -1)IRM(R,2) - y 4 ky +1)/2 + 47, ty<47 K satisfies (6).

21

6.5 The Dijkstra-Yen Search The Dijkstra-Yen search finds the length of the shortest paths from the boundary to every node I in G and stores the value in XMINL(I),

1 s I s N. During the search the (immediate) predecessor of node J along a shortest path is stored in NEXT(J), 1 s J s N. When some node has more than one such predecessor, the extras are stored in a vector NPOOL. A link (an index for NP00L) is stored in the upper portion of the word NEXT(J) to indicate where the second predecessor of J is stored. This second predecessor, NPOOL(LINK), is linked to another entry in NP00L if there is a third predecessor of J, etc.* These data allow the efficient retracing of all (not just one) ahortest paths to each target, as explained in the next section.

In Dijkstra's algorithm [3] each node has a label which eventually becomes the length of the shortest paths from the boundary to the node.

These labels are temporary as long as they represent only the shortest path lengths currently found by the search, and they beccane permanent labels as soon as they are known to be the absolutely shortest lengths.

l i

SPUI3 initially sets all boundary node labels to zero and all other labels to = (a large machine number). The boundary node label XLABEL(N) is made permanent first by setting IPERM(1)=N. All the other labels are l

temporary. From the last permanently labeled node I, all the temporary labels XLABEL(J) are examined and reduced if XLABEL(J) > XLABEL(I) + dy,y ,

where d must be found in AWT as described in the previous section. Each

• We are indebted to Louann Grady, 57hl, for giving us this idea for linking together multiple predecessors.

22

, f- >-

. . l

, './

time XLABEL(J) is reduced, the predecessor I is stored in NEXT(J). If 4

XLABEL(J)=XLABEL(I)jg,y, ,

(to machine precision), then I is an extra predecessor of J which must be -

stored in the next available entry of NPOOL, and for which an additional link nrast be created at the end of the chain beginning with the link in the ,

upper 3 portion of NEXT(J). After all the temporary nodes have been examined from the one with the least temporary label is r.a e pemanent by placing

/  ?

it in IPERM. This is correct because the nonnegativity of the d I,J 'im;. lies s

)

In the case j of a tie, it does that this label cannot be reduced further.

not matter which of the nodes is pemanently labeled ne'xt. I is sit to this new pemanent node number and the process is repeated until all the nodes are pemanently labeled. Notice that IPERM has become a list of the nodes of G in order of nondecreasing distance from the boundary, and the '

shortest sabotage path lengths are XLABEL(J),1 s J s N1. /

Yen's contribution [6] to this search procedure is one of improved ,

implementation. Rather than letting J range from 1 to N at each stage and l

asking if each J is temporary, Yen suggests the following coding device.

Initialize ITDE(I) = I,1 s I s N, and K = N - 1. The temporary nodes, then, are the first K entries of IT0 . While trying to reduce each

h. .

temporary node label, keep track of the minimizing temporary node IP as

' well as its position IQ in ITEMP. Then, when IP is stored in IPER4, set ITDT(IQ) = ITDG(K). This has the double effect of removing IP from i

ITEMP and leaving the new set of temporary nodes in the first K entries of ITDG. Yen's modification saves SPTH3 about 25% in run time.

If, because of omissions in arc data, some node is isolated from the boundary, its infinite label will eventually become the least temporary l

l l

/

23

label at some stage. When this happens, NE is set to zero and SPIH3 returns to the user, who must supply the missing data before trying again.

6.6. Retracing the Shortest Paths Given the predecessors NEXT(*) and possibly some predecessors in NPOOL(*), SPTH3 can retrace the digraph S of all the shortest paths from the boundary to the targets. No label-arithmetic is needed. As each directed arc of S is obtained, it is stored as an ordered pair of integers in IEDGE(2,-) and IEDGE(3,-), and the arc's region number is stored in IEDGE(1,-). The retrace proceeds as follows.

i.e., the one Initialize NE = 0. Find the last target node in IPERM, Let I = NEXT(J),

furthest from the boundary, and set J to this node number.

Add one to NE, and if NE the predecessor of J, assuming J has only one.

does not exceed MAXE, store arc (I,J) and its region number in IEDGE(*,NE).

Now record the fact that a shortest sabotage path passes through I by If J has another predecessor, it is negating ITEMP(I) if it is positive.

In this NPOOL(LINK), where LINK is packed in the upper portion of NEXT(J).

case, set I = NPOOL(LINK), repeat the above arc-storage process and continue until all the predecessors of J contribute arcs to IEDGE. (Notice that all Set J i the arcs of S leading into J are listed consecutively in IEDGE.)

to the node in IPERM just before the one last used to set J, i.e., let J

~

l range over the nodes in the order opposite that in which they were made f

permanent.

If J is a target node or a barrier node with negative ITEMP(J),

i If J is a boundary node then repeat the above procedure for this new J.

or a barrier node that does not belong to a shortest sabotage path, then 1

skip it, continuing until J = IPERM(1) has been treated.

Thus, IEDGE contains all the arcs in the digraph S of all shortest i

sabotage paths. Moreover, the second nodes of these arcs occur in the l 24

order of nonincreasing distance from the boundary.

6.7 Counting the Shortest Paths The fact that the second nodes in IEDGE have nonincreasing distance from the boundary allows the shortest paths to be counted quickly as follows.

Set f1, boundary node, NPATH(I) = J

,0 , barrier or target node.

Then for each arc K in IEDGE, taken from bottom to top, i.e., from the boundary to the last target, set I = IEDGE(2,K)

J = IEDGE(3,K)

NPATH(J) = NPATH(J) + NPATH(I), K = NE,...,1 .

The final value of NPATH(J) ic just the sum of NPATH(I) over all the nodes I in S which have an are leading to J. Notice that each such node I will have its final NPATH value co=puted before NPATH(I) is added to NPATH(J) because of the ordering of the arcs in IEDGE. Hence, NPATH(J), is the number of shortest paths from the boundary to each node J in S, in particular to J = 1,2,...,N1.

l l

t I

25

7 Listing of SPTH3 SUBROUTINE SPTH3(N1,N2,N3,NA,W,MR,II,JJ.AWT,MAXE,IEDGE,NE,NSP, 1 XMINL) W(1),MR(1),II(1) JJ(1),AWT(1) ! EDGE (3,1),NSP(1),XMINL(1)

DIMENSION XLA9EL(155),NPATH(155),! PERM (155),ITEMP(155), NODE (155,4),

COMMON USES 1

IREG(82,2),NFXT(155),NPOOL(40)SAROTAGF PROBLEM--ONE TEAM PER C SIMULTANEOUS C

DIJKSTRA-TYPE SABOTAGE ALGORITHM--UNDIRECTED HARDWARE NODE.NODES, TIME WEIGH C SAVFS SHORTEST PATHS FROM OFF-SITE TO EACH C SPTH3 SEARCHES INWARD AND USES NO DISTANCE MATRIX.

C IMPUT.

C N1 NO. OF HARDWARE NODES.

C N2 NO. OF BARRIER NODES.

C N3 NO. OF BOUNDARY NODES. .

C NA NO. OF ARCS.

W NODE WEIGHT VECTOR, DIMENSIONED N=NL+N2+N3.

C C W IS CHANGED. REGION.

ARCS MUST BE LISTED REGION BY C ARC DATA--FOUR NA VECTORS.FURTHERMORE, WITH!N EACH REGION HAVIN C IN STRICTLY UPPER BE P*(P-1)/2 ARCS LISTED s.1 1, I P ) ,

C TRIANGULAR FORM.

THATROW BY ROW IS, (11,12), (11,131, ....

(13,IP), ...,

C (12,I3), ..., (12,IP), (13,I4), ....

C C

(IPM1,IP).

C MR REGION INDEX VECTOR.

C II N00E INDEX VECTOR.

C JJ NODE INDEX VECTOR.

ARC NEIGHT VECTOR. AWT IS CHANGED.

C AWT C MAXE MAXIMUM NO. EDGES (ARCS) IN THE DIGRAPH S OF SHO C FROM OFF-%ITE TO ALL HARDWARE NODES. IEDGE.

C THIS VALUE IS THE SECOND DIMENSION OF OUTPUT.

EDGES IN THE DIGRAPH 5, THE UNION OF ALL SHORT EST PATHS C

C IEDGE IEDGE WILL C DIRFCTED FROM THE BOUNDARY TO 3 ALL INDICES - THE REGION, HARDWARE NODES.

HOLD MAXE EDGES, EACH BEING GIVEN BY C

AND TWO ORDERED NODES.

THE EDGES ARE LISTED IN IEDGE SO C

C THAT THE SECOND NODES HAVE A DECREASING DISTANCE FROM C OFF-SITE.

( NF NO. EDGES IN DIGRAPH S.

C ...,N1 NO. SHORTEST PATHS TO H, H=1,2 H=1,2,... N1.

C NSP XMINL LENGTH OF SHORTEST PATHS TO H, C AND XMINL MUST BE AT LEAST AS LARGE AS N1 THE DIMENSION OF NSP THERE WAS A FAILURE OF THE TRIANGLE C

l C MAXE IF MAXE=0 UPON EXIT, INEQUALITY ON THE ARC WEIGHTS OF A REGION, AND THE C

ALGORITHM WAS NOT EXECUTED.

C C WORK ARRAYS C FOUR VECTORS DIMENSIONED N=N1+N2+N3 THESE LABELS C XLAAEL TEMPORARY AND PERMANENT DISTANCE LABELS.

C REPRESENT THE LENGTH OF THE CURRENTLY SHORTEST S.

C C NPATH PATHS NUMBER OF FROM OFF-SITE TO EACH NODE. SHORTE C IPERM NODES WHERE DISTANCF LABELS HAVE BEEN MADE PERMAN C ITEMP N00ES WHERE DISTANCE LARELS ARE STILL TEMPORARY.

C NODE RFGION AND LOCAL NODE NUMBFRS FOR EACH NODE.

C DIMENSION (N,4). I.

ARF RFGION NUMBERS FOR NODE C NODE (1,11, NODE (I,3) ARF CORRESPONDING LOCAL NODE NUMBERS.

C NODE (I 2), NODF(1,4) 26

REGION DATA CONCERNING ARCS.

DIMENSIONED (NO. REGIONS, 2).

C IREG C IREG(R,1) IS THE FIRST WORD ADDRESS MINUS ONE IN iE ARC C LIST OF THE ARCS OF REGION R.

. C IREG(R,2) IS THE NUMBER OF NODES IN REGION R, IMPLYING C THERE ARE IREG(R,2)*(IREG(R,21-11/2 ARCS IN REGION R.

C NEXT PREDECESSOR OF EACH NODE J ALONG A CURRENTLY SHORTEST PATH

• C FROM OFF-SITE TO J. DIMENSIONED N.

C NPOOL A LINKED LIST IN WHICH ADDITIONAL PREDECFSSORS MAY BE C STORED WHEN NODE J HAS MORE THAN ONE. THE LINK FROM C NEXT(J) TO NPOOL(LINK) IS STORED IN THE LEFT 51 BITS OF S

C NEXT(J). SIMILARLY, IF THERE IS A THIRD PREDECESSOR OF C J, THEN LINK 1 FROM NPOOL(LINK) TO NPOOL(LINK 1) IS STORED DIMENSIONED 40 C IN THE LEFT 51 BITS OF NPOOL(LINK), ETC. -

C IF THE DIMENSION OF NPOOL IS CHANGED, THEN THE FOURTH C STATEMENT NPLDP=41 MUST BE CHANGED. NPLDP IS THE NPOOL C DIMENSION PLUS ONE. IF THE DIMENSION N IS INCREASED TO C

MORE THAN 511 NODES, THEN THE FIRST THREE STATEMENTS MUST C BE CHANGED TO ALLOW MORE THAN 9 BITS IN THE RIGHT OF C EACH MoSK.

DATA EPS BIG / 1.0F-13,1 0E321 /

LTEST=1000B LOW =7778 IHIGH=77777777777777777000R NPLDPn41 MAXEP=MAXE+1 OMEPS=1 0-EPS OPEPS=1.0+EPS N12=N1+N2 N=N12+N3 NM1=N-1 N1P=N1+1 N12P=N12+1 C CHECK EACH REGION FOR TRIANGLE INEQUALITY ON ARC WEIGHTS ICT=0 IREG=1 5 IAEGP=IREG+1 IF(MR(IAEG) .NE. MR(IREGP)) GO TO 52 LIKE=II(IBEGI DO 10 !=IBEGP,NA l IF(II(I) .NE. LIKE) GO TO 15 10 CONTINUE GO TO 52 15 NM=I-IBEG IF(NM .LF. 1) GO TO 52

~

70 17=IREG+NM IEND=I2-2 NMT=NM-1 DO 50 11=IBEG,IEND AWTOM=AWT(11)*0MEPS 13=I1+1 DO 45 J=1,NMT IF(AWT(12)+AWT(13) .GE. AWTOM) GO TO 35 25 FORMAT (* TRIANGLE *313* FAILS. ARC WEIGHTS--*3E15.5) 30 PRINT 25,II(II).JJtII)pJJ(I3),AWT(II),AWT(I2),AWT(I3)

ICT=1 27

GO TO 40 35 IF(AWT(II)+AWT(12) .LT. AWT(13)*OMEPS) GO TO 30 IFIAWT(II)+AWT(13) .LT. AWT(12)*0MEPS) GO TO 30 ,

40 12=12+1 45 13=I3+1 NMT=NMT-1 50 NM=NM-1 IAEG=IFNO+2 IF(NM .GE. 2) GO TO 20 52 IREG=IBEG+1 IF(IBEG .LT. NA) GO TO 5 290 IF(ICT .EO. O) GO TO 55 MAXE=O RET (IRN C COMRINE NODF WEIGHTS INTO ARC WEIGHTS 55 00 65 != NIP N12 W(!)=0.5*W(I) 65 CONTINUE DO 68 IA=1,NA

!=II(IA)

J=JJ(!A)

AWT(IA)=AWT(IA)+W(I)+W(J) 68 CONTINUE C %ET THE ARRAYS NODE, IREG.

DO 70 !=1,N NODF(I,1)=0 70 NODF(I.3)=0 L=1 72 K=1 IR=MR(L)

IREG(IR,1)=L-1

!=II(L)

IF(NODF(I,1) .EO. O) GO TO 73 NODE (I,3)=IR NODE (I,4)=K GO TO 74 73 NODF(I,1)=IR NODF(I,2)=K 74 K=K+1 J=JJtL)

IF(NODE (J,1) .EO. 0) GO TO 75 NODE (J,3)=IR NODE (J,4)=K GO TO 76 75 NODE (J,1)=IR NODF(J,2)=K 76 IF(L .EO. NA) GO TO 77 L=L+1 IF((I .EO. II(L)) .AND. (IR .EO. MR(L))) GO TO 74 IREG(IR,2)=K L=L-K+K*(K-11/2+1 IF(L .LE. NA) GO TO 72 77 IPEG(IR,2)=K C DIJKSTRA-YEN SEARCH INWARD.

C INITIALIZE.

28

00 125 I=1,N12 XLABEL(I)= RIG NPATH(11=0 ITEMP(I)=I 125 CONTINUE DO 127 !=N12P,N XLAREL(I)=0.

NPATH(!)=1 ITEMP(I)=1 127 CONTINUF IPL=1 L=1 C PERMANENTLY LAREL NODE N.

IPERM(1)=N ,

!=N IR=NOOF(I,1)

LI= NODE (I,21 M=IREGt!R,1)+(LI-1)*IREG(IR,21-LI*(LI+11/2 IR2=0 K=NMI V= RIG C TREAT EACH TEMPORARILY LABELED NODE.

C V IS THE SMALLEST SUCH LAREL.

130 00 140 I T = 1,K J=ITEMP(IT)

IF(NODE (J,1) .NE. IR) GO TO 131 LJ=HODE(J,2)

GO TO 132 131 IF(NODE (J,3) .NE. IR) GO TO 133 LJ= NODE (J,4) 132 IF(LI .GT. LJ) GO TO 138 IAR=M+LJ GO TO 137 138 IAR=IRc3(IR,11+(LJ-1)*IREG(IR,21-LJ*(LJ+11/2+LI GO TO 137 133 IF(NODE (J,1) .NE. IR2) GO TO 134 LJ= NODE (J,2) f l GO TO 136 134 IF(NODE (J,3) .NE. IR2) GO TO 135 IF(IR2 .EO. 01 GO TO 135 LJmNODE(J,41 l 136 IFILI2 .GT. LJ) GO TO 139 IAR=M2+LJ l GO TO 137 139 IAR=IREG(IR2,11+(LJ-1)*IRFG(IR2,21-LJ*(LJ+11/2+LI2 137 DIJ=AWT(IAR)

Z=XLABEL(I)+DIJ XJPEPS=XLABEL(J)*0 PEPS IF(Z .GT. XJPEPS) GO TO 135 XJMFPS=XLABEL(J)*OMEPS IF(Z .GE. XJMEPS) GO TO 300 XLAREL(J)=Z NEXT(J)=I

' GO TO ISS 300 IF(IPL-NPLDP) 305,302,340 1

29

301 FORMAT (* NPOOL NEEDS TO STORE MORE LINKS *)

302 PRINT 301 GO TO 340 305 NPRFD=NEXT(J) -

310 IF(NPRED .LT. LTEST) GO TO 320 LINK = SHIFT (NPRED .AND. IHIGH,-9)

NPRED=NDOOL(LINK)

GO TO 310 320 NPOOL(IPL)=I 11= SHIFT (IPL,91 .OR. NPREn IF(NPRED .EO. NEXT(J)) GO TO 330 NPOOL(LINK)=f1 -

GO TO 340 330 NEXT(J)=Il '

340 IPL=IPL+1 135 IF(XLABEL(J) .GE. v) GO TO 140 V=XLABEL(J)

IP=J IO=IT 140 CONTINUE IF(V .NF. PIG) GO TO 155 NF=0 DO 152 I=1,N1 -

NsP(!)=0 XMINL(1)= RIG 152 CONTINUE RETURN C NODE IP IS TO BE PERMANENTLY LABELEO.

155 V= RIG L=L+1 -

IPERMIL)=IP

!=IP IR=NODF(I,1)

LI=N00E(1,21 M=IREG(IR,11+(LI-1)*1RFG(IR,21-LI*(LI+11/2 IR2=NODF(I,3)

LI2= NODE (I,4)

/

M2=IREG(IR2,11+(LI2-1)*IREGtlR2,21-LI2*(L12+11/2

! 1 TEMP (IO)=ITEMP(K) f K=K-1 l

IF(K .GT. 01 GO TO 130

- C ALL NODES ARE PERMANENTLY LABELED.

C RETRACE ANO STORF. THE SHORTEST PATHS TO ALL HARDWARE NODES NF=0 18n J=IPERM(L)

L*L-1 IF(J .GT. N11 GO TO 180 182 !=NrXT(J) 183 'NPRED=I IF(I .GE. LTEST) !=1 .AND. LOW .

NF=NF+1 i IF(NE-MAXEP) 193,192,205 13 191 FORMAT (* DIGRAPH OF SHORTEST PATHS CONT AINS MORE THAN*

I

• EDGFS*)

192 PRINT 191, MAXE 30

GO TO 205 193 IEDGF(2,NE)=1 IEDGr(3,NF)=J IR=NOOr(J-1)

IR2=NonE(J,3)

IF((NODE (1,1) .EO. IR) .OR. (NODE (1,3) .EO. IR)) IR2=IR IEDGE(1,NE)=IR2 IT=ITEMP(!)

IF(IT .GT. 0) ITEMP(I)=-IT 205 IF(I .EO. NPRED) GO TO 215 LINK = SHIFT (NPRED .AND. IHIGH,-9)

!=NPOOL(LINK)

GO TO 183 -

215 IF(L .ro. 01 GO TO 220 Jz!PFRM(L)

L=L-1 IF(J .LE. N11 GO TO 182 IF(J .GT. N12) GO TO 215 IF(ITEMP(J) .LT. 0) GO TO 182 GO TO 215 C COUNT THE SHORTEST PATHS TO EACH HARDWARE NODE.

220 K=NE DO 225 L=1,NE

!=IEDGE(2 K)

J=IEDGE(1,K)

NPaTH(J)=NPATH(J)+NDATH(I)

K=<-1 225 CONTINUE 00 210 Isl,N1 NSP(I)=NPATH(I)

XMINL(I)=XLAREL(I) 230 CONTINUE RETilRN FND e

e t

31

Acknowledgements We want to thank S. L. Daniel, 5411, and G. B. Varnado, 5412, for .

supplying us with some of the test problems and for their helpful comments concerning the use of SPTH3 REFERENCES

[1] H. A. Bennett, The "EASI" Approach to Physical Security Evaluation, SAND 76-0500, Sandia Laboratories, Albuquerque, New Mexico, January 1 777

[2] L. D. Chapman, Effectiveness Evaluation of Alternative Fixed-Site Safeguard Security Systems, SAND 75-6159, Sandia Laboratories, Albuquerque, New Mexico, July 1976.

E. W. Dijkstra, A Note on Two Problems in Connexion with Graphs,

[3] Numer. Math. 1, 269-271 (1959).

[k] B. L. Hulme, Pathfinding in Graph-Theoretic Sabotage Models. I.

Simultaneous Attack by Several Teams, SAND 76-031k, Sandia Laboratories, Albuquerque, New Mexico, July 1976.

[5] T. A. Williams and G. P. White, A Note on Yen's Algorithm for Finding the Length of All Shortest Paths in N-Node Nonnegative-Distance Networks, J. Assoc. Comput. Mach. 2,0, 389-390 (17/3).

[6] J. Y. Yen, Finding the Lengths of All Shortest Paths in N-Node 3

, Nonnegative-DistanceCompleteNetworksUsingh3 Additions and N '

Comparisons, J. Assoc. Comput. Mach. M, h23 424 (1972).

32

{

e DISTRIBUTION:

USNRC Distribution Section 5412 J. W. Hickman Attn: Robert Wade' 5412 D. E. Bennett Washington, DC 20555 5412 D. M. Ericson, Jr.

NRC-13 (208) 5412 G. B. Varnado 5700 J. H. Scott 5740 V. L. Dugan 1000 G. A. Fowler 5741 L. D. Chapman 1140 W. D. Weart

- 1141 L. R. Hill 5741 K. G. Adams 1141 D. B. Holdridge (10) 5741 H. A. Bennett 5741 D. Engi 1230 W. L. Stevens L. M. Grady 1233 R. E. Smith 5741 5741 R. D. Jones 1233 M. D. Olman R. G. Roosen 1310 A. A. Lieber 5741 Attn: W. F. Roherty, 1311 5741 D. W. Sasser 5741 A. A. Trujino 1700 0. E. Jones S. G. Varnado 1710 V. E. Blake 5742 8300 B. F. Murphey 1712 J. W. Kane J. Jacobs 8320 T. S. Gold 1738 R. L. Rinne 1739 J. D. Winiams 8321 D. L. Mangan 8266 E. A. Aas (2) 1739 C. A. Pepmuener (Actg.) (5) 1750 J. E. Stiegler 3141 1750A M. N. Cravens 3151 W. L. Garner (3) 1750A J. M. Demontmollin For ERDA/ TIC (Unlimited Release)

T. A. Seners 3171-1 R. Campbell (25) 1751 1751 J. L. Darbey ForERDA/ TIC 1751 B. R. Fenchel 1751 L. C. Nogales 1751 A. E. Winblad 1752 M. R. Madsen 1.154 J. F. Ney 1754 J. L. Todd, Jr.

1758 T. J. Hoban 1758 D. D. Boozer 1758 R. C. Han

( 1758 G. A. Einemond l 1758 W. K. Paulus 1758 I. G. Waddoups l

1758 R. B. Worrell 4010 C. Winter

.- 5000 A. Narath, Attn: Directorates 5200, 5800 l

- 5100 J. K. Galt I 5110 F. L. Vook 5120 G. J. Simons 5121 R. J. Thompson 5121 P. J. Slater 5122 L. F. Shampine 5122 B. L. Hulme (50) 5130 G. A. Samara J. E. Schirber 5150 5160 W. Herman 5400 A. W. Snyder 5410 D. J. McCloskey 5411 S. L. Daniel 33 i

. -. . _ _ . _. .