UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Straight-line realization of planar graphs. Shiau, Luang-hung 1971

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1971_A6_7 S55.pdf [ 5MB ]
Metadata
JSON: 831-1.0051252.json
JSON-LD: 831-1.0051252-ld.json
RDF/XML (Pretty): 831-1.0051252-rdf.xml
RDF/JSON: 831-1.0051252-rdf.json
Turtle: 831-1.0051252-turtle.txt
N-Triples: 831-1.0051252-rdf-ntriples.txt
Original Record: 831-1.0051252-source.json
Full Text
831-1.0051252-fulltext.txt
Citation
831-1.0051252.ris

Full Text

STRAIGHT-LINE REALIZATION OF PLANAR GRAPHS by LUANG-HUNG SHIAU B.Sc. National Taiwan University, 1956 M.A. University of British Columbia,1969 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in the Department of Computer Science We accept this thesis as conforming to the required! standard. THE UNIVERSITY OF BRITISH COLUMBIA April, 1971 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h Co lumb ia , I a g ree tha t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s tudy . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y pu rpo se s may be g r a n t e d by the Head o f my Department o r ^ by h i s r e p r e s e n t a t i v e s . It i s u n d e r s t o o d tha t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f Computer Science The U n i v e r s i t y o f B r i t i s h Co lumbia Vancouver 8, Canada Date April 16. 1,971 ( i i ) ABSTRACT Few theorems are known about planar graphs. For, example, Kuratowski proved that a graph i s planar i f and only i f i t has no subgraph homeomorphic to or K, It has remained as a direct criterion for 3,3 determining whether a graph i s planar or not. Powerful asr the theorem i s , i t i s not always easy to apply. This leads us to try some practical methods to test a planar graph. In this thesis, we have an algorithm for finding an outer circuit for a simple connected planar graph. Then, we use this outer circuit to draw a straight line graph i n the plane. The programme for this algorithm i s written i n FORTRAN for an IBM 360/67 Computer. ( i i i ) TABLE OF CONTENTS Page SECTION 1 :. I n t r o d u c t i o n 1 SECTION 2 : D e f i n i t i o n o f Terms and T h e o r e t i c a l Background 4 SECTION 3 : A Computer A l g o r i t h m f o r R e c o g n i z i n g a P l a n a r Graph 12 SECTION 4 : Drawing a P l a n a r Graph w i t h S t r a i g h t L i n e s U s i n g the Adjacency M a t r i x 30 SECTION 5 : R e s u l t s and Examples 42 SECTION 6 : How t o Use the Programmes 55 BIBLIOGRAPHY 5 9 APPENDIX A : The Main Programme f o r F i n d i n g an Outer C i r c u i t 60 APPENDIX B : GRAPHPACK 67 APPENDIX C : A l l the S u b r o u t i n e s Used by the Programme S t a t e d i n Appendix A 74 APPENDIX D : The Main Programme f o r Drawing a Given.Graph 84 ACKNOWLEDGEMENTS I am greatly indebted to Professor J. M. Kennedy for suggesting the topic of this thesis, for allowing me a generous amount of his time and for his many constructive comments during the preparation of this thesis. I also wish to thank Professor A. Mowshowitz for his criticism of the draft form of this work. The financial support of the University of British Columbia and the National Research Council of Canada are gratefully acknowledged. 1. Introduction. In the study of many problems a r i s i n g i n areas such as e l e c t r i c a l networks and t r a f f i c control, i t i s often important to represent a system i n the form of a simple l i n e a r graph. Since the problem i s to draw the graph i n a two-dimensional plane, i t i s desirable to draw i t with a minimum number of edge crossings. In 1930 , Kuratowski proved that a graph i s planar i f and only i f i t has no subgraph homeomorphic to or ^ ( F i g . 1 , Section 2) [ 4 ] . In the case of a simple planar graph, i n 1948, Fary [1] has proved that i f a f i n i t e graph can be represented on the plane a t , a l l , i t can be represented with straight seg-ments as edges. Powerful as those two theorems are, they are not always easy to apply. An algorithm suitable for implementation on a d i g i t a l computer f o r determining whether a graph G i s planar has been developed by Fisher and Wing [ 2 ] and [ 3 ] . A l l the operations are performed on matrices which are formed d i r e c t l y from the incidence matrix and t h e i r algorithm i s based on a decomposition scheme. They have shown that G i s planar i f and only i f an associated graph known as the Pseudo-Hamiltonian(Defini-ti o n 2 .210 graph i s planar and (2 ) each decomposed subgraph i s planar. Our algorithm i s based on a corollary to the decomposition theorem(Theorem 2 . 4 ) . It leads to some p r a c t i c a l methods by 2. which one can test and draw a simple connected planar graph eas i l y , or at least systematically. Before we introduce our algorithm i n Sections 2, we give the d e f i n i t i o n of some terms and the t h e o r e t i c a l basis f o r our algorithm. Our programmes can be divided into two parts: Part I (Section 3 ) . A l l the operations i n t h i s part are per-formed i n a representation that enables the user to describe operations i n graph-theoretical terms such as edge, vertex etc., and also save storage space i n the Computer. In Section 3, we explain how GRAPHPACK(Appendix B) represents a graph i n the Computer and the main algorithm f o r finding an outer c i r c u i t of a planar graph. Part II (Section 4 ) . The purpose of t h i s part of the programme i s to have a s t r a i g h t - l i n e representation of a planar graph i n the plane i f one has formed or can provide an outer c i r c u i t of the graph to be drawn. This part of programme can be used independently as long as the user provides a l l the required data. It w i l l draw a graph by using the results obtained from Section 3 or the data provided by the user. In Section 5 the execution time of the graphs of the fiv e regular s o l i d figures and some other graphs i s given. Since our programme i s written for planar graphs, i t might f a i l to detect a.'ronplanar graph because G i(pp. 9) might be non-planar. Some of such examples are also given i n t h i s section. In Section 6 we show how to use our programme. Programming d e t a i l s of our algorithm are given i n Appen-dices A to D. 4. 2. D e f i n i t i o n of Terms and Theoretical Background. Before stating the theorems on which our algorithm "is Abased, some standard terminology of graph theory w i l l be introduced i n t h i s section. Further special d e f i n i t i o n s w i l l be stated i n Sections 3 and 4. D e f i n i t i o n 2.1 A graph, G=(V,E), consists of a set V of vertices, and a set E of edges joining these vertices. E may be considered as a subset of ordered pairs of VxV. D e f i n i t i o n 2.2 A subgraph G'sCV'.E') of G s a t i s f i e s the condi-tions V 1 = V and E' = E. G' i s said to span G i f V = V. D e f i n i t i o n 2.3 A graph i s said to be directed i f directions are assigned to the edges, and i s said to be undirected otherwise. D e f i n i t i o n 2.4 A graph i s said to be f i n i t e , i f i t contains a f i n i t e number of edges. D e f i n i t i o n 2.5 An edge i s said to be incident with the vertices i t joins. D e f i n i t i o n 2.6 In a graph (directed or undirected), a path i s an alternating sequence of d i s t i n c t vertices and edges v 0 » e i » v1'* * *' vn-1 , en , vn' beginning a n d ending with vertices, i n which each edge i s incident with the two vertices immediately preceding and following i t . D e f i n i t i o n 2.7 A c i r c u i t i s a path i n which v =v and n> 3. 5. De f i n i t i o n 2.8 The number of edges between two vertices i n a graph i s called the m u l t i p l i c i t y of th i s pair of ver t i c e s . A graph that contains pairs of vertices with m u l t i p l i c i t i e s larger then 1 i s sometimes called a multigraph. A l i n e a r graph i s a graph the m u l t i p l i c i t i e s of the ordered pairs of vertices of which are no larger than !. De f i n i t i o n 2.9 A graph i s said to be simple i f i t does not contain loops(edges joining the same vertex to i t s e l f ) or multiple edges(several edges joining the same pair of v e r t i c e s ) . D e f i n i t i o n 2.10 A graph i s said to be embedded i n a surface S when i t i s drawn on S so that no two edges intersect. A graph i s planar i f i t can be embedded i n the plane. D e f i n i t i o n 2.11 In a graph (directed or undirected), two vertices are said to be connected i f there i s a path between them. De f i n i t i o n 2.12 An undirected graph i s said to be connected i f every two vertices i n the graph are connected and i s said to be disconnected otherwise. D e f i n i t i o n 2.13 In a graph (directed or undirected), the degree of a vertex i s the number of edges that are incident with i t . In a directed graph, the indegree of a vertex i s the number of edges that incident into i t , and the outdegree of a vertex i s the number of edges that are incident from i t . 6. De f i n i t i o n 2.14 The adjacency matrix A of a graph G with n vertices i s an n x n matrix, the (.i,j)th entry of which i s 1 i f there i s an edge joining the i - t h and j-th vertices, and i s 0 otherwise. D e f i n i t i o n 2.15 The incidence matrix A of a graph G with n vertices and m edges i s an n x m matrix i n which the rows correspond to the vertices and the columns correspond to the edges. The ( i , j ) t h entry i n the matrix i s 1 i f the i - t h vertex i s incident with the j-th edge and i s 0 otherwise. D e f i n i t i o n 2.16 I f e ^ = v\jVj (v.^ and Vj are the i n i t i a l and the terminal vertices of i s an edge of a graph G, and v i s not a vertex of G, then e.. i s subdivided when i t i s replaced by J the edges v.v and w.. J D e f i n i t i o n 2.17 Two graphs are homeomorphic i f both can be obtained from the same graph by a sequence of subdivisions of edges. We s h a l l describe some theorems i n the following:. Kuratowski [4 ] has proved: Theorem 2.1 A graph i s planar i f and only i f i t contains no subgraph homeomorphic to Kj- or K., , ( F i g . l ) . F i g . 1 For some time aft e r i t s publication i n 1930, Kuratowski's; theorem has remained the only dir e c t c r i t e r i o n for determining whether a graph i s planar or nonplanar. Powerful as the theorem i s , i t i s not always convenient to apply. For example, consider the graphs shown i n F i g . 2. It i s not obvious which of the graphs contains Kuratowski's graph as a subgraph. The v e r i f i -cation of the existence or nonexistence of a Kuratowski's basic nonplanar graph i n a given graph may become quite d i f f i c u l t i n some cases. F i g . 2 In the case of a simple planar graph, Istvan Fary [1] has proved: Theorem .2.2 I f a f i n i t e graph can be represented on the plane at a l l , i t can be represented with straight segments as edges. The main idea of his proof i s to suppose that the theorem holds f o r graphs with n vertices and l e t G be a graph with n+1 vertices and~~having no multiple edges. By l e t t i n g one of i t s edges shrink into a point we get a graph G* having n ve r t i c e s . Suppose f i r s t t h i s graph G* has•no multiple edges; then by hypothesis we can draw i t with straight segments as edges. Now, 8. stretch the vertex which correponds to the shrunken edge of G into a short straight edge. Thus we get G drawn with straight segments as edges. Secondly, i f G* has multiple edges, we can divide G by a c i r c u i t of three edges into two subgraphs; drawing these with straight segments as edges, one outside and the other inside of a triangle, we obtain a straight represen-tation of the graph G. Although the fundamental step of Fary's proof i s the construction of G*, he did not specify which vertex of G i s to be chosen i n order to construct G* or where G* i s to be located i n the plane. We s h a l l discuss these i n Section 4 i n d e t a i l . Before we introduce a decomposition theorem which i s given by G. J. Fisher and 0. Wing [3], we need some s p e c i f i c d e f i n i t i o n s for the terminology we are going to use: De f i n i t i o n 2.18 By the deletion of an edge we mean the removal of the edge but not the two vertices associated with the edge. Let C be a c i r c u i t i n a graph G and G-C the subgraph of G that remains when the edges of C are deleted. The.edges of G-G are c l a s s i f i e d as follows: (1) Direct Connections: edges with both vertices on C. (2) Edges of Attachment: edges with exactly one vertex on C. (3) Exterior Edges: edges with no vertex on C. The bridges of C i n G are defined by construction. F i r s t , delete the vertices of C and a l l of the edges incident to these 9. ve r t i c e s . Next, group the subgraph of G that remains into a set of connected components. Denote each component which consists of a single isolated vertex by V , and each of the remaining components by G^. F i n a l l y , associate with each component the set of edges of attachment which reconnect i t to C (Note that t h i s set may be n u l l for some G^ i f G i s not connected). From the above construction, we have D e f i n i t i o n 2.19 A bridge of C i n G i s a subgraph of G which con-s i s t s of (1) V. or G., (2) the edges which j o i n the vertex V. or J J vertices of G^ and the vertices on C and (3) the vertices on C which joined the above mentioned edges. I f an edge i n G-C which i s a direct connection then the bridge consists of th i s edge and the two vert i c e s on C which joins. Thus a bridge of C i n G belongs to one of the following types: Type 1 : a direct connection to C. Type 2 : a set of edges of attachment which connect a vertex to C. Type 3 : a connected component G^, and the corresponding edges of attachment which connect G^ to C. Let B be a bridge of G i n a graph G. D e f i n i t i o n 2.20 The vertices which are common to B and C are called vertices of attachment of B. We s h a l l define a Pseudo-Hamiltonian graph G' of a graph G with respect to C by construction again: I f G has Type 3 bridges which are not either Type 1 or 2, shrink 10. a l l the vertices but the attachment ones of each Type 3 bridge to form a "new" vertex. Then j o i n each "new" vertex to the r~ vertices of attachment of $he respective bridges and form a "new" Type 2 bridge. This "new" graph G' w i l l be called a Pseudo-Hamiltonian graph of G. In general, we have De f i n i t i o n 2.2T A graph i s Pseudo-Hamiltonian i f i t s decom-position with respect to a specified, c i r c u i t C consists of bridges which are a l l of.fype 1 or 2. Let G' be a Pseudo-Hamiltonian graph with respect to a c i r c u i t C. Let B be a bridge of C i n G'. Assume that B: can not be separated from C, i . e . , there are at least two vertices of attachment. Let the vertices of attachment of B be ordered i n a clockwise sense on G. The successive vertices i n this ordering divide C into a set of edge-disjoint paths. Suppose B' i s a bridge of C which i s d i s t i n c t from B, but possibly having the s'ame vertices of attachment as B. De f i n i t i o n 2.22 We say that B' does not alternate with B, i f a l l the v e r t i c e s of attachment of B* l i e on a path defined by two successive vertices of attachment of B. Othewise, we say that B' alternates with B. Further, i f B' alternates with B, then B alternates with B'. Now, we can state the decomposition theorem. 11. Theorem 2.3 Let G he a graph, G1 the Pseudo-Hamiltonian graph of G with respect to a c i r c u i t C. GV the decomposed subgraph ( i s formed by the union of C and a bridge of Type 3) for each component G^. G i s planar i f and o n ^ i f (1) the Pseudo-Hamiltonian graph G1 i s planar, and (2) each decomposed subgraph GV i s planar. The problem of determining the planarity of an arbi t r a r y graph i s , therefore, by Theorem 2.3, reduced to the problem of determining whether or not a Pseudo-Hamiltonian graph i s planar. By the d e f i n i t i o n of alternation, one observes that bridges which alternate must be mapped on opposite sides of C i f no two edges are to cross. On the other hand, bridges which do not alternate are not so constrained and may be mapped on either the same or on opposite sides of C. Thus we have Theorem 2.4 A Pseudo-Hamiltonian graph G' i s planar i f and only i f i t s bridges can be associated with two d i s j o i n t classes, I and 0, such that no two bridges i n the same class alternate. Our algorithm uses Theorem 2.4 to find an outer c i r c u i t C of a planar graph G, and Theorem 2.2 to find a straight l i n e representation of G i n the plane. In (3.2) of Section 3 we s h a l l give the reasons why we have to f i n d an outer c i r c u i t i n order to draw a planar graph. 12. 3v A Computer Algorithm for Recognizing a Planar Graph. Assume that the graph G i s planar, connected and a l l vertices are of degree ^ 2. Since a disconnected graph can always be treated as a c o l l e c t i o n of components each of which i s a connected graph or an isolated vertex, i t i s only necessary to be concerned with the connected graphs. Furthermore, vertices of degree 1 do not a l t e r or affect the construction of the straight l i n e graph, so we s h a l l concentrate on graphs whose vertices are of degree ^ 2. Some examples and comments about graphs with vertices of degree 1 w i l l be given i n Section 5 and Remarks 3 . 1 , 4.1 and 4 . 2 . F i r s t , we s h a l l explain how the algorithm recognizes a planar graph. ( 3 . 1 ) Representation (of a Graph i n the Computer. A l l the operation of the algorithm for testing planar graphs and extraction of planar graphs by Fisher and Wing [ 2 ] and [ 3 ] are expressed i n terms of incidence matrix. By contrast, we use separate tables of edges and vertices to represent a graph. This representation not only allows one to deal i n graph-the o r e t i c a l terms such as edge, vertex, etc., but also saves storage space i n the Computer, since the space used i s propor-t i o n a l to the numbers of vertices and edges, rather than to some higher powers of these numbers. This feature i s desirable i f graphs are f a i r l y sparse i . e . i f the degree of a vertex i s 13. small compared to the t o t a l number of v e r t i c e s . A set of subroutines known as GRAPHPACK was written o r i g i n a l l y for IBM 7040 by Dr. J. M. Kennedy and Mrs. J. Fowler and has been converted to IBM 360/67 with amendments and corrections by L.'"H. Shiau. GRAPHPACK i s b r i e f l y described i n the following (the de t a i l s are i n Appendix B): A number of singly-indexed integer arrays are used as follows: (3.1.1) V, VPROP, EDO and EDI are Vertex Tables. NV, the number of vertices i n the graph cannot exceed 128 i n the present version of GRAPHPACK. (3.1.2) P, S, EPROP, SL, PL and IDEL are Edge Tables. NE, the number of edges i n the graph cannot exceed 400 i n the present version of GRAPHPACK., The following are subroutines of GRAPHPACK: (3.1.3) I N I T L / — ( I n i t i a l i z e ) , NEWED(V1,V2) —(New edge) and NE¥VE(VN,V1 ,V2) —(New vertex) are Subroutines for Building •.. Graphs. (3.1.4) DELED(V1 ,V2,I) — ( D e l e t e edge), DELVE'(VN) — ( D e l e t e vertex), RESTED(V1,V2,I,ERR) — ( R e s t o r e edge), RESTVE(VN) — (Restore vertex) and RESTAL — ( R e s t o r e a l l edges and vertices) are Subroutines f o r Deletion and Restoration of Edges and Vertices. 14. (3.1.5) NEXEDO(VN,K) —( N e x t edge out), NEXEDI(VN,K) — ( N e x t edge in) and NEXEDG(VN,K) — ( N e x t edge) are f o r Traversal of  a Graph. (3.1.6) VERNAM(VN,J) — ( F i n d a vertex). This subroutine i s used by many of the other subroutines and may also be wanted i n the mainline programme. A c a l l of VERNAM sets J to the index of the vertex VN i n the vertex tables. (-3.2) Reasons for Finding an Outer C i r c u i t of a Planar Graph. Having properly stored a graph i n the Computer using GRAPHPACK, we have to explain why we want to find an outer c i r c u i t of a planar graph i n order to draw i t i n the plane. D e f i n i t i o n 3.2.1 A f i n i t e (or inner)'.'faee of a planar graph embedded i n the plane i s a connected domain.'-of' the /-plane--bounded by l i n e s representing edges of the graph. The bounding edges taken i n sequence form the c i r c u i t of the face. D e f i n i t i o n 3.2.2 The i n f i n i t e ( o r outer) face of a planar graph embedded i n the plane i s the domain of the plane which i s not bounded by edges of the graph. D e f i n i t i o n 3.2.3 The term face means either a f i n i t e or an i n f i n i t e face. Since each face i s a domain bounded by a c i r c u i t , the complete set of c i r c u i t s of the graph G, which includes a l l 15. the c i r c u i t s plus the outer c i r c u i t bounding the planar graph G i s unique i n the following sense: by choosing any one of the c i r c u i t s as external, i t i s possible (1) to have the planar graph inscribed i n i t , and (2) the set of c i r c u i t s i s the same regardless of which c i r c u i t i s chosen as the outer one [101. Thus we can start to find an outer c i r c u i t of a given planar graph G. ( 3 . 3 ) An Algorithm f o r Finding an Outer C i r c u i t of a Planar Graph. The algorithm i s divided into four steps. Step 1 Pick a c i r c u i t C i n G, find i t s bridges and form i t s Pseudo-Hamiltonian graph G 1. This i s done by shrinking a l l Type 3 bridges u n t i l a l l vertices not on C are coincident. Method: Vertices of G are read i n pairs (V1',V2) with the " e l e s t i c i t y " of the edge formed by V1 and V2. To form new edges the main l i n e programme c a l l s NEWSD(Vi,V2) and NEWED(V2,V1) since we are working on an undirected graph. The reason why we need the " e l a s t i c i t y " of each edge w i l l become clear at the end of Section 4 . To fi n d a c i r c u i t C, the main programme c a l l s APATH(3.4.1.1) 16. which returns the names of vertices on C i n array LIST. To f i n d i t s bridges, we f i r s t delete the vertices on C and a l l the edges incident to those vertices by c a l l i n g DELVE for each vertex i n LIST. Next, group the subgraph of G that remains into a set of connected components by c a l l i n g ALPATH (3.4.1.3) which returns the number of connected components i n YAL ; and the vertices of connected components i n array ANS. If.Tthere aare.-.«-*wo or more connected components, terminator symbols, i . e . 9 9 9 9 , are inserted i n ANS to separate them. Then c a l l RESTAL to restore a l l deleted edges and vertices to G. A vertex, which i s not a vertex of attachment, on C i s said to be of Type 0, To obtain Pseudo-Hamiltonian graph G', every shrinking Type 3 bridge i s replaced by a "new" vertex which i s not on C and "new" edges are assigned between th i s vertex and a l l the vertices of attachment of t h i s bridge. The vertices of attachment and those shrinking vertices are said to be of Type 3 and the "new" vertex i s of Type 5. I f the bridge i s of Type 2, the vertex which i s not on C, V and the vertices of attachment are said to be of Type 2. I f the bridge i s of Type 1, the two vertices of attachment are said to be of Type 1. Two arrays VPROP and EPROP are used to store these properties. VPROP: The lowest byte of VPROP(I) has the type of I-th vertex i n array V, the higher order bytes have the "nameof "the 17. "new" vertex i f the I-th vertex i s of Type 3. I f the I-th vertex i s of Type 5, the higher order bytes contain i t s weight(number of Type 3 vertices contained i n thi s "new" vertex). Note, i n order to distinguish whether a vertex i s on C or not, vertices of attachment of Types ,2 and 3 are stored i n the lowest byte of VPROP(I) as a zero. EPROP: This i s used to store the "representative" of each bridge and i t s vertices of attachment. The highest order byte of EPROP(I) has the index J of LIST(J)(since we have to keep track of the location of each vertex of attachment on C i n Step 2, to fin d the alternation of bridges) i f LIST(J) i s a vertex of attachment. The middle two bytes have the vertex "name", LIST(J), and the lowest byte has i t s type. Each bridge i s terminated by -1. Since array ANS has a l l the vertices of each connected component, we use thi s to find a l l the bridges and store the properties of each vertex i n VPROP and EPROP. For example, i f a graph i s given as i n F i g . 3, then 7 Fi g . 3 18. we s h a l l have Tables 1,2 and 3: LIST VPROP NV NEW VERTEX .(or WEIGHT) • 1 1 1 » * EPROP TYPE Table 1 INDEX f LIST LIST TYPE T 1 2 2 4 4 5 6 1 3 11 1 2 2 4 7 4 5 6 1 3 5 3 3 3 3 -1 2 2 2 2 -1 1 1 -1 Table 3. Step 2 Having b u i l t VPROP and EPROP, we s h a l l f i n d the alternate bridges and c l a s s i f y a l l the bridges into two d i s j o i n t classes* These are stored i n arrays IN and OUT, such that no two bridges i n the same class alternate. Method: Since the vertices on a c i r c u i t are stored ( l i n e a r l y ) i n array LIST, to determine whether two bridges alternate, we can not simply perform arithmetic comparison operations on t h e i r respective vertices of attachment (as suggested by Fisher and Wing [3] ) according to t h e i r indices i n LIST. Recall that the vertices of attachment of a bridge B i n 19. G with respect to C divide C into a set of edge-disjoint paths. Now, we s h a l l "paint" each path a dif f e r e n t colour, i . e . the vertices on C which are i n a path have the same colour and the connecting vertices are doubly-coloured. By the d e f i n i t i o n of alternate bridge, we say B' does not alternate with B i f a l l the vertices of attachment of B' are i n one edge-disjoint path, i . e . a l l the vertices of attachment of B* have the same colour. Othewise they have d i f f e r e n t colours. Our programme i d e n t i f i e s the colours by different small prime numbers 2,3,5,...,etc., and uses the product of the primes for a multicoloured vertex. Then, two vertices are of the same colour i f and only i f t h e i r H.C.F. (highest common factor) i s greater than 1. The "colour" of each vertex on G i s stored i n the higher order 3 bytes of each LIST(I), 1=1,L-t. For example, i f we want to "paint" the c i r c u i t C (from Table 1) i n F i g . 3 hy using the f i r s t bridge B i n EPR0P(from Table 3) we store B i n array IN. Then we s h a l l have F i g . 4 (a subgraph of F i g . 3) and a "new" LIST (Table 4) i n which the Type 3 bridge 11 or vertex 11 i s connected to vertices 1,2 and 4. -5_ 1. 2*3 2 3 4 5 6 7 LIST 10! i 6' 2 F i g . 4 Table 4 2 0 . Then any other bridge, say B', can be drawn inside the c i r c u i t C i f and only i f a l l i t s vertices of attachment are of the same colour, i . e . B* does not alternate with B. Now, i f B'(the second bridge) i n EPROP alternates with B, then B' w i l l be stored i n array OUT. Otherwise i t i s stored i n array IN. I f there are two or more bridges i n array IN, we have to "repaint" the c i r c u i t C,(since a l l the bridges of G with respect to a c i r c u i t must be tested against each other for t h e i r alternation properties). For example i n Pig. 3, the Type 2 bridge 7 or vertex 7 i s connected to vertices 4 ,5 and 6. Since t h e i r colours are the same (t h e i r common factor i s 5 ) , we see that bridge 7 does not alternate with bridge 11. Hence bridge 7 i s stored i n array IN and we have to "repaint" the c i r c u i t C. To do t h i s subroutine REPANT(3.4.2.2) i s call e d and i n t h i s example, we obtain F i g . 5 and "new" LIST (Table 6) as follows: 2*11 LIST 7*11 5*1 _ 2*3 3 4 5 6 7 2 3 15 35 77 22 6 3 4 5 6 2 F i g . 5 Table 6 21. In proceeding through the bridges of a given graph, we do those of Type 3 f i r s t , then those of Type 2 and Type 1 (in fact, our programme stores a l l the bridges i n EPROP i n this order). We also do th i s i n a way that t r i e s to put as many bridges as possible "inside" C, i . e . i n array IN. This i s done because our aim i s either to show that C i s an outer c i r c u i t or else to simplify the algorithm i n Step 4 for finding a c i r c u i t outside C. Step 3 If a l l bridges are inside C, i . e . no bridge i s i n array OUT, then C i s the outer c i r c u i t and we are done. If there are further bridges i n array OUT, we then have to "erase" the colour of G ( c a l l subroutine ERASE(3.4.2.3)). Then "paint" by the f i r s t bridge i n array OUT etc.,in order to test a l l the bridges i n array OUT. If there i s any pair of bridges i n array OUT alternating with each other, then we conclude that the given graph i s nonplanar and a message w i l l be delivered. In this case, the testing w i l l be teminated and no graph w i l l be drawn. Otherwise, go to Step 4 to find a new c i r c u i t that i s "outside" C — sooner or l a t e r the resu l t i n g c i r c u i t w i l l be outside everything as required. Step 4 Getting the external (outer) c i r c u i t C'. Having done the tests i n Step 3, we may assume that a l l the bridges IL i n array OUT do not alternate. Pind what th i s piece i s , and replace i t by a "detour" v i a G^. Then fi n d C 1 outside C, replace G by C' and go back to Step 2. Method: F i r s t we delete a l l bridges "inside" G, and restore 22. a l l bridges "outside" C. I f the bridge i n OUT i s of Type 3, restore a l l the "shrinking" vertices and t h e i r edges connected to 0, delete the "new" vertex and put VPR0P("new" vertex) = - 1 , The l a s t one indicates that t h i s "new" vertex w i l l not be used i n the following i t e r a t i o n . Since we have t r i e d i n Section 2 to put the Type 3 bridges f i r s t and then as many bridges of other types as possible i n array IN, i t w i l l save us some unnecessary work:. Next "erase" the coloured LIST which has been "painted" i n Step 2. Then delete the edges on C which are covered by the bridges i n array OUT, and c a l l subroutine APATH(3.4.1.1) to f i n d a second c i r c u i t C , replace G by C', and go back to Step 2. For example, i n F i g . 3 , a f t e r Step 3 has been completed, we get two classes of bridges stored i n arrays IN and OUT as shown i n Tables 7 and 8. IN 1 1 1 1 1 T i 5 2 * ! 1 ! 5 3 2 ' 2 ! 3 4 4 | 4 1 3 5 i i -1 6 I 7 i 2 7 4 ; 4 ! 2 8 5 ! 5 1 2 9 6 TO I i " 1 1 2 3 OUT " l 1: 1 ! 1 3! 3 ! 1 i i • -1 Table 8 Table 7 23. Note that duplicate vertices of attachment of a bridge have been eliminated and those that remain are i n the order of the i r occurence on C. Since there-is one bridge i n array OUT i n this example, i n Step 4 we find a new c i r c u i t C = ( 1 , 3 , 4 , 5 , 6 ) . Repetition of Step 2 gives F i g . 6, Tables 9, 10 and 1 1 . For the second i t e r a t i o n , the "new" vertex 12 i s used. C i s "painted" only once for there are only two bridges of G with respect to C . Both are stored i n array IN since they do not alternate with each other. Thus the outer c i r c u i t i s ( 1 , 3 , 4 , 5 , 6 ) and we are done. 3*5 F i g . 6 Table 9 NY VPROP EPROP 1 1 I » \ t 0 1 i i 12,' 5 2 12 i 3 2 2 ; 5; 3 3 0 3 1 ; 1 3 4 0 4 1 • 1; 3 5 0 5 3 ! 4! 3 6 0 6 • -1 7 2 7 8 12 ! 3 8 3 i 4- 2 9 12 . 3 9 4 ' 5' 2 10 12 i 3 10 5 ; 6| 2 11 -1 11 ; , -1 12 4 ! 5 Table 10 Table 11 24. In Step 4 , i f an outer c i r c u i t cannot be found because some i s nonplanar, a message w i l l be delivered and no graph w i l l be drawn. The d e t a i l s of thi s algorithm for finding an outer c i r c u i t are i n Appendix A. ( 3 . 4 ) Subroutines. In the above algorithm ( 3 . 3 ) , we use the following sub-routines to find a c i r c u i t , "paint" i t and c l a s s i f y the bridges. The d e t a i l s are i n Appendix C. (3.4.1) Paths or Connected Components of a Graph. (3.4.1.1) APATH(I,END,LIST,L,FAIL) — ( F i n d a path from vertex I to vertex END). Given an i n i t i a l vertex I and a terminal vertex END, a c a l l of APATH w i l l find a path from I to END and put a l l the vertices along the path (including I and END) i n array LIST. L i s the length of LIST. FAIL i s a f l a g , set to be 1 i f there i s no path from I to END, otherwise 0. If END = I, then APATH w i l l give a c i r c u i t . ( 3 . 4 . 1 . 2 ) PATH(I,NODE,NO,ANS,IX) — ( F i n d a path s t a r t i n g at I ) . Given any vertex I, thi s subroutine w i l l find a path from I as far as possible. NODE has a l l the vertices i n G which have been tested i n order to find a path and NO i s number of elements 25. i n NODE. I f a p a t h i s f o u n d , a l l t he v e r t i c e s ( i n c l u d i n g I ) a l o n g t h e p a t h a re s t o r e d i n a r r a y ANS and t e r m i n a t e d by a s ymbo l , 9 9 9 9 . I X i s the number o f e l ement s i n ANS. T h i s s u b r o u t i n e i s c a l l e d by ALPATH(3.4 .1 .3 ) t o f i n d a connec ted component i n a g r a p h . ( 3 . 4 . 1 . 3 ) ALPATH(VAL,NODE,NO,ANS,IX) — ( F i n d a l l p a t h s ) . G i v e n any g raph G o r G-C where C i s a c i r c u i t , a c a l l o f ALPATH w i l l f i n d a l l t he connected components o f G o r G-G. NODE, NO, ANS and IX have the same meaning as t ho se o f ( 3 . 4 . 1 . 2 ) . VAL i s t he number o f pa th s ( o r connec ted components) i n G o r G-C. ALPATH i s c a l l e d by the ma in programme. I n t he f o l l o w i n g s u b r o u t i n e s , t he arguments LIST and L a r e the same as t ho se p r e v i o u s l y d e f i n e d . ( 3 . 4 . 2 ) " P a i n t " a C i r c u i t C. ( 3 . 4 . 2 . 1 ) PA INT ( L I ST , L , SPP ,PP , S I , I N , I ) — ( P a i n t C ) . I n t h i s s u b r o u t i n e , a r r a y PRIME c o n t a i n s some s m a l l p r ime numbers i n " n a t u r a l " o r d e r . I f t h e r e a r e two o r more b r i d g e s i n a r r a y IN , t he c i r c u i t C might be " r e p a i n t e d " , we have t o keep t r a c k o f the f i r s t and t he l a s t p r imes h a v i n g been used i n p a i n t i n g . 26. The elements i n array PRIME, from PRIME(SPP) to PRIME(PP), are the prime numbers being used to "paint" C. Since the elements i n array IN, from IN(SI) to IN(I), are vertices of attachment of a bridge and divide C into edge-d i s j o i n t paths, we paint the vertices (on C) of each edge-disjoint path a same small prime number. If a vertex i s both i n array I and on G, i t w i l l be "painted" twice. The prime numbers being used to paint the vertices are stored i n the higher order 3 bytes of t h e i r corresponding location i n array LIST. Note that the l a s t vertex i n array LIST i s not painted as i t i s the same as the f i r s t . (3.4.2.2) REPANT(LIST,L,SP?,PP,SI,IN,I) —(Repaint C). A l l the arguments are the same as those of PAINT. This subroutine i s called by ALTER(3.4.3.4), i f we have to "paint" the c i r c u i t C again. The rules for painting are the same as those of PAINT. (3.4.2.3) ERASE(LIST,L) (Erase the colours). This subroutine w i l l "erase" a l l the colours being painted, i . e . , the array LIST contains only the "name" of a l l the vertices on C i n the lowest order byte. (3.4.3) Cla s s i f y a l l the Bridges of a Graph G with respect to a C i r c u i t C. (3.4.3.1) SAME(IN,I) This subroutine simply eliminates the same elements i n 27. array IN which has I elementsJ the "new" array w i l l he put hack i n array IN and I i s the number of elements i n the "new" array IN. ( 3 . 4 . 3 . 2 ) ORDER(IN.I) Rearrange the given array IN with I elements such that the highest order byte of each element of array IN to be i n natural order and put the result i n array IN. ( 3 . 4 . 3 . 3 ) ALTNAT(LIST,L,SI,IN,I,STEST,TEST,TE,SO,OUT,OT, NOBIN,NOBOUT) — ( T e s t i f two bridges alternate or not). Use the bridge B, from IN(SI) to IN(I), to "paint" C. The bridge B', from TEST(STEST) to TEST(TE), i s to be tested against B. I f B' alternates with B, then B' i s stored i n array OUT, from OUT(SO) to OUT(OT), otherwise i n array IN. In the l a t t e r case, both SI and I w i l l be increased by the length of array TEST. NOBIN and NOBOUT are the number of bridges i n arrays IN and OUT respectively. This subroutine i s called by subroutine ALTER ( 3 .4 .3 .4 ) . ( 3 . 4 . 3 . 4 ) ALTER(BC,LIST, 1,IN,I,OUT,OT ,NOBIN,NOBOUT,*) — ( T o find the alternation property among a l l the bridges). A l l the arguments are the same as those of ALTNAT, except BC which i s the length of array EPROP. Recall that EPROP has a l l the bridges of G with respect to C. The main l i n e programme c a l l s ALTER to c l a s s i f y a l l the bridges of G with respect to C into two classes!:which'-.are'. 2 8 . stored i n arrays IN and OUT. If BC = 0, then the given graph i s a simple c i r c u i t , t h i s subroutine w i l l do nothing and return to the main programme by RETURN 1. If there i s only one bridge, then i t w i l l simply put this bridge i n array IN and return to the main programme by RETURN 1, i. e . the outer c i r c u i t i s found. Otherwise, i t w i l l do the following: (1) Whenever a bridge i n EPROP i s copied into arrays IN or TEST, subroutines ORDER and SAME are c a l l e d . (2) The f i r s t bridge, say B, i n EPROP i s copied into array IN, then subroutine PAINT i s called to "paint" the c i r c u i t C by using t h i s bridge. (3) The next bridge, say B', i n EPROP i s copied into array TEST, subroutine ALTNAT i s called to test i f B and B' alternate with each other, i f so copy TEST into array OUT, otherwise into array IN. (4) I f there are two or more bridges i n array IN and EPROP, the c i r c u i t w i l l be " r e p a i n t " ( c a l l subroutine REPANT) by using a l l the bridges i n array IN except the f i r s t one. The bridges l e f t i n EPROP w i l l be tested one by one against those i n array IN by c a l l i n g ALTNAT u n t i l a l l the bridges i n EPROP are exhausted. Remark 3.1 Separable bridges, i . e . those bridges having only one vertex of attachment, i n par t i c u l a r , a vertex of degree one, are ignored and deleted i n thi s subroutine.(Examples 5.1 and 5.2) Having found the outer c i r c u i t by the method described i n th i s section, we are i n a position to draw the given planar graph i n the plane. 30. 4. Drawing a Planar Graph with Straight Lines Using the Adjacency Matrix. Some additional d e f i n i t i o n s are required f o r the following discussion. D e f i n i t i o n 4.1 Let C be a c i r c u i t of a graph G and #(C) denote the number of bridges of G with respect to C. If #(C) ^  1 , we c a l l C a peripheral c i r c u i t of G. D e f i n i t i o n ^ . 2-' The"connectivity k = k(G) of a graph G i s the minimum number of vertices whose removal results i n a d i s -connected or t r i v i a l graph. A graph G i s n-connected i f k(G)£ n. Let C be a peripheral c i r c u i t of a 3-connected graph G:: having no Kuratowski subgraphs.(Two examples, Examples 5.2' and 5.4,' for 1-connected and 2-connected graphs respectively are given i n Section 5.) Recall that NV i s the number of vertices i n G and (L-1) i s the number of vertices of G on C. Let Q be a (geometrical) (L-1)-sided convex polygon i n the Euclidean plane. We s h a l l define a function i n the following: D e f i n i t i o n 4.3 Let f be a 1-1 mapping of the vertices on C onto the set of vertices on Q such that the c y c l i c order of vertices on C agrees, under f, withYthe c y c l i c order of vertices on Q. Let's enumerate the vertices of G as V., V9,..., YmT 31. so that the f i r s t (L-1) are the vertices of G on C. We extend f to the other vertices of G by the following r u l e . I f (L-1) < i S NV, l e t A(i) be the set of a l l vertices of G adjacent to V.. For each V. i n A ( i ) , l e t a unit mass J m. be placed at the point f ( V . ) . Then f(V.) i s required to be the centroid of the masses m.. The extended f i s called J a barycentric mapping of G. De f i n i t i o n 4.4 Let , U2,..., U k be subsets of a given set U, not necessarily a l l d i s t i n c t . Their mod 2 sum i s the set of a l l u €U such that the number of suffixes i s a t i s f y i n g u <S i s odd. De f i n i t i o n 4.5 Let E(G) be the set of edges of a graph G. A cycle of a graph G i s a subset S of E(G) such that the number of lin k s of G i n S incident with any vertex of G i s even. I f C i s any c i r c u i t of G then E'(C) i s a cycle, we c a l l a cycle of t h i s kind elementary. D e f i n i t i o n 4.6 A planar mesh of G i s a set M = J S1,S9,...,S of elementary cycles of G, not necessarily a l l d i s t i n c t , which s a t i s f i e s the following conditions. (1) I f an edge of G belongs to one of the sets S i i t belongs to just two of them. (2) Each non-null cycle of G can be expressed as a mod 2 sum of members. of M. 32. In 1963, W. T. Tutte [8] has shown by using barycentric mapping that i f & i s a simple graph having a planar mesh, then one can find a straight representation of G i n the plane. He has also proved that i f G i s any graph, propositions "G i s planar", "G has a planar mesh", and "G has no Kuratowski subgraph" are equivalent. Hence by Fary's Theorem(Theorem 2.2 i n Section 2), we can draw a planar graph with straight l i n e s i n the Euclidean plane. Assume that graph G with vertices V.^  (i=1 ,2,... ,NV) i s undirected and simple. Then the adjacency matrix A=(a. .) is; symmetric and the diagonal elements ? a^^ are zero, since ;loops are forbidden. The problem i s to locate the vertices at positions (x i,y i) i n the plane i n a way that allows the edges to be drawn with non-intersecting straight l i n e s . Our method, "The E l a s t i c Model", i s to consider a mechanical model of a given graph G, i n which the edges are represented by short (but very stretchable)pieces of e l a s t i c rubber bands'. Suppose the vertices are set at some positions so that a l l the elastics;- are stretched. Then the system i s i n mechanical equilibrium i f the net force acting on each vertex i s zero. As shown i n Fig.7, l e t us consider the vertex V\, and l e t V. be one of the vertices adjacent to V.. Let d.. be 0 33. / I x r x i i __*X F i g . 7 the distance between them. Hooke's Law of e l a s t i c i t y says that the force i s proportional to the stretching, and since the i n i t i a l length was very small, the force between V. and V. has magnitude F. . =• d. . (omitting a constant of proportionality) This force can be resolved into x and y components by multiplying by the appropriate Cosines or Sines: (x) 10 X - i - x i i j X j " X i (v) y i ~ y i F . \ y ; = — ^ — — • d. . = y. - y. 10 d ± J 13 *z The t o t a l force on comes from summing over all'edges; t h i s must be zero for equilibrium. Hence (4.1) a. • (x. - x.) = 0 S a u ( y j - y ± ) = o i=1,2,...,NV. 34. These can be rewritten as j J F I and the same for the y. . Thus (4.1) can be written as (4.2) DZ = 0 T where Z = and the matrix D of coefficients for the linear system i s just the adjacency matrix A with the • negative of i t s row sums inserted on the diagonal. In order to get a non-trivial solution of (4.2), we have to f i x some vertices and let the others take up their equilibrium positions. Tutte [8] has shown that i f a graph G i s connected and planar, fixing the vertices of any one face i s necessary and sufficient to give a unique solution, so we shall f i x the vertices which are in array LIST on C ( The outer circuit obtained i n (3.2), Section 3) to solve (4.2). Without loss: of generality, suppose that , "V^ ,..., , (L-1) fE. NV are on C and the coordinates of V^ are (P^CL^)* then the k-th equation in (4.1) i s replaced by x. k = Pk and ^k = *k in the "x-set" and "y-set" respectively. Then (4.2) can be rewritten as (4.3) D'Z = B 35 where B = Pi P 1 *2 *L-1 0 ... 0 T q_l q 2 • • • Q.jJ_'j 0 ... 0 L = number of elements i n LIST and , Z = X1 X2 y1 y2 x NV yNV> / ; ' I(L-1)*(L-1) * °(L-1)*(NV-L+1 ) the same as those entries of D / For example, l e t G be the "graph of a cube", as shown i n Fi g . 8 . 1 , . 4 Let F i g . 8 A = / 0 1 0 1 0 0 0 1 / 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 \ 0 0 0 1; 0 1 0 1 V 1 0 0 0 1 0 1 0 matrix of G, then D = /-3 1 0 1 0 0 0 1 \ 0-3 1 0 1 0 0 0 0 1 - 3 1 0 1 0 0 1 0 1-3 0 0 1 0 0 1 0 0 - 3 1 0 1 0 0 1 0 1 - 3 1 0 . 0 0 0 1 0 1-3 1 / 1 0 0 0 1 0 1 -3 / and D' = /1 0 0 0' 0 0 0 . 0 0 1 0 o ! 0 0 0 0 0 0 1 0 i 0 0 0 0 0 0 0 i ! 0 0 0 0 0 1 0 0 -3 1 0 1 0 0 1 0 1 -3 1 0 0 0 0 1 0 1 -3 1 \1 0 0 0 1 0 1 -3 36, If B = then Z = 0 10 10 0 0 0 0 0 0 0 10 10 0 0 0 0 T 0 10 10 0 20/3 20/3 10/3 10/3 0 0 10 10 10/3 20/3 20/3 10/3 and F i g . 9 i s a representation of the graph of the cube i n the plane. ' Y f X F i g . 9 The programme, i s quite simple using UBC Library subroutines: (1 ) FSLE [9a] to solve a system of l i n e a r equations AX=B and (2) P l o t t i n g routines [9b]. Of course, we must decide how to choose the locations of the vertices on the outer c i r c u i t . Let G be the given graph. Recall that i n (3«3K Section 3: (1) Each edge of G i s defined by i t s i n i t i a l and terminal vertices with i t s " e l a s t i c i t y " , i n general the " e l a s t i c i t y " i s 1: for we. use t h i s to form matrix A. But sometimes we may wish- to change the " e l a s t i c i t y " of some of the edges i n a graph.(the reason'why 37. we want to do this w i l l become clear l a t e r i n th i s section). (2) We have NV and NE, the number of vertices and edges of G. respectively. (3) We also have the name of vertices on the outer c i r c u i t C which are stored i n array LIST(I), 1=1,L. Those data can be stored i n a f i l e and the f i l e supplied as input data to the graph-drawing programme. There i s a f l a g , called IFLAG i n the second part of our programme (Appendix D), which i s to be set by the user. I f IFLAG = 0, the data are read from the f i l e designated as UNIT 3, otherwise from UNIT 5 = *S0URCE* (Remark 4.3). In the '^former •.case.* i . e . -IFLAG = 0, our programme w i l l assign the outer c i r c u i t i n the f i r s t quadrant of XY-plane as a (L-1)-regular polygon i n the order i n which the vertices are given. Their coordinates are thus obtained from our programme to form matrix B and the adjacency matrix A w i l l be completed by using the " e l a s t i c i t y " of each edge. Otherwise, the outer c i r c u i t w i l l be assigned by the user anywhere i n the plane he wishes. In th i s case, the user has to provide a l l the edges with t h e i r i n i t i a l and terminal vertices along with t h e i r " e l a s t i c i t i e s " , x t h e names of vertices on the outer c i r c u i t and matrix B. In doing so, we l e t the user use the second part of our programme independently, i . e . one can draw a graph i f one wishes without using the f i r s t part of our programme. Now, we have a l l the required data, the programme then forms the matrix D' from matrix A and c a l l s subroutine FSLE to solve 38. D'Z=B i n (4.3). The unique n o n t r i v i a l solution 'is stored i n array Z. F i n a l l y , the plo t t i n g suroutines are called to plot G. For some graphs, i t i s important to get the "best" outer c i r c u i t . For a given graph, two different outer c i r c u i t s might result i n having two completely different straight l i n e represen-tations. Such an example w i l l be given i n Section 5(Fig.17a:and Fi g . 17b). In some cases, the coordinates of the solution i n equation (4.3) might be too close to be plotted by the plot t e r as distinguished points i n the plane because the outer c i r c u i t obtained i n our algorithm i s not the "best" one. One may want to improve the appearance of the graph as to change the " e l a s t i c i t y " of certain edges i n G. We s h a l l show how to obtain matrices A, D and D' i f we-.have to change the " e l a s t i c i t y " of certain edges of G by an example. I n i t i a l l y , l e t us consider G, the "graph of a Tetrahedron" as shown i n F i g . 1,0, then we have the adjacency matrix A as A = JO 1 1 1 \ 1 0 1 1 1 1 0 1 \ 1 1 1 0 / 2 3 F i g 10 From A we obtain 39. D = -3 1 -\ 1 1 t •3 1 1 \ and D' = - 3 / / 1 0 0 0 0 1 0 0 0 0 1 0 V 1 1 1 -3 I f the vertices 1, 2 and 3 are assigned at (0,1), (0,0) and (1,0) respectively i n the plane, then by solving the equation (4.3), the coordinates of vertex 4 i s then (1/3,1/3) (Pig.11a). Suppose the " e l a s t i c i t i e s " of the edges 4 to 1(or 1 to 4), 4 to 2(or 2 to 4) and 4 to 3(or 3 to 4) i n G have been changed to 2, 5 and 9 respectively, instead of forming the adja-cency matrix of G, we s h a l l form the matrix A* as follows: (0 1 1 2 \ 1 0 1 5 1 1 0 9 \ 2 5 9 0 / A* = and matrices D* and D*1 are obtained according to the scheme we stated i n early part of this; section. 1 1 \ 2 Now i f 1 1 2 \ •7 1 5 1 -11 9 5 9 -16 / B* = 0 1 /1 and D*1 0 0 then by solving D*'Z* = B* 0^  0 2 1 0 0 0 0 1 0 5 0 o \ 0 0 1 0 9 -16 / 40. we have Z* = 0 1 0 0 1 9/16 0 1/8 X Fi g . 11a F i g . 11b In short, i f we change the " e l a s t i c i t y " to m. . of an edge, say V. to V., then the "1" i n the ( i , j ) t h and ( j , i ) t h entries J_ J of the adjacency matrix A w i l l be replaced by m. .( since G i s an undirected graph), c a l l t h i s "new" matrix A*. Furthermore, the matrix D* i s just the matrix A* wit hi thej negative;'ofits ;row sums inserted on the diagonal and D*1 = I(L-1)*(L-1) i °(L-1)*(NV-L+1) the same as those entries of D* Thus i n our programme, the edges are read i n with t h e i r " e l a s t i c i t i e s " and matrices A or A* are formed automatically. Remark 4.1 If there i s a vertex V\ of degree 1 which i s adjacent to V. i n the given graph, the the coordinate of V. w i l l be the same as those of V. (Example 5.1). J Remark 4.2 I f there i s a vertex of - degree 2 which i s adjacent to V. and V, i n the given graph, then V., V. J K J 1 and V k are co l l i n e a r ( Example 5.3). Remark 4.3 *SOURCE* i s used as an input f i l e or device name. It i s normally the terminal i n conversational operation or the card reader i n batch operation, and i s the source where MTS gets i t s commands. The f i l e or device which *S0URCE* represents may be changed through"- use of the SOURCE command. *SOURCE* i s one of the MTS pseudo-device names. 42. 5. Results and Examples. The algorithms described i n Sections 3 and 4 have been programmed i n FORTRAN for an IBM 360/67 computer. The computer programme i d e n t i f i e s a simple connected planar graph G with up to 128 vertices and 400 edges i n the present version of GRAPHPACK. The execution time i s divided into two parts, Part I and Part II for the algorithms i n Sections 3 and 4 respectively. The execution time for some graphs are given i n Table 12 and graphs are i n Figures 12 - 18. Some s p e c i f i c examples for previous remarks are given i n the following. Number of vertices NV Number of edges NE Part I (in seconds) Part II (in seconds) Remark 4 12/2 0.13 0.22 Tetrahedron F i g . 12 8 24/2 0.21 0.24 Cube Fi g . 13 6 24/2 0.21 0.21 Octahedron Fi g . 14 20 60/2 0.54 0.39 Dodecahedron F i g . 15 ' : 12 60/2 0.49 0.31 Icosahedron F i g . 16 80 240/2 3.70 1 .85 "Soccer b a l l " Figures 17a & 17b 51 190/2 3.61 1 .24 Fi g . 18 Table 12 43. 44. 45. F i g . 1.4 46. j "Graph of Icosahedron" CM "Graph of a Soccer B a l l " oo CO • — i cr rf o to CM OO o' a o" O.B 0.0 0.4 I 1.2 1.6 ~1 2.0 < X AXIS F i g . 1.7a CM "Graph of a Soccer B a l l • Pig. !7b J 50. 51. Remark 5.1 The execution time of Part I depends on the number of i t e r a t i o n s performed i n finding an outer c i r c u i t of a given graph. For example, "the Soccer b a l l " , the execution time for 1, 2 and 3 i t e r a t i o n s are 3.70, 5.17 and 8.95 seconds respectively. Remark 5.2 In Section 4 we pointed out that two di f f e r e n t outer c i r c u i t s for a graph might result i n two different representations.. Figures 17a and 17b for "the Soccer b a l l " show that i f the outer c i r c u i t i s a "Pentagon" we get the former, i f the outer c i r c u i t i s a. . "Hexagon" we get the l a t t e r . Remark 5.3 The execution time for Part II does not include- the Plot t i n g time) f o r a graph. Although the algorithms are intended f o r use with simple connected planar graphs a l l of whose vertices, are-of degree ^  2 they"also get results of a sort for exceptional cases. Some of these are discussed i n th i s section. Treatment of Degenerate Cases. In the following examples, a l l the graphs i n Figures - a : are given and those i n Figures - b are the results we obtained. Example 5.1 1 — A ( 1 » 4 ) F i g . 19a Fi g . 19b 52. Since vertex 4 i s of degree one, we obtain the coordinates 4 coincide with those of vertex 1. In order to get the given graph, one may assign any coordinates to vertex 4.(Remarks 3.T and 4.1). Example 5.2 2 5 F i g . 20a F i g . 20b If the outer c i r c u i t i s C=(i»2\3,4) ,"-then 13^5,6,7*8) form a separable bridge of Type 3. In thi s example, we get the. same coordinates for vertices 3, 5, 6, 7, and 8. In fact, one may put (5,6,7,8) i n or out the square (1,2,3,4), then join the vertices 3 and 8 to form the given graph(Remark 3-1 and De f i n i t i o n 4.2; t h i s i s an 1-connected graph). Example 5.3 1 1 Fig . 21a F i g . 21b If the outer c i r c u i t i s (1,2,3,4,5,6), vertices 2,7,6 are c o l l i n e a r since vertex 7 i s of degree 2. 53, Pig. 22a Fig. 22b If the outer circuit i s (1,2,3,4), vertices 2,7,6,8,5,4 are collinear (Remark 4.2 and Definition 4.2; . t h i s i s a 2-connected graph). Example 5.4 Fig. 23 Clearly, this i s a nonplanar graph. If the outer circuit C is (1,2,3,4), then our programme identifies this graph as nonplanar. For i f the bridge formed by the connected component (5,6,7,8) and i t s vertices of attachment 1,2,3. and 4 i s i n array IN, the*! the Type 1 bridges B1 = (1,3) and B 2 = (2,4) are in array OUT. Since B^, alternates with B 2 a nonplanar graph message w i l l be delivered. If the outer circuit i s (5,6,7,8), since we did not check i f the connected component (1,2,3,4) i s planar or not, Fig. 24 This i s one of Kuratowski's basic nonplanar graphs. If the outer circuit i s (1,2,3,4,5), our programme identifies this as a nonplanar graph. If the outer circuit i s (1,2,3), since our programme did not check i f G.. are planar or not, the nonplanar message w i l l not be given. Instead i t w i l l be considered as a planar graph and the following graph i s obtained. 1 Fig. 25 55. 6. How to Use the Programmes. Our programme can be divided into two parts: Part I The main programme and subroutines of this part of algorithm are i n Appendices A, B and C. It finds an outer c i r c u i t C for the given graph G. For example, l e t us consider G, the "graph of a Tetrahedron", F i g . 10 i n Section 4. Then one has to provide the i n i t i a l and the terminal vertices of a l l the edges of G along with t h e i r " e l a s t i c i t i e s " , i . e . INITIAL TERMINAL ELASTICITY the edges of G. termination of G. 0 the l a s t graph to be tested. A non-positive value for any one of the three values associated with an edge indicates the termination of the data for a graph. I f there are some other graphs to be tested, a positive integer must be followed by using a new record (card) before the edges of a new graph to be:read in;/ otherwise a non-positive integer must be provided. After the programme i n Part I i s executed, one w i l l obtain the results on UNIT 6 = *SINK* (Remark 6.1). In the meantime, the i n i t i a l and the terminal vertices 56. with i t s " e l a s t i c i t y " of each edge, the number of edges (since we are working on undirected graphs, the number of edges obtained i s twice those of edges being read in) and the number of vertices of G, number of vertices and t h e i r names on the outer c i r c u i t C we found w i l l be recorded on UNIT J>. This should be a f i l e i f one wishes to draw the graph, or *DUI"IMY*(Remark 6.2) i f not. Part II The programme i s i n Appendix D. It w i l l draw a st r a i g h t - l i n e graph for the given graph G. The user has to give the data for IP1AG and ISIZE for each graph to be drawn. The l a t t e r w i l l give the region ISIZE*ISIZE i n which the graph to be plotted [9b]. (In fact, i n our programme ISIZE i s converted into r e a l , i n order to use the Plo t t i n g subroutines.) I f IP1AG = 0, the data are to be read from UNIT 3. I f IPLAG ^ 0, then the user has to provide: (1) N, the number of vertices of the graph G to be drawn. I f N i s non-positive, i t indicates there are no more graphs to be drawn. (2:) The i n i t i a l and the terminal vertices of each edge of G with i t s " e l a s t i c i t y " . (3) L, the number of vertices on the outer c i r c u i t C plus 1. (4) Array LIST, the "name" of vertices on C, one of them i s entered twice, i . e . the f i r s t and the l a s t ones are the same i n array LIST. The order of vertices i n LIST must be the same as 57. the c i r c u l a r order of C i n G. (5) The matrix B, i f the vertex V(I) i s on C then the user has to assign i t s coordinates to the I-th row of B, otherwise the entries of I-th row are zero. For example, i f we want to draw the graph G, F i g . 11b, we have to provide the following data: No. of Card. 1 : 1 6 2 ' 4 3 1 2 1 4 : 2 3 1 5 ; 3 1 1 6 : 4 1 2 7 4 2 5 8 4 3 9 9 ! -1 -1 -1 10 ! 4 11 : 1 2 3 1 12 0.0 1 .0 13 0.0 0.0 14 1 .0 0.0 15 0.0 0.0 16 : -1 IFLAG & ISIZE N = No. of vertices, edges of G and " e l a s t i c i t i e s " . termination of G L array LIST matrix B the l a s t graph to be drawn. In our programmes, the input data have the following FORMAT: 315 for integers and 2F10.1 for f l o a t i n g point numbers. 58. Remark 6.1 *SINK* i s one of the MTS pseudo-device names. It i s used as .an. output f i l e or device name. It i s normally the terminal i n conversational mode or the l i n e printer i n batch mode. However thi s designation may be changed through use of the SINK commend. Remark 6.2 *DUMMY* i s also one of the MTS pseudo-device names. This pseudo-device may be used anywhere a f i l e i s needed f o r some application. For output, i t represents an i n f i n i t e wastebasket: l i n e s are accepted and they disappear. On input, i t acts l i k e an empty f i l e : every time a l i n e i s requested an end-of-file condi-t i o n i s returned. BIBLIOGRAPHY 59. [ l l Fary, I., On Straight Line Representation of Planar i Graphs, Acta. S c i . Math., Szeged, 11(4), pp.229-233, 1948. [2] Fisher, G. J. & Wing, 0., An Algorithm for testing Planar Graphs from the Incidence Matrix, Proc. Seventh Midwest Symp. on C i r c u i t Theory, pp.67-75, May 1964. [ 3 ] Fisher, G. J. & Wing, 0., Computer Recognition-and ^ Extraction of Planar Graphs from the Incidence Matrix, IEEE Trans, on C i r c u i t Theory, Vol.CT-13, pp.154-163, June 1966. [ 4 ] Harary, F, Graph Theory, Addison-Wesley Publishing > Company, Inc., 1969. £5] Lin, P. M., On Methods of Detecting Planar Graphs, Proc. Eighth Midwest Symp. on C i r c u i t Theory, Colorado State University, Boulder, pp.1.1-1.9, June 1965. |^6 ] Liu, C. L., Introduction to Combinatorial Mathematics, McGraw-Hill Book Company, New York, 1968. [7] Tutte, W. T., Convex Representation of Graphs, Proc. London Math. Soc. (3), 10, pp.304-320, 1960. [ 8 J Tutte, W. T., How to Draw a Graph, Proc. London Math. S o c , Vol. 1 3 , pp.743-768, A p r i l 1963. jj3a] UBC SLIN (Moore, C ) , Fast Simultaneous Linear Equations and Matrix Inversion Package, UBC Computing Centre, Subject Codes: 45.1, 45.4, March 1970. [9b] UBC PLOT (Coulthard, W. J . ) , UBC P l o t t e r Subroutines, UBC Computing Centre, Subject Codes: 08.6, Jan. 1969. j j o ] Woo, L., An Algorithm for Straight Line Representation of Simple Planar Graphs, IBM, New York S c i . Center Report, No. 320-2918, October 1967. 60. ST G R A P H 1 C A P P E N D I X A 2 C 3 I M P L I C I T I N T E G E R * 4 ( A - Z ) 4 R E A L T I M E 1 * T I M E 2 , S C L 0 C K 5 COMMON P ( 4 Q 0 ) , S ( 4 0 0 ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) t E P R O P ( 4 0 0 ) , V P R O P ( 1 2 8 ) 6 CON HON E D 0 ( 2 C 0 ) , ED I { 2 0 0 ) , I D E L ( 4 0 0 ) , N E , N V 7 D I M E N S I O N I N ( 1 0 0 ) , 0 U T ( 1 0 0 ) ,TE ST( IOC ) 8 D I M E N S I O N N O D E ( 4 0 0 ) , A N S ( 1 0 0 ) , L 1 S T ( 1 0 0 ) -9 D I M E N S I O N P R I M E ( 2 0 ) 10 D I M E N S I O N V E 1 ( 4 C 0 ) , V E 2 ( 4 0 0 ) , E L A S T ( 4 G O 11 D I M E N S I O N P R O P ( 4 0 0 ) , IN 1 ( 1 0 0 ) , O U T 1 ( 1 C O ) 12 DATA P R I M E / 2 , 3 , 5 , 7 , 1 1 , 1 3 , 1 7 , 1 9 , 2 3 , 2 9 , 13 $ 3 1 , 3 7 , 4 1 , 4 3 , 4 7 , 5 3 , 5 9 , 6 1 , 6 7 , 7 1 / 14 DATA N E G , O N E S / 1 0 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / 15 DATA G I S , G I S l / 2 5 6 , 2 5 5 / 16 DATA C I R C , C I R C 1/ 1 6 7 7 7 2 1 6 , 1 6 7 7 7 2 1 5 / 17 C G I S = 2 * * 8 = 2 5 6 18 C C I R C = 2 * * 2 4 = 1 6 7 7 7 2 1 6 19 C NEG = 2 * * 3 0 = 1 0 7 3 7 4 1 8 2 4 2 0 1 0 0 F O R M A T ( 1 0 1 5 ) 2 1 1 0 1 F G R M A T U X t 2 5 1 5 ) 22 102 F O R M A T ! I X , 1 0 1 1 2 ) 2 3 K 0 N = 1 0 0 O 2 4 2 1 0 C A L L I N I T L 25 T I M E 1 = S C L 0 C K ( 0 . ) 26 DO 2 2 0 1 = 1 , 1 0 0 2 7 L I S T ( I ) = C 2 8 N C C E d )=C 2 9 A N S ( I ) = 0 30 2 2 0 C O N T I N U E 31 DO 2 2 2 1 = 1 , 4 0 0 32 E P R O P d )=0 3 3 2 2 2 C C N T I N U E 3 4 DO 2 2 4 1 = 1 , 1 2 8 3 5 V P R O P ( I ) = 0 3 6 2 2 4 C C N T I N U E 3 7 C E A C H EDGE I S READ I N BY I T S I N I T I A L ANC T E R M I N A L V E R T I C E S 3 8 C W ITH I T S " E L A S T I C I T Y " . 39 1=0 4 0 W R I T E ( 6 t 2 9 9 ) 41 2 9 9 F O R M A T ! / / ' • » * THE EDGES AND THE IR R E S P . " E L S T I C I T Y " OF G I V E N 42 $ G R A P H ARE * , / ) 4 3 2 0 0 1=1 + 1 44 MN=KON+I 4 5 R E A D ( 5 , 1 C G ) V E K I ) , V E 2 ( I ) ,E LA ST ( I ) 4 6 W R I T E ( 6 , 1 0 2 ) V E 1 ( I ) , V E 2 ( I ) , E L A S T { I ) 4 7 WRI TE( 3 ' M N t l G l ) VE1 ( I ) »VE2 ( I ) f E L A S T ( I ) 4 8 C A N O N - P O S I T I V E V A L U E FOR ANY ONE O F V E 1 { I ) » V E 2 d ) AND E L A S T ( I ) 4 9 C I N D I C A T E S THE T E R M I N A T I O N O F THE DATA FOR A GRAPH 5 0 I F ( V E l d ) . L E . 0 . G R . V E 2 ( I ) . L E . 0 ) GO TO 2 9 0 51 C A L L N E W E 0 ( V E 1 ( I ) * V E 2 ( I ) ) 5 2 GO TO 2 0 0 5 3 2 9 0 C C N T I N U E 54 I 1 = 1 - 1 5 5 DO 2 3 0 J = 1, I I 5 6 C A L L N E W E C ( V E 2 ( J ) , V E 1 ( J ) ) 57 2 3 0 C O N T I N U E 61 . 58 C ************************************** ****************************** 5 9 C F I N C A C I R C U I T C 6 0 C R E A L N V = THE NO. OF V E R T I C E S OF G 61 C R E A L N E = THE NUMBER OF EDGES OF G 6 2 R E A L N E = N E 6 3 RE ALNV=NV 6 4 NXY=0 65 DO 3 0 0 1 = 1 ,NV 6 6 C A L L A P A T H ( I , I , L I S T , L , F A I L ) 6 7 I F ( F A I L . E G . 0 ) GO TO 3 1 0 6 8 3 0 0 C C N T I N U E £ 9 3 1C C O N T I N U E 7 0 W R I T E l 6 , 1 0 3 ) 7 1 1 0 3 F O R M A T < / / / • THE V E R T I C E S ON THE C I R C U I T A R E ' ) 72 W R I T E ( 6 , 1 0 1 ) ( L I S T ( I ) ,1=1 , L ) 73 C D E L E T E THE V E R T I C E S OF C AND A L L OF THE 74 C EDGES I N C I D E N T TO T H E S E V E R T I C E S 75 1 5 9 9 C C N T I N U E 76 L L = L - 1 77 DO 4 0 0 1=1 , L L 78 C A L L D E L V E ( L 1ST ( I ) ) 7 9 4 0 0 C C N T I N U E ec C 81 c GROUP T H E S U B G R A P H OF G THAT R E M A I N S I N T O 82 c A SET CF CONNECTED COMPONENTS 8 3 C A L L A L P A T H ( V A L , K G O E ,N0 , A N S , I X ) 8 4 I F ( I X . L E . 1 ) GO TO 4 5 C 85 c RESTORE A L L D E L E T E D EDGES AND V E R T I C E S TO THE G R A P H 86 C A L L R E S T A L £7 c ******************************************************************** 88 c U S I N G VPROP TO F I N D THE T Y P E OF EACH B R I D G E 89 c L I S T C I = 1 , L - 1 ) C O N S I S T S OF THE V E R T I C E S ON THE C I R C U I T 9C c WHICH MAY BE C O N S I D E R E D AS T Y P E 0 91 c NOTE T Y P E 1 ARE C O N S I D E R E D AS TYPE 0 NOW 92 DC 5 0 0 1 = 1 , IX 9 3 I F ( A N S ( I ) . E Q . 9 9 9 9 ) GO TO 5 0 0 94 V P R O P ( A N S ( I ) ) = 3 95 5 0 0 C C N T I N U E 96 T=NV+1 97 BC = C 98 COUNT=0 99 DC 6 0 0 IA = 1, IX I CO I F { A N S ( I A ) . E G . 9 9 9 9 ) GO TO 6 9 0 1C 1 I = A N S ( I A ) 1 0 2 I F ( V P R O P ( I ) . E Q . - l ) GO TO 6 0 0 1 0 3 I F ( V P R O P ( I J . G E . G I S ) GO TO 6 0 0 1C4 I F ( V P R 0 P ( I ) . N E . 3 ) GO TC 6 0 0 1 0 5 C0UNT=C0UNT+1 1 0 6 I F ( C O U N T . E Q . l ) GO TO 6 2 0 1 0 7 C ************************************ ** ****************************** 1 0 8 C TO F I N D T Y P E 3 B R I D G E S . 1 0 9 C I D E N T I F Y A C O N N E C T E D COMPONENT WITH A NEW V E R T E X T=NV+1 1 1 0 C AND S E T T I N G V P R G P ( T ) = 5 1 1 1 63C V P R O P ( I ) = V ( N E W ) * G I S + V P R O P { I ) 1 1 2 T T = L - 1 1 1 3 J = 0 1 1 4 6 4 0 C A L L N E X E D O ( I , J ) 1 15 I F ( J . E Q . C ) GO TO 6 8 0 1 1 6 DC 6 5 0 L I = l t ' T T 1 1 7 I F ( S ( J ) . N E . L I S T ( L I ) ) GC TO 6 5 0 1 1 8 8C=BC+1 6 2 . 1 1 9 E P R G P < B C)=LISTai ) * G I S + 3 1 2 0 E P R O P ( B C ) = L I * C I R C + E P R O P ( B C ) 1 21 C A L L N E W E D I V ( N E W ) , L I S T ( L I ) ) 1 2 2 C A L L N E W E D ( L I S T ( L I ) » V < N E W ) ) 1 2 3 6 5 0 C O N T I N U E 1 2 4 GO TO 6 4 0 1 2 5 6 2 0 N E W = N E W V E ( T , 0 , 0 ) 1 2 6 VPROPdMEW ) = 5 1 2 7 NXY=NXY+1 1 2 8 C THE H I G H E S T ORDER 3 EYTES OF V P R O P ( N E W ) C O N T A I N THE N O . OF V E R T I C E S 1 2 9 C IN T H I S B R I D G E , I . E . , THE WEIGHT OF NEW V E R T E X . 1 3 0 BC=BC+1 131 E P R C P ( B C ) = N E W * G I S + 5 1 3 2 GO TO 6 3 0 1 3 3 6 9 0 I F I C O U N T . E Q . C ) GO TO 6 C 0 1 3 4 V P R 0 P ( N E W ) = V P R O P { N E W ) + C O U N T * G I S 1 3 5 CCUNT=G 1 3 6 T=NV+1 1 3 7 BC=BC+1 1 3 8 E P R 0 P ( B C ) = - 1 1 3 9 GO TO 6 0 0 1 4 0 6 8 0 C A L L D E L V E ( I ) 1 41 6 0 0 C O N T I N U E 142 GC TO 8 2 0 1 4 3 C THE N O N D E L E T E D V E R T I C E S FORM P - H G R A P H , I . E . , 1 4 4 C THE ABOVE FORMS THE P S E U D O - H A M I L T O N I A N G R A P H OF THE G I V E N G R A P H . 1 4 5 C THE V E R T I C E S B E L O N G TO T Y P E 3 B R I D G E S H A V E B E E N D E L E T E D . .14 6 C fc******************************-********* 1 4 7 C TO F I N D T Y P E 2 B R I D G E S FROM VPROP AND 1 4 8 C STORE ATTACHMENT V E R T I C E S IN EPROP . 1 4 9 4 5 0 C O N T I N U E 1 5 0 C THERE I S NO T Y P E 3 B R I D G E 1 5 1 C A L L R E S T A L 152 BC=0 1 5 3 82 0 C O N T I N U E 1 5 4 KEEP=BC 1 5 5 L L = L - 1 1 5 6 DC 8 0 0 I = 1 , R E A L N V 1 5 7 I F ( V P R 0 P ( I ) . N E . 2 ) GO TO 8 0 0 1 5 8 BC=BC+1 1 5 9 E P R O P ( B C ) = I * G I S + 2 1 6 0 BCC=8C+1 1 6 1 J=C 1 6 2 8 4 0 D=NE X E D G ( I » J ) 1 6 3 I F ( C . E G . O ) GO TO 6 7 0 1 6 4 F LAG=0 1 6 5 DO 85C KK = 1 , L L 1 6 6 I I = L I S T ( K K ) 1 6 7 I F ( S ( J ) . E Q . I I . O R . P ( J ) . E Q . I I ) GO TO 8 8 0 1 6 8 GC TO 85C 1 6 9 8 8 0 BC=BC+1 1 7 0 C A L L D E L E D U t l l t O ) 171 C A L L DELED 1 1 1 , 1 , 0 ) 1 7 2 E P R O P ( B C ) = I I * G I S + 2 1 7 3 E P R 0 P ( 8 C ) = K K * C I R C + E P R O P ( B C ) 1 7 4 F L A G = 1 1 7 5 GO TO 8 4 0 1 7 6 8 5 0 CONT INUE 1 7 7 8 7 0 I F < F L A G . E Q . O ) GC TO 800 1 7 8 DC 8 1 0 T E M P = B C C , E C 63. I 7*5 T T = M O D ( E P R O P { T E K P ) ,C I R C ) / C I S 1 8 0 E R R 1 = 1 0 0 0 181 C A L L R E S T E D { I , T T , 0 , E R R 1 ) 1 8 2 E R R 2 = 1 0 0 C 1 8 3 C A L L R E S T E D t T T , I , G , E R R 2 ) 1 8 4 C ERRS ARE 0 I F T F E R E S T O R A T I O N I S S U C C E S F U L 185 8 1 0 C O N T I N U E 1 8 6 BC=BC+1 1 8 7 E P R 0 P ( B C ) = - 1 1 8 8 8 0 0 C O N T I N U E 1 8 9 I F ( B C - l . E C . K E E P ) GO TO 8 9 0 1 9 0 GO TO 7 0 0 1 9 1 C * * * * * * * * * £ 4 3 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 9 2 C L O O K I N G FOR T Y P E 1 B R I D G E S AND STORE E A C H P A I R OF 1 9 3 C ATTACHMENT V E R T I C E S I N E P R C P . 1 9 4 C NOTE THAT WE S H A L L D E L E T E A L L THE EDGES ON THE C I R C U I T 1 9 5 C AND T Y P E 1 B R I D G E S 1 9 6 8 9 0 E P R C P ( B C ) = 0 1 9 7 B C = B C - 1 1 9 8 C T H E R E IS NO T Y P E 2 B R I D G E 1 9 9 7 0 0 C O N T I N U E 2 G 0 K E E P 1 = B C 2 0 1 L L = L - 1 2 0 2 K = l 2 0 3 7 1 0 KK=K+1 2 0 4 I = L I S T ( K ) 2 G 5 J = 0 2 0 6 7 2 0 C A L L N E X E D O l 1 , J ) 2 0 7 I F ( J . E Q . O ) GO TO 7 1 0 2 0 8 I I = L I S T ( K K ) 2 0 9 I F ( S ( J J . N E . I I ) GO TO 7 2 0 2 1 0 C A L L DELEDC It 1 1 , 0 ) 2 1 1 C A L L DEL E D { I I , I ,C ) 2 1 2 K=KK 2 1 3 I F { K . L E . L L ) GO TO 7 1 0 2 1 4 L F = L - 2 2 1 5 DO 7 6 0 K = 1 , L F 2 1 6 I = L I S T ( K ) 2 1 7 J=0 2 1 8 75G D = N E X E D G ( I , J ) 2 1 9 I F ( D . E Q . O ) GO TO 7 6 0 2 2 0 K1=K+1 2 2 1 DC 7 6 6 KK =K1 , L L 2 2 2 I I = L I S T ( K K ) 2 2 3 I F ( S t J ) . E G . I I . O R . P ( J ) . E Q . I I ) GO TO 7 8 0 2 2 4 GO TO 7 6 6 2 2 5 7 8 0 C A L L D E L E D C I , I I t C ) 2 2 6 C A L L D E L E D ( 1 1 » I , C ) 2 2 7 V P R C P ( I ) = 1 2 2 8 V P R G P ( I I ) = 1 2 2 9 BC=BC+1 2 3 0 E P R 0 P ( 8 C ) = I * G I S + 1 2 3 1 E P R O P ( B C ) = K * C I R C + E P R C P ( B C ) 2 3 2 BC=BC+1 2 3 3 E P R 0 P ( B C ) = I I * G I S + 1 2 3 4 E P R O P < B C ) = K K * C I R C + E P R O P ( B C ) 2 3 5 BC=BC+1 2 3 6 E P R 0 P ( B C ) = - 1 2 3 7 7 6 6 C C N T I N U E 2 3 8 GO TO 75C 64. 2 3 9 7 6 0 C O N T I N U E 2 4 0 I F O C - l . E Q . K E E P l ) GO TO 7 8 5 2 4 1 I F ( B C . E Q . O ) GO TC 1 0 0 0 2 4 2 GO TO 7 9 9 2 4 3 7 8 5 E P R O P ( B C ) = 0 2 4 4 B C = B C - 1 2 4 5 C THERE I S NO TYPE 1 B R I D G E 2 4 6 7 9 9 C O N T I N U E 2 4 7 c ********************* ******************************************** 2 4 8 C F I N D THE A L T E R N A T E B R I D G E S 2 4 9 DO 1 1 1 1 N=ltBC 2 5 0 P R C P ( N ) = E P R O P ( N ) 2 5 1 1 1 1 1 C C N T I N U E 2 5 2 C A L L A L T E R ( B C , P R O P , L I S T , L , I N , I , O U T , O T,NOB I N , N O BOUT,£1000) 2 5 3 I F ( I . E Q . Q ) GO TO 1GGC 2 5 4 I F ( G T . E Q . O . O R .OUT (1 ) . E C O ) GO TO 1G0Q 2 5 5 I F { N O B O U T . L T . 2 ) GO TC 3 0 0 0 2 5 6 C A L L ERA S E ( L I S T , L ) 2 5 7 C A L L A L T E R ( O T , O U T , L I S T , L , I N 1 ,1 1 , O U T 1,0T 1 , N O B I N 1 , N O O U T 1 f 1 1 0 0 0 ) 2 5 8 I F ( N 0 G U T 1 . E Q . 0 ) GO TO 3 0 0 0 2 5 9 W R I T E ( 6 » 3 1 G 0 ) 2 6 0 3 1 0 0 F O R M A T ! / / • ' T H E G I V E N G R A P H I S N O N P L A N A R 1 ) 2 6 1 L = l 2 6 2 L I S T ( L ) = C 2 6 3 GO TO 10G0 2 6 4 c * * * ***************************************************************** 2 6 5 C D E L E T E A L L B R I D G E S IN THE C I R C U I T C 2 6 6 3 0 0 0 C C N T I N U E 2 6 7 DO 1 1 0 0 11 = 1, I 2 6 8 I F ( I I + 1 . G T . I ) GO TG 1 1 0 0 2 6 9 I F ( I N ( I I ) . L E . O . A N D . I N ( I I + l ) . G E . C I R C ) GO TO 1110 2 7 0 I F ( I N ( I I ) . L E . 0 ) GO TO 11C0 271 I F U N ( I I ) . G E . C I R C ) GO TO 1 1 0 0 2 7 2 V 1 = I N ( I I ) / G I S 2 7 3 C V I I S THE D E L E T E D B R I D G E I N THE C I R C U I T 2 7 4 C A L L D E L V E ( V l ) 2 7 5 GC TO 1100 2 7 6 11.10 N = I I + 1 2 7 7 V l = M O D < I N ( N ) , C I R C ) / G I S 2 7 8 V 2 = M 0 D ( I N ( N + 1 ) , C I R C ) / G I S 2 7 9 C A L L D E L E D ( V I ,V2 ,G ) 2 8 0 C A L L DEL E D ( V 2 , V I , Q ) 2 8 1 1 1 0 0 C C N T I N U E 2 8 2 C 2 8 3 C R E S T O R E A L L B R I D G E S O U T S I D E THE C I R C U I T C 2 84 DC 1 2 0 0 11=1,OT 2 8 5 I F ( O U T ( I I ) . L T . 0 ) GO TO 1 2 0 0 2 8 6 T Y P E = M O D ( O U T ( I I ) , G I S ) 2 8 7 I F ( T Y P E . E Q . 5 ) GO TO 1 2 1 0 2 8 8 I F ( T Y P E . E G . l ) GO TO 1 2 2 0 2 8 9 GO TO 1 2 0 0 2 9 0 C * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 2 9 1 C IF THE BR IDGE IS OF T Y P E 3 , R E S T O R E A L L THE V E R T I C E S C O N T A I N E D I N 2 9 2 C T H I S B R I D G E AND D E L E T E THE NEW V E R T E X 2 9 3 1 2 1 0 NEW = O U T ( I I ) / G I S 2 9 4 DC 1 2 1 1 J = l , R E A L N V 2 9 5 I F { V P R O P ( J ) . L T . G I S ) GO TO 1 2 1 1 2 9 6 V 1 = V P R 0 P { J ) / G I S 2 9 7 I F ( V l . N E . N E W ) GO TO 1211 2 9 8 C A L L R E S T V E ( J ) 65. 2 9 9 . 1211 C O N T I N U E 3 0 0 C A L L D E L V E ( N E W ) 3 0 1 GC TO 1 2 0 0 3 0 2 1 2 2 0 I F (OUT ( I I + U . E Q . - 1 ) GO TO 1 2 0 0 3 0 3 0 N 1 = 0 U T { I I ) / C I R C 3 0 4 0 N 2 = 0 U T ( I I + l ) / C I R C 3 C 5 E R R 1 = 1 0 0 0 3 0 6 C A L L R E S T E D ( O N I » C N 2 » 0 ? E R R 1 ) 3 0 7 E R R 2 = 1 0 0 G 3 0 8 C A L L R E S T E O ( O N 2 , C N 1 , 0 , E R R 2 ) 3 C 9 1 2 C 0 C C N T I N U E 3 1 0 C A L L ERA S E ( L I S T » L ) 3 1 1 . C RESTORE A L L EDGES ON THE C I R C U I T 3 1 2 L L = L - 1 3 1 3 - DO 1 2 5 0 J = 1 * L L 3 1 4 V 1 = L I S T ( J ) 3 1 5 V 2 = L I S T ( J + 1 ) 3 1 6 E R R 1 = 1 0 0 0 3 1 7 ERR2=1000 3 1 8 C A L L R E S T E O C V 1 , V 2 , 0 , E R R 1 ) 3 1 9 C A L L R E S T E D ( V 2 , V 1 , 0 , E R R 2 ) 3 2 0 1 2 5 0 C O N T I N U E 3 2 1 C TO D E L E T E EDGES ON THE C I R C U I T WHICH ARE COVERED 3 2 2 C BY ANY B R I D G E S IN ARRAY OUT 3 2 3 J = l 3 2 4 F I X J = J 3 2 5 1 2 6 0 I F ( O U T ( J ) . G E . C I R C ) GO TO 1 2 6 2 3 2 6 B R D G £ = O U T ( J ) / G I S 3 2 7 J = J + 1 3 2 8 1 2 6 2 F I R S T = J 3 2 9 N 1 = G U T ( F I R S T J / C I R C 3 3 0 1 2 6 5 J = J+1 '3 31 I F (OUT( J ) .NE . - 1 ) GO TO 1 2 6 5 3 3 2 L A S T = J - 1 3 3 3 N 2 = 0 U T ( L A S T ) / C I R C 3 3 4 N N 2 = N 2 - 1 3 3 5 NN1=N1 + 1 3 3 6 DG 1 2 7 0 K=N1,NN2 3 3 7 V 1 = L I S T ( K ) 3 3 8 V 2 = L I S T ( K + 1 ) 3 3 9 C A L L D E L E D ( V 1 , V 2 , 0 ) 3 4 0 C A L L D E L E D ( V 2 , V 1 , 0 ) 3 4 1 1 2 7 0 C O N T I N U E 3 4 2 DO 1 2 7 1 K=NN 1» NN2 3 4 3 V 1 = L I S T ( K ) 3 4 4 I F ( F I X J . E Q . F I R ST ) GO TO 1 2 7 2 3 4 5 C A L L D E L E D l V 1 , 8 R D G E , 0 ) 3 4 6 C A L L D E L E D < B R D G E , V 1 , 0 ) 3 4 7 1 2 7 2 C A L L D E L V E ( V 1 ) 3 4 8 1 2 7 1 CONT INUE 3 4 9 J = J + 1 3 5 0 I F ( J . L T . C T ) GO TC 1 2 6 0 3 5 1 1 3 C 0 C O N T I N U E 3 5 2 C 3 5 3 DC 1 3 1 0 K = 1 , N V 3 5 4 C A L L A P A T H ( K , K t L I S T , L , F A I L ) 3 5 5 I F ( F A I L . E Q . O ) GO TO 1 3 5 9 356 v. 357 •i 3 5 8 35 9 360 361 362 363 : 364 : 365 366 367 36 8 369 ':- 3 70 - , 3 7 1 372 373 374 - 375 376 v 377 378 3 79 36C 381 3 82 3 63 3 84 3 85 386 367 368 389 39C 391 392 393 394 395 396 397 398 3 99 400 401 402 403 404 405 • 4C6 407 END OF 1310 1311 1359 116 1360 1370 1361 10C0 2200 2100 2300 C IF 4999 5000 », ' OUTER CIRCUIT CAN NOT BE FOUND * ) THE VERTICES ( LIST(K),K = 1 ,L) ON THE NEXT CIRCUIT ARE') GO TO 1599 CCNTINUE WRITE(6,1311) FORMAT!//* L=l LIST(L)=0 GO TO 1000 CONTINUE WRITE!6,116) FORMAT!//' ', WRITE(6,1C2) KK = R EALNV +1 K KK = REALNV+NXY DO 1360 K = l t RE ALNV VPROPIK)=G CCNTINUE DO 1370 K=1,EC EPROP(K)=Q CONTINUE CALL RESTAL IF (NXY.LE.O) 00 1361 K=KK f KKK VPR0P!K)=-1 CALL CELVE(V!K)) CONTINUE GO TO 1599 CONTINUE WRITE(6,22G0) FORMAT(/« ' , ' THE NUMBER LI=KON+480 WRITE(6,1C2) REALNVt REALNE MRITE(3*LIt102) REALNV,REALNE WRITE!6,2ICO) FORMAT(//* ', » THE VERTICES ON IF(L.LE.l) GO TO 2300 CALL ERASE(LIST»L) CONTINUE LI=K0N+490 WRITE!3»LI,10 2 ) L LI=K0N+491 WRITE!3»LI,102 ) (LIST(K), K=1,L) WRITE(6,102) CLIST(K), K= 1, L ) READ 100,AGAIN AGAIN IS A POSITIVE INTEGER THEN LI=K0N+499 WRITE(3'LI ,102 ) AGAIN KON=KON+5C0 TIME2=SCL0CK(T IME1 ) WRITE!6,4999) TIME2 FORMAT!//« THE EXECUTION TIME =«,F10.2, IF!AGAIN.GT.C ) GO TO 210 STOP END 6 6 . OF VERTICES AND EDGES OF THIS GRAPH ARE' THE OUTER CIRCUIT ARE' ) START A NEW GRAPH, OTHERWISE HALT SECONDS') FILE C^OMMENT "SKIP TO TCP OF NEXT PAGE" $COPY *SKIP 67. $ L I S T G R A P H . S 1 C 2 C 3 C 4 C 5 6 7 8 9 10 11 12 13 14 10 15 16 1 7 18 19 2 0 2 1 15 22 2 3 2 4 2 0 25 2 6 2 7 2 8 2 9 C 3 0 C 31 3 2 C 3 3 34 3 5 3 6 3 7 10 38 3 9 4 0 4 1 4 2 4 3 44 4 5 4 6 4 7 4 8 4 9 5 0 51 52 5 3 54 55 A P P E N D I X 8 G R A P H P A C K S U B R O U T I N E I N I T L I M P L I C I T I N T £ G E R * 4 { A - Z ) COMMON P ( 4 G 0 ) , S ( 4 C G ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V i 1 2 8 ) , E P R O P ( 4 0 0 ) , V P R 0 P ( 1 2 8] COMMON E D O ( 2 0 0 ) , E D I ( 2 0 0 ) , I O E L ( 4 0 0 ) , N E , N V MAX=2C0 MMAX=400 DO 10 1=1,MAX E D O ( I ) = 0 E C U I ) = G C C N T I N U E DC 15 I = 1 ,MMAX P L ( I )=0 S L ( I ) = 0 I C E L C I ) = 0 P ( I ) = 0 S ( I ) = 0 C C N T I N U E DO 2 0 1 = 1 , 1 2 8 V ( I ) = G C O N T I N U E NE=0 NV=G R E T U R N END S U B R O U T I N E N E W E D ( V 1 » V 2 ) INSERT NEW EDGE I M P L I C I T I N T E G E R * 4 ( A - Z ) COMMON P ( 4 0 0 ) , S ( 4 C C ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) , E P R O P ( 4 0 0 ) , V P R O P ( 1 2 8 ) COMMON E D 0 < 2 G Q ) , E D I ( 2 0 0 ) , I D E L ( 4 0 0 ) , N E , N V DATA N E G , O N E S / 1 0 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / F O R M A T ( / / » « , • V E R T E X M I S S I N G ' ) MAX=128 LV=0 MV=0 I F ( V l . E Q . O ) GO TO 50 J = 1 0 0 0 0 C A L L V E R N A M t V I , J ) I F ( J . E Q . G ) I R = N E W V E ( V 1 , L V ,MV) I F ( V 2 . E Q . G ) GO TO 5G J = 1 0 0 0 0 C A L L V E R N A M ( V 2 » J ) I F ( J . E Q . O ) IR=NEfcVE( V 2 , L V , M V ) NNE=NE NE=NE+1 P ( N E ) = V 1 S ( N E )=V2 J = NE I F ( N N E . L E . O ) GO TO 18 DO 10 1 = 1 , N N E 5 6 J = J - 1 5 7 I F { P ( J ) . N E . V 1 ) G 0 TO 10 58 S L ( J ) = NE 68. 5 9 GC TO 15 6 0 1 0 C C N T I N U E 61 15 J=NE 6 2 DO 20 1=1 ,NNE 6 3 J = J - 1 6 4 I F ( S ( J ) . N E . V 2 ) GC TO 20 65 P L ( J ) = N E 6 6 GO TO 18 6 7 2 0 C C N T I N U E 68 18 I F ( V l . G T . M A X ) GO TO 25 6 9 I F ( L A N D ( V { V I ) , O N E S ) . N E . V I ) GO TO 5 7 0 I F ( E D 0 ( V 1 ) . N E . G ) GO TO 25 71 E D 0 ( V 1 ) = N E 72 25 I F ( V 2 . G T . M A X ) GO TO 40 7 3 I F ( L A N D ( V ( V 2 ) , O N E S ) . N E . V 2 ) GO TO 4C 74 I F t E D I ( V 2 ) . N E . 0 ) R E T U R N 75 E D I ( V 2 ) = N E 76 R E T U R N 77 5 DC 3 0 1=1 ,MAX 78 I F ( L A N D I V U ) ,ONES J . N E . V l ) GO TO 3 0 79 I F ( E D O U ) . E G . O ) E D C ( I ) = N E 80 GO TO 25 8 1 30 C C N T I N U E 82 GO TO 25 83 40 DC 45 1=1 ,MAX 84 I F ( L A N D ( V ( I ) , O N E S ) . N E.V 2 ) GO TO 45 85 I F (ED I ( D . E Q . O ) E D I ( I ) = N E 86 RETURN 87 4 5 C C N T I N U E 88 R E T U R N 89 5G W R I T E ( 6 , 1 C 0 ) V 1 , V 2 9 0 RETURN 91 END 9 2 C 93 C 9 4 F U N C T I O N N E W V E i V N , V I , V 2 ) 95 C I N SERT NEW V E R T E X 9 6 I M P L I C I T I N T E G E R * 4 ( A - Z ) 9 7 COMMON P ( 4 C 0 ) , S ( 4 C 0 ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V U 2 8 ) , E P R O P ( 4 0 0 ) , V P R O P ( 1 2 8 ) 9 8 COMMON E D O ( 2 0 0 ) , E C I ( 2 G G ) , I D E L ( 4 0 0 ) » N E » N V 99 1 0 0 F O R M A T ( / / * * , « NUMBER OF V E R T I C E S E X C E E D S * t 1 7 ) I CO MAX=128 1 0 1 NV=NV+1 1 0 2 I F ( N V . G T . M A X ) GO TO 27 1 0 3 I F ( V N . G T . M A X ) GO TO 20 1 0 4 I F ( V ( V N ) . N E . O ) GO TO 20 1 0 5 V ( V N ) = V N 1 C 6 N E k V E = V N 1 0 7 26 I F ( V l . E Q . C ) GO TO 10 1 0 8 C A L L V E R N A M ( V 1 , J ) 1 0 9 I F ( J . E O . O ) GO TO 10 1 1 0 C A L L N E W E D ( V 1 » V N ) 1 1 1 " E C I ( N V ) = N E 1 1 2 10 I F ( V 2 . E Q . O ) GO TC 15 1 1 3 C A L L V E R N A M ( V 2 , J ) 1 1 4 I F ( J . E Q . G ) GO TO 10 1 1 5 C A L L N E W E D ( V N , V 2 ) 1 1 6 E D 0 ( N V ) = N E 1 1 7 15 R E T U R N 69. 1 1 8 20 DO 25 K = l f M A X 1 1 9 I F ( V C K ) . N E . O ) GO TO 25 1 2 0 V ( K ) = V N 1 2 1 NEVtVE=K 1 2 2 GO TO 26 12 3 25 C C N T I N U E 1 2 4 27 W R I T E ( 6 , 1 0 0 ) HAX 1 2 5 R E T U R N 1 2 6 END 1 2 7 C 1 2 8 C 1 2 9 S U B R O U T I N E D E L E D ( V 1 , V 2 , M ) 1 3 0 C D E L E T E EDGE 1 3 1 I M P L I C I T I N T E G E R S ( A - Z ) 1 3 2 COMMON P ( 4 G 0 ) , S ( 4 C 0 ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) t V I 1 2 8 ) , E P R O P ( 4 G 0 ) , V P R O P 1 1 2 8 ) 1 3 3 COMMON E D O ( 2 0 0 ) , E D I ( 2 0 0 ) » I D E L ( 4 0 0 ) , N £ ,NV 1 3 4 I = M 1 3 5 I F ( I . E Q . O ) GO TC 5 1 3 6 I D E L ( I ) = - l 1 3 7 R E T U R N 1 3 8 5 DO 10 1 =1 ,NE 1 3 9 I F ( P d ) . N E . V l ) GC TO 10 1 4 0 I F I s m . N E . V 2 ) GO TO 10 1 4 1 I C E L ( I ) = - l 1 4 2 RETURN 1 4 3 10 C O N T I N U E 1 4 4 DO 11 1=1 ,NE 1 4 5 I F ( P ( I J . N E . V 2 ) GO TO 11 1 4 6 I F ( S U ) . N E . V 1 ) GC TO 11 1 4 7 I D E L ( I ) = - 1 1 4 8 R E T U R N 1 4 9 11 C O N T I N U E 1 5 0 C EDGE ! D E F I N E D BY V I AND V 2 DOES NOT E X I S T . 1 5 1 RETURN 1 5 2 END 1 5 3 C 1 5 4 C 1 5 5 S U B R O U T I N E D E L V E ( I V ) 1 5 6 C D E L E T E V E R T E X 15 7 I M P L I C I T I N T E G E R * 4 ( A - Z ) 1 5 8 COMMON P ( 4 0 0 ) , S ( 4 C C ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V U 2 8 ) , E P R 0 P ( 4 0 0 ) , V P R O P ( 1 2 8 ) 1 5 9 COMMON E D O ( 2 0 0 ) , E D I ( 2 C G ) , I D E L ( 4 0 0 ) ,NE ,NV 1 6 0 DATA N E G , O N E S / 1 0 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / 161 1 0 0 F O R M A T ! / / ' * , • V E R T E X * , 1 5 , 3 X , f T O EE D E L E T E D DOES NOT E X I S T * ) 1 6 2 C A L L V E R N A M ( I V , J V ) 1 6 3 I F ( J V . E Q . O ) GO TC 5 0 1 6 4 I F ( V ( J V ) . G E . N E G ) R E T U R N 1 6 5 MK=C 1 6 6 V ( J V ) = V ( J V ) + N E G 1 6 7 J = E D O ( J V ) 1 6 8 15 I F ( J . E Q . G ) G O TO 10 1 6 9 I F ( I D E L ( J ) . c Q . - 1 ) G 0 TO 10 1 7 0 I D E L ( J ) = 1 1 7 1 K = S L ( J ) 1 7 2 I F ( M K . E Q . l ) K = P L ( J ) 1 7 3 I F t K . E G . O G O TO 10 1 7 4 J = K 1 7 5 GO TO 15 1 7 6 10 I F I M K . E Q . D G O TO 2G 1 7 7 MK=1 1 7 8 J = ED I { J V ) 70. 1 7 9 GO TO 15 1 8 0 20 RETURN 181 50 W R I T E ! 6 , 1 G G > IV 1 8 2 R E T U R N 1 8 3 END 1 8 4 C 1 8 5 C 1 6 6 S U B R O U T I N E R E S T E D ( V R ,VS , M , E R R ) 1 8 7 C R E S T O R E EDGE 1 8 8 I M P L I C I T I N T E G E R * 4 ( A - Z ) 1 8 9 COMMON P ( 4 C 0 ) , S ! 4 C C ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) , E P R O P ( 4 C 0 ) , V P R O P ( 1 2 8 ) 1 9 0 COMMON E D O ( 2 G 0 ) , E D I ( 2 G G ) , I D E L ( 4 C G ) , N £ , N V 191 DATA N E G , O N E S / 1 G 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / 1 9 2 I = M 1 9 3 I F ( I . E Q . O ) GO TO 7 1 9 4 V 1 = P ! I ) 1 9 5 V2 = S ( I ) 1 9 6 GC TO 5 1 9 7 7 V1=VR 1 9 8 V2=VS 1 9 9 5 C A L L V E R N A M ( V I , J ) 2 G 0 I F ( J . E Q . O ) GO TO 4 0 2 0 1 I F ( V 1 J ) . G E . N E G ) GO TO 20 2 02 C A L L V E R N A M ( V 2 , J ) 2 G 3 I F ( J . E G . O ) GC TO 4 0 2 0 4 I F ( V ( J ) . G E . N E G ) GO TO 20 2 0 5 I F ( I . E Q . O ) GO TO 6 2G6 I D E L ( I ) = 0 2 0 7 40 ERR = 0 2 0 8 RETURN 2 0 9 6 DC 3 0 1=1 ,NE 2 1 0 I F ( P ( I ) . N E . V 1 ) GC TO 30 2 1 1 I F { S 1 1 J . N E . V 2 ) GO TC 30 2 1 2 I C E L ( I ) = Q 2 1 3 GC TO 4 0 2 1 4 30 C C N T I N U E 2 1 5 DO 5 0 1 = 1 ,NE 2 1 6 I F ( P ( I ) . N E . V 2 ) GC TO 5C 2 1 7 I F ( S ( I ) . N E . V I ) GC TO 5 0 2 1 8 ID E L ( I ) = C 2 1 9 GO TO 40 2 2 0 50 C C N T I N U E 2 2 1 ERR = 0 2 2 2 20 I F ( E R R . E Q . 1 G 0 0 ) R E T U R N 2 2 3 E R R = L A N D ( V ( J ) t O N E S ) 2 2 4 W R I T E ( 6 , 1 0 0 ) V 1 , V 2 , E R R 2 2 5 10G F O R M A T ! / / ' ' , ' E D G E * 2 1 5 , 3 X , ' C A N N O T EE R E S T O R E D ' , 1 5 , 3 X , ' I S D E L E T E D ' 2 2 6 R E T U R N 2 2 7 END 2 2 8 C 2 2 9 C 2 3 0 S U B R O U T I N E R E S T V E ( I V ) 2 3 1 C R E S T O R E V E R T E X 2 3 2 I M P L I C I T I N T E G E R * 4 ( A - Z ) 2 3 3 COMMON P ( 4 C 0 ) , S ( 4 C 0 ) , S L ( 4 0 0 ) , P L ( 4 0 C ) , V ( 1 2 8) , E P R O P ( 4 0 0 ) , V P R O P ( 1 2 8 ) 2 3 4 COMMON E C O ( 2 0 0 ) , E D I ( 2 0 0 ) , I D E L I 4 0 0 ) , N E , N V 2 3 5 DATA N E G , O N E S / l C 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / 71 . 2 3 6 100 F O R M A T ! / / ' ' V E R T E X * , 1 5 , 3 X , * T 0 8E RESTORED DOES NOT E X I S T * ) 2 3 7 ERR=0 2 3 8 C A L L V E R N A M t I V , J V ) 2 3 9 I F ( J V . E Q . O ) GO TO 50 2 4 0 I F ( V ! J V ) . L E . N E G ) R E T U R N 2 4 1 MK = 0 2 4 2 V ( J V ) = L A N D ( V ( J V ) , O N E S ) 2 4 3 J = E D O ! J V ) 2 4 4 15 I F ( J . E Q . Q ) GC T C 20 2 4 5 I F { I D E L ( J K L T . G ) GO TO 13 2 4 6 V1=0 2 4 7 V2=0 2 4 8 C A L L R E S T E D ! V I , V 2 , J , E R R ) 2 4 9 13 I F ( M K . E Q . 1 ) G 0 TO 10 2 5 0 J = S L ( J ) 2 5 1 GO TO 15 2 5 2 10 J = P L ! J ) 2 5 3 GO TO 15 2 5 4 20 I F ! M K . E Q . l ) R E T U R N 2 5 5 J = E D I ( J V ) 2 5 6 MK= 1 2 5 7 GC TO 15 2 5 8 5G W R I T E ! 6 , 1 0 0 > IV 2 5 9 R E T U R N 2 6 0 END 2 6 1 C 2 6 2 C 2 6 3 S U B R O U T I N E R E S T A L 2 6 4 C R E S T O R E A L L D E L E T E D V E R T I C E S AND EDGES 2 6 5 I M P L I C I T I N T E G E R * 4 ( A - Z ) 2 6 6 COMMON P ( 4 C Q ) , S ( 4 C C ) , S L { 4 0 0 ) , P L 1 4 0 0 ) , V ( 1 2 8 ) , E P R O P ( 4 0 0 ) , V P R O P U 2 8 ) 2 6 7 COMMON E D O ( 2 0 0 ) , E D I ( 2 C C ) , I D E L ( 4 0 0 ) , N E , N V 2 6 8 E X T = 2 5 5 2 6 9 DO 10 1=1 ,NE 2 7 0 10 I D E L ( I ) = 0 2 7 1 DC 20 I = 1 , N V 2 7 2 I V = L A N D ( V ! I ) , E X T ) 2 7 3 V ( I ) = I V 2 7 4 20 C C N T I N U E 2 7 5 R E T U R N 2 7 6 END 2 7 7 C 2 7 8 C 2 7 9 S U B R O U T I N E N E X E D O ( I , K P C ) 2 8 0 c F I N D NEXT EDGE OUT OF V E R T E X 2 8 1 I M P L I C I T I N T E G E R # 4 ( A - Z ) 2 8 2 COMMON P ( 4 0 0 ) , S ( 4 0 0 ) , S L ( 4 0 0 ) , P L < 4 0 C ) , V i 1 2 8 ) , E P R O P I 4 0 0 ) , V P R O P U 2 8 ) 2 8 3 COMMON E D C ( 2 0 0 ) , E D I ( 2 0 0 ) , I D E L { 4 0 0 ) , N E »NV 2 8 4 J = E D O ! I ) 2 8 5 I F ( J . E O . O ) GO TO 10 2 8 6 15 I F ( K P D . N E . O ) J = S L ! K P C ) 2 8 7 10 KPD = 0 2 8 8 I F ( J . E Q . O ) R E T U R N 2 8 9 K F C = J 2 9 0 I F ( I D E L ( J ) . N E . O ) GO TO 15 2 9 1 R E T U R N 2 9 2 END 2 9 3 c 2 9 4 c 2 9 5 S U B R O U T I N E N E X E D I ( I , K P C ) 2 9 6 C F I N D NEXT EDGE INTO V E R T E X Id. 2 9 7 I M P L I C I T I N T E G E R S ( A - Z ) 2 9 8 COMMON P ( 4 0 0 ) , S ( 4 C C ) , S L { 4 0 0 ) , P L ( 4 0 0 ) , V U 2 8 ) , E P R O P { 4 0 0 ) , V P R O P ( 1 2 8 ) 2 9 9 COMMON E D O 1 2 C 0 ) » E O I ( 2GC) , I D E L ( 4 0 0 ) , N E , N V 3 C 0 J = E D I { I ) 3 0 1 I F ( J . E Q . O ) GO TO 10 3 G 2 15 I F ( K P D . N E . O ) J = P L { K P D ) 3 0 3 10 K P C = 0 3 0 4 I F U . E Q . O ) R E T U R N 3 C 5 KPD=J 3 0 6 I F { I D E L ( J ) . N E . 0 ) GO TO 15 3 0 7 RETURN 3 0 8 END 3 0 9 C 3 1 0 c 3 1 1 F U N C T I O N N E X E D G ( I V , K ) 3 1 2 C TO F I N E NEXT EDGE FROM V E R T E X IV FOR AN U N D I R E C T E D G R A P H . 3 1 3 I M P L I C I T I N T E G E R * 4 ( A - Z ) 3 1 4 COMMON P( 4 0 0 ) f S ( 4G0 ) , S L ( 4 0 0 ) , P L { 4 0 0 , V { 1 2 8 ) ,E P R O P ( 4 0 0 ) , V P R O P ( 1 2 8 ) 3 1 5 COMMON EDO 1 2 0 0 ) , E D I { 2 0 0 ) , I D E L { 4 0 0 ) , N E , N V 3 1 6 1G0 F O R M A T { / / » * , « V E R T E X INTO N E X T E D G E I S ZERO * ) 3 1 7 I F ( I V . E Q . O ) GO TO 20 3 1 8 I F U . E Q . O ) GO TO 10 3 1 9 I F ( P { K ) . N E . I V ) GO TO 15 3 2 0 10 C A L L N E X E 0 O U V , K ) 3 2 1 I F t K . E Q . O ) GO TO 15 3 2 2 17 NEXEDG=1 3 2 3 R E T U R N 3 2 4 15 C A L L N E X E D I ( I V , K ) 3 2 5 NEXEDG=0 3 2 6 I F ( K . N E . O ) GC TO 16 3 2 7 R E T U R N 3 2 8 16 N EXEDG= -1 3 2 9 RETURN 3 3 0 2 0 W R I T E ( 6 , 1 0 0 ) 3 3 1 R E T U R N 3 3 2 END 3 3 3 C 3 3 4 C 33 5 S U B R O U T I N E VERNAMK I V , J V ) 3 3 6 I M P L I C I T I N T E G E R * 4 ( A - Z ) 3 3 7 COMMON P { 4 0 0 ) , S ( 4 0 0 ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) , E P R O P ( 4 0 0 ) , V P R O P { 1 2 8 ) 3 3 8 COMMON EDO 1 2 0 0 ) , E D I ( 2 G G ) , I D E L ( 4 0 0 ) , N E , N V 3 3 9 DATA N E G , O N E S / 1 C 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / 3 4 0 E X T = 2 5 5 3 4 1 MAX=128 3 4 2 I F ( I V . L E . M A X ) GO TO 20 3 4 3 21 DO 10 1=1 ,MAX 3 4 4 M = L A N D I V ( I ) , O N E S ) 3 4 5 I F ( M . E Q . O ) GO TO 11 3 4 6 M = L A N D ( M , E X T ) 347 I F ( I V . N E . M ) GO TO 10 348 JV = I 34 9 R E T U R N 350 10 C O N T I N U E 351 11 I F ( J V . E Q . I C O O O ) GO TO 12 35 2 W R I T E ( 6 , 1 0 2 ) IV 3 5 3 12 JV = 0 3 5 4 R E T U R N 3 5 5 102 F O R M A T { / / » • V E R T E X C A L L E D 1 5 , 3 X , * HAS NOT B E E N I N S E R T E D * ) 3 5 6 20 I F ( I V . N E . L A N D f V ( I V ) , E X T ) ) GO TO 21 • <• 3 5 7 J V = I V / 3 5 8 RETURN 73 3 5 9 END END OF F I L E ' $ CONSENT ' ' S K I P TO T O P OF NEXT P A G E " $ C O P Y * S K I P 74. $ L I S T GS 1 C A P P E N D I X C 2 C 3 S U B R O U T I N E A P A T H ( I , E N D , L 1 S T , L , F A I L ) 4 I M P L I C I T IN T E G E R * 4 ( A - Z ) 5 COMMON P ( 4 0 0 ), S ( 4 C Q ) , S L ( 4 0 0 ) , P L ( 4 O 0 ) , V U 2 8) , E D ( 4 0 0 ) , V P R 0 P ( 1 2 8 ) 6 COMMON E D 0 ( 2 G 0 ) , E C I ( 2 0 0 ) , I D E L ( 4 0 0 ) , N E , N V 7 D I M E N S I O N L I S T ( I C O ) 8 DATA N E G , O N E S / 1 0 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / 9 DATA G I S , G I S l / 2 5 6 , 2 5 5 / 1 0 C I=THE I N I T I A L V E R T E X 11 C END=THE T E R M I N A L V E R T E X 12 C L I S T = S T O R I N G V E R T I C E S I N THE P A T H 13 C L= THE L E N G T H OF THE L I S T 14 C F A I L = 1 I F NO PATH C A N BE F C U N D , O T H E R W I S E 0 15 DO 100 T = 1 » N E 16 1 00 E C ( T ) = I 17 L = 0 18 F A I L = 1 19 C A L L V E R N A M l I , K K ) 2 0 I F ( K K . E Q . O ) R E T U R N 21 I F ( V ( K K ) . G T . N E G ) GO TO 5 0 0 22 140 C O N T I N U E 2 3 I F ( V ( K K ) . G T . G I S ) GO TO 150 24 V ( K K ) = G I S + V ( K K ) 25 15G L=L+1 2 6 L I S T ( L ) = V ( K K ) - G I S 2 7 K = L I S T ( L ) 28 2 0 0 J = 0 29 22G C A L L N E X E D O < K , J ) 3 0 I F ( J . E Q . G ) GO TO 550 31 I F ( I DEL ( J ) .N E .0 ) GO TO 2.20 32 I F ( E D ( J ) . N E . 1 ) GC TO 2 2 0 3 3 E D ( J ) = E D ( J ) + l 3 4 I I = S ( J ) 35 C A L L V E R N A M l I I , K K ) 3 6 I F ( K K . E Q . G ) GO TO 2 2 0 3 7 I F ( K K . E Q . E N D ) GO TO 6CC 3 8 C A L L DEL E C ( K K , K , 0 ) 3 9 GC TO 140 4 0 5 0 0 C O N T I N U E 41 C V E R T E X I HAS BEEN D E L E T E D 4 2 R E T U R N 4 3 55C C O N T I N U E 4 4 C THERE IS NO P A T H BETWEEN V E R T I C E S I AND END 4 5 RETURN 4 6 6 0 0 F A I L = 0 4 7 L=L+1 4 8 L I S T ( L ) = L A N 0 ( V ( K K ) , G I S 1 ) 4 9 C C L E A R A L L F L A G S 5 0 DO 7 0 0 T = 1 , N V 51 7CC V (T ) = LAND ( V ( T ) »G I S1 ) 52 DO 8 0 0 T = 1 , N E 5 3 8 0 0 E C ( T ) = 0 54 R E T U R N r 55 END 5 6 C 57 C 58 S U B R O U T I N E P A T H ( I , N C D E , N G , A N S , I X ) 7 5 . 59 I M P L I C I T I N T E G E R * 4 { A - Z ) 6 0 COMMON P ( 4 0 0 ) , S ( 4 0 0 ) , S L ( 4 0 0 ) , P L ( 4 0 0 } , V ( 1 2 8 ) , £ D ( 4 0 0 ) , V P R 0 P ( 1 2 € ) 6 1 COMMON E D O C 2 0 0 ) t E D I ( 2 0 0 ) , I D E L ( 4 0 0 ) , N E ,NV 6 2 D I M E N S I O N N O D E ( 4 C 0 ) , A N S ( 1 0 0 ) 6 3 DATA N E G , O N E S / 1 0 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / 64 DATA G I S , G I S l / 2 5 6 , 2 5 5 / 6 5 C I = G I V E N V E R T E X 6 6 C STORE A V E R T E X WHENEVER IT IS T E S T E D 6 7 C NO=NO. OF V E R T I C E S IN ARRAY NODE 68 C ED = S TORE A L L E D G E S I N ARRAY ED WHICH ARE W K I T E I = 1 ) TO S T A R T W ITH 6 9 C ANS= ALL. THE D I F F E R E N T V E R T I C E S ARE STORED I N A R R A Y ANS ALONG P A T H 7 0 C I X=NO. OF E L E M E N T S I N ANS 71 I X = I X + 1 7 2 NQ=1 7 3 F F I X = I X 7 4 C A L L V E R N A M ( I, KK ) 7 5 I F ( K K . E Q . O ) R E T U R N 76 C STORE ANY T IME A V E R T E X I S R E A C H E D 7 7 F I XNO=NO 78 K = V ( K K ) 7 9 N 0 D E ( N O ) = K 8 0 NC=N0+1 81 NEXNO=NO 82 C P A I N T V E R T E X K R E D ( 1 * G I S ) I F IT IS G R E E N ( V E R T E X I T S E L F ) IN ARRAY V 83 I F ( V ( K K J . G T . G I S ) GO TO 110 8 4 1 0 0 V ( K K ) = G I S + V ( K K ) 85 1 10 A N S ( I X ) = V { K K ) ~ G I S 86 I X = I X +1 87 K = L A N D ( V ( K K ) , G I S 1 ) £ 8 F I X K = K 89 F I XNO=NO 9 0 2 0 0 J =0 91 2 2 0 C A L L N E X E D O ( K , J ) 92 I F U . E Q . O ) GO TO 3 6 0 9 3 C F I N D WHITE EDGE 9 4 I F ( I D E L ( J ) . N E . 0 ) GO TO 220 95 V1 = S U ) 96 I F ( V ( V l ) . G T . N E G ) GO TO 3 9 0 9 7 3 0 0 I F ( E D ( J ) . N E . 1 ) GC TO 2 2 0 98 C FOLLOW THE WHITE E D G E , C O L O U R G R A Y ( = 2 ) AND D E L E T E THE O P P O S I T E S I D E 99 E D U ) = E D ( J ) + 1 1 0 0 I = S U ) 101 C A L L V ERNAM( I , KK ) 102 I F ( K K . E Q . O ) GO TC 2 2 0 1 0 3 TE MP = V ( K K ) 1 0 4 I F ( T E M P . G T . N E G ) GO TO 2 2 0 1 0 5 I F ( T E M P . G T . G I S ) TEMP=V (KK J - G I S 1C6 K=TEMP 1 0 7 C A L L D E L E D ! K , F I X K , 0 ) 1 0 8 F I X K = K 1 0 9 N C D E ( N O ) = K 1 1 0 N0=N0+1 1 1 1 NEXNO=NO 112 C WHAT CCLOR V E R T E X ? 1 13 I F ( V ( K K ) . £ Q . K ) GO TC 1 0 0 1 1 4 GO TO 2 2 0 1 1 5 C I F THE V E R T E X COLOUR IS R E C , TRY FOR N E X T WH ITE E D G E , I F NOT 1 1 6 C TURN AROUND AND R E T U R N BY SAME EDGE 1 1 7 3 6 0 N 0 = N 0 - 1 1 1 8 I F f N O . L E . O . A N D . F F I X . L T . I X ) GO TO 4 C 0 76. 1 1 9 I F ( N O . L E . O ) R E T U R N 1 2 0 K=NODE(NO) 121 F IXNO=NO 1 2 2 GC TO 2 2 0 1 23 390 C A L L D E L E D ( 0 , 0 , J ) 1 2 4 GO TO 22C 1 2 5 C T E R M I N A T I O N S Y M 8 0 L E OF ANY PATH I N ANS I S 9 9 9 9 126 4 0 0 ANS ( I X ) = 9 9 9 9 1 2 7 R E T U R N 1 2 8 END 1 2 9 C 1 3 0 C 131 S U B R O U T I N E A L P A T H { V A L , N O D E , N 0 , A N S , I X ) 1 3 2 I M P L I C I T I N T E G E R * 4 ( A - Z ) 1 3 3 COMMON P ( 4 0 0 ) , S ( 4 0 0 ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) , E D ( 4 0 0 ) , V P R O P ( 1 2 8) 1 3 4 COMMON E D 0 ( 2 0 0 ) , E D I ( 2 0 0 ) , I D E L ( 4 0 0 ) , N E , N V 1 3 5 D I M E N S I O N N O D E ( 4 0 0 ) , A N S I 1 0 0 ) 1 3 6 DATA N E G , G N E S / 1 0 7 3 7 4 1 8 2 4 , 1 0 7 3 7 4 1 8 2 3 / 1 3 7 DATA G I S , G I S l / 2 5 6 , 2 5 5 / 1 3 8 C V A L = N O . OF PATHS I N ARRAY ANS 1 3 9 C A L L V E R T I C E S ARE G R E E N ( = 1 ) TO START WITH 1 4 0 C I . E . , THE NAME OF E A C H V E R T E X IS IN A R R A Y V 141 C A L L EDGES ARE W H I T E ( = 1 ) TO START WITH 142 DO 110 K = 1 , N E 1 4 3 1 1 0 E D ( K ) = 1 1 4 4 VAL=0 1 4 5 I X=0 1 4 6 DC 2 0 0 J = 1 , N V 1 4 7 KPD=0 1 4 8 I = V ( J ) 1 4 9 I F ( V P R O P ( J ) . E Q . - l ) GO TO 2 0 0 1 5 0 I F ( I . G E . N E G ) GO TO 2 8 0 1 5 1 I F ( I . G T . G I S ) GO TO 2 0 0 1 5 2 2 1 0 C A L L N E X E D O ( I , K P D ) 1 5 3 I F ( K P D . E Q . O ) GO TO 2 5 0 1 5 4 I F ( I D E L ( K P D ) • N E • C ) GO TO 2 1 0 1 5 5 V 1 = S ( K P D ) 1 5 6 I F ( V ( V 1 ) . G T . N E G ) GO TO 2 7 0 1 5 7 F I X = I X + 1 1 5 8 C A L L P A T H ( I , N O D E , N 0 , A N S , I X ) 1 5 9 I F ( F I X . L E . I X ) V A L = V A L + 1 1 6 0 GC TO 2 0 0 161 2 5 0 V P R 0 P ( J ) = 2 1 6 2 C V E R T E X J I S OF T Y P E 2 1 6 3 GC TO 200 1 6 4 2 7 0 C A L L D E L E D ( 0 , 0 , K P D ) 1 6 5 GO TO 2 1 0 1 6 6 2 8 0 V P R O P ( J ) = Q 1 6 7 2 0 0 C C N T I N U E 1 6 8 I F ( V A L . G T . O ) GO TO 4 0 0 1 6 9 C THERE I S NO PATH I N T H I S PART OF GRAPH 1 7 0 4 0 0 C O N T I N U E 171 C C L E A R ARRAY ED B E F O R E RETURN 1 7 2 DO 4 1 0 J = l » N E 1 7 3 4 1 0 E D ( J ) = 0 1 7 4 RETURN 1 7 5 END 1 7 6 C 1 7 7 C 7 7 1 7 8 S U B R O U T I N E PA I N T { L 1 S T , L , S P P , P P , S I, I N , I ) ' ' * 1 7 9 C P A I N T THE V E R T I C E S ON C BY SMALL PR IME N O S . , I F THE V E R T I C E S ARE 1 8 0 C ON ARRAY IN THEN P A I N T TWICE 1 8 1 C I = THE LAST INDEX OF ARRAY I N , L 1 = 1-1 1 8 2 C S I = S T A R T I N G INDEX OF ARRAY IN 1 8 3 I M P L I C I T I N T E G E R * 4 ( A - Z ) 1 8 4 COMMON P ( 4 0 0 ) , S ( 4 0 0 ) , S L ( 4 C Q ) , P L ( 4 0 C ) , V U 2 8 ) , £ P R C P < 4 0 0 ) , V P R 0 P U 2 8 ) 1 8 5 COMMON E D C { 2 Q 0 ) , E D I ( 2 0 0 ) , I D E L ( 4 0 0 ) , N E , N V 1 8 6 D I M E N S I O N I N ( 1 0 0 ) , L I S T ( 1 0 0 ) , P R I M E ( 2 0 ) 1 8 7 DATA P R I M E / 2 , 3 , 5 , 7 , 1 1 , 1 3 , 1 7 , 1 9 , 2 3 , 2 9 , 1 8 8 $ 3 1 , 3 7 , 4 1 , 4 3 , 4 7 , 5 3 , 5 9 , 6 1 , 6 7 , 7 1 / 1 6 9 DATA G I S , G I S l / 2 5 6 , 2 5 5 / 1 9 0 DATA C I R C , C I R C 1 / 1 6 7 7 7 2 1 6 , 1 6 7 7 7 2 1 5 / 1 9 1 P P = S P P 1 9 2 X I = SI 1 9 3 I F ( I N ( S I ) . L T . C I R C ) X I = 5 1 + 1 1 9 4 L L = L - 1 195 L I = I - 1 1 9 6 KK=X I 1 9 7 F L A G = 0 1 9 8 DC 3 3 0 K = 1 , L L 1 9 9 Z = I N ( K K ) / C I R C 2 0 0 I F ( K . E Q . Z ) GO TO 3 4 0 2 0 1 GO TO 330 2 0 2 3 4 0 F L AG= F L A G + 1 2 0 3 I F ( F L A G . G T . l ) GO TO 3 5 5 2 0 4 FK=K 2 0 5 F I X K = K 2 C 6 3 6 0 KK=KK+1 2 0 7 I F ( K K . G T . L I ) GO TO 3 8 0 2 0 8 GO TO 330 2 0 9 3 5 5 I F ( F L A G . G T . 2 ) GO TO 3 5 0 2 1 0 DO 3 7 0 K 1 = F I X K , K 2 1 1 L I S T ( K 1 ) = P R I M E ( P P ) * G I S + L I S T ( K 1 ) 2 1 2 3 7 0 C C N T I N U E 2 1 3 PP=PP+1 2 1 4 F I X K = K 2 1 5 GO TO 36G 2 1 6 3 5 0 C C N T I N U E 2 1 7 T E M P = L A N D ( L 1 S T ( F I X K ) , G I S 1 ) 2 1 8 L I S T ( F I X K ) = ( L I S T ( F I X K ) / G I S ) * P R I M E { P P ) * G I S + T E M P 2 1 9 K 2 = F I X K + 1 2 2 0 DO 3 7 5 K 1 = K 2 , K 2 2 1 L I S T ( K 1 ) = P R I M E ( P P ) * G I S + L I S T ( K l ) 2 2 2 3 7 5 C O N T I N U E 2 2 3 PP=PP+1 2 2 4 F I X K = K 2 2 5 GO TO 3 6 0 2 2 6 2 3 0 C O N T I N U E 2 2 7 GC TO 4 0 0 2 2 8 3 8 0 T E M P = L A N D ( L I S T ( K ) , G I S 1 ) 22 9 L I S T ( K ) = ( L I S T ( K ) / G I S ) * P R I M E ( P P ) * G I S + TEMP 2 3 0 I F ( K . E Q . L L ) GO TO 3 8 6 2 3 1 K2=K+1 2 3 2 DC 3 9 0 K 1 = K 2 , L L 2 3 3 L I S T ( K 1 ) = P R I M E ( P P ) * G I S + L I S K K l ) 2 3 4 3 9 0 C C N T I N U E 2 3 5 3 8 6 I F ( F K . L E . l ) GO TC 3 9 9 2 3 6 F K K = F K - 1 2 3 7 DC 3 8 7 K 1 = 1 , F K K 2 3 8 L I S T ( K 1 ) = P R I M E { P P ) * G I S + L I S T ( K 1 ) 78. 2 3 9 3 8 7 C O N T I N U E 2 4 0 3 9 9 T E M P = L A N D ( L I S T ( F K ) » G I S 1 ) 2 4 1 L I S T CFK ) = ( L I S T ( F K ) / G I S ) * P R I M E ( P P ) * G I S + T E M P 2 4 2 4 0 0 R E T U R N 2 4 3 END 2 4 4 C 2 4 5 C 2 4 6 S U B R O U T I N E R E P A N T ( L I S T , L , S P P t P P * S I , I N , I ) 2 4 7 C P A I N T THE C I R C U I T A G A I N BY U S I N G ARRAY I N ( S I ) TO I N C I ) 2 4 8 I M P L I C I T I N T E G E R * 4 ( A - Z ) 2 4 9 COMMON P ( 4 G 0 ) , S ( 4 C G ) , S L ( 4 0 0 ) t P L ( 4 0 0 ) , V { 1 2 8 ) » E P R O P ( 4 0 0 ) , V P R O P ( 1 2 8 ) 2 5 0 COMMON EDOC 2 0 0 ) , E D I ( 2 G C ) , I D E L ( 4 0 0 ) , N E , N V 2 5 1 D I M E N S I O N I N < 1 0 0 ) , L I S T ( I C O ) , P R I M E ( 2 0 ) 2 5 2 DATA P R I M E / 2 , 3 , 5 , 7 , 1 1 , 1 3 , 1 7 , 1 9 , 2 3 , 2 9 , 2 5 3 $ 3 1 , 3 7 , 4 1 , 4 3 , 4 7 , 5 3 , 5 9 , 6 1 , 6 7 , 7 1 / 2 5 4 OATA G I S , G I S l / 2 5 6 , 2 5 5 / 2 5 5 DATA C I R C , C I R C l / 1 6 7 7 7 2 1 6 , 1 6 7 7 7 2 1 5 / 2 5 6 P P = S P P 2 5 7 X I = S I 2 5 8 I F U N C S D . L T . C I R C ) X I = S I + 1 2 5 9 L L = L - 1 2 6 0 L I = I - 1 2 6 1 K K = X I 2 6 2 X = I N ( K K ) / C I R C 2 6 3 3 4 0 F I X I = X 2 6 4 N I =X+1 2 6 5 C 2 6 6 C I F F I X I = L L , START FROM T H E F I R S T V E R T E X IN A R R A Y L I S T 2 6 7 I F ( F I X I . E Q . L L ) R E T U R N 2 6 8 C O L 1 = L 1 S T ( F I X I ) / G I S 2 6 9 C C L 2 = L I S T ( N D / G I S 2 7 0 F 1 2 = H C F ( C 0 L 1 , C 0 L 2 ) 2 7 1 C Q l = l OR > 1 2 7 2 Q 1 = C 0 L 1 / F 1 2 2 7 3 I F C C 1 . E Q . 1 ) GO TC 5 0 0 2 7 4 C 2 7 5 C C A S E l : L I S T ( F I X I ) / ( G I S * F 1 2 ) > 1 2 7 6 C R E P A I N T NEXT I N T E R S E C T I O N BY P R I M E ( P P ) , E R A S E F 1 2 FOR THE F O L L O W I N G 2 7 7 C V E R T I C E S T I L L IT R E A C H E S L I S T ( ? ) / ( G I S * F 1 2 ) > 1 2 7 8 KK=KK+1 2 7 9 I F C K K . G T . L D R E T U R N 2 8 0 Y = I N ( K K ) / C I R C 281 I F ( K K . E Q . L I ) GO TO 3 7 0 282 3 4 5 KK=KK+1 283 I F ( K K . G T . L I ) R E T U R N 284 Z = I N ( K K ) / C I R C 285 C 2ND AND 3RD ARE NOT THE L A S T ONE I N A R R A Y I N 286 T E M P Y = L A N D ( L 1 S T ( Y ) , G I S 1) 287 C C L Y = L I S T ( Y ) / G I S 2 88 L I S T ( Y ) = C O L Y * P R I M E ( P P ) * G I S + T E M P Y :»89 K1 = Y+1 i ?90 I F ( K K . E Q . L I ) GO TO 3 6 5 291 DO 3 5 0 K = K 1 , Z !?92 T E M P K = L A N D ( L I S T ( K ) , G I S 1 ) 2 9 3 C C L K = L I S T ( K ) / G I S 2 9 4 Q K = C 0 L K / F 1 2 2 9 5 L I S T ( K ) = Q K * G I S * P R I M E ( P P ) + T E M P K 2 9 6 3 5 0 C C N T I N U E 2 9 7 Y=Z 2 9 8 PP=PP+1 79. 2 9 9 GC TO 3 4 5 3 0 0 3 6 5 Y = Z 3 0 1 C 2ND V E R T E X I S THE LAST C NE IN ARRAY IN 3 0 2 370 C O L Y = L I S T I Y ) / G I S 3 0 3 Q Y = C 0 L Y / F 1 2 3 0 4 I F ( Q Y . E O . l ) GO TC 3 9 0 3 0 5 C L I S K Y ) I S THE L A S T ONE AND I S OF M U L T I P L E COLOURS 3 0 6 D I F F = I - X I 3 0 7 C I F THE BR IDGE FAS ONLY TWO ATTACHMENT V E R T I C E S AND BOTH HAVE 3 0 8 C M U L T I P L E COLOURS THAN R E T U R N 3 0 9 I F ( D I F F . E Q . 2 ) R E T U R N 3 1 0 T E M P Y = L A N D ( L I S T ( Y ) , G I S 1 ) 3 1 1 L I S T ( Y ) = C Y * P R I M E ( P P ) * G I S + T E M P Y 3 1 2 GO TO 60G 3 1 3 3 9 0 T E M P Y = L A N D ( L I S T ( Y ) , G I S 1 ) 3 1 4 L I S T ( Y ) = P R I M E ( P P ) * P R I M E ( P P + 1 ) * G I S + T E M P Y 3 1 5 P P = P P + 1 3 1 6 I F ( Y . E Q . L L ) GO TO 4 3 0 3 1 7 YY=Y+1 il8 4 10 DO 4 2 0 K = YY» L L 3 1 9 C O L K = L I S T ( K ) / G I S 3 2 0 Q K = C 0 L K / F 1 2 3 2 1 I F ( O K . G T . l ) GO TC 4 4 0 3 2 2 TE M P K = L A N D { L I S T ( K ) » G I S 1 ) 3 2 3 L I S T ( K ) = Q K * P R I M E ( P P ) * G I S + T E M P K 3 2 4 4 2 0 C C N T I N U E 3 2 5 4 3 0 YY=1 3 2 6 GO TO 4 1 0 3 2 7 4 4 0 T E M P K = L A N D ( L 1 S T ( K ) , G I S 1 ) 3 2 8 L I S T { K ) = C K * P R I M E ( P P ) * G I S + T E M P K 3 2 9 GO TO 6 0 0 3 3 0 C 3 3 1 C C A S E 2 : L 1 S T ( F IS I ) / ( G I S * F 1 2 ) = 1 3 3 2 C R E P A I N T L I S T ( F I X I ) BY P R I M E ( P P ) AND E R R A S E F 1 2 FOR THE F O L L O W I N G 3 3 3 C V E R T I C E S T I L L IT R E A C H E S L I S T ( ? ) / ( G I S * F 1 2 ) > 1 3 3 4 5 0 0 C C N T I N U E 3 3 5 Y=X 3 3 6 GO TO 3 4 5 3 3 7 6 0 0 RETURN 3 3 8 END 3 3 9 C 3 4 0 C 3 4 1 S U B R O U T I N E E R A S E ( L I S T , L ) 3 4 2 C E R A S E THE P A I N T E D V E R T I C E S ON THE C I R C U I T 3 4 3 I M P L I C I T I NT E G E R * 4 ( A - Z ) 3 4 4 COMMON P ( 4 G 0 ) , S ( 4 C 0 ) , S L ( 4 C 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) , E P R O P ( 4 0 0 ) , V P R O P 1 1 2 8 ) 3 4 5 COMMON E D O ( 2 0 0 ) , E D I ( 2 0 0 ) , I D E L ( 4 0 0 ) , N E , N V 3 4 6 D I M E N S I O N L I S T ( 1 0 0 ) 3 4 7 DATA G I S , G I S 1 / 2 5 6 , 2 5 5 / 3 4 8 L L = L - 1 3 4 9 DC 2 0 0 K = l t L L 3 5 0 L I S T ( K ) = L A N D ( L I S T ( K ) , G I S 1 ) 3 5 1 2 0 0 C O N T I N U E 3 5 2 RETURN 3 5 3 END 3 5 4 C 3 5 5 C 3 5 6 F U N C T I O N H C F ( A » 8 ) 3 5 7 C TO F I N D H C F OF A AND B 8 0 3 5 8 I M P L I C I T IN T E G £ R * 4 ( A - Z ) 3 5 9 COMMON P ( 4 G 0 ) , S ( 4 C C ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) , E P R O P ( 4 0 O ) , V P R O P ( 1 2 8 ) 3 6 0 COMMON E D O ( 2 C 0 ) , E D I ( 2 0 0 ) , I D E L < 4 0 0 ) , N E , N V 3 6 1 Y=A 3 6 2 Y1=B 3 6 3 1 5 0 T E M P = M 0 D ( Y , Y 1 ) 3 6 4 I F ( T E M P . E G . 0 ) GO TO 200 3 6 5 I F ( T E M P . E Q . l ) GO TO 3G0 3 6 6 Y=Y1 3 6 7 Y1=TEMP 3 6 8 GO TO 15C 3 6 9 2 0 0 HCF=Y1 3 7 0 R E T U R N 3 7 1 3 0 0 HCF=1 3 7 2 RETURN 3 7 3 END 3 7 4 C 3 75 C 3 7 6 S U B R O U T I N E S A M E ( I N , I ) 3 7 7 C E L I M I N A T E THE SAME E L E M E N T S IN ARRAY I N 3 7 8 I M P L I C I T INT E G E R * 4 { A - Z ) 3 7 9 COMMON P ( 4 C 0 > , S ( 4 C G ) , S L { 4 0 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) , E P R O P ( 4 0 0 ) , V P R O P 1 1 2 8 ) 3 8 0 COMMON E D O ( 2 0 0 ) , E D I ( 2 0 C ) , I D E L ( 4 0 0 ) , NE ,NV 3 8 1 D I M E N S I O N IN ( 1 0 0 ) 3 8 2 K I = 1 3 8 3 9 1 4 I F ( I N ( K I ) . N E . I N ( K I + D ) GO TO 9 1 6 3 8 4 9 1 7 1=1 -1 3 8 5 DC 915 K K I = K I , I 3 8 6 9 1 5 I N I K K I ) = I N ( K K I + 1 ) 3 87 I N ( I + 1 ) = 0 3 8 8 9 1 6 C C N T I N U E 3 8 9 I F ( I N ( K I ) . £ Q . I N ( K I + 1 ) ) GO TO 9 1 7 3 9 0 K I = K I + 1 3 9 1 I F ( K I . L E . I ) CO TC 9 1 4 3 9 2 R E T U R N 3 9 3 END 3 9 4 C 3 9 5 C 3 9 6 S U B R O U T I N E O R D E R ! I N , I ) 3 9 7 C R E A R R A N G E THE ORDER OF ARRY IN I N THE S E N S E OF C B E I N G O B T A I N E D 3 9 8 I M P L I C I T INT E G E R * 4 ( A - Z ) 3 9 9 COMMON P ( 4 G 0 ) , S ( 4 C C ) , S L ( 4 0 0 ) , P L ( 4 0 0 ) , V ( 1 2 8 ) , E P R G P ( 4 0 0 ) , V P R O P ( 1 2 8 ) 4 0 0 COMMON E D O ( 2 G 0 ) » E D I ( 2 G C ) , I D E L ( 4 0 0 ) » N E » N V 401 D I M E N S I O N I N ( 1 0 0 ) 4 G 2 DATA C I R C , C I R C 1 / 1 6 7 7 7 2 1 6 , 1 6 7 7 7 2 1 5 / 4 0 3 ST=1 4 0 4 K K = I - 2 4 0 5 I F ( K K . L E . O ) R E T U R N 4 C 6 9 1 9 DO 9 1 8 K = S T , K K 4 0 7 X = I N ( K ) / C I R C 4 0 8 Y = I N ( K + 1 ) / C I R C 4 0 9 I F ( X . L T . Y ) C-C TO 9 1 8 4 1 C S W A P = I N ( K + 1 ) 4 1 1 I N ( K + 1) = I N ( K ) 4 1 2 INCK)=SWAP 4 1 3 9 1 8 C O N T I N U E 4 1 4 K K = K K - 1 4 1 5 I F ( K K . G T . l ) GO TC 9 1 9 4 1 6 R E T U R N 4 1 7 END 4 1 8 C 81 . 4 1 9 C 4 2 0 S U B R O U T I N E A L T N A T ( L I S T , L , S I , I N , I , S T E S T , T E S T , T E , S O , O U T , O T , N O B I N , 4 2 1 $ NOBOUT) 4 2 2 C I=THE LAST INDEX OF ARRAY I N , I T = I - 1 4 2 3 C SI = S T A R T I N G INDEX OF ARRAY IN 4 2 4 C STE ST= S T A R T I N G I N D E X OF ARRAY TEST 4 2 5 C TE = THE L A S T INDEX OF ARRAY T E S T , T E E = T E - I 4 2 6 C S0 = ( S T A R T I N G INDEX - 1 ) OF ARRAY OUT 4 2 7 C 0T = THE L A S T I N D E X OF ARRAY OUT 4 2 8 C TO CHECK I F T E S T A L T E R N A T E S WITH B R I D G E S I N ARRAY I N , I F Y E S 4 2 9 C STORE IN ARRAY O U T , OTHERWISE IN ARRAY IN 4 3 0 I M P L I C I T I N T E G E R * 4 { A - Z ) 4 3 1 COMMON P ( 4 C C ) , S ( 4 C C ) , S L ( 4 C G ) , P L ( 4 0 C ) , V ( 1 2 8 ) , E P R O P ( 4 0 0 ) , V P R O P ( 1 2 8 ) 4 3 2 COMMON E D O ( 2 0 0 ) , E D I ( 2 0 0 ) , I D E L ( 4 0 0 ) , N E , N V 4 3 3 D I M E N S I O N I N ( 1 0 0 ) , C U T ( 1 0 0 ) , T E S T ( 1 0 0 ) , L 1 S T { 1 0 0 ) 4 3 4 DATA G I S , G I S l / 2 5 6 , 2 5 5 / 4 3 5 DATA C I R C C I R C 1 / 1 6 7 7 7 2 1 6 , 1 6 7 7 7 2 1 5 / 4 3 6 C 4 3 7 OT = SO 4 3 8 T E E = T E - 1 4 3 9 I F ( T E . L E . 2 ) R E T U R N 4 4 0 X T = S T E S T 4 4 1 I F ( T E S T ( S TE S T ) . L T . C I RC) X T = S T E S T + 1 4 4 2 C W=NO. ATTACHMENT V E R T I C E S ON C 4 4 3 W=TE-XT 4 4 4 C THE F I R S T ATTACHMENT V E R T E X 4 4 5 X = T E S T ( X T ) / C I R C 4 4 6 Y = L I S T ( X ) / G I S 4 4 7 C THE L A S T A L L A C H M E N T V E R T E X 4 4 8 L X = T E S T ( T E E ) / C I R C 4 4 9 L Y = L I S T ( L X ) / G I S 4 5 0 I F ( Y . E G . L Y . A N D . W . E G . 2 ) GO TO 9 7 5 4 5 1 H=HC F { Y , L Y ) 4 5 2 I F ( H . G T . 1 . A N D . W . E Q . 2 ) GO TO 9 7 5 4 5 3 I F I Y . E G . L Y . O R . H . G T . 1 ) GO TO 4 0 0 4 5 4 GO TO 9 8 5 4 5 5 4 0 0 NT= XT 4 5 6 4 0 1 NT=NT+1 4 5 7 I F ( N T . G E . T E E ) GO TO 4 1 0 45 8 X 1 = T E S T ( N T ) / C I R C 4 5 9 Y 1 = L I S T ( X 1 ) / G I S 4 6 0 I F ( Y . E Q . Y l ) GO TO 4 0 5 4 6 1 H 1 = H C F ( Y , Y 1 ) 4 6 2 I F ( H l . E Q . l ) GO TO 9 8 5 4 6 3 40 5 Y=Y1 4 6 4 GC TO 4 0 1 4 6 5 4 1 0 I F ( Y l . E Q . L Y ) GO TC 9 7 5 4 6 6 HL=HCF ( Y 1 , L Y ) 4 6 7 I F ( H L . G T . l ) GO TC 9 7 5 4 6 8 GO TO 9 8 5 4 6 9 C T H E S E TWO B R I D G E S DO NOT A L T E R N A T E 4 7 0 9 7 5 DC 9 7 0 NGT = S T E S T , T E -4 7 1 1 = 1 + 1 4 7 2 1 N ( I ) = T E S T ( N O T ) 4 7 3 9 7 0 C O N T I N U E 4 7 4 N C E I N = N O B I N + I 4 7 5 RETURN 4 7 6 C THESE TWO B R I D G E S A L T E R N A T E WITH EACH OTHER 4 7 7 98 5 C O N T I N U E 8 2 4 7 8 DC 9 8 0 Y E S = S T E S T , T E 4 7 9 0T=0T+1 4 8 0 O U T ( O T ) = T E S T ( Y E S ) 4 8 1 9 8 0 C C N T I N U E 4 8 2 N C B 0 U T = N C 8 O U T + I 4 8 3 R E T U R N 4 8 4 END 4 8 5 C 4 8 6 C 4 87 S U B R O U T I N E A L T E R ( B C , P R C P , L I S T , L , I N , I , O U T , O T , N O B I N , N O B O U T , * ) 4 8 8 C F I N C THE A L T E R N A T E B R I D G E S 4 8 9 ' C I = I N D E X FOR I N , I T = I - 1 4 9 0 C J = I N D E X FOR EPROP 4 9 1 C T E = I N D E X FOR T E S T , T £ E = T E - 1 4 9 2 C OT= INCEX FOR OUT 4 9 3 C NOB IN=NO. OF B R I D G E S IN ARRAY IN 4 9 4 C NOBOUT=NO. OF B R I D G E S I N ARRAY OUT 4 9 5 I M P L I C I T I N T E G E R S ! A - Z ) 4 96 CCMMON P { 4 0 0 ) , S ( 4 0 0 ) , S L ( 4 0 0 ) , P L ( 4 0 G ) , V { 1 2 8 ) , E P R O P ! 4 0 0 ) , V P R O P ( 1 2 8) 4 9 7 COMMON E D O { 2 G 0 ) , E D I ( 2 0 0 ) , I D E L ( 4 0 0 ) , N E , N V 4 9 8 D I M E N S I O N I N ( 1 G O ) , O U T l 1 0 0 ) , T E S T ( I O C ) , L I S T i l O C ) 4 9 9 D I M E N S I O N P R O P { 4 0 0 ) 5 C 0 DATA G I S , G I S l / 2 5 6 , 2 5 5 / 5 0 1 DATA C I R C , C I R C 1 / 1 6 7 7 7 2 1 6 , 1 6 7 7 7 2 1 5 / 5 0 2 C 5 0 3 DC 2 0 0 Z = l , 1 0 0 5 C 4 I N ! Z ) = 0 5 0 5 O U T ! Z ) = 0 5 C 6 T E S T ( Z ) = 0 5 0 7 2 0 0 C C N T I N U E 5 0 8 S0 = 0 5 0 9 I F ( B C . L E . C ) R E T U R N 1 5 1 0 11=1 5 1 1 GO TO 9 0 2 5 1 2 9 0 1 X 1 = I N ( 1 ) / G I S 5 1 3 C A L L D E L V E t X 1 ) 5 1 4 9 0 2 1=0 5 1 5 S I = I + 1 5 1 6 DO 9 0 0 J = I I , B C 5 1 7 1=1+1 5 1 8 I F ! P R O P ( J ) . LT . 0 ) GO TO 9 1 0 5 1 9 I N ( I ) = P R O P { J ) 5 2 0 9 0 0 C C N T I N U E 5 2 1 9 1 0 I M I ) = - 1 5 2 2 NCB IN=1 5 2 3 I F U . E Q . B C ) R E T U R N 1 5 2 4 F I X I = J 5 2 5 C R E A R R A N G E THE ORDER OF ARRY IN IN THE S E N S E WE O B T A I N C 5 2 6 C A L L O R D E R ! I N , 1 ) 5 2 7 C E L I M I N A T E THE SAME V E R T I C E S IN I N U ) 5 2 8 C A L L S A M E ! I N , I ) 5 2 9 SPP=1 5 3 0 NOBOUT=0 5 3 1 I I = F I X I + 1 5 3 2 C S E P A R A B L E B R I D G E S ARE IGNORED AND D E L E T E D 5 3 3 I F { I N ( 1 ) . L T . C I R C . A N D . I . E Q . 3 ) GO TO 9 0 1 5 3 4 C A L L P A I N T t L I S T , L , S P F , P P , S I , I N , I ) 5 3 5 C P A N T I = THE INDEX OF L A S T B R I D G E I N ARRAY I N HAD B E E N P A I N T E D 5 3 6 PANT I = I 53 7 99 0 C O N T I N U E 5 3 8 3 9 8 0 TE=1 83. 53 9 S T E S T = T E 5 4 0 DC 9 2 0 J = I I , B C 541 I F { P R O P ( J ) . L T . 0 ) GO TC 9 3 0 5 4 2 T EST(TE)=PROP (J ) 5 4 3 TE=T E + l 5 4 4 9 2 0 C C N T I N U E 5 4 5 9 3 0 I J = J+1 5 4 6 T E S T ( T E ) = - 1 5 4 7 C R E A R R A N G E THE ORDER CF ARRAY T E S T IN T H E S E N S E WE O B T A I N C 5 4 8 C A L L O R D E R l T E S T , T E ) 5 4 9 C E L I M I N A T E THE SAME V E R T I C E S IN TE S T ( T E ) 5 5 0 C A L L S A M E ( T E S T , T E ) 5 5 1 C S E P A R A B L E B R I D G E S ARE IGNORED AND D E L E T E D 5 5 2 I F ( T E S T ( 1 ) . L T . C I R C . A N D . T E . E Q . 3 ) GO TO 9 8 1 5 5 3 NCB=NOBOUT 5 5 4 S I =1 c 5 5 98 0 C A L L A L T N A T f L I S T , L , S I , 1 N , I , S T E S T , T E S T , T E , S O , O U T tOT , N O B I N , N O B C U T : 5 5 6 C S0= ( N E X T S T A R T I N G INDEX - 1) OF OUT 5 5 7 SC = CT 5 5 8 I F I I J . G T . B C ) GO TO 9 9 9 5 5 9 I F ( N O B . L T . N O B O U T ) GO TO 4 0 0 5 6 0 I F ( N 0 B I N . L T . 2 ) GC TO 4 0 0 5 6 1 S PP=PP+1 5 6 2 C NEXT B R I D G E IN ARRAY I N TO BE R E P A I N T E C ' F R O M I N ( S I ) TO I N I L A S T I ) 5 6 3 2 2 0 0 S I = P A N T I + 1 5 6 4 2 4 3 0 C A L L R E P A N T ( L I S T , L , S P P , P P , S I , I N , I ) 5 6 5 P A N T I = I 5 6 6 4 0 0 GO TO 2 9 8 1 5 6 7 9 8 1 X1 = T E S T ( 1 ) / G IS 5 6 8 C A L L D E L V E ( X l ) 5 6 9 2 9 8 1 I I = J + 1 5 7 0 I F I I J . G T . B C ) GO TC 9 9 9 5 7 1 DO 2 9 0 2 I S = 1 , T E 5 7 2 T E S T d S )=0 5 7 3 2 9 0 2 C O N T I N U E 5 74 GC TO 9 9 0 5 7 5 9 9 9 R E T U R N 5 7 6 END END OF F I L E ^COMMENT » ' S K I P TO TOP OF NEXT P A G E ' * $COPY * S K I P ( D £ N * ( r ) 2 N « ( D I M ( I OT * NW i E) OV 3« SS r + NOX = \IW vS 33N*T=r 002 OQ £S 2/3N=33N 2S *tf »0 V X i a i V M ADN3Dtf PQtf 3HI WaOd 01 D IS ODE 01 00 ( 0'3N * 9 V l d I ) d l OS Q Z 01 DO ( T*3Vi\ l ) d I 5* v ( SI '»=3N • *SI ' t=AN i ** .//JIVWaOd OTI 8v 3 M * A N ( 0 I l » 9 ) 3 i i a M Zv AN=N 9v 3M*AN (ZOT* n»E)QV3a S<? 087+N0>l=n vv 3 Z I S I = 3 Z I S ev 3ZISI*0V1=II (O0I'S)OV3ti Zh ( * 0) MD010S=13WI1 Iv .! 3 DM I IN 30 I 0*7 ******************.************ ** ** ** * * *** * * * * ** if if if.ii.if.1fif.iiiif.if. * * * * * * * * * * * 3 6 £ S l O l d 11V0 8£ 3nNIlM30 66 ZE •0=(P'>l)tf^ 9£ • o = ( r * x ) v S£ l 821* T = T 66 00 v£ 8 2 I M = >I 66 00 ££ *3oanos*=s I I N H O 2£ WQ8d 3SIMa3H10 *£ II Nil W0H3 Qtf3« 3dV VIVO 3H1 *0=9VldI 0 IE H3S0 3H1 A8 i3S 38 H I M 3ZIS1 ON? 9VTdI 0 OE ********;*:*********************************************************** 3 62 OOOI=NDX 82 Z="!OSN LZ 82I=1N31 92 821=X8N31 S2 82T=VN31 *?Z 3 = X*D 3AIDS 01 0 £2 •3nai*=9tfld 22 « (ZTIOT'XT UVWttOd 201 12 ( S I S Z*XIJ l V W b O J 191 02 (SlOT)lVWaOd 001 61 ( i S I I V d SN0IlVnS3 HV3NI1 30 NOIimOS « i//)lVWHOd 09 81 ( 9 ' E I d O I ' X U l V W U O d OS L\ (T*G1J8)lVW83d OZ 91 (SI9T)iVW«0d OT ST /6V T/1SN09 */ZS8I£3Z*9/IdOMl VIVQ hi ({I )AA * ( Z ' I ) 8 ) *(XX*8) 30N3"IVAIflD3 £T ( ( T)A * ( ? * T)Z)*(X'? ) 3 D N 3 1 V A I 0 5 3 ZI (82 I)AA *(821 } XX N0ISN3WI0 IT ( 8 Z 1 ) A M 821)X*(031)1S11 N0ISN3WI0 01 • < ( 8 Z T * 8 Z I ) t f f N0ISN3WI0 6 (OO^JEN 4 (0Dv)2N«(00»7}IN N01SN3WIQ 8 ( 9S2) W«3dl M 821*821) I* (2*821 ) Z M Z * 821)9* (8ZI*8ZT)V N0ISN3^I0 L Dtfld 1V0I931 9 ovid/onega/Nowwoo s VV »7*TV3y v A * X * i 3 G " l ' Z i 8 * V v*TV3y £ * D 2 Q XI0N3ddV 0 I ONUJLOld i s n $ •o=(r*>nv six 61 O i 03 < r *Q3 *>») J I • / I T N M = r M 30 6 £ 1 1 9 01 09 ZII SI 01 00 ( N ' 1 9 * > U 3 I I I I L 01 0 9 ( N * i V > i * Q M t f * l * i 9 * W l ) 3 I O i l T + X=>l 8 1 601 W n S - = ( X * » ) V 801 3ONI1NO0 £ 1 L0\ (r*>n v+wns=ans 9Di N M = r £1 30 SOI •o=wns L *?o\ O I ' M J V wns- i n d O N V wns Moy ONid o E O I 6 O i 09 ( ( W 1 ) I S I V 3 3 * > I ) 3 I 9 ZOI I = W 1 TOT I=>l ODI • 0 = { r * I ) t f QNtf • T = ( I * l ) t f N3H1 0 6 5 I S n N I X3i«3A 3N0 A N V 0 1 1VH03 SI MOH H i - 1 31 D 86 1 - 1 = 1 Lb 30NI1NQ9 D3"7 96 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 0 5 5 ( 1 M = M MMJ1SI1) ( 0 I 4 9 ) 3 i i a M ^6 (•SI iinDHID d31H3 3 H 1 » *. i / / ] l V H i l O d * £5 ( * * 9 ) 3 1 I H M 26 ( T i ^ M M j i s n i (0T*s)a*3« 16 1 <0I*S)aV3M Ob 30NI1M3D IT 5 3 S£ 01 39 8 8 EW=(TW*ZW)tftf 18 EW=(TW*2W)V 93 £'*!=( ZW* TW) Vtf 58 EW=(2W*TW)V *8 EW*ZW*IW (20I*9)31iyM £ 8 IT O i 03 ( 0 * 3 T £ W * y O # 0 , 3 T Z W 8 0 * 0 * 3 * * I W ) 3 I 2 8 EW«ZW*TW ( 0 0 T ' S ) Q ^ 3 a 1 8 30NI1N03 SE 0 8 ( / 4 . 3 « t f H d V « 9 N3AI9 3Hi$ 6 1 3 0 S 3 U I 3 U S V 1 3 3AI103dS3« «I3Hi ONtf S39G3 3H1 • * • »//)IVW«Q3 SET 8 1 (SEI*9)3iI«M I I 0 1 O i 0 9 ( 0 * 3 1 * N ) 3 1 9L 1M ( 0 T * S ) a ^ 3 « SZ. S39IIH3A 30 H3awn.M=.M 3 *?L anNIINOD ODE £L r * 3 N * i 31 ( i * r )*v= ( r * i>*v I V H I 3 I O N O ZL •SIN3S3«d3« HDIHM 3903 3H1 30 « A l l 3 I IS* 1 3 • 3H1 NO 9 M I ON! 3d3Q D I I SH38WnN 3 M i l S 0 d A . N V 39 NV9 *V X I * l i W 30 S3I«1N3 OW3Z -N0N 3H1 9 O i * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 9 6 9 OOV 01 09 89 ( 1 M = > I 1 ( M ) l S I l ) ( 0 I ' 9 ) 3 i i y M L9 (•/*9)3iIW1 99 ( l M = > i M > l ) l S n ) ( Z O T * l l . E ) a ? 3 « S? T6+r+N0M = I l V9 665 Oi 09 ( I * 3 T 1 ) 3 I £9 i czoi»n.e)av3u z? 06+7+N0>l=Il 19 3'nNI IN03 002 09 ( D £ M = ( ( P ) T M * ( D Z N ) V V 6 5 •<;g ( D £ M = ( ( D Z N * (DIN)tftf 85 ( r> £ N = < ( D I N * ( D Z M ) V IS (DEN=( ( D Z N * ( D I N ) V 95 1 1 6 GC TO 1 4 117 19 A ( K , J ) = 1 . 1 1 8 14 C O N T I N U E , 86. 1 1 9 LM=LM+1 1 2 0 GC TO 18 12.1 1 5 C O N T I N U E 122 I F ( I F L A G . N E . O ) GO TO 5 C 0 1 2 3 C 1 2 4 DC 12 K=1 ,N 1 2 5 DO 12 J = 1 , N S 0 L 1 2 6 B ( K , J ) = 0 . 1 2 7 12 C C N T I N U E 128 C THE OUTER C I R C U I T W I L L BE PUT IN THE F I R S T GUARDRANT OF X Y - P L A N E 1 2 9 C AS A ( L - 1 ) R E G U L A R P O L Y G O N 1 3 0 T I = T W O P I / F L O A T { L ) 1 31 DC 6 0 G K = 1 , L 132 T 2 = T 1 * F L 0 A T ( K ) 1 3 3 X X ( L I S T ( K ) ) = C 0 N S T * C Q S ( T 2 ) 1 3 4 X X ( L I S T ( K ) ) = X X ( L I S T ( K ) ) + C O N S T 1 3 5 Y Y ( L I S T ( K ) ) = C O N S T * S I N ( T 2 ) 136 YY (L 1ST(K ))=YY(LIST(K) )+CONST 1 3 7 6 0 0 C C N T I N U E 1 3 8 GO TO 6 1 0 1 3 9 C > > * * $ $ * s M * * * * * * * ^ 1 4 0 C THE OUTER C I R C U I T MAY BE A S S I G N E D BY T H E USER ANYWHERE HE W I S H E S . 1 4 1 C THE R E G I O N I S I S I Z E * I S I Z E CR S I Z E * S I Z E 1 4 2 5 0 0 C O N T I N U E 1 4 3 DC 5 5 0 K=1 ,N 1 4 4 R E A D ( 5 , 2 G ) ( B ( K , J ) , J = l , N S O L ) 1 4 5 W R I T E ( 6 , 5 C ) ( B ( K , J ) , J = 1 , N S 0 L ) 1 4 6 5 5 0 C O N T I N U E 1 4 7 6 1 0 C C N T I N U E 1 4 8 C A L L F S L E ( N , L E N A , A , N S C L , L E N B X , B , Z , I P E R M , L E N T , T , D E T , T E X P ) 1 4 9 I F ( D E T ) 2 5 , 3 0 , 2 5 1 5 0 2 5 C C N T I N U E 151 W R I T E ( 6 , 2 6 ) 1 52 26 F O R M A T ( / / » ' , * S G L U T I O N Z I S M 1 5 3 DC 27 K=1,N 1 5 4 W R I T E ( 6 , 5 0 ) ( Z ( K , J ) , J = l , N S O L ) 1 5 5 27 C O N T I N U E 1 5 6 C A L L S C A L E ( X , N , S I Z E , X M I N , D X , 1) 1 5 7 C A L L S C A L E ( Y , N , S I Z E , Y M I N , D Y , 1 ) 1 5 8 C A L L A X I S ( 0 . , G . , 6 H X AX I S , - 6 , S I Z E , 0 . , X M I N , D X ) 1 5 9 C A L L A XI S ( 0 . , 0 . , 6 H Y A X I S , 6 , S I Z E , 9 0 . , Y M I N » D X ) 1 6 0 DC 8 0 K = 1 , N 161 C A L L P L 0 T < X ( K ) , Y M < ) , + 3 ) 162 I F ( K . G E . N ) GO TO 81 1 6 3 J J = K + 1 164 DC 9 0 J = J J , N 1 6 5 I F ( A A ( K , J ) . E G . 0 . ) GO TC 9 0 1 6 6 C IF THERE I S AN EDGE BETWEEN ( X ( K ) , Y ( K ) ) AND ( X ( J ) , Y ( J ) ) , THEN DRAW 1 6 7 C A L I N E AND MOVE BACK TO ( X ( K ) , Y ( K ) ) WITH PEN UP 1 6 8 C A L L P L O T ( X ( J ) , Y ( J ) ,+2 ) 1 6 9 C A L L P L 0 T ( X ( K ) , Y ( K ) , + 3 ) 1 7 0 9 0 C C N T I N U E 1 7 1 8 0 C C N T I N U E 1 7 2 81 C C N T I N U E 1 7 3 C A L L P L O T t 1 2 . 0 , 0 . 0 , - 3 ) 1 7 4 8 0 0 C C N T I N U E 1 7 5 DC 7 0 0 K = 1 , N 176 DC 700 J = l ,N 177 AA(K,J)=C. 178 700 AIK,J)=0. 87. 179 IF(I FLAG.NE.0 ) GC TO 701 180 LI=KQN+499 181 READ(3'LI»1G2) II 182 GC- TO 702 183 701 . READ(5,100) II 184 702 CONTINUE 185 KCN=K0N+500 186 TIME2 = SCL0CK(TIME1 ) 187 WRITE(6,4999) TI ME2 188 4999 FORMAT!//' ',» THE EXECUTION TIME = « , F6.2, • SECONDS* ) 189 IF(II.LE.O) GO TC 70 190 GO TO 1 191 30 WRITE(6,60) 192 GC TO 800 193 999 CCNTINUE 194 WRITE(6,998) 195 998 FORMAT(//* *, * THE OUTER CIRCUIT CAN NOT BE FOUND, PLOT ROUTINES 196 SWILL NOT BE CALLEC * ) 197 GO TO 800 198 70 CONTINUE ••- 199 CALL PLOTND 200 STOP : 201 END END OF FILE $SIGNOFF 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051252/manifest

Comment

Related Items