Task 1

In Java, a class may extend another class to create a type hierarchy. If class A extends class B, then class A depends on class B; the compiler must first compile class B and then compile class A. Now consider the following code snippet:

public class A extends B {

}

public class B extends C {

}

public class C extends A {

}

Attempting to compile this program will result in a "cyclic inheritance" error. To better depict the issue, we can capture the inheritance relationship in a directed graph where vertices show Java classes. There is a directed edge from $v$ to $u$ if class $u$ extends class $v$.

Notice the cyclic inheritance is exhibited as a directed cycle (closed path) between the vertices.

In this task, you will write a program to perform a sanity check of the type hierarchy in a Java program. That is, to check that there is no cyclic inheritance. For this, we provide you with directed graphs in standard form. Then, it is enough to check whether the given graph contains a (directed) cycle.

Example 1

Input:

4 4
1 2
4 1
2 3
3 1

Output:

true

Explanation

As it can be seen in the image, the graph contains a directed cycle from 1 to 2 to 3 and back to 1.

Example 2

Input:

5 7 
1 2 
2 3 
1 3 
3 4 
1 4 
2 5 
3 5

Output:

false

Explanation

There is no cycle in this graph. This can be seen, for example, by noting that all edges in this graph go from a vertex with a smaller number to a vertex with a larger number.

You must complete the implementation of Task1.hasCyclicInheritance. Notice the method returns a boolean. The above examples are provided as test cases in Task1Test.java file. You are encouraged but not required to add more tests.

To detect cycles in a directed graph, you can use depth-first search algorithm. (Think how?)

In your implementation of Task1.hasCyclicInheritance you must (slightly) modify the pseudocode provided in lecture notes for DFS (see this link) to get the task done. Try your best to keep the modifications minimal. A solution that is vastly different from the provided pseudocode will be flagged as potentially taken from unauthorized resources over the internet.

In the README file, briefly elaborate whether BFS can be used to solve this problem. If your answer is no, explain why. If your answer is yes, elaborate if there is a preference to use DFS over BFS or vice-versa.