How to manage partial orders? 
Author Message
 How to manage partial orders?

Hello everybody!

I need to manage partial orders over a finite set of objects.  The
objects are known in advance. Because this seems to be a more or less
standart problem, I would like to ask you to point me to an existing
implementation.  No, this is not a homework assignement ;-)

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.

Thank you, Uli

--
Ulrich Scholz


http://www.*-*-*.com/ ~scholz/



Thu, 03 Jun 2004 20:09:25 GMT  
 How to manage partial orders?
On Sun, 16 Dec 2001 13:09:25 +0100, Ulrich Scholz

Quote:

>Hello everybody!

>I need to manage partial orders over a finite set of objects.  The
>objects are known in advance. Because this seems to be a more or less
>standart problem, I would like to ask you to point me to an existing
>implementation.  No, this is not a homework assignement ;-)

>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 spent quite a bit of time looking for existing implementations,
but was unable to find such. I had to write my own code....

A.L.



Fri, 04 Jun 2004 05:29:58 GMT  
 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



Fri, 04 Jun 2004 05:44:43 GMT  
 How to manage partial orders?
I have solution for such problem
I describe elementary relations between terms
   nt(X, Y) means that X is more then Y  should be eplicitly asserted in
database    -  narrow term
   et(X, Y)  means that X is equal Y
and then I create transitive closure of nt
so you can find answers on  questions like nrt(X, Y)
where nrt is transitive close of nt
I'll send code little later today


Quote:
> Hello everybody!

> I need to manage partial orders over a finite set of objects.  The
> objects are known in advance. Because this seems to be a more or less
> standart problem, I would like to ask you to point me to an existing
> implementation.  No, this is not a homework assignement ;-)

> 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.

> Thank you, Uli

> --
> Ulrich Scholz


> http://www.intellektik.informatik.tu-darmstadt.de/~scholz/



Sat, 05 Jun 2004 09:41:15 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Higher-Order Logic Programming and Partial Evaluation (Was Permutations)

2. Partial-order problem

3. partial ordering problem

4. Partial Order Planners in Prolog

5. Sorting according to a partial order

6. Partial ordering and unions

7. Partial ordering algorithm needed

8. Partial Orders

9. Partial Orders

10. Partial order sort

11. Partial.py: convenient notation for partial application/currying

12. Order of ORDER output

 

 
Powered by phpBB® Forum Software