How to manage partial orders?

Quote:

> I need to manage partial orders over a finite set of objects. The

> objects are known in advance.

> The possible orderings between objects are =<, <, =, >, and =>.

> Operations are adding a new ordering constraint between two objects and

> extracting a total ordering which is consistent with the partial one.

> Adding a new constraints should fail, if the resulting constraint set is

> inconsistent.

I wouldn't call this a "standard problem" in the sense of having

a standard solution -- doesn't it depend on what you intend to

do with this when you have it?

One potential solution treats the ordering relations as

elements of a square matrix representing the cartesian product

of your set of objects with itself. You then have

o1 o2 o3 o4 ......

o1 = # # #

o2 # = # #

o3 # # = #

o4 # # # =

. .

. .

. .

which is easy enough to represent in Prolog as a list of tuples

r(Row,Col,Reln), where Reln are values that replace the # of

the matrix above, i.e. =, >=, >, etc. (and actually, only the

lower or upper triangle of the matrix is really necessary).

For partial orders, you also need a value that means "unspecified";

depending on your implementation, a Prolog variable might work.

It is then relatively straightforward to define transitivity,

reflexivity and symmetry as predicates holding of two lists,

one which specifies your initial partial order, and another

which expresses the closure of your partial order, with respect

to transitivity, symmetry, etc. as you have defined them.

I worked out a such a solution for identifying the complete

set of total orders consistent with a given partial order,

where only > and < were considered. It's not particularly

pretty, easy to use, or well-documented, but I'll dig it up

if you want to look at it.

Hope that helps,

John Paolillo

SLIS and Informatics

Indiana University