Boost logo

Boost :

From: mkenniston_at_[hidden]
Date: 2000-10-27 11:49:46


Daryle Walker wrote:

> But doesn't this assume that every object of a type can be put into an
> order, so it can be related with every other object? What about types that
> have object(s) that incomparable with (a subset of) other objects of that
> type?

David Abrahams replied:

> Valentin Bonnard has proposed something like this in the past. He even had
> the correct mathematical name for it ("partially_ordered<>", I think). You
> might search the past message archives for references.

(Try the thread beginning with message 176 in the archive.)

There is an established mathematical concept called a "partial order".
The usual <, =, > where everything is related to everything else is called
a "total order", and you can represent a total order by mapping the entire
set onto a single line.

A partial order can be represented by mapping the entire set onto a
directed acyclic graph. In order for a relationship to be a partial order,
there are still constraints like transitivity: if a < b and b < c, then a < c.

One area where partial orders can be useful is in the analysis of
distributed systems timing. If event a is known to precede event b
then a < b, but in cases where no order can be determined we
consider the events to be concurrent or simultaneous.

- Michael Kenniston


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk