From 4008cc6f7eb547d7e93808b9ba9a87fba9acf0e6 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 10 Jul 2020 20:23:19 -0500
Subject: Checking in implementation with stack. Didn't pass the grader. I'm
 checking in first and then start from scratch.

---
 src/main/Toposort.java     |  94 ++++++++++++++++++++++++++++++++++-----
 src/test/ToposortTest.java | 108 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 190 insertions(+), 12 deletions(-)
 create mode 100644 src/test/ToposortTest.java

(limited to 'src')

diff --git a/src/main/Toposort.java b/src/main/Toposort.java
index ede04b4..17cebff 100644
--- a/src/main/Toposort.java
+++ b/src/main/Toposort.java
@@ -1,42 +1,45 @@
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Scanner;
+import java.util.Stack;
+import java.util.Arrays;
 
 public class Toposort {
     private static ArrayList<Integer> toposort(ArrayList<ArrayList<Integer>> adj) {
-        int[] visited = new int[adj.size()];
-        ArrayList<Integer> postv = new ArrayList<>(Collections.nCopies(adj.size(),0));
+        boolean[] visited = new boolean[adj.size()];
+        Integer[] postv = new Integer[adj.size()];
         int[] clock = new int[1];
         dfs(adj, visited, postv, clock);
 
-        ArrayList<Integer> reverse_postv = (ArrayList<Integer>) postv.clone();
-        Collections.sort(reverse_postv, Collections.reverseOrder());
+        Integer[] reverse_postv =  postv.clone();
+        Arrays.sort(reverse_postv, Collections.reverseOrder());
 
-        ArrayList<Integer> order = new ArrayList<Integer>();
+        ArrayList<Integer> order = new ArrayList<>();
 
         for (int n : reverse_postv) {
-            order.add(postv.indexOf(n));
+            order.add(Arrays.asList(postv).indexOf(n));
         }
 
         return order;
+
     }
 
-    private static void dfs(ArrayList<ArrayList<Integer>> adj, int[] visited, ArrayList<Integer> postv, int[] clock) {
+    private static void dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, Integer[] postv, int[] clock) {
         for (int v = 0; v < adj.size(); v++) {
-            if (visited[v] == 0)
+            if (visited[v] == false)
                 explore(adj, v, visited, postv, clock);
         }
     }
 
-    private static void explore(ArrayList<ArrayList<Integer>> adj, int v, int[] visited, ArrayList<Integer> postv, int[] clock) {
-        visited[v] = 1;
+    private static void explore(ArrayList<ArrayList<Integer>> adj, int v, boolean[] visited, Integer[] postv, int[] clock) {
+        visited[v] = true;
         clock[0] = clock[0] + 1;
 
         for (int n : adj.get(v)) {
-            if (visited[n] == 0)
+            if (visited[n] == false)
                 explore(adj, n, visited, postv, clock);
         }
-        postv.set(v, clock[0]);
+        postv[v] =  clock[0];
         clock[0] = clock[0] + 1;
 
     }
@@ -60,5 +63,72 @@ public class Toposort {
             System.out.print((x + 1) + " ");
         }
     }
+
+    static ArrayList<Integer> postOrder(ArrayList<ArrayList<Integer>> adj) {
+        boolean[] visited = new boolean[adj.size()];
+        ArrayList<Integer> postv = new ArrayList<>(Collections.nCopies(adj.size(), 0));
+        int[] clock = new int[1];
+        clock[0] = clock[0] + 1;
+        for (int v = 0; v < adj.size(); v++) {
+            exploreIterative(adj, v, visited, postv, clock);
+        }
+        return postv;
+    }
+
+    private static void exploreIterative(ArrayList<ArrayList<Integer>> adj, int v, boolean[] visited, ArrayList<Integer> postv, int[] clock) {
+        if (visited[v] == false) {
+            // prev[v] = clock[0]
+            boolean[] inStack = new boolean[adj.size()];
+            clock[0] = clock[0] + 1;
+            visited[v] = true;
+            inStack[v] = true;
+            Stack<Integer> vertexStack = new Stack<>();
+            vertexStack.push(v);
+
+            while (vertexStack.isEmpty() == false) {
+                int tempVertex = vertexStack.peek();
+//                if (tempVertex != v) {
+//                    visited[tempVertex] = true;
+//                    // prev[v] = clock[0]
+//                    clock[0] = clock[0] + 1;
+//                }
+                if (tempVertex != v && visited[tempVertex]) {
+                    vertexStack.pop();
+                    continue;
+                }
+                if (adj.get(tempVertex).size() == 0) {
+                    if (tempVertex != v) {
+                        // prev[tempVertex] = clock[0];
+                        clock[0] = clock[0] + 1;
+                        visited[tempVertex] = true;
+                    }
+                    postv.set(tempVertex, clock[0]);
+                    clock[0] = clock[0] + 1;
+                    vertexStack.pop();
+                } else {
+                    boolean allEdgesFollowed = true;
+                    for (int i : adj.get(tempVertex)) {
+                        if (visited[i] == false) {
+//                            visited[i] = true;
+                            // prev[i] = clock[0]
+                            if (inStack[i] == false) {
+                                inStack[i] = true;
+                                vertexStack.push(i);
+                            }
+                            allEdgesFollowed = false;
+                        }
+                    }
+                    if (allEdgesFollowed) {
+                        visited[tempVertex] = true;
+                        if (postv.get(tempVertex) == 0)
+                            postv.set(tempVertex, clock[0]);
+                        clock[0] = clock[0] + 1;
+                        vertexStack.pop();
+                    }
+                }
+            }
+        }
+    }
+
 }
 
diff --git a/src/test/ToposortTest.java b/src/test/ToposortTest.java
new file mode 100644
index 0000000..e38d3bc
--- /dev/null
+++ b/src/test/ToposortTest.java
@@ -0,0 +1,108 @@
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class ToposortTest {
+
+    @Test
+    void test() {
+        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+        for (int i = 0; i < 4; i++) {
+            adj.add(new ArrayList<>());
+        }
+
+        adj.get(0).add(1);
+        adj.get(2).add(0);
+        adj.get(3).add(0);
+
+        ArrayList<Integer> results = new ArrayList<Integer>(Arrays.asList(4, 3, 6, 8));
+        assertEquals(results, Toposort.postOrder(adj));
+    }
+
+    @Test
+    void test1() {
+        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+        for (int i = 0; i < 5; i++) {
+            adj.add(new ArrayList<>());
+        }
+
+        adj.get(1).add(0);
+        adj.get(1).add(2);
+        adj.get(1).add(3);
+        adj.get(1).add(4);
+
+        adj.get(2).add(0);
+        adj.get(2).add(3);
+        adj.get(2).add(4);
+
+        adj.get(3).add(0);
+        adj.get(3).add(4);
+
+        adj.get(4).add(0);
+
+        ArrayList<Integer> results = new ArrayList<Integer>(Arrays.asList(2, 7, 6, 5, 4));
+        assertEquals(results, Toposort.postOrder(adj));
+    }
+
+    @Test
+    void test2() {
+        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+        for (int i = 0; i < 5; i++) {
+            adj.add(new ArrayList<>());
+        }
+
+        adj.get(1).add(0);
+        adj.get(1).add(2);
+        adj.get(1).add(4);
+        adj.get(1).add(3);
+
+        adj.get(2).add(0);
+        adj.get(2).add(3);
+        adj.get(2).add(4);
+
+        adj.get(3).add(4);
+        adj.get(3).add(0);
+
+        adj.get(4).add(0);
+
+        ArrayList<Integer> results = new ArrayList<Integer>(Arrays.asList(2, 7, 6, 5, 4));
+        assertEquals(results, Toposort.postOrder(adj));
+    }
+
+    @Test
+    void test10() {
+        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+        for (int i = 0; i < 10; i++) {
+            adj.add(new ArrayList<>());
+        }
+
+        adj.get(9).add(1);
+        adj.get(9).add(7);
+        adj.get(4).add(3);
+        adj.get(2).add(1);
+        adj.get(7).add(3);
+        adj.get(9).add(3);
+        adj.get(0).add(1);
+        adj.get(8).add(6);
+        adj.get(1).add(7);
+        adj.get(2).add(9);
+        adj.get(6).add(5);
+        adj.get(0).add(4);
+        adj.get(0).add(7);
+        adj.get(0).add(5);
+        adj.get(0).add(8);
+        adj.get(2).add(5);
+        adj.get(6).add(9);
+        adj.get(8).add(3);
+        adj.get(8).add(4);
+        adj.get(4).add(2);
+
+        ArrayList<Integer> results = new ArrayList<Integer>(Arrays.asList(13, 7, 9, 5, 10, 3, 11, 6, 12, 8));
+        assertEquals(results, Toposort.postOrder(adj));
+    }
+
+}
\ No newline at end of file
-- 
cgit v1.2.3