Re: Data structures for checking consistency of a partial order?



On Sat, 30 Jun 2007 01:45:55 -0700, Benjamin Johnston wrote:

I'm hoping somebody could point me in the direction of a good
datastructure for checking the consistency of a partial order.
/snip/
I have a series of constraints that arrive incrementally over time.
/snip/
/snip/

Thinking over this for the past few days has got me thinking that the
problem is much like finding the shortest path on a graph.

I'm thinking now that it may be possible to annotate each variable
with an integer, thereby forming a "temporary" total ordering: this
would allow fast checking of facts that happen to be consistent with
the total ordering, and if a new fact in the partial order arrives
that is inconsistent with the total order, then the total order could
be updated fairly quickly (if no valid total order exists, then it the
partial order would be invalid). Something like an incremental version
of Dijsktra's algorithm.

Thanks for your help,

-Benjamin Johnston

IMHO finding inconsistencies boils down to finding loops in the graph.

I don't know if you want to only keep 'ordered pairs' of
{item,item,(operator)} ; or if you also will allow *sets* of items
(as in "dogs are smaller then horses" )
Allowing sets, the empty set can sometimes be a valid solution to
a "query" (eg: find dogs that are bigger than horses) , but adding the
ordering "horses are smaller than dogs" would of course need to be
detected as a violation.

Maybe a bit related to your problem:
http://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf

HTH,
AvK
.



Relevant Pages

  • Re: about nonreflexivity of order relation
    ... irreflexive iff not for all x; ... A weak partial order is a relation that is reflexive, antisymmetric, and transitive. ... A strict partial order is a relation that is irreflexive and transitive. ... A strict total order is a dichotomous strict partial order. ...
    (sci.math)
  • Re: Data structures for checking consistency of a partial order?
    ... datastructure for checking the consistency of a partial order. ... A multi-dimensional array would be one possibility. ... equivalent to computing the transitive closure, ... that is inconsistent with the total order, ...
    (comp.programming)
  • Re: Details about pythons set implementation
    ... isn't this the normal definition? ... Mathematically speaking, it is an order, and a very useful one. ... it's a partial order, which means that if a!= b then they are not ... What you need is a total order, where any two distinct elements are ...
    (comp.lang.python)
  • Re: Efficient Vector Comparison
    ... Yeah, I do not have a total order, but I do not need such total order. ... They are in a partial order, ... if this vector set is partial ordered? ...
    (comp.programming)
  • Re: Limits
    ... then "ordering by a" yields a total ordering over R: ... but "ordering by b" gives the partial ordering: ... Can it understand partial order? ...
    (comp.databases.theory)