🚀 go-pugleaf

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 <REDDY.91May28195125@reddy.cs.uiuc.edu>)
and T.M. Breuel (tmb@ai.mit.edu, <TMB.91May29174602@volterra.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.