3
$\begingroup$

I have a table of inequality constraints, each with an "x < y" relation. How can I check this table for contradictory logic such as a < b, b < c, c < a?

For example

library(data.table)
set.seed(0)
ineqs <- unique(data.table(
  X = sample(head(letters, 5), 5, replace = T),
  Rel = "<",
  Y = sample(head(letters, 5), 5, replace = T)
))

ineqs
   X Rel Y
1: e   < b
2: b   < e
3: c   < d
4: e   < d

In this case, a function like is_valid(constraints) should obviously return FALSE because the constraints e < b, and b < e are contradictory.

$\endgroup$

closed as off-topic by Kodiologist, Sycorax, kjetil b halvorsen, mkt, Firebug Oct 5 '18 at 12:35

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question appears to be off-topic because EITHER it is not about statistics, machine learning, data analysis, data mining, or data visualization, OR it focuses on programming, debugging, or performing routine operations within a statistical computing platform. If the latter, you could try the support links we maintain." – Sycorax, kjetil b halvorsen, mkt, Firebug
If this question can be reworded to fit the rules in the help center, please edit the question.

3
$\begingroup$

The relation matrix $M(R)$ is the binary indicator of the relation: in this case, the entry in $M(\lt)$ for variables $x,y$ is $1$ (true) when $x\lt y$ and $0$ (false) otherwise.

These individual relationships imply other relationships through the transitivity property $a\lt b$ and $b\lt c$ implies $a\lt c.$ The resulting transitive closure of the relation matrix must be consistent with antisymmetry: $M(R)[x,y]=1$ implies $M(R)[y,x]=0.$ The transitive closure is readily (if not entirely efficiently) found by taking powers of $M(R)$ until they stabilize, treating all values of $0$ as false and all nonzero values as true.

Thus, you can systematically check such a relation by (1) generating its matrix, (2) computing its transitive closure, and (3) checking that for (partial) antisymmetry. This is a general solution for any transitive, partially asymmetric relation, although it needs an (obvious) modification for reflexive relationships like $\le$ (where $M(R)[x,x]=1$ for all $x$).

Below is working R code to illustrate. It checks five relations defined by sets of inequalities (given as character strings involving alpha variables). Its output is

[1] "Invalid: FALSE"
[1] "Valid: TRUE"
[1] "Invalid.2: FALSE"
[1] "Valid.2: TRUE"
[1] "Invalid.3: FALSE"

The first term is my indication of whether the relation is valid and the second TRUE/FALSE is the code's determination. It and I agree. The first line of output corresponds to the example in the question.

constraint.to.matrix <- function(x) {
  ab <- sapply(x, function(s) strsplit(s, "[^[:alpha:]]+"))
  vars <- sort(unique(unlist(ab)))
  n <- length(vars)
  r <- matrix(0, n, n, dimnames=list(vars, vars))
  for (rel in ab) {
    r[rel[1], rel[2]] <- 1
  }
  r
}

is.antisymmetric <- function(r) all(c(t(r) + r + diag(nrow(r))) <= 1)

transitive.closure <- function(r) {
  s <- r + diag(nrow(r)) >= 1
  while(TRUE) {
    r1 <- r %*% s > 0
    if (all(r1 - r == 0)) break
    r <- r1
  }
  r
}

check <- function(constraints) 
  is.antisymmetric(transitive.closure(constraint.to.matrix(constraints)))

trials <- list(Invalid=list("e < b", "b < e", "c < d", "e < d"),
               Valid=list("a<b", "b<c", "c<d"),
               Invalid.2=list("a<b", "b<c", "c<d", "d<a"),
               Valid.2=list(),
               Valid.3=list("a<a"))

for (s in names(trials))  print(paste0(s, ": ", check(trials[[s]])))
$\endgroup$
2
$\begingroup$

The solution by @whuber is more complete than this one. However, if one accepts to use the igraph package, one can use the graph properties to test for transitivity, so that there is almost no code to write.

Transforming the list of inequalities into a list of edges of a directed graph, we can test whether the graph is acyclic (see here for a definition).

library(igraph)
## Form a graph out of the edge list
gg <- graph_from_edgelist(as.matrix(ineqs[,c(1,3)]), 
    directed = TRUE)
## Test if the graph is a DAG
is_dag(gg)

In the case of the data generated above, indeed, the graph is not acyclic and the test returns FALSE. (If you change the seed to 1 and keep the code above, you'll generate a DAG: the inequalities do not have any contradiction).

$\endgroup$
  • $\begingroup$ +1 I ended up using this because it runs significantly faster than whuber's solution on my large-ish dataset. It's also easier to implement and easier to understand IMO. $\endgroup$ – Ben Oct 6 '18 at 15:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.