Here is my summary of responses on functional programming of graph algorithms.

Quote:

> 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:

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

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

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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.

------------------------------------------------------------------------------

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

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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 .

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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.

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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):

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}

)

------------------------------------------------------------------------------

------------------------------------------------------------------------------

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
...

**read more »**