How to implement a Poset in Java

Inspired by this question in Stack Overflow, I decided to try my hand at implementing a Poset in Java. In order to understand how to do this, we need to define some concepts.

Basic Poset terminology

Poset definition

A Poset is a set of elements with a binary relation defined between them (not necessarily between all of them) that must satisfy the following rules:

• reflexivity (every element is related to itself)
• antisymmetry (relationships between elements can only occur in one direction)
• transitivity (if an element a is related to another element b, then a is also related to all elements b is related to)

A binary relation with these properties is called “partial order” and is denoted by ≤ :

• partial implies that not all elements are necessarily related to some other
• order makes reference to the fact that the above properties define some kind of precedence among the elements of the set.

Incidence matrix

The binary relation between the different elements can be represented as a square binary matrix (the elements are ones and zeros) where rows and columns are indexed by the elements of the set.

Such a matrix is also called incidence matrix:

• 1 means that the elements corresponding to those indexes are related
• 0 means that they are not.

For instance, given a set of 4 elements {a, b, c, d} and the incidence matrix:

   

these are the corresponding binary relations:

                              a ≤ a
                              a ≤ b
                              b ≤ b
                              b ≤ c
                              c ≤ c
                              d ≤ a
                              d ≤ d

Because of the:

• reflexivity property, all elements in the main diagonal must be 1.
• antisymmetry property, elements in symmetric positions with respect to the main diagonal cannot be both 1.

The above example is the so-called transitive reduction, a simplified version of the incidence matrix without the transitive relations.

After applying the transitive property (transitive expansion), the above example becomes:

   

Topological sort

A Poset can be interpreted as a directed acyclic graph (DAG) in which the shortest distance between all pairs of elements that are connected is always 1 (because of the transitivity property). Therefore, it is possible to compute its topological sort:

topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering

In our example, the topological sort is: [d, a, b, c].

The topological sort is ambiguous for elements that are not connected between them. For instance, if the incidence matrix were

   

then any of these lists would be a valid topological sort: [d, a, b, c], [c, d, a, b], [d, a, c, b]

Now that we have become familiar with the notion of Poset, let’s move on to the actual implementation.

Type hierarchy of Set in Java

In Java, a set can be implemented by extending AbstractSet, which provides a skeletal implementation of the Set interface. Concretely, AbstractSet implements equals and hashCode, and extends AbstractCollection, which in turn provides a skeletal implementation of the Collection interface. According to the API docs

To implement an unmodifiable collection, the programmer needs only to extend this class [AbstractCollection] and provide implementations for the iterator and size methods. (The iterator returned by the iterator method must implement hasNext and next.)

The above quote is justified because:

• the default implementation of the method add in AbstractCollection is

public boolean add(E e) {
    throw new UnsupportedOperationException();
}

• the implementation of the method addAll is based on add (this is the famous example explained on Effective Java when discussing the benefits of composition over inheritance)
• all other default implementations to check for membership or remove elements are based on Iterator
• the default implementation of the method Iterator.remove is

public boolean add(E e) {
    throw new UnsupportedOperationException();
}

Here is the type hierarchy of our Poset

Poset implementation

This implementation is an unmodifiable set that returns its elements in topological order when iterating over them. Although the elements of the set can still be mutated, that will not affect its topological sort. The following image shows the different members of the class defined or overridden.

In order to create a Poset, we need a list of elements and the corresponding incidence matrix. The signature of the constructor is

Poset(List<E> elements, int[][] incidenceMatrix)

Once the Poset is created, it is possible to iterate over its elements in topological order and to get the incidence matrices corresponding to the transitive expansion and the transitive reduction.

Poset<String> poset = new Poset<>(Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h"), new int[][] {
      {1, 0, 0, 1, 0, 0, 0, 0},
      {0, 1, 0, 1, 1, 0, 0, 0},
      {0, 0, 1, 0, 1, 0, 0, 1},
      {0, 0, 0, 1, 0, 1, 1, 1},
      {0, 0, 0, 0, 1, 0, 1, 0},
      {0, 0, 0, 0, 0, 1, 0, 0},
      {0, 0, 0, 0, 0, 0, 1, 0},
      {0, 0, 0, 0, 0, 0, 0, 1}
    });

    //Elements in topological sort
    System.out.println(new ArrayList<>(poset));

    //Transitive expansion
    System.out.println(Arrays.deepToString(poset.getTransitiveExpansion()));

    //Transitive reduction
    System.out.println(Arrays.deepToString(poset.getTransitiveReduction()));

Here’s the output of the above snippet:

[b, a, c, d, e, f, g, h]

(manually formatted)
[
[1, 0, 0, 1, 0, 1, 1, 1], 
[0, 1, 0, 1, 1, 1, 1, 1], 
[0, 0, 1, 0, 1, 0, 1, 1], 
[0, 0, 0, 1, 0, 1, 1, 1], 
[0, 0, 0, 0, 1, 0, 1, 0], 
[0, 0, 0, 0, 0, 1, 0, 0], 
[0, 0, 0, 0, 0, 0, 1, 0], 
[0, 0, 0, 0, 0, 0, 0, 1]
]

(manually formatted)
[
[1, 0, 0, 1, 0, 0, 0, 0], 
[0, 1, 0, 1, 1, 0, 0, 0], 
[0, 0, 1, 0, 1, 0, 0, 1], 
[0, 0, 0, 1, 0, 1, 1, 1], 
[0, 0, 0, 0, 1, 0, 1, 0], 
[0, 0, 0, 0, 0, 1, 0, 0], 
[0, 0, 0, 0, 0, 0, 1, 0], 
[0, 0, 0, 0, 0, 0, 0, 1]
]

And here’s the corresponding graph representation (generated with graphviz):

How to calculate the topological sort

The algorithm to calculate the topological order is based on the following considerations:

1. if a ≤ b, then deg(a) is greater or equal to deg(b)

whereas deg is the degree.

The above statement is true because if a ≤ b, then, due to the transitivity property, a will have at least one more ≤ than b.

2. given the transitive expansion of the incidence matrix, the sum of the elements of each row is equivalent to the degree of the corresponding vertex

As a result, the algorithm to calculate the topological sort consists in sorting the rows of the transitive expansion by the sum of its elements.

From the above, it follows that two elements with the same degree cannot be connected. Therefore, the relative position of elements with the same degree is irrelevant in the topological sort.

Calculation of the transitive expansion

Given that the transitive expansion of the incidence array is at the heart of the algorithm to calculate the topological sort, it is worth taking a look at the process to calculate it.

Applying the transitivity property on the incidence matrix is equivalent to doing a bitwise OR between a row and the rows it points to. Every time a row is updated, all the rows pointing to it must be updated.

To implement this pattern of cascading changes, the implementation makes use of the Observer pattern:

• the observed subject is the row under consideration
• the observers or subscribers are the other rows that point to it

Finally, after completing the transitive expansion, it is necessary to verify that the resulting Poset still complies with the antisymmetry property.

Definition of equality

Two posets are equal if they have the same elements and the same transitive expansion of the incidence matrix.

The method equals is overridden in accordance with that criterion:

• it relies on the definition of AbstractSet.equals() to check for membership of the elements
• in addition, it compares the transitive expansion of the corresponding incidence matrices

Of course, the method hashCode is overridden accordingly too.

It is worth noting that two equal posets may return their elements in different order due to the already mentioned ambiguity of the topological sort when it comes to elements not connected among them.

Iterator implementation

The elements of the Poset are stored internally in an ArrayList in topological order. The iterator returns the elements of that list.

Instead of using ArrayList.iterator(), we define our own version as the former allows mutations via Iterator.remove().

The complete implementation can be found on https://github.com/falvarezb/Poset/tree/postPoset