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

*From*: moi <root@xxxxxxxxxxxxxxxxxxxxx>*Date*: Sat, 30 Jun 2007 14:57:37 +0200

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

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

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

.

**References**:**Data structures for checking consistency of a partial order?***From:*Benjamin Johnston

**Re: Data structures for checking consistency of a partial order?***From:*Rob Thorpe

**Re: Data structures for checking consistency of a partial order?***From:*Benjamin Johnston

- Prev by Date:
**Re: Application programming language of choice** - Next by Date:
**Re: Help** - Previous by thread:
**Re: Data structures for checking consistency of a partial order?** - Next by thread:
**Re: Data structures for checking consistency of a partial order?** - Index(es):