Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!unido!ztivax!corvara From: corvara@ztivax.UUCP (Dr Gerd Venzl) Newsgroups: comp.lang.functional Subject: Summary: functional programming of graph algorithms (long) Message-ID: <5495@ztivax.UUCP> Date: 11 Jun 91 14:07:46 GMT Reply-To: roessel@ztivax.siemens.com (Torsten Roessel) Organization: Siemens AG, Munich, W-Germany Lines: 341 Here is my summary of responses on functional programming of graph algorithms. To remind you, in article <5332@ztivax.UUCP> I wrote: > Some months ago somewhere in the literature I found a statement like > > "Functional programming is not well suited for algorithms of graph > theory as these usually make frequent use of side effects." > > When I tried to write down a purely functional formulation of some > manipulations on binary decision diagrams I found that indeed to be > quite a difficult and unnatural task. Are there really fundamental > reasons for these difficulties to arise or is my vision and understanding > of graph algorithms just too imperative? Are there any published attempts > to give functional formulations of graph algorithms? Any opinions from > netland? As some people wondered where I found the above statement: it's in the concluding remarks of the following German (I'm sorry, netters) book on automatic complexity analysis of functional programs: @book(Zimmermann90a, author = {W. Zimmermann}, title = {Automatische Komplexit\"atsanalyse funktionaler Programme}, publisher = {Springer}, year = {1990}, volume = {261}, series = {Informatik-Fachberichte}, address = {Berlin} ) Below you find the (partially commented) responses I received. Thanks to anyone who replied. More answers have been posted to the net by U.S. Reddy (reddy@reddy.cs.uiuc.edu, article ) and T.M. Breuel (tmb@ai.mit.edu, ). I do not repost these. While I received quite some hints and opinions there were (almost) no references given to related work. One might conclude that here we found a topic that is still worth publishing on. Torsten Roessel Siemens Corporate Research & Development Design Automation Department InterNet: roessel@ztivax.siemens.com ------------------------------------------------------------------------------ From: tmb@ai.mit.edu (Thomas M. Breuel) ------------------------------------------------------------------------------ Well, that statement was probably made by someone who didn't have much experience with functional programming. If you represent your graph as a "mess of pointers" and you don't have lazyness or side-effects in your language, you are in trouble. (In SML, you can use "ref" types to build mess-of-pointer data structures, if you really want to.) In a purely functional setting, you should take a more abstract approach: think about what the operations are you want to use and then about how to represent them. For example: signature GRAPH = sig type Graph type Node val nodes: Graph -> Node list val neighbors: Node -> Node list val with_edge: Graph * Node * Node -> Graph val without_edge: Graph * Node * Node -> Graph val without_node: Graph * Node -> Graph end Internally, you could represent graphs as adjacency matrices, sparse adjacency matrices, etc. No need to use a "mess-of-pointers" representation. COMMENT: as you use SML in your example, how would you implement these matrices efficiently in SML? Using functions of type Node * Node -> bool ? Using (nested) lists ? And then: the binary decision diagrams I was working on are very regular graphs (almost tree-like). It seems to me, that adjacency matrices are a too general and inefficient representation for these. ------------------------------------------------------------------------------ From: rmz@ifi.uio.no (Bjorn Remseth) Organization: University of Oslo, Institute of Informatics ------------------------------------------------------------------------------ It isn't really that difficult. A graph can be thougth of as a relation between nodes. Most graph algorithms work by either adding new relations (new edges) or modifying old ones. This is basically array updating. The trouble with pure functional programming languages is that an entire array has to be sent as an argument, mofigirf a little, and then sent on to the next part of the algorithm. When done stupidly this is very inefficient because the entire array has to be copied every time it is applied, this is why the array updates in graph algorithms are usually implemented with side effects. However, it is possible to determine when an array is not needed elsewhere and in those cases not do a copy but instead send the only array as the argument.. If you are a bit careful when designing your algorithms, it turns out that you in many cases can get away with almost no copying and thus quite effective code. So, essentially this boils down to a problem of efficient code generation for functional languages. A good book to check out for a general introduction to this field is "Functional Programming" by Anthony J. Field and Peter G. Harrision (ISBN 0 201 19249 7). You might also want to check out what the SISAL people at Livermore has done. SISAL is a functional programming language designed for numerical work. It generates very efficient code due to a small set of clever optimizations. You should contact John Feo (feo@lll-crg.llnl.gov) for more information about SISAL. ------------------------------------------------------------------------------ From: rockwell@socrates.umd.edu (Raul Rockwell) ------------------------------------------------------------------------------ Well, I'd call J a functional programming language, and it allows you to do a lot of "graph theory" work. Basically, you can represent a graph as a square two-dimensional array. I guess, I could say Aij is 0 for the case where there is no arc from i to j, and is 1 for the case where there is an arc from i to j. The binaries come with several pages of examples of this kind of stuff. (Not that the documentation that you can get via ftp is adequate). COMMENT: J version 2.9 for Sun-3, Sun-4 and a couple of other machines is available by anonymous ftp from watserv1.waterloo.edu (129.97.129.140) in directory languages/apl/j . ------------------------------------------------------------------------------ From: mmh@dcs.qmw.ac.uk (Matthew Huntbach) ------------------------------------------------------------------------------ I am not sure about functional programming, but a particular interest of mine is representing graph algorithms in parallel logic languages. You need to think of each vertex in the graph as a process and the edges as communication channels. You can then develop some very elegant declarative programs. Two references to papers of mine: Implementing a Graph-Colouring Algorithm in Parlog SIGPLAN notices, 24, 10 pp.80-85 Sep. 1989. A single-message distributed algorithm for minimal spanning trees. To appear in the First International Conference of the Austrian Centre for Parallel Computing, 1991. ------------------------------------------------------------------------------ From: S.R.Adams@ecs.southampton.ac (Stephen Adams) ------------------------------------------------------------------------------ I am interested in this problem. I have had many problems trying to rewrite algorithms in a functional style. Many of the algorithms are not graph algorithms as such, just clever imperative algorithms. I would like to see functional, *declarative* versions of these algorithms: 1. Closure of a set under a relation 2. Traversal of a graph 3. A functional solution to the O(nG(n)) union-find problem. [Robert Sedgewick, Algotithms 2ed, Addison Wesley 1988, p441-449] 4. A functional solution of Hopcroft & Tarjan's O(V) planarity test [Efficient Planarity Testing, J.ACM 21(4) Oct. '74 549-568] In one sense these problems are all easy. It is simply a matter of passing the mutable data structures as parameters. By writing one function for each control point in the imperative program it can be arranged that the variables used for the mutable data structures are suitable for in-place-update optimization. Programs written like this are using the functional paradigm as a poor tool for expressing an imperative algorithm and are consequently not very easy to read and understand. They are hardly declarative. ------------------------------------------------------------------------------ From: m89mph%ecs.oxford.ac.uk (Mark P. Harrison) ------------------------------------------------------------------------------ I don't know about the difficulty of functional languages and graph theory. I'm an undergraduate at Balliol College, Oxford, and thus was brought up with my first programming lessons on Orwell (Wadler, Bird : like Miranda), and would prefer to do my current (Modula-2) practicals in a functional language. If you mail me the problem you did on graphs, I'll see what I make of it, from the perspective of a functional programmer with MUCH LESS imperative experience COMMENT: Have a look at the algorithms in the following paper and try to reformulate them in a functional language (SML or at least non-lazy/eager evaluation scheme preferred): @article(Bryant86a, author = {R.E. Bryant}, title = {Graph-Based Algorithms for Boolean Function Manipulation}, journal = {IEEE Trans. on Computers}, year = {1986}, volume = {C-35}, number = {8}, pages = {677-691} ) ------------------------------------------------------------------------------ From: jl@cs.glasgow.ac.uk (John Launchbury) ------------------------------------------------------------------------------ A couple of years ago, I coded the double DFS algorithm for finding strongly-connected components algorithm in Lazy ML (Aho, Hopcroft and Ullman, in ``Data Structures and Algorithms'', describe it on page 224 and attribute it on page 229 to R. Kosaraju (1978, unpublished) and Sharir (1981, ``A Strong Connectivity Algorithm & its Application in Data Flow Analysis'', in Computers and Mathematics with Applications 7:1, pp. 67-72)). It took me a few hours to re-express it functionally, but I was very pleased at how concisely the algorithm may be expressed. Even more pleasing, however, is the fact that it enables us to pinpoint exactly the parts that need `imperative-like' features to be fully efficient. The algorithm is as follows. let rec cyclic es vs = snd (span (range (map swap es)) ([],[]) (snd (dfs (range es) ([],[]) vs))) and range [] w = [] || range ((x,y).xys) w = if x=w then y.range xys w else range xys w and dfs r (vs,ns) [] = (vs,ns) || dfs r (vs,ns) (x.xs) = if member vs x then dfs r (vs,ns) xs else let (vs',ns') = dfs r (x.vs,[]) (r x) in dfs r (vs',x.ns'@ns) xs and span r (vs,ns) [] = (vs,ns) || span r (vs,ns) (x.xs) = if member vs x then span r (vs,ns) xs else let (vs',ns') = dfs r (x.vs,[]) (r x) in span r (vs',(x.ns').ns) xs The function `cyclic' is given a list of edges and vertices (defining the graph). The complexity is O(n.n). To achieve O(n.log n) you need to do two things: first, represent the `visited' list as a tree. However this is not of itself enough: the functions `ins' and `outs' are linear to use and so they also cause the complexity to be O(n.n). In an implementation with finite functions (i.e. arrays with constant access time e.g. Haskell) these functions could be generated once (linear) and access would be constant thereafter. (In the imperative case, this corresponds to constructing an actual node in the heap from the abstract description of the graph). If both of these are done we get O(n.log n) for the whole thing. If we had updateable arrays to use instead of a `visited' list (single-threading analysis and all that jazz) then we can get O(n) as in the imperative case. In case you are not overly familiar with LML, here is an almost equivalent version in Orwell (very like Miranda): > cyclic es vs = snd (span ins ([],[]) (snd (dfs outs ([],[]) vs))) > where ins w = [x | (x,y) <- es; y=w] > outs w = [y | (x,y) <- es; x=w] > dfs = foldl . df > df r (vs,ns) x = (vs,ns), if x $in vs > = (vs', x:ns'), otherwise > where (vs',ns') = dfs r (x:vs,ns) (r x) > span = foldl . sp > sp r (vs,ns) x = (vs,ns), if x $in vs > = (vs', (x:ns'):ns), otherwise > where (vs',ns') = dfs r (x:vs,[]) (r x) Thus, the marking of the graph is the *only* place where the imperative algirithm wins. Hope this is of some use. ------------------------------------------------------------------------------- From: louk%tslwat@watmath.waterloo.edu (Lou Kates) Organization: Teleride Sage, Ltd., Waterloo ------------------------------------------------------------------------------- Could you please tell me what you find out. By the way, I find this hard to believe. For example, if you represent a graph by its adjacency matrix then the graph algorithm will be transformed into a matrix algorithm and functional languages like APL are very good at matrix manipulation. ------------------------------------------------------------------------------- From: mcphee@cs.utexas.edu (Nic McPhee) Organization: U. Texas CS Dept., Austin, Texas ------------------------------------------------------------------------------- Programming with graphs can actually be quite interesting and easy, especially if you are using a lazy langauge. The trick is building the graph in the first place, but once that's done everthing else is a piece of cake. Most people are familiar with circular lists (a simple form of graphs), e.g., ones = 1:ones (using Miranda) and the question is how to generalize this to more interesting graphs. I did this a few years ago when doing some work with circuits (the gates were the nodes and the wires the edges). My solution was to put the nodes in a list and include in each node its index in that list. This index could then be "dereferenced" to generate an "edge". As an example take the following definition of a fully connected graph with n nodes: node :: Node num [ node ] graph n = the_graph where the_graph = map build_graph [0..n-1] build_graph i = Node i [ the_graph!j | j<-[0..n-1]; j != i ] There very well may be even better ways of doing this. If this isn't terribly clear I apologize; it's been quite a while and I'm doing this from memory. If you'd like more (or clearer) information just poke me and I'll hunt up the old source code and try to be more coherent. ------------------------------------------------------------------------------- From: Jeremy.Gibbons@prg.oxford.ac.uk ------------------------------------------------------------------------------- Please summarize! COMMENT: Well, that's it all. Hope you're satisfied.