The code must work from the command line using the Java jdk: being compiled by j
ID: 665248 • Letter: T
Question
The code must work from the command line using the Java jdk: being compiled by javac and run by the java command. There should be two parameters to your program: the first is an input file containing the adjacency matrix of a directed graph; the second is an output file that you will print out to. The project is to determine whether or not a cycle exists in the graph BY
1) Performing a topological sort on the graph
2) ONLY using matrices/arrays and/or linked lists as your data structures. No graph APIs or hash table/map APIs may be used. But, you then can create your OWN derived classes.
3) The code must be yours.
The input file format must follow the following:
first line is the number of vertices n
the next n lines must contain the adjacency matrix row by row, each row containing a binary string of length n
The output file format can be decided by you, but must FIRST output the following:
If the inputted graph has a cycle, then your output will state so and report the first vertex that is known to be part of the cycle.
If the inputted graph does not have a cycle, then your output will state so and provide the listing of all the vertices according to the topological sort.
When submitting your project, only submit the .java files, a sample input file and output file you used that demonstrates that the code works. In addition, it is expected that your code is properly commented.
Explanation / Answer
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class CheckCycle
{
private Stack<Integer> stack;
private int adjacencyMatrix[][];
public CheckCycle()
{
stack = new Stack<Integer>();
}
public void dfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
for (int sourcevertex = 1; sourcevertex <= number_of_nodes; sourcevertex++)
{
for (int destinationvertex = 1; destinationvertex <= number_of_nodes; destinationvertex++)
{
adjacencyMatrix[sourcevertex][destinationvertex] =
adjacency_matrix[sourcevertex][destinationvertex];
}
}
int visited[] = new int[number_of_nodes + 1];
int element = source;
int destination = source;
visited[source] = 1;
stack.push(source);
while (!stack.isEmpty())
{
element = stack.peek();
destination = element;
while (destination <= number_of_nodes)
{
if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1)
{
if (stack.contains(destination))
{
System.out.println("The Graph contains cycle");
return;
}
}
if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)
{
stack.push(destination);
visited[destination] = 1;
adjacencyMatrix[element][destination] = 0;
element = destination;
destination = 1;
continue;
}
destination++;
}
stack.pop();
}
}
public static void main(String...arg)
{
int number_of_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the source for the graph");
source = scanner.nextInt();
CheckCycle checkCycle = new CheckCycle();
checkCycle.dfs(adjacency_matrix, source);
}catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}