This lab is about the composition of relations and about Warshall relations for computing transitive closures.
Let $A := \{a_1, a_2, \ldots, a_n\}$ be a finite set of cardinality $n$.
Let $R \subseteq A \times A$ be a binary relation on $A$. The transitive closure of $R$ is a relation $R^{+} \supseteq R$ that contains the minimum number of additional elements of $A \times A$ required to make the relation transitive.
For finite sets $A$, where $n = |A|$. Recall from the textbook that $R^k := R \circ R \circ \cdots \circ R$ is result of composing $R$ with itself $k-1$ times. In other words, $R^{+}$ is the set of pairs that be arrived at through repeated application of the composition operator. An alternative way to compute $R^{+}$ is thus:
The update step needs to be repeated at most $n-1$ times. In other words, $R^+$ can be computed using $n-1$ composition operations and $n-1$ unions.
You are expected to modify these files:
Relations.java – where several static methods like compose, union, and transitive closure are defined but left for you to implement. It also contains some useful debugging tools.Warshall.java – where you should implement a more efficient version of transitive closure based on Warshall relations (optional challenge problem)Implement the methods shown in the provided code.
Here’s a rough guide on how to proceed.
Relations.union. Create a main method and test it before moving on!Relations.compose. Again, test it!Relations.transitiveClosure and test.Warshall.transitiveClosure and test. In the main method, compare the runtime of the two approaches to computing transitive closure.In this lab, a binary relation is represented using a double array of booleans as follows.
Recall that $A := \{ a_1, \ldots a_n \}$ and $R \subseteq A \times A$ is a relation on $A$.
We represent a binary relation $R$ using a double array double[][] R, where R[i][j] == true means that $(a_{i+1}, a_{j+1}) \in R$, and R[i][j] == false means that $(a_{i+1}, a_{j+1}) \notin R$. (Note there is an “off by one” thing going on here. Our set starts couning elements at 1 but double arrays in Java are indexed starting at 0.)
The above descriptions offers a correct but inefficient solution. There is a more efficient way based on Warshall relations.
Consider the following definition of a sequences of relations $W_k$ for $k := 0..n$:
Example: if $\langle a_i, a_2 \rangle \in R$ and $\langle a_2, a_5 \rangle \in R$ and $\langle a_5, a_j \rangle \in R$, then we could say that $\langle a_i , a_j \rangle \in W_5$ because only $a_2$ and $a_5$ need to be used as intermediates to get from $a_i$ to $a_j$ through a sequence of relationships in $R$. However, suppose that $a_\ell$ and $a_m$ are only connected through $a_6$, then $\langle a_\ell, a_m \rangle \not \in W_5$ because it requires using $a_6$ as an intermediate.
It’s important to note that the $k$ subscript on $W_k$ is not the length of the sequence connecting elements, but rather a restriction on which elements are used as intermediates. Of course, such a sequence has length at most $k+2$ (including the endpoints).
Note that $W_n = R^{+}$. This is because $\langle a_i, a_j \rangle \in W_n$ whenever there is a path (using any intermediate elements) from $a_i$ to $a_j$, which is exactly the structure that a transitively closed relation should have.