/* * The graph will contain N node and represented as an adjacency list. This * method is to determine if the ordering provided is a legal topological * ordering. You may assume that the ordering will be of length N and contain * all the node values 0, 1, ... N-1. The ordering is a legal topological * ordering if, for each value, v, in the ordering, all the incoming arcs to v * appear to the left of v in the ordering. */ @Problem(doThis = false, pts = 5) // Graph 4 @TestCase(io = "([[4],[],[3],[1], [2]], [0,4,2,3,1]) -> true") @TestCase(io = "([[4],[],[3],[1],[2]], [0,4,2,1,3]) -> false") // Graph 6 @TestCase(io="([[1,2,4],[2,3,4],[],[4],[]], [0,1,2,3,4]) -> true") @TestCase(io="([[1,2,4],[2,3,4],[],[4],[]], [0,1,3,4,2]) > true") @TestCase(io="([[1,2,4],[2,3,4],[],[4],[]], [0,1,4,3,2])-> false") public static boolean is ToplogicalOrdering(TreeSet[] adjlist, ArrayList ordering) { int N = adjlist.length; int n = ordering.size(); Stack stk = new Stack(); Set visited = new TreeSet(); // // while (!stk.isEmpty()){ Integer vertex = stk.peek(); TreeSet connections = adjlist[vertex]; for (Integer v: connections) { if (!visited.contains(v)) { visited.add(v); stk.push(v); return false; } } return true; Graph #4 4 N 3 Graph #6 0 2 3 /* * The graph will contain N node and represented as an adjacency list. This * method is to determine if the ordering provided is a legal topological * ordering. You may assume that the ordering will be of length N and contain * all the node values 0, 1, ... N-1. The ordering is a legal topological * ordering if, for each value, v, in the ordering, all the incoming arcs to v * appear to the left of v in the ordering. */ @Problem(doThis = false, pts = 5) // Graph 4 @TestCase(io = "([[4],[],[3],[1], [2]], [0,4,2,3,1]) -> true") @TestCase(io = "([[4],[],[3],[1],[2]], [0,4,2,1,3]) -> false") // Graph 6 @TestCase(io="([[1,2,4],[2,3,4],[],[4],[]], [0,1,2,3,4]) -> true") @TestCase(io="([[1,2,4],[2,3,4],[],[4],[]], [0,1,3,4,2]) > true") @TestCase(io="([[1,2,4],[2,3,4],[],[4],[]], [0,1,4,3,2])-> false") public static boolean is ToplogicalOrdering(TreeSet[] adjlist, ArrayList ordering) { int N = adjlist.length; int n = ordering.size(); Stack stk = new Stack(); Set visited = new TreeSet(); // // while (!stk.isEmpty()){ Integer vertex = stk.peek(); TreeSet connections = adjlist[vertex]; for (Integer v: connections) { if (!visited.contains(v)) { visited.add(v); stk.push(v); return false; } } return true; Graph #4 4 N 3 Graph #6 0 2 3