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
.