Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!mintaka!ai-lab!life!tmb
From: tmb@ai.mit.edu (Thomas M. Breuel)
Newsgroups: comp.lang.functional
Subject: Re: Summary: functional programming of graph algorithms (long)
Message-ID: <TMB.91Jun19001755@volterra.ai.mit.edu>
Date: 19 Jun 91 04:17:55 GMT
References: <5495@ztivax.UUCP>
Sender: news@ai.mit.edu
Organization: MIT Artificial Intelligence Lab
Lines: 41
In-reply-to: corvara@ztivax.UUCP's message of 11 Jun 91 14:07:46 GMT

In article <5495@ztivax.UUCP> corvara@ztivax.UUCP (Dr Gerd Venzl) writes:
   Here is my summary of responses on functional programming of graph algorithms.

   >>> From: tmb@ai.mit.edu (Thomas M. Breuel)

   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.

The method of reverse diffs that I described in my previous posting is
applicable to most data structures (remember: for algorithms converted
from imperative languages, you pay only O(1) overhead using reverse
diffs if you use data structures based on reverse diffs and a fully
functional programming style).

Probably, the simplest and most flexible data structure for computing
the "neighbors" functions is a hash table that maps from nodes to node
lists and is maintained using reverse diffs.

						Thomas.