When I find something interesting and new, I post it here - that's mostly programming, of course, not everything.

Wednesday, January 07, 2009

Incrementally calculating factorsets (Java class)

Recently I encountered a problem of calculating a factorset, given a set and a binary relationship. If you ask wtf is binary relationship, it is a predicate defined on pairs of elements:
interface BinaryRelationship<X, Y> extends Predicate<Pair<X, Y>> {}

Well, of course Java does not have type variables, so that one cannot interchange these two definitions... poor, poor Java programmers, poor, poor me.

But anyway.

Oh, and if you ask wtf a factorset is, let me introduce.

Definition
A binary relationship R on set A is called reflexive if aRa for all a∈A.

Definition
A binary relationship R on set A is called symmetric if aRb => bRa for all a∈A, b∈A.

Definition
A binary relationship R on set A is called transitive if aRb && bRc => aRc for all a∈A, b∈A, c∈A.

Definition
Given a set A and a reflexive, symmetric, transitive binary relationship R on A, an equivalence class over R is any such subset A1 of A that first, if x∈A1 and y∈A1 then xRy, and second, if x∈A1 and xRy then y∈A1

Definition
Given a set A and a reflexive, symmetric, transitive binary relationship R on A, a factorset A/R is defined as a set of all equivalence classes over R.

Example
Take integer numbers, and let nRm if n - m is divisible by 2. We'll have just two equivalence classes, odd numbers and even numbers. By the way, guess why two equivalence classes never intersect.

Anyway.

One can calculate a factorset even if the relationship is not symmetric, reflexive or transitive. Just produce a symmetric, reflexive transitive closure, and factor over it. The problem is, calculating a transitive closure may be costly. So, for practical reasons, I have implemented factorsets in a non-lazy way. And then I realized that, on some occasions, to provide the necessary relationship, I had to build a set of pairs, and then provide the relationship that checks if a pair is in that set, and then calculate the factorset that transitively closes the relationship. Pretty stupid, why not just do it incrementally?

That's how I got this class:

public static class FactorSet<X> {
Set<X> set;
Map<X, Set<X>> equivalenceClasses;

/**
* Builds an initial factorset, given the domain set.
*
* @param set domain set.
*/
public FactorSet(Set<X> set) {
this.set = set;
equivalenceClasses = new HashMap<X, Set<X>>();
for (X x : set) {
equivalenceClasses.put(x, Set(x));
}
}

/**
* Builds a factorset of a given set, by the transitive closure of a given relationship.
*
* @param set base set
* @param r binary relationship
*/
public FactorSet(Set<X> set,  BinaryRelationship<X, X> r) {
this(set);
factorByRelationship(r);
}

/**
* Given a <code>BinaryRelationship r</code>, merges equivalent classes if they
* contain elements that are in <code>r</code>.
*
* @param r the binary relationship. Does not have to be symmetrical or transitive.
*/
public void factorByRelationship(BinaryRelationship<X, X> r) {
for (X x1 : set) {
for (X x2 : set) {
if (x1 == x2) {
continue; // skip same value
}
if (equivalenceClasses.get(x1) == equivalenceClasses.get(x2)) {
continue; // skip same class
}
if (r.eval(x1, x2) || r.eval(x2, x1)) {
merge(x1, x2);
}
}
}
}

/**
* Merges equivalence classes for two elements
* @param x1 first element
* @param x2 second element
*/
public void merge(X x1, X x2) {
Set<X> class1 = equivalenceClasses.get(x1);
Set<X> class2 = equivalenceClasses.get(x2);
Set<X> merged = new HashSet<X>(class1);
merged.addAll(class2);
for (X x3 : merged) {
equivalenceClasses.put(x3, merged);
}
}

/**
* @return the latest version of factorset built here.
*/
public Set<Set<X>> factorset() {
return new HashSet<Set<X>>(equivalenceClasses.values());
}

/**
* @return the function from the domain set to the factorset.
*/
public Function<X, Set<X>> asFunction() {
return Functions.forMap(equivalenceClasses);
}

/**
* @return the domain set.
*/
public Set<X> domain() {
return set;
}
}

Neat, right? Look at this unittest:
public void testFactorSet_incremental() {
Set<Integer> set = Set(1, 2, 3, 4, 5);
FactorSet<Integer> factorset = new FactorSet<Integer>(set);
factorset.merge(1, 3);
factorset.merge(3, 5);
factorset.merge(4, 2);
Set<Set<Integer>> expected = Set(Set(1, 3, 5), Set(2, 4));
assertEquals(expected, factorset.factorset());
}

(Don't get confused by the functional-programming style of set constructors. Just open The Scala Book, they do it everywhere!

If you find a better way to do this thing, please let me know.

Followers

Subscribe To My Podcast

whos.amung.us