Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!bionet!agate!darkstar!terra.ucsc.edu!ged
From: ged@terra.ucsc.edu
Newsgroups: comp.lang.prolog
Subject: Re: Partial Orders
Message-ID: <13048@darkstar.ucsc.edu>
Date: 4 Mar 91 22:38:50 GMT
Sender: usenet@darkstar.ucsc.edu
Reply-To: ged@terra.ucsc.edu ()
Organization: University of California, Santa Cruz
Lines: 91

>       From: steve@comp.vuw.ac.nz (Steve Cassidy)
>
>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. 

This transitive closure representation uses O(n^2) space.
While a dag representation of the non-transitive representation of a poset is 
still O(n^2), it uses a subset of the space of the transitive dag. 
Then the non-transitive representation of your poset

             a    b    c
              \  /    /
                d    /  
                 \  /
                  e

would be written as:

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

This problem has been attacked by people from a number of areas: chemical
substructure search, chess playing systems, semantic network retrieval. All
of which have complex  comparison operations (graph isomorphism).

Before we could help you further we need to know the structure of the
terms in the poset. As Richard O'Keefe pointed out: ordering sets by
cardinality also ordered them by inclusion.  Similarly, cardinality can
be used for graphs. However, terms such as semantic networks which have
abstraction over terms, size is not a necessary condition.  Size is
still only a very coarse first step.

Searching the dag of a poset can in fact be worse than linear, since a
traversal is O(m + n), where the number of edges, m, could be O(n^2) in
the worse case.  Ideally we would like a data structure similar in
performance to a balanced tree for total orders. Unfortunately we
cannot select an arbitrary pivot element that is used in balanced
trees.  The dag representation is useful for posets whose ordering is
close to a balanced tree: wide and shallow hierarchies.

Some references which you may find of interest include:

@techreport{Levinson89,
        author = {Robert A. Levinson},
        title = {A Self-Organizing Pattern Retrieval System and Its
                Applications},
        institution = {University of California},
        year = {1989},
        number = {UCSC-CRL-89-21},
        month = {September}}
@inproceedings{Ellis90a,
        author = {Gerard Ellis},
        title = {Compiling Conceptual Graphs},
        booktitle = {CGW5},
        year = {1990},
        address = {Boston\&Stockholm},
        publisher = {Link{\"o}ping University},
        editor = {Peter Eklund and Laurie Gerholz},
        series = {ISBN 91-7870-718-8},
        pages = {23-32}}
@inproceedings{Ellis90b,
        author = {Gerard Ellis},
        title = {Sorting Conceptual Graphs},
        booktitle = {Proceedings of the 5th Annual Workshop on Conceptual
                Structures},
        year = {1990},
        address = {Boston\&Stockholm},
        publisher = {Link{\"o}ping University},
        editor = {Peter Eklund and Laurie Gerholz},
        series = {ISBN 91-7870-718-8},
        pages = {265-280}}

I have a more recent paper of my work if you are interested.

Gerard Ellis
Department of Computer and Information Sciences
227 Applied Sciences Building
University of California
Santa Cruz, CA 95064
U.S.A.

ARPANET: ged@terra.ucsc.edu
PH: (408) 459 4043
          423 6734 (home)
FAX:      429 0146