/* Input (G=(V,E)) * for each v in V do status[v] <- 0 * for each v with no out links * Visit(v) * * Visit(v) * Status[v] <- 1 * for each u with (u, V) in E * if status[u] == 1 then end (Cyclic graph) * if status[u] == 0 then visit(u) * Status[v] <- 2 * print V * */ import java.util.Scanner; public class TopMain { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //Scanner variable used to take user input boolean startExists; //to check whether there are nodes that have no out links or not boolean flag; // a flag to check if input is correct (y or n) int nodeNumber; // number of nodes in the graph boolean isCyclic; //used to determine whether a graph is cyclic or not String linked; //used to store user input regarding the link of 2 nodes(y or n) TopFuncClass Topobj; //Object(instance) for the TopFuncClass to implement function from there System.out.println("Enter the number of nodes: "); nodeNumber = sc.nextInt(); //input for number of nodes boolean [][] Neighbors = new boolean [nodeNumber][nodeNumber]; //Adjacency matrix boolean [] outEdges = new boolean[nodeNumber]; //Array to keep track of which nodes have out nodes and which don't for (int i = 0; i < nodeNumber; i ++) outEdges[i] = false; //initializing "outEdges" with values of false System.out.println("Specify which nodes are linked and which are not"); //Code to ask the user about linked nodes and fill it in the "neighbor" boolean array as an adjacency Matrix for(int i= 0; i < nodeNumber ; i++) { // a loop to go through all the nodes for(int j = 0; j < nodeNumber ; j++) { // an inner loop to compare each node with the node in the outer loop if (i == j) continue; //So the program doesn't compare a node with itself flag = true; System.out.println("Is node " + (i+1) + " linked with node " + (j+1) +"? (y, n)"); linked = sc.next(); while(flag) { //while loop to repeat this input for the link of 2 nodes if the input is not y or n if(linked.equals("y")) { //case where the nodes are actually connected Neighbors[i][j] = true; outEdges[i] = true;//marking that this node has an out link flag = false; } else if(linked.equals("n")) {// case where nodes are not connected Neighbors[i][j] = false; flag = false; } else { //case input incorrect System.out.println("Please enter y or n"); linked = sc.next(); } } } } Topobj = new TopFuncClass(Neighbors, nodeNumber);//feeding the adjacency matrix and the node number to the other class to work with the "Visit(V)" function startExists = false; isCyclic =false; //assuming that the graph is not cyclic yet for(int i = 0; i < nodeNumber; i ++) {//iterating through all nodes to check which node has no out links if(!outEdges[i]) { startExists = true; isCyclic = Topobj.Visit(i); } if(isCyclic) break; //in case graph is cyclic } //case where all nodes have a out links which means it is a cyclic graph if(!startExists) System.out.println("There are no nodes with no out links which means that this graph is cyclic!"); } } public class TopFuncClass { int nodeNumber; //number of nodes int [] Status; //Store the whether each node is visited(1), not visited(0) and finished(2) boolean [][] Adjacency; //adjacency matrix public TopFuncClass(boolean [][] Array, int nodeNumber) { //initializing values to be used in the public void Visit(int V){} function this.nodeNumber = nodeNumber; Status = new int[nodeNumber]; Adjacency = new boolean[nodeNumber][nodeNumber]; for(int i = 0; i < nodeNumber; i++) { Status[i] = 0; } for(int i = 0; i < nodeNumber; i++) { //copying the adjacency Matrix into this class to be used in "Visit" function for(int j = 0; j < nodeNumber; j++) { if(i == j) continue; else Adjacency[i][j] = Array [i][j]; } } } boolean isCyclic;//To deal with a bug where it would print what nodes it visited regardless if it was cyclic or not public boolean Visit(int V) { //depth first strategy integrated to suit the topological sorting algorithm Status[V] = 1; //Setting The node V as visited for(int j = 0; j < nodeNumber; j++) { //second loop to compare outer node with possibly connected nodes if(V == j) continue; //So the program doesn't compare a node with itself else if(Adjacency[j][V] && Status[j] == 1) { //case where graph is cyclic (only directed graphs are allowed) System.out.println("This Graph is cyclic!"); isCyclic = true; break; } else if(Adjacency[j][V] && Status[j] == 0) Visit(j); //If the node is not visited and is adjacent to "V", then visit the node } if(!isCyclic) { //case where graph is not cyclic System.out.println("Node " + (V+1)+ " has been visited"); Status[V] = 2; //after all the related nodes to the starting node have been visited, it is set to finished, as in, this node should not be visited again return false; //Needed since the function has been declared as an int function } else return true; //case where graph is cyclic } }

Topological Sorting alogrithm