Represent antichains with efficient join and meet operations

Question

Some information

I am working on a program that works with basic sets and antichains.

Antichains are subsets of the powerset of a set so that no two elements (sets) in this subset are subset of another element (set) in this subset. For instance {{1},{1,2}} is not an antichain because {1} ⊆ {1,2}.

Some of the most important operations on antichains A and B can be defined as

1. a.join(b) = sup(a ∪ b)
2. a.meet(b) = sup({X ∩ Y | X ∈ a and Y ∈ b})

Where sup is the supremum of an antichain, meaning the smallest antichain bigger than the given set.

Representation thus far

The basic set is represented by a long, bitarray-alike. This means that every element of the set is represented by a 1 in the bitarray. For instance the set {1,2,3} is represented by 7 (the bitarray 111) and the set {1,2,4} is represented by 11 (the bitarray 1011) and so on.

Now I wanted to lift this representation to represent the antichains in a similar way. This means I could represent the antichain {{1},{2,3}} as 1000010 in a bitarray, because the long storing the set {1} is 1 and for {2,3} it is 6 (the indices of the 1's in the bitarray).
Unless I find some better alternatives, I use the BitSet-class to work with this bitarray, hoping to save some time over working with any Collection<T>.

I managed already to define and optimise most of the elementary operations stated before, but they were optimised in an older implementation, simply using a TreeSet, thus not optimised for working with the bitarray.

My questions

1. My question now is whether BitSet is the optimal representation, knowing that these bitarray-representations double in size every time an element to the starting set is added. I also thought of BigInteger for instance, having the advantage to be comparable (something I also need).
2. Also I would like to know whether anybody already did something likely and knows how to implement the join and meet efficiently, using bitarray-properties.

Thanks in advance.

---

Edit:

The code for my join and meet look like this, for the moment:

public AntiChain join(AntiChain ac) {
    AntiChain res = new AntiChain(this);
    for(int i = ac.bitset.nextSetBit(0); i >= 0; i = ac.bitset.nextSetBit(i+1)) {
        res.addAndMakeAntiChain(new BasicSet(i));
    }
    return res;
}

public AntiChain meet(AntiChain ac) {
        AntiChain res = AntiChain.emptyAntiChain(this.getUniverse());
        for(int i = bitset.nextSetBit(0); i >= 0; i = bitset.nextSetBit(i+1))
            for(int j = ac.bitset.nextSetBit(0); j >= 0; j = ac.bitset.nextSetBit(j+1)) 
                res.addAndMakeAntiChain(new BasicSet(j).intersection(new BasicSet(i)));
        return res;
    }

private void addAndMakeAntiChain(BasicSet x) {
    for(int k = bitset.nextSetBit(0); k >= 0; k = bitset.nextSetBit(k+1)) {
        BasicSet a = new BasicSet(k);                         //new BasicSet(7) = {1,2,3}
        if(a.hasAsSubset(x)) return;
        if(x.hasAsSubset(a)) bitset.set(k, false);
    }
    bitset.set(x.toIntRepresentation());                      //{1,2,3}.toLong() = 7
}

Answer 1

Now I wanted to lift this representation to represent the antichains in a similar way. This means I could represent the antichain {{1},{2,3}} as 1000010 in a bitarray, because the long storing the set {1} is 1 and for {2,3} it is 6 (the indices of the 1's in the bitarray).

This sounds wrong: What about {{1, 64}}. IIUYC the index is 2**63 + 1, way too big for a BitSet. If you want an optimized representation for this, consider some primitive long collection (trove4j, colt, hppc, ...).

3. In order to be able to compare my bitarrays, are there any more efficient ways to convert a BitSet to a BigInteger?

The most efficient way will surely be avoiding the conversion. A BitSet can be iterated (in both directions), so you can do a lexicographical comparison directly.

BigInteger result = BigInteger.ZERO;
for(int i = theAntiChain.nextSetBit(0); i >= 0; i = theAntiChain.nextSetBit(i+1))
    result = result.setBit(i);
return result;

This is extremely inefficient, you could create a byte[] instead, fill it, and use new BigInteger(int signum, byte[] magnitude).

Answer 2

Well, I can think of a better way of storing your antichains (still in BitSets). Currently, your sets will be pretty sparse -- high 0:1 ratio.

I'd just concatenate them. Each one is guaranteed to be less than 64 bits long since you are representing them with long values, so I'd do something like this

public static void put(BitSet antiChain, long value) {
    int len = antiChain.length();
    antiChain.clear(antiChain.size() - 1);
    len -= len % 64;
    for (int i = 0; i < 64; i++)
        if ((value & (1 << i)) != 0) antiChain.set(len + i);
    antiChain.set(antiChain.size());
}
public static long get(BitSet antiChain, int index) {
    long value = 0;
    for (int i = 0; i < 64; i++)
        if (antiChain.get(index * 6 + i)) value |= (1 << i);
    return value;
}
public static boolean contains(BitSet antiChain, long value) {
    for (int i = 0; i < antiChain.size() / 64; i++) {
        if (get(antiChain, i) == value) return true;
    }
    return false;
}

which does include one set bit at the end no matter what to make sure that the number of sets contained is explicit; i.e. so that {} != {{}}

For a concrete example, here's what would happen to {{1},{2,3}}. (Note that s(n) refers to the set that n refers to.

• {{1},{2,3},{4,5}} = {s(0b10), s(0b110), s(0b110000)} = {s(2), s(6), s(48)}
• The put function will encode this as 2*2^(64*0) + 6 * 2^(64*1) + 48*2^(64*2) (where ^ represents exponentiation, not XOR).
• The BitSet representing this is {1, 33, 64, 65, 66, 97, 98, 128, 132, 133, 164, 165, 256}

Also, no matter how efficiently you convert a BitSet to a BigInteger, compare will still take place in O(L) time, where L is the length of your antichain in sets. You are probably better off

• If multiple comparisons per antichain: just calling toLongArray() and comparing the long values manually
• If one comparison per antichain: manually looping from high bit to low bit and checking.