Since you say that the preprocessing step does not need to be super-fast, then I suggest storing it as a graph. Once you add the "base" comparisons as directed edges, you can compute the transitive closure of the graph. To check a comparison query, you just have to see whether the edge exists in the transitive closure, which is a very fast operation if the graph is pre-computed.

The only thing to watch out for is the equalities in the data. As long as we're using graphs, you can use an undirected graph to keep track of which items are equivalent, so you can map the members of each equivalence class to a unique representative. Also, if something comes in the data that says xx>yy and later yy>xx, should I infer that xx=yy, or is that an error? My sample code below treats it as an error (the resulting graph is not a DAG), but I suppose you could do either.

Here is a rough proof-of-concept that I hope doesn't have too many bugs.

use strict;
use Graph::Undirected;
use Graph::Directed;

my @data = qw[ xx<yy yy<zz zz>aa bb<yy yy=aa aa>cc ];

## take all equalities in the data, map each item to
## a canonical (equivalent) representative.

my $eq = Graph::Undirected->new;
$eq->add_edge( split /=/, $_ ) for grep /=/, @data;

my %canonical;
for ($eq->connected_components) {
   my $representative = $_->[0];
   for (@$_) {
      $canonical{$_} = $representative;
   }
}

sub canonical {
    exists $canonical{$_[0]} ? $canonical{$_[0]} : $_[0];
}

## take all inequalities in the data, make a dag from them
## and take the transitive closure.

my $g = Graph::Directed->new;
for (grep !/=/, @data) {
    my ($x, $y) = split /<|>/, $_;
    ($x,$y) = ($y,$x) if /</;

    $g->add_edge( canonical($x), canonical($y) );
}

die "Not a DAG!" unless $g->is_dag;
$g = $g->transitive_closure;

sub compare {
    my ($x,$y) = map canonical($_), @_;
    return  0 if $x eq $y;
    return  1 if $g->has_edge($x,$y);
    return -1 if $g->has_edge($y,$x);
    return  0;
}

my @items = qw[ aa bb cc xx yy zz ];

for my $x (@items) {
  for my $y (@items) {
     print "$x, $y: " . compare($x,$y). $/;
  }
}
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.