Algorithm: how to check whether two set doesn't conflict

Question

write a function:

Input: two set, one reflect equal relationship, like {A = B, B = C}, another one reflect not-equal relationship, like {A != C}

Output: check whether the two set conflict or not, return a boolean type

public boolean isConflict(List<String> equalRelation, List<String> notEqualRelation) {
    //......
}

Answer 1

Create a graph from your data. Every variable is a node and every equal is an undirected edge between corresponding nodes. After that every connected component represents equality between all of its nodes. For finding contradictions you could simply check if two nodes in a not equal relationship are in a same component or not. If they are this a contradiction.

You can use dfs,bfs for finding connected components. But if your data is dynamic it is better to use disjoint-set data structure.

Answer 2

You have done half the job:

• your set of set equal relationship => keep it like Set< Pair< String,String> > , and the same thing for not-equal relationship
• create a set of entities equal, like a Map : any symbol => reduced symbol equals. For example: A=B gives you, if A< B : A=>A (implicit), B=>A, and if A=>C, then B=>C. You have to iterate another time to reduce everything. With that,you map every equal symbols to an unique one (the least in my example);
• finally, iterate through your Set of non-equals, and check every pair (X,Y) => is reduced(X)=reduced(Y) which means X=Y : you have a conflict there

If you want to keep Pair<>, use this, courtesy of : A Java collection of value pairs? (tuples?)

public class Pair<L,R> implements java.io.Serializable  {

  private final L left;
  private final R right;

  public Pair(L left, R right) {
    this.left = left;
    this.right = right;
  }

  public L getLeft() { return left; }
  public R getRight() { return right; }

  @Override
  public int hashCode() { return left.hashCode() ^ right.hashCode(); }

  @Override
  public boolean equals(Object o) {
    if (o == null) return false;
    if (!(o instanceof Pair)) return false;
    Pair pairo = (Pair) o;
    return this.left.equals(pairo.getLeft()) &&
           this.right.equals(pairo.getRight());
  }

}

Answer 3

Vogel612 is pretty much right. The basic algorithm is: complete the equality relation, then test each inequality in the list to see if any conflicts. However, you would not generally do any completion on the inequalities.

I’ll mention that equivalence is transitive (a = b = c implies a = c) but inequality is not (1 ≠ 1+1 and 2 ≠ 1, but 1+1 = 2). Both are symmetric, though (if a = b, b = a), and equivalence is also reflexive (each element must equal itself).

The exact data structure to use might depend on whether we have a list of all the elements in advance, how many there are, and how sparse the truth table for the relation is likely to be. If the amount of memory we need to store the truth table as a two-dimensional array is reasonable, we could do it that way. Vogel612’s approach of storing the table as a collection of rows, each row containing the set of elements equivalent to its index, is a good way of storing a truth table with only a few elements equivalent to every element. (If every row is guaranteed to contain at least one element, itself, this should become an array or arrayList.) Another approach is to create an arbitrary total ordering on the element names, such as the order in which we added them to an arrayList, the hash value of their names, or a lexicographic ordering. This order has nothing to do with the values of those elements or the provided equality relation, but can be used to put every pair into a canonical form. That is, our elements are listed a, b, c, and a < b < c when we compare their names even if the values are equal by the relation. Keep a set (probably a hashSet in Java) of tuples of elements (a,b) such that 'a' precedes 'b' in this ordering and their contents are equal, letting the facts that a = a, b = b and b = a be implicit. This will be efficient when very few other pairs of elements are equivalent. There are also more complicated data structures for sparse matrix storage that are not in the standard library.

In any case, you always want x ≠ x to fail and to look for the tuples in the same canonical form that you stored them in.