Re: Data structure for partial orders

On May 26, 8:47 pm, Florian Brucker <t...@xxxxxxxxxxxx> wrote:
Hello,

I'm looking for possible choices of data structures for storing a
partial order P. The structure should allow for (relatively) fast

- element checks (given A and B find out if (A,B) in P or (B,A) in P)

- calculation of transitive closure (The closure itself doesn't have to
be stored explicitely if checking whether A and B can be compared using
transitivity can be done in a "fast" way)

- locating incomparable elements (i.e. elements A and B such that
neither (A,B) in P nor (B,A) in P)

- updating with new elements (i.e. adding (A,B) to P)

As a bonus it would be nice if checking for inconsistences with respect
to a possible new element could be easily done (e.g. checking whether
after adding (A,B) P is still a partial order).

Any pointers on this are greatly appreciated.

The PO is equivalent to a directed acyclic graph (DAG), so any
directed graph data structure applies: adjacency lists or edge
matrices for example. If you are calculating transitive closure, the
edge matrix provides for simple implementation by matrix
multiplication. See http://csdl2.computer.org/comp/proceedings/asilomar/1995/7370/00/73700799.pdf
for example.

.