How should I represent these relative taller/shorter comparisons?

Question

Say I'm parsing a statement like: "Blake is taller than Mary and Mary is taller than Sue and Sam is shorter than Mary and John is taller than Mary"

Which would look like:

Sue, Sam
Mary
John, Blake

Maybe:

Array(
    [0] => Array(
        [0] => Sue
        [1] => Sam
    )

    [1] => Mary
    [2] => Array(
        [0] => John
        [1] => Blake
    )
)

We don't know which of Sue and Sam is shorter/taller and we don't know which of John and Blake is shorter/taller so they sit together on the same lines.

But then later I could give it the statement: "Blake is shorter than John" which would make it look like:

Sue, Sam
Mary
Blake
John

Thoughts? I know if I just try to jump in here I'm going to make a mess of it, so I was just wondering about the best way to represent it. An array like above or maybe a tree array?

I'm thinking of later giving it a question like "Who is shorter, Blake or Sue?" with the answer being Sue.

Answer 1

That can be represented with a directed graph. When you have relative information about the height of two persons, add an edge between them such that it either points to the taller or shorter person. (Which does not matter as long as you're consistent.) To see if someone is shorter or taller than another, see if they are an ancestor or descendant of the other. If a cycle is formed, it means the information is inconsistent.

In PHP, you'd probably have a Person class. Each Person would have an array of Persons that they're taller (shorter) than. You'd then have an array of Person objects. To create a link, you'd add the tallest (shortest) person to the shortest (tallest) person's taller (shorter) arrays.

To test whether a person A is shorter (taller) than a person B, start with person A and recurse through all direct and transitive taller (shorter) persons. If you reach person B, person A is shorter (taller) than person B. Try swapping person A and B and seeing if that yields a result. If there is still no definite result, then there is not enough information to determine the relative heights of persons A and B.

In the case that the information is inconsistent, recursing as above will lead to infinite recursion.