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 `A`_{1}

of `A`

that first, if `x∈A`_{1}

and `y∈A`_{1}

then `xRy`

, and second, if `x∈A`_{1}

and `xRy`

then `y∈A`_{1}

**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.

## No comments:

Post a Comment