Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!comp.vuw.ac.nz!steve
From: steve@comp.vuw.ac.nz (Steve Cassidy)
Newsgroups: comp.lang.prolog
Subject: Re: Partial Orders
Message-ID: <1991Mar01.005726.13016@comp.vuw.ac.nz>
Date: 1 Mar 91 00:57:26 GMT
References: <1991Feb27.032403.23920@comp.vuw.ac.nz>
Sender: news@comp.vuw.ac.nz (News Admin)
Organization: Dept. of Comp. Sci., Victoria Uni. of Wellington, New Zealand.
Lines: 80
Nntp-Posting-Host: climie.comp.vuw.ac.nz

I wrote:
>I need some help in finding an appropriate representation for
>my data. I am storing a set of objects (they are, in fact, rules
>for translating text to speech) for which I have an ordering
>relation (generality -- the rule applies to more pieces of text) which
>defines only a partial ordering on the objects (eg. x>y -- yes;
>x>z -- dunno; x>w -- no).

Let me attempt to answer my own question. What I'm after representing
is a directed acyclic graph (dag).  After a little more
thought (and a good nights sleep) I came up with the idea of
using adjacency lists, where each node has associated with
it a list of nodes that follow it in the ordering. So the
dag:

             a    b    c
	      \  /    /
	        d    /          ( where the arrows go from top to bottom)
	       / \  /
	     (f)  e

would be written as: 

               [a/[],
		b/[],
		c/[],
		d/[a,b],
		e/[a,b,c,d]]

Adding an item to the dag (say f in brackets above) involves
comparing it with the existing elements using our ordering
relation.  If f > X then X is added to the adjacency list of
f, if X > f then f is added to the adj list of X. In the
above case we must add f/[a,b,d] to the list.  Note that
this results in us keeping the full transitive closure of
the dag at all times, this helps for deletion.

Deletion is a problem, it would seem to require copying all
or most of the existing structure, plus to remove, say, b we
need to remove b's adjacency list and remove b from all
other adjacency lists.  My solution is to represent each
node as a pair n( a, DelA ) where DelA is a deleted flag
which will be unbound if a has not been deleted.  The above
dag would now look like: 

               [n(a, DA)/[],
		n(b, DB)/[],
		n(c, DC)/[],
		n(d, DD)/[n(a, DA),n(b, DB)],
		n(e, DE)/[n(a, DA),n(b, DB),n(c, DC),n(d, DD)]]

To delete a now I just unify DA = del.  My access routines
must ignore items marked as deleted and, if there are a lot
of deleted items all operations will be slowed but deletion 
itself is very quick, which is what I wanted.  

Since a lot of items may be deleted it is a good idea to get
rid of the deadwood every now and then.  We can do this by
copying the entire dag and leaving out the deleted items.  

I've implemented this using binary trees to store both the
set of nodes/adjacency lists and the individual adjacency
lists.  My initial trials seem to work, I have not yet tried
it in anger.  

So, any opinions on this solution? Is it good style to use
unbound variables as deletion flags as I have done?  If
there are any flaws in my solution I'd appreciate some
clues. 


Thanks, 

Steve Cassidy
==========================================================
Computer Science,                     steve@comp.vuw.ac.nz
Victoria University of Wellington,    ====================
Box 600,                              Voice:  +64 4 715328
Wellington, New Zealand.              Fax:    +64 4 712070
----------------------------------------------------------