representing graph in Clean

[Adrian Hey]

Hello,

On Sun 11 Jun, khamenya wrote:
> Q1: How to represent graph in Clean?
> Q2: How to effectively represent graph in Clean?

I was playing about with this sort of thing a little while ago and had a
module of graph tools in Clean, but now I seem to have lost it:-(, but
I can remember roughly how I did this (without using arrays, uniqueness etc)

I used a binary tree data structure, where each node can be identified by
the path taken from the root to that node.
e.g  L = Left R = Right T=Terminate
 path ::= L path | R path | T

                                  T
                        LT                 RT
                  LLT       LRT       RLT       RRT
               LLLT LLRT LRLT LRRT RLLT RLRT RRLT RRRT
               etc..
               etc....
               etc........

You can create an infinite list of new paths..
 path_supply :: [path]
 path_supply = [T:(split path_suply)]
  where split [p:ps] = [(L p):(R p):(split ps)]

If you put nodes in the tree in the order supplied by path_supply it will
always be height balanced. Also, each new path only uses 1 new heap record.

It's fairly easy to write functions to 'randomly' insert/read/modify
nodes from a binary tree. At each node you have some data structure of your
own design which represents a vertex of the graph, with the edges being a
list of paths.

> Q2a: Can I access node Y which is neighbor for given node X at constant time?

Using a binary tree of N nodes, access time will be O(log(N)).

> Q2b: Is it possible to effectively represent graph in Clean _without_
>      arrays?

Yes, I think what I've described is a bit more flexible, but not so efficient,
depends what you want to do. I was using it to do dependancy analysis by
finding strongly connected components.

Regards
-- 
Adrian Hey