GRAAP(ID:5972/gra002)GRaph Algorithmic Applications PackageGraph theoretic extensions to ALGOL 68 Related languages
References: 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 |