GEA(ID:507/gea001)Graph Extended ALGOLS. Crespi-Reghizzi and R. Morpurgo 1969 Politecnico di Milano, Milan, Italy for Graph Extended ALGOL. Extension of ALGOL-60 for graph manipulation, on UNIVAC 1108. Structures: Related languages
References: Graphs are represented by linked lists. The language is syntactically defined as an extension to ALGOL 60, and it is translated into ALGOL by means of a syntax-driven compiler. Application areas for this language are operation research, network problems, control theory, traffic problems, etc. in [ACM] CACM 13(05) (May 1970). view details in Computers & Automation 21(6B), 30 Aug 1972 view details in [ACM] CACM 16(02) February 1973 view details The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one. There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages. The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM. Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) . It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers. The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA). As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found. It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel. We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work. Graz / Austria, May, 1973 in [ACM] CACM 16(02) February 1973 view details in [ACM] CACM 17(10) (Oct 1974) view details Introduction A graph can be used to represent many physical situations which involve discrete objects and relations between them. The objects are represented by the nodes of the graph and the relations between them are represented by the edges of the graph. We do not repeat here the terminology associated with graphs as this can be found in the many texts now available on the subject. Two such are Deo (1974) and Christofides (1975); these also provide excellent accounts of the diverse applications of graphs. The solution to a problem whose fundamental nature can be represented by a graph may often be obtained by manipulating the graph in a number of discrete steps according to some algorithm. We shall refer to such algorithms as graph algorithms. Example 3.1 implements an algorithm for finding the cliques of a graph using the package described in this paper. In particular the cliques of the graph of Fig. 1 are found (see Fig. 5). Attempting to implement graph algorithms on a computer raises a number of programming problems. These involve the efficient representation and manipulation of a wide variety of graphs of different types and complexity. It is desirable to have facilities which directly use the objects and operations natural to the subject and this has been the aim of the graph algorithmic applications package (GRAAP) described in this paper. The package is written in ALGOL 68-R for use on ICL 1900 series machines. It should be able to cater for most needs imme- diately but the existing facilities can be used as a basis from which to extend into the user's area of application. This potential extensibility of GRAAP makes it unlike any other package or language so far produced in the area of graph algorithms. The package, which includes structures for representing graphs and related objects as well as routines for handling them, is available as an ALGOL 68-R segmented album and so a user's program need only include those segments specifically required for the implementation of his algorithm. The object of this paper is to outline the package and its uses; full details are given in Garside and Pintelas (1978). We first sketch the background against which GRAAP has been developed. A large number of software aids for implementing graph algorithms already exist but they are all much more limited than GRAAP. Some of the more important of these are mentioned below. Standard algorithmic languages such as FORTRAN or ALGOL 60, with their restricted data structures, are unsuitable for implementing graph algorithms, while list processing languages provide more appropriate data structures but tend to hide ths graph-theoretic nature of the algorithm and lead to slow execution and large demands for storage (see Rheinbolt, Basili and Mesztenyi, 1972). Special purpose languages and software systems have been developed to free the programmer from representational problems and assist him with the manipulation of graph structures. It would be inefticient to design a new language and write a compiler for it because of the limited application of the language and the enormous amount of time required to produce the compiler. Consequently all graph-theoretic languages are embedded in some well known high level language. There are two main approaches. The first is to extend the host language by designing extra language constructs to take care of the graph statements and expressions. This requires a preprocessor which translates the graph statements into statements of the host language. Languages using this approach are GTPL of King (1970) which is based on FORTRAN 11, GEA of Crespi-Reghizzi and Morpurgo (1968) which is an ALGOL 60 extension with digraphs as a new data type, GASP at the University of Illinois (Chase, 1970) which is an extension of PL/I and GRASPE at the University of Texas (Friedman, 1968) which is an extension language for processing digraphs and has been embedded in SNOBOL4, SLIP-FORTRAN and LISP 1.5. For a full account of existing graph processing aids the reader is referred to Pintelas (1976). The second approach requires the host language to possess facilities which enable new data structures and operations to be defined. ALGOL 68 is such a language and we have used an implementation of this, ALGOL 68-R on ICL 1900 series computers, in producing GRAAP. As far as we know, no other package is available which uses a language with these kinds of facilities. Consequently GRAAP has much wider application than any of the above-mentioned extensions and has already been used to implement many existing graph algorithms and to develop new ones in various fields. Section 2 describes the GRAAP structures and some of the rroutines for handling them, while two examples of the use of the package are given in Section 3. In conclusion Section 4 contains observations based on the experience of using the package extensively. in The Computer Journal 23(3) 1980 view details |