Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Representing graphs?
Message-ID: <6566@goanna.cs.rmit.oz.au>
Date: 30 Jun 91 09:08:00 GMT
References: <ARI.HUTTUNEN.91Jun23021130@wonderwoman.hut.fi> <1991Jun27.094828@aifh.ed.ac.uk>
Distribution: comp
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 36

In article <1991Jun27.094828@aifh.ed.ac.uk>, fcs@aifh.ed.ac.uk (Flavio
Soares Correa Da Silva) writes:
> In article <6505@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A.
> O'Keefe) writes:
> 
> # Another representation would be the
> # adjacency matrix, represented as a quad-tree, which works rather
> # nicely.
> 
> Could you explain this a bit more? 

I see that Flavio Soares Correa Da Silva is posting from DAI Edinburgh.
My last notes in Dr Bundy's Mathematical Reasoning Group's ``Blue Book''
are about matrix manipulation in Prolog.

Basically, the idea is that you represent an M-by-N matrix as
	matrix(M, N, QuadTree)
what does the QuadTree look like?
M = 1, N = 1	=> scalar(X_11)
M = 1, N > 1	=> row(X_11_to_X1J, X1K_to_X1N)		 1    J K   N
		   where J = N div 2, K = J+1		+-----+-----+ 1
M > 1, N = 1	=> col(X_11_to_XP1, XQ1_to_XM1)		|  A  |  B  | P
		   where P = M div 2, Q = P+1		+-----+-----+ 
M > 1, N > 1	=> matrix(A, B, C, D)			|  C  |  D  | Q
                   where the matrix is partitioned	+-----+-----+ M
		   as shown on the right.
This provides very efficient `bulk' operations on such matrices,
and logarithmic time access to individual elements.  It's a very nice
data structure for linear algebra operations, and has some useful
extensions.

Graph algorithms expressed in terms of the adjacency matrix can be
programmed using this data structure, and if they work by rows and/or
columns rather than by individual elements, they perform well.
-- 
I agree with Jim Giles about many of the deficiencies of present UNIX.